GES-TSP: Graph Edge Sparsification for TSP

기술 요약: GES-TSP: TSP를 위한 그래프 엣지 희소화(Graph Edge Sparsification)

문제 정의
외판원 문제(Traveling Salesman Problem, TSP), 특히 유클리드 변형(ETSP)은 전형적인 NP-난해(NP-hard) 조합 최적화 문제이다. CPLEX나 SCIP와 같은 정밀 해법(exact methods)은 최적해를 구할 수 있지만, 완전 그래프(complete graph) 구성 시 발생하는 엣지의 이차적 증가($O(n^2)$)로 인해 대규모 인스턴스에 대해서는 계산 비용이 매우 높다. k-최근접 이웃(k-nearest neighbor, KNN) 그래프나 델로네 삼각측량(Delaunay triangulation)과 같은 전통적인 그래프 희소화 기법은 고정된 기하학적 휴리스틱을 사용하여 탐색 공간을 줄인다. 그러나 이러한 방법들은 인스턴스 특유의 구조적 정보를 충분히 활용하지 못하여, 불필요한 엣지를 남기거나 중요한 문제 특정적 구조를 누락하는 경우가 빈번하다. 반면, 최근의 엔드 투 엔드(end-to-end) 학습 기반 TSP 솔버들은 일반화 능력이 제한적이고 아키텍처가 복합적이라는 단점이 있다. 본 논문이 다루는 핵심 과제는, 높은 품질의 해를 보존하고 다양한 인스턴스 분포에 대해 강력한 일반화 성능을 유지하면서도 계산 오버헤드를 크게 줄일 수 있는 적응형 희소 그래프를 생성하는 방법이다.

방법론
저자들은 기하학적 구조와 그래프 신경망(GNN)을 결합하여 유망한 엣지를 식별하는 학습 기반 프레임워크인 GES-TSP(Graph Edge Sparsification for TSP)를 제안한다. 방법론은 네 가지 주요 단계로 진행된다:

1. 조밀한 그래프 구축(Coarse Graph Construction): 완전 그래프에서의 학습 부담을 완화하기 위해, 이 방법은 먼저 델로네 삼각측량을 사용하여 조밀한 희소 그래프를 구축한다. 이 기하학적 구조는 국소적 근접 관계를 보존하며 $O(n)$개의 엣지를 포함하므로, 완전 그래프보다 훨씬 작은 강력한 초기 후보 집합 역할을 한다.
2. 특징 구축(Feature Construction): 모델은 각 엣지 $(i, j)$에 대해 4차원 특징 벡터를 활용한다:
   • 유클리드 거리 ($d_{ij}$): 근본적인 비용 메트릭.
   • KNN 지표 ($KNN_{ij}$): 노드들이 상호 k-최근접 이웃인지 여부를 나타내는 이진 특징으로, 국소 밀도를 포착한다.
   • Q-값 ($Q_{ij}$): 노드 $i$에 연결된 가장 짧은 엣지의 길이에 비해 해당 엣지의 길이를 비교한 정규화된 메트릭으로, 이진 KNN보다 더 세밀한 국소 엣지 품질 측정을 제공한다.
   • IMST (Iterative Minimum Spanning Tree): MST를 반복적으로 계산하고 제거하여 얻은 글로벌 특징으로, 다양한 그래프 크기에 대해 척도 불변성을 보장하도록 정규화된다.
3. GNN 추론(GNN Inference): 엣지의 중요도를 예측하기 위해 **그래프 어텐션 네트워크(GAT)**가 사용된다. 모델은 어텐션 메커니즘을 사용하여 이웃 정보를 집계하며, 노드 임베딩과 앞서 언급한 엣지 특징들을 모두 통합한다. 출력값은 각 엣지에 대한 점수이며, 클래스 불균형 가중치가 적용된 이진 교차 엔트로피 손실(binary cross-entropy loss)을 사용하여 이진 분류 작업(최적 경로에 엣지가 포함되는지 여부)으로 학습된다.
4. 희소 그래프 생성 및 해결(Sparse Graph Generation and Solving): 점수를 기준으로 엣지를 필터링한다. 결정적으로, 실행 가능한 해의 존재를 보장하기 위해 크리스토피데스(Christofides) 알고리즘의 해에서 도출된 엣지들을 희소 그래프에 강제로 포함시킨다. 이는 연결성을 보장하고 최소 하나 이상의 유효한 해밀턴 사이클(Hamiltonian cycle)이 존재하도록 보장한다. 생성된 희소 그래프는 최종 경로를 계산하기 위해 정밀 솔버(SCIP)로 전달된다.

