AGDN: 비등방성 그래프 확산 네트워크 (Anisotropic Graph Diffusion Network)를 이용한 외판원 문제 (TSP)

외판원 문제 (Traveling Salesman Problem, TSP)는 조합 최적화 (combinatorial optimization)의 초석이며 많은 실질적인 시나리오에서 발생합니다. TSP를 위해 그래프 기반 학습 접근 방식이 탐구되어 왔지만, 그래프 구조를 어떻게 더 효과적으로 활용할 것인가에 대한 문제는 여전히 미해결 상태로 남아 있습니다. 본 논문에서는 TSP를 해결하기 위해 설계된 새로운 그래프 신경망 (Graph Neural Network, GNN) 프레임워크인 비등방성 그래프 확산 네트워크 (Anisotropic Graph Diffusion Network, AGDN)를 제시합니다. 우리의 방법은 두 가지 핵심적인 어려움을 다룹니다: (1) 완전 연결된 (fully connected) TSP 그래프에서 정보가 풍부한 위상적 사전 정보 (topological prior)의 부족, 그리고 (2) 흔히 사용되는 그래프 희소화 (graph sparsification) 기술을 적용한 후 최적해에서 연결된 노드들을 놓치게 되는 문제. 이러한 문제들을 극복하기 위해, 우리는 노드 유사도 (node similarity)와 쌍별 거리 (pairwise distance)를 결합하는 MixScore 전이 행렬 (transition matrix)을 구축하며, 여러 홉 (multiple hops)에 걸쳐 효율적인 정보 교환을 지원하는 비등방성 그래프 확산 (anisotropic graph diffusion) 전략을 개발합니다. 다양한 인스턴스 크기와 노드 분포를 아우르는 포괄적인 실험을 통해, AGDN는 계산 시간을 경쟁력 있게 유지하면서도 기존 방법들을 일관되게 능가함을 보여줍니다. 또한, AGDN는 학습 중에 보지 못한 문제 크기와 분포로도 잘 일반화됩니다. 구현 코드는 다음에서 공개적으로 사용할 수 있습니다: https://github.com/LabRAI/AGDN.