arXiv:2511.19837cs.LGcs.AI2025-11

提出新框架,让图相似度计算更贴近真实编辑距离。

GED-Consistent Disentanglement of Aligned and Unaligned Substructures for Graph Similarity Learning

  • 从节点匹配转向图与子结构级匹配,更符合编辑距离原理。
  • 在4个基准数据集上达到最优性能,显著提升相似度计算精度。
  • 适合研究图神经网络、图对齐与相似性分析的学者使用。

图相似度计算(GSC)是图相关任务的基础,图编辑距离(GED)是常用度量标准。GED由两图间的最优对齐决定,将每图划分为零成本的对齐子结构和需代价的非对齐子结构。由于精确计算GED属于NP难问题,基于图神经网络(GNN)的近似方法应运而生。现有基于GNN的GED方法通常学习各图的节点嵌入,再聚合成对节点相似性以估计最终相似度。尽管有效,但其节点中心匹配范式与GED核心原则存在不一致,导致两大局限:(1)无法捕捉最优对齐的全局结构对应关系;(2)因虚假节点级信号导致编辑代价误判。为此,我们提出GCGSim框架,聚焦图级匹配与子结构级编辑代价,实现与GED一致的图相似度学习。具体贡献包括三方面技术革新。在四个基准数据集上的实验表明,GCGSim达到当前最优性能。全面分析进一步验证该框架能有效学习解耦且语义明确的子结构表示。

原文摘要 · Abstract (English)

Graph Similarity Computation (GSC) is a fundamental graph related task where Graph Edit Distance (GED) serves as a prevalent metric. GED is determined by an optimal alignment between a pair of graphs that partitions each into aligned (zero-cost) and unaligned (cost-incurring) substructures. Due to NP-hard nature of exact GED computation, GED approximations based on Graph Neural Network(GNN) have emerged. Existing GNN-based GED approaches typically learn node embeddings for each graph and then aggregate pairwise node similarities to estimate the final similarity. Despite their effectiveness, we identify a mismatch between this prevalent node-centric matching paradigm and the core principles of GED. This discrepancy leads to two critical limitations: (1) a failure to capture the global structural correspondence for optimal alignment, and (2) a misattribution of edit costs driven by spurious node level signals. To address these limitations, we propose GCGSim, a GED-consistent graph similarity learning framework centering on graph-level matching and substructure-level edit costs. Specifically, we make three core technical contributions. Extensive experiments on four benchmark datasets show that GCGSim achieves state-of-the-art performance. Our comprehensive analyses further validate that the framework effectively learns disentangled and semantically meaningful substructure representations.

图相似度子结构图神经网络对齐

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。