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

技术摘要：Gromov–Wasserstein 空间中的 $k$-最近邻算法

问题陈述
本文研究了在严谨的度量学习框架下，对包括无属性图和有节点属性图在内的图结构数据的分类挑战。传统的 $k$-最近邻 ($k$-NN) 分类器依赖于定义在欧几里得或标准度量空间中的距离函数。然而，图通常具有复杂的结构，使得直接比较变得困难，特别是当图具有不同的节点数量或缺乏规范嵌入时。虽然 Gromov–Wasserstein (GW) 距离为比较度量测度空间 (mm-spaces) 提供了一个框架，且融合 Gromov–Wasserstein (fGW) 距离将其扩展到了包含节点特征的情况，但这些特定度量空间中运行的 $k$-NN 分类器的理论性质此前是未知的。具体而言，目前尚不清楚当底层空间是配备 GW 或 fGW 距离的图空间时，$k$-NN 是否具有通用一致性（即收敛到最优贝叶斯风险）。

方法论
作者利用 GW 和 fGW 距离实现了 $k$-NN 分类，并对其理论一致性进行了研究。其方法论的核心在于通过建立这些度量空间的拓扑性质，以满足实现通用一致性所需的条件。

1. 度量空间定义：

   • GW 空间 ($\mathbb{X}$): 具有有限支撑和均匀概率测度的 mm-spaces 等价类空间，配备 $p=2$ 的 Gromov–Wasserstein 距离。这用于建模无属性图。
   • fGW 空间 ($\mathbb{Y}^f$): 结构化对象（向 $\mathbb{R}^d$ 映射特征图的 mm-spaces）的弱同构类空间，配备融合 Gromov–Wasserstein 距离 ($p=1, q=2$)。这用于建模有节点属性的图。

2. 理论框架：
   作者依赖于学习理论中已建立的结果（特别是 Chaudhuri 和 Dasgupta [9]），这些结果指出，如果一个可分度量空间拥有 $\sigma$-有限度量维度（这是一个与勒贝格微分条件相关的性质），则 $k$-NN 在该空间上是通用一致的。为了证明这一点，作者：

   • 在这些框架内构建了 $n$ 点空间的有限维模型。
   • 证明了 $n$ 点图空间与特定的欧几里得矩阵商空间（针对 GW）以及矩阵与特征向量乘积空间（针对 fGW）之间存在 双 Lipschitz 映射 (bi-Lipschitz maps)。
   • 证明了这些商空间具有有限的 Assouad-Nagata 维度。
   • 利用引理 2.4 表明，向有限维空间存在双 Lipschitz 映射这一事实，意味着目标空间 ($\mathbb{X}$ 和 $\mathbb{Y}^f$) 具有 $\sigma$-有限度量维度。

3. 数值实验：
   作者在七个基准数据集上评估了 GW-$k_n$-NN 和 fGW-$k_n$-NN 的性能：

   • 有属性图： BZR、COX-2 和 PROTEINS（分子数据集）。
   • 无属性图： IMDb-B、IMDb-M（社交网络）以及两个合成数据集 (ERSBM1, ERSBM2)。
   • 基准方法： 与图卷积网络 (GCN)、各种图核方法（最短路径、Graphlet、HOPPER、Propagation）以及使用 GW/fGW 核的 SVM 进行对比。

核心贡献
这项工作的首要贡献是证明了在使用 GW 和 fGW 距离进行图分类的背景下，$k$-NN 分类器的通用一致性。

• 理论结果：

  • 定理 1.8： 证明了在满足 $k \to \infty$ 且 $k/n \to 0$ 的条件下，GW-$k_n$-NN 分类器在图空间 $(\mathbb{X}, GW_2)$ 上是通用弱一致的。若满足 $k/\log(n) \to \infty$，则它是通用强一致的。
  • 定理 1.9： 证明了相同的一致性结果对于有节点属性图空间 $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ 中的 fGW-$k_n$-NN 分类器同样成立。
  • 这些结果是通过证明这两个空间都是可分的，并且拥有 $\sigma$-有限度量维度（该维度是通过双 Lipschitz 嵌入到欧几里得空间的商空间中推导出来的）来建立的。

• 实证结果：

  • 在有属性图数据集（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 更具效率优势。

意义与主张
本文声称为在 Gromov–Wasserstein 框架内使用 $k$-NN 等度量分类器建立了理论基础。通过证明通用一致性，作者认为这些方法不仅是启发式的，而且在图分类任务中具有理论上的完备性。

其意义在于弥合了最优传输理论与结构化数据统计学习理论之间的鸿者。作者强调，他们的方法提供了一个“高度可解释的框架”，其中图之间的距离直接衡量了结构相似性（同构意味着距离为零）。他们明确指出，据其所知，这是首次将 GW-$k$-NN 应用于图分类，也是首次对其一致性进行理论证明。

该论文对于未来的泛化保持了审慎的态度。作者承认，虽然一致性已针对特定参数（GW 对应 $p=2$，fGW 对应 $p=1, q=2$）得到证明，但对于其他参数选择或在最一般的 Z-Gromov–Wasserstein 设置下是否仍然成立，仍是一个开放性问题。作者推测，类似于 Wasserstein 空间，如果不加特定限制，通用一致性可能无法在最广泛的范畴内成立。