Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation

Graph similarity computation, which predicts a similarity score between one pair of graphs, has been widely used in various fields, such as recommendation system Wu, Xiao and Chen (2015); Hu, Xu, Wang, Li and Liu (2020), computer vision Horaud and Skordas (1989); Pelillo, Siddiqi and Zucker (1999) and so on. However, most of the common distance measures evaluating how similar two graphs are, like Graph Edit Distance (GED) Bunke (1983) and Maximum Common Subgraph (MCS) Bunke and Shearer (1998), still suffer from large search spaces or excessive memory requirements. They are weak to compute exact graph distance for graphs with more than 16 nodes Blumenthal and Gamper (2018). Traditional graph similarity computation methods such as A* Riesen, Emmenegger and Bunke (2013), Hungarian Kuhn (1955); Riesen and Bunke (2009), VJ Fankhauser, Riesen and Bunke (2011); Jonker and Volgenant (1987), and BeamNeuhaus, Riesen and Bunke (2006), try to use pruning strategy or find approximate values instead of exact similarity to alleviate the problem. Nevertheless, by performing directly from the edges and nodes characteristics of the graphs, these exact and approximate algorithms still have a high time-complexity for computing the GED or MCS between two graphs, and are hard to be generalized to large graphs in real applications. With the rapid development of deep learning technology, graph embedding that automatically extracts the structural characteristics of the graph, provides a new solution for similarity computation and matching of graph structures. Recently, researchers proposed some representative graph deep learning models based on graph embedding for graph similarity computation.