기술 요약: 볼록 거리 연산자 운송 (Convex Distance Operator Transport, CDOT)

문제 정의

최적 운송(Optimal Transport, OT)은 확률 측량 간의 비용을 정량화하여 두 분포를 비교하는 근본적인 프레임워크를 제공한다. 그러나 와서스타인 거리(Wasserstein distance)에 기반한 고전적 OT는 데이터 분포가 동일한 공간 내에 존재해야 한다는 제약이 있으며, 이는 이질적인 도메인에 대한 적용을 제한한다. 그로모프-와서스타인(Gromov–Wasserstein, GW) 및 퓨즈드 그로모프-와서스타인(Fused Gromov–Wasserstein, FGW) 프레임워크는 교차 도메인 비용 없이도 내재적 메트릭-측량(metric-measure, mm) 공간을 통해 구조적 정보를 정렬함으로써 이 문제를 해결한다.

이러한 범용성에도 불구하고, (F)GW 정식화는 **비볼록성(non-convexity)**이라는 근본적인 한계를 갖는다. 이는 GW 비용이 결합(coupling, $\pi \otimes \pi$)의 텐서 곱을 포함하여 쌍별 거리 비교를 생성함으로써 비볼록한 최적화 지형을 만들기 때문에 발생한다. 결과적으로 표준 최적화 알고리즘은 일반적으로 지역 정점(local stationary points)에만 수렴하며, 도출된 솔루션은 전역 최적성 보장을 결여할 수 있다. 또한, 기존의 볼록 완화(convex relaxations) 방식들은 속성된 mm 공간에서의 의사메트릭(pseudometric) 성질을 보존하지 못하거나, 문제의 기하학적 구조를 변화시키는 추가적인 평활화 파라미터(예: 엔트로피 정규화)를 요구하기도 한다.

방법론: 볼록 거리 연산자 운송 (CDOT)

저자들은 특징 대응(feature correspondence)과 내재적 기하 구조를 모두 보존하면서 이질적인 mm 공간을 정렬하도록 설계된 최초의 볼록 최적 운송 프레임워크인 **볼록 거리 연산자 운송(CDot)**을 제안한다.

핵심 정식화

CDOT는 각 공간의 기하 구조와 운송 계획을 $L^2$ 공간에서 작용하는 선형 연산자로 격상시킨다. CDOT는 쌍별 거리를 직접 비교하는 대신, **집계된 거리 구조(aggregated distance structures)**를 연산자 합성(operator composition)을 통해 정렬한다.

두 개의 속성된 컴팩트 mm 공간 $\mathcal{X} = (X, d_X, P_X, f_X)$와 $\mathcal{Y} = (Y, d_Y, P_Y, f_Y)$, 그리고 운송 계획 $\pi \in \Pi(P_X, P_Y)$가 주어졌을 때, CDOT 목적 함수 $L_\alpha(\pi)$는 두 구성 요소를 균형 있게 조절한다:

1. 특징 정렬 (Feature Alignment): $F(\pi) = \mathbb{E}_\pi[\|f_X(X) - f_Y(Y)\|_2^2]$, 이는 특징 간의 원소별 유사성을 장려한다.
2. 구조적 정규화 (Structural Regularization): $R(\pi) = \|D_{P_X} T_\pi - T_\pi D_{P_Y}\|_{HS}^2$, 이는 구조적 불일치를 처벌한다.

여기서:

• $D_{P_X}$와 $D_{P_Y}$는 연속적인 쌍별 거리 행렬의 아날로그를 나타내는 $L^2(X, P_X)$ 및 $L^2(Y, P_Y)$ 상의 적분 연산자인 **거리 연산자(distance operators)**이다.
• $T_\pi$는 함수를 $L^2(Y, P_Y)$에서 $L^2(X, P_X)$로 매핑하는 결합 $\pi$와 관련된 **조건부 기대 연산자(conditional expectation operator)**이다.
• $\|\cdot\|_{HS}$는 힐베르트-슈미트(Hilbert–Schmidt) 노름을 나타낸다.

CDOT 문제는 다음과 같이 정식화된다:
$$\inf_{\pi \in \Pi(P_X, P_Y)} \left[ (1-\alpha)F(\pi) + \frac{\alpha}{2}R(\pi) \right]$$

이론적 기초

• 볼록성 (Convexity): 저자들은 CDOT 목적 함수가 볼록함을 증명한다. 이는 구조적 항 $R(\pi)$가 $T_\pi$($\pi$에 대해 아핀 함수임)에 선형적으로 의존하고, 제곱 힐베르트-슈미트 노름이 볼록하기 때문에 가능하다. 이는 $\pi$에 대한 이차적 의존성으로 인해 비볼록성을 유발하는 GW와 대조된다.
• 의사메트릭 성질 (Pseudometricity): 도출된 CDOT 불일치(discrepancy)는 최소 목적 함수 값의 제곱근으로 정의되며, 속성된 컴팩트 mm 공간 상에서 유효한 **의사메트릭(pseudometric)**임이 증명되었다.
• 분산 갭 (Dispersion Gap): 본 논문은 CDOT와 GW 사이의 관계를 공식적으로 설명하기 위해 "분산 갭" 분석을 도입한다. GW 목적 함수가 CDOT 목적 함수와 결합의 공간적 불확실성을 정량화하는 분산 처벌(dispersion penalty) $V(\pi)$의 합으로 분해될 수 있음이 밝혀졌다. GW의 비볼록성은 결정론적(concentrated) 결합을 선호하는 이 분산 항에서 기인한다. CDOT는 이 처벌 항을 분리하고 제거함으로써 볼록성을 달a성한다.

