論文の概要: PRESTO: Simple and Scalable Sampling Techniques for the Rigorous
Approximation of Temporal Motif Counts
- arxiv url: http://arxiv.org/abs/2101.07152v1
- Date: Mon, 18 Jan 2021 16:35:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-27 05:46:32.245300
- Title: PRESTO: Simple and Scalable Sampling Techniques for the Rigorous
Approximation of Temporal Motif Counts
- Title（参考訳）: PRESTO: 時間モチーフ数の厳密な近似のためのシンプルでスケーラブルなサンプリング手法
- Authors: Ilie Sarpe, Fabio Vandin
- Abstract要約: 時間的モチーフのカウントの厳密な近似を得るために,効率的かつスケーラブルなアルゴリズムを提案する。
私たちのアルゴリズムは、シンプルで効果的なサンプリングアプローチに基づいており、非常に大規模なデータセットに実用的です。
- 参考スコア（独自算出の注目度）: 7.025709586759655
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The identification and counting of small graph patterns, called network
motifs, is a fundamental primitive in the analysis of networks, with
application in various domains, from social networks to neuroscience. Several
techniques have been designed to count the occurrences of motifs in static
networks, with recent work focusing on the computational challenges provided by
large networks. Modern networked datasets contain rich information, such as the
time at which the events modeled by the networks edges happened, which can
provide useful insights into the process modeled by the network. The analysis
of motifs in temporal networks, called temporal motifs, is becoming an
important component in the analysis of modern networked datasets. Several
methods have been recently designed to count the number of instances of
temporal motifs in temporal networks, which is even more challenging than its
counterpart for static networks. Such methods are either exact, and not
applicable to large networks, or approximate, but provide only weak guarantees
on the estimates they produce and do not scale to very large networks. In this
work we present an efficient and scalable algorithm to obtain rigorous
approximations of the count of temporal motifs. Our algorithm is based on a
simple but effective sampling approach, which renders our algorithm practical
for very large datasets. Our extensive experimental evaluation shows that our
algorithm provides estimates of temporal motif counts which are more accurate
than the state-of-the-art sampling algorithms, with significantly lower running
time than exact approaches, enabling the study of temporal motifs, of size
larger than the ones considered in previous works, on billion edges networks.
- Abstract（参考訳）: ネットワークモチーフと呼ばれる小さなグラフパターンの識別とカウントは、ソーシャルネットワークから神経科学まで、様々な分野のネットワーク分析における基本的な原始である。
静的ネットワークにおけるモチーフの発生を数えるためにいくつかの技術が設計され、近年では大規模ネットワークによる計算課題に焦点が当てられている。
現代のネットワークデータセットには、ネットワークエッジによってモデル化されたイベントが発生した時間など、豊富な情報が含まれている。
時間的モチーフと呼ばれる時間的ネットワークにおけるモチーフの分析は、現代のネットワーク化されたデータセットの分析において重要な要素となっている。
最近、時間的ネットワークにおける時間的モチーフのインスタンス数をカウントするために、いくつかの手法が設計されている。
このような手法は厳密であり、大規模ネットワークには適用できないが、生産する推定値に対する弱い保証しか提供せず、大規模ネットワークにはスケールしない。
本研究では,時間モチーフ数を厳密に近似するために,効率的でスケーラブルなアルゴリズムを提案する。
アルゴリズムは単純だが効果的なサンプリング手法に基づいており、非常に大きなデータセットに対してアルゴリズムを実用的なものにしている。
実験により,本アルゴリズムは,最先端サンプリングアルゴリズムよりも精度の高い時間的モチーフ数を推定し,正確なアプローチよりも実行時間が有意に低く,従来考えられていたより大きい時間的モチーフを数十億のエッジネットワーク上で研究することができることを示した。
関連論文リスト
- State-Space Modeling in Long Sequence Processing: A Survey on Recurrence in the Transformer Era [59.279784235147254]
このサーベイは、シーケンシャルなデータ処理の反復モデルに基づく最新のアプローチの詳細な概要を提供する。
新たなイメージは、標準のバックプロパゲーション・オブ・タイムから外れた学習アルゴリズムによって構成される、新しいルートを考える余地があることを示唆している。
論文 参考訳（メタデータ） (2024-06-13T12:51:22Z) - How neural networks learn to classify chaotic time series [77.34726150561087]
本研究では,通常の逆カオス時系列を分類するために訓練されたニューラルネットワークの内部動作について検討する。
入力周期性とアクティベーション周期の関係は,LKCNNモデルの性能向上の鍵となる。
論文 参考訳（メタデータ） (2023-06-04T08:53:27Z) - Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs [51.51417735550026]
時間的ネットワーク上での機械学習の方法は、一般的に2つの制限のうちの少なくとも1つを示す。
ネットワークのライングラフは,各インタラクションのノードを含むもので,インタラクション間の時間差に基づいて,このグラフのエッジを重み付けする。
実世界のネットワークにおける実験結果から,エッジ分類と時間リンク予測の両方において,本手法の有効性と有効性を示す。
論文 参考訳（メタデータ） (2022-09-30T18:24:13Z) - Graph-Survival: A Survival Analysis Framework for Machine Learning on
Temporal Networks [14.430635608400982]
連続時間時間ネットワークのための生成モデルを設計するためのフレームワークを提案する。
本稿では,本フレームワーク内のモデルに適合する手法と,所望の特性を持つ新しい時間ネットワークをシミュレートするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-14T16:40:57Z) - Temporal Graph Network Embedding with Causal Anonymous Walks
Representations [54.05212871508062]
本稿では,時間グラフネットワークに基づく動的ネットワーク表現学習のための新しいアプローチを提案する。
評価のために、時間的ネットワーク埋め込みの評価のためのベンチマークパイプラインを提供する。
欧州の大手銀行が提供した実世界のダウンストリームグラフ機械学習タスクにおいて、我々のモデルの適用性と優れた性能を示す。
論文 参考訳（メタデータ） (2021-08-19T15:39:52Z) - odeN: Simultaneous Approximation of Multiple Motif Counts in Large
Temporal Networks [7.025709586759655]
時間的モチーフを研究する際の主な合併症の1つは、構築できる多くのモチーフである。
そこで我々は,すべてのモチーフを正確に近似したサンプリングベースアルゴリズムodeNを提案する。
論文 参考訳（メタデータ） (2021-08-19T15:06:05Z) - Frequent Pattern Mining in Continuous-time Temporal Networks [0.0]
我々は,時間的ネットワークデータセットにおける頻繁な時間パターンの完全集合をマイニングするための一連のアルゴリズムを開発した。
3つの実世界のデータセットに対するアルゴリズムの実装は、提案アルゴリズムの実用性を証明する。
論文 参考訳（メタデータ） (2021-05-12T02:47:24Z) - Anomaly Detection on Attributed Networks via Contrastive Self-Supervised
Learning [50.24174211654775]
本論文では,アトリビュートネットワーク上の異常検出のためのコントラスト型自己監視学習フレームワークを提案する。
このフレームワークは、新しいタイプのコントラストインスタンスペアをサンプリングすることで、ネットワークデータからのローカル情報を完全に活用します。
高次元特性と局所構造から情報埋め込みを学習するグラフニューラルネットワークに基づくコントラスト学習モデルを提案する。
論文 参考訳（メタデータ） (2021-02-27T03:17:20Z) - TempNodeEmb:Temporal Node Embedding considering temporal edge influence
matrix [0.8941624592392746]
時間的ネットワークにおけるノード間の将来のリンクを予測することは、時間的ネットワークの進化の重要な側面を明らかにする。
いくつかのアプローチは、時間ネットワークの単純化された表現を、高次元で一般にスパース行列で考える。
本稿では, 単純な3層グラフニューラルネットワークを各ステップで考慮し, ネットワークの進化特性を利用した新しいノード埋め込み手法を提案する。
論文 参考訳（メタデータ） (2020-08-16T15:39:07Z) - Efficient Sampling Algorithms for Approximate Temporal Motif Counting
(Extended Version) [24.33313864327473]
時間的モチーフのインスタンス数を推定する汎用エッジサンプリング(ES)アルゴリズムを提案する。
また、エッジサンプリングとウェッジサンプリングを併用した改良されたEWSアルゴリズムを考案し、3頂点と3エッジの時間的モチーフをカウントする。
我々のアルゴリズムは、時間的モチーフカウントのための最先端サンプリング手法よりも効率が高く、精度が高く、スケーラビリティが高い。
論文 参考訳（メタデータ） (2020-07-28T07:15:25Z) - ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
簡単な反復マスク探索法により,非常に深いネットワークの最先端の圧縮を実現することができることを示す。
本アルゴリズムは,シングルショット・ネットワーク・プルーニング法とロッテ・ティケット方式のハイブリッド・アプローチを示す。
論文 参考訳（メタデータ） (2020-06-28T23:09:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。