부분 그래프 매칭을 위한 미분 가능한 Top-K를 통한 딥러닝

그래프 매칭(GM)은 매칭된 노드 간의 노드 및 엣지 위계적 유사도를 최대화함으로써 그래프 간의 노드 매칭을 탐색하는 것을 목표로 한다. NP-완전 문제인 이 문제는 특히 시각 문제에서 흔히 나타나는 두 그래프 내에 이상치 노드(outlier nodes)가 존재함에 따라 더욱 도전적인 과제가 된다. 그러나 기존의 유사도 최대화 기반 접근법은 잘못된 매칭을 억제하기 위한 체계적인 방법이 부족하여, 수작업으로 설정한 임계값(thresholding)을 통해 이상치를 제거하는 방식에 의존한다. 이러한 한계는 이상치가 없는 이상적인 환경에서 뛰어난 성능을 보이는 신경망 기반 GM 솔버에도 그대로 이어진다. 본 논문에서는 주어진 또는 추정된 내부점(inlier) 수 k에 기반하여 부분적 그래프 매칭(partial GM) 문제를 상위-k 선택(top-k selection) 문제로 재정의하는 새로운 접근법을 제안한다. 구체적으로, 최적 운반(optimal-transport) 계층에서 효과적인 경사 하강법을 가능하게 하는 미분 가능한 상위-k 모듈을 설계하였으며, 이는 최신의 깊은 GM 파이프라인인 이차형 매칭 네트워크 NGMv2 및 선형 매칭 네트워크 GCAN에 쉽게 통합될 수 있다. 동시에, k를 자동 추정할 수 있도록 주의 집중(attention-fused) 집계 레이어를 개발하여 실제 환경에서의 이상치에 강건한 매칭을 가능하게 했다. 마지막으로, IMC-PT 스테레오 매칭 데이터셋에서 유래한 새로운 벤치마크인 IMC-PT-SparseGM을 재구성하고 공개하였다. 이 새로운 벤치마크는 실제 세계에서 얻은 다양한 스케일을 가진 그래프와 부분 매칭 인스턴스를 포함하고 있다. 실험 결과, 제안한 방법이 기존의 부분 매칭 기법들에 비해 주요 벤치마크에서 우수한 성능을 보였다.