論文の概要: BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs
- arxiv url: http://arxiv.org/abs/2504.10948v1
- Date: Tue, 15 Apr 2025 07:53:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-16 22:06:21.384451
- Title: BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs
- Title（参考訳）: BEACON: グラフの効率的かつ正確なカウントのためのベンチマーク
- Authors: Mohammad Matin Najafi, Xianju Zhu, Chrysanthi Kosyfaki, Laks V. S. Lakshmanan, Reynold Cheng,
- Abstract要約: 本稿では,アルゴリズム(AL)と機械学習(ML)の両方のサブグラフカウント手法を厳格に評価するベンチマークであるBEACONを紹介する。
BEACONは、検証済みの真実、統合評価環境、公開リーダボードを備えた標準化されたデータセットを提供する。
実験の結果,AL法は,非常に大きなグラフ上の部分グラフを効率的に数えるのに優れるが,複雑なパターンに悩まされることがわかった。
- 参考スコア（独自算出の注目度）: 18.281284442275457
- License:
- 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.
- Abstract（参考訳）: 大規模グラフ内のクエリパターンのインスタンス数を決定するタスクを数えるのは、金融ネットワークや交通システムの分析から生物学的相互作用の理解に至るまで、多くの重要なアプリケーションの中心にある。
何十年にもわたって、効率的なアルゴリズム(AL)ソリューションと、最近では機械学習(ML)アプローチを生み出してきたが、明確な比較理解はあり得ない。
このギャップは、統一された評価フレームワーク、標準化されたデータセット、アクセス可能な地上の真実が欠如していることに起因している。
これらの障壁を克服するために、ALおよびMLベースのサブグラフカウント手法を厳格に評価するために設計された包括的なベンチマークであるBEACONを紹介する。
BEACONは、検証済みの土台真実、統合評価環境、および公開リーダボードを備えた標準化されたデータセットを提供し、様々なアプローチで再現可能かつ透過的な比較を可能にする。
我々の広範な実験により、AL法は、非常に大きなグラフ上の部分グラフを効率的に数えるのに優れていますが、複雑なパターン(例えば、6つのノードを超えるもの)に苦労しています。
対照的に、ML法はより大きなパターンを扱うことができるが、大量のグラフデータ入力を必要とするため、小さくて密度の高いグラフでは、しばしば準最適精度が得られる。
これらの洞察は、それぞれのアプローチの独特な強みと限界を浮き彫りにするだけでなく、グラフカウント技術における将来の進歩の道を開く。
BEACONは全体として、サブグラフカウントの研究の統合と加速、革新的なソリューションの奨励、アルゴリズムと機械学習のパラダイム間のトレードオフのより深い理解を促進するための重要なステップである。
関連論文リスト
- Instance-Aware Graph Prompt Learning [71.26108600288308]
本稿では,インスタンス対応グラフプロンプト学習(IA-GPL)について紹介する。
このプロセスでは、軽量アーキテクチャを使用して各インスタンスの中間プロンプトを生成する。
複数のデータセットと設定で実施された実験は、最先端のベースラインと比較して、IA-GPLの優れたパフォーマンスを示している。
論文 参考訳（メタデータ） (2024-11-26T18:38:38Z) - MTLSO: A Multi-Task Learning Approach for Logic Synthesis Optimization [19.13500546022262]
MTLSOは論理合成最適化のためのマルチタスク学習手法である。
一次回帰タスクと並行して,二元多ラベルグラフ分類の補助タスクを導入する。
また、階層的なグラフ表現学習戦略を用いて、表現力のあるグラフレベルの表現を学習するためのモデルの能力を向上させる。
論文 参考訳（メタデータ） (2024-09-09T21:20:36Z) - DIVE: Subgraph Disagreement for Graph Out-of-Distribution Generalization [44.291382840373]
本稿では,グラフ機械学習におけるアウト・オブ・ディストリビューションの一般化の課題に対処する。
従来のグラフ学習アルゴリズムは、この仮定が失敗する現実世界のシナリオで失敗する。
この準最適性能に寄与する主な要因は、ニューラルネットワークの本質的な単純さバイアスである。
論文 参考訳（メタデータ） (2024-08-08T12:08:55Z) - Harnessing the Power of Large Language Model for Uncertainty Aware Graph Processing [24.685942503019948]
本稿では,大言語モデル(LLM)のパワーを生かした新しい手法を提案する。
筆者らは,2つのグラフ処理タスク,すなわち知識グラフ補完とグラフ分類について実験を行った。
LLM が生成した回答の正確性を予測するため,10 つのデータセットのうち 7 つに対して 0.8 以上の AUC を達成した。
論文 参考訳（メタデータ） (2024-03-31T07:38:39Z) - Persistent Laplacian-enhanced Algorithm for Scarcely Labeled Data
Classification [2.8360662552057323]
永続ラプラシア拡張グラフMBO (PL-MBO) と呼ばれる半教師付き手法を提案する。
PL-MBOは、永続スペクトルグラフ理論と古典的なメリマン・バーンス=オッシャースキームを統合する。
データ分類における提案手法の性能評価を行った。
論文 参考訳（メタデータ） (2023-05-25T16:49:40Z) - Rethinking Clustering-Based Pseudo-Labeling for Unsupervised
Meta-Learning [146.11600461034746]
教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。
このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。
このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
論文 参考訳（メタデータ） (2022-09-27T19:04:36Z) - Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
グラフの外れ値検出は、多くのアプリケーションにおいて、新しいが重要な機械学習タスクである。
UNODと呼ばれるグラフに対して、最初の包括的教師なしノード外乱検出ベンチマークを示す。
論文 参考訳（メタデータ） (2022-06-21T01:46:38Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。
提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。
いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2021-12-15T01:45:32Z) - Self-supervised on Graphs: Contrastive, Generative,or Predictive [25.679620842010422]
SSL(Self-supervised Learning)は、よく設計されたプリテキストタスクを通じて有益な知識を抽出するための新しいパラダイムとして登場しています。
既存のグラフSSLメソッドは、コントラスト、生成、予測の3つのカテゴリに分けられる。
また、一般的なデータセット、評価メトリクス、下流タスク、さまざまなアルゴリズムのオープンソース実装をまとめています。
論文 参考訳（メタデータ） (2021-05-16T03:30:03Z) - Model-Agnostic Graph Regularization for Few-Shot Learning [60.64531995451357]
グラフ組み込み数ショット学習に関する包括的な研究を紹介します。
本稿では,ラベル間のグラフ情報の組み込みによる影響をより深く理解できるグラフ正規化手法を提案する。
提案手法は,Mini-ImageNetで最大2%,ImageNet-FSで6.7%の性能向上を実現する。
論文 参考訳（メタデータ） (2021-02-14T05:28:13Z) - Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
半教師付き学習における簡単なメタ学習アルゴリズムを提案する。
その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
論文 参考訳（メタデータ） (2020-07-08T08:48:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。