用吴方法比较图结构,实现无需嵌入的图分类。
$k$-Nearest Neighbors in Gromov--Wasserstein Space

- 直接用吴距离衡量图间差异,不依赖节点对齐或嵌入。
- 理论证明分类器在多种图数据上具普遍一致性。
- 适合处理带属性的异构图分类,性能稳定可靠。
吴-沃瑟斯坦(GW)距离提供了一种比较度量测度空间的框架,不受底层结构或几何限制。对于网络数据,它可直接比较节点数不同的图,无需嵌入或其他抽象。通过融合吴-沃瑟斯坦(fGW)变体,还可结合节点特征与图结构。本文基于GW与fGW距离实现k近邻(k-NN)分类。证明了在有限支撑且均匀概率测度的度量测度空间等价类上,GW-k-NN分类器具有普遍一致性。将图视为带有成对距离度量和节点均匀概率测度的有限支撑度量测度空间,得到GW-k-NN在图空间中的普遍一致性。类似地,对包含欧氏空间特征映射的结构化对象弱同构类,也证明了fGW-k-NN的普遍一致性,从而确立其在带属性图空间中的普遍一致性。数值实验表明,GW-k-NN与fGW-k-NN在多个图数据集上表现稳定,说明基于度量的k-NN在吴框架中效果良好。
原文摘要 · Abstract (English)
The Gromov--Wasserstein (GW) distance provides a framework for comparing metric measure spaces, regardless of their underlying structure or geometry. For network-based data, it enables direct comparisons of graphs with different numbers of nodes, without requiring an embedding or other abstraction. Furthermore, through a variant of GW known as fused Gromov--Wasserstein (fGW), it is also possible to incorporate node features in addition to graph structure. In this work, we implement $k$-nearest neighbors ($k$-NN) classification using the GW and fGW distances. We prove the universal consistency of the GW-$k$-NN classifier on the space of equivalence classes of metric measure spaces with finite support and uniform probability measure. By viewing graphs as finitely supported metric measure spaces equipped with the pairwise distance metric and a uniform probability measure on the nodes, we obtain universal consistency of GW-$k$-NN for the space of graphs. Likewise for fGW-$k$-NN, we prove universal consistency on the space of weak isomorphism classes of structured objects consisting of metric measure spaces with finite support and uniform probability measure and feature maps into Euclidean space, thus establishing universal consistency on the space of node-attributed graphs. Our numerical experiments show that GW-$k$-NN and fGW-$k$-NN consistently perform well across multiple graph datasets, suggesting that metric classifiers such as $k$-NN work well in the GW framework.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。