기술 요약: 신경 최적 운송을 통한 메트릭 그래프 상의 생성 모델링

문제 정의

도로 네트워크, 혈관 구조, 강 시스템과 같은 많은 과학적 및 기하학적 데이터셋은 자연스럽게 메트릭 그래프(metric graphs) 위에 지지됩니다. 메트릭 그래프는 에지가 길이를 가지며 연속적인 구간으로 취급되는 1차원 측지 공간입니다. 기존의 생성 모델링 접근 방식은 근방 유클리드 공간(ambient Euclidean space)에서 점을 생성한다는 근본적인 한계에 직면해 있으며, 이는 샘플이 그래프 위에 지지되거나 그래프의 고유한 메트릭 기하학을 준수하도록 보장하지 못합니다.

반대로, 그래프에 대한 전통적인 최적 운송(Optimal Transport, OT) 접근 방식은 종종 **이산화(discretization)**에 의존하여 연속적인 분포를 유한한 노드 기반 측도로 근사합니다. 이 방식은 계산적으로 접근 가능하지만, 이산화가 정밀해짐에 따라 메쉬 의존적인 근사를 초래하며 원래 도메인의 연속적인 성질을 상실하는 등 확장성 문제가 발생합니다.

본 논문은 메트릭 그래프의 기하학적 충실도를 희생하지 않으면서도 계산을 위해 매끄러운 근방 구조를 활용할 수 있는 연속적인 그래프 지지 생성 프레임워크의 필요성을 다룹니다.

방법론

저자들은 메트릭 그래프를 매끄러운 근방 공간에 임베딩하고, 그곳에서 엔트로피적 OT 문제를 해결한 뒤 샘플을 다시 그래프로 투영하는 딥 생성 모델링 프레임워크를 제안합니다. 파이프라인은 다음 세 가지 주요 단계로 구성됩니다.

1. 임베딩(Embedding): 메트릭 그래프 $\Gamma$를 사상 $\Psi$를 통해 매끄러운 근방 다양체 $M_\Psi$로 임베딩합니다. 본 논문은 두 가지 특정 임베딩을 조사합니다.

   • 외적 유클리드 실현($\iota$): 그래프를 $\mathbb{R}^m$으로 매핑합니다 (예: 도로 네트워크의 평면 좌표).
   • 내적 열대 아벨-자코비 임베딩($\Phi_p$): 그래프를 열대 자코비안 토러스(Tropical Jacobian torus) $J(\Gamma)$로 매핑합니다. 이 임베딩은 에지 길이와 사이클 구조에만 의존하며, 특정 유클리드 드로잉으로부터 독립적인 내적 기하학을 제공합니다.

2. 신경 엔트로피적 최적 운송(Neural Entropic Optimal Transport):

   • 소스($P_\Gamma$)와 타겟($Q_\Gamma$) 측도는 근방 공간($P_\Psi, Q_\Psi$)으로 푸시포워드(push forward)됩니다.
   • **신경 세미듀얼 파라미터화(neural semidual parameterization)**를 사용하여 임베딩된 측도들 사이의 **엔트로피적 칸토로비치 문제(entropic Kantorovich problem)**를 해결합니다.
   • 맵 기반의 몽주(Monge) 정식화와 달리, 이 접근 방식은 결합(coupling, plan)을 학습합니다. 타겟 측의 슈뢰딩거 포텐셜은 신경망 $g_\theta$에 의해 파라미터화됩니다.
   • 타겟 원자(atoms)에 제한된 샘플이 아닌 연속적인 출력을 생성하기 위해, 학습된 조건부 법칙은 **근방 열 커널(ambient heat kernel)**을 사용하여 매끄럽게 처리됩니다. 이는 근방 공간 상에서 존재하며 임베딩된 그래프 상에 정확히 놓이지 않을 수 있는 샘플을 생성합니다.

3. 회복(투영-풀백, Recovery: Projection–Pullback):

   • 열로 매끄러워진 샘플이 임베딩된 그래프를 벗어날 수 있으므로, 임베딩된 그래프 $\Psi(\Gamma)$로의 **최근접 점 투영(nearest-point projection)**을 수행합니다.
   • 그 후 역 임베딩 $\Psi^{-1}$을 적용하여 투영된 점을 원래의 메트릭 그래프 $\Gamma$로 매핑합니다.
   • 최종 생성기는 $\rho_\Gamma^\Psi = \Psi^{-1} \circ \text{proj}_{\Psi(\Gamma)}$로 구축되어, 생성된 모든 샘플이 원래의 메트릭 그래프 상에 엄격히 지지되도록 보장합니다.

주요 기여

