📊 statistics

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

이 논문은 그래프와 노드 속성 그래프를 각각 비교하기 위해 그로모프-바서슈타인(Gromov–Wasserstein) 및 융합 그로모프-바서슈타인(fused Gromov–Wasserstein) 거리를 사용하여 $k$ -최근접 이웃 분류를 구현하며, 이러한 분류기들의 보편적 일관성을 증명하는 동시에 여러 데이터셋에 걸친 강력한 경험적 성능을 입증한다.

원저자: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

게시일 2026-06-10

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 서로 다른 다양한 물체들이 쌓여 있는 거대한 더미를 분류하려고 한다고 상상해 보십시오. 어떤 것들은 단순한 모양이고, 어떤 것들은 지하철 노선도나 사회적 관계망처럼 복잡한 네트워크 형태를 띠고 있습니다. 당신의 목표는 이미 알고 있는 물체들을 보고, 처음 보는 새로운 물체가 어떤 카테고리에 속하는지 알아내는 것입니다. 이것이 바로 $k$ -최근접 이웃( $k$ -NN) 분류기의 역할입니다.

$k$ -NN을 주변 이웃들 사이의 "인기 투표"라고 생각해 보세요. 만약 당신이 알려진 물체들이 가득한 방에 새로운 물체를 떨어뜨린다면, 당신은 가장 가까이 있는 $k$ 개의 이웃을 살펴봅니다. 만약 그 이웃들 대부분이 "고양이"라면, 당신은 새로운 물체도 고양이일 것이라고 추측합니다.

문제는 이렇습니다: 물체들이 정해진 크기나 모양이 없는 복잡한 네트워크(그래프)일 때, "가까움"을 어떻게 측정할 것인가? 단순히 지도 위의 두 점 사이의 거리를 측정하는 방식으로는 불가능합니다.

이 논문은 **그로모프-와서스타인(Gromov–Wasserstein, GW)**과 **퓨즈드 그로모프-와서스타인(Fused Gromov–Wasserstein, fGW)**이라는 개념을 사용하여 이 거리를 측정하는 영리한 새로운 방법을 소개합니다. 이해를 돕기 위해 쉬운 용어로 설명해 드리겠습니다.

1. 문제: 사과와 오렌지를 비교하는 것 (그리고 오렌지와 비행기를 비교하는 것)

보통 두 대상을 비교하려면 크기가 같아야 합니다. 만약 두 개의 그래프(점과 선의 네트워크)를 비교하고 싶다면, 전통적인 방식들은 종종 두 그래프의 크기를 강제로 맞추거나, 그것들을 하나의 숫자 리스트(임베딩)로 변환해야 합니다. 이는 마치 작은 가계도와 거대한 기업 조직도를 똑같이 작은 상자 안에 구겨 넣으려고 하는 것과 같습니다. 이 과정에서 정보가 손실됩니다.

2. 해결책: "형태를 바꾸는" 자

저자들은 그로모프-와서스타인 거리라는 수학적 도구를 사용합니다.

비유: 서로 다른 두 도시가 있다고 상상해 보십시오. 하나는 격자 구조(맨해튼 같은)이고, 다른 하나는 굽이굽이 이어진 도로망(샌프란시스코 같은)입니다. 겉모습은 완전히 다릅니다.
GW의 마법: GW는 도로를 직접 비교하는 대신 다음과 같이 묻습니다. "만약 내가 도시 A의 사람들을 도시 B의 인구 밀도에 맞춰 마법처럼 재배치할 수 있다면, 이웃 간의 '관계적 거리'가 얼마나 변할까?"
GW는 도시의 인구가 100명인지 1,000명인지 상관하지 않습니다. 오직 관계의 패턴에만 주목합니다. 만약 도시 A에 연결이 많은 "허브"가 있고 도시 B에도 유사한 "허브"가 있다면, GW는 "이 두 도시는 구조적으로 유사하다"라고 판단합니다. 즉, 지도로 볼 때 모습이 다르더라도 말입니다.

3. "특징" 추가하기: 퓨즈드(Fused) 버전