최적화

유한 샘플 환경에서 CDOT 문제는 운송 다면체(transport polytope) 상의 **볼록 이차 계획법(convex quadratic program)**으로 축소된다. 저자들은 투영이 필요 없는 특성(projection-free nature)을 고려하여 프랭크-울프(Frank–Wolfe, FW) 알고리즘을 사용하여 이를 해결한다. 또한 이차 구조를 활용하여 그래디언트를 효율적으로 업데이트함으로써, 전체 복잡도는 행렬 연산에 대한 $O(n^3)$에 의해 지배되지만, 반복당 계산 오버헤드를 세제곱 시간에서 제곱 시간으로 줄이는 "레이지 그래디언트(lazy gradient)" 변형을 제안한다.

주요 기여

1. 최초의 볼록 기하 인식 OT 프레임워크: CDOT는 불일치만을 추정하는 슬라이싱 기반 방법들과 달리, 최적 운송 계획을 명시적으로 복구하면서 이질적인 mm 공간을 정렬하기 위한 최초의 볼록 정식화를 제공한다.
2. 이론적 보장:
   • 존재성 및 볼록성: 엔트로피 정규화 없이도 최적 결합의 존재성과 목적 함수의 볼록성을 입증했다.
   • 의사메트릭 성 성질: CDOT 불일치가 유효한 의사메트릭임을 확립했다.
   • 리스크 일관성: 최적화 오류와 통계적 오류로 분해된 비점근적 리스크 바운드를 도출하여, 에스티메이터가 전역 수렴하는 Frank–Wolfe 알고리즘 하에서 리스크 일관성을 가짐을 증명했다.
3. 기하학적 통찰: "분산 갭" 분석은 GW의 비볼록성의 원인을 공식적으로 설명하고, CDOT가 어떻게 분산 항을 필터링하여 볼록한 지형을 달성하는지 보여준다.
4. 실험적 성능: 합성 점 구름(point clouds), 뇌 커넥톰(OASIS-3), 그래프 분류 벤치마크(TUDataset)에서 기존 방법들(FGW, Entropic FGW, IsoRank, Spectral Matching, COPT)보다 우수한 성능을 입증했다.

실험 결과

• 합성 데이터: 2D 클러스터 점 구름에서 CDOT는 다양한 샘플 크기에 걸쳐 일관되게 가장 낮은 평균 제곱 오차(MSE)를 달 기록하며 안정적인 수렴을 보여주었다. 반면, Entropic FGW(EFGW)는 정규화 파라미터 $\epsilon$에 매우 민적이었으며, $\epsilon$이 작을 때 CDOT의 정밀도를 따라잡지 못하거나 지역 최적점에 갇히는 경향을 보였다.
• 뇌 커넥톰 (OASIS-3): 구조적 뇌 네트워크 연구에서, CDOT는 확산 거리(diffusion distance)(강건한 전역 메트릭)를 사용할 때 FGW(18.53%)를 크게 상회하는 61.36%의 매칭 정확도를 달성했다. 저자들은 이를 CDOT가 쌍별 대비(pairwise contrasts)가 확산에 의해 평탄해진 상황에서도 집계된 기하학적 프로파일을 정렬할 수 있는 능력 덕분이라고 분석했다. 지오데식 거리(geodesic distance)에서는 FGW가 약간 더 나은 성능을 보였는데, 이는 엄격한 쌍별 정렬과 강건한 전역 정렬 사이의 트레이드오프를 보여준다.
• 그래프 분류: TUDataset 벤치마크에서 CDOT는 특징 정보가 풍부한 데이터셋(예: MUTAG, ENZYMES)에서 베이스라인 방법들(FGW, GW, COPT)보다 일관되게 높은 분류 정확도를 보였다. 특히 노드 특징이 없는 IMDB-BINARY 데이터셋에서도 CDOT가 최상의 성능을 유지했는데, 이는 CDOT의 연산자 기반 기하학이 표준 GW 접근 방식보다 위상적 차이를 더 효과적으로 포착함을 시사한다.

의의 및 주장

본 논문은 CDOT가 기존의 비볼록 OT 방법들에 대한 강건하고 신뢰할 수 있는 대안을 제공한다고 주장한다. 볼록한 최적화 지형을 보장함으로써, CDOT는 솔루션을 불안정하게 만들 수 있는 하이퍼파라미터 튜닝(예: 엔트로피 정규화) 없이도 전역 최적점으로의 수렴을 보장한다. 이 프레임워크는 뇌 네트워크 분석 및 그래프 분류와 같이 내재적 기하 구조를 보존해야 하는 이질적 도메인 관련 응용 분야에서 특히 중요하다.

저자들은 두 가지 한계점을 겸허히 언급하였다:

1. CDOT는 엄격한 일대일 매칭보다는 연산자 수준의 정렬을 위해 설계되었으므로, 불일치가 0이라고 해서 반드시 측량 보존적 등거리 사상(measure-preserving isometry)이 완벽하게 일치함을 의미하지는 않는다.
2. 볼록하기는 하지만, 현재 구현은 OT 서브문제를 지배하는 Frank–Wolfe 반복에 의존하므로, 매우 큰 규모의 설정보다는 중간 규모의 문제 크기에 더 적합하다.

저자들이 제시한 향 향후 연구 방향에는 CDOT 불일치를 기반으로 한 통계적 추론 프레임워크(예: 동형성(isomorphism)을 위한 가설 검정) 개발과, 최적의 그라운드 메트릭을 공동 학습하기 위해 CDOT 목적 함수를 딥 뉴럴 네트워크의 미분 가능한 레이어로 통합하는 것이 포함된다.