論文の概要: TIMEST: Temporal Information Motif Estimator Using Sampling Trees

• arxiv url: http://arxiv.org/abs/2507.20441v1
• Date: Sun, 27 Jul 2025 23:31:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-29 16:23:57.680511
• Title: TIMEST: Temporal Information Motif Estimator Using Sampling Trees
• Title（参考訳）: TIMEST:サンプリング木を用いた時間情報モチーフ推定器
• Authors: Yunjie Pan, Omkar Bhalerao, C. Seshadhri, Nishil Talati,
• Abstract要約: 本稿では,時間的ネットワークにおける任意の大きさの時間的モチーフをカウントする汎用的,高速,高精度な推定アルゴリズムTIMESTを提案する。 TIMESTは,従来のアルゴリズムよりも高速かつ高精度であることを示す。 例えば、TIMESTは4分間の時間的モチーフのインスタンス数を0.6%エラーでカウントでき、正確なメソッドは2日以上かかる。
• 参考スコア（独自算出の注目度）: 5.114632024458956
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The mining of pattern subgraphs, known as motifs, is a core task in the field of graph mining. Edges in real-world networks often have timestamps, so there is a need for temporal motif mining. A temporal motif is a richer structure that imposes timing constraints on the edges of the motif. Temporal motifs have been used to analyze social networks, financial transactions, and biological networks. Motif counting in temporal graphs is particularly challenging. A graph with millions of edges can have trillions of temporal motifs, since the same edge can occur with multiple timestamps. There is a combinatorial explosion of possibilities, and state-of-the-art algorithms cannot manage motifs with more than four vertices. In this work, we present TIMEST: a general, fast, and accurate estimation algorithm to count temporal motifs of arbitrary sizes in temporal networks. Our approach introduces a temporal spanning tree sampler that leverages weighted sampling to generate substructures of target temporal motifs. This method carefully takes a subset of temporal constraints of the motif that can be jointly and efficiently sampled. TIMEST uses randomized estimation techniques to obtain accurate estimates of motif counts. We give theoretical guarantees on the running time and approximation guarantees of TIMEST. We perform an extensive experimental evaluation and show that TIMEST is both faster and more accurate than previous algorithms. Our CPU implementation exhibits an average speedup of 28x over state-of-the-art GPU implementation of the exact algorithm, and 6x speedup over SOTA approximate algorithms while consistently showcasing less than 5% error in most cases. For example, TIMEST can count the number of instances of a financial fraud temporal motif in four minutes with 0.6% error, while exact methods take more than two days.
• Abstract（参考訳）: モチーフとして知られるパターン部分グラフのマイニングは、グラフマイニングの分野における中核的なタスクである。 現実世界のネットワークのエッジにはしばしばタイムスタンプがあるため、時間的モチーフマイニングが必要である。 時間モチーフはよりリッチな構造であり、モチーフの端にタイミング制約を課す。 テンポラルモチーフは、ソーシャルネットワーク、金融取引、生物学的ネットワークの分析に使われてきた。 時間グラフのモチーフカウントは特に難しい。 数百万のエッジを持つグラフは、同じエッジが複数のタイムスタンプで発生するため、数兆の時間モチーフを持つことができる。 組み合わさった可能性の爆発があり、最先端のアルゴリズムは4つ以上の頂点を持つモチーフを管理できない。 本研究では,時間的ネットワークにおける任意のサイズの時間的モチーフをカウントする汎用的,高速,高精度な推定アルゴリズムTIMESTを提案する。 提案手法では, 加重サンプリングを応用し, 対象の時間的モチーフのサブ構造を生成する時間的スパンニングツリーサンプリング手法を提案する。 この方法は、共同で効率的にサンプリングできるモチーフの時間的制約のサブセットを慎重に取る。 TIMESTは乱数推定手法を用いてモチーフカウントの正確な推定値を求める。 TIMESTのランニング時間と近似保証について理論的に保証する。 本研究では,TIMESTが従来のアルゴリズムよりも高速かつ高精度であることを示す。 我々のCPU実装では、精度の高いアルゴリズムの最先端GPU実装よりも平均28倍、SOTA近似アルゴリズムより6倍のスピードアップを示し、ほとんどのケースでは5%未満のエラーを示している。 例えば、TIMESTは、金融詐欺の時間的モチーフのインスタンス数を4分で0.6%のエラーでカウントでき、正確な方法は2日以上かかる。

