Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

논문 개요

이 논문은 외판원 문제 (TSP) 를 해결하는 고성능 솔버 (예: LKH) 의 성능을 극대화하기 위해, 그래프 희소화 (Graph Sparsification) 기법에 머신러닝을 적용한 새로운 2 단계 접근법을 제안합니다. 기존 방법론의 한계를 극복하고, 다양한 거리 유형과 문제 규모에 걸쳐 안정적이고 효율적인 후보 그래프를 생성하는 것을 목표로 합니다.

1. 문제 정의 (Problem)

• 배경: LKH 와 같은 고성능 TSP 솔버는 모든 가능한 간선을 탐색하는 대신, 희소화된 '후보 그래프 (Candidate Graph)' 내에서만 탐색을 수행합니다.
• 도전 과제:
  • 희소성 vs. 신뢰성: 후보 그래프가 너무 밀집하면 탐색 시간이 낭비되고, 너무 희소하면 최적 해 (Optimal Tour) 에 포함된 간선이 제거되어 해의 질이 떨어집니다.
  • 기존 방법의 한계:
    • $\alpha$-Nearest: 회수율 (Recall, 최적 간선 포함 비율) 은 높지만 그래프가 너무 밀집합니다.
    • POPMUSIC: 매우 희소하지만 큰 규모나 어려운 공간 분포에서 회수율이 급격히 떨어집니다.
    • 단일 휴리스틱: 어떤 단일 방법도 모든 문제 크기와 분포에서 동시에 희소성과 신뢰성을 보장하지 못합니다.
  • 기존 ML 방법의 한계: 기존 머신러닝 기반 희소화 방법들은 완전 그래프 (Complete Graph) 에서 작동하여 계산 비용이 크고, 대부분 유클리드 거리 (Euclidean Distance) 에만 국한되어 다른 거리 유형 (MAN_2D, GEO 등) 에 적용하기 어렵습니다.

2. 제안 방법론 (Methodology)

저자들은 2 단계 그래프 희소화 파이프라인을 제안합니다.

1 단계: 회수율 극대화 (Heuristic Union)

• 전략: $\alpha$-Nearest 와 POPMUSIC 두 가지 휴리스틱의 결과를 합집합 (Union) 하여 초기 후보 그래프를 구성합니다.
• 목적: 최적 tour 에 속하는 간선을 최대한 포함하도록 회수율 (Recall) 을 99.9% 이상으로 극대화합니다.
• 핵심 이점: 이 과정에서 각 간선이 어느 휴리스틱에서 유래했는지 (단일 소스 vs. 양쪽 소스) 에 대한 **'소스 출처 신호 (Source-Provenance Signal)'**가 생성됩니다. 이는 머신러닝 모델에게 강력한 특징 (Feature) 이 됩니다.

2 단계: 학습 기반 가지치기 (Learned Pruning)

• 전략: 1 단계에서 생성된 희소화된 그래프 (완전 그래프가 아님) 에 대해 머신러닝 모델을 학습시켜 각 간점에 점수를 매기고, 점수가 낮은 간선을 제거합니다.
• 특징:
  • 거리 유형 무관성 (Distance-Type Agnostic): 좌표 기하학이 아닌 간선 가중치, 순위, 비율, 지역 통계 등 거리 유형에 의존하지 않는 특징 (Features) 만을 사용합니다. 따라서 TSPLIB 의 모든 거리 유형 (EUC_2D, ATT, MAN_2D, GEO) 에 적용 가능합니다.
  • 모델: 로지스틱 회귀 (LR), 선형 SVM, XGBoost 등을 실험했습니다.
  • 학습 목표: 최적 tour 에 속하는 간선 ($y=1$) 을 정확히 분류하고, 불필요한 간선을 제거하는 것입니다.
  • 선택 규칙: 전역 임계값 대신 노드 단위의 로컬 소프트맥스 분포를 사용하여 각 노드의 차수 (Degree) 를 유지하면서 하위 점수 간선을 제거합니다.

3. 주요 기여 (Key Contributions)

