論文の概要: Online Change Point Detection for Weighted and Directed Random Dot
Product Graphs
- arxiv url: http://arxiv.org/abs/2201.11222v1
- Date: Wed, 26 Jan 2022 22:48:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-29 02:52:20.119599
- Title: Online Change Point Detection for Weighted and Directed Random Dot
Product Graphs
- Title(参考訳): 重み付きおよび有向ランダムドット製品グラフのオンライン変化点検出
- Authors: Bernardo Marenco, Paola Bermolen, Marcelo Fiori, Federico Larroca,
Gonzalo Mateos
- Abstract要約: 汎用的ランダムドット製品グラフ(RDPG)モデルに基づくグラフ表現学習基板を用いた変化点検出(CPD)手法を提案する。
モニタリング機能のオンライン更新は、ストリーミンググラフ観測と名目G観測の相違を定量化する。
我々は、重み付きおよび直接グラフのための新しいオンラインCDDのオープンソース実装を提供する。
- 参考スコア(独自算出の注目度): 9.652642545116532
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a sequence of random (directed and weighted) graphs, we address the
problem of online monitoring and detection of changes in the underlying data
distribution. Our idea is to endow sequential change-point detection (CPD)
techniques with a graph representation learning substrate based on the
versatile Random Dot Product Graph (RDPG) model. We consider efficient, online
updates of a judicious monitoring function, which quantifies the discrepancy
between the streaming graph observations and the nominal RDPG. This reference
distribution is inferred via spectral embeddings of the first few graphs in the
sequence. We characterize the distribution of this running statistic to select
thresholds that guarantee error-rate control, and under simplifying
approximations we offer insights on the algorithm's detection resolution and
delay. The end result is a lightweight online CPD algorithm, that is also
explainable by virtue of the well-appreciated interpretability of RDPG
embeddings. This is in stark contrast with most existing graph CPD approaches,
which either rely on extensive computation, or they store and process the
entire observed time series. An apparent limitation of the RDPG model is its
suitability for undirected and unweighted graphs only, a gap we aim to close
here to broaden the scope of the CPD framework. Unlike previous proposals, our
non-parametric RDPG model for weighted graphs does not require a priori
specification of the weights' distribution to perform inference and estimation.
This network modeling contribution is of independent interest beyond CPD. We
offer an open-source implementation of the novel online CPD algorithm for
weighted and direct graphs, whose effectiveness and efficiency are demonstrated
via (reproducible) synthetic and real network data experiments.
- Abstract(参考訳): ランダムな(方向と重み付き)グラフのシーケンスが与えられた場合、オンライン監視と基盤となるデータ分布の変化の検出の問題に対処します。
我々の考えは,汎用的ランダムドット製品グラフ(RDPG)モデルに基づくグラフ表現学習基板を用いた逐次変化点検出(CPD)技術の実現である。
本稿では,ストリーミンググラフ観測とRDPGの差分を定量化する,効果的なオンライン監視機能の更新について考察する。
この参照分布は、最初の数個のグラフのスペクトル埋め込みによって推定される。
我々は、この動作統計の分布を、誤差レート制御を保証するしきい値の選択に特徴付け、近似を単純化することにより、アルゴリズムの検出精度と遅延に関する洞察を提供する。
結局のところ、RDPG埋め込みの精度の良い解釈性によって説明できる軽量オンラインCDDアルゴリズムである。
これは、広範な計算に依存する既存のグラフCPDアプローチや、観測された時系列全体を保存して処理するグラフCPDアプローチとは対照的である。
RDPGモデルの明らかな制限は、非方向性グラフと非重みグラフのみに適合する点である。
従来の提案と異なり、重み付けグラフに対する非パラメトリックRDPGモデルは、推定と推定を行うために重み付け分布の事前仕様を必要としない。
このネットワークモデリングの貢献は、PDを超えた独立した関心事である。
我々は、重み付き直接グラフのための新しいオンラインCPDアルゴリズムをオープンソースで実装し、(再現可能な)合成および実ネットワークデータ実験によって効率と効率を実証する。
関連論文リスト
- Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳(メタデータ) (2024-01-12T17:57:07Z) - Probabilistically Rewired Message-Passing Neural Networks [43.638280289905026]
メッセージパッシンググラフニューラルネットワーク(MPNN)は、グラフ構造化入力を処理する強力なツールとして登場した。
MPNNは、潜在的なノイズや欠落した情報を無視して、固定された入力グラフ構造で動作する。
確率的に再構成されたMPNN(PR-MPNN)を考案し、より有益なものを省略しながら、関連するエッジを追加することを学習する。
論文 参考訳(メタデータ) (2023-10-03T15:43:59Z) - Gradient-Based Spectral Embeddings of Random Dot Product Graphs [7.612218105739107]
本稿では,RDPG (Random Dot Product Graph) の組込み問題の解法について述べる。
そこで我々は, 結果の多様体に対して, 実現可能な新しい最適化手法を開発した。
当社のオープンソースアルゴリズムの実装はスケーラブルで、エッジデータに欠ける堅牢さと異なり、ストリーミンググラフからゆっくりと、潜伏した位置を追跡することができます。
論文 参考訳(メタデータ) (2023-07-25T21:09:55Z) - A fast topological approach for predicting anomalies in time-varying
graphs [0.0]
トポロジカルデータ解析(TDA)からの永続化ダイアグラム(PD)は、点間距離が明確に定義されたデータ形状記述法として人気がある。
本稿では,グラフデータから形状情報を抽出する計算効率の良いフレームワークを提案する。
実際のデータアプリケーションでは、暗号取引ネットワークの異常な価格予測において、我々のアプローチは最大で22%上昇する。
論文 参考訳(メタデータ) (2023-05-11T01:54:45Z) - Score-based Generative Modeling of Graphs via the System of Stochastic
Differential Equations [57.15855198512551]
本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。
本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
論文 参考訳(メタデータ) (2022-02-05T08:21:04Z) - Handling Distribution Shifts on Graphs: An Invariance Perspective [77.14319095965058]
グラフ上のノードレベルの予測にOOD問題を定式化する。
そこで我々は,探索から抽出までのリスク最小化という新たなドメイン不変学習手法を開発した。
理論的に有効なOOD解の保証を示すことによって,本手法の有効性を実証する。
論文 参考訳(メタデータ) (2022-02-05T02:31:01Z) - A Graph Data Augmentation Strategy with Entropy Preserving [11.886325179121226]
本稿では,グラフ間の特徴情報を評価するための定量的指標として,新しいグラフエントロピー定義を提案する。
グラフエントロピーの保存を考慮し、摂動機構を用いてトレーニングデータを生成する効果的な方法を提案する。
提案手法はトレーニング過程におけるGCNの堅牢性と一般化能力を大幅に向上させる。
論文 参考訳(メタデータ) (2021-07-13T12:58:32Z) - Reinforcement Learning-based Black-Box Evasion Attacks to Link
Prediction in Dynamic Graphs [87.5882042724041]
動的グラフ(LPDG)におけるリンク予測は、多様な応用を持つ重要な研究課題である。
我々は,LPDG法の脆弱性を調査し,最初の実用的なブラックボックス回避攻撃を提案する。
論文 参考訳(メタデータ) (2020-09-01T01:04:49Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳(メタデータ) (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。