때때로 네트워크의 점들은 추가적인 정보를 가지고 있습니다. 예를 들어, 분자 그래프에서 각 원자는 특정 종류(탄소, 산소 등)를 가집니다. 사회적 관계망에서는 각 사람이 직업을 가질 수 있습니다.

비유: 다시 두 도시를 비교한다고 해봅시다. GW는 도로의 패턴을 봅니다. 하지만 만약 건물들의 '유형'도 함께 비교하고 싶다면 어떨까요?
fGW의 마법: 퓨즈드 그로모프-와서스타인(fGW) 거리는 이 두 가지를 동시에 수행합니다. 도로 패턴이 일치하는지 확인하는 동시에, 유사한 위치에 있는 건물들의 유형도 일치하는지 확인합니다. 이는 도시의 형태와 집의 색깔을 모두 측정하는 자와 같습니다.

4. 핵심 주장: "항상 작동한다" (보편적 일관성)

저자들은 단순히 새로운 자를 만든 것이 아니라, 이 자를 $k$ -NN 방식과 함께 사용할 때 결국에는 항상 작동한다는 것을 수학적으로 증명했습니다.

보장된 결과: 저자들은 더 많은 학습 데이터(그래프의 예시들)를 계속 추가할수록, 이 새로운 거리를 사용하는 $k$ -NN 분류기가 이론적으로 가능한 최고 수준의 정확도에 도달하게 된다는 것을 증명했습니다.
주의 사항: 이 증명은 데이터가 늘어남에 따라 "이웃의 수"( $k$ )를 선택하는 특정 규칙을 따를 경우, 모든 크기의 그래프에 대해 유효합니다. 저자들은 모든 가능한 그래프의 공간이 이 수학적 원리가 성립할 만큼 충분히 매끄럽게 작동함을 보여주었습니다.

5. 실험: 실제로 도움이 되는가?

저자들은 실제 데이터를 통해 자신들의 방법을 테스트했습니다.

분자: 구조와 원자 유형을 기반으로 화학 물질을 분류합니다.
사회적 관계망: 영화 협업 네트워크(예: "액션" 영화 vs "로맨스" 영화)를 분류합니다.
합성 데이터: 한계를 테스트하기 위해 만들어진 가상의 네트워크입니다.

결과:

저자들의 방법(GW- $k$ -NN 및 fGW- $k$ -NN)은 매우 우수한 성능을 보였으며, 종종 그래프 신경망(GCN)이나 복잡한 그래프 커널과 같은 인기 있는 다른 방법들과 대등하거나 더 나은 성능을 보였습니다.
주요 발견: 추가 데이터(원자 유형)가 있는 분자의 경우, "퓨즈드" 버전(fGW)이 확실한 승자였습니다. 이는 구조와 특징을 함께 살펴보는 것이 하나만 보는 것보다 더 낫다는 것을 보여주었습니다.
효율성: 수학적 계산은 무겁지만, 특히 속성이 없는 그래프의 경우 이 방법은 다른 복잡한 방법들에 비해 놀라울 정도로 빠르고 효율적이었습니다.

요 요약

이 논문의 핵심은 다음과 같습니다: "우리는 크기나 모양에 상관없이 복잡한 네트워크 간의 유사성을 측정하는 방법을 찾아냈습니다. 이 측정법을 사용하여 가장 가까운 이웃을 기준으로 새로운 네트워크를 분류하면, 더 많은 데이터를 입력할수록 수학적으로 점점 더 정확해진다는 것을 증명했습니다. 실험 결과, 우리의 방법은 분자 식별이나 영화 장르 분류와 같은 실제 문제에서 매우 잘 작동함을 확인했습니다."

이 논문이 주장하지 않은 것:

이 방법이 모든 종류의 데이터(그래프 및 구조화된 객체만 해당)에 적용된다고 주장하지 않았습니다.
이 방법이 세상에서 가장 빠른 방법이라고 주장하지 않았습니다(계산량이 많을 수 있음을 언급하며, 다른 방법들과 경쟁력이 있음을 보여주었습니다).
의료 진단이나 임상적 용도로 적용하지 않았으며, 엄격하게 그래프 분류 작업에 집중했습니다.

