Multilevel Graph Matching Networks for Deep Graph Similarity Learning

While the celebrated graph neural networks (GNNs) yield effective representations for individual nodes of a graph, there has been relatively less success in extending to the task of graph similarity learning. Recent work on graph similarity learning has considered either global-level graph–graph interactions or low-level node–node interactions, however, ignoring the rich cross-level interactions (e.g., between each node of one graph and the other whole graph). In this article, we propose a multilevel graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects in an end-to-end fashion. In particular, the proposed MGMN consists of a node–graph matching network (NGMN) for effectively learning cross-level interactions between each node of one graph and the other whole graph, and a siamese GNN to learn global-level interactions between two input graphs. Furthermore, to compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph–graph classification and graph–graph regression tasks with different sizes in order to evaluate the effectiveness and robustness of our models. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph–graph classification and graph–graph regression tasks. Compared with previous work, multilevel graph matching network (MGMN) also exhibits stronger robustness as the sizes of the two input graphs increase.