Interpretable Graph Similarity Computation via Differentiable Optimal Alignment of Node Embeddings
Interpretable Graph Similarity Computation via Differentiable Optimal Alignment of Node Embeddings
复制标题
DOI：
10.1145/3404835.3462960
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Khoa D. Doan;Saurav Manchanda;Suchismit Mahapatra;Chandan K. Reddy
中科院分区：
文献类型：
--
作者：
Khoa D. Doan;Saurav Manchanda;Suchismit Mahapatra;Chandan K. Reddy
计算图的相似度是图数据库检索、图聚类等与图相关的应用中的一项重要任务。虽然已经提出了许多措施来捕捉一对图之间的相似性，图编辑距离（GED）和最大公共子图（MCS）是两个广泛使用的措施在实践中。GED和MCS是图之间结构相似性的域不可知度量，并将相似性定义为两个图中不同实体（如节点、边和子图）的成对对齐的函数。由成对比对提供的明确的可解释性提供了相似性得分的透明度和合理性，因此，GED和MCS具有重要的实际应用。然而，它们的精确计算是NP难的。虽然最近提出的基于神经网络的近似已经被证明可以准确地计算这些相似性得分，但与经典的组合算法相比，它们在提供全面解释方面的能力有限，例如，光束搜索。本文旨在通过神经网络有效地近似这些领域不可知的相似性度量，并同时学习对齐（即，解释）类似于经典的棘手的方法。具体来说，我们制定一对图之间的相似性作为最小的“变换”成本从一个图到另一个在可学习的节点嵌入空间。我们表明，如果节点嵌入能够密切捕捉其邻域上下文，我们提出的相似性函数非常接近经典方法的对齐和相似性得分。此外，我们还提出了一个有效的微分计算我们提出的目标模型训练。从经验上讲，我们证明了所提出的方法实现了高达50%-100%的减少均方误差的图形相似性近似任务和高达20%的改进的检索评价指标的图形检索任务。源代码可在https://github.com/khoadoan/GraphOTSim上获得。
Computing graph similarity is an important task in many graph-related applications such as retrieval in graph databases or graph clustering. While numerous measures have been proposed to capture the similarity between a pair of graphs, Graph Edit Distance (GED) and Maximum Common Subgraphs (MCS) are the two widely used measures in practice. GED and MCS are domain-agnostic measures of structural similarity between the graphs and define the similarity as a function of pairwise alignment of different entities (such as nodes, edges, and subgraphs) in the two graphs. The explicit explainability offered by the pairwise alignment provides transparency and justification of the similarity score, thus, GED and MCS have important practical applications. However, their exact computations are known to be NP-hard. While recently proposed neural-network based approximations have been shown to accurately compute these similarity scores, they have limited ability in providing comprehensive explanations compared to classical combinatorial algorithms, e.g., Beam search. This paper aims at efficiently approximating these domain-agnostic similarity measures through a neural network, and simultaneously learning the alignments (i.e., explanations) similar to those of classical intractable methods. Specifically, we formulate the similarity between a pair of graphs as the minimal "transformation" cost from one graph to another in the learnable node-embedding space. We show that, if node embedding is able to capture its neighborhood context closely, our proposed similarity function closely approximates both the alignment and the similarity score of classical methods. Furthermore, we also propose an efficient differentiable computation of our proposed objective for model training. Empirically, we demonstrate that the proposed method achieves up to 50%-100% reduction in the Mean Squared Error for the graph similarity approximation task and up to 20% improvement in the retrieval evaluation metrics for the graph retrieval task. The source code is available at https://github.com/khoadoan/GraphOTSim.