関連論文リスト

• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$は、投機的デコードにインスパイアされた遅延対応のテスト時間スケーリングメソッドである。 我々の結果は、$textttSPECS$matchはビームサーチの精度を上回り、最大$sim$19.1%のレイテンシを削減していることを示している。
  論文  参考訳（メタデータ） (2025-06-15T05:50:05Z)
• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。 本稿では,時間的経路サンプリングの新しい手法を用いて,この問題に対処するアルゴリズムTEACUPSを提案する。 数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
  論文  参考訳（メタデータ） (2024-09-13T16:48:39Z)
• Representation Learning for Frequent Subgraph Mining [64.32430554934021]
  Subgraph Pattern Miner (SPMiner) は、大きなターゲットグラフに頻繁なサブグラフを見つけるための新しいニューラルネットワークである。 5ノードと6ノードのモチーフでは、SPMinerは正確な列挙法よりも100倍速く、最も頻繁なモチーフをほぼ完全に識別できる。 SPMinerは、10ノードの頻繁なモチーフを確実に特定できる。
  論文  参考訳（メタデータ） (2024-02-22T08:11:22Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Uncovering the Missing Pattern: Unified Framework Towards Trajectory Imputation and Prediction [60.60223171143206]
  軌道予測は、観測されたシーケンスから実体運動や人間の行動を理解する上で重要な作業である。 現在の方法では、観測されたシーケンスが完了したと仮定し、欠落した値の可能性を無視する。 本稿では,グラフに基づく条件変動リカレントニューラルネットワーク (GC-VRNN) の統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-03-28T14:27:27Z)
• TimesNet: Temporal 2D-Variation Modeling for General Time Series Analysis [80.56913334060404]
  時系列解析は、天気予報、異常検出、行動認識などの応用において非常に重要である。 従来の手法では、1D時系列から直接これを達成しようと試みていた。 複雑な経時的変化を、複数の経時的変化と経時的変化に明らかにする。
  論文  参考訳（メタデータ） (2022-10-05T12:19:51Z)
• Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs [51.51417735550026]
  時間的ネットワーク上での機械学習の方法は、一般的に2つの制限のうちの少なくとも1つを示す。 ネットワークのライングラフは,各インタラクションのノードを含むもので,インタラクション間の時間差に基づいて,このグラフのエッジを重み付けする。 実世界のネットワークにおける実験結果から,エッジ分類と時間リンク予測の両方において,本手法の有効性と有効性を示す。
  論文  参考訳（メタデータ） (2022-09-30T18:24:13Z)
• Motiflets -- Simple and Accurate Detection of Motifs in Time Series [3.6463708995502273]
  時系列のモチーフは直感的に、より大きな時系列の中でほぼ同じことを繰り返す短い時系列である。 モチーフ発見(MD)は、与えられた入力系列においてそのようなモチーフを見つけるタスクである。 そこで我々は,k-Motifletの正確な近似アルゴリズムを提案し,その複雑性を解析する。
  論文  参考訳（メタデータ） (2022-06-08T08:22:28Z)
• 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)
• Multi-Temporal Convolutions for Human Action Recognition in Videos [83.43682368129072]
  複数の解像度で抽出できる新しい時間・時間的畳み込みブロックを提案する。 提案するブロックは軽量で,任意の3D-CNNアーキテクチャに統合可能である。
  論文  参考訳（メタデータ） (2020-11-08T10:40:26Z)
• Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version) [24.33313864327473]
  時間的モチーフのインスタンス数を推定する汎用エッジサンプリング(ES)アルゴリズムを提案する。 また、エッジサンプリングとウェッジサンプリングを併用した改良されたEWSアルゴリズムを考案し、3頂点と3エッジの時間的モチーフをカウントする。 我々のアルゴリズムは、時間的モチーフカウントのための最先端サンプリング手法よりも効率が高く、精度が高く、スケーラビリティが高い。
  論文  参考訳（メタデータ） (2020-07-28T07:15:25Z)

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

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