확장 가능한 Gromov--Wasserstein 학습을 위한 거리 행렬 Wasserstein 통계량

원문 발행 2026. 05. 15. 00:45원문 언어 영어AI 한국어 번역arXiv cs.LG 원문 보기

요약

본 논문은 공통 좌표계 없이 내부 거리를 이용해 그래프, 형상 등을 비교하는 Gromov--Wasserstein (GW) 거리의 대규모 추정 문제를 해결하기 위해 Distance-Matrix Wasserstein (DMW) 통계량을 제안합니다. DMW는 전역적인 포인트 정렬 대신 샘플링된 쌍별 거리 행렬 분포를 운송하여 GW의 완화(relaxation)이자 하한(lower bound)임을 증명했습니다. 또한, 데이터 매니폴드에 의존하는 유한 샘플 경계와 확장 가능한 계산을 위한 sliced 및 multi-scale DMW 기법을 제시하며, 이를 다양한 응용 분야에서 검증합니다.

핵심 포인트

Distance-Matrix Wasserstein (DMW) 통계량은 Gromov--Wasserstein (GW) 거리의 대규모 추정 문제를 해결하는 새로운 방법론입니다.
DMW는 GW의 완화(relaxation)이자 하한(lower bound)임을 수학적으로 증명했으며, 이 간극은 샘플링 오차에 의해 제어됩니다.
제안된 DMW 기법은 데이터 매니폴드에 의존하는 유한 샘플 경계와 확장 가능한 계산 방식을 포함합니다.
sliced 및 multi-scale DMW를 도입하여 효율적인 계산을 가능하게 했으며, 이는 합성 메트릭 공간, 그래프 분류 등 다양한 분야에서 활용됩니다.

Gromov--Wasserstein (GW) 거리는 공통의 좌표계(coordinate system)를 요구하지 않고 내부 거리(internal distances)를 통해 그래프, 형상(shapes), 그리고 포인트 클라우드(point clouds)를 비교합니다. 이러한 불변성(invariance)은 강력하지만, 이산(discrete) GW는 비볼록 이차 최적 운송(nonconvex quadratic optimal transport) 문제이며 대규모로 추정하기 어렵습니다. 우리는 무작위 유한 거리 행렬(random finite distance matrices)의 분포를 비교하는 Wasserstein 통계량의 계층 구조인 Distance-Matrix Wasserstein (DMW)를 제안합니다. DMW는 전역적인 포인트 수준의 정렬(point-level alignment)을 최적화하는 대신, 각 공간에서 $n$개의 포인트를 샘플링하고, 이들의 쌍별 거리(pairwise distances)를 기록하며, 결과로 나온 행렬 분포를 운송(transport)합니다. 우리는 DMW가 GW의 완화(relaxation)이자 하한(lower bound)임을 증명하며, 역 근사 부등식(reverse approximation inequality)을 확립합니다: 즉, GW--DMW 간극(gap)은 각 원래 측도(measure)를 $n$개의 샘플로 근사할 때 발생하는 Wasserstein 오차에 의해 제어됩니다. 따라서 샘플링된 부분 공간(subspaces)이 조밀해짐에 따라 모집단 DMW는 GW로 수렴합니다. 나아가 우리는 주변 행렬 차원 $inom n2$이 아닌 데이터 매니폴드(manifold)에 의존하는 내재적 차원(intrinsic-dimensional) 속도를 포함한 유한 샘플 경계(finite-sample bounds)를 제시합니다. 확장 가능한 계산을 위해, 우리는 sliced 및 multi-scale DMW를 도입합니다; $p=1$인 경우, sliced multi-scale 비유사도(dissimilarity)는 양의 정부호 지수 커널(positive-definite exponential kernels)을 생성합니다. 합성 메트릭 공간(synthetic metric spaces), 확장성 벤치마크, 그래프 분류, 그리고 두 샘플 검정(two-sample testing)에 대한 실험을 통해 이론을 검증하고 구조적 비교를 위한 해석 가능한 GW 스타일의 프록시(proxy)를 입증합니다.

AI 자동 생성 콘텐츠

원문 바로가기

확장 가능한 Gromov--Wasserstein 학습을 위한 거리 행렬 Wasserstein 통계량

요약

핵심 포인트

댓글