AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

기술 요약: AGDN – 이방성 그래프 확산을 이용한 외판원 문제 해결 학습

문제 정의
외판원 문제(Traveling Salesman Problem, TSP)는 일련의 도시들을 정확히 한 번씩만 방문하고 출발지로 돌아오는 가장 짧은 경로를 찾는 근본적인 조합 최적화 문제이다. 그래프 신경망(GNN)은 TSP의 위상적 탐색 공간과 부합하기 때문에 효과적인 도구로 부상했으나, 현재의 학습 기반 접근 방식들은 두 가지 결정적인 한계에 직면해 있다:

1. 정보가 풍부한 위상적 사전 정보(Topological Prior)의 부재: 표준적인 그래프 학습 작업과 달리, TSP 인스턴스는 일반적으로 완전 연결 그래프(fully connected graphs)로 모델링된다. 이러한 구조는 최적해와 관련된 위상적 사전 정보를 내포하고 있지 않아, 모델이 솔루션과 관련 있는 정보와 노이즈를 구분하는 것을 어렵게 만든다.
2. 희소화(Sparsification)를 통한 정보 교환의 손실: 계산 복잡성을 관리하기 위해 기존 방법들은 종종 TSP 그래프를 희소화한다(예: $k$-NN 사용). 그러나 이 과정은 최적해의 일부인 에지를 제거할 위험이 있다. 최적의 노드 쌍이 연결 해제될 때, 얕은 GNN은 필요한 다중 홉(multi-hop) 관계를 포착하기 어려우며, 깊은 GNN은 오버 스무딩(over-smoothing) 및 오버 스쿼싱(over-squashing) 문제를 겪는다.

방법론: 이방성 그래프 확산 네트워크 (Anisotropic Graph Diffusion Network, AGDN)
저자들은 그래프 희소화에 의존하지 않고 TSP를 해결하기 위해 설계된 프레임워크인 AGDN를 제안한다. 이 방법론은 네 가지 핵심 구성 요소로 이루어져 있다:

1. MixScore 전이 행렬 (MixScore Transition Matrix):
   표준적인 인접 행렬이나 단순 거리 기반 전이를 사용하는 대신, AGDN는 MixScore 전이 행렬을 구축한다. 이 행렬은 두 가지 유형의 정보를 통합한다:

   • 쌍별 거리(Pairwise Distance): 기하학적 근접성을 포착하기 위해 가우시안 커널($\exp(-e_{ij}/\sigma)$)을 통해 인코딩된다.
   • 노드 유사도(Node Similarity): 소스(Source, $S$) 공간과 데스티네이션(Destination, $D$)이라는 두 개의 서로 다른 잠재 공간 내 노드 임베딩으로부터 유도된다.
     이 행렬은 임베딩의 내적($H_S H_D^T$)과 정규화된 거리 행렬($T_{rw}$)을 결합하고 이를 다층 퍼셉트론(MLP)으로 처리하여 형성된다. 이를 통해 모델은 기하학적 거리와 학습된 구조적 유사성을 모두 반영하는 전이 확률을 인코딩할 수 있다.

2. 이방성 그래프 확산 (Anisotropic Graph Diffusion):
   AGDN는 정보를 들어오는($S$) 방향과 나가는($D$) 방향으로 각각 분리하여 전파하는 확산 메커니즘을 채택한다.

   • 다중 홉 어텐션 (Multi-hop Attention): 프레임워크는 단일 컨볼루션 레이어 내에서 $K$개의 홉으로부터 정보를 집계하기 위해 학습 가능한 다중 홉 어텐션(매개변수 $\theta_k$로 표현됨)을 활용한다. 이는 여러 레이어를 쌓아야 할 필요성을 없애 오버 스무딩을 완화한다.
   • 이방성 (Anisotropy): 별도의 $S$ 및 $D$ 공간을 유지함으로써, 모델은 방향성 정보 흐름을 포착하여 노드 특성화의 정밀도를 높인다.

