Graph Neural Networks are Heuristics

기술 요약: 그래프 신경망은 휴리스틱이다

문제 정의
본 논문은 $n$개의 도시를 통과하는 최단 해밀턴 사이클(Hamiltonian cycle)을 찾는 것을 목표로 하는 전형적인 조합 최적화 문제인 유클리드 외판원 문제(TSP)를 다룬다. 저자들은 그래프 신경망(GNN)이 단순히 점수를 제공하거나, 탐색을 유도하거나, 고전적 솔버의 알고리즘을 모방하는 보조 도구로 사용되는 기존의 패러다임에 도전한다. 대신, 본 논문은 GNN이 독립적인 학습된 휴리스틱으로서 기능할 수 있다고 주장한다. 구체적인 과제는 자기회귀적 디코딩(autoregressive decoding), 강화 학습 보상, 명시적 탐색 절차(예: 빔 서치), 또는 사후 로컬 개선(예: 2-opt)에 의존하지 않고 단 한 번의 순방향 패스(forward pass)만으로 완전한 투어(tour)를 구성하는 것이다.

방법론
제안된 방법은 문제의 기하학적 구조로부터 직접 TSP 인스턴스를 학습하는 비자기회귀적(non-autoregressive), 비지도 학습 기반의 GNN 프레임워크이다.

1. 목적 함수 및 정식화:
   TSP는 거리 행렬 $D$와 순열 행렬 $V$에 의해 변환된 순열 행렬 $P$의 곱의 트레이스(trace)를 최소화하는 것으로 정식화된다. 엔드투엔드(end-to-end) 경사 하강법 기반 최적화를 가능하게 하기 위해, 이산적인 순열 $P$는 학습 과정에서 Gumbel-Sinkhorn 완화(relaxation)를 통해 소프트 순열 행렬 $T$로 완화된다. 손실 함수는 단순히 기대 투어 길이이다: $L_{TSP} = \langle D, TVT^\top \rangle$. 추론 시에는 헝가리안 알고리즘(Hungarian algorithm)을 사용하여 소프트 순열을 하드 순열로 변환한다.

2. 대칭성을 고려한 특징 추출:
   모델이 유클리드 군(Euclidean group)의 대칭성(순열 및 평행 이동 불변성/동변성)을 준수하도록 하기 위해, 저자들은 결정론적 특징 추출기를 도입한다.

• 평행 이동 불변성: 중심점(mean)을 빼서 도시 좌표를 중앙 정렬한다.
• 정준 프레임(Canonical Frame): 중심화된 점들의 경험적 공분산 행렬의 고유벡터를 사용하여 정준 프레임을 구축한다. 이는 회전 및 반사 모호성을 제거한다.
• 조화 인코딩(Harmonic Encoding): 점들을 이 정준 프레임에 투영하여 고유한 극좌표($r, \theta$)를 도출한다. 각도 정보는 $M$개의 푸리에 조화 함수($\sin(m\theta), \cos(m\theta)$)를 사용하여 인코딩되며, 이를 통해 GNN에 회전 불변적인 구조적 단서를 제공한다.

3. 네트워크 아키텍처:
   핵심 모델은 스캐터링-어텐션 그래프 신경망(SCT-GNN)이다. 이는 확산 기반 표현(부드러운 랜덤 워크 행렬의 거듭제곱으로부터 유도된 그래프 연산자 사용)과 다양한 확산 척도에 걸쳐 특징을 적응적으로 혼합하는 학습 가능한 어텐션 메커니즘을 결합한다. 이 네트워크는 구조적으로 순열 동변(permutation-equivariant)하다.

4. 다양성을 위한 앙상블 전략:
   여러 모델을 학습시키거나 반복적인 탐색을 수행하지 않고도 솔루션의 다양성을 생성하기 위해, 본 논문은 단일 학습 궤적 내에서 두 가지 메커즘을 사용한다.

• 몬테카를로(MC) 드롭아웃: 추론 중에 드롭아웃이 적용된다. 서로 다른 드롭아웃 마스크를 사용하여 여러 차례의 확률적 순방향 패스를 수행함으로써, 단일 학습된 인스턴스로부터 다양한 투어를 생성한다.
• 스냅샷 앙상블(Snapshot Ensembling): 단일 학습 실행 중 서로 다른 에포크(epoch)에서 여러 체크포인트를 저장한다. 최적화 지형의 서로 다른 지점을 나타내는 이러한 스냅샷들은 추론 시 공동으로 사용된다. 스냅샷 중 가장 좋은 투어가 선택된다.

