Multi-level Graph Matching Networks for Deep and Robust Graph Similarity Learning

While the celebrated graph neural networks yield effective representations for individual nodes of a graph, there has been relatively less success in extending to graph similarity learning. Recent works have considered either global-level graph-graph interactions or low-level node-node interactions, ignoring the rich cross-level interactions (e.g., between nodes of a graph and the other whole graph). In this paper, we propose a Multi-level Graph Matching Network (MGMN) for computing the graph similarity between any pair of graph-structured objects in an end-to-end fashion. The proposed MGMN model consists of a node-graph matching network for effectively learning cross-level interactions between nodes of a graph and the other whole graph, and a siamese graph neural network to learn global-level interactions between two graphs. Furthermore, to bridge the gap of the lack of standard graph similarity learning benchmark, we have created and collected a set of datasets for both graph-graph classification and regression tasks with different sizes in order to evaluate the robustness of models. Our comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baselines on these graph similarity learning benchmarks.