Hierarchical Graph Matching Network For Graph Similarity Computation

Abstract

Graph edit distance / similarity is widely used in many tasks, such as graph similarity search, binary function analysis, and graph clustering. However, computing the exact graph edit distance (GED) or maximum common subgraph (MCS) between two graphs is known to be NP-hard. In this paper, we propose the hierarchical graph matching network (HGMN), which learns to compute graph similarity from data. HGMN is motivated by the observation that two similar graphs should also be similar when they are compressed into more compact graphs. HGMN utilizes multiple stages of hierarchical clustering to organize a graph into successively more compact graphs. At each stage, the earth mover distance (EMD) is adopted to obtain a one-to-one mapping between the nodes in two graphs (on which graph similarity is to be computed), and a correlation matrix is also derived from the embeddings of the nodes in the two graphs. The correlation matrices from all stages are used as input for a convolutional neural ne

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyxiu2020hierarchical

Related papers

• Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
• SEGMN: A Structure-enhanced Graph Matching Network For Graph Similarity Learning (2024)2.26
• Sub-gmn: The Neural Subgraph Matching Network Model (2021)6.34
• Hierarchy-aware Neural Subgraph Matching With Enhanced Similarity Measure (2025)1.20
• Learning-based Efficient Graph Similarity Computation Via Multi-scale Convolutional Set Matching (2018)13.60
• MATA*: Combining Learnable Node Matching With A* Algorithm For Approximate Graph Edit Distance Computation (2023)6.34
• Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration (2025)0.00
• Learning Graph Edit Distance By Graph Neural Networks (2020)10.85