The Z-Gromov-Wasserstein Distance

이 논문은 임의의 거리 공간 $Z$를 값으로 갖는 커널이 부여된 측정 공간인 '$Z$-네트워크'를 정의하고, 이를 비교하기 위한 '$Z$-그로모프-워스터슈타인 ($Z$-GW) 거리'를 제안하여 기존 다양한 거리 방법론을 통합하는 이론적 틀을 마련하고 그 거리 공간의 수학적 성질과 실용적 계산 방법을 규명합니다.

핵심

1. 문제 상황: 서로 다른 언어를 쓰는 두 도시를 비교하다

상상해 보세요. 두 개의 아주 복잡한 도시가 있습니다.

• A 도시: 길거리의 거리, 건물의 높이, 주민들의 소득 분포 등 모든 것이 숫자로 표현됩니다.
• B 도시: 길거리의 거리, 건물의 '색깔', 주민들의 '취향' (예: 커피를 좋아하는지, 차를 좋아하는지) 등이 표현됩니다.

이 두 도시를 비교하려면 어떻게 해야 할까요?

• A 도시의 '거리'와 B 도시의 '색깔'을 어떻게 비교하죠? 숫자와 색깔은 서로 다른 단위입니다.
• 기존 수학 도구들은 보통 "두 대상이 모두 숫자로만 이루어져 있을 때"만 비교할 수 있었습니다. 하지만 현실 데이터는 훨씬 복잡합니다. 노드 (사람) 에는 이름이 있고, 엣지 (관계) 에는 신뢰도 점수가 있고, 또 다른 속성으로 색깔이 붙어 있을 수도 있습니다.

이런 서로 다른 속성 (Attribute) 을 가진 복잡한 데이터를 비교할 수 있는 새로운 '자'가 필요했습니다.

2. 해결책: Z-그로모프-워터스타인 (Z-GW) 거리

이 논문은 **"Z-네트워크"**라는 새로운 개념을 도입했습니다.

• Z (제이) 란 무엇인가?

  • Z 는 **'비교할 수 있는 모든 것의 집합'**입니다.
  • 만약 두 데이터의 속성이 '숫자'라면 Z 는 숫자 세계입니다.
  • 만약 속성이 '색깔'이라면 Z 는 색깔 세계입니다.
  • 만약 속성이 '확률 분포'라면 Z 는 확률 세계입니다.
  • 핵심: Z 는 우리가 비교하려는 데이터의 속성이 들어가는 '보편적인 저장소' 역할을 합니다.

• Z-네트워크 (Z-Network):

  • 기존에 우리는 "점과 점 사이의 거리"만 비교했습니다.
  • 하지만 Z-네트워크는 **"점과 점 사이의 관계가 Z 세계의 어떤 값으로 표현된다"**고 봅니다.
  • 예: 두 사람 사이의 관계가 단순히 '거리 5km'가 아니라, '신뢰도 0.8' (Z=숫자) 이거나, '공유된 취향 3 가지' (Z=색깔) 일 수 있습니다.

• Z-GW 거리:

  • 이제 두 개의 Z-네트워크 (두 도시) 를 비교할 때, 단순히 숫자만 비교하는 게 아니라, Z 세계의 규칙을 따라 두 네트워크를 어떻게 맞추면 가장 잘 겹쳐지는지 찾아냅니다.
  • 마치 두 개의 서로 다른 언어로 된 지도를 비교할 때, **번역기 (Z)**를 통해 두 지도의 구조가 얼마나 닮았는지 재는 것과 같습니다.

3. 이 연구의 핵심 기여 (왜 이것이 대단한가?)

이 논문은 단순히 새로운 자를 만든 것을 넘어, 이 자의 성질들을 수학적으로 완벽하게 증명했습니다.

1. 하나의 자로 모든 것을 재다 (통일성):

   • 기존에 학계에는 '그래프 비교법', '확률 분포 비교법', '동적 거리 비교법' 등 수많은 비교법이 따로따로 존재했습니다.
   • 이 논문은 **"아, 사실 이 모든 방법들은 Z-네트워크라는 큰 틀 안에서 Z 를 다르게 설정한 것에 불과하구나!"**라고 밝혀냈습니다.
   • 마치 "사과, 배, 포도 모두 '과일'이라는 큰 카테고리 안에 있다"고 밝힌 것과 같습니다. 이제 과일 하나하나를 따로 연구할 필요 없이, '과일'이라는 큰 원리를 연구하면 모두 해결됩니다.