1. 메트릭 그래프를 위한 최초의 딥 생성 프레임워크: 저자들의 지식에 따르면, 압축된 메트릭 그래프 상의 확률 분포를 위한 최초의 연속적 딥 생성 모델을 도입했습니다.
2. 이중 임베딩 기하학: 본 프레임워크는 두 가지 구별되는 운송 기하학을 위해 개발되었습니다.
   • 외적 유클리드 실현.
   • 자코비안 토러스로의 내적 열대 아벨-자코비 임베딩.
3. 이론적 수렴성: 저자들은 신경망의 표현력 증가와 열 스케일(heat scale)의 소멸이라는 공동 극한에서, 학습된 열 매끄럽기 투영-풀백 생성기가 원래의 그래프 측도 사이의 유효한 운송 결합(transport coupling)으로 **약하게 수렴(converges weakly)**함을 증명합니다. 이는 근방 공간에서 학습함에도 불구하고, 극한의 객체가 그래프 상의 진정한 결합임을 보장합니다.
4. 브릿지(Bridge) 처리: 브릿지를 처리하기 위해 정준 증강(가상 평행 에지 추가)을 포함하며, 이를 통해 열대 아벨-자코비 맵이 단사(injective)가 되도록 하고 그래프가 이미지로부터 회복될 수 있도록 합니다.

실험 결과

방법론은 합성 벤치마크와 실제 데이터를 통해 평가되었습니다.

• 합성 벤치마크: theta, wheel, grid, small road 그래프를 대상으로 테스트했습니다. 신경 OT 변형들(Tropical 및 Euclidean 모두)은 휴리스틱 베이스라인(노드 보간 및 근방 푸시포워드 기반의 이산 그래프 OT)에 비해 오차를 일관되게 감소시켰습니다 (내재적 그래프 와서스타인 거리 $W_1^\Gamma, W_2^\Gamma$ 및 밀도/CDF $L_1$ 오차 기준). 두 임베딩 기하학은 유사한 성능을 보였으며, 이는 주요 이득이 특정 임베딩의 이점보다는 아마티즈된(amortized) 엔트로피적 운송 규칙에서 온다는 것을 시사합니다.
• 확장성: 신경 방식은 지지 집합의 크기에 따라 유리하게 확장됩니다. 대규모 지지 쌍에서 내재적 최단 경로 거리를 평가해야 하는 명시적 쌍별 그래프 OT와 달리, 신경 방식은 미니배치로 학습하며 학습된 규칙을 배치 추론을 통해 적용합니다.
• 실제 응용: 프레임워크는 뉴욕 맨해튼의 100만 개 Uber 승차 위치 데이터에 적용되었습니다.
  • 과업은 그래프 지지 공간 밀도 생성(균일한 도로 소스로부터 승차 위치를 생성하는 법 학습)입니다.
  • 밀집 그래프 OT 베이스라인은 메모리 제약($10^{12}$ 개의 쌍별 비용)으로 인해 이 규모에서 실행이 불가능했습니다.
  • 신경 유클리드(Gromov) 모델은 맨해튼 도로 그래프 상의 지배적인 승차 구조를 성공적으로 복구하는 샘플을 생성하였으며, 하위 샘플링된 부분 집합(16,384개 지점)으로 학습된 휴리스틱 베이스라인보다 우수한 성능을 보였습니다.

의의 및 주장

본 논문은 이산화의 함정을 피하면서 메트릭 그래프 상의 확률 분포를 생성하는 원칙적인 솔루션을 제공한다고 주장합니다. 근방 공간에서 운송 문제를 해결하고 투영을 통해 그래프에 지지된 샘플을 회복함으로써, 이 방법은 도메인의 연속적인 기하학을 유지합니다.

저자들은 이 접근 방식이 맵(map) 기반이 아닌 플랜(plan) 기반임을 강조하며, 이를 통해 근방 밀도로 몰딩(mollify)하지 않고도 그래프 상의 특이 측도(singular measures)를 다룰 수 있다고 설명합니다. 유효한 결합으로의 약한 수렴에 대한 이론적 보장은 이 방법이 단순한 휴리스틱이 아니라 최적 운송 이론에 대한 엄격한 기초를 가지고 있음을 보장합니다.

이 연구는 신경 OT가 비유클리드, 1차원 기하학적 도메인에 어떻게 적응될 수 있는지를 보여주며, 도시 모빌리티에서 생물학적 네트워크에 이르기까지 다양한 응용 분야를 위한 확장 가능한 대안을 제시합니다. 저자들은 유한 샘플 속도(finite-sample rates)에 대한 부재와 현재의 초점이 시간적 또는 공변량 조건부 예측이 아닌 무조건적 생성에 국한되어 있다는 점을 포함한 한계점을 언급했습니다.