Towards Metric-Faithful Neural Graph Matching

Graph Edit Distance (GED) 는 구조적 그래프 유사성을 측정하는 기본적이지만 NP-hard인 거리입니다. 최근 신경 그래프 매칭 아키텍처는 먼저 Graph Neural Network (GNN) 으로 그래프를 인코딩한 후, 그래프 레벨 회귀 헤더 또는 매칭 기반 정렬 모듈을 적용하여 GED 를 근사합니다. 상당한 아키텍처적 진보에도 불구하고, 신경 GED 추정에서 인코더 기하학의 역할은 여전히 잘 이해되지 않았습니다. 이 논문에서는 두 가지 넓은 범주의 신경 GED 추정기인 그래프 유사성 예측기와 정렬 기반 방법의 경우 인코더 기하학을 GED 추정 품질과 연결하는 이론적 프레임워크를 개발합니다. doubly-stochastic metric $d_{\mathrm{DS}}$ 가 GED 와 비교 가능한 고정된 그래프 컬렉션에서, 그래프 레벨 bi-Lipschitz 인코더는 제어된 GED surrogate 를 제공하고 개선된 순위 안정성을 제공합니다; 매칭 기반 추정기의 경우, 노드 레벨 bi-Lipschitz 기하학은 인코더 유도 정렬 비용과 최적화된 정렬 목표에 전달됩니다. 우리는 이 관점을 FSW-GNN 을 사용하여 구체화합니다. FSW-GNN 은 bi-Lipschitz WL-등가 인코더로, 대표적인 신경 GED 아키텍처에서 drop-in replacement 으로 사용됩니다. 대표적인 기준선과 벤치마크 데이터셋을 통해, 결과적인 기하학 인식 변형은 GED 예측 및 순위 지표에 유의미한 개선 효과를 보입니다. 훈련되지 않은 인코더의 faithfulness 사례 연구, ablation 과 transfer 실험은 이러한 이득이 개선된 표현 기하학에서 비롯됨을 지지하며, 인코더 기하학을 신경 그래프 매칭에 유용한 설계 원칙으로 위치시킵니다.