2. 수학적인 안전장치 (완전성):

   • 이 새로운 자로 비교했을 때, "비슷한 것"과 "다른 것"을 명확히 구분할 수 있는지, 비교 결과가 갑자기 튀지 않는지 등 수학적으로 매우 튼튼한지를 증명했습니다.
   • 특히, 두 네트워크가 수학적으로 '동일한 구조'라면 거리가 0 이 되고, 다르면 0 이 아닌 값을 가진다는 것을 확실히 했습니다.

3. 계산 가능한 방법 제시:

   • 이론만 좋으면 쓸모가 없습니다. 이 논문은 복잡한 Z-네트워크를 비교할 때, 이미 잘 알려진 계산 방법 (Rn-네트워크) 으로 근사해서 계산할 수 있는 방법도 제시했습니다.
   • 즉, "너무 복잡한 Z 세계를 비교하기 힘들다면, 일단 간단한 숫자 세계로 번역해서 대략적인 거리를 재고, 오차 범위를 계산하면 된다"는 실용적인 가이드를 줍니다.

4. 일상생활에 비유하면?

• 과거: 두 개의 서로 다른 게임을 비교할 때, "A 게임은 점수제고 B 게임은 레벨제라 비교할 수 없어!"라고 포기했습니다.
• 이제 (Z-GW): "아, 두 게임 모두 '플레이어의 성장 곡선'이라는 공통된 Z(속성) 로 표현할 수 있구나! 이 성장 곡선을 비교하면 두 게임이 얼마나 유사한 구조를 가졌는지 알 수 있겠다!"라고 깨달은 것입니다.

5. 결론

이 논문은 데이터 과학과 기계 학습 분야에서 매우 중요한 이정표입니다.

• 복잡한 데이터 (그래프, 신경망, 분자 구조 등) 를 비교할 때 더 이상 각기 다른 방법을 쓰지 않아도 됩니다.
• Z-그로모프-워터스타인 거리라는 하나의 강력한 프레임워크를 통해, 데이터의 구조적 유사성을 정량적으로 측정할 수 있는 길을 열었습니다.
• 이는 향후 AI 가 더 복잡한 세상을 이해하고, 의약품 개발, 소셜 네트워크 분석, 3D 모델 비교 등 다양한 분야에서 더 정교한 분석을 가능하게 할 것입니다.

간단히 말해, **"서로 다른 언어로 된 복잡한 데이터들을 비교할 수 있는 보편적인 번역기와 자를 만들어, 수학적으로 완벽하게 증명했다"**는 것이 이 논문의 핵심입니다.

기술 요약

1. 문제 제기 (Problem)

• 복잡한 데이터 구조의 비교 필요성: 데이터 과학과 머신러닝 분야에서 노드와 엣지에 속성 (attributes) 이 부여된 그래프, 확률적 거리 공간, 동적 메트릭 공간 등 구조가 점점 더 복잡해지는 데이터셋을 비교해야 할 필요성이 증가하고 있습니다.
• 기존 GW 거리의 한계: 기존의 그로모프-워셔스테인 (GW) 거리는 주로 실수값 ($\mathbb{R}$) 을 갖는 커널 (adjacency matrix 등) 을 가진 메트릭 측정 공간 (metric measure spaces) 을 비교하는 데 사용되었습니다.
• 문제의 중복성: 새로운 GW 변형 (예: Fused GW, Attributed Graph GW 등) 이 등장할 때마다 매번 해당 거리가 거리 함수 (metric) 의 조건을 만족하는지, 완비성 (completeness) 이나 분리 가능성 (separability) 같은 위상적 성질이 있는지 증명하는 과정이 반복되어 왔습니다. 이는 비효율적이며, 이러한 변형들 사이의 공통된 수학적 본질을 파악하지 못하게 합니다.
• 핵심 질문: 임의의 거리 공간 $Z$에 값을 갖는 커널을 가진 네트워크를 비교하는 일반적인 프레임워크를 구축할 수 있으며, 이를 통해 기존 GW 변형들의 성질을 일괄적으로 유도할 수 있는가?

