Min Generalized Sliced Gromov Wasserstein: A Scalable Path to Gromov Wasserstein

기술 요약: Min Generalized Sliced Gromov–Wasserstein (min-GSGW)

문제 제기

Gromov–Wasserstein (GW) 거치는 형태 분석, 그래프 매칭, 생물학적 데이터 통합과 같이 공통된 주변 공간이 존재하지 않는 거리 측정 공간들을 비교하는 데 있어 핵심적인 도구입니다. GW 는 두 공간 간의 내부 쌍별 기하학적 불일치를 최소화하는 결합 (coupling) 을 찾습니다. 그러나 GW 문제를 해결하는 것은 계산적으로 매우 비용이 큽니다. 이산적 설정에서 GW 문제는 일반적으로 NP-난해인 비볼록 2 차 계획법이며, 단순한 구현 방식은 $O(n^4)$의 연산이 필요합니다.

기존의 확장 가능한 대안들, 특히 Sliced Gromov–Wasserstein (SGW) 은 고차원 측정을 1 차원 선으로 투영하고 단조 매칭을 수행함으로써 복잡도를 줄입니다. 효율적 ($O(n \log n)$) 임에도 불구하고, 이러한 방법들은 세 가지 치명적인 한계를 겪습니다:

1. 비최적 1 차원 매칭: 투영된 영역에서의 단조 매칭은 반드시 1 차원 GW 부분 문제를 정확히 해결하지는 않습니다. 반례들은 항등 또는 역항등 치열이 항상 최적이지 않음을 보여줍니다.
2. 투영 비호환성: 기존 방법들은 종종 두 공간에 대해 독립적으로 선택된 투영을 사용하는데, 이는 의미 있는 구조적 정렬을 포착하지 못할 수 있습니다.
3. 운송 계획의 신뢰성: 투영된 공간에서 생성된 운송 계획은 원래 거리 측정 공간으로 다시 들어올렸을 때 진정한 GW 최적 결합에 근접함을 보장하지 않습니다. 따라서 기존의 슬라이스드 GW 방법들은 종종 GW 손실을 직접 최소화하는 대신 대체 거리 목적 함수로 기능합니다.

방법론

저자들은 고정된 선형 투영에 의존하는 대신 결합된 비선형 슬라이서를 학습함으로써 명시적인 운송 계획을 구축하는 min Generalized Sliced Gromov–Wasserstein (min-GSGW) 프레임워크를 제안합니다.

핵심 메커니즘:

1. 일반화된 슬라이서 및 리프팅: 경직된 선형 임베딩 대신, min-GSGW 는 저차원 공간을 고차원 공간으로 매핑하는 리프팅 맵 $h: X \to Y$와 공유되는 비선형 슬라이서 $f: Y \to \mathbb{R}$을 학습합니다.
2. 푸시-포워드 및 정렬: 이 방법은 리프트된 소스 점 ($f \circ h$) 과 타겟 점 ($f$) 에 대한 푸시-포워드 값을 계산합니다.
3. 단조 결합: 결과적으로 얻어진 1 차원 값들은 정렬되며, 이 정렬된 시퀀스 사이에 단조 결합이 형성됩니다.
4. 계획의 리프팅: 이 1 차원 단조 결합은 원래 공간으로 다시 리프트되어 운송 계획 $\pi_{f,h}$를 형성합니다.
5. 최적화: 목적은 이 리프트된 계획을 사용하여 원래 공간에서 평가된 GW 손실을 최소화하는 것입니다:
   $$\text{min-GSGW}(\mu, \nu) := \inf_{f, h} L_{GW}(\mu, \nu, \pi_{f,h})$$
   중요한 점은 슬라이서의 비선형성으로 인해 유도된 결합들이 선형 투영으로는 접근할 수 없는 결합 공간의 영역에 도달할 수 있으며, 이를 통해 학습된 비선형 재배열을 통해 1 차원 GW 해를 효과적으로 근사한다는 것입니다.

구현 세부 사항:

