用扩散过程提升图匹配精度,尤其在噪声和缺失边时表现更稳。
Diffusion enabled Optimal Transport distances for graph matching
- 融合扩散机制的半松弛融合格罗莫夫-沃瑟斯坦距离
- 在中等难度任务中使ARI提升至正数,最高比基线高20个百分点
- 适合处理噪声大、结构不完整的真实图数据
本文提出Diffusion Semi-Relaxed Fused Gromov-Wasserstein(DsrFGW),一种统一节点特征与结构连接性的图比较新方法。传统Gromov-Wasserstein及其半松弛变体(srGW, srFGW)在稀疏、含噪或部分观测图上表现不佳。受图扩散距离启发,即图若能产生相似的信息传播模式则视为相似,DsrFGW引入扩散过程,实现跨节点的信息传播,捕捉局部与全局结构模式,降低对噪声或缺失边的敏感性。在36个合成成对图匹配任务(易、中、难)上的广泛评估显示,其性能持续优于srFGW:准确率提升0-20个百分点,且在中等难度场景下,srFGW常出现负ARI(劣于随机),而DsrFGW在内部与外部聚类质量指标(调整兰德指数与真实聚类下的准确率)上均显著提升。即使在严重噪声下,92%的合成任务中,通过最优扩散尺度自适应问题难度,仍保持聚类质量优势,确立了其在结构不确定情形下的鲁棒图比较框架地位。
原文摘要 · Abstract (English)
This paper introduces Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW), a novel method for graph comparison that unifies node features and structural connectivity through optimal transport. While traditional Gromov-Wasserstein and semi-relaxed variants (srGW, srFGW) capture graph structure, they often struggle with sparse, noisy, or partially observed graphs. Inspired by Graph Diffusion Distance, which posits graphs are similar if they enable similar information transmission patterns, DsrFGW incorporates diffusion processes allowing information propagation across nodes, capturing local and global structural patterns while reducing sensitivity to noise or missing edges. An extensive evaluation on 36 synthetic pairwise graph matching tasks (easy, medium, hard) demonstrates consistent superiority over srFGW, achieving accuracy improvements of 0-20 percentage points and dramatic Adjusted Rand Index (ARI) gains: in medium-difficulty scenarios, srFGW often achieves negative ARI (worse than random) while DsrFGW offers better performance in terms of both internal and external clustering quality measures (i.e., Adjusted Rank Index and Accuracy with respect to the true underlying clusters, respectively). Even under severe noise, DsrFGW improves clustering quality in 92% of the synthetic tasks with optimal diffusion scales adapting to problem difficulty, establishing DsrFGW as a robust framework for graph comparison under structural uncertainty.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。