2. 방법론 (Methodology)

저자들은 **$Z$-네트워크 ($Z$-network)**라는 새로운 개념을 도입하고 이를 비교하기 위한 $Z$-그로모프-워셔스테인 ($Z$-GW) 거리를 정의했습니다.

• $Z$-네트워크 정의:
  • 전통적인 측정 네트워크 $(X, \omega_X, \mu_X)$에서 커널 함수 $\omega_X: X \times X \to \mathbb{R}$가 임의의 완비 분리 가능 거리 공간 $(Z, d_Z)$로 치환된 구조입니다.
  • 즉, $Z$-네트워크는 $(X, \omega_X, \mu_X)$로 정의되며, 여기서 $\omega_X$는 $Z$ 값의 $L^p$ 함수입니다.
• $Z$-GW 거리 정의:
  • 두 $Z$-네트워크 $X=(X, \omega_X, \mu_X)$와 $Y=(Y, \omega_Y, \mu_Y)$ 사이의 거리는 다음과 같이 정의됩니다:
    $$GW^Z_p(X, Y) = \frac{1}{2} \inf_{\pi \in \mathcal{C}(\mu_X, \mu_Y)} \left( \iint_{(X \times Y)^2} d_Z(\omega_X(x, x'), \omega_Y(y, y'))^p \, d\pi(x, y) d\pi(x', y') \right)^{1/p}$$
  • 여기서 $\pi$는 $\mu_X$와 $\mu_Y$의 결합 (coupling) 이며, $d_Z$는 타겟 공간 $Z$의 거리 함수입니다.
• 수학적 도구:
  • 최적 수송 (Optimal Transport) 이론, $L^p$ 공간 (거리 공간 값), 약한 동형 (weak isomorphism) 개념, 그리고 결합 공간의 위상적 성질 (Gluing Lemma 등) 을 활용하여 이론을 전개합니다.

3. 주요 기여 (Key Contributions)

1. 통일된 프레임워크 구축:

   • 기존 문헌에 등장하는 다양한 GW 변형들이 모두 적절한 $Z$ 선택 하에서 $Z$-GW 거리의 특수한 경우임을 증명했습니다.
   • 포함된 거리들:
     • 표준 GW 거리 ($Z=\mathbb{R}$)
     • 워셔스테인 거리 ($Z$는 임의의 거리 공간)
     • 초메트릭 GW 거리, $(p, q)$-GW 거리
     • Fused GW 거리 (노드 속성 포함), Fused Network GW 거리 (노드 및 엣지 속성 포함)
     • 스펙트럴 GW 거리, 동적 메트릭 공간 (DMS) 간 GW 거리
     • 그래폰 (Graphon) 의 컷 거리 (Cut distance) 와의 관계 분석
     • 새로운 적용 사례: 모양 그래프 (Shape Graphs), 연결 그래프 (Connection Graphs), 확률적 메트릭 공간 (Probabilistic Metric Spaces) 등을 $Z$-네트워크로 모델링할 수 있음을 보였습니다.

2. 거리 함수 (Metric) 성질의 증명:

   • $Z$가 분리 가능 (separable) 한 거리 공간일 때, $Z$-GW 거리가 약한 동형 (weak isomorphism) 을 식별자로 하여 **진정한 거리 함수 (metric)**가 됨을 증명했습니다.
   • 특히, 기존에 '완화된 삼각 부등식 (relaxed triangle inequality)'만 증명되었던 Fused GW 및 Fused Network GW 거리가 실제로 완전한 삼각 부등식을 만족함을 보였습니다.