3. 노드 정보 집계 (Node Information Aggregation):
   확산 후, $S$ 공간과 $D$ 공간의 임베딩이 집계된다. 저자들은 $S$ 공간의 임베딩이 쿼리(query) 역할을 하고 $D$ 공간의 임베딩이 키(key) 및 값(value) 역할을 하는 셀프 어텐션 메커니즘을 사용한다. 이러한 비대칭적 집계 이후, 최종적인 노드 임베딩을 생성하기 위해 최종 MLP가 적용된다.

4. 솔루션 식별 (Solution Identification):
   집계된 노드 임베딩은 외적(outer product)을 통해 에지 임베딩을 생성하는 데 사용된다. 에지 수준의 어텐션 메커니즘은 이 임베딩들의 가중치를 재조정하여 중요한 에지를 강조한다. 마지막으로, MLP는 각 에지가 최적의 투어의 일부일 확률을 나타내는 히트맵을 예측한다. 이 히트맵은 몬테카를로 트리 탐색(MCTS)을 유도하여 최종 솔루션을 구성한다. 모델은 정답 히트맵에 대한 지도 학습(cross-entropy) 또는 기대 투어 길이를 최소화하는 비지도 학습을 통해 최적화된다.

주요 기여

• 문제 특성화: 본 논문은 현재의 GNN 접근 방식, 특히 그래프 희소화로 인한 단절과 완전 연결된 TSP 그래프에서의 정보 있는 사전 정보 부족 문제를 식별하고 공식화하였다.
• 알고리즘 설계: MixScore 전이 행렬과 이방성 그래프 확산 메커니즘을 도입하였다. 이러한 혁신은 희소화 없이도 효율적인 다중 홉 정보 전파를 가능하게 하여 최적 노드 쌍 간의 연결성을 보존한다.
• 실증적 검증: 광범가한 실험을 통해 AGDN가 다양한 문제 크기와 노드 분포에 걸쳐 지도 학습 및 비지도 학습 설정 모두에서 최신 기술(state-of-the-art) 방식들을 능가함을 입증하였다.

실험 결과
저자들은 200개에서 1000개의 노드를 가진 TSP 인스턴스와 TSPLIB의 실제 데이터셋에 대해 AGDN을 평가하였다.

• 효과성: 지도 학습(SL) 설정에서, AGDN은 GatedGCN, Att-GCN, DIFUSCO와 같은 베이스라인 모델들과 비교하여 최적해 대비 가장 낮은 격차(gap)를 달 나타냈다. 예를 들어, TSP-1000에서 AGDN은 GatedGCN의 7.26%와 비교하여 1.28%의 격차를 달성했다. 비지도 학습(UL)에서도 AGDN은 UTSP 및 Position보다 우수한 성능을 보였다.
• 효율성: AGDN은 탁월한 계산 효율성을 보여주었다. 특히 정보 집계를 위한 홉 수가 증가함에 따라 GatedGCN보다 더 적은 파라미터와 적은 추론 시간을 요구했다. 이는 단일 레이어에서 다중 홉 정보를 포착할 수 있는 능력 덕분이다.
• 일반화: 모델은 TSP 100에서 학습되어 더 큰 인스턴스(TSP-200, 500, 1000) 및 다양한 노드 분포(Uniform, Cluster, Explosion, Implosion)로 테스트되었을 때 견고한 일반화 성능을 보였다. 또한 재학습 없이도 다양한 실세계 TSPLIB 인스턴스(tsp225, pcb442, pr1002)에서 높은 성능을 유지하였다.

의의
본 논문은 AGDN이 TSP 해결에 있어 그래프 희소화와 정보 손실 사이의 근본적인 트레이드오프를 해결한다고 주장한다. 이방성 확산 전략과 MixScore 사전 정보를 도입함으로써, 이 프레임워크는 GNN이 TSP 그래프의 전체 연결성을 효과적으로 활용할 수 있게 한다. 결과는 AGDN이 이론적인 그래프 학습 능력과 조합 최적화의 실질적인 요구 사이의 간극을 메우는 확장 가능하고 일반화 가능한 솔루션을 제공하며, 경쟁력 있는 추론 시간을 유지하면서 최첨단 성능을 달성함을 시사한다.