論文の概要: Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged
Approach
- arxiv url: http://arxiv.org/abs/2011.13085v1
- Date: Thu, 26 Nov 2020 01:38:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-20 12:06:29.506118
- Title: Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged
Approach
- Title（参考訳）: 2段階アプローチによる動的グラフの高速かつ高精度な異常検出
- Authors: Minji Yoon, Bryan Hooi, Kijung Shin, Christos Faloutsos
- Abstract要約: 動的グラフにおける異常検出のためのオンラインアルゴリズムAnomRankを提案する。
AnomRank氏は、異常を示す2つの新しいメトリクスを定義する2段階のアプローチを使用している。
理論的,実験的に,この2つのアプローチが共通の2種類の異常の検出に成功していることを示す。
- 参考スコア（独自算出の注目度）: 49.25767340466445
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a dynamic graph stream, how can we detect the sudden appearance of
anomalous patterns, such as link spam, follower boosting, or denial of service
attacks? Additionally, can we categorize the types of anomalies that occur in
practice, and theoretically analyze the anomalous signs arising from each type?
In this work, we propose AnomRank, an online algorithm for anomaly detection in
dynamic graphs. AnomRank uses a two-pronged approach defining two novel metrics
for anomalousness. Each metric tracks the derivatives of its own version of a
'node score' (or node importance) function. This allows us to detect sudden
changes in the importance of any node. We show theoretically and experimentally
that the two-pronged approach successfully detects two common types of
anomalies: sudden weight changes along an edge, and sudden structural changes
to the graph. AnomRank is (a) Fast and Accurate: up to 49.5x faster or 35% more
accurate than state-of-the-art methods, (b) Scalable: linear in the number of
edges in the input graph, processing millions of edges within 2 seconds on a
stock laptop/desktop, and (c) Theoretically Sound: providing theoretical
guarantees of the two-pronged approach.
- Abstract（参考訳）: 動的グラフストリームを考えると,リンクスパムやフォロワブースト,サービス攻撃拒否など,異常なパターンの突然の出現を検知するにはどうすればよいのでしょう?
さらに,実際に発生する異常のタイプを分類し,各タイプから発生する異常な兆候を理論的に分析することができるか?
本研究では,動的グラフにおける異常検出のためのオンラインアルゴリズムAnomRankを提案する。
AnomRank氏は、異常を示す2つの新しいメトリクスを定義する2段階のアプローチを使用している。
各メトリクスは'ノードスコア'(またはノードの重要度)関数の独自のバージョンの導関数を追跡する。
これにより、ノードの重要性に対する突然の変化を検出できます。
理論的,実験的に,この2つのアプローチが,エッジに沿った突然の重み変化と,グラフの突然の構造変化の2つの共通なタイプの異常を検出することに成功した。
AnomRankは
a) 高速で正確: 最先端の手法よりも49.5倍速く、または35%正確である。
(b)スケーラブル:入力グラフのエッジ数を線形にし、ストックラップトップ/デスクトップ上で2秒以内に数百万のエッジを処理する。
(c)理論的には、二段階アプローチの理論的保証を提供する。
関連論文リスト
- SLADE: Detecting Dynamic Anomalies in Edge Streams without Labels via Self-Supervised Learning [24.41015179377796]
本稿では,エッジストリーム中の動的異常を迅速に検出するためのSLADE(Self-supervised Learning for Anomaly Detection in Edge Streams)を提案する。
現実世界の4つのデータセットにわたる動的異常検出では、SLADEは9つの競合する手法より優れている。
論文 参考訳（メタデータ） (2024-02-19T08:19:26Z) - ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection [84.0718034981805]
我々はAnomaly-Denoized Autoencoders for Graph Anomaly Detection (ADA-GAD)という新しいフレームワークを導入する。
第1段階では,異常レベルを低減したグラフを生成する学習自由な異常化拡張法を設計する。
次の段階では、デコーダは元のグラフで検出するために再訓練される。
論文 参考訳（メタデータ） (2023-12-22T09:02:01Z) - Graph Anomaly Detection with Unsupervised GNNs [19.772490600670363]
グラフニューラルネットワーク(GNN)に基づくエンドツーエンドのグラフレベルの異常検出モデルであるGLAMを設計する。
また,これまでに検討されていない分布異常の検出を目的とした,MDDプールと呼ばれるグラフレベルの埋め込みのための新しいプール方式を提案する。
論文 参考訳（メタデータ） (2022-10-18T01:59:58Z) - Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか?
本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
論文 参考訳（メタデータ） (2021-06-08T16:10:36Z) - Unveiling Anomalous Edges and Nominal Connectivity of Attributed
Networks [53.56901624204265]
本研究では、相補的な強さを持つ2つの異なる定式化を用いて、属性グラフの異常なエッジを明らかにする。
まず、グラフデータマトリックスを低ランクとスパースコンポーネントに分解することで、パフォーマンスを著しく向上させる。
第2は、乱れのないグラフを頑健に復元することにより、第1のスコープを広げ、異常識別性能を高める。
論文 参考訳（メタデータ） (2021-04-17T20:00:40Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳（メタデータ） (2020-10-20T05:54:31Z) - Real-Time Anomaly Detection in Edge Streams [49.26098240310257]
マイクロクラスタ異常の検出に焦点を当てたMIDASを提案する。
さらに、アルゴリズムの内部状態に異常が組み込まれている問題を解くために、MIDAS-Fを提案する。
実験の結果,MIDAS-Fの精度はMIDASよりも有意に高かった。
論文 参考訳（メタデータ） (2020-09-17T17:59:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。