摘要

图相似搜索是最重要的基于图的应用之一，例如，找到与查询化合物最相似的化学物质。图相似计算（如图编辑距离（Graph Edit Distance, GED）和最大公共子图（Maximum Common Subgraph, MCS））是图相似搜索及其他许多应用的核心操作，但在实际中计算成本非常高。受近年来神经网络方法在多个图应用（如节点分类或图分类）中取得成功的启发，我们提出了一种新的基于神经网络的方法来解决这一经典而具有挑战性的图问题，旨在减轻计算负担的同时保持良好的性能。所提出的这种方法称为SimGNN，结合了两种策略。首先，我们设计了一个可学习的嵌入函数，将每个图映射到一个向量，从而提供该图的全局概要。为此，我们提出了一种新颖的注意力机制，以强调特定相似度度量下重要的节点。其次，我们设计了一种成对节点比较方法，以补充图级别的嵌入信息，并提供细粒度的节点级信息。我们的模型在未见过的图上实现了更好的泛化能力，并且在最坏情况下运行时间与两个图中的节点数呈二次关系。以GED计算为例，在三个真实图数据集上的实验结果证明了我们方法的有效性和高效性。具体而言，我们的模型相比一系列基线方法（包括几种GED计算的近似算法以及许多现有的基于图神经网络的模型）实现了更低的错误率和显著的时间减少。据我们所知，我们是最早采用神经网络显式建模两个图形之间相似性的研究者之一，并为未来的图形相似性计算和图形相似性搜索研究提供了新的方向。