# BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 48 references that are in the map.
- First posted on arXiv 15 Apr 2025.

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

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (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)
- [Subgraph Neural Networks](https://mlsanity.com/paper/2006.10538/) (2020)
- [A Theoretical Comparison of Graph Neural Network Extensions](https://mlsanity.com/paper/2201.12884/) (2022)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Motif-aware Riemannian Graph Neural Network with Generative-Contrastive Learning](https://mlsanity.com/paper/2401.01232/) (2024)
- [Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks](https://mlsanity.com/paper/2107.10957/) (2021)
- [An Efficient Subgraph GNN with Provable Substructure Counting Power](https://mlsanity.com/paper/2303.10576/) (2023)
- [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)
- [Flow Motifs in Interaction Networks](https://mlsanity.com/paper/1810.08408/) (2018)
- [Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE](https://mlsanity.com/paper/1911.10616/) (2019)

## Abstract (arXiv)

Subgraph counting the task of determining the number of instances of a query pattern within a large graph lies at the heart of many critical applications, from analyzing financial networks and transportation systems to understanding biological interactions. Despite decades of work yielding efficient algorithmic (AL) solutions and, more recently, machine learning (ML) approaches, a clear comparative understanding is elusive. This gap stems from the absence of a unified evaluation framework, standardized datasets, and accessible ground truths, all of which hinder systematic analysis and fair benchmarking. To overcome these barriers, we introduce BEACON: a comprehensive benchmark designed to rigorously evaluate both AL and ML-based subgraph counting methods. BEACON provides a standardized dataset with verified ground truths, an integrated evaluation environment, and a public leaderboard, enabling reproducible and transparent comparisons across diverse approaches. Our extensive experiments reveal that while AL methods excel in efficiently counting subgraphs on very large graphs, they struggle with complex patterns (e.g., those exceeding six nodes). In contrast, ML methods are capable of handling larger patterns but demand massive graph data inputs and often yield suboptimal accuracy on small, dense graphs. These insights not only highlight the unique strengths and limitations of each approach but also pave the way for future advancements in subgraph counting techniques. Overall, BEACON represents a significant step towards unifying and accelerating research in subgraph counting, encouraging innovative solutions and fostering a deeper understanding of the trade-offs between algorithmic and machine learning paradigms.