주요 기여

• 독립적 휴리스틱으로서의 GNN: 본 논문은 GNN이 보조적인 탐색이나 정교화 없이 단 한 번의 순방위 패스로 유효한 투어를 생성하는 완전한 휴리스틱이 될 수 있음을 입증한다.
• 비지도 학습: 모델은 정답(ground-truth) 최적해나 강화 학습 보상을 필요로 하지 않으며, 오직 투어 길이를 최소화함으로써 학습한다.
• 전역 구조 학습: 로컬 그리디(greedy) 메커니즘을 제거하고 전역 해밀턴 사이클 목적 함수에 의존함으로써, 모델은 순수하게 국소적인 결정 규칙(예: 최근접 이웃 방식)이 놓치는 비국소적 조합 제약 조건을 학습한다.
• 효율성: 이 방법은 GPU에서 밀리초 단위의 추론을 달성하여, 자기회귀적 디코딩이나 탐색에 의존하는 다른 학습 기반 접근 방식이나 고전적 휴리스틱에 비해 유리한 품질-효율성 트레이드오프를 제공한다.

결과
실험은 균등 유클리드 분포에서 추출된 $n=100, 200, 500$ 노드의 TSP 인스턴스를 대상으로 수행되었다.

• 그리디(Greedy) 대비 성능: 모델은 그리디 최근접 이웃(NN) 베이스라인보다 일관되게 우수한 성능을 보인다. TSP100의 경우, 평균 투어 길이가 9.67(Greedy)에서 8.18(Deterministic GNN)로 개선되었다.
• 고전적 휴리스틱 대비 성능: 이 방법은 작은 인스턴스(TSP100, TSP200)에서 크리스토피데스(Christofides) 휴리스틱보다 성능이 뛰어나며, TSP500에서는 대등한 성능을 보이면서도 GPU에서 수십 배 더 빠른 추론 시간을 기록했다.
• 학습 기반 베이스라인 대비 성능: 강화 학습(RL) 및 지도 학습(SL) 베이스라인(예: GAT, GCN)과 비교했을 때, 제안된 방법은 경쟁력 있거나 더 우수한 최적성 갭(optimality gap)을 달면서도(예: 강력한 빔 서치를 사용하는 RL 베이스라인의 2.48% 갭 대비 TSP100에서 4.39% 갭), 자기회귀적 디코딩과 빔 서치를 피함으로써 훨씬 더 빠른 속도를 달성했다.
• 앙상블 효과: MC 드롭아웃과 스냅샷 앙상블 모두 최적성 갭을 줄이는 효과가 있었다. 두 전략을 결합했을 때 최상의 결과(TSP100에서 4.39% 갭, TSP200에서 8.25%, TSP500에서 12.11%)를 얻었으며, 앙상블 적용 시에도 추론 시간은 밀리초 단위(TSP500에 대해 결합 앙상블 시 최대 약 82ms)를 유지했다.

의의 및 주장
본 논문은 휴리스틱이 반드시 수작업으로 설계된 규칙이나 탐색 절차일 필요는 없으며, 문제의 구조로부터 직접 학습될 수 있다고 주장한다. TSP를 미분 가능한 해밀턴 사이클 목적 함수를 가진 직접적인 순열 학습으로 정식화함으로써, 저자들은 GNN이 전역적인 조합 제약 조건을 내재화할 수 있음을 보여준다. 이 연구의 의의는 조합 최적화의 패러다임을 전환하는 데 있다. 즉, 구조적 제약 조건과 생성 모델이 난해한 문제를 해결하기 위한 기초로서 명시적 탐색을 대체할 수 있다는 것이다. 결과는 "학습된 휴리스틱"이 탐색 비용이 과도할 때 고전적인 엔지니어링 방식보다 솔루션 품질과 계산 효율성 측면에서 대등하거나 이를 능가할 수 있음을 시사한다. 본 연구는 비지도 학습 기반의 GNN을 조합 최적화를 위한 새로운 클래스의 빠르고 학습된 휴리스틱으로 포지셔닝한다.