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

Mohammad Matin Najafi † , Xianju Zhu † , Chrysanthi Kosyfaki † , Laks V.S. Lakshmanan § , Reynold Cheng † · 2025

Read BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs [Experiment, Analysis & Benchmark Paper] by Mohammad Matin Najafi † , Xianju Zhu † , Chrysanthi Kosyfaki † , Laks V.S. Lakshmanan § , Reynold Cheng † (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10948.txt.

Introduction

Mohammad Najafi and co-authors release BEACON, a benchmark for counting small patterns inside huge graphs. Their twenty twenty-five paper serves a task behind fraud rings, traffic flows, and molecular studies: how many times does a query shape appear in the network? Algorithmic and learning methods both claim speed.

No shared test had let the two camps fight fairly. BEACON ships standard datasets with verified true counts, a test harness, and a public leaderboard. Ground truth is the hard part at this scale, and it is provided. Future counters can now be ranked in the open instead of each paper grading its own homework.

Catalog record

CREATORMohammad Matin Najafi † , Xianju Zhu † , Chrysanthi Kosyfaki † , Laks V.S. Lakshmanan § , Reynold Cheng †
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10948

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs [Experiment, Analysis & Benchmark Paper] Mohammad Matin Najafi † , Xianju Zhu † , Chrysanthi Kosyfaki † , Laks V.S. Lakshmanan § , Reynold Cheng † 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. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/zxj0302/MLSC . 1. Introduction Subgraph counting is a fundamental problem within graph analytics, where the objective is to enumerate and count all subgraphs in a large graph G=(V,E) that are isomorphic to a given query graph q=(V_{q},E_{q}) ( Foulds 1995 ) . Formally, the goal is to compute C_{G}(q) , or the number of occurrences of q within G . Figure 1 . An example input graph G , a query pattern q , and the 4 corresponding instances of q in G , yielding \mathcal{N}_{q}(G)=4 . Subgraph counting plays a vital role in many domains ( Kane et al. 2012 ; Vassilevska Williams and Williams 2013 ; Ahmed et al. 2016 ; Comandur and Tirthapura 2019 ; Bordino et al. 2008 ; Slota and Madduri 2013 ; Ribeiro et al. 2022 ; Focke and Roth 2024 ; Bonifati et al. 2024 ; Fang et al. 2022 ; Ribeiro et al. 2010 ; Floderus et al. 2015 ; Wackersreuther et al. 2010 ; Kuramochi and Karypis 2001 ; Papapetrou et al. 2011 ) . In network science, for example, identifying frequently-occurring patterns—such as cliques (fully connected subgraphs) or small recurring motifs—can help in deciphering community structures and interaction patterns within social networks ( Chen and Lui 2018 ) . In biological networks, counting subgraphs such as motifs is instrumental in revealing functional modules or biologically significant interactions ( Wang et al. 2021 ; Mrzic et al. 2018 ; Najafi et al. 2023 ) . Furthermore, in financial and transaction networks, the detection and counting of specific subgraph patterns can expose anomalous transaction behaviors, which may signal fraudulent activities like money laundering ( Kosyfaki et al. 2019 ) . These applications underscore the important role of subgraph counting for extracting deep insights about complex and interconnected systems. Figure 1 illustrates a pattern q , and its instances for graph G . Challenges. Due the NP-completeness of the underlying subgraph isomorphism, subgraph counting is computationally challenging ( Ullmann 1976 ; Cook 2023 ) . This problem exacerbates when G is huge, or when q is complex. To tackle these issues, two classes of solutions were studied in the literature: Algorithmic (AL) and Machine Learning (ML)-based, as discussed below. 1. Algorithmic (AL) methods include exact and approximate techniques. State-of-the-art exact methods leverage advanced combinatorial strategies and specialized hand-crafted formulas tailored to specific subgraph patterns (e.g., ESCAPE ( Pinar et al. 2017 ) and EVOKE ( Pashanasangi and Seshadhri 2020 ) ), which can compute counts efficiently when such formulas exist. However, deriving these formulas is inherently challenging. Also, they usually do not support larger or more complex subgraphs, and cannot scale to handle dense graphs due to the exponential nature of the NP-complete subgraph isomorphism ( Ullmann 1976 ; Cook 2023 ) . Approximate AL methods (e.g., ( mot 2019 ) ) aims to trade accuracy for efficiency. Their performance can degrades significantly as both G and q become larger or denser. 2. Machine Learning (ML)-based approaches have emerged as a promising alternative ( Papp and Wattenhofer 2022 ; Qian et al. 2022 ; Sandfelder et al. 2021 ; Schwabe and Acosta 2024 ; Sun et al. 2024 ; Zhang et al. 2023b ; Zhang et al. 2023a ; Zhao et al. 2021 ) to traditional algorithmic methods for subgraph counting. These methods use graph patterns to train a model (e.g., GNN ( Zhao et al. 2022 ) ). The trained model can then produce subgraph counts quickly, even for large and complex graphs / subgraphs that cannot be supported by AL methods. However, there is a lack of a unified framework and curated datasets for ML-based subgraph counting, making standardized evaluation against AL strategies difficult. The performance of these models is also sensitive to variations in software environments, hardware configurations, and training procedures, raising reproducibility concerns. Moreover, we observe that in existing works in ML approaches, only few AL methods, which may not be SOTA, were used for comparisons. Without a comprehensive and systematic comparison, it is not clear when and how ML approaches fare better than AL methods. This makes it difficult to realize the strengths and weaknesses of existing subgraph counting algorithms, or design better ones. The BEACON benchmark. To address the limitations and open questions of current subgraph counting approaches, we propose BEACON , or B enchmark for E fficient and A ccuracy CO u N ting. This is the first unified framework that enables comparisons among AL and ML-based methods across various types of graphs and query patterns. It also enhances reproducibility through standardized datasets, detailed protocols, and containerized environments. It can also be useful to the research community by elucidating the trade-offs among scalability, accuracy, and runtime that are made by the various methods. BEACON facilitates a deeper understanding of existing methodologies and supports the development of next-generation methods that effectively harness both algorithmic and machine learning techniques. Specifically, our contributions are: (1) Insightful Experimental Findings: \bullet Comprehensive Evaluation Across Diverse Scenarios: our benchmark evaluates a wide range of subgraph counting

Read the complete text