# Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure

arXiv: https://arxiv.org/abs/2510.00402 · HTML: https://mlsanity.com/paper/2510.00402/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 42 references that are in the map.
- First posted on arXiv 1 Oct 2025.

## Builds on (most cited first, 12 of 12)

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Generalized Intersection over Union: A Metric and A Loss for Bounding Box Regression](https://mlsanity.com/paper/1902.09630/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching](https://mlsanity.com/paper/2306.06380/) (2023)
- [Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs](https://mlsanity.com/paper/1802.06060/) (2018)

## Built on by (most cited first, 1 of 1)

- [Revisiting the Generalization of Neural Graph Edit Distance Models](https://mlsanity.com/paper/2610.04644/) (2026)

## Abstract (arXiv)

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 node-rooted subtrees, ensuring matched graph pairs maintain consistent hierarchies while complying with containment constraints in feature counts. To enhance the ranking ability for matched pairs, we introduce a novel similarity dominance ratio-enhanced measure, which quantifies the dominance of similarity over dissimilarity between graph pairs. Empirical results on nine datasets validate the effectiveness, generalization ability, scalability, and transferability of NC-Iso while maintaining time efficiency, offering a more discriminative neural subgraph matching solution for subgraph retrieval. Code available at https://github.com/liuzhouyang/NC-Iso.