Graph similarity search is among the most important graph-based applications,
e.g. finding the chemical compounds that are most similar to a query compound.
Graph similarity computation, such as Graph Edit Distance (GED) and Maximum
Common Subgraph (MCS), is the core operation of graph similarity search and
many other applications, but very costly to compute in practice. Inspired by
the recent success of neural network approaches to several graph applications,
such as node or graph classification, we propose a novel neural network based
approach to address this classic yet challenging graph problem, aiming to
alleviate the computational burden while preserving a good performance.
The proposed approach, called SimGNN, combines two strategies. First, we
design a learnable embedding function that maps every graph into a vector,
which provides a global summary of a graph. A novel attention mechanism is
proposed to emphasize the important nodes with respect to a specific similarity
metric. Second, we design a pairwise node comparison method to supplement the
graph-level embeddings with fine-grained node-level information. Our model
achieves better generalization on unseen graphs, and in the worst case runs in
quadratic time with respect to the number of nodes in two graphs. Taking GED
computation as an example, experimental results on three real graph datasets
demonstrate the effectiveness and efficiency of our approach. Specifically, our
model achieves smaller error rate and great time reduction compared against a
series of baselines, including several approximation algorithms on GED
computation, and many existing graph neural network based models. To the best
of our knowledge, we are among the first to adopt neural networks to explicitly
model the similarity between two graphs, and provide a new direction for future
research on graph similarity computation and graph similarity search.

本文提出一种新颖的神经网络方法 SimGNN，该方法通过可学习的嵌入函数和注意力机制实现了对图形编辑距离等图形相似性计算的高效计算和良好性能的综合优化，并在三种真实图数据集上取得了比现有基线算法更小的误差率和更大的时间降低。