기술 요약: C2TSP (Connected by Construction)

문제 정의

본 논문은 두 가지 구조적 제약 조건(모든 노드의 차수가 2여야 한다는 국소적 차수 제약과 선택된 간선들이 단일 해밀턴 사이클을 형성해야 한다는 전역적 연결성 제약)을 만족하는 해를 요구하는 전형적인 조합 최적화 문제인 외판원 문제(Traveling Salesman Problem, TSP)를 다룹니다.

TSP를 위한 기존의 학습 기반 방법들은 학습된 객체 내에 이러한 전역적 연결 구조를 직접적으로 표현하는 데 어려움을 겪습니다. 대신 다음과 같은 방식에 의존합니다:

• 자기회귀적 구축 (Autoregressive construction): 절차적 마스킹을 통해 순차적으로 투어(tour)를 생성합니다.
• 히트맵 기반 접근법 (Heatmap-based approaches): 간선 점수를 예측하고 이후의 복구(repair), 샘플링 또는 탐색 과정에 의존하여 유효한 투어를 얻습니다.
• 할당 공간 완화 (Assignment-space relaxations): 투어 비용을 결정하는 간선 인접 구조를 직접적으로 포착하지 못하는, 매끄러운 순열 유사 객체를 모델링합니다.

이러한 접근 방식들은 두 가지 주요 한계를 가집니다: 첫째, 연결된 조합 객체에 대한 다루기 쉬운 전역 분포를 제공하지 못하며, 둘째, 학습된 표현의 품질과 사후 처리(post-processing) 효과를 분리하기 어렵게 만들어 성능이 다운스트림 디코딩이나 탐색 과정에 강하게 결합됩니다.

방법론: C2TSP

저자들은 구조적으로 의미 있는 잠재 객체인 **루티드 1-트리 (rooted 1-tree)**를 통해 TSP를 학습하는 엔드투엔드 비지도 학습 파이프라인인 C2TSP (Connected by Construction)를 제안합니다.

1. 루티드 1-트리 대리물 (The Rooted 1-Tree Surrogate)

해밀턴 사이클을 직접 학습하려고 시도하는 대신(이는 다루기 힘든 분할 함수를 가짐), 이 모델은 루티드 1-트리 제품군 위에서 작동합니다.

• 정의: 루티드 1-트리는 모든 비루트 노드($\bar{V}$)에 대한 신장 트리(spanning tree)와 고정된 루트 노드($r$)에 인접한 정확히 두 개의 간선으로 구성됩니다.
• 구조적 보장: 설계상, 이 제품군 내의 모든 구성은 전역적으로 연결되어 있으며 루트 차수 제약($d_r = 2$)을 만족합니다.
• 다루기 쉬움 (Tractability): 해밀턴 깁스 분포와 달리, 루티드 1-트리 깁스 제품군은 정확한 인수분해가 가능합니다. 이를 통해 기대 비용(expected-cost) 학습을 위해 샘플링 없이도 분할 함수 $Z_r(\eta)$, 간선 주변 확률(edge marginals) $\mu(\eta)$, 그리고 차수 모멘트(degree moments)를 정확하게 계산할 수 있습니다.

2. 평활화된 헬드-카프 평형화 (Smoothed Held–Karp Equilibration)

루티드 1-트리의 주요 구조적 결함은 비루트 노드들의 차수가 2가 아닐 수 있다는 점입니다. 이를 교정하기 위해 저자들은 평활화된 헬드-카프(HK) 평형화 레이어를 도입합니다.

• 이 레이어는 노드 가산 듀얼 변수($\lambda$)를 해결하여 간선 비용을 기울임으로써, 수정된 깁스 분포 하에서 모든 비루트 노드의 기대 차수가 2가 되도록 합니다.
• 이 레이어는 암시적 최적화 레이어(implicit optimization layers)의 패러다임을 따라, 평형 맵(equilibrium map)을 통한 암시적 미분을 사용하여 엔드투엔드로 학습됩니다.
• 이 과정은 학습된 분포가 기대치 측면에서 차수 균형을 이루도록 보장하여, 연결성을 유지하면서도 "차수 결함(degree defect)"을 제거합니다.

3. 인증 기반 샤프닝 (Certificate-Guided Sharpening)

HK 평형화 이후에도, 분포에는 여전히 비-투어 구조(해밀턴 사이클이 아닌 루티드 1-트리)에 대한 확률 질량이 포함될 수 있습니다.

• 인증 (Certificate): 저자들은 비루트 노드 차수의 총 분산을 사용하여 이 "비-투어 질량"($\gamma(q)$)을 상한으로 제한하는 인증을 도출합니다: $\gamma(q) \leq \frac{1}{2} \sum \text{Var}(d_i)$.
• 정교화 (Refinement): 인증 가이드 샤프닝 단계는 베르누이 상한 인증의 미분을 사용하여 주변 분포를 더 투어에 가까운 구조로 밀어냅니다. 이는 확률이 낮은 간선을 억제하고 확률이 높은 간선에 보상을 주는 결정론적 정교화 역할을 하여, 인증된 비-투어 질량의 상한을 줄입니다.

