[Experiment, Analysis, and Benchmark] BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs

Subgraph counting, the task of determining the number of instances of a query pattern within a large graph, plays an important role in many real-world applications, from analyzing financial networks and transportation systems to understanding biological interactions. Although this problem has been widely explored, ranging from efficient algorithmic (AL) solutions to more recently developed machine learning (ML) approaches, systematic comparative insights, particularly direct comparisons between AL and ML methods, remain 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 benchmark for efficient and accurate counting of subgraphs to 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 show that while AL methods perform more efficiently in 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 complex 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.