신경 그래프 매칭 네트워크: Lawler의 이차 할당 문제 학습 및 하이퍼그래프와 다중 그래프 매칭으로의 확장

그래프 매칭은 엣지 간 친화성 행렬을 기반으로 하는 조합 최적화 문제로, 일반적으로 Lawler의 이차 할당 문제(QAP)로 표현될 수 있습니다. 본 논문에서는 친화성 행렬(즉, 연관 그래프)을 직접 학습하는 QAP 네트워크를 제시하여, 매칭 문제를 제약 조건이 있는 정점 분류 작업으로 변환합니다. 연관 그래프는 정점 분류를 위해 임베딩 네트워크에서 학습되며, 이어서 Sinkhorn 정규화와 크로스 엔트로피 손실 함수를 사용하여 엔드투엔드 학습이 이루어집니다. 우리는 또한 그래프의 크기가 일치하지 않는 경우를 처리하기 위해 더미 노드를 도입하고, Sinkhorn 기반 매칭 인식 제약 조건을 추가하여 연관 그래프의 임베딩 모델을 개선하였습니다. 최선의 지식에 따르면, 이는 일반적인 Lawler의 QAP를 직접 학습하는 첫 번째 네트워크 중 하나입니다. 최근의 딥 매칭 방법들은 두 그래프 각각의 노드/엣지 특징 학습에 초점을 맞추고 있는 반면, 우리의 접근 방식은 다르다는 점을 강조합니다. 또한 우리는 네트워크를 하이퍼그래프 매칭과 다중 그래프 매칭으로 확장하는 방법도 설명합니다. 실험 결과는 합성 그래프와 실제 이미지 모두에서 그 효과성을 입증하였습니다. 합성 데이터와 QAPLIB 벤치마크에서 순수 QAP 작업에 대한 결과는 우리의 방법이 경쟁력을 가지며, 심지어 시간 비용이 크게 적게 들면서도 최신 그래프 매칭 및 QAP 솔버들을 능가할 수 있음을 보여줍니다. 프로젝트 홈페이지는 http://thinklab.sjtu.edu.cn/project/NGM/index.html 에서 제공됩니다.