4. 학습 파이프라인

파이프라인은 편향되지 않은 TSP 비용으로부터 잔차 간선 섭동 ($\Gamma_\theta$)을 학습합니다.

• 순방향 패스 (Forward Pass): 원시 비용이 섭동되고, 노드 가산 성분을 제거하기 위해 투영되며, HK 평형화 레이어를 통과한 후, 인증 가이드 샤프닝을 통해 정교화됩니다.
• 손실 함수: 모델은 명시적인 구조적 제약에 대한 페널티 항 없이(구조적 제약은 아키텍처에 의해 강제됨), 학습된 간선 주변 확률의 기대 TSP 비용을 기반으로 하는 비지도 손실을 사용하여 학습됩니다.

주요 기여

1. 다루기 쉬운 루티드 1-트리 표현: 본 논문은 전역적 연결성을 설계에 의해 보장하면서도 학습을 위한 정확한 주변 확률 계산을 허용하는 표현을 도입합니다.
2. C2TSP 파이프라인: 잔차 간선 섭동을 위한 그래프 신경망(GNN)과 차수 평형화를 위한 평활화된 헬드-카프 레이어를 결합한 엔드투엔드 비지도 프레임워크를 제안합니다.
3. 비-투어 질량 인증: 비-투어 질량을 제한하는 인증을 도출하였으며, 이를 통해 주변 분포를 해밀턴 사이클로 밀어붙이는 샤프닝 메커니즘을 가이드합니다.
4. 실험적 검증: 루티드 1-트리 표현이 강력한 퓨어 디코딩(pure-decoding) 성능을 낸다는 것과, 히트맵 기반의 여러 베이스라인 모델들이 대규모 문제에서 성능이 저하되는 것과 달리 LKH-3와 같은 고전적 솔버와 통합되었을 때 견고함을 유지함을 입증했습니다.

실험 결과

저자들은 DIFUSCO, DIMES, Fast-T-2T, UTSP, NeuroLKH를 포함한 베이스라인들과 함께 2D 대칭 유클리드 TSP 인스턴스(TSP-50 ~ TSP-1000)에 대해 C2TSP를 평가했습니다.

• 퓨어 디코딩 (Pure Decoding): C2TSP는 테스트된 25개 구성(문제 크기 및 디코더 수준 변화) 중 20개에서 가장 낮은 최적성 갭(optimality gap)을 달로 달성했습니다. 특히, 로컬 서치 예산(예: 100회의 2-opt)이 많은 영역에서 가장 우수한 성능을 보였는데, 이는 학습된 분포가 이미 강력한 투어 구조를 인코딩하고 있음을 시사합니다.
• LKH 통합: LKH-3 솔버의 후보 소스로 사용되었을 때, C2TSP는 모든 문제 크기에 걸쳐 견고함을 유지하며 일반적인 LKH-3의 약 1‱(만 분의 일) 이내의 오차를 유지했습니다. 반면, 히트맵 기반 방법들(DIFUSCO, Fast-T2T, UTSP)은 LKH와 통합되었을 때 큰 규모($n \geq 500$)에서 성능이 크게 저하되었습니다.
• 절제 연구 (Ablation Studies):
  • 간선 섭동을 제거했을 때 성능이 크게 하락하여(평균 갭이 1.55%에서 12.74%로 증가), 잔차 간선 기하학을 학습하는 것의 필요성을 입증했습니다.
  • 인증 가이드 샤프닝은 주변 분포를 정교화함으로써 성능을 더욱 향상시켰으며, 이는 낮은 완화 비용(relaxed cost)만으로는 고품질 디코딩을 위한 충분조건이 아님을 확인시켜 줍니다.

의의 및 주장

본 논문은 미분 가능한 잠재 객체가 학습 기반 TSP의 핵심적인 모델링 선택이라고 주장합니다. 연결성을 디코딩 전에 인코딩함으로써, C2TSP는 구조적 진화가 학습, 인증 및 분석될 수 있는 "근사 투어 주변 확률(near-tour marginal)"을 드러냅니다.

저자들은 자신의 작업이 단순한 비제약 간선 점수 학습에서 명시적인 구조적 의미를 가진 다루기 쉬운 근사 투어 주변 확률을 학습하는 것으로의 전환이라고 규정합니다. 그들은 이 접근 방식이 학습된 표현을 사후 처리로부터 분리하여, 모델이 로컬 서치 절차를 위한 전역적으로 일관된 시작점을 제공할 수 있게 한다고 주장합니다.

논문은 설계상의 한계로 루티드 1-트리가 정확한 해밀턴 사이클 지지 집합(support)을 완화한다는 점을 인정합니다. 연결성은 강제되고 차수 균형은 기대치 측면에서 복구되지만, 남은 차수 변동은 정확히 제거되는 것이 아니라 평형화와 샤프닝을 통해 제어됩니다. 저자들은 이것이 더 엄격한 인증 기반 업데이트와 더 풍부한 다루기 쉬운 연결 가족(connected families)을 향한 방향을 제시한다고 제언합니다.