arXiv:2412.12185cs.LGcs.AI2024-12被引 1

提出可解释的神经节点对齐方法,实现无需真实标签的精确图相似性计算。

Graph Similarity Computation via Interpretable Neural Node Alignment

  • 将图编辑距离中的二次分配问题转化为嵌入空间的线性对齐
  • 通过可微Gumbel-Sinkhorn模块无监督生成最优一对一节点匹配矩阵
  • 在真实图数据集上相比当前最优方法误差降低16%,检索指标提升12%

图相似性计算在药物检索、社交网络好友推荐等实际应用中至关重要。图编辑距离(GED)与最大公共子图(MCS)是常用的通用度量方法,但精确计算GED属于NP难问题。现有基于神经网络的方法虽能近似计算,但缺乏可解释性,难以还原经典方法中的一一节点/子图对齐过程。本文提出一种无需依赖节点对齐真值的可解释神经节点对齐模型:首先将经典GED中的二次分配问题松弛为嵌入空间的线性对齐;其次引入可微的Gumbel-Sinkhorn模块,无监督生成最优的一对一节点对齐矩阵。在真实图数据集上的实验表明,该方法在图相似性计算与图检索任务中均优于现有最佳方法,分别实现16%的均方误差下降和12%的检索评估指标提升。

原文摘要 · Abstract (English)

\Graph similarity computation is an essential task in many real-world graph-related applications such as retrieving the similar drugs given a query chemical compound or finding the user's potential friends from the social network database. Graph Edit Distance (GED) and Maximum Common Subgraphs (MCS) are the two commonly used domain-agnostic metrics to evaluate graph similarity in practice. Unfortunately, computing the exact GED is known to be a NP-hard problem. To solve this limitation, neural network based models have been proposed to approximate the calculations of GED/MCS. However, deep learning models are well-known ``black boxes'', thus the typically characteristic one-to-one node/subgraph alignment process in the classical computations of GED and MCS cannot be seen. Existing methods have paid attention to approximating the node/subgraph alignment (soft alignment), but the one-to-one node alignment (hard alignment) has not yet been solved. To fill this gap, in this paper we propose a novel interpretable neural node alignment model without relying on node alignment ground truth information. Firstly, the quadratic assignment problem in classical GED computation is relaxed to a linear alignment via embedding the features in the node embedding space. Secondly, a differentiable Gumbel-Sinkhorn module is proposed to unsupervised generate the optimal one-to-one node alignment matrix. Experimental results in real-world graph datasets demonstrate that our method outperforms the state-of-the-art methods in graph similarity computation and graph retrieval tasks, achieving up to 16\% reduction in the Mean Squared Error and up to 12\% improvement in the retrieval evaluation metrics, respectively.

图神经网络图相似性可解释性

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