기술 요약: 그로모프-바서슈타인 공간에서의 $k$ -최근접 이웃( $k$ -NN)

문제 정의
본 논문은 엄격한 메트릭 학습 프레워크 내에서 속성이 없는 그래프와 노드 속성이 있는 그래프를 모두 포함하는 그래프 구조 데이터의 분류 문제를 다룹다. 전통적인 $k$ -최근접 이웃( $k$ -NN) 분류기는 유클리드 또는 표준 메트릭 공간에 정의된 거리 함수에 의존한다. 그러나 그래프는 직접적인 비교가 어려운 복잡한 구조를 가진 경우가 많으며, 특히 그래프들의 노드 수가 다르거나 정형화된 임베딩이 없는 경우 더욱 그러하다. 그로모프-바서슈타인(Gromov–Wasserstein, GW) 거리는 메트릭 측정 공간(mm-spaces)을 비교하는 프레임워크를 제공하며, 융합 그로모프-바서슈타인(fused Gromov–Wasserstein, fGW) 거리는 이를 노드 특징까지 확장하여 모델링한다. 하지만 이러한 특정 메트릭 공간 내에서 작동하는 $k$ -NN 분류기의 이론적 특성은 기존에 알려져 있지 않았다. 구체적으로, 기저 공간이 GW 또는 fGW 거리를 갖춘 그래프 공간일 때, $k$ -NN이 보편적 일관성(universal consistency, 최적의 베이즈 위험으로 수렴함)을 갖는지 여부가 불분명했다.

방법론
저자들은 GW 및 fGW 거리를 이용한 $k$ -NN 분류를 구현하고 그 이론적 일관성을 조사한다. 이들의 방법론의 핵심은 보편적 일관성을 충족하는 데 필요한 조건을 만족하도록 해당 메트릭 공간의 위상적 성질을 확립하는 것이다.

메트릭 공간 정의:
- GW 공간 ( $\mathbb{X}$ ): 유한한 지지 집합(finite support)과 균등 확률 측량을 가진 mm-space의 동치류(equivalence classes)의 공간으로, $p=2$ 그로모프-바서슈타인 거리를 사용한다. 이는 속성이 없는 그래프를 모델링한다.
- fGW 공간 ( $\mathbb{Y}^f$ ): 구조화된 객체(특징 맵이 $\mathbb{R}^d$ 로 매핑되는 mm-space)의 약 동형류(weak isomorphism classes) 공간으로, 융합 그로모프-바서슈타인 거리( $p=1, q=2$ )를 사용한다. 이는 노드 속성이 있는 그래프를 모델링한다.
이론적 프레임워크:
저자들은 $k$ -NN이 분리 가능한 메트릭 공간(separable metric space)에서 보편적 일관성을 갖는다는 학습 이론의 확립된 결과(특히 Chaudhuri와 Dasgupta [9])에 의존한다. 이 공간이 $\sigma$ -유한 메트릭 차원(Lebesgue 미분 조건과 관련된 성질)을 갖는다는 점을 입증하기 위해, 저자들은 다음을 수행한다:
- 이 프레임워크 내에서 $n$ -점 공간에 대한 유한 차원 모델을 구축한다.
- $n$ -점 그래프의 공간과 특정 유클리드 행렬의 몫 공간(GW의 경우), 그리고 행렬과 특징 벡터의 곱 공간(fGW의 경우) 사이의 비-립시츠(bi-Lipschitz) 사상의 존재를 증명한다.
- 이러한 몫 공간들이 유한한 Assouad-Nagata 차원을 가짐을 증명한다.
- Lemma 2.4를 활용하여, 유한 차원을 가진 공간으로의 비-립시츠 사상의 존재가 대상 공간( $\mathbb{X}$ 및 $\mathbb{Y}^f$ )이 $\sigma$ -유한 메트릭 차원을 가짐을 함의함을 보여준다.
수치 실험:
저자들은 7개의 벤치마크 데이터셋에 대해 GW- $k_n$ -NN 및 fGW- $k_n$ -NN의 성능을 평가한다:
- 속성 그래프: BZR, COX-2, PROTEINS (분자 데이터셋).
- 비속성 그래프: IMDb-B, IMDb-M (소셜 네트워크), 그리고 두 개의 합성 데이터셋 (ERSBM1, ERSBM2).
- 베이스라인: 그래프 합성곱 신경망(GCN), 다양한 그래프 커널 방법(Shortest Path, Graphlet, HOPPER, Propagation), 그리고 GW/fGW 커널을 사용하는 SVM과의 비교.

