BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs

• URL: http://arxiv.org/abs/2504.10948v1
• Date: Tue, 15 Apr 2025 07:53:47 GMT
• Title: BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs
• Authors: Mohammad Matin Najafi, Xianju Zhu, Chrysanthi Kosyfaki, Laks V. S. Lakshmanan, Reynold Cheng,
• Abstract summary: We introduce BEACON: a benchmark designed to rigorously evaluate both algorithmic (AL) and machine learning (ML) subgraph counting methods.<n> BEACON provides a standardized dataset with verified ground truths, an integrated evaluation environment, and a public leaderboard.<n>Our experiments reveal that while AL methods excel in efficiently counting subgraphs on very large graphs, they struggle with complex patterns.
• Score: 18.281284442275457
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• G-OSR: A Comprehensive Benchmark for Graph Open-Set Recognition [54.45837774534411]
  We introduce textbfG-OSR, a benchmark for evaluating Graph Open-Set Recognition (GOSR) methods at both the node and graph levels.<n>Results offer critical insights into the generalizability and limitations of current GOSR methods.
  arXiv  Detail & Related papers  (2025-03-01T13:02:47Z)
• Instance-Aware Graph Prompt Learning [71.26108600288308]
  We introduce Instance-Aware Graph Prompt Learning (IA-GPL) in this paper. The process involves generating intermediate prompts for each instance using a lightweight architecture. Experiments conducted on multiple datasets and settings showcase the superior performance of IA-GPL compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-11-26T18:38:38Z)
• DIVE: Subgraph Disagreement for Graph Out-of-Distribution Generalization [44.291382840373]
  This paper addresses the challenge of out-of-distribution generalization in graph machine learning. Traditional graph learning algorithms falter in real-world scenarios where this assumption fails. A principal factor contributing to this suboptimal performance is the inherent simplicity bias of neural networks.
  arXiv  Detail & Related papers  (2024-08-08T12:08:55Z)
• Harnessing the Power of Large Language Model for Uncertainty Aware Graph Processing [24.685942503019948]
  We introduce a novel approach that harnesses the power of a large language model (LLM) to provide a confidence score on the generated answer. We experiment with our approach on two graph processing tasks: few-shot knowledge graph completion and graph classification. Our confidence measure achieves an AUC of 0.8 or higher on seven out of the ten datasets in predicting the correctness of the answer generated by LLM.
  arXiv  Detail & Related papers  (2024-03-31T07:38:39Z)
• Persistent Laplacian-enhanced Algorithm for Scarcely Labeled Data Classification [2.8360662552057323]
  We propose a semi-supervised method called persistent Laplacian-enhanced graph MBO (PL-MBO) PL-MBO integrates persistent spectral graph theory with the classical Merriman-Bence- Osher scheme. We evaluate the performance of the proposed method on data classification.
  arXiv  Detail & Related papers  (2023-05-25T16:49:40Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  Graph outlier detection is an emerging but crucial machine learning task with numerous applications. We present the first comprehensive unsupervised node outlier detection benchmark for graphs called UNOD.
  arXiv  Detail & Related papers  (2022-06-21T01:46:38Z)
• From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale Contrastive Learning Approach [26.973056364587766]
  Anomaly detection from graph data is an important data mining task in many applications such as social networks, finance, and e-commerce. We propose a novel framework, graph ANomaly dEtection framework with Multi-scale cONtrastive lEarning (ANEMONE in short) By using a graph neural network as a backbone to encode the information from multiple graph scales (views), we learn better representation for nodes in a graph.
  arXiv  Detail & Related papers  (2022-02-11T09:45:11Z)
• Self-supervised on Graphs: Contrastive, Generative,or Predictive [25.679620842010422]
  Self-supervised learning (SSL) is emerging as a new paradigm for extracting informative knowledge through well-designed pretext tasks. We divide existing graph SSL methods into three categories: contrastive, generative, and predictive. We also summarize the commonly used datasets, evaluation metrics, downstream tasks, and open-source implementations of various algorithms.
  arXiv  Detail & Related papers  (2021-05-16T03:30:03Z)
• Model-Agnostic Graph Regularization for Few-Shot Learning [60.64531995451357]
  We present a comprehensive study on graph embedded few-shot learning. We introduce a graph regularization approach that allows a deeper understanding of the impact of incorporating graph information between labels. Our approach improves the performance of strong base learners by up to 2% on Mini-ImageNet and 6.7% on ImageNet-FS.
  arXiv  Detail & Related papers  (2021-02-14T05:28:13Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.