论文标题
通过最大常见子图推理的更可解释的图相似度计算
More Interpretable Graph Similarity Computation via Maximum Common Subgraph Inference
论文作者
论文摘要
在各种与图相关的任务中出现了计算两个图之间的距离/相似性的图形相似性测量。最近的基于学习的方法缺乏可解释性，因为它们直接将两个图之间的交互信息转换为一个隐藏的向量，然后将其映射到相似性。为了解决这个问题，本研究提出了一个更容易解释的端到端范式，用于图形相似性学习，通过最大常见的子图推理（INFMC）命名相似性计算。我们对INFMCS的关键见解是相似性评分与最大常见子图（MCS）之间的牢固相关性。我们隐含地推断MC以获得归一化的MCS大小，其监督信息仅是训练期间的相似性评分。为了捕获更多的全局信息，我们还使用图形卷积层堆叠一些香草变压器编码层，并提出了一种新颖的置换式插入节点位置编码。整个模型非常简单却有效。全面的实验表明，INFMC始终优于用于图形分类和回归任务的最先进的基线。消融实验验证了提出的计算范式和其他组件的有效性。此外，结果的可视化和统计数据揭示了INFMC的解释性。
Graph similarity measurement, which computes the distance/similarity between two graphs, arises in various graph-related tasks. Recent learning-based methods lack interpretability, as they directly transform interaction information between two graphs into one hidden vector and then map it to similarity. To cope with this problem, this study proposes a more interpretable end-to-end paradigm for graph similarity learning, named Similarity Computation via Maximum Common Subgraph Inference (INFMCS). Our critical insight into INFMCS is the strong correlation between similarity score and Maximum Common Subgraph (MCS). We implicitly infer MCS to obtain the normalized MCS size, with the supervision information being only the similarity score during training. To capture more global information, we also stack some vanilla transformer encoder layers with graph convolution layers and propose a novel permutation-invariant node Positional Encoding. The entire model is quite simple yet effective. Comprehensive experiments demonstrate that INFMCS consistently outperforms state-of-the-art baselines for graph-graph classification and regression tasks. Ablation experiments verify the effectiveness of the proposed computation paradigm and other components. Also, visualization and statistics of results reveal the interpretability of INFMCS.
