# Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

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

## Key facts

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

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

- [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)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network](https://mlsanity.com/paper/1905.11605/) (2019)
- [A Survey of Graph Neural Networks for Social Recommender Systems](https://mlsanity.com/paper/2212.04481/) (2022)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs](https://mlsanity.com/paper/2006.04330/) (2020)
- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding (Technical Report)](https://mlsanity.com/paper/2309.15641/) (2023)
- [On the expressive power of message-passing neural networks as global feature map transformers](https://mlsanity.com/paper/2203.09555/) (2022)
- [Sub-GMN: The Neural Subgraph Matching Network Model](https://mlsanity.com/paper/2104.00186/) (2021)
- [Representation Learning for Frequent Subgraph Mining](https://mlsanity.com/paper/2402.14367/) (2024)
- [Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification](https://mlsanity.com/paper/2203.11683/) (2022)
- [Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction](https://mlsanity.com/paper/2304.12610/) (2023)
- [D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching](https://mlsanity.com/paper/2306.06380/) (2023)
- [GuP: Fast Subgraph Matching by Guard-based Pruning](https://mlsanity.com/paper/2306.06557/) (2023)

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

- [Federated Layer-Wise Exchange for Cross-Client Money Laundering Pattern Detection](https://mlsanity.com/paper/2605.06433/) (2026)

## Abstract (arXiv)

Homomorphism is a key mapping technique between graphs that preserves their structure. Given a graph and a pattern, the subgraph homomorphism problem involves finding a mapping from the pattern to the graph, ensuring that adjacent vertices in the pattern are mapped to adjacent vertices in the graph. Unlike subgraph isomorphism, which requires a one-to-one mapping, homomorphism allows multiple vertices in the pattern to map to the same vertex in the graph, making it more complex. We propose HFrame, the first graph neural network-based framework for subgraph homomorphism, which integrates traditional algorithms with machine learning techniques. We demonstrate that HFrame outperforms standard graph neural networks by being able to distinguish more graph pairs where the pattern is not homomorphic to the graph. Additionally, we provide a generalization error bound for HFrame. Through experiments on both real-world and synthetic graphs, we show that HFrame is up to 101.91 times faster than exact matching algorithms and achieves an average accuracy of 0.962.