• 미분 가능 완화: 정렬은 미분 불가능하므로, 저자들은 슬라이서의 기울기 기반 최적화를 가능하게 하기 위해 훈련 중에 소프트 정렬 완화 (LapSum) 를 사용합니다.
• 상각 변형 (Amortized Variant): 이 프레임워크는 신경망이 미처 보지 못한 입력 쌍에 대해 슬라이서 매개변수와 푸시-포워드 값을 직접 예측하는 상각 설정을 지원합니다. 이를 통해 단일 순전파로 각 인스턴스별 최적화를 제거합니다.
• 불변성: 내재적 토큰화 (정렬된 제곱 거리 프로파일) 와 공변층을 사용하여 구조적으로 강체 운동 불변성을 만족하도록 설계되었습니다.

주요 기여

1. 일반화된 슬라이서 프레임워크: 공유 맵과 리프팅을 통해 두 슬라이서를 결합하고 원래 거리 측정 공간에서 직접 운송 계획을 유도하는 min-GSGW 의 도입. 이는 선형 슬라이싱보다 풍부한 결합 계열을 탐색할 수 있게 합니다.
2. 구조적 속성: 강체 운동 불변성의 확립과 최적화를 위한 미분 가능 정렬 완화의 개발.
3. 상각 학습: 인스턴스별 최적화를 대체하는 학습된 예측기의 개발로, 새로운 입력 쌍에 대한 효율적인 매칭을 가능하게 함.
4. 실증적 검증: min-GSGW 가 고비용의 반복 솔버 (예: Frank-Wolfe, Sinkhorn) 와 경쟁력 있는 기하학적 대응 관계와 GW 목적 함수 값을 생성하면서도 계산 비용은 현저히 낮음을 입증.

실험 결과

저자들은 세 가지 작업에서 min-GSGW 를 평가했습니다:

• 현실적인 형태 매칭: 동물 메쉬 (말, 코끼리, 고양이) 벤치마크에서 min-GSGW 는 모든 쌍에 걸쳐 지오데식 오차 (지오메트릭 정확도를 기준 참값과 비교하여 측정) 가 가장 낮았으며, 동시에 가장 빠른 실행 시간을 유지했습니다 (예: POT-GW 의 1.82 초 대비 약 0.08 초).
• 말 메쉬 보간: 이 방법은 말 메쉬 간의 매끄럽고 기하학적으로 일관된 중간 변형을 생성했습니다. POT-GW 가 더 낮은 GW 목적 함수 값을 달성했지만, min-GSGW 계획은 대규모 구조를 효과적으로 보존하여 전역 GW 최적성이 항상 기하학적 유용성과 일치하지는 않음을 시사했습니다.
• ShapeNet 부품 분할: 상각 비지도 설정에서 학습된 매처는 훈련 중 부품 레이블을 사용하지 않고 부품 대응 관계를 예측했습니다. Min-GSGW 는 POT GW (68.9%) 및 Sinkhorn 에 비해 더 높은 부품 레이블 전이 정확도 (예: $N=256$에서 78.2%) 를 달성했으며, 순전파 추론 시간은 수 배 더 빨랐습니다 (75.3ms 대비 2.66ms).

의의 및 주장

이 논문은 min-GSGW 가 슬라이서 유도 결합 계열에 대한 GW 목적 함수를 직접 최소화함으로써 Gromov–Wasserstein 에 대한 "확장 가능한 경로"를 제공한다고 주장합니다. 주요 주장에는 다음이 포함됩니다:

• 직접 GW 최소화: 이전의 슬라이스드 방법들이 대체 거리 목적 함수를 정의한 것과 달리, min-GSGW 는 원래 GW 손실을 최소화하여 진정한 GW 거리에 대한 유효한 상한을 제공합니다.
• 표현력 대 효율성: 비선형 슬라이서를 사용하여 선형 투영의 한계를 극복함으로써, 계획 추출의 $O(n \log n)$ 복잡성에도 불구하고 반복 솔버와 경쟁하거나 종종 더 우수한 결합을 달성합니다.
• 실용적 유용성: 상각 변형은 밀집된 GW 최적화가 계산적으로 prohibitive 한 고해상도 문제에 GW 기반 매칭을 적용할 수 있게 하여, 형태 분석 및 다중 모달 데이터 통합과 같은 작업에 구조 인식 매칭을 실용적으로 만듭니다.

저자들은 이 방법이 근사치이지만, 학습된 슬라이서의 표현력이 상한을 좁히도록 허용하며, 강체 운동 불변성은 기하학적 작업에 대한 견고성을 보장한다고 지적합니다.