주요 기여

• 하이브리드 프레임워크: 본 논문은 결정론적 기하학적 휴리스틱(델로네 삼각측량, 크리스토피데스)과 데이터 기반 학습(GAT)을 결합하여 견고한 희소화 파이프라인을 만드는 새로운 접근 방식을 도입한다.
• 적응형 특징 공학: 국소적 구조 품질과 글로벌 그래프 특성을 모두 효과적으로 포착하도록 설계된 Q-값 및 정규화된 IMST를 포함한 특정 엣지 특징 세트를 제안한다.
• 실행 가능성 보장: 그래프의 연결을 끊을 위험이 있는 일부 학습 기반 프루닝(pruning) 방법들과 달리, GES-TSP는 크리스토피데스 엣지를 통합하여 프루닝된 그래프가 여전히 풀릴 수 있음을 수학적으로 보장한다.
• 일반화: 이 방법은 특정 인스턴스 크기에 대해 재학습할 필요 없이, 합성 데이터셋인 MATILDA와 실제 세계의 TSPLIB 벤치마크 모두에서 강력한 일반화 능력을 입증한다.

실험 결과
실험은 MATILDA 데이터셋(100개 노드 인스턴스의 다양한 분포)과 TSPLIB 벤치마크(130개에서 2392개 노드 범위의 인스턴스)를 대상으로 수행되었다.

• 프루닝 비율(Pruning Rate): GES-TSP는 베이스라인 방법들(SGN 및 Fitzpatrick 등)에 비해 현저히 높은 엣지 프루닝 비율을 달ace한다. MATILDA 데이터셋에서 최대 **94%**의 엣지를 제거한다. 대규모 TSPLIB 인스턴스(예: pcb1002, vm1748, pr2392)의 경우, 프루닝 비율이 **99%**를 초과한다.
• 솔루션 품질: 공격적인 프루닝에도 불구하고, 이 방법은 매우 타이트한 최적성 격차(optimality gap)를 유지한다. MATILDA에서 평균 격차는 **0.10%**이다 (SGN의 0.68% 및 Fitzpatrick의 0.17% 대비). TSPLB에서는 가장 큰 인스턴스에 대해서도 격차가 1% 미만으로 유지된다.
• 효율성: 높은 프루닝 비율은 상당한 속도 향상으로 이어진다. GES-TSP는 해결 시간 측면에서 베이스라인을 지속적으로 능가하며, 이는 줄어든 그래프 크기가 정밀 솔버를 훨씬 빠르게 실행할 수 있음을 보여준다.
• 절제 연구(Ablation Studies): 델로네 코스 필터를 제거하거나 이를 KNN으로 대체하면 프루닝 비율이 약 3~5% 감소한다. 특징 절제 연구를 통해 KNN과 IMST 특징이 가장 영향력이 크며, Q-값과 거리 특징은 필요한 세부 조정을 제공한다는 것을 확인했다.

의의 및 주장
본 논문은 GES-TSP가 대규모 인스턴스에 대해 정밀 TSP 솔버를 확장하는 데 있어 실용적이고 효과적인 솔루션을 제공한다고 주장한다. 그래프 크기를 95% 이상(경우에 따라 최대 99%) 줄이면서도 솔루션 격차를 1% 이내로 유지함으로써, 이 방법은 휴리스틱의 확장성과 정밀 방법의 최적성 보장 사이의 간극을 메운다. 저자들은 이 접근 방식이 기하학적 구조 정보를 성공적으로 활용하여 학습을 유도함으로써, 다양한 데이터 분포와 문제 규모에 걸쳐 잘 일반화되는 시스템을 구축했다고 강조한다. 이 연구는 조합 최적화를 위해 기하학적 휴리스틱과 그래프 신경망을 통합하는 잠재력을 보여주지만, 저자들은 현재 프레임워크가 TSP에 국한되어 있으며 아직 다른 조합 문제로 확장되지 않았음을 겸허히 언급하였다.