# Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 42 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [A Theoretical Comparison of Graph Neural Network Extensions](https://mlsanity.com/paper/2201.12884/) (2022)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)
- [On the Combinatorial Power of the Weisfeiler-Lehman Algorithm](https://mlsanity.com/paper/1704.01023/) (2017)
- [Homomorphisms Are a Good Basis for Counting Small Subgraphs](https://mlsanity.com/paper/1705.01595/) (2017)
- [Graphs Identified by Logics with Counting](https://mlsanity.com/paper/1503.08792/) (2015)
- [The Weisfeiler-Leman Dimension of Planar Graphs is at most 3](https://mlsanity.com/paper/1708.07354/) (2017)
- [A Single-Exponential Time 2-Approximation Algorithm for Treewidth](https://mlsanity.com/paper/2104.07463/) (2021)
- [An Improved Parameterized Algorithm for Treewidth](https://mlsanity.com/paper/2211.07154/) (2022)
- [The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs](https://mlsanity.com/paper/1908.05268/) (2019)
- [The k-Dimensional Weisfeiler-Leman Algorithm](https://mlsanity.com/paper/1907.09582/) (2019)
- [Rank-width: Algorithmic and structural results](https://mlsanity.com/paper/1601.03800/) (2016)
- [A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus](https://mlsanity.com/paper/1904.07216/) (2019)
- [Finding and Counting Patterns in Sparse Graphs](https://mlsanity.com/paper/2301.02569/) (2023)

## Abstract (arXiv)

Subgraph counting is a fundamental task for analyzing structural patterns in graph-structured data, with important applications in domains such as computational biology and social network analysis, where recurring motifs reveal functional and organizational properties. In this paper, we propose localized versions of the Weisfeiler-Leman (WL) algorithms to improve both expressivity and computational efficiency for this task. We introduce Local k-WL, which we prove to be more expressive than k-WL and at most as expressive as (k+1)-WL, and provide a characterization of patterns whose subgraph and induced subgraph counts are invariant under Local k-WL equivalence. To enhance scalability, we present two variants -- Layer k-WL and Recursive k-WL -- that achieve greater time and space efficiency compared to applying k-WL on the entire graph. Additionally, we propose a novel fragmentation technique that decomposes complex subgraphs into simpler subpatterns, enabling the exact count of all induced subgraphs of size at most 4 using only 1-WL, with extensions possible for larger patterns when k>1. Building on these ideas, we develop a three-stage differentiable learning framework that combines subpattern counts to compute counts of more complex motifs, bridging combinatorial algorithm design with machine learning approaches. We also compare the expressive power of Local k-WL with existing GNN hierarchies and demonstrate that, under bounded time complexity, our methods are more expressive than prior approaches.