論文の概要: Sketch-Based Anomaly Detection in Streaming Graphs

• arxiv url: http://arxiv.org/abs/2106.04486v3
• Date: Thu, 13 Jul 2023 11:14:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-19 01:07:03.511591
• Title: Sketch-Based Anomaly Detection in Streaming Graphs
• Title（参考訳）: ストリームグラフにおけるスケッチに基づく異常検出
• Authors: Siddharth Bhatia, Mohit Wadhwa, Kenji Kawaguchi, Neil Shah, Philip S. Yu, Bryan Hooi
• Abstract要約: 動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
• 参考スコア（独自算出の注目度）: 89.52200264469364
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? For example, in intrusion detection, existing work seeks to detect either anomalous edges or anomalous subgraphs, but not both. In this paper, we first extend the count-min sketch data structure to a higher-order sketch. This higher-order sketch has the useful property of preserving the dense subgraph structure (dense subgraphs in the input turn into dense submatrices in the data structure). We then propose 4 online algorithms that utilize this enhanced data structure, which (a) detect both edge and graph anomalies; (b) process each edge and graph in constant memory and constant update time per newly arriving edge, and; (c) outperform state-of-the-art baselines on 4 real-world datasets. Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
• Abstract（参考訳）: 動的グラフからグラフエッジのストリームを与えられた場合、一定時間とメモリを用いて異常な振る舞いを検出するために、どのようにして異常スコアをエッジやサブグラフにオンライン的に割り当てるか。 例えば、侵入検知では、既存の研究は異常なエッジまたは異常なサブグラフを検知しようとするが、どちらも検出しない。 本稿では,まず,カウントミンスケッチデータ構造を高次スケッチに拡張する。 この高次スケッチは、高密度な部分グラフ構造を保存するのに有用な性質を持つ(入力の高密度な部分グラフはデータ構造の高密度な部分行列となる)。 次に,この拡張データ構造を利用した4つのオンラインアルゴリズムを提案する。 a) エッジとグラフの両方の異常を検出する。 b) 各エッジとグラフを一定メモリで処理し,新たに到着したエッジ毎の更新時間を一定にする。 c) 4つの実世界のデータセットで最先端のベースラインを上回る。 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。

関連論文リスト

• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• 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)
• A fast topological approach for predicting anomalies in time-varying graphs [0.0]
  トポロジカルデータ解析(TDA)からの永続化ダイアグラム(PD)は、点間距離が明確に定義されたデータ形状記述法として人気がある。 本稿では,グラフデータから形状情報を抽出する計算効率の良いフレームワークを提案する。 実際のデータアプリケーションでは、暗号取引ネットワークの異常な価格予測において、我々のアプローチは最大で22%上昇する。
  論文  参考訳（メタデータ） (2023-05-11T01:54:45Z)
• Digraphwave: Scalable Extraction of Structural Node Embeddings via Diffusion on Directed Graphs [20.432261314154804]
  Digraphwaveは、有向グラフ上の構造ノード埋め込みを抽出するスケーラブルなアルゴリズムである。 この2つの組込み強化は、自己同型アイデンティティの分類において、マクロF1スコアの顕著な増加につながることが示されている。
  論文  参考訳（メタデータ） (2022-07-20T19:03:35Z)
• Computing Graph Descriptors on Edge Streams [4.129847064263056]
  約3種類のグラフ記述子を計算するために,ストリーミングアルゴリズムを提案する。 エッジストリームを操作することで、グラフ全体をメモリに格納するのを避けることができます。 私たちのスケーラブルなアルゴリズムは、数分で数百万のエッジを持つグラフの記述子を計算します。
  論文  参考訳（メタデータ） (2021-09-02T06:21:47Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  本稿では,動的グラフの異常エッジを検出するために,エンドツーエンドの時間構造グラフニューラルネットワークモデルを提案する。 特に,まずターゲットエッジを中心にした$h$ホップ囲むサブグラフを抽出し,各ノードの役割を識別するノードラベル機能を提案する。 抽出した特徴に基づき,GRU(Gated Recurrent Unit)を用いて,異常検出のための時間的情報を取得する。
  論文  参考訳（メタデータ） (2020-05-15T09:17:08Z)

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

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