GMN-Zoomer: Learning graph similarity via hierarchical parsing, pooling and matching.

Abstract

Graph similarity learning aims to measure the similarity between graph pairs within a learning paradigm. It can effectively address the NP-hard challenges posed by traditional metrics, such as graph edit distance and maximum common subgraph. However, existing learning-based methods often fail to explore the hierarchical nature of graph structures, which is critical for capturing similarities across diverse structural granularities. In this paper, we propose a graph similarity learning framework based on hierarchical parsing, pooling, and matching. Firstly, we generate hierarchical graphs for each input graph through structural parsing followed by hierarchical pooling. Then, graphs at the same granularity level are matched to derive cross-graph interaction information. Finally, the matching results across all granularity levels are attentively fused into an overall graph similarity score. Extensive experiments on three benchmark datasets demonstrate that our proposed method achieves an overall average reduction of 28.65% in the mean squared error compared to state-of-the-art models. Our method also shows robust performance across various hierarchical parsing strategies in ablation studies.