論文の概要: 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アルゴリズムをオープンソースで実装し、(再現可能な)合成および実ネットワークデータ実験によって効率と効率を実証する。

関連論文リスト

• Online Graph Learning via Time-Vertex Adaptive Filters: From Theory to Cardiac Fibrillation [37.69303106863453]
  グラフシフト演算子(GSO)の適応推定のためのオンラインアルゴリズムであるAdaCGPを導入する。 シミュレーションにより、AdaCGPは様々なグラフトポロジに対して一貫して良好に機能し、GSO推定において82%以上の改善が達成されることを示す。 AdaCGPのグラフ構造の変化を追跡する能力は、抗不整脈薬による心室細動動態の記録に示されている。
  論文  参考訳（メタデータ） (2024-11-03T13:43:51Z)
• Conformalized Link Prediction on Graph Neural Networks [8.807684750444626]
  グラフニューラルネットワーク(GNN)は様々なタスクに優れていますが、高い領域でのその応用は信頼性の低い予測によって妨げられます。 本稿では,GNNに基づくリンク予測の統計的保証を伴う予測区間を構築するために,分布自由かつモデルに依存しない不確実性定量化手法を提案する。
  論文  参考訳（メタデータ） (2024-06-26T21:17:37Z)
• Redefining the Shortest Path Problem Formulation of the Linear Non-Gaussian Acyclic Model: Pairwise Likelihood Ratios, Prior Knowledge, and Path Enumeration [0.0]
  本稿では,LiNGAM-SPPフレームワークの3倍拡張を提案する。 パラメータチューニングの必要性は、kNNベースの相互情報の代わりに、ペアワイズ確率比を用いて排除される。 先行知識の組み入れは、すべての因果順序のグラフ表現に実装されたノードスキッピング戦略によって実現される。
  論文  参考訳（メタデータ） (2024-04-18T05:59:28Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• 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)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。 本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
  論文  参考訳（メタデータ） (2022-02-05T08:21:04Z)
• 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)

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

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