3. 위상적 및 기하학적 성질 규명:

   • 분리 가능성 (Separability): $Z$가 분리 가능하면 $Z$-GW 공간도 분리 가능합니다.
   • 완비성 (Completeness): $Z$-GW 공간이 완비일 필요충분조건은 $Z$가 완비인 것입니다.
   • 축약 가능성 (Contractibility): $1 \le p < \infty$인 경우,$Z$의 위상과 무관하게$Z$-GW 공간은 항상 축약 가능 (contractible) 합니다. 이는 통계적 방법 (예: Fréchet 평균 계산) 에 유리한 성질입니다.
   • 측지선 (Geodesicity): $Z$가 측지선 공간이면 $Z$-GW 공간도 측지선 공간임을 증명했습니다. ($p=1$인 경우와 $p>1$인 경우의 차이점도 논의됨).

4. 계산적 접근 및 하한 (Lower Bounds):

   • NP-hard 인 정확한 GW 거리 계산을 대신할 수 있는 다항 시간 계산 가능한 하한 (Lower Bounds) 계층 구조를 제시했습니다.
   • 임의의 $Z$-네트워크를 유한 차원 $\mathbb{R}^n$-네트워크로 근사하여 기존 GW 알고리즘을 활용할 수 있음을 보였습니다 (Theorem 52). 이는 Hausdorff 거리에 기반한 오차 한계를 제공합니다.

4. 주요 결과 (Results)

• 정리 29 (Theorem 29): $Z$가 분리 가능하면 $Z$-GW 거리는 약한 동형에 대한 몫 공간에서 거리 함수를 정의합니다.
• 정리 39 (Theorem 39): $Z$-GW 공간의 완비성은 타겟 공간 $Z$의 완비성과 동치입니다.
• 정리 42 (Theorem 42): $p < \infty$인 경우, $Z$-GW 공간은 $Z$의 위상 구조와 무관하게 항상 축약 가능합니다. 이는 공간이 위상적으로 매우 단순함을 의미합니다.
• 정리 52 (Theorem 52): 유계인 거리 공간 $Z$에 대해, $Z$-GW 거리는 $\mathbb{R}^n$-GW 거리로 근사할 수 있으며, 그 오차는 $Z$와 근사점 집합 $Q$ 사이의 하우스도르프 거리로 제어됩니다.
• 계산적 결과: $Z$-GW 거리의 하한을 계산하는 알고리즘을 제안했으며, 이를 통해 기존 GW 솔버를 변형하여 복잡한 속성 데이터를 처리할 수 있음을 보였습니다.

5. 의의 및 향후 전망 (Significance)

• 이론적 통합: 기존에 산발적으로 존재하던 GW 변형들의 성질 증명 작업을 제거하고, 하나의 고차원 원리에서 모든 성질을 유도할 수 있게 했습니다. 이는 향후 새로운 GW 변형이 등장할 때 추가적인 증명 노력이 불필요하게 만듭니다.
• 새로운 데이터 분석 도구: 모양 그래프, 연결 그래프, 확률적 메트릭 공간 등 기존 GW 거리로는 다루기 어려웠던 복잡한 데이터 구조를 체계적으로 비교하고 분석할 수 있는 수학적 기반을 마련했습니다.
• 실용적 적용 가능성:
  • 축약 가능성: 공간이 축약 가능하므로 Fréchet 평균과 같은 기하학적 통계량을 정의하고 계산하는 것이 이론적으로 가능합니다.
  • 근사 알고리즘: $\mathbb{R}^n$으로의 근사 이론은 실제 대규모 데이터셋에 대한 효율적인 GW 거리 계산을 가능하게 합니다.
• 미래 연구 방향:
  • $p=\infty$인 경우 (Gromov-Hausdorff 거리와 유사) 의 위상적 성질 (축약 가능성 등) 에 대한 추가 연구.
  • $Z$-GW 공간의 곡률 (curvature) 경계와 Alexandrov 기하학의 연결.
  • 최적 결합 (optimal coupling) 의 구조에 대한 심층 분석 및 실제 머신러닝 응용 (예: 분자 구조 비교, 사회 네트워크 분석 등) 에의 적용.

결론적으로, 이 논문은 Gromov-Wasserstein 거리의 이론적 기반을 확장하고 강화하여, 복잡하고 다양한 형태의 데이터 구조를 비교하는 데 있어 강력한 통일된 수학적 도구를 제공한다는 점에서 중요한 의의를 가집니다.