BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs

Mohammad Matin Najafi, Xianju Zhu, Chrysanthi Kosyfaki, Laks V. S. Lakshmanan, Reynold ChengarXiv 2025 · DOI · arXiv

Bridging the Gap in Subgraph Counting

Subgraph counting—identifying the frequency of specific patterns like triangles or cliques within a larger network—is a fundamental task in data science. It enables critical applications ranging from identifying functional modules in biological protein networks to detecting fraudulent loops in financial transaction data.

Despite its importance, the task is computationally intensive (NP-complete). For decades, researchers relied on Algorithmic (AL) methods rooted in combinatorial mathematics. Recently, Machine Learning (ML) approaches, particularly Graph Neural Networks (GNNs), have emerged with the promise of faster counting for complex patterns. However, a significant disconnect exists: AL and ML research often utilize different datasets and metrics, making direct comparison impossible. BEACON (Benchmark for Efficient and Accuracy COuNting) is the first unified framework designed to standardize evaluation across these two paradigms.

The BEACON Framework

The authors developed a modular framework to ensure reproducibility and comprehensive testing across three core pillars:

  1. Data Module: Features the BEACON-Sampler, allowing researchers to generate custom datasets based on specific constraints like node count or average degree.
  2. Environment Module: Utilizes Docker containers to guarantee that experiments are reproducible regardless of local software configurations.
  3. Testing Module: Provides a standardized suite of metrics and a public leaderboard to track progress.
The modular architecture of the BEACON framework, integrating data sampling, containerized environments, and standardized testing.

The Oracle Dataset

Central to BEACON is the Oracle Dataset, a massive collection of 26,435 graphs aggregated from the TUDataset and the Open Graph Benchmark (OGB). Every graph is pre-labeled with ground truth counts for subgraphs up to five nodes. To test various aspects of model performance, the authors curated 10 specific subsets: Sets 1–6 focus on small graphs with varying densities to test accuracy, while Sets 7–10 feature larger graphs (up to 5,000 nodes) to evaluate scalability.

Analysis of subgraph count distributions across diverse domains (Bioinformatics, Social Networks, Computer Vision, and Molecules) within the Oracle Dataset.

Key Insights and Empirical Findings

BEACON’s standardized evaluation revealed several critical bottlenecks in current subgraph counting methods:

  • The "Preprocessing Tax": Many ML studies overlook preprocessing time. BEACON factors this in, showing that some "fast" ML models spend so much time preparing data that they are actually slower than traditional AL methods in practice.
  • The 1-WL Bottleneck: Standard GNNs are limited by the "1-Weisfeiler-Lehman" test, meaning they cannot distinguish certain complex graph structures. This explains why "vanilla" GNNs are fast but often inaccurate.
  • Learning vs. Memorizing: In Zero-Shot tests (predicting on unseen graphs), many ML models performed poorly, suggesting they often "memorize" training data distributions rather than learning underlying graph geometry.
  • Density Challenges: As graph density increases, both AL and ML methods struggle. AL methods face an exponential explosion in search space, while ML models fail to produce accurate counts in "clique-heavy" environments.

Results and Future Directions

The evaluation identified PPGN and DeSCo as accuracy leaders, though PPGN requires high training costs. Traditional AL methods like ESCAPE remain the gold standard for simple patterns on massive graphs but cannot handle the complex patterns that ML models can process. The authors found that Few-Shot Fine-Tuning offers the best balance, providing significant accuracy gains over Zero-Shot models without the prohibitive cost of full training.

Future work for BEACON includes expanding the benchmark to patterns larger than five nodes and improving the interpretability of ML models to understand why a GNN arrives at a specific count.

Summary updated

Abstract

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.
BibTeX
@misc{najafi2025beacon,
  author = {Mohammad Matin Najafi and Xianju Zhu and Chrysanthi Kosyfaki and Laks V. S. Lakshmanan and Reynold Cheng},
  title = {{BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs}},
  year = {2025},
  eprint = {2504.10948},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.10948},
}
Figure