Multidimensional Graph Matching Network Using Topological Features

Graph similarity computation is an important problem for research in the field of complex networks, which can further facilitate tasks such as graph classification, clustering and similarity search. Graph similarity is usually measured by the graph edit distance (GED) metric; however, the exact computation of GED is an NP-hard problem with high computational complexity and difficult to solve. In recent years, graph similarity computation using graph neural networks (GNN) has emerged to achieve efficient metric results. To fully exploit the deep information in the graph and obtain more accurate graph similarity computation results, we propose a multidimensional graph matching network model using graph topological information. Firstly, to capture the rich fine-grained information in the graph, a multidimensional graph matching module is proposed in the model, including cross-graph feature interactions at the node-graph level as well as at the multi-level graph-graph level, and the expressiveness of the model is improved by the graph matching module. Secondly, graph topology feature matching is added in the similarity calculation to focus on how similar a pair of graphs are in terms of topology and to utilize topology information more fully. We conducted experiments on real-world datasets to demonstrate the effectiveness of the model.