주요 기여
본 연구의 주요 기여는 GW 및 fGW 거리를 사용한 그래프 분류 맥락에서 $k$ -NN 분류기의 보편적 일관성(universal consistency)을 증명한 것이다.

이론적 결과:
- 정리 1.8: $k \to \infty$ 및 $k/n \to 0$ 조건 하에서, 그래프 공간 $(\mathbb{X}, GW_2)$ 에 대해 GW- $k_n$ -NN 분류기가 보편적 약 일관성(universally weakly consistent)을 가짐을 증명한다. 또한 $k/\log(n) \to \infty$ 일 때 보편적 강 일관성(universally strongly consistent)을 갖는다.
- 정리 1.9: 노드 속성 그래프 공간 $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ 에 대해 동일한 일관성 결과를 증명한다.
- 이러한 결과는 두 공간이 분리 가능하며, 유클리드 공간의 몫 공간으로의 비-립시츠 임베딩을 통해 도출된 $\sigma$ -유한 메트릭 차원을 가짐을 보여줌으로써 확립된다.
실험적 결과:
- 속성 그래프 데이터셋(BZR, COX-2, PROTEINS)에서 fGW- $k_n$ -NN은 GCN 및 다른 커널 기반 방법들을 능가하며 지속적으로 가장 높은 평균 정확도를 달성했다. GW- $k_n$ -NN 역시 경쟁력 있는 성능을 보였다.
- 비속성 데이터셋에서 GW- $k_n$ -NN은 ERSBM2 합성 데이터셋에서 완벽한 정확도(100%)를 기록했으며, IMDb-B에서 그래프 커널과 GCN을 능가하는 강력한 성능을 보였다.
- 저자들은 GW/fGW 방법이 해석 가능하지만(작은 거리는 구조적 유사성을 의미함), 일부 커널 방법과 비교했을 때 계산 집약적일 수 있으나 특정 맥락에서는 GW 커널을 사용하는 SVM보다 효율성 개선을 제공한다고 언급한다.

의의 및 주장
본 논문은 그로모프-바서슈타인 프레임워크 내에서 $k$ -NN과 같은 메트릭 분류기를 사용하기 위한 이론적 토대를 구축한다고 주장한다. 보편적 일관성을 증명함으로써, 저자들은 이러한 방법들이 단순한 휴리스틱이 아니라 그래프 분류 작업에 있어 이론적으로 타당하다고 주장한다.

이 연구의 의의는 최적 운송 이론(optimal transport theory)과 구조화된 데이터를 위한 통계적 학습 이론 사이의 간극을 메우는 데 있다. 저자들은 자신들의 접근 방식이 "매우 해석 가능한 프레임워크"를 제공하며, 여기서 그래프 간의 거리는 구조적 유사성을 직접 측정한다(동형(isomorphism)은 거리가 0임을 의미함)는 점을 강조한다. 또한, 자신들이 아는 바로는 이것이 그래프 분류에 GW- $k$ -NN을 적용한 첫 번째 사례이며, 그 일관성에 대한 첫 번째 이론적 증명이라고 명시한다.

논문은 향후 일반화에 대해 신중한 태도를 유지한다. 특정 파라미터( $\text{GW의 } p=2, \text{ fGW의 } p=1, q=2$ )에 대해서는 일관성이 증명되었으나, 이러한 결과가 다른 파라미터 선택이나 가장 일반적인 Z-그로모프-바서슈타인 설정에서도 유지될지는 여전히 미해결 과제로 남아 있음을 인정한다. 저자들은 바서슈타인 공간과 유사하게, 특정 제약 조건 없이는 일반적인 상황에서 보편적 일관성이 성립하지 않을 수 있다는 가설을 제시한다.