論文の概要: Fast and Attributed Change Detection on Dynamic Graphs with Density of States

• arxiv url: http://arxiv.org/abs/2305.08750v1
• Date: Mon, 15 May 2023 16:02:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-16 13:58:01.430877
• Title: Fast and Attributed Change Detection on Dynamic Graphs with Density of States
• Title（参考訳）: 状態密度を持つ動的グラフの高速かつ分散的な変化検出
• Authors: Shenyang Huang, Jacob Danovitch, Guillaume Rabusseau, Reihaneh Rabbany
• Abstract要約: 現在のソリューションは、大規模な実世界のグラフに対してうまくスケールせず、大量のノードの追加/削除に対する堅牢性がなく、ノード属性の変更を見落としている。 SCPDは,各ステップにおけるラプラシアスペクトルの分布を効率よく近似することにより,各グラフスナップショットに対する埋め込みを生成する。 SCPDは最先端の性能を実現し,数分間で数百万のエッジを容易に処理できることを示す。
• 参考スコア（独自算出の注目度）: 9.409281517596396
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How can we detect traffic disturbances from international flight transportation logs or changes to collaboration dynamics in academic networks? These problems can be formulated as detecting anomalous change points in a dynamic graph. Current solutions do not scale well to large real-world graphs, lack robustness to large amounts of node additions/deletions, and overlook changes in node attributes. To address these limitations, we propose a novel spectral method: Scalable Change Point Detection (SCPD). SCPD generates an embedding for each graph snapshot by efficiently approximating the distribution of the Laplacian spectrum at each step. SCPD can also capture shifts in node attributes by tracking correlations between attributes and eigenvectors. Through extensive experiments using synthetic and real-world data, we show that SCPD (a) achieves state-of-the art performance, (b) is significantly faster than the state-of-the-art methods and can easily process millions of edges in a few CPU minutes, (c) can effectively tackle a large quantity of node attributes, additions or deletions and (d) discovers interesting events in large real-world graphs. The code is publicly available at https://github.com/shenyangHuang/SCPD.git
• Abstract（参考訳）: 学術ネットワークにおける国際航空輸送ログからの交通障害やコラボレーションのダイナミクスの変化をどうやって検出できるのか? これらの問題は、動的グラフにおける異常な変化点の検出として定式化することができる。 現在のソリューションは、大規模な実世界のグラフに対してうまくスケールせず、大量のノードの追加/削除に対する堅牢性がなく、ノード属性の変更を見落としている。 そこで本研究では,新しいスペクトル法であるスケーラブルな変化点検出(scpd)を提案する。 SCPDは、各ステップにおけるラプラシアスペクトルの分布を効率的に近似することにより、グラフスナップショット毎に埋め込みを生成する。 scpdはまた、属性と固有ベクトルの間の相関を追跡することで、ノード属性のシフトをキャプチャできる。 合成データと実世界データを用いた広範な実験を通して、scpdは (a)最先端の成果を成し遂げる。 b) は最先端のメソッドよりもはるかに高速であり、数cpuで数百万のエッジを簡単に処理できる。 c) 大量のノード属性、追加または削除に効果的に取り組むことができる。 (d) 大きな実世界のグラフで興味深い事象を発見する。 コードはhttps://github.com/shenyangHuang/SCPD.gitで公開されている。

関連論文リスト

• Multitask Active Learning for Graph Anomaly Detection [48.690169078479116]
  MultItask acTIve Graph Anomaly Detection framework,すなわちMITIGATEを提案する。 ノード分類タスクを結合することにより、MITIGATEは既知の異常を伴わずに配布外ノードを検出する能力を得る。 4つのデータセットに関する実証的研究は、MITIGATEが異常検出のための最先端の手法を著しく上回っていることを示している。
  論文  参考訳（メタデータ） (2024-01-24T03:43:45Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  この研究は、モデルの特徴と重要な設計制約を識別することに焦点を当てた、単一の大規模グラフでの表現学習を前進させる。 この研究の重要な革新は、局所的な注意機構と組み合わされた高速な近傍サンプリング技術の作成である。 ogbn-products と snap-patents の3倍の高速化と16.8%の性能向上を報告し、ogbn-100M で LargeGT を5.9% の性能改善で拡張した。
  論文  参考訳（メタデータ） (2023-12-18T11:19:23Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。 ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。 BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
  論文  参考訳（メタデータ） (2023-07-28T00:44:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• A fast topological approach for predicting anomalies in time-varying graphs [0.0]
  トポロジカルデータ解析(TDA)からの永続化ダイアグラム(PD)は、点間距離が明確に定義されたデータ形状記述法として人気がある。 本稿では,グラフデータから形状情報を抽出する計算効率の良いフレームワークを提案する。 実際のデータアプリケーションでは、暗号取引ネットワークの異常な価格予測において、我々のアプローチは最大で22%上昇する。
  論文  参考訳（メタデータ） (2023-05-11T01:54:45Z)
• Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs [9.663142156296862]
  動的グラフにおける変化点検出に着目し、この問題に関連する3つの主な課題に対処する。 まず,各スナップショットにおけるグラフ構造の低次元埋め込みとして,グラフラプラシアンスペクトルを用いたラプラシアン異常検出(Laplacian Anomaly Detection,LAD)を提案する。 次に,多視点グラフへのLADの単純かつ効果的な一般化であるMultiLADを提案する。
  論文  参考訳（メタデータ） (2023-02-02T16:30:43Z)
• Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation [61.39364567221311]
  グラフレベルの異常検出(GAD)は、その構造やノードの特徴に異常なグラフを検出する問題を記述している。 GADの課題の1つは、局所的および大域的非正則グラフの検出を可能にするグラフ表現を考案することである。 本稿では,グラフとノード表現の連成ランダム蒸留により,グローバルおよびローカルな正規パターン情報を豊富に学習するGADのための新しい深部異常検出手法を提案する。
  論文  参考訳（メタデータ） (2021-12-19T05:04:53Z)
• Fast Attributed Graph Embedding via Density of States [17.360163137925994]
  分散DOSベースのグラフ埋め込みのためのA-DOGEを提案する。 A-DOGEは望ましい特性の長いデシラタを満たすように設計されている。 グラフの固有スペクトル全体に基づいて、A-DOGEは複数の「局所」スケールで構造特性と属性特性をキャプチャすることができる。
  論文  参考訳（メタデータ） (2021-10-11T12:44:58Z)
• Laplacian Change Point Detection for Dynamic Graphs [10.556288610354997]
  各スナップショットにおけるグラフ構造のラプラシアン行列のスペクトルを用いて低次元埋め込みを求めるラプラシアン異常検出(Laplacian Anomaly Detection,LAD)を提案する。 合成実験では、LADは最先端の手法よりも優れている。 また,UCIメッセージネットワーク,米国上院共同責任ネットワーク,カナダ紙幣投票ネットワークの3つの実動的ネットワーク上で,本手法の評価を行った。
  論文  参考訳（メタデータ） (2020-07-02T16:24:24Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  本稿では,動的グラフの異常エッジを検出するために,エンドツーエンドの時間構造グラフニューラルネットワークモデルを提案する。 特に,まずターゲットエッジを中心にした$h$ホップ囲むサブグラフを抽出し,各ノードの役割を識別するノードラベル機能を提案する。 抽出した特徴に基づき,GRU(Gated Recurrent Unit)を用いて,異常検出のための時間的情報を取得する。
  論文  参考訳（メタデータ） (2020-05-15T09:17:08Z)

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

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