# D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 10 Jun 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Graph Optimal Transport for Cross-Domain Alignment](https://mlsanity.com/paper/2006.14744/) (2020)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)

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

- [Neural Graduated Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2505.12325/) (2025)
- [Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks](https://mlsanity.com/paper/2507.20226/) (2025)
- [Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure](https://mlsanity.com/paper/2510.00402/) (2025)

## Abstract (arXiv)

Subgraph matching is a fundamental building block for graph-based applications and is challenging due to its high-order combinatorial nature. Existing studies usually tackle it by combinatorial optimization or learning-based methods. However, they suffer from exponential computational costs or searching the matching without theoretical guarantees. In this paper, we develop D2Match by leveraging the efficiency of Deep learning and Degeneracy for subgraph matching. More specifically, we first prove that subgraph matching can degenerate to subtree matching, and subsequently is equivalent to finding a perfect matching on a bipartite graph. We can then yield an implementation of linear time complexity by the built-in tree-structured aggregation mechanism on graph neural networks. Moreover, circle structures and node attributes can be easily incorporated in D2Match to boost the matching performance. Finally, we conduct extensive experiments to show the superior performance of our D2Match and confirm that our D2Match indeed exploits the subtrees and differs from existing GNNs-based subgraph matching methods that depend on memorizing the data distribution divergence