論文の概要: Accurate and Fast Estimation of Temporal Motifs using Path Sampling
- arxiv url: http://arxiv.org/abs/2409.08975v2
- Date: Sun, 06 Oct 2024 18:27:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-10 14:01:43.847259
- Title: Accurate and Fast Estimation of Temporal Motifs using Path Sampling
- Title（参考訳）: 経路サンプリングによる時間的モチーフの高精度・高速推定
- Authors: Yunjie Pan, Omkar Bhalerao, C. Seshadhri, Nishil Talati,
- Abstract要約: モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。
本稿では,時間的経路サンプリングの新しい手法を用いて,この問題に対処するアルゴリズムTEACUPSを提案する。
数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
- 参考スコア（独自算出の注目度）: 5.114632024458956
- License:
- Abstract: Counting the number of small subgraphs, called motifs, is a fundamental problem in social network analysis and graph mining. Many real-world networks are directed and temporal, where edges have timestamps. Motif counting in directed, temporal graphs is especially challenging because there are a plethora of different kinds of patterns. Temporal motif counts reveal much richer information and there is a need for scalable algorithms for motif counting. A major challenge in counting is that there can be trillions of temporal motif matches even with a graph with only millions of vertices. Both the motifs and the input graphs can have multiple edges between two vertices, leading to a combinatorial explosion problem. Counting temporal motifs involving just four vertices is not feasible with current state-of-the-art algorithms. We design an algorithm, TEACUPS, that addresses this problem using a novel technique of temporal path sampling. We combine a path sampling method with carefully designed temporal data structures, to propose an efficient approximate algorithm for temporal motif counting. TEACUPS is an unbiased estimator with provable concentration behavior, which can be used to bound the estimation error. For a Bitcoin graph with hundreds of millions of edges, TEACUPS runs in less than 1 minute, while the exact counting algorithm takes more than a day. We empirically demonstrate the accuracy of TEACUPS on large datasets, showing an average of 30$\times$ speedup (up to 2000$\times$ speedup) compared to existing GPU-based exact counting methods while preserving high count estimation accuracy.
- Abstract（参考訳）: モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。
多くの現実世界のネットワークは、エッジがタイムスタンプを持つ、指示的かつ時間的です。
向き付けされた時間グラフを数えるのは、様々な種類のパターンが存在するため、特に難しい。
時間的モチーフカウントは、よりリッチな情報を明らかにし、モチーフカウントのためのスケーラブルなアルゴリズムが必要である。
数えることの大きな課題は、何百万もの頂点を持つグラフであっても、時間的モチーフマッチングが数兆個存在することである。
モチーフと入力グラフは2つの頂点の間に複数のエッジを持つことができ、組合せ爆発問題を引き起こす。
4つの頂点を含む時間的モチーフをカウントすることは、現在の最先端のアルゴリズムでは不可能である。
我々は、時間的経路サンプリングの新しい手法を用いて、この問題に対処するアルゴリズム、TEACUPSを設計する。
本研究では,経路サンプリング手法と時間的データ構造を慎重に設計し,時間的モチーフカウントのための効率的な近似アルゴリズムを提案する。
TEACUPSは、証明可能な濃度挙動を持つ非バイアス推定器であり、推定誤差のバウンドに使用できる。
数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
我々は、大規模なデータセット上でのTEACUPSの精度を実証的に実証し、既存のGPUベースの正確なカウント方法と比較して平均30$\times$スピードアップ(最大2000$\times$スピードアップ)を示し、高いカウント推定精度を維持した。
関連論文リスト
- Representation Learning for Frequent Subgraph Mining [64.32430554934021]
Subgraph Pattern Miner (SPMiner) は、大きなターゲットグラフに頻繁なサブグラフを見つけるための新しいニューラルネットワークである。
5ノードと6ノードのモチーフでは、SPMinerは正確な列挙法よりも100倍速く、最も頻繁なモチーフをほぼ完全に識別できる。
SPMinerは、10ノードの頻繁なモチーフを確実に特定できる。
論文 参考訳（メタデータ） (2024-02-22T08:11:22Z) - Scalable Pattern Matching in Computation Graphs [0.0]
グラフの書き直しは、グラフ表現の最適化と修正に人気のあるツールである。
ポートグラフにおけるパターンマッチングの新しい解法を提案する。
我々のアルゴリズムは、10万の現実世界のパターンのデータセット上での現在の実装の20倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2024-02-20T15:02:24Z) - Learning Graph Search Heuristics [48.83557172525969]
本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。
我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。
実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
論文 参考訳（メタデータ） (2022-12-07T22:28:00Z) - Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
大規模時間グラフにおける時間的モチーフを正確にカウントするための拡張性のある並列フレームワークを提案する。
提案手法に基づいて,ノード間並列戦略とノード内並列戦略の両方を特徴とする階層型並列フレームワークを設計する。
16の実世界の時間グラフデータセットに対する実験により,提案フレームワークの優位性と性能が示された。
論文 参考訳（メタデータ） (2022-04-20T05:41:38Z) - odeN: Simultaneous Approximation of Multiple Motif Counts in Large
Temporal Networks [7.025709586759655]
時間的モチーフを研究する際の主な合併症の1つは、構築できる多くのモチーフである。
そこで我々は,すべてのモチーフを正確に近似したサンプリングベースアルゴリズムodeNを提案する。
論文 参考訳（メタデータ） (2021-08-19T15:06:05Z) - Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか?
本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
論文 参考訳（メタデータ） (2021-06-08T16:10:36Z) - Local Algorithms for Estimating Effective Resistance [26.54556748340991]
本研究では,大規模グラフ上での有効抵抗を推定するための複数のエンファンローカアルゴリズムを設計する。
主アルゴリズムは任意の頂点対 $s,t$ と任意に小さな加算誤差の間の有効抵抗を近似する。
いくつかのベンチマークデータセットについて広範な実験を行い、アルゴリズムを検証した。
論文 参考訳（メタデータ） (2021-06-07T10:08:12Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳（メタデータ） (2021-03-30T08:58:45Z) - Scalable Graph Neural Networks via Bidirectional Propagation [89.70835710988395]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータを学習するための新興分野である。
本稿では、特徴ベクトルとトレーニング/テストノードの両方から局所的な双方向伝搬プロセスを利用するスケーラブルなGNNであるGBPを提案する。
実証実験により、GBPは、トレーニング/テスト時間を大幅に減らして最先端のパフォーマンスを達成することが示された。
論文 参考訳（メタデータ） (2020-10-29T08:55:33Z) - Efficient Sampling Algorithms for Approximate Temporal Motif Counting
(Extended Version) [24.33313864327473]
時間的モチーフのインスタンス数を推定する汎用エッジサンプリング(ES)アルゴリズムを提案する。
また、エッジサンプリングとウェッジサンプリングを併用した改良されたEWSアルゴリズムを考案し、3頂点と3エッジの時間的モチーフをカウントする。
我々のアルゴリズムは、時間的モチーフカウントのための最先端サンプリング手法よりも効率が高く、精度が高く、スケーラビリティが高い。
論文 参考訳（メタデータ） (2020-07-28T07:15:25Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。