論文の概要: Efficient Approximate Temporal Triangle Counting in Streaming with Predictions

• arxiv url: http://arxiv.org/abs/2506.13173v1
• Date: Mon, 16 Jun 2025 07:34:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:47.691079
• Title: Efficient Approximate Temporal Triangle Counting in Streaming with Predictions
• Title（参考訳）: 予測付きストリーミングにおける効率的な近似時間的三角法
• Authors: Giorgio Venturin, Ilie Sarpe, Fabio Vandin,
• Abstract要約: 時間的辺のストリームから時間的三角形数を近似するスケーラブルで効率的なアルゴリズムSTEPを導入する。 STEPは、時間的エッジが関与する三角形の数と、単純なサンプリング戦略を組み合わせる。 解析学的に、サブ線形メモリを使用することで、STEPは偏りのない非常に正確な推定値が得られることを証明した。
• 参考スコア（独自算出の注目度）: 3.9623532668625576
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Triangle counting is a fundamental and widely studied problem on static graphs, and recently on temporal graphs, where edges carry information on the timings of the associated events. Streaming processing and resource efficiency are crucial requirements for counting triangles in modern massive temporal graphs, with millions of nodes and up to billions of temporal edges. However, current exact and approximate algorithms are unable to handle large-scale temporal graphs. To fill such a gap, we introduce STEP, a scalable and efficient algorithm to approximate temporal triangle counts from a stream of temporal edges. STEP combines predictions to the number of triangles a temporal edge is involved in, with a simple sampling strategy, leading to scalability, efficiency, and accurate approximation of all eight temporal triangle types simultaneously. We analytically prove that, by using a sublinear amount of memory, STEP obtains unbiased and very accurate estimates. In fact, even noisy predictions can significantly reduce the variance of STEP's estimates. Our extensive experiments on massive temporal graphs with up to billions of edges demonstrate that STEP outputs high-quality estimates and is more efficient than state-of-the-art methods.
• Abstract（参考訳）: 三角計数は静的グラフの基本的かつ広く研究されている問題であり、最近ではエッジが関連する事象のタイミングに関する情報を運ぶ時間グラフが問題となっている。 ストリーミング処理とリソース効率は、数百万のノードと最大数十億の時間エッジを持つ現代の巨大な時間グラフで三角形をカウントするための重要な要件である。 しかし、現在の正確で近似的なアルゴリズムは、大規模な時間グラフを扱えない。 このようなギャップを埋めるために、時間的辺のストリームから時間的三角形数を近似するスケーラブルで効率的なアルゴリズムSTEPを導入する。 STEPは、時間的エッジが関与する三角形の数と、単純なサンプリング戦略を組み合わせることで、スケーラビリティ、効率、そして8つの時間的三角形の型を同時に正確に近似する。 解析学的に、サブ線形メモリを使用することで、STEPは偏りのない非常に正確な推定値が得られることを証明した。 実際、ノイズの多い予測でさえ、STEPの推定値のばらつきを著しく低減することができる。 最大数十億のエッジを持つ大規模時間グラフに関する広範な実験は、STEPが高品質な見積もりを出力し、最先端の手法よりも効率的であることを示している。

関連論文リスト

• Fast and Accurate Triangle Counting in Graph Streams Using Predictions [4.000869978312742]
  本稿では, グラフストリーム中の三角形の数を予測した最初の効率的かつ実用的なアルゴリズムを提案する。 提案アルゴリズムは,待機室サンプリングと貯水池サンプリングと,エッジの重み,すなわちエッジが関与する三角形の数の予測器を組み合わせる。
  論文  参考訳（メタデータ） (2024-09-23T16:52:11Z)
• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。 本稿では,時間的経路サンプリングの新しい手法を用いて,この問題に対処するアルゴリズムTEACUPSを提案する。 数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
  論文  参考訳（メタデータ） (2024-09-13T16:48:39Z)
• Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making [66.27188304203217]
  時間的距離は、計画、制御、強化学習のための多くのアルゴリズムの中心にある。 このような時間的距離を設定内で定義しようとする以前の試みは、重要な制限によって妨げられている。 比較学習によって学習された後継特徴が,三角形の不等式を満たす時間的距離を形成することを示す。
  論文  参考訳（メタデータ） (2024-06-24T19:36:45Z)
• TriDet: Temporal Action Detection with Relative Boundary Modeling [85.49834276225484]
  既存の手法はビデオのあいまいな動作境界による不正確な境界予測に悩まされることが多い。 本稿では,その境界付近の相対確率分布を推定して,行動境界をモデル化する新しいトライデントヘッドを提案する。 TriDetは3つの挑戦的なベンチマークで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2023-03-13T17:59:59Z)
• Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
  大規模時間グラフにおける時間的モチーフを正確にカウントするための拡張性のある並列フレームワークを提案する。 提案手法に基づいて,ノード間並列戦略とノード内並列戦略の両方を特徴とする階層型並列フレームワークを設計する。 16の実世界の時間グラフデータセットに対する実験により,提案フレームワークの優位性と性能が示された。
  論文  参考訳（メタデータ） (2022-04-20T05:41:38Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。 従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。 提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
  論文  参考訳（メタデータ） (2022-03-17T19:26:00Z)
• Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data [0.0]
  ストリーミングフレームワークは、時系列に現れる時間変化のミニバッチを使用して最適化問題を解決するのに類似している。 我々は、様々な勾配に基づくアルゴリズムの漸近収束率を提供する。 時間変化したミニバッチに応じて学習率を選択して収束を加速する方法を示す。
  論文  参考訳（メタデータ） (2021-09-15T06:58:23Z)
• Spatio-Temporal Graph Scattering Transform [54.52797775999124]
  グラフニューラルネットワークは、十分な高品質のトレーニングデータがないために、現実のシナリオでは実用的ではないかもしれない。 我々は時間的データを解析するための数学的に設計された新しいフレームワークを考案した。
  論文  参考訳（メタデータ） (2020-12-06T19:49:55Z)
• Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version) [24.33313864327473]
  時間的モチーフのインスタンス数を推定する汎用エッジサンプリング(ES)アルゴリズムを提案する。 また、エッジサンプリングとウェッジサンプリングを併用した改良されたEWSアルゴリズムを考案し、3頂点と3エッジの時間的モチーフをカウントする。 我々のアルゴリズムは、時間的モチーフカウントのための最先端サンプリング手法よりも効率が高く、精度が高く、スケーラビリティが高い。
  論文  参考訳（メタデータ） (2020-07-28T07:15:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。