Learning-Based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching

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 graphgraph similarity as the inner product of their graph-level representations, with different techniques proposed for generating one embedding per graph. However, using one fixeddimensional 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, GRAPH-SIM, achieves the state-of-the-art performance on four realworld 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. Recent years we have witnessed the growing importance of graph-based applications in the domains of chemistry, bioinformatics, recommender systems, social network study, static program analysis, etc. One of the fundamental problems related to graphs is the computation of distance/similarity between two graphs. It not only is a core operation in graph similarity search and graph database analysis (Zeng et al. 2009; Wang et al. 2012) , but also plays a significant role in a wide range of applications. For example, in computer security, similarity between binary functions is useful for plagiarism * The two first authors made equal contributions. † This work is done before Hao Ding joined AWS AI Labs.