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

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)를 입증합니다.