BEACON为子图计数提供统一评测基准,助力算法与模型对比。
BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs
- 构建标准化数据集与验证真值,支持公平对比
- 发现算法方法在大图上高效但难处理复杂模式
- 机器学习方法可处理大模式但需海量数据且小图精度低
子图计数是确定查询模式在大型图中出现次数的任务,广泛应用于金融网络、交通系统及生物互作分析。尽管已有大量高效算法(AL)和近年兴起的机器学习(ML)方法,但缺乏统一评估框架、标准数据集和可信真值,导致难以系统比较。为此,我们提出BEACON:一个全面的基准,包含经验证的真值数据集、集成评估环境和公开排行榜,支持可复现的透明比较。大量实验表明,算法方法在超大图上效率高,但对超过六节点的复杂模式表现不佳;而机器学习方法能处理更大模式,但需海量图数据输入,且在小而密集图上准确率常不理想。这些发现揭示了两类方法的优劣,推动未来子图计数技术发展。总体而言,BEACON为该领域研究的统一与加速提供了关键支撑。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。