1. 효율적인 2 단계 파이프라인: 완전 그래프가 아닌 이미 희소화된 휴리스틱 그래프에 학습을 적용하여, 단일 모델로 4 가지 거리 유형과 5 가지 공간 분포를 모두 처리합니다.
   • 성능: 최적 tour 간선을 99.69% 이상 유지하면서 후보 그래프의 밀도를 최대 47% 까지 감소시켰습니다.
   • 범용성: 유클리드 거리에만 국한된 기존 신경망 방법보다 다양한 거리 유형에서 우수한 성능을 보입니다.
2. 소스 출처 신호의 효과: 두 휴리스틱의 합집합을 통해 생성된 '출처 신호'가 학습을 매우 용이하게 만듭니다.
   • 복잡한 신경망 없이도 로지스틱 회귀 (Logistic Regression) 만으로도 효과적인 가지치기가 가능하며, 훈련 크기보다 5 배 큰 문제 (N=500) 로도 안정적으로 전이 (Transfer) 됩니다.
3. 규모에 따른 확장성: 단일 휴리스틱 (특히 POPMUSIC) 은 작은 규모에서는 우수하지만 큰 규모에서 성능이 저하되는 반면, 제안된 2 단계 방법은 N=200 이상에서 POPMUSIC 단독보다 더 높은 회수율을 달성합니다.

4. 실험 결과 (Results)

• 데이터셋: TSPLIB 의 4 가지 거리 유형과 5 가지 공간 분포 (균일, 군집, 격자, 이상치, 회랑) 를 조합한 20 개 TSP 패밀리를 사용했습니다. 문제 크기는 N=50 에서 500 까지 다양하게 테스트했습니다.
• 밀도 감소 및 커버리지:
  • XGBoost 모델을 사용할 때, N=500 에서 약 47% 의 간선을 제거하면서도 99.69% 의 최적 간선을 유지했습니다.
  • 단순 로지스틱 회귀도 35~47% 의 밀도 감소 효과를 보였습니다.
• 솔버 성능 (LKH):
  • 가지치기된 그래프를 LKH 솔버에 입력했을 때, 1.20~1.28 배의 속도 향상을 기록했습니다.
  • 최적성 간격 (Optimality Gap) 은 증가하지 않았으며, 오히려 일부 경우 감소했습니다.
• 신경망 방법론 비교 (EUC_2D 기준):
  • DIFUSCO, AttGCN, DIMES 등 최신 신경망 희소화 방법보다 더 높은 커버리지와 더 낮은 밀도를 달성했습니다.
  • 신경망 방법들은 GPU 가 필요하고 유클리드 거리만 지원하지만, 제안 방법은 CPU 만으로도 작동하며 다양한 거리 유형을 지원합니다.
• 강건성 (Robustness):
  • 훈련 데이터 (N=100) 와 다른 크기 (N=50, 200, 500) 와 다른 거리 유형에서도 일관된 성능을 보였습니다.
  • 특히 'Corridor' 분포처럼 어려운 경우에도 단일 휴리스틱보다 우수한 성능을 유지했습니다.

5. 의의 및 결론 (Significance)

• 실용성: 이 방법은 TSP 솔버의 전처리 단계로 즉시 적용 가능하며, GPU 없이 CPU 만으로도 매우 빠르게 실행됩니다.
• 이론적 통찰: '휴리스틱의 합집합'이 생성하는 출처 신호가 머신러닝 모델의 학습 난이도를 획기적으로 낮추고, 대규모 문제로의 전이 능력을 보장한다는 것을 증명했습니다.
• 한계 및 향후 과제: 학습을 위해 Concorde 솔버를 사용한 정확한 최적 tour 라벨이 필요하여 훈련 비용이 높다는 점, 그리고 'Corridor'와 같은 특정 어려운 분포에서 여전히 일부 최적 간선이 손실될 수 있다는 점이 한계로 지적되었습니다.

요약하자면, 이 논문은 TSP 해결을 위한 후보 그래프 생성 과정에서 휴리스틱의 강점 (높은 회수율) 과 머신러닝의 강점 (효율적인 밀도 감소) 을 결합한 혁신적인 2 단계 프레임워크를 제시하며, 기존 방법론의 한계를 극복하고 다양한 문제 설정에서 우수한 성능을 입증했습니다.