Towards Metric-Faithful Neural Graph Matching

요약

본 논문은 구조적 그래프 유사성을 측정하는 NP-hard 문제인 Graph Edit Distance (GED)를 근사하는 신경 그래프 매칭 아키텍처의 인코더 기하학 역할을 이론적으로 분석합니다. 연구진은 그래프 유사성 예측기와 정렬 기반 두 가지 범주의 신경 GED 추정기에 대해, 특정 조건 하에서 bi-Lipschitz 인코더가 제어된 GED 대리값(surrogate)을 제공하고 순위 안정성을 개선함을 증명했습니다. 이를 바탕으로 FSW-GNN이라는 bi-Lipschitz WL-등가 인코더를 제안하며, 이 변형이 기존 아키텍처에 적용되었을 때 GED 예측 및 순위 지표에서 유의미한 성능 향상을 보임을 입증합니다.

핵심 포인트

• 신경 그래프 매칭은 NP-hard인 Graph Edit Distance (GED)를 근사하는 것이 목표이다.
• 제안된 이론적 프레임워크는 신경 GED 추정기의 인코더 기하학이 예측 품질과 어떻게 연결되는지 설명한다.
• 그래프 유사성 예측기 및 정렬 기반 방법 모두에서 bi-Lipschitz 인코더가 안정적인 성능 개선을 가져온다.
• FSW-GNN은 bi-Lipschitz WL-등가 인코더로, 기존 신경 GED 아키텍처에 쉽게 통합할 수 있는(drop-in replacement) 솔루션이다.
• 실험 결과는 개선된 표현 기하학이 GED 예측 및 순위 지표의 성능 향상에 결정적인 역할을 함을 보여준다.