Graph similarity computation is one of the core operations in many
graph-based applications, such as graph similarity search, graph database
analysis, graph clustering, etc. Since computing the exact distance/similarity
between two graphs is typically NP-hard, a series of approximate methods have
been proposed with a trade-off between accuracy and speed. Recently, several
data-driven approaches based on neural networks have been proposed, most of
which model the graph-graph similarity as the inner product of their
graph-level representations, with different techniques proposed for generating
one embedding per graph. However, using one fixed-dimensional embedding per
graph may fail to fully capture graphs in varying sizes and link structures, a
limitation that is especially problematic for the task of graph similarity
computation, where the goal is to find the fine-grained difference between two
graphs. In this paper, we address the problem of graph similarity computation
from another perspective, by directly matching two sets of node embeddings
without the need to use fixed-dimensional vectors to represent whole graphs for
their similarity computation. The model, GraphSim, achieves the
state-of-the-art performance on four real-world graph datasets under six out of
eight settings (here we count a specific dataset and metric combination as one
setting), compared to existing popular methods for approximate Graph Edit
Distance (GED) and Maximum Common Subgraph (MCS) computation.

本文介绍了 GraphSim 模型，该模型从直接匹配两组节点嵌入的角度解决了图相似性计算问题，获得了在四个真实世界图数据集上的最先进性能。