# Representation Learning for Frequent Subgraph Mining

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 56 references that are in the map.
- First posted on arXiv 22 Feb 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (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)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network](https://mlsanity.com/paper/1905.11605/) (2019)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Large-scale analysis of disease pathways in the human interactome](https://mlsanity.com/paper/1712.00843/) (2017)
- [A General Framework for Estimating Graphlet Statistics via Random Walk](https://mlsanity.com/paper/1603.07504/) (2016)
- [Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts](https://mlsanity.com/paper/1411.4942/) (2014)
- [ESCAPE: Efficiently Counting All 5-Vertex Subgraphs](https://mlsanity.com/paper/1610.09411/) (2016)
- [Motivo: fast motif counting via succinct color coding and adaptive sampling](https://mlsanity.com/paper/1906.01599/) (2019)
- [Faster motif counting via succinct color coding and adaptive sampling](https://mlsanity.com/paper/2009.03052/) (2020)
- [GraphPi: High Performance Graph Pattern Matching through Effective Redundancy Elimination](https://mlsanity.com/paper/2009.10955/) (2020)

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

- [Building Optimal Neural Architectures using Interpretable Knowledge](https://mlsanity.com/paper/2403.13293/) (2024)
- [Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism](https://mlsanity.com/paper/2505.21988/) (2025)
- [Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks](https://mlsanity.com/paper/2507.20226/) (2025)
- [Frequent subgraph-based persistent homology for graph classification](https://mlsanity.com/paper/2512.24917/) (2025)
- [GraDE: A Graph Diffusion Estimator for Frequent Subgraph Discovery in Neural Architectures](https://mlsanity.com/paper/2602.03257/) (2026)

## Abstract (arXiv)

Identifying frequent subgraphs, also called network motifs, is crucial in analyzing and predicting properties of real-world networks. However, finding large commonly-occurring motifs remains a challenging problem not only due to its NP-hard subroutine of subgraph counting, but also the exponential growth of the number of possible subgraphs patterns. Here we present Subgraph Pattern Miner (SPMiner), a novel neural approach for approximately finding frequent subgraphs in a large target graph. SPMiner combines graph neural networks, order embedding space, and an efficient search strategy to identify network subgraph patterns that appear most frequently in the target graph. SPMiner first decomposes the target graph into many overlapping subgraphs and then encodes each subgraph into an order embedding space. SPMiner then uses a monotonic walk in the order embedding space to identify frequent motifs. Compared to existing approaches and possible neural alternatives, SPMiner is more accurate, faster, and more scalable. For 5- and 6-node motifs, we show that SPMiner can almost perfectly identify the most frequent motifs while being 100x faster than exact enumeration methods. In addition, SPMiner can also reliably identify frequent 10-node motifs, which is well beyond the size limit of exact enumeration approaches. And last, we show that SPMiner can find large up to 20 node motifs with 10-100x higher frequency than those found by current approximate methods.