Hierarchy-aware Neural Subgraph Matching With Enhanced Similarity Measure

Abstract

Subgraph matching is challenging as it necessitates time-consuming combinatorial searches. Recent Graph Neural Network (GNN)-based approaches address this issue by employing GNN encoders to extract graph information and hinge distance measures to ensure containment constraints in the embedding space. These methods significantly shorten the response time, making them promising solutions for subgraph retrieval. However, they suffer from scale differences between graph pairs during encoding, as they focus on feature counts but overlook the relative positions of features within node-rooted subtrees, leading to disturbed containment constraints and false predictions. Additionally, their hinge distance measures lack discriminative power for matched graph pairs, hindering ranking applications. We propose NC-Iso, a novel GNN architecture for neural subgraph matching. NC-Iso preserves the relative positions of features by building the hierarchical dependencies between adjacent echelons within n

Stats

• citations0
• S2 citations—
• github stars3
• HF likes0
• heat score1.20
• arxiv keyliu2025hierarchy

Related papers

• Iteratively Refined Early Interaction Alignment For Subgraph Matching Based Graph Retrieval (2025)3.21
• Hierarchical Graph Matching Network For Graph Similarity Computation (2020)0.00
• Sub-gmn: The Neural Subgraph Matching Network Model (2021)6.34
• SEGMN: A Structure-enhanced Graph Matching Network For Graph Similarity Learning (2024)2.26
• S\(^3\)GND: An Effective Learning-based Approach For Subgraph Similarity Search Under Generalized Neighbor Difference Semantics (technical Report) (2026)0.00
• Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
• Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration (2025)0.00
• Learning-based Efficient Graph Similarity Computation Via Multi-scale Convolutional Set Matching (2018)13.60