論文の概要、ライセンス

# (参考訳) ダイナミックグラフにおけるスケッチベースストリーミング異常検出 [全文訳有]

Sketch-Based Streaming Anomaly Detection in Dynamic Graphs ( http://arxiv.org/abs/2106.04486v1 )

ライセンス: CC BY 4.0
Siddharth Bhatia, Mohit Wadhwa, Philip S. Yu, Bryan Hooi(参考訳) 動的グラフからグラフエッジのストリームを与えられた場合、一定時間とメモリを用いて異常な振る舞いを検出するために、どのようにして異常スコアをエッジやサブグラフにオンライン的に割り当てるか。 例えば、侵入検知では、既存の研究は異常なエッジまたは異常なサブグラフを検知しようとするが、どちらも検出しない。 本稿では,まず,カウントミンスケッチデータ構造を高次スケッチに拡張する。 この高次スケッチは、高密度な部分グラフ構造を保存するのに有用な性質を持つ(入力の高密度な部分グラフはデータ構造の高密度な部分行列となる)。 次に、この強化されたデータ構造を利用する4つのオンラインアルゴリズムを提案し、(a)エッジとグラフの異常を検知し、(b)各エッジとグラフを一定メモリで処理し、(c)4つの実世界のデータセット上で、最先端のベースラインを性能良くする。 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。

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 four 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 four real-world datasets. Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
公開日: Tue, 8 Jun 2021 16:10:36 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] S D . s c [ 8 ] S D。 sc [ 0.69
1 v 6 8 4 4 0 1 v 6 8 4 4 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Sketch-Based Streaming Anomaly Detection in スケッチに基づくストリーミング異常検出 0.71
Dynamic Graphs Siddharth Bhatia 動的グラフ シッダート・バティア(Siddharth Bhatia) 0.53
National University of Singapore シンガポール国立大学 0.63
siddharth@comp.nus.e du.sg siddharth@comp.nus.e du.sg 0.47
Philip S. Yu Philip S. Yu 0.94
University of Illinois at Chicago イリノイ大学シカゴ校 0.58
psyu@uic.edu psyu@uic.edu 0.78
Mohit Wadhwa Mohit Wadhwa 0.85
mailmohitwadhwa@gmai l.com mailmohitwadhwa@gmai l.com 0.78
Bryan Hooi National University of Singapore bhooi@comp.nus.edu.s g ブライアン・フーイ national university of singapore bhooi@comp.nus.edu.s g 0.55
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? 概要 動的グラフからグラフエッジのストリームを与えられた場合、一定時間とメモリを用いて異常な振る舞いを検出するために、どのようにして異常スコアをエッジやサブグラフにオンライン的に割り当てるか。 0.62
For example, in intrusion detection, existing work seeks to detect either anomalous edges or anomalous subgraphs, but not both. 例えば、侵入検知では、既存の研究は異常なエッジまたは異常なサブグラフを検知しようとするが、どちらも検出しない。
訳抜け防止モード: 例えば 侵入検知では 異常エッジまたは異常サブグラフのいずれかを検出するが、両方を検出できないようにする。
0.75
In this paper, we first extend the count-min sketch data structure to a higher-order sketch. 本稿では,まず,カウントミンスケッチデータ構造を高次スケッチに拡張する。 0.57
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). この高次スケッチは、高密度な部分グラフ構造を保存するのに有用な性質を持つ(入力の高密度な部分グラフはデータ構造の高密度な部分行列となる)。 0.59
We then propose four 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 four real-world datasets. 次に、この強化されたデータ構造を利用する4つのオンラインアルゴリズムを提案し、(a)エッジとグラフの異常を検知し、(b)各エッジとグラフを一定メモリで処理し、(c)4つの実世界のデータセット上で、最先端のベースラインを性能良くする。 0.78
Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time. 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。 0.75
1 Introduction Consider an intrusion detection system, in which many forms of anomalous behavior can be described as a group of attackers making a large number of connections to some set of targeted machines to restrict accessibility or look for potential vulnerabilities. 1 はじめに 侵入検知システム(intrusion detection system)を考えると、多くの形態の異常な行動は、アクセシビリティを制限したり潜在的な脆弱性を探すためにターゲットマシン群と大量の接続を行う攻撃者のグループとして記述できる。 0.72
We can model this as a dynamic graph, where nodes correspond to machines, and each edge represents a timestamped connection from one machine to another. ノードがマシンに対応する動的グラフとしてモデル化でき、各エッジはひとつのマシンから別のマシンへのタイムスタンプ接続を表します。 0.81
In this graph, anomalous behavior often takes the form of a dense subgraph, as shown in several real-world datasets in [1–3]. このグラフでは、[1-3]のいくつかの実世界のデータセットに示されているように、異常な振る舞いは、しばしば密度の高い部分グラフの形を取る。
訳抜け防止モード: このグラフでは、異常な振る舞いはしばしば密度のある部分グラフの形を取る。 いくつかの実世界のデータセットで示されるように。
0.64
Thus, we ask the question: Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to both edges and subgraphs in an online manner, for the purpose of detecting unusual behavior, using constant memory and constant update time per newly arriving edge? 動的グラフからグラフエッジのストリームが与えられた場合、不規則な振る舞いを検知するために、新しいエッジ毎に一定メモリと一定更新時間を用いて、どのようにして異常スコアをオンライン的にエッジとサブグラフの両方に割り当てることができるのか? 0.80
Several approaches [4–10] aim to detect anomalies in graph settings. いくつかのアプローチ[4–10]は、グラフ設定の異常を検出することを目的としている。 0.50
However, these approaches focus on static graphs, whereas many real-world graphs are time-evolving in nature. しかし、これらのアプローチは静的グラフにフォーカスするが、現実のグラフの多くは本質的に時間発展している。 0.57
In streaming or online graph scenarios, some methods can detect the presence of anomalous edges, [3, 11–13], while others can detect anomalous subgraphs [1, 2, 14]. ストリーミングやオンライングラフのシナリオでは、[3, 11–13]という異常なエッジの存在を検出する方法と、[1, 2, 14]の異常なサブグラフを検出する方法がある。 0.64
However, all existing methods are limited to either anomalous edge or graph detection but not able to detect both kinds of anomalies, as summarized in Table 1. しかし、既存のすべての手法は異常エッジまたはグラフ検出に限られているが、表1に示すように、どちらの種類の異常も検出できない。 0.76
As we discuss in Section 7, our approach outperforms existing methods in both accuracy and running time; and on both anomalous edge and subgraph detection scenarios. 第7節で論じるように、我々の手法は、精度と実行時間の両方で既存の手法より優れており、異常なエッジとサブグラフ検出のシナリオでも優れている。
訳抜け防止モード: 第7節で論じたように、我々は既存の手法を精度と実行時間の両方で上回ります。 そして 異常なエッジと サブグラフ検出のシナリオで
0.74
Moreover, our approach is the only streaming method that makes use of dense subgraph search to detect graph anomalies while only requiring constant memory and time. さらに,本手法は,一定のメモリと時間しか必要とせず,グラフ異常を検出するために高密度部分グラフ探索を利用する唯一のストリーミング手法である。 0.75
英語(論文から抽出)日本語訳スコア
Table 1: Comparison of relevant anomaly detection approaches. 表1: 関連する異常検出アプローチの比較。 0.83
Property DenseStream SedanSpot MIDAS-R PENminer (KDD’20) プロパティDenseStream SedanSpot MIDAS-R PENminer (KDD’20) 0.86
(ICDM’20) (AAAI’20) (ICDM’20) (AAAI'20) 0.84
(KDD’17) F-FADE (KDD’17) F‐FADE 0.71
(WSDM’21) DenseAlert SpotLight AnomRank Our Method (KDD’17) (WSDM’21) DenseAlert SpotLight AnomRank Our Method (KDD’17) 0.85
(KDD’18) (KDD’19) (KDD'18) (KDD’19) 0.84
(2021) Edge Anomaly Graph Anomaly Constant Memory Constant Update Time Dense Subgraph Search (2021) Edge Anomaly Graph Anomaly Constant Memory Constant Update Time Dense Subgraph Search 0.85
! – – – ! ! ! – – – ! ! 0.85
– ! ! – ! – ! – ! ! – ! – ! 0.85
! – ! – – ! ! – ! – – ! 0.85
– ! – ! ! – – ! – ! ! – 0.85
– ! – – ! – ! – ! – – ! – ! 0.85
! ! – – ! – – – ! ! – – ! – – – 0.85
" " " " " We first extend the two-dimensional sketch to a higher-order sketch to enable it to embed the relation between the source and destination nodes in a graph. " " " " " まず、2次元のスケッチを高階のスケッチに拡張し、ソースノードと宛先ノードの関係をグラフに埋め込むことを可能にする。 0.79
A higher-order sketch has the useful property of preserving the dense subgraph structure; dense subgraphs in the input turn into dense submatrices in this data structure. 高次スケッチは、高密度部分グラフ構造を保存するのに有用であり、入力の高密度部分グラフは、このデータ構造で高密度部分グラフとなる。 0.57
Thus, the problem of detecting a dense subgraph from a large graph reduces to finding a dense submatrix in a constant size matrix, which can be achieved in constant time. したがって、大きなグラフから高密度部分グラフを検出する問題は、一定時間で達成できるような、一定のサイズ行列内の高密度部分行列を見つけることにつながる。 0.67
The higher-order sketch allows us to propose several algorithms to detect both anomalous edges and subgraphs in a streaming manner. 高次スケッチにより、異常なエッジとサブグラフの両方をストリーミング形式で検出するアルゴリズムを複数提案できる。 0.78
We introduce two edge anomaly detection methods, ANOEDGE-G, and ANOEDGE-L, and two graph anomaly detection methods ANOGRAPH, and ANOGRAPH-K, that use the same data structure to detect the presence of a dense submatrix, and consequently anomalous edges, or subgraphs respectively. 本稿では,同じデータ構造を用いて密度の高いサブマトリックスの存在を検知する2つのエッジ異常検出法,anoedge-g,anoedge-l ,および2つのグラフ異常検出法anograph,anograph-kを導入する。 0.73
All our approaches process edges and graphs in constant time, and are independent of the graph size, i.e., they require constant memory. 我々のアプローチはすべて、エッジとグラフを一定時間処理し、グラフのサイズ、すなわち、一定のメモリを必要とする。 0.74
We also provide theoretical guarantees on the higher-order sketch estimate and the submatrix density measure. また,高次スケッチ推定とサブマトリクス密度測定に関する理論的保証も提供する。 0.82
In summary, the main contributions of our paper are: まとめると、私たちの論文の主な貢献は次のとおりです。 0.68
1. Higher-Order Sketch (Section 4): We transform the dense subgraph detection problem into finding a dense submatrix (which can be achieved in constant time) by extending the count-min sketch (CMS) [15] data structure to a higher-order sketch. 1. 高次スケッチ(第4節): 高密度部分グラフ検出問題を,count-min sketch (cms) [15] データ構造を高次スケッチに拡張することにより,高密度部分行列(一定時間内に達成できる)を見つけるように変換する。 0.83
2. Streaming Anomaly Detection (Sections 5,6): We propose four novel online approaches to detect anomalous edges and graphs in real-time, with constant memory and update time. 2. Streaming Anomaly Detection (Sections 5,6): 一定のメモリと更新時間でリアルタイムに異常なエッジとグラフを検出する4つの新しいオンラインアプローチを提案する。 0.80
Moreover, this is the first streaming work that incorporates dense subgraph search to detect graph anomalies in constant memory/time. さらに、これは密度の高いサブグラフ探索を組み込んだ最初のストリーミング作業であり、一定メモリ/時間におけるグラフ異常を検出する。 0.63
3. Effectiveness (Section 7): We outperform all state-of-the-art streaming edge and graph 3. 有効性(セクション7): 最先端のストリーミングエッジとグラフよりも優れています。 0.72
anomaly detection methods on four real-world datasets. 4つの実世界のデータセットにおける異常検出法 0.56
Reproducibility: Our code and datasets are available at https://github.com/S tream-AD/AnoGraph. 再現性: 私たちのコードとデータセットは、https://github.com/s tream-ad/anographで利用可能です。 0.38
2 Related Work Our work is closely related to areas like anomaly detection on graphs [16–23] and streams [24–32], and streaming algorithms [33–37]. 2 関連作業 我々の研究はグラフ [16–23] やストリーム [24–32] の異常検出やストリーミングアルゴリズム [33–37] といった分野と密接に関連している。 0.77
Higher-order sketches are discussed in [37], however, they are restricted to count-sketches and non-graph settings. 高次スケッチは[37]で議論されるが、カウントスケッチや非グラフ設定に制限される。 0.63
[38, 39] discuss deep learning based anomaly detection, however, such approaches are unable to detect anomalies in a streaming manner. 38,39]はディープラーニングに基づく異常検出について論じるが,このような手法はストリーミング方式では異常を検出できない。 0.82
[4–10] are limited to anomaly detection in static graphs. 4-10]は静的グラフの異常検出に制限される。 0.76
In this section, however, we limit our review only to methods detecting edge and graph anomalies in dynamic graphs; see [40] for an extensive survey. しかし、本節では、このレビューは、動的グラフにおけるエッジおよびグラフ異常を検出する方法のみに限定されます。 0.61
Edge Stream Methods: HOTSPOT [41] detects nodes whose egonets suddenly change. エッジストリームメソッド: HOTSPOT [41]は、エゴネが突然変化するノードを検出する。 0.78
RHSS [42] focuses on sparsely-connected graph parts. RHSS[42]は疎結合なグラフ部品に焦点を当てている。 0.58
CAD [43] localizes anomalous changes using commute time distance measurement. CAD[43]は通勤時間距離測定を用いて異常変化を局所化する。 0.74
More recently, DENSESTREAM [1] maintains and updates a dense subtensor in a tensor stream. より最近では、dungstream [1]はテンソルストリーム内の密度の高いサブテンソルを維持して更新する。 0.55
SEDANSPOT [11] identifies edge anomalies based on edge occurrence, preferential attachment, and mutual neighbors. SEDANSPOT[11]は、エッジの発生、優先アタッチメント、および相互隣人に基づいてエッジ異常を特定する。 0.64
PENminer [12] explores the persistence of activity snippets, i.e., the length and regularity of edge-update sequences’ reoccurrences. penminer [12] はアクティビティスニペットの永続性、すなわちエッジ更新シーケンスの繰り返しの長さと規則性を探求する。
訳抜け防止モード: PENminer [ 12 ] はアクティビティスニペットの永続性、すなわち the length and regularity of edge - update sequences ’ reoccurrences .
0.76
F-FADE [13] aims to detect anomalous interaction patterns by factorizing their frequency. F-FADE[13]はその周波数を分解して異常な相互作用パターンを検出することを目的とする。 0.56
MIDAS [3] identifies microcluster-based anomalies. MIDAS[3]はマイクロクラスタベースの異常を識別する。 0.58
However, all these methods are unable to detect graph anomalies. しかし,これらの手法はグラフ異常を検出できない。 0.77
Graph Stream Methods: DTA/STA [44] approximates the adjacency matrix of the current snapshot using matrix factorization. グラフストリームメソッド: dta/sta [44] は、マトリックス分解を使って現在のスナップショットの隣接行列を近似する。 0.68
COPYCATCH [45] spots near-bipartite cores where each node is connected to others in the same core densely within a short time. コピーキャッチ [45] は、各ノードが同じコア内の他のノードと短時間で密に接続される2部近くのコアである。 0.66
SPOT/DSPOT [30] use extreme value theory to automatically set thresholds for anomalies. SPOT/DSPOT [30] は極値理論を用いて異常の閾値を自動的に設定する。 0.72
IncGM+ [46] utilizes incremental method to process graph updates. IncGM+[46]はインクリメンタルメソッドを使用してグラフ更新を処理する。 0.66
More recently, DENSEALERT identifies subtensors created within a short time and utilizes incremental method to process graph updates or subgraphs more efficiently. 最近では、DENSEALERTは、短時間で作成された拡張子を特定し、インクリメンタルメソッドを使用してグラフ更新やサブグラフをより効率的に処理している。
訳抜け防止モード: 最近では、DENSEALERTは短い時間で生成された拡張子を識別する インクリメンタルな手法を使って グラフ更新やサブグラフをより効率的に処理します
0.65
SPOTLIGHT 2 SPOTLIGHT 2 0.85
英語(論文から抽出)日本語訳スコア
[2] discovers anomalous graphs with dense bi-cliques, but uses a randomized approach without any search for dense subgraphs. [2] は密接な双斜体を持つ異常グラフを発見するが、密接な部分グラフを探索せずにランダム化アプローチを用いる。 0.64
ANOMRANK [14], inspired by PageRank [47], iteratively updates two score vectors and computes anomaly scores. ANOMRANK [14]はPageRank [47]にインスパイアされ、2つのスコアベクトルを反復的に更新し、異常スコアを計算する。 0.62
However, these methods are slow and do not detect edge anomalies. しかし、これらの手法は遅く、エッジ異常を検出できない。 0.65
Moreover, they do not search for dense subgraphs in constant memory and time. さらに、彼らは一定の記憶と時間で密度の高い部分グラフを探索しない。 0.60
3 Problem Let E = {e1, e2,···} be a stream of weighted edges from a time-evolving graph G. Each arriving edge is a tuple ei = (ui, vi, wi, ti) consisting of a source node ui ∈ V, a destination node vi ∈ V, a weight wi, and a time of occurrence ti, the time at which the edge is added to the graph. 3問題 e = {e1, e2,····} を時間発展グラフ g から重み付きエッジのストリームとする: 各エッジは、ソースノード ui ∈ v と宛先ノード vi ∈ v, 重みwi, 発生時刻 ti からなるタプル ei = (ui, vi, wi, ti) である。
訳抜け防止モード: 3 問題 E = { e1, e2, · · · } を時間-発展グラフ G からの重み付きエッジのストリームとする。 vi, wi, ti ) はソースノード ui ∈ V から構成される。 宛先ノード vi ∈ V, 重み wi, 発生時刻tiは、エッジがグラフに追加される時間です。
0.66
For example, in a network traffic stream, an edge ei could represent a connection made from a source IP address ui to a destination IP address vi at time ti. 例えば、ネットワークトラフィックストリームでは、edge eiは、時刻tiにおいて、ソースipアドレスuiから宛先ipアドレスviへの接続を表すことができる。 0.62
We do not assume that the set of vertices V is known a priori: for example, new IP addresses or user IDs may be created over the course of the stream. 例えば、新しいIPアドレスやユーザIDがストリームの途中で生成される可能性がある。
訳抜け防止モード: 我々は、頂点 V の集合が先験として知られていると仮定しない。 例えば、新しいIPアドレスやユーザIDは、ストリームを通じて作成できる。
0.67
We model G as a directed graph. g を有向グラフとしてモデル化する。 0.71
Undirected graphs can be handled by treating an incoming undirected edge as two simultaneous directed edges, one in each direction. 無向グラフは、入ってくる無向エッジを2つの同時有向エッジとして扱うことで処理できる。 0.71
We also allow G to be a multigraph: edges can be created multiple times between the same pair of nodes. エッジは、同じノードのペア間で複数回作成することができます。
訳抜け防止モード: また、G を多重グラフとして許す。 エッジは、同じノードのペア間で複数回作成できる。
0.71
Edges are allowed to arrive simultaneously: i.e. エッジは同時に到着することができる。 0.66
ti+1 ≥ ti, since in many applications ti is given as a discrete time tick. ti+1 ≥ ti は、多くのアプリケーションにおいて、ti が離散時間ティックとして与えられるためである。
訳抜け防止モード: ti+1 ≥ ti 以降 多くの応用では タイは離散時間として与えられます
0.75
The desired properties of our algorithm are as follows: 我々のアルゴリズムの望ましい性質は以下の通りである。 0.78
• Detecting Anomalous Edges: To detect whether the edge is part of an anomalous subgraph in an online manner. • 異常エッジの検出: 異常エッジが異常サブグラフの一部であるかどうかをオンラインで検出する。 0.82
Being able to detect anomalies at the finer granularity of edges allows early detection so that recovery can be started as soon as possible and the effect of malicious activities is minimized. エッジの粒度の細かい異常を早期に検出できるため、回復をできるだけ早く開始でき、悪意のある活動の効果を最小限に抑えることができる。
訳抜け防止モード: エッジのより微細な粒度で異常を検出することができる 早期発見が可能で 回復はできるだけ早く開始できます 悪意ある活動の効果は 最小限に抑えられます
0.86
• Detecting Anomalous Graphs: To detect the presence of an unusual subgraph (consisting of edges received over a period of time) in an online manner, since such subgraphs often correspond to unexpected behavior, such as coordinated attacks. • 異常グラフの検出: 異常なサブグラフ(一定期間にわたって受信されるエッジの構成)の存在をオンラインで検出する。
訳抜け防止モード: •異常なグラフの検出 : 異常なサブグラフ(一定時間にわたって受信されたエッジからなる)の存在をオンラインで検出する このようなサブグラフはしばしば、協調攻撃のような予期せぬ行動に対応している。
0.79
• Constant Memory and Update Time: To ensure scalability, memory usage and update time should not grow with the number of nodes or the length of the stream. • 一定メモリと更新時間: スケーラビリティを確保するため、メモリ使用量と更新時間は、ノードの数やストリームの長さによっては増加しない。 0.81
Thus, for a newly arriving edge, our algorithm should run in constant memory and update time. したがって、新しいエッジでは、アルゴリズムは一定のメモリと更新時間で実行されるべきである。 0.74
4 Higher-Order Sketch & Notations 4高次スケッチと表記法 0.62
Count-min sketches (CMS) [15] are popular streaming data structures used by several online algorithms [48]. カウントミンスケッチ (CMS) [15] は、いくつかのオンラインアルゴリズム [48] で使われている一般的なストリーミングデータ構造です。 0.62
CMS uses multiple hash functions to map events to frequencies, but unlike a hash table uses only sub-linear space, at the expense of overcounting some events due to collisions. CMSは複数のハッシュ関数を使ってイベントを周波数にマッピングするが、ハッシュテーブルがサブ線形空間のみを使用するのとは異なり、衝突によるイベントのオーバーカウントを犠牲にしている。 0.68
Frequency is approximated as the minimum over all hash functions. 周波数はすべてのハッシュ関数の最小値として近似される。 0.62
CMS, shown in Figure 1(a), is represented as a two-dimensional matrix where each row corresponds to a hash function and hashes to the same number of buckets (columns). 図1(a)に示すCMSは、各行がハッシュ関数に対応し、同じ数のバケット(カラム)をハッシュする2次元行列として表される。 0.72
We introduce a Higher-order CMS (H-CMS) data structure where each hash function maps multi-dimensional input to a generic tensor instead of mapping it to a row vector. 本稿では,各ハッシュ関数が行ベクトルにマッピングする代わりに,多次元の入力を一般的なテンソルにマッピングする高階CMS(H-CMS)データ構造を提案する。 0.71
H-CMS enhances CMS by separately hashing the individual components of an entity thereby maintaining more information. H−CMSは、エンティティの個々のコンポーネントを別々にハッシュすることでCMSを強化し、より多くの情報を維持する。 0.54
Figure 1(b) shows a 3-dimensional H-CMS that can be used to hash two-dimensional entities such as graph edges to a matrix. 図1(b)は、グラフエッジのような二次元の実体を行列にハッシュするのに使用できる3次元H-CMSを示している。 0.73
The source node is hashed to the first dimension and the destination node to the other dimension of the sketch matrix, as opposed to the original CMS that will hash the entire edge to a one-dimensional row vector as shown in Figure 1(a). 原点ノードは、図1(a)に示すように、エッジ全体を1次元の行ベクトルにハッシュする元のCMSとは対照的に、スケッチ行列の他の次元への第1次元および宛先ノードにハッシュされる。 0.76
Theorem 1. (Proof in Appendix C) H-CMS has the same estimate guarantees as the original CMS. 理論1。 (Appendix C での証明) H-CMS は元の CMS と同じ推定保証を持つ。 0.73
We use a 3-dimensional H-CMS (operations described in Appendix A) where the number of hash functions is denoted by nr, and matrix M corresponding to each hash function is of dimension nb × nb, i.e., a square matrix. ハッシュ関数の数を表す3次元H-CMS(Appendix A で記述された操作)を用い、各ハッシュ関数に対応する行列 M は nb × nb,すなわち正方行列である。
訳抜け防止モード: 私たちは3次元H-CMS(Appendix A で記述された操作)を使用します。 ハッシュ関数の数はnrで表される そして各ハッシュ関数に対応する行列 M は nb × nb,すなわち平方行列である。
0.80
A hash function denoted by h(u) maps an entity u to an integer in the range [0, nb). h(u) で表されるハッシュ関数は、エンティティ u を [0, nb) の範囲内の整数に写像する。 0.74
A 3-dimensional H-CMS maps edge (u, v) to a matrix index (h(u), h(v)), i.e. 3次元 H-CMS は辺 (u, v) を行列指数 (h(u, h(v)) に写す。 0.68
the source node is mapped to a row index and the destination node is mapped to a column index. ソースノードは行インデックスにマッピングされ、宛先ノードは列インデックスにマッピングされる。 0.68
Therefore, each matrix in a 3-dimensional H-CMS captures the essence of a graph adjacency matrix. したがって、3次元 H-CMS の各行列はグラフ隣接行列の本質を捉えている。 0.71
Dense subgraph detection can thus be transformed into a dense submatrix detection problem (as shown in Figure 2) where the size of the matrix is a small constant, independent of the number of edges or the graph size. これにより、密度部分グラフ検出は密度の低い部分行列検出問題に変換することができる(図2に示すように、行列のサイズは、エッジの数やグラフのサイズによらず、小さな定数である。 0.71
3 3 0.85
英語(論文から抽出)日本語訳スコア
Figure 1: (a) Original CMS (b) Higher-order CMS 図1:(a)オリジナルCMS(b)高次CMS 0.79
Figure 2: (a) Dense subgraph in the original graph between source nodes s1, s2, and destination nodes d1, d2, d3 is transformed to a (b) Dense submatrix between rows r1, r2, and columns c1, c2, c3 in the H-CMS. 図2:(a)ソースノードs1,s2と宛先ノードd1,d2,d3との間の元のグラフにおけるDenseサブグラフを、列r1,r2と列c1,c2,c3との間の(b)Denseサブマトリックスに変換する。 0.77
Frequently used symbols are discussed in Table 2, and we leverage the subgraph density measure discussed in [49] to define the submatrix (Sx, Tx) density. 頻繁に使われる記号は表2で議論され、[49]で議論される部分グラフ密度測度を利用して部分行列 (sx, tx) の密度を定義する。 0.71
Definition 1. Given matrix M, density of a submatrix of M represented by Sx ⊆ S and Tx ⊆ T , is: 定義1。 行列 M が与えられたとき、Sx > S と Tx > T で表される M の部分行列の密度は次のようになる。 0.66
(cid:80) D(M, Sx, Tx) = (cid:80) D(M, Sx, Tx) = 0.82
s∈Sx (cid:80) (cid:112)|Sx||Tx| s・Sx (cid:80) (cid:112)|sx||tx| 0.45
t∈Tx M[s][t] t~Tx M[s][t] 0.59
(1) 5 Edge Anomalies (1) 5つのエッジ異常 0.70
In this section, using the H-CMS data structure, we propose ANOEDGE-G and ANOEDGE-L to detect edge anomalies by checking whether the received edge when mapped to a sketch matrix element is part of a dense submatrix. 本稿では、h-cmsデータ構造を用いて、スケッチマトリクス要素にマッピングされた際に受信したエッジが高密度サブマトリックスの一部であるかどうかをチェックすることにより、エッジ異常を検出するためのanoedge-gとanoedge-lを提案する。 0.58
ANOEDGE-G finds a Global dense submatrix and performs well in practice while ANOEDGE-L maintains and updates a Local dense submatrix around the matrix element and therefore has better time complexity. ANOEDGE-GはGlobal dense submatrixを見つけ、実際はよく機能し、ANOEDGE-Lは行列要素の周りの局所的な高密度サブマトリクスを維持し更新する。 0.75
5.1 ANOEDGE-G 5.1 Anoedge-G 0.42
ANOEDGE-G, as described in Algorithm 1, maintains a temporally decaying H-CMS, i.e. ANOEDGE-Gはアルゴリズム1で説明されているように、時間的に減衰するH-CMSを維持している。 0.51
whenever 1 unit of time passes, we multiply all the H-CMS counts by a fixed factor α (lines 2,4). 1 つの時間単位が経過すると、すべての H-CMS を固定係数 α で乗算する(ライン2,4)。 0.79
This decay 4 (a)(b)11101010000100 00(a)(b) この崩壊は 4 (a)(b)11101010000100 00(a)(b) 0.79
英語(論文から抽出)日本語訳スコア
Symbol nr nb h(u) M シンボル nr nb h(u) M 0.79
M[i][j] S Scur Srem M[i][j] S Scur Srem 0.81
T Tcur Trem [z] T Tcur Trem [z] 0.85
D(M, Sx, Tx) E(M, Sx, Tx) R(M, u, Tx) C(M, Sx, v) D(M, Sx, Tx) E(M, Sx, Tx) R(M, u, Tx) C(M, Sx, v) 0.85
L(M, u, v, Sx, Tx) L(M, u, v, Sx, Tx) 0.85
dmax Table 2: Table of symbols. dmax 表2:シンボルの表。 0.79
Definition number of hash functions number of buckets hash function u → [0, nb) a square matrix of dimensions nb × nb element at row index i and column index j set of all row indices set of current submatrix row indices set of remaining row indices i.e. ハッシュ関数の数の定義 ハッシュ関数 u → [0, nb) 行インデックス i における次元 nb × nb 要素の平方行列と、残行インデックス i の現在の部分行列行インデックス集合のすべての行インデックス集合の列インデックス j である。
訳抜け防止モード: ハッシュ関数の定義数 バケツの数 ハッシュ関数 u → [ 0, nb ) 行指数 i における次元 nb × nb 要素の平方行列 また、列インデックスjセットは、現在のサブマトリックス行インデックスのすべての行インデックスのセットであり、残りの行インデックスのセットである。
0.83
indices not part of current submatrix set of all column indices set of current submatrix column indices set of remaining column indices i.e. indices not part of current submatrix set of all column indices set of current submatrix column indices set of remaining column indices i.e. (英語) 0.96
indices not part of current submatrix set of all integers in the range [1, z], i.e., {1, 2, ..., z} density of submatrix (Sx, Tx) sum of elements of submatrix (Sx, Tx) submatrix row-sum i.e. Indices not part of current submatrix set of all integers in the range [1, z], i., {1, 2, ..., z} density of submatrix (Sx, Tx) sum of element of submatrix (Sx, Tx) submatrix row-sum i.e. 0.87
sum of elements of submatrix ({u}, Tx) submatrix column-sum i.e. submatrix ({u}, Tx) submatrix column-sum の要素の和。 0.80
sum of elements of submatrix (Sx, {v}) likelihood of index (u, v) w.r.t. 部分行列 (Sx, {v}) の要素の和 (u, v) w.r.t である。 0.75
submatrix (Sx, Tx) maximum reported submatrix density submatrix (sx, tx) 最大報告サブマトリクス密度 0.86
simulates the gradual ‘forgetting’ of older and hence more outdated information. の段階的にシミュレートし、したがって時代遅れの情報をより古いものにします。 0.49
When an edge (u, v) arrives, u, v are mapped to matrix indices h(u), h(v) respectively for each hash function h, and the corresponding H-CMS counts are updated (line 5). エッジ(u,v)が到着すると、それぞれハッシュ関数hに対する行列指標h(u,h(v)に、エッジ(u,v)がマッピングされ、対応するH−CMSカウントが更新される(ライン5)。 0.70
EDGE-SUBMATRIX-DENSI TY procedure (described below) is then called to compute the density of a dense submatrix around (h(u), h(v)). edge-submatrix-densi tyプロシージャ(後述)は、(h(u), h(v)) の周りの密な部分行列の密度を計算するために呼ばれる。 0.69
Density is reported as the anomaly score for the edge; a larger density implies that the edge is more likely to be anomalous. 密度はエッジの異常スコアとして報告される; 密度が大きいことは、エッジが異常である可能性が高いことを意味する。 0.73
EDGE-SUBMATRIX-DENSI TY procedure calculates the density of a dense submatrix around a given index (u, v). edge-submatrix-densi tyプロシージャは、与えられたインデックス (u, v) の周りの高密度部分行列の密度を計算する。 0.59
A 1 × 1 submatrix represented by Scur and Tcur, is initialized with row-index u and column index v (line 9). scur と tcur で表される 1 × 1 のサブ行列は、行インデックス u と列インデックス v (行 9) で初期化される。 0.79
The submatrix is iteratively expanded by greedily selecting a row up from Srem (or a column vp from Trem) that obtains the maximum row (or column) sum with the current submatrix (lines 14,16). サブマトリクスは、現在のサブマトリクスと最大行(またはカラム)の和を求めるsrem(またはtremからカラムvp)から行を欲して選択することで反復的に拡張される(ライン14,16)。 0.75
This selected row up (or column vp) is removed from Srem (or Trem), and added to Scur (or Tcur) (lines 15,17). この選択された行アップ(またはカラムvp)はsrem(またはtrm)から削除され、scur(またはtcr)に追加される(ライン15,17)。 0.67
The process is repeated until both Srem and Trem are empty (line 11). このプロセスは、sremとtremの両方が空になるまで繰り返される(ライン11)。 0.66
Density of the current submatrix is computed at each iteration of the submatrix expansion process and the maximum over all greedily formed submatrix densities is returned (line 18). サブマトリックス展開プロセスの各イテレーションで電流サブマトリックスの密度を計算し、欲張りに形成されたすべてのサブマトリックス密度を最大に戻す(ライン18)。 0.87
Proposition 1. (Proof in Appendix D.1) Time complexity of Algorithm 1 is O(|E | ∗ nr ∗ n2 Proposition 2. 命題1。 (付録 d.1) アルゴリズム 1 の時間複雑性は o(|e | ∗ nr ∗ n2 命題 2 である。 0.66
(Proof in Appendix D.1) Memory complexity of Algorithm 1 is O(nr ∗ n2 b). (Appendix D.1) アルゴリズム 1 のメモリ複雑性は O(nr ∗ n2 b) である。 0.88
b) 1. 5.2 ANOEDGE-L b) 1。 5.2 Anoedge-L 0.60
Inspired by Definition 1, we define the likelihood measure of a matrix index (u, v) with respect to a submatrix (Sx, Tx), as the sum of the elements of submatrix (Sx, Tx) that either share row with index v or column with index u divided by the total number of such elements. 定義 1 から着想を得た行列指数 (u, v) の準行列(Sx, Tx) に対する可能性測度を、指数 v で行を共有する部分行列 (Sx, Tx) の要素の和として定義する。
訳抜け防止モード: 定義1に触発された。 行列指数の 可能性尺度を定義します (u,v) 部分行列(Sx, Tx )に関して、部分行列(Sx, Tx )の要素の和として インデックス v または カラムで共有する 指数 u をそのような要素の総数で割る。
0.73
Definition 2. Given matrix M, likelihood of an index (u, v) with respect to a submatrix represented by Sx ⊆ S and Tx ⊆ T , is: 定義2。 行列 M が与えられたとき、Sx > S および Tx > T で表される部分行列に対する指数 (u, v) の確率は、次の通りである。 0.69
L(M, u, v, Sx, Tx) = L(M, u, v, Sx, Tx) = 0.85
(cid:80) (s,t) ∈ Sx×v ∪ u×Tx (cid:80) (s,t) ∈ Sx×v > u×Tx 0.80
|Sx × v ∪ u × Tx| |Sx × v > u × Tx| 0.92
M[s][t] (2) M[s][t] (2) 0.80
ANOEDGE-L, as described in Algorithm 2, maintains a temporally decaying H-CMS to store the edge counts. ANOEDGE-Lはアルゴリズム2で説明されているように、エッジ数を保存するために時間的に減衰するH-CMSを維持している。 0.48
We also initialize a mutable submatrix of size 1 × 1 with a random element, and represent また、ランダムな要素を持つサイズ 1 × 1 の可変部分行列を初期化し、表現する。 0.68
1This is for processing all edges; the time per edge is constant. 1 これはすべてのエッジを処理するためのもので、エッジ毎の時間は一定です。 0.57
5 5 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 1: ANOEDGE-G : Streaming Anomaly Edge Scoring Input: Stream E of edges over time Output: Anomaly score per edge アルゴリズム1:ANOEDGE-G : Streaming Anomaly Edge Scoring Input: Stream E of edges Over Time Output: Anomaly score per edge 0.89
Initialize H-CMS matrix M for edge count while new edge e = (u, v, w, t) ∈ E is received do Temporal decay H-CMS with timestamp change Update H-CMS matrix M for new edge (u, v) with value w output score(e) ← EDGE-SUBMATRIX-DENSI TY(M, h(u), h(v)) 新しいエッジ e = (u, v, w, t) ∈ E が受信される一方で、エッジ数に対する H-CMS 行列 M を初期化する タイムスタンプ変更を伴うテンポラル崩壊 H-CMS 行列 M を新しいエッジ (u, v) に対して更新する 値 w 出力スコア(e) = EDGE-SUBMATRIX-DENSI TY(M, h(u, h(u), h(v))) 0.79
1 Procedure AN OED G E-G(E ) 2 3 4 5 6 7 Procedure ED G E-SU B M A T R I X-DE N S I T Y(M, u, v) 8 9 10 11 12 13 14 1 プロシージャAN OED G E-G(E ) 2 3 4 5 6 7 プロシージャED G E-SU B M A T R I X-DE N S I T Y(M, u, v) 8 9 10 11 12 13 14 0.86
up ← argmaxsp∈Srem R(M, sp, Tcur) vp ← argmaxtp∈Trem C(M, Scur, tp) if R(M, up, Tcur) > C(M, Scur, vp) then は R(M, up, Tcur) > C(M, Scur, vp) であるなら、R(M, up, Tcur) > C(M, Scur, vp) である。 0.67
S ← [nb]; T ← [nb]; Scur ← {u}; Tcur ← {v}; Srem ← S/{u}; Trem ← T /{v} dmax ← D(M, Scur, Tcur) while Srem (cid:54)= ∅ ∨ Trem (cid:54)= ∅ do S > [nb]; T > [nb]; Scur > {u}; Tcur > {v}; Srem > S/{u}; Trem > T /{v} dmax > D(M, Scur, Tcur) に対し、Srem (cid:54) = . > Trem (cid:54) = . > > Trem (cid:54) = . do である。 0.77
// submatrix max row-sum index // submatrix max column-sum index submatrix max row-sum index // submatrix max column-sum index 0.83
// decay count // update count delete decay count // update count"に完全一致する 0.47
// H-CMS data structure H-CMSデータ構造 0.83
Scur ← Scur ∪ {up}; Srem ← Srem/{up} Tcur ← Tcur ∪ {vp}; Trem ← Trem/{vp} Scur > Scur > Scur > {up}; Srem > Srem/{up} Tcur > Tcur > {vp}; Trem > Trem/{vp} 0.66
else dmax ← max(dmax,D(M, Scur, Tcur)) その他の dmax は max(dmax, d(m, scur, tcur) である。 0.86
15 16 17 18 15 16 17 18 0.85
return dmax // dense submatrix density dmaxを返せ //密度サブマトリクス密度 0.77
it as (Scur, Tcur). それは (scur, tcur) である。 0.77
As we process edges, we greedily update (Scur, Tcur) to maintain it as a dense submatrix. エッジを処理すると、(scur, tcur) を更新して、密集したサブマトリックスとして維持します。 0.64
When an edge arrives, H-CMS counts are first updated, and the received edge is then used to check whether to expand the current submatrix (line 7). エッジが到着すると、H-CMSカウントが最初に更新され、受信されたエッジを使用して、現在のサブマトリックスを拡張するかどうかをチェックする(ライン7)。 0.63
If the submatrix density increases upon the addition of the row (or column), then the row-index h(u) (or column-index h(v)) is added to the current submatrix, (Scur, Tcur). 列(または列)の追加によってサブマトリックス密度が増加すると、行インデックスh(u)(またはカラムインデックスh(v))が現在のサブマトリックス(scur, tcur)に追加される。 0.82
To remove the row(s) and column(s) decayed over time, the process iteratively selects the row (or column) with the minimum row-sum (or column-sum) until removing it increases the current submatrix density. 時間とともに崩壊した行と列を除去するために、プロセスは最小の行サム(または列サム)で行(または列)を反復的に選択し、除去すると電流サブ行列密度が増加する。 0.81
This ensures that the current submatrix is as condensed as possible (line 9). これにより、現在の部分行列は可能な限り凝縮される(ライン9)。 0.65
As defined in Definition 2, ANOEDGE-L computes the likelihood score of the edge with respect to (Scur, Tcur) (line 10). 定義2で定義されているように、ANOEDGE-Lは(Scur,Tcur)に対してエッジの確率スコアを算出する(ライン10)。 0.66
A higher likelihood measure implies that the edge is more likely to be anomalous. 高い可能性測度は、エッジが異常である可能性が高いことを意味する。 0.64
Algorithm 2: ANOEDGE-L : Streaming Anomaly Edge Scoring Input: Stream E of edges over time Output: Anomaly score per edge アルゴリズム2: ANOEDGE-L : Streaming Anomaly Edge Scoring Input: Stream E of edges Over Time Output: Anomaly score per edge 0.89
1 Procedure AN OED G E-L(E ) 2 3 4 5 6 7 8 9 10 1 手順 AN OED G E-L(E ) 2 3 4 6 6 7 8 9 10 0.91
Initialize H-CMS matrix M for edges count Initialize a randomly picked 1 × 1 submatrix (Scur, Tcur) while new edge e = (u, v, w, t) ∈ E is received do Temporal decay H-CMS with timestamp change Update H-CMS matrix M for new edge (u, v) with value w (cid:46) Check and Update Submatrix: Expand (Scur, Tcur) Condense (Scur, Tcur) output score(e) ← L(M, h(u), h(v), Scur, Tcur) エッジをカウントする H-CMS 行列 M の初期化 ランダムに選択された 1 × 1 サブマトリクス (Scur, Tcur) を初期化する一方で、新しいエッジ e = (u, v, w, t) ∈ E はタイムスタンプ変更を伴うテンポラル崩壊 H-CMS を受信する 更新 H-CMS 行列 M for new edge (u, v) with value w (cid:46) Check and Update Submatrix: Expand (Scur, Tcur) Condense (Scur, Tcur) output score(e) > L(M, h(u, h(u), h(v), Scur, Tcur) 0.86
// H-CMS data structure // mutable submatrix H-CMS データ構造 //muttable submatrix 0.86
// decay count // update Count derupt count // update Count 0.68
// expand submatrix // condense submatrix // from Definition 2 expand submatrix // condense submatrix // from definition 2 0.88
Proposition 3. (Proof in Appendix D.2) Time complexity of Algorithm 2 is O(nr ∗ n2 Proposition 4. 命題3。 ( Appendix D.2) アルゴリズム2の時間複雑性は O(nr ∗ n2 命題 4 である。 0.71
(Proof in Appendix D.2) Memory complexity of Algorithm 2 is O(nr ∗ n2 b). (Appendix D.2) アルゴリズム2のメモリ複雑性は O(nr ∗ n2 b) である。 0.87
b +|E |∗ nr ∗ nb). b +|E |∗ nr ∗ nb)。 0.86
6 6 0.85
英語(論文から抽出)日本語訳スコア
6 Graph Anomalies We now propose ANOGRAPH and ANOGRAPH-K to detect graph anomalies by first mapping the graph to a higher-order sketch, and then checking for a dense submatrix. 6つのグラフ異常 我々はANOGRAPHとANOGRAPH-Kを提案し、まずグラフを高階のスケッチにマッピングし、次に密度の高いサブ行列をチェックする。 0.66
These are the first streaming algorithms that make use of dense subgraph search to detect graph anomalies in constant memory and time. これらは、密度の高いサブグラフ探索を使用して、一定のメモリと時間のグラフ異常を検出する最初のストリーミングアルゴリズムである。 0.72
ANOGRAPH greedily finds a dense submatrix with a 2-approximation guarantee on the density measure. ANOGRAPH は密度測定で 2-近似を保証するような密度のサブ行列を欲しがる。 0.67
ANOGRAPH-K leverages EDGE-SUBMATRIX-DENSI TY from Algorithm 1 to greedily find a dense submatrix around K strategically picked matrix elements performing equally well in practice. ANOGRAPH-Kはアルゴリズム1からEDGE-SubMATRIX-DENSI TYを利用して、K の戦略選択行列要素の周囲に密接な部分行列を優しく見つける。 0.68
6.1 ANOGRAPH 6.1 ANOGRAPH 0.71
ANOGRAPH, as described in Algorithm 3, maintains an H-CMS to store the edge counts that are reset whenever a new graph arrives. ANOGRAPHはアルゴリズム3で説明されているように、新しいグラフが到着するたびにリセットされるエッジ数を格納するH-CMSを維持している。 0.67
The edges are first processed to update the H-CMS counts. エッジは最初に処理され、H-CMSカウントを更新する。 0.61
ANOGRAPH-DENSITY procedure (described below) is then called to find the dense submatrix. ANOGRAPH-DENSITY法(後述)は、密度の高い部分行列を見つけるために呼ばれる。 0.62
ANOGRAPH reports anomaly score as the density of the detected (dense) submatrix; a larger density implies that the graph is more likely to be anomalous. ANOGRAPHは、異常スコアを検出された(密度)サブマトリクスの密度として報告している。
訳抜け防止モード: ANOGRAPHは異常スコアを検出された(高密度)サブマトリクスの密度として報告している より大きな密度は、グラフが異常になりやすいことを意味する。
0.77
ANOGRAPH-DENSITY procedure computes the density of a dense submatrix of matrix M. The current dense submatrix is initialised as matrix M and then the row (or column) from the current submatrix with minimum row (or column) sum is greedily removed. ANOGRAPH-DENSITY 法は行列 M の高密度部分行列の密度を計算する。現在の高密度部分行列は行列 M として初期化され、最小の行(または列)の和を持つ電流サブ行列からの行(または列)は強引に除去される。
訳抜け防止モード: ANOGRAPH - DENSITY procedure computes the density of a dense submatrix of matrix M. The current dense submatrix is initialized as matrix M. そして、最小の行(または列)の和を持つ現在のサブマトリクスからの行(または列)は、優しく取り除かれる。
0.88
This process is repeated until Scur and Tcur are empty (line 12). この過程は Scur と Tcur が空になるまで繰り返される(ライン12)。 0.86
The density of the current submatrix is computed at each iteration of the submatrix expansion process and the maximum over all densities is returned (line 19). 電流サブマトリクスの密度は、サブマトリクス展開工程の各イテレーションで計算され、すべての密度に対する最大値が返される(ライン19)。 0.84
Algorithm 3 is a special case of finding the densest subgraph in a directed graph problem [49] where the directed graph is represented as an adjacency matrix and detecting the densest subgraph essentially means detecting dense submatrix. アルゴリズム3は、有向グラフを隣接行列として表現した有向グラフ問題[49]における最も密な部分グラフを見つけ、最も密な部分グラフを検出する特別なケースである。 0.67
We now provide a guarantee on the density measure. 我々は現在、密度測度の保証を提供する。 0.83
Theorem 2. (Proof in Appendix E.1) Algorithm 3 achieves a 2-approximation guarantee for the densest submatrix problem. 定理2。 (付録e.1)アルゴリズム3は、最も密度の高い部分行列問題に対する2近似保証を達成する。 0.58
Algorithm 3: ANOGRAPH: Streaming Anomaly Graph Scoring Input: Stream G of edges over time Output: Anomaly score per graph アルゴリズム3: ANOGRAPH: Streaming Anomaly Graph Scoring Input: Stream G of edges Over Time Output: Anomaly score per graph 0.82
1 Procedure AN OGR A P H(G ) 2 3 4 5 6 1 プロシージャ AN OGR A P H(G ) 2 3 4 5 6 0.80
Initialize H-CMS matrix M for graph edges count while new graph G ∈ G is received do Reset H-CMS matrix M for graph G for edge e = (u, v, w, t) ∈ G do output score(G) ← ANOGRAPH-DENSITY(M) グラフエッジに対する H-CMS 行列 M を初期化し、新しいグラフ G ∈ G を受信し、エッジ e = (u, v, w, t) ∈ G をグラフ G にリセットする H-CMS 行列 M は出力スコア(G) = ANOGRAPH-DENSITY(M) を出力する。 0.84
Update H-CMS matrix M for edge (u, v) with value w 値wのエッジ(u, v)に対するH-CMS行列Mの更新 0.83
// H-CMS data structure H-CMSデータ構造 0.83
// reset count // update count //リセット数 // 更新数 0.82
// anomaly score Scur ← [n]; Tcur ← [n] dmax ← D(M, Scur, Tcur) while Scur (cid:54)= ∅ ∨ Tcur (cid:54)= ∅ do //異常スコア Scur (cid:54)= s , Tcur (cid:54)= s , Tcur (cid:54)= s , D (M, Scur, Tcur) である。 0.72
7 8 Procedure AN OGR A P H-DE N S I T Y(M) 9 10 11 12 13 14 15 7 8 手順 AN OGR A P H-DE N S I T Y(M) 9 10 11 12 13 14 15 0.88
up ← argminsp∈Scur R(M, sp, Tcur) vp ← argmintp∈Tcur C(M, Scur, tp) if R(M, up, Tcur) < C(M, Scur, vp) then c(m, scur, tp) if r(m, up, tcur) < c(m, scur, vp) then if r(m, up, tcur) < c(m, scur, vp)
訳抜け防止モード: Scur R(M, sp, Tcur ) vp > argmintp~Tcur C(M, Tcur ) Scur, tp ) if R(M, up, Tcur ) < C(M,) すると、scur , vp )
0.75
Scur ← Scur/{up} Tcur ← Tcur/{vp} Scur/Scur/{up} Tcur/Tcur/{vp} 0.78
else dmax ← max(dmax,D(M, Scur, Tcur)) その他の dmax は max(dmax, d(m, scur, tcur) である。 0.86
16 17 18 19 16 17 18 19 0.85
// initialize to size of M // M のサイズに初期化 0.85
// submatrix min row-sum index // submatrix min column-sum index submatrix min row-sum index // submatrix min column-sum index 0.83
// remove row // remove column // 行を削除 //削除列 0.75
return dmax // dense submatrix density dmaxを返せ //密度サブマトリクス密度 0.77
b +|E |∗ nr). b +|E |∗ nr)。 0.84
Proposition 5. (Proof in Appendix E.1) Time complexity of Algorithm 3 is O(|G|∗ nr ∗ n2 Proposition 6. 命題5。 (Appendix E.1) アルゴリズム3の時間複雑性は O(|G|∗ nr ∗ n2 である。 0.69
(Proof in Appendix E.1) Memory complexity of Algorithm 3 is O(nr ∗ n2 b). (Appendix E.1) アルゴリズム3のメモリ複雑性は O(nr ∗ n2 b) である。 0.86
7 7 0.85
英語(論文から抽出)日本語訳スコア
6.2 ANOGRAPH-K 6.2 ANOGRAPH-K 0.50
Similar to ANOGRAPH, ANOGRAPH-K maintains an H-CMS which is reset whenever a new graph arrives. ANOGRAPHと同様に、ANOGRAPH-KはH-CMSを維持し、新しいグラフが到着するたびにリセットされる。 0.63
It uses the ANOGRAPH-K-DENSITY procedure (described below) to find the dense submatrix. ANOGRAPH-K-DENSITY法(後述)を用いて、密度の高いサブマトリクスを見つける。 0.66
ANOGRAPH-K is summarised in Algorithm 4. ANOGRAPH-Kはアルゴリズム4で要約される。 0.68
ANOGRAPH-K-DENSITY computes the density of a dense submatrix of matrix M. The intuition comes from the heuristic that the matrix elements with a higher value are more likely to be part of a dense submatrix. ANOGRAPH-K-DENSITY は行列 M の高密度部分行列の密度を計算する。
訳抜け防止モード: ANOGRAPH - K - DENSITY は行列 M の高密度部分行列の密度を計算する。 高い値のマトリックス要素は、密度の高いサブマトリクスの一部である可能性が高い。
0.78
Hence, the approach considers K largest elements of the matrix M and calls EDGE-SUBMATRIX-DENSI TY from Algorithm 1 to get the dense submatrix around each of those elements (line 14). したがって、この手法は行列 M の K 個の最大要素を考慮し、アルゴリズム 1 から EDGE-SubMATRIX-DENSI TY と呼び、これらの要素の周囲に密度のある部分行列を得る(線14)。 0.70
The maximum density over the considered K dense submatrices is returned. 考慮されたK密度サブマトリクスの最大密度が返される。 0.77
Algorithm 4: ANOGRAPH-K: Streaming Anomaly Graph Scoring Input: Stream G of edges over time Output: Anomaly score per graph 1 Procedure AN OGR A P H-K(G , K) 2 3 4 5 6 アルゴリズム4: ANOGRAPH-K: Streaming Anomaly Graph Scoring Input: Stream G of edges Over Time Output: Anomaly score per graph 1 procedure AN OGR A P H-K(G , K) 2 3 4 5 6 0.91
Initialize H-CMS matrix M for graph edges count while new graph G ∈ G is received do Reset H-CMS matrix M for graph G for edge e = (u, v, w, t) ∈ G do output score(G) ← ANOGRAPH-K-DENSITY(M , K) グラフ辺数に対するh-cms行列 m を初期化し、新しいグラフ g ∈ g を受信し、辺 e = (u, v, w, t) ∈ g のグラフ g に対するリセット h-cms 行列 m を出力スコア(g) ; anograph-k-density(m , k) で表す。
訳抜け防止モード: グラフエッジに対する初期化H-CMS行列M 新しいグラフ G ∈ G が受信される do Reset H - CMS matrix M for graph G for edge e = ( u, v, w, t ) ∈ G do output score(G ) = ANOGRAPH - K - DENSITY(M,K )
0.95
Update H-CMS matrix M for edge (u, v) with value w 値wのエッジ(u, v)に対するH-CMS行列Mの更新 0.83
7 8 Procedure AN OGR A P H-K-Density(M, K) 9 10 11 12 13 14 7 8 手順 AN OGR A P H-K-Density(M, K) 9 10 11 12 13 14 0.95
B ← [n] × [n] dmax ← 0 for j ← 1 ... K do B > [n] × [n] dmax × 0 for j > 1 ... K do 0.61
up, vp ← argmax(sp,tp)∈B M[sp][tp] dmax ← max(dmax, EDGE-SUBMATRIX-DENSI TY(M, up, vp)) B ← B/{(up, vp)} 上、 vp は argmax(sp,tp)~B M[sp][tp] dmax は max(dmax, EDGE-SUBMATRIX-DENSI TY(M, up, vp)) B は B/{(up, vp)} 0.87
// H-CMS data structure H-CMSデータ構造 0.83
// reset count // update count //リセット数 // 更新数 0.82
// anomaly score // set of all indices //異常スコア //全インデックスのセット 0.87
// pick the max element // max 要素を選択します。 0.62
// remove max element index //max要素インデックスを削除する 0.70
15 return dmax 15 dmaxを返せ 0.83
// dense submatrix density //密度サブマトリクス密度 0.73
Proposition 7. (Proof in Appendix E.2) Time complexity of Algorithm 4 is O(|G| ∗ K ∗ nr ∗ n2 |E | ∗ nr). プロポーズ7。 (Appendix E.2) アルゴリズム 4 の時間複雑性は O(|G| ∗ K ∗ nr ∗ n2 |E | ∗ nr) である。 0.68
Proposition 8. (Proof in Appendix E.2) Memory complexity of Algorithm 4 is O(nr ∗ n2 b). 命題8。 (Appendix E.2) アルゴリズム4のメモリ複雑性は O(nr ∗ n2 b) である。 0.68
b + 7 Experiments In this section, we evaluate the performance of our approaches as compared to all baselines discussed in Table 1. b + 実験7 本稿では,表1で論じているすべてのベースラインと比較して,我々のアプローチの性能を評価する。 0.80
We use four real-world datasets: DARPA [50] and ISCX-IDS2012 [51] are popular datasets for graph anomaly detection; [52] surveys more than 30 datasets and recommends to use the newer CIC-IDS2018 and CIC-DDoS2019 datasets [53, 54]. DARPA [50] と ISCX-IDS2012 [51] はグラフ異常検出の一般的なデータセットです。 [52] は30以上のデータセットを調査し、より新しい CIC-IDS2018 と CIC-DDoS2019 データセット [53,54] を使用することを推奨します。 0.72
Dataset details are discussed in Appendix B. Hyperparameters for the baselines are provided in Appendix H. Appendix F describes the experimental setup and results with some additional parameters are shown in Appendix G. All edge (or graph)-based methods output an anomaly score per edge (or graph), a higher score implying more anomalousness. Appendix B ではデータセットの詳細が議論されている。 ベースラインのハイパーパラメータは Appendix H では提供されている。 Appendix F では実験的な設定を記述し、追加のパラメータを持つ結果が Appendix G では示されている。
訳抜け防止モード: Appendix H ではベースラインのハイパーパラメータが提供され、Appendix F では実験的なセットアップが説明され、追加のパラメータが Appendix G. All edge で示されている。 あるいはグラフ)ベースのメソッドは、エッジ毎の異常スコア(またはグラフ)を出力する。 より高いスコアは より異常を示唆します
0.78
Similar to baseline papers, we report the Area under the ROC curve (AUC) and the running time. ベースライン論文と同様に,roc曲線(auc)下の領域と実行時間について報告する。 0.61
Unless explicitly specified, all experiments including those on the baselines are repeated 5 times and the mean is reported. 明示的に指定しない限り、ベースライン上の実験を含む全ての実験を5回繰り返し、平均を報告する。 0.73
We aim to answer the following questions: 私たちは以下の質問に答えようとしている。 0.59
Q1. Edge Anomalies: How accurately do ANOEDGE-G and ANOEDGE-L detect edge Q1。 エッジ異常:ANOEDGE-GおよびANOEDGE-L検出エッジの精度 0.78
anomalies compared to baselines? ベースラインと比較して異常? 0.65
Are they fast and scalable? 高速でスケーラブルか? 0.41
Q2. Graph Anomalies: How accurately do ANOGRAPH and ANOGRAPH-K detect graph Q2。 グラフ異常: ANOGRAPH と ANOGRAPH-K の精度 0.72
anomalies i.e. anomalous graph snapshots? 異常 i.e. 異常なグラフスナップショット? 0.68
Are they fast and scalable? 高速でスケーラブルか? 0.41
8 8 0.85
英語(論文から抽出)日本語訳スコア
7.1 Edge Anomalies Accuracy: Table 3 shows the AUC of edge anomaly detection baselines, ANOEDGE-G, and ANOEDGE-L. We report a single value for DENSESTREAM and PENminer because these are non-randomized methods. 7.1 エッジ異常 精度: 表3は, エッジ異常検出ベースライン, ANOEDGE-G, ANOEDGE-LのAUCを示す。
訳抜け防止モード: 7.1 エッジ異常 精度 : 表3は、エッジ異常検出ベースラインのAUCを示す。 ANOEDGE - G と ANOEDGE - L は非ランダム化メソッドであるため、DENSESTREAM と PENminer の単一値を報告する。
0.67
PENminer is unable to finish on the large CIC-DDoS2019 within 24 hours; thus, that result is not reported. PENminerは24時間以内に大規模なCIC-DDoS2019を終えることができないため、その結果は報告されていない。 0.65
SEDANSPOT uses personalised PageRank to detect anomalies and is not always able to detect anomalous edges occurring in dense block patterns while PENminer is unable to detect structural anomalies. SEDANSPOTはパーソナライズされたPageRankを使用して異常を検知し、PENminerが構造的異常を検出できない間、密ブロックパターンで発生する異常なエッジを常に検出できるわけではない。
訳抜け防止モード: SEDANSPOTはパーソナライズされたPageRankを使って異常を検知する 密集したブロックパターンで発生する異常なエッジを検出する PENminerは構造異常を検出することができない。
0.77
Among the baselines, MIDAS-R is most accurate, however, it performs worse when there is a large number of timestamps as in ISCX-IDS2012. ベースラインの中では、MIDAS-Rが最も正確であるが、ISCX-IDS2012のように、多数のタイムスタンプが存在する場合、さらに悪化する。 0.60
Note that ANOEDGE-G and ANOEDGE-L outperform all baselines on all datasets. ANOEDGE-GとANOEDGE-Lはすべてのデータセットのベースラインを上回ります。 0.60
Table 3: AUC and Running Time when detecting edge anomalies. 表3: エッジ異常を検出する際のAUCとランニング時間。 0.73
Averaged over 5 runs. Dataset 平均5回に及んだ。 データセット 0.60
DARPA ISCX-IDS2012 DARPA ISCX-IDS2012 0.66
CIC-IDS2018 CIC-IDS2018 0.47
CIC-DDoS2019 CIC-DDoS2019 0.47
DENSESTREAM 0.532 57.7s 0.551 138.6s 0.756 3.3 hours 0.263 265.6s DENSESTREAM 0.532 57.7s 0.551 138.6s 0.756 3.3 hours 0.263 265.6s 0.43
SEDANSPOT 0.647 ± 0.006 129.1s 0.581 ± 0.001 19.5s 0.325 ± 0.037 209.6s 0.567 ± 0.004 697.6s SEDANSPOT 0.647 ± 0.006 129.1s 0.581 ± 0.001 19.5s 0.325 ± 0.037 209.6s 0.567 ± 0.004 697.6s 0.46
MIDAS-R PENminer 0.872 5.21 hrs 0.530 1.3 hrs 0.821 10 hrs MIDAS-R PENminer 0.872 5.21 hrs 0.530 1.3 hrs 0.821 10 hrs 0.59
0.953 ± 0.002 1.4s 0.820 ± 0.050 5.3s 0.919 ± 0.019 1.1s 0.983 ± 0.003 2.2s 0.953 ± 0.002 1.4s 0.820 ± 0.050 5.3s 0.919 ± 0.019 1.1s 0.983 ± 0.003 2.2s 0.44
> 24 hrs F-FADE 0.919 ± 0.005 317.8s 0.533 ± 0.020 137.4s 0.607 ± 0.001 279.7s — 0.717 ± 0.041 18.7s >24時間。 F-FADE 0.919 ± 0.005 317.8s 0.533 ± 0.020 137.4s 0.607 ± 0.001 279.7s – 0.717 ± 0.041 18.7s 0.62
ANOEDGE-G 0.970 ± 0.001 28.7s 0.954 ± 0.000 7.8s 0.963 ± 0.014 58.4s 0.997 ± 0.001 123.3s ANOEDGE-G 0.970 ± 0.001 28.7s 0.954 ± 0.000 7.8s 0.963 ± 0.014 58.4s 0.997 ± 0.001 123.3s 0.44
ANOEDGE-L 0.964 ± 0.001 6.1s 0.957 ± 0.003 0.7s 0.927 ± 0.035 10.2s 0.998 ± 0.001 17.8s ANOEDGE-L 0.964 ± 0.001 6.1s 0.957 ± 0.003 0.7s 0.927 ± 0.035 10.2s 0.998 ± 0.001 17.8s 0.44
Running Time: Table 3 shows the running time (excluding I/O) and real-time performance of ANOEDGE-G and ANOEDGE-L. ランニング時間:テーブル3は、ANOEDGE-GとANOEDGE-Lのランニング時間(I/Oを除く)とリアルタイムのパフォーマンスを示す。 0.65
Since ANOEDGE-L maintains a local dense submatrix, it is faster than ANOEDGE-G. DENSESTREAM maintains dense blocks incrementally for every coming tuple and updates dense subtensors when it meets an updating condition, limiting the detection speed. ANOEDGE-Lは局所的な高密度部分行列を保持するため、ANOEDGE-Gよりも高速である。
訳抜け防止モード: ANOEDGE 以降、L は局所的な高密度部分行列を維持している。 ANOEDGEより速いです -G.DENSESTREAMは来るべきタプル毎に徐々に密度の高いブロックを維持 密度の高い増分器を更新すると 更新条件を満たし 検出速度を制限します
0.62
SEDANSPOT requires several subprocesses (hashing, random-walking, reordering, sampling, etc), PENminer and F-FADE need to actively extract patterns for every graph update, resulting in the large computation time. SEDANSPOTはいくつかのサブプロセス(ハッシュ、ランダムウォーキング、リオーダー、サンプリングなど)を必要とし、PENminerとF-FADEはグラフ更新毎にパターンを積極的に抽出する必要がある。 0.62
When there is a large number of timestamps like in ISCX-IDS2012, MIDAS-R performs slower than ANOEDGE-L which is the fastest. ISCX-IDS2012のような多くのタイムスタンプがある場合、MIDAS-Rは最速のANOEDGE-Lよりも遅い。 0.65
AUC vs Running Time: Figure 3(a) plots accuracy (AUC) vs. running time (log scale, in seconds, excluding I/O) on the ISCX-IDS2012 dataset. AUC vs ランニングタイム: 図3(a)は、ISCX-IDS2012データセット上の実行時間(I/Oを除く)に対して精度(AUC)をプロットする。 0.85
ANOEDGE-G and ANOEDGE-L achieve much higher accuracy compared to all baselines, while also running significantly fast. ANOEDGE-GとANOEDGE-Lは、全てのベースラインよりもはるかに高い精度で動作し、高速である。 0.60
Figure 3: On ISCX-IDS2012, (a) AUC vs running time when detecting edge anomalies. 図3: iscx-ids2012 では、(a) エッジ異常検出時の auc 対 実行時間。 0.74
(b) Linear scalability with number of hash functions. (b)ハッシュ関数の数による線形スケーラビリティ。 0.80
(c) Linear scalability with number of edges. (c) エッジ数による線形スケーラビリティ。 0.72
Scalability: Figures 3(b) and 3(c) plot the running time with increasing number of hash functions and edges respectively, on the ISCX-IDS2012 dataset. スケーラビリティ: 図3(b) と 3(c) はそれぞれ ISCX-IDS2012 データセットでハッシュ関数とエッジの数を増やして実行時間をプロットする。 0.87
This demonstrates the scalability of ANOEDGE-G and ANOEDGE-L. これはANOEDGE-GとANOEDGE-Lのスケーラビリティを示している。 0.52
7.2 Graph Anomalies Accuracy: Table 4 shows the AUC of graph anomaly detection baselines, ANOGRAPH, and ANOGRAPH-K. We report a single value for DENSEALERT and ANOMRANK because these are non-randomized methods. 7.2 グラフ異常 精度:表4は,グラフ異常検出ベースライン,ANOGRAPH,ANOGRAPH-K のAUCを示す。
訳抜け防止モード: 7.2 グラフ異常 精度:表4はグラフ異常検出ベースラインのAUCを示す。 非ランダム化手法であるため、DENSEALERTとANOMRANKの1つの値を報告する。
0.65
ANOMRANK is not meant for a streaming scenario, therefore the low AUC. ANOMRANKはストリーミングのシナリオを意図していないため、AUCは低い。 0.71
DENSEALERT can estimate only one subtensor at a time and SPOTLIGHT uses a randomized approach without any actual search for dense subgraphs. DENSEALERT は一度に1つの拡張子のみを推定でき、SPOTLIGHT は密接な部分グラフを実際に検索することなくランダムなアプローチを使用する。 0.52
Note that ANOGRAPH and ANOGRAPH-K ANOGRAPHとANOGRAPH-K 0.77
9 9 0.85
英語(論文から抽出)日本語訳スコア
outperform all baselines on all datasets while using a simple sketch data structure to incorporate dense subgraph search as opposed to the baselines. すべてのデータセットのベースラインを上回り、単純なスケッチデータ構造を使用して、ベースラインとは対照的に密度の高いサブグラフ検索を組み込む。 0.67
We provide results with additional set of parameters in Table 6, Appendix G. 結果には、テーブル 6 で追加のパラメータセットを提供する。 0.57
Table 4: AUC and Running Time when detecting graph anomalies. 表4: グラフ異常を検出する際のAUCと実行時間。 0.80
Averaged over 5 runs. Dataset 平均5回に及んだ。 データセット 0.60
DARPA ISCX-IDS2012 DARPA ISCX-IDS2012 0.66
CIC-IDS2018 CIC-IDS2018 0.47
CIC-DDoS2019 CIC-DDoS2019 0.47
DENSEALERT 0.833 49.3s 0.906 6.4s 0.950 67.9s 0.764 1065.0s DENSEALERT 0.833 49.3s 0.906 6.4s 0.950 67.9s 0.764 1065.0s 0.39
SPOTLIGHT ANOMRANK 0.728 ± 0.016 0.754 88.5s 3.7s 0.872 ± 0.019 0.194 5.2s 21.1s 0.835 ± 0.022 0.783 149.0s 7.0s 0.468 ± 0.048 0.241 0.2s 289.7s SPOTLIGHT ANOMRANK 0.728 ± 0.016 0.754 88.5s 3.7s 0.872 ± 0.019 0.194 5.2s 21.1s 0.835 ± 0.022 0.783 149.0s 7.0s 0.468 ± 0.048 0.241 0.241 289.7s 0.43
ANOGRAPH ANOGRAPH-K 0.839 ± 0.002 0.835 ± 0.002 0.3s 0.3s 0.950 ± 0.001 0.950 ± 0.001 0.5s 0.5s 0.957 ± 0.000 0.957 ± 0.000 0.2s 0.3s 0.948 ± 0.002 0.946 ± 0.002 0.4s 0.4s ANOGRAPH ANOGRAPH-K 0.839 ± 0.002 0.835 ± 0.002 0.3s 0.3s 0.950 ± 0.001 0.950 ± 0.001 0.5s 0.957 ± 0.000 0.957 ± 0.000 0.2s 0.3s 0.948 ± 0.002 0.946 ± 0.4s 0.4s 0.48
Running Time: Table 4 shows the running time (excluding I/O). 実行時間: テーブル4は(i/oを除く)実行時間を表示する。 0.77
DENSEALERT has O(|E |) worse case time complexity (per incoming edge). DENSEALERT は O(|E |) より悪いケース時間複雑性を持つ。 0.73
ANOMRANK needs to compute a global PageRank, which does not scale for stream processing. ANOMRANKは、ストリーム処理にスケールしないグローバルなPageRankを計算する必要がある。 0.82
Note that ANOGRAPH and ANOGRAPH-K run much faster than all baselines. ANOGRAPHとANOGRAPH-Kは、すべてのベースラインよりもはるかに高速である。 0.65
AUC vs Running Time: Figure 4 (a) plots accuracy (AUC) vs. running time (log scale, in seconds, excluding I/O) on the CIC-DDoS2019 dataset. AUC vs ランニングタイム: 図4(a)は、CIC-DDoS2019データセット上の実行時間(ログスケール、数秒でI/Oを除く)をプロットする。 0.87
ANOGRAPH and ANOGRAPH-K achieve much higher accuracy compared to the baselines, while also running significantly faster. ANOGRAPHとANOGRAPH-Kはベースラインよりもはるかに精度が高く、実行速度もかなり速い。 0.74
Figure 4: On CIC-DDoS2019, (a) AUC vs running time when detecting graph anomalies. 図4: cic-ddos2019では、(a) グラフ異常検出時の auc 対 実行時間。 0.73
(b) ANOGRAPH-K scales linearly with factor K. (c) Linear scalability with number of hash functions. b) anograph-k は因子 k で線形にスケールする(c) ハッシュ関数の数の線形スケーラビリティ。 0.77
(d) Linear scalability with number of edges. (d)エッジ数による線形スケーラビリティ。 0.72
Scalability: Figures 4(b), 4(c), and 4(d) plot the running time with increasing factor K (used for top-K in Algorithm 4), number of hash functions and number of edges respectively, on the CIC-DDoS2019 dataset. スケーラビリティ: 図4(b), 4(c), 4(d)は、CIC-2019データセット上で、増加要因K(アルゴリズム4でトップKに使用される)、ハッシュ関数の数、エッジの数で実行時間をプロットする。 0.78
This demonstrates the scalability of ANOGRAPH and ANOGRAPH-K. これはANOGRAPHとANOGRAPH-Kのスケーラビリティを示している。 0.64
8 Conclusion In this paper, we extend the CMS data structure to a higher-order sketch to capture complex relations in graph data and to reduce the problem of detecting suspicious dense subgraphs to finding a dense submatrix in constant time. 8 結論 本稿では,cmsデータ構造を高次スケッチに拡張し,グラフデータにおける複雑な関係を捉え,疑わしい高密度部分グラフの検出問題を低減し,高密度部分行列を一定時間発見する。 0.78
We then propose four sketch-based streaming methods to detect edge and subgraph anomalies in constant time and memory. 次に,エッジとサブグラフの異常を一定時間とメモリで検出する,スケッチに基づく4つのストリーミング手法を提案する。 0.62
Furthermore, our approach is the first streaming work that incorporates dense subgraph search to detect graph anomalies in constant memory and time. さらに,本手法は,高密度サブグラフ探索を組み込んだ最初のストリーミング処理であり,一定メモリと時間におけるグラフ異常を検出する。 0.68
We also provide a theoretical guarantee on the submatrix density measure and prove the time and space complexities of all methods. また、サブ行列密度測度に関する理論的保証を提供し、すべての方法の時間と空間の複雑さを証明する。
訳抜け防止モード: サブマトリクス密度測度に関する理論的な保証も提供します すべての方法の時間と空間の複雑さを証明できます
0.77
Experimental results on four real-world datasets demonstrate our effectiveness as opposed to popular state-of-the-art streaming edge and graph baselines. 4つの実世界のデータセットに対する実験結果は、最先端のストリーミングエッジやグラフベースラインとは対照的に、我々の有効性を示している。 0.50
Future work could consider incorporating node and edge representations, and more general types of data, including tensors. 今後の作業では、ノードとエッジ表現、テンソルを含むより一般的なタイプのデータの導入を検討することができる。 0.56
References [1] Kijung Shin, Bryan Hooi, Jisu Kim, and Christos Faloutsos. 参照: [1] Kijung Shin, Bryan Hooi, Jisu Kim, Christos Faloutsos。 0.73
Densealert: Incremental dense-subtensor Densealert: インクリメンタルな高密度化 0.63
detection in tensor streams. テンソルストリームにおける検出。 0.66
KDD, 2017. 2017年、KDD。 0.80
10 10 0.85
英語(論文から抽出)日本語訳スコア
[2] Dhivya Eswaran, Christos Faloutsos, Sudipto Guha, and Nina Mishra. [2] dhivya eswaran, christos faloutsos, sudipto guha, nina mishra。 0.57
Spotlight: Detecting anomalies in spotlight: 異常を検出する 0.88
streaming graphs. ストリーミンググラフ。 0.72
In KDD, 2018. 2018年、KDD。 0.62
[3] Siddharth Bhatia, Bryan Hooi, Minji Yoon, Kijung Shin, and Christos Faloutsos. Siddharth Bhatia, Bryan Hooi, Minji Yoon, Kijung Shin, Christos Faloutsos。 0.56
Midas: Microcluster-based midas: マイクロクラスタベース 0.68
detector of anomalies in edge streams. エッジストリームにおける異常の検出 0.78
In AAAI, 2020. AAAI、2020年。 0.69
[4] Leman Akoglu, Mary McGlohon, and Christos Faloutsos. 4]Leman Akoglu, Mary McGlohon, Christos Faloutsos。 0.64
Oddball: Spotting anomalies in weighted graphs. oddball: 重み付きグラフで異常を見つける。 0.75
In PAKDD, 2010. 2010年、PAKDD。 0.71
[5] Deepayan Chakrabarti. 5]Deepayan Chakrabarti。 0.65
Autopart: Parameter-free graph partitioning and outlier detection. autopart: パラメータフリーなグラフ分割と異常検出。 0.83
In PKDD, 2004. 2004年、PKDD。 0.74
[6] Bryan Hooi, Kijung Shin, Hyun Ah Song, Alex Beutel, Neil Shah, and Christos Faloutsos. 6]Bryan Hooi, Kijung Shin, Hyun Ah Song, Alex Beutel, Neil Shah, Christos Faloutsos。
訳抜け防止モード: [6 ]Bryan Hooi, Kijung Shin, Hyun Ah Song, Alex Beutel氏、Neil Shah氏、Christos Faloutsos氏。
0.80
Graph-based fraud detection in the face of camouflage. グラフベース カモフラージュの顔の不正検出。 0.55
TKDD, 2017. 2017年、TKDD。 0.87
[7] Meng Jiang, Peng Cui, Alex Beutel, Christos Faloutsos, and Shiqiang Yang. [7]Meng Jiang, Peng Cui, Alex Beutel, Christos Faloutsos, Shiqiang Yang。 0.71
Catching synchronized behaviors in large networks: A graph mining approach. 同期をキャッチする 大規模ネットワークにおける行動: グラフマイニングアプローチ。 0.71
TKDD, 2016. TKDD、2016年。 0.89
[8] Jon M Kleinberg. ジョン・M・クラインバーグ(Jon M Kleinberg) 0.56
Authoritative sources in a hyperlinked environment. ハイパーリンク環境における権威ソース。 0.72
JACM, 1999. 1999年、JACM。 0.81
[9] Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. [9]キジュン・シン、ティナ・エリアッシ=ラド、クリストス・ファルートス。 0.49
Patterns and anomalies in k-cores of real-world 実世界のkコアにおけるパターンと異常 0.62
graphs with applications. アプリケーションによるグラフです 0.80
KAIS, 2018. 2018年、デビュー。 0.48
[10] Hanghang Tong and Ching-Yung Lin. [10]Hanghang TongとChing-Yung Lin。 0.90
Non-negative residual matrix factorization with application to graph 非負の残留行列分解とグラフへの応用 0.67
anomaly detection. In SDM, 2011. 異常検出 2011年、SDM。 0.54
[11] Dhivya Eswaran and Christos Faloutsos. 11]Dhivya Eswaran氏とChristos Faloutsos氏。 0.78
Sedanspot: Detecting anomalies in edge streams. Sedanspot: エッジストリームの異常を検出する。 0.75
In ICDM, 2018. 2018年、ICDM。 0.67
[12] C Belth, X Zheng, and D Koutra. [12]C Belth, X Zheng, D Koutra。 0.70
Mining persistent activity in continually evolving networks. 継続的に進化するネットワークにおける永続的な活動のマイニング。 0.51
In KDD, 2020. 略称KDD。 2020. 0.68
[13] Yen-Yu Chang, Pan Li, Rok Sosic, MH Afifi, Marco Schweighauser, and Jure Leskovec. [13]Yen-Yu Chang、Pan Li、Rok Sosic、MH Afifi、Marco Schweighauser、Jure Leskovec。 0.69
F-fade: Frequency factorization for anomaly detection in edge streams. Fフェード:周波数 エッジストリームにおける異常検出のための因子化 0.67
In WSDM, 2021. 2021年、WSDM。 0.75
[14] Minji Yoon, Bryan Hooi, Kijung Shin, and Christos Faloutsos. 十四 みんじよおん、Bryan Hooi、Kijung Shin、Christos Faloutsos。 0.54
Fast and accurate anomaly detection in 高速かつ高精度な異常検出 0.75
dynamic graphs with a two-pronged approach. 2-prongedアプローチによる動的グラフ。 0.80
In KDD, 2019. 2019年、KDD。 0.72
[15] Graham Cormode and Shan Muthukrishnan. 15]グラハム・コルモドとシャン・ムトゥクリシュナン 0.41
An improved data stream summary: the count-min sketch and 改良されたデータストリーム要約:count-min sketchと 0.79
its applications. Journal of Algorithms, 2005. 応用。 アルゴリズム』、2005年。 0.51
[16] Jiabao Zhang, Shenghua Liu, Wenjian Yu, Wenjie Feng, and Xueqi Cheng. [16]Jiabao Zhang、Senghua Liu、Wenjian Yu、Wenjie Feng、Xueqi Cheng。 0.66
Eigenpulse: Detecting surges eigenpulse:サージを検出する 0.69
in large streaming graphs with row augmentation. 行を拡大した大きなストリーミンググラフです 0.78
In PAKDD, 2019. 2019年、PAKDD。 0.74
[17] Petko Bogdanov, Christos Faloutsos, Misael Mongiovì, Evangelos E Papalexakis, Razvan Ranca, and Ambuj K Singh. 17]petko bogdanov、christos faloutsos、misael mongiov、evangelos e papalexakis、razvan ranca、ambuj k singh。 0.39
Netspot: Spotting significant anomalous regions on dynamic networks. Netspot: 動的ネットワーク上で重要な異常領域を見つける。 0.79
In SDM, 2013. 2013年、SDM。 0.56
[18] Neil Shah, Alex Beutel, Bryan Hooi, Leman Akoglu, Stephan Gunnemann, Disha Makhija, Mohit Kumar, and Christos Faloutsos. 12]Neil Shah, Alex Beutel, Bryan Hooi, Leman Akoglu, Stephan Gunnemann, Disha Makhija, Mohit Kumar, Christos Faloutsos。 0.73
Edgecentric: Anomaly detection in edge-attributed networks. edgecentric: エッジ属性ネットワークにおける異常検出。 0.77
In ICDMW, 2016. ICDMW、2016年。 0.72
[19] Bryan Perozzi and Leman Akoglu. [19]Bryan PerozziとLeman Akoglu。 0.75
Discovering communities and anomalies in attributed graphs: Interactive 帰属グラフにおけるコミュニティと異常の発見:インタラクティブ 0.79
visual exploration and summarization. 視覚的な探索と要約です 0.64
TKDD, 2018. 2018年、TKDD。 0.86
[20] Francesco Bonchi, Ilaria Bordino, Francesco Gullo, and Giovanni Stilo. 20]フランチェスコ・ボンチ、イリア・ボルディノ、フランチェスコ・グルロ、ジョヴァンニ・スティロ 0.46
The importance of unexpectedness: 予期せぬことの重要性 0.67
Discovering buzzing stories in anomalous temporal graphs. 異常な時相グラフでバズングストーリーを発見する。 0.66
Web Intelligence, 2019. web intelligence、2019年。 0.75
[21] Francesco Bonchi, Ilaria Bordino, Francesco Gullo, and Giovanni Stilo. 1621]Francesco Bonchi, Ilaria Bordino, Francesco Gullo, Giovanni Stilo。 0.64
Identifying buzzing stories via buzzing stories を識別する 0.88
anomalous temporal subgraph discovery. 異常な時間的部分グラフ発見 0.59
In WI, 2016. [22] Aleksandar Bojchevski and Stephan Günnemann. 2016年、WI。 [22]Aleksandar BojchevskiとStephan Günnemann。 0.60
Bayesian robust attributed graph clustering: Joint Bayesian robust attributed graph clustering: Joint 0.85
learning of partial anomalies and group structure. 部分的な異常とグループ構造の学習。 0.81
In AAAI, 2018. 2018年、AAAI。 0.59
[23] Wenchao Yu, Wei Cheng, C Aggarwal, K Zhang, H Chen, and Wei Wang. [23]Wenchao Yu、Wei Cheng、C Aggarwal、K Zhang、H Chen、Wei Wang。 0.64
Netwalk: A flexible deep netwalk: 柔軟な深層 0.76
embedding approach for anomaly detection in dynamic networks. 動的ネットワークにおける異常検出のための埋め込み手法 0.81
KDD, 2018. 2018年、KDD。 0.77
[24] Gyoung S Na, Donghyun Kim, and Hwanjo Yu. [24]行恩 SNa、ドンギュン・キム、Hwanjo Yu。 0.44
Dilof: Effective and memory efficient local outlier Dilof: 有効でメモリ効率のよいローカルアウトレイア 0.73
detection in data streams. データストリームにおける検出。 0.75
In KDD, 2018. 2018年、KDD。 0.62
[25] Emaad A Manzoor, Hemank Lamba, and Leman Akoglu. Emaad A Manzoor, Hemank Lamba, Leman Akoglu. [25] Emaad A Manzoor, Hemank Lamba, Leman Akoglu. 0.63
xstream: Outlier detection in feature-evolving xstream: 機能進化における外乱検出 0.70
data streams. In KDD, 2018. データストリーム。 2018年、KDD。 0.67
[26] Swee Chuan Tan, Kai Ming Ting, and Tony Fei Liu. [26]Swee Chuan Tan、Kai Ming Ting、Tony Fei Liu。 0.66
Fast anomaly detection for streaming data. ストリーミングデータの高速異常検出。 0.71
In IJCAI, 2011. IJCAI 2011. 0.57
11 11 0.85
英語(論文から抽出)日本語訳スコア
[27] Dimitrije Jankov, Sourav Sikdar, Rohan Mukherjee, Kia Teymourian, and Chris Jermaine. Dimitrije Jankov, Sourav Sikdar, Rohan Mukherjee, Kia Teymourian, Chris Jermaine。 0.54
Real-time high performance anomaly detection over data streams: Grand challenge. リアルタイムハイ データストリーム上のパフォーマンス異常検出: 壮大な挑戦。 0.76
DEBS, 2017. 2017年、DBS。 0.73
[28] Shaofeng Zou, Yingbin Liang, H Vincent Poor, and Xinghua Shi. [28]ショーフェンゾウ、Yingbin Liang、H Vincent Poor、Xinghua Shi。 0.56
Nonparametric detection of anomalous 異常の非パラメトリック検出 0.85
data streams. IEEE Transactions on Signal Processing, 2017. データストリーム。 IEEE Transactions on Signal Processing, 2017 (英語) 0.77
[29] Masud Moshtaghi, James C Bezdek, Christopher Leckie, Shanika Karunasekera, and Marimuthu Palaniswami. Masud Moshtaghi氏、James C Bezdek氏、Christopher Leckie氏、Shanika Karunasekera氏、Marimuthu Palaniswami氏。 0.61
Evolving fuzzy rules for anomaly detection in data streams. データストリームにおける異常検出のためのファジィルールの進化。 0.68
IEEE Transactions on Fuzzy Systems, 2015. IEEE Transactions on Fuzzy Systems, 2015 0.73
[30] Alban Siffer, Pierre-Alain Fouque, Alexandre Termier, Christine Largouet, and C Largouët. Alban Siffer氏、Pierre-Alain Fouque氏、Alexandre Termier氏、Christine Largouet氏、C Largouët氏。 0.72
Anomaly detection in streams with extreme value theory. 異常 極限値理論によるストリームの検出。 0.55
KDD, 2017. 2017年、KDD。 0.80
[31] Maurras Ulbricht Togbe, Mariam Barry, Aliou Boly, Yousra Chabchoub, Raja Chiky, Jacob Montiel, and Vinh-Thuy Tran. Maurras Ulbricht Togbe, Mariam Barry, Aliou Boly, Yousra Chabchoub, Raja Chiky, Jacob Montiel, Vinh-Thuy Tran。 0.69
Anomaly detection for data streams based on isolation forest using scikit-multiflow. scikit-multiflowを用いた孤立林に基づくデータストリームの異常検出 0.78
In ICCSA, 2020. ICCSA、2020年。 0.74
[32] Jiabao Zhang, Shenghua Liu, Wenting Hou, Siddharth Bhatia, Hua-Wei Shen, Wenjian Yu, and Xueqi 32]jiabao zhang, shenghua liu, wenting hou, siddharth bhatia, hua-wei shen, wenjian yu, xueqi
訳抜け防止モード: [32 ]Jiabao Zhang,Senghua Liu,Wenting Hou, Siddharth Bhatia, Hua - Wei Shen, Wenjian Yu, Xueqi
0.85
Cheng. Augsplicing: Synchronized behavior detection in streaming tensors. Cheng augsplicing: ストリーミングテンソルにおける同期動作検出。 0.65
AAAI, 2021. AAAI、2021年。 0.73
[33] Shirui Pan, Xingquan Zhu, Chengqi Zhang, and S Yu Philip. [33]しるいパン、Xingquan Zhu、Chengqi Zhang、S Yu Philip。 0.68
Graph stream classification using labeled and ラベル付きおよびラベル付きグラフストリーム分類 0.74
unlabeled graphs. In ICDE, 2013. ラベルなしのグラフ 2013年、ICDE。 0.70
[34] Wei Wang, Xiaohong Guan, and Xiangliang Zhang. [34]wui wang, xiaohong guan, xiangliang zhang。 0.54
Processing of massive audit data streams for real-time 大規模監査データストリームのリアルタイム処理 0.84
anomaly intrusion detection. Computer communications, 2008. 異常侵入検出 2008年、コンピュータ通信。 0.71
[35] Aditya Krishna Menon, Gia Vinh Anh Pham, Sanjay Chawla, and Anastasios Viglas. Aditya Krishna Menon氏、Gia Vinh Anh Pham氏、Sanjay Chawla氏、Anastasios Viglas氏。 0.65
An incremental data-stream sketch using sparse random projections. 漸進的 スパースランダムプロジェクションを用いたデータストリームスケッチ。 0.60
In SDM, 2007. 2007年、sdm。 0.61
[36] Peixiang Zhao, Charu C Aggarwal, and Min Wang. [36]Pixiang Zhao、Charu C Aggarwal、Min Wang。 0.65
gsketch: On query estimation in graph streams. gsketch: グラフストリームのクエリ推定について。 0.74
VLDB, 2011. vldb。 2011. 0.68
[37] Yang Shi and Animashree Anandkumar. [37]yangshiとanimashree anandkumar。 0.61
Higher-order count sketch: Dimensionality reduction that retains 高次数スケッチ:保持する次元性低減 0.75
efficient tensor operations. 効率的なテンソル操作 0.62
DCC, 2020. DCC、2020年。 0.89
[38] Raghavendra Chalapathy and Sanjay Chawla. [38]Raghavendra ChalapathyとSanjay Chawla。 0.78
Deep learning for anomaly detection: A survey. 異常検出のためのディープラーニング:調査。 0.72
ArXiv, abs/1901.03407, 2019. arxiv。 abs/1901.03407, 2019 0.64
[39] Guansong Pang, Chunhua Shen, Longbing Cao, and Anton van den Hengel. [39]Guansong Pang、Chunhua Shen、Longbing Cao、Anton van den Hengel。 0.63
Deep learning for anomaly detection: A review. 異常の深層学習 detection: レビュー。 0.67
arXiv preprint arXiv:2007.02500, 2020. arXiv preprint arXiv:2007.02500, 2020 0.81
[40] Leman Akoglu, Hanghang Tong, and Danai Koutra. [40]Leman Akoglu、Hanghang Tong、Danai Koutra。 0.64
Graph based anomaly detection and description: A グラフに基づく異常検出と記述:A 0.88
survey. Data mining and knowledge discovery, 2015. 調査。 データマイニングと知識発見, 2015年。 0.73
[41] Weiren Yu, Charu C Aggarwal, Shuai Ma, and Haixun Wang. [41]Weiren Yu,Charu C Aggarwal,Shuai Ma,Haixun Wang 0.61
On anomalous hotspot discovery in graph グラフにおける異常ホットスポット発見について 0.57
streams. In ICDM, 2013. ストリーム。 2013年、ICDM。 0.70
[42] Stephen Ranshous, Steve Harenberg, Kshitij Sharma, and Nagiza F Samatova. [42]Stephen Ranshous, Steve Harenberg, Kshitij Sharma, Nagiza F Samatova。 0.76
A scalable approach for スケーラブルなアプローチ 0.48
outlier detection in edge streams using sketch-based approximations. スケッチに基づく近似を用いたエッジストリームの異常検出 0.74
In SDM, 2016. 2016年、SDM。 0.61
[43] Kumar Sricharan and Kamalika Das. [43]Kumar SricharanとKamalika Das。 0.55
Localizing anomalous changes in time-evolving graphs. 時間発展グラフにおける異常変化の局在化 0.68
In SIGMOD, 2014. SIGMOD 2014. 0.58
[44] Jimeng Sun, Dacheng Tao, and Christos Faloutsos. 44]Jimeng Sun, Dacheng Tao, Christos Faloutsos。 0.63
Beyond streams and graphs: dynamic tensor analysis. ストリームとグラフを超えて:動的テンソル解析。 0.78
In KDD, 2006. 2006年、KDD。 0.71
[45] Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, Christos Faloutsos。 0.58
Copycatch: Copycatch: 0.85
stopping group attacks by spotting lockstep behavior in social networks. ソーシャルネットワークのロックステップを 見つけ出すことでグループ攻撃を止める 0.71
In WWW, 2013. 2013年、WWW。 0.67
[46] Ehab Abdelhamid, Mustafa Canim, M. Sadoghi, B. Bhattacharjee, Yuan-Chi Chang, and Panos Kalnis. [46]Ehab Abdelhamid, Mustafa Canim, M. Sadoghi, B. Bhattacharjee, Yuan-Chi Chang, Panos Kalnis。 0.91
Incremental frequent subgraph mining on large evolving graphs. 大規模進化グラフ上の頻繁なサブグラフマイニング。 0.69
TKDE, 2017. 2017年、TKDE。 0.88
[47] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. Lawrence Page氏、Sergey Brin氏、Rajeev Motwani氏、Terry Winograd氏。 0.64
The pagerank citation ranking : ページランク引用ランキング 0.47
Bringing order to the web. ウェブに秩序をもたらす。 0.67
In WWW, 1999. 1999年、WWW。 0.68
[48] Andrew Mcgregor. アンドリュー・マクグレゴール(Andrew McGregor)。 0.65
Graph stream algorithms: a survey. グラフストリームアルゴリズム: 調査。 0.46
SIGMOD Record, 2014. 2014年、SIGMODレコード。 0.82
[49] Samir Khuller and Barna Saha. 49] Samir Khuller 氏と Barna Saha 氏。 0.86
On finding dense subgraphs. 濃密な部分グラフを見つけること。 0.45
In ICALP, 2009. 2009年、ICP。 0.57
12 12 0.85
英語(論文から抽出)日本語訳スコア
[50] Richard Lippmann, Robert K Cunningham, David J Fried, Isaac Graf, Kris R Kendall, Seth E Webster, and Marc A Zissman. Richard Lippmann氏、Robert K Cunningham氏、David J Fried氏、Isaac Graf氏、Kris R Kendall氏、Seth E Webster氏、Marc A Zissman氏。 0.77
Results of the darpa 1998 offline intrusion detection evaluation. darpa 1998 オフライン侵入検出評価の結果。 0.66
In Recent advances in intrusion detection, 1999. 侵入検知の最近の進歩、1999年。 0.75
[51] Ali Shiravi, Hadi Shiravi, Mahbod Tavallaee, and Ali A Ghorbani. [51]Ali Shiravi、Hadi Shiravi、Mahbod Tavallaee、Ali A Ghorbani。 0.68
Toward developing a systematic システム開発に向けて 0.80
approach to generate benchmark datasets for intrusion detection. 侵入検知のためのベンチマークデータセット生成のアプローチ。 0.66
computers & security, 2012. コンピュータとセキュリティ、2012年。 0.81
[52] Markus Ring, Sarah Wunderlich, Deniz Scheuring, Dieter Landes, and Andreas Hotho. Markus Ring氏、Sarah Wunderlich氏、Denis Scheuring氏、Diter Landes氏、Andreas Hotho氏。 0.63
A survey of network-based intrusion detection data sets. アンケート調査 ネットワークベースの侵入検知データセット。 0.60
Computers & Security, 2019. コンピュータとセキュリティ、2019年。 0.79
[53] Iman Sharafaldin, Arash Habibi Lashkari, and Ali A Ghorbani. 53]Iman Sharafaldin、Arash Habibi Lashkari、Ali A Ghorbani。 0.64
Toward generating a new intrusion detection 新しい侵入検知の実現に向けて 0.81
dataset and intrusion traffic characterization. データセットと侵入トラフィックの特徴 0.79
In ICISSP, 2018. 2018年、ICISSP。 0.50
[54] Iman Sharafaldin, Arash Habibi Lashkari, Saqib Hakak, and Ali A Ghorbani. [54]Iman Sharafaldin, Arash Habibi Lashkari, Saqib Hakak, Ali A Ghorbani。 0.74
Developing realistic distributed denial of service (ddos) attack dataset and taxonomy. 現実的な開発 distributed denial of service(ddos)はデータセットと分類を攻撃します。 0.62
In ICCST, 2019. 2019年、ICCST。 0.72
[55] Random Cut Forest. [55]森林のランダムカット。 0.82
https://github.com/a ws/random-cut-forest -by-aws, 2021. https://github.com/a ws/random-cut-forest -by-aws, 2021。 0.35
[56] J Lawrence Carter and Mark N Wegman. [56]jローレンス・カーターとマーク・n・ウェグマン 0.63
Universal classes of hash functions. ハッシュ関数の普遍クラス。 0.66
Journal of computer and journal of computer and 0.81
system sciences, 1979. 1979年、大学教授。 0.56
Appendix A H-CMS Algorithm 5 shows the H-CMS operations. 付録 H-CMS アルゴリズム5は、H-CMS操作を示す。 0.65
Algorithm 5: H-CMS Operations アルゴリズム5:h-cms演算 0.69
for r ← 1 ... nr do hr : V → [0, nb) Mr → [0]nb×nb r > 1 ... nr do hr : V → [0, nb) Mr → [0]nb×nb 0.79
1 Procedure INITIALIZE H-CMS(nr, nb) 2 3 4 1 Procedure RESET H-CMS(nr, nb) 2 3 1 H-CMS(nr, nb) 2 3 4 1 の手順 H-CMS(nr, nb) 2 3 0.79
for r ← 1 ... nr do Mr ← [0]nb×nb r > 1 ... nr の場合、mr > [0]nb×nb 0.54
// hash vertex // reset to zero matrix //ハッシュ頂点 //ゼロマトリクスにリセットする 0.78
1 Procedure UPDATE H-CMS(u, v, w) 2 3 1 手順 UPDATE H-CMS(u, v, w) 2 3 0.94
for r ← 1 ... nr do r を 1 に... nr do 0.56
Mr[hr(u)][hr(v)] ← Mr[hr(u)][hr(v)] + w Mr[hr(u)][hr(v)] > Mr[hr(u)][hr(v)] + w 0.61
1 Procedure DECAY H-CMS(δ) 2 3 1 手順 DeCAY H-CMS(δ) 2 3 0.89
for r ← 1 ... nr do Mr ← δ ∗ Mr r > 1 ... nr に対して、mr > δ ∗ M は 0.46
// decay factor: δ B Datasets Table 5 shows the statistical summary of the datasets. //崩壊要因:δ bデータセットテーブル5は、データセットの統計概要を示す。 0.83
|E| corresponds to the total number of edge records, |V | and |T| are the number of unique nodes and unique timestamps, respectively. E| はエッジレコードの総数に対応し、|V| と |T| はそれぞれユニークなノード数とユニークなタイムスタンプ数である。 0.80
Table 5: Statistics of the datasets. 表5: データセットの統計。 0.75
Dataset DARPA ISCX-IDS2012 CIC-IDS2018 CIC-DDoS2019 DARPA ISCX-IDS2012 CIC-IDS2018 CIC-DDoS2019 0.46
|V | 25,525 30,917 33,176 1,290 |V | 25,525 30,917 33,176 1,290 0.51
|E| 4,554,344 1,097,070 7,948,748 20,364,525 |E| 4,554,344 1,097,070 7,948,748 20,364,525 0.29
|T| Edge Anomalies Graph Anomalies 26.5% 3.38% 11.0% 51.4% T|エッジ異常グラフ異常 26.5% 3.38% 11.0% 51.4% 0.61
60.1% 4.23% 7.26% 99.7% 60.1% 4.23% 7.26% 99.7% 0.62
46,567 165,043 38,478 12,224 46,567 165,043 38,478 12,224 0.45
13 13 0.85
英語(論文から抽出)日本語訳スコア
DARPA [50] and ISCX-IDS2012 [51] are popular anomaly detection datasets used by baseline papers to evaluate their algorithms. DARPA [50] と ISCX-IDS2012 [51] は、ベースライン論文がアルゴリズムを評価するために使用する一般的な異常検出データセットである。 0.69
[52] surveys more than 30 datasets and recommends to use the newer CIC-IDS2018 [53] and CIC-DDoS2019 [54] containing modern attack scenarios. 52]は30以上のデータセットを調査し、最新の攻撃シナリオを含む新しいCIC-IDS2018[53]とCIC-DDoS2019[54]を使用することを推奨している。 0.64
C Higher-Order Sketch Proof C級高次スケッチ証明 0.66
Theorem 1. H-CMS has the same estimate guarantees as the original CMS. 理論1。 H-CMSは元のCMSと同じ推定値を持つ。 0.69
Proof. Consider a 3-dimensional H-CMS, with depth nr, where an entity a ∈ [1, N ] is mapped to index (i, j) with two independent hash functions h(cid:48) : [1, N ] → [0, b) and h(cid:48)(cid:48) : [1, N ] → [0, b), i.e., i = h(cid:48)(a) and j = h(cid:48)(cid:48)(a) . 証明。 深さ nr の三次元 H-CMS を考えると、ある実体 a ∈ [1, N ] を2つの独立ハッシュ関数 h(cid:48) : [1, N ] → [0, b) と h(cid:48)(cid:48) : [1, N ] → [0, b) を持つ指数 (i, j) に写像する。
訳抜け防止モード: 証明。 深さ nr の 3 次元 h-cms を考えると、エンティティ a ∈ [ 1, n ] は 2 つの独立ハッシュ関数 h(cid:48 ) : [ 1, j ) を持つ指数 (i, j ) に写像される。 n ] → [ 0, b ) および h(cid:48)(cid:48 ) : [ 1, n ] → [ 0, b ) i = h(cid:48)(a) である。 j = h(cid:48)(cid:48)(a) である。
0.72
Without loss of generality, the 3-dimensional H-CMS can be converted to a CMS data structure by combining h(cid:48) and h(cid:48)(cid:48) in the following way: h(a) = nb ∗ h(cid:48)(a) + h(cid:48)(cid:48)(a) , i.e., h(a) = nb ∗ i + j where b ∗ i ∈ [0, n2 b − nb) and j ∈ [0, nb]. h(a) = nb ∗ h(cid:48)(a) + h(cid:48)(cid:48)(a) + h(cid:48)(cid:48)(a) 、すなわち h(a) = nb ∗ i + j ここで b ∗ i ∈ [0, n2 b − nb) と j ∈ [0, nb] である。
訳抜け防止モード: 一般性を失うことなく、次の方法でh(cid:48)(cid:48)(ci d:48)(cid:48)とh(cid:48)(cid:48)(a ) = nb ∗ h(cid:48)(cid:48)(ci d:48)(a ) + h(cid:48)(cid:48)(ci d:48)(a ))を組み合わせることで、3次元のH-CMSをCMSデータ構造に変換することができる。 すなわち、h(a ) = nb ∗ i + j である。 n2 b − nb ) および j ∈ [0, nb ] である。
0.69
Hence, h(a) ∈ [0, b2), and h : [1, N ] → [0, b2) can be a hash function for a CMS data structure with width n2 b and depth nr. したがって、h(a) ∈ [0, b2) と h : [1, N ] → [0, b2) は、幅 n2 b と深さ nr を持つ CMS データ構造に対するハッシュ関数である。 0.86
Therefore, the CMS estimate guarantee holds for a 3-dimensional H-CMS data structure. したがって、CMS推定保証は3次元H-CMSデータ構造を保持する。 0.82
A higher dimensional H-CMS can be reduced to a CMS data structure in a similar manner. 同様に高次元H-CMSをCMSデータ構造に還元することができる。 0.80
D Edge Anomalies Proofs d エッジ異常の証明 0.59
D.1 Proofs: ANOEDGE-G Proposition 1. D.1 証明: ANOEDGE-G Proposition 1 0.76
Time complexity of Algorithm 1 is O(|E | ∗ nr ∗ n2 b). アルゴリズム1の時間複雑性は O(|E | ∗ nr ∗ n2 b) である。 0.82
Proof. Procedure EDGE-SUBMATRIX-DENSI TY removes rows (or columns) iteratively, and the total number of rows and columns that can be removed is nb + nb − 2. 証明。 手続き EDGE-SUBMATRIX-DENSI TY は行(または列)を反復的に除去し、除去できる行と列の総数は nb + nb − 2 である。 0.73
In each iteration, the approach performs the following three operations: (a) pick the row with minimum row-sum; (b) pick the column with minimum column-sum; (c) calculate density. 各イテレーションにおいて、アプローチは以下の3つの操作を実行する: (a) 行を最小の行で選択する; (b) 列を最小の列で選択する; (c) 密度を計算する。 0.79
We keep nb-sized arrays for flagging removed rows (or columns), and for maintaining row-sums (or column-sums). 削除された行(または列)をフラグ付けし、行サム(または列サム)を維持するため、nbサイズの配列を保持します。 0.47
Operations (a) and (b) take maximum nb steps to pick and flag the row with minimum row-sum (or column-sum). 操作 (a) と (b) は最大 nb ステップで行を選択し、最小の行sum (または列sum) でフラグを立てる。 0.78
Updating the column-sums (or rows-sums) based on the picked row (or column) again takes maximum nb steps. 選択された行(または列)に基づいたカラムサム(または行サム)の更新は、再び最大nbステップを踏む。 0.60
Time complexity of (a) and (b) is therefore O(nb). したがって、(a) と (b) の時間複雑性は O(nb) である。 0.82
Density is directly calculated based on subtracting the removed row-sum (or column-sum) and reducing the row-count (or column-count) from the earlier density value. 密度は、削除された行数(またはカラム数)を減算し、以前の密度値から行数(またはカラム数)を減算することで直接計算される。
訳抜け防止モード: 削除行の減算に基づいて直接密度を算出する -sum(または column - sum) 行数を減らし -カウント(または列 - カウント) 前の密度値から
0.72
Row-count and column-count are kept as separate variables. Row-count と column-count は別々の変数として保持される。 0.55
Therefore, the time complexity of the density calculation step is O(1). したがって、密度計算ステップの時間複雑性はO(1)である。 0.79
Total time complexity of procedure EDGE-SUBMATRIX-DENSI TY is O((nb + nb − 2) ∗ (nb + nb + 1)) = O(n2 b). 手順EDGE-SUBMATRIX-DENSI TYの総時間複雑性は O(nb + nb − 2) ∗ (nb + nb + 1)) = O(n2 b) である。 0.91
Time complexity to initialize and decay the H-CMS data structure is O(nr ∗ n2 b). h-cms データ構造の初期化と崩壊の時間複雑性は o(nr ∗ n2 b) である。 0.74
Temporal decay operation is applied whenever the timestamp changes, and not for every received edge. タイムスタンプが変化するたびに時間減衰操作が適用され、受信されたエッジ毎には適用されない。 0.58
Update counts operation updates a matrix element value (O(1) operation) for nr matrices, and the time complexity of this step is O(nr). Update counts Operations updates a matrix element value (O(1) operation) for nr matrices, and the time complexity of this step is O(nr)。
訳抜け防止モード: Update counts Operations updates a matrix element value (O(1 ) operation ) for nr matrices. そして、このステップの時間的複雑さは O(nr ) である。
0.90
Anomaly score for each edge is based on the submatrix density computation b); the time complexity of nr matrices becomes O(nr ∗ n2 b). 各エッジの異常スコアはサブ行列密度計算bに基づいており、nr行列の時間複雑性はO(nr ∗ n2 b)となる。 0.74
Therefore, the procedure which is O(n2 total time complexity of Algorithm 1 is O(|E | ∗ (nr + nr ∗ n2 b)) = O(|E | ∗ nr ∗ n2 b). したがって、アルゴリズム1のO(n2)トータル時間複雑性は O(|E | ∗ (nr + nr ∗ n2 b)) = O(|E | ∗ nr ∗ n2 b) である。 0.84
Proposition 2. Memory complexity of Algorithm 1 is O(nr ∗ n2 b). 命題2。 アルゴリズム1のメモリ複雑性は O(nr ∗ n2 b) である。 0.65
Proof. For procedure EDGE-SUBMATRIX-DENSI TY, we keep an nb-sized arrays to flag rows and columns that are part of the current submatrix, and to maintain row-sums and column-sums. 証明。 手順EDGE-SubMATRIX-DENSI TYでは、nbサイズの配列を現在のサブマトリクスの一部である行と列にフラグ付けし、行サムと列サムを維持する。 0.65
Total memory complexity of EDGE-SUBMATRIX-DENSI TY procedure is O(4 ∗ nb) = O(nb). EDGE-SUBMATRIX-DENSI TY の総メモリ複雑性は O(4 ∗ nb) = O(nb) である。 0.80
Memory complexity of H-CMS data structure is O(nr ∗ n2 b). H-CMSデータ構造のメモリ複雑性はO(nr ∗ n2 b)である。 0.78
Dense submatrix search and density computation procedure require O(nb) memory. 密度サブ行列探索と密度計算はO(nb)メモリを必要とする。 0.75
For nr matrices, this becomes O(nr ∗ nb). nr 行列の場合、これは O(nr ∗ nb) となる。 0.74
Therefore, b + nr ∗ nb) = O(nr ∗ n2 the total memory complexity of Algorithm 1 is O(nr ∗ n2 b). したがって、b + nr ∗ nb) = o(nr ∗ n2 アルゴリズム 1 の総メモリ複雑性は o(nr ∗ n2 b) である。 0.84
D.2 Proofs: ANOEDGE-L Proposition 3. D.2 証明: ANOEDGE-L Proposition 3 0.77
Time complexity of Algorithm 2 is O(nr ∗ n2 アルゴリズム2の時間複雑性は o(nr ∗ n2 である 0.77
b + |E | ∗ nr ∗ nb). b + |E | ∗ nr ∗ nb)。 0.84
14 14 0.85
英語(論文から抽出)日本語訳スコア
Proof. As shown in Proposition 1, the time complexity of H-CMS is O(nr ∗ n2 b) and update operation is O(nr). 証明。 命題1に示すように、H-CMSの時間複雑性は O(nr ∗ n2 b) であり、更新操作は O(nr) である。 0.70
Current submatrix (Scur, Tcur) is updated based on expand and condense submatrix operations. 現在のsubmatrix(scur, tcur)は、expandおよびcondenseサブマトリックス操作に基づいて更新される。 0.75
(a) We keep an nb-sized array to flag the current submatrix rows (or column), and also to maintain row-sums (or column-sums). (a) nbサイズの配列を保持して、現在のサブマトリクス行(または列)をフラグし、行サム(または列サム)を維持する。 0.69
Expand submatrix operation depends on the elements from row h(u) and column h(v), and the density is calculated by considering these elements, thus requiring maximum nb steps. 展開部分行列演算は列 h(u) と列 h(v) の要素に依存し、密度はこれらの要素を考慮して計算され、最大 nb ステップを必要とする。 0.84
Upon addition of the row (or column), the dependent column-sums (or row-sums) are also updated taking maximum nb steps. 行(または列)を追加すると、依存するカラムサム(または行サム)も最大nbステップで更新される。 0.67
Time complexity of expand operation is therefore O(nb). したがって拡張演算の時間複雑性は O(nb) である。 0.80
(b) Condense submatrix operation removes rows and columns iteratively. b) Condense submatrix 操作は行と列を反復的に削除する。 0.79
A row (or column) elimination is performed by selecting the row (or column) with minimum row-sum (or column-sum) in O(nb) time. O(nb)時間に最小の行サム(または列サム)で行(または列)を選択して行(または列)除去を行う。 0.81
Removed row (or column) affects the dependent column-sums (or row-sums) and are updated in O(nb) time. 削除された行(または列)は依存するカラムサム(または行サム)に影響を与え、O(nb)時間で更新される。 0.65
Time complexity of a row (or column) removal is therefore O(nb). したがって、行(または列)削除の時間複雑性は O(nb) である。 0.78
Condense submatrix removes rows (or columns) that were once added by the expand submatrix operation which in worse case is O|E |. Condense submatrixは拡張サブマトリクス演算によって一度追加された行(または列)を削除します。 0.80
Expand and condense submatrix operations are performed for nr matrices. nr行列に対して展開および凝縮サブ行列演算を行う。 0.73
Likelihood score calculation depends on elements from row h(u) and column h(v), and takes O(nr ∗ nb) time for nr matrices. 確率スコアの計算は列 h(u) と列 h(v) の要素に依存し、nr 行列に対して o(nr ∗ nb) の時間を取る。 0.81
Therefore, the total time complexity of Algorithm 2 is O(nr ∗ n2 b + |E | ∗ nr + |E | ∗ nr ∗ nb + |E | ∗ nr ∗ nb + |E | ∗ nr ∗ nb) = O(nr ∗ n2 Proposition 4. したがって、アルゴリズム 2 の総時間複雑性は o(nr ∗ n2 b + |e | ∗ nr + |e | ∗ nr ∗ nb + |e | ∗ nr ∗ nb + |e | ∗ nr ∗ nb) = o(nr ∗ n2 proposition 4 である。 0.92
Memory complexity of Algorithm 2 is O(nr ∗ n2 b). アルゴリズム2のメモリ複雑性は O(nr ∗ n2 b) である。 0.81
Proof. Memory complexity of the H-CMS data structure is O(nr ∗ n2 b). 証明。 H-CMSデータ構造のメモリ複雑性はO(nr ∗ n2 b)である。 0.72
To keep current submatrix information, we utilize nb-sized arrays similar to Proposition 2. 現在のサブマトリクス情報を保持するために,提案2に類似したnbサイズの配列を用いる。 0.62
For nr matrices, submatrix information requires O(nr ∗ nb) memory. nr行列の場合、サブ行列情報はo(nr ∗ nb)メモリを必要とする。 0.67
Hence, total memory complexity of Algorithm 2 is O(nr ∗ n2 したがって、アルゴリズム2の総メモリ複雑性はO(nr ∗ n2)である。 0.70
b + nr ∗ nb) = O(nr ∗ n2 b). b + nr ∗ nb) = o(nr ∗ n2 b) である。 0.94
b + |E | ∗ nr ∗ nb). b + |E | ∗ nr ∗ nb)。 0.84
E Graph Anomalies-Proofs E Graph Anomalies-Proofs 0.78
E.1 Proofs: ANOGRAPH Lemma 1. E.1 Proofs: ANOGRAPH Lemma 1。 0.87
Let S∗ and T ∗ be the optimum densest sub-matrix solution of M with density D(M, S∗, T ∗) = dopt. S∗ と T ∗ を密度 D(M, S∗, T ∗) = dopt の M の最も高密度な部分行列解とする。
訳抜け防止モード: S∗ と T ∗ を密度 D(M,) を持つ M の最適高密度部分行列解とする。 S∗ , T ∗ ) = dopt 。
0.82
Then ∀u ∈ S∗ and ∀v ∈ T ∗, すると、u ∈ s∗ と sv ∈ t ∗ である。 0.50
R(M, u, T ∗) ≥ τS∗ ; R(M, u, T ∗) ≥ τS∗ ; 0.92
C(M, S∗, v) ≥ τT ∗ C(M, S∗, v) ≥ τT ∗ 0.92
(3) where: τS∗ =E(M, S∗, T ∗) τT ∗=E(M, S∗, T ∗) (3) どこに? τS∗ = E(M, S∗, T ∗) τT ∗=E(M, S∗, T ∗) 0.78
(cid:16) (cid:16) (cid:16)(cid:16) 0.73
1 −(cid:113) 1 −(cid:113) 1 −(cid:113) 1 −(cid:113) 0.86
1 − 1|S∗| 1 − 1|T ∗| 1 − 1|S∗| 1 − 1|T ∗| 0.72
(cid:17) (cid:17) (cid:17)(cid:17) 0.73
, Proof. Leveraging the proof from [49], let’s assume that ∃u ∈ S∗ with R(M, u, T ∗) < τS∗. , 証明。 証明を [49] から活用すると、R(M, u, T ∗) < τS∗ の su ∈ S∗ が成り立つと仮定する。 0.75
Density of submatrix after removing u = (|S∗−1|)|T ∗| = dopt, and that is not possible. u = (|s∗−1|)|t ∗| = dopt を取り除いた後の部分行列の密度は、不可能である。 0.66
Hence, R(M, u, T ∗) ≥ τS∗. したがって、R(M, u, T ∗) ≥ τS∗ である。 0.80
C(M, S∗, v) ≥ τT ∗ can be proved in a similar manner. C(M, S∗, v) ≥ τT ∗ も同様に証明できる。 0.68
Theorem 2. Algorithm 3 achieves a 2-approximation guarantee for the densest submatrix problem. 定理2。 アルゴリズム3は、最も密度の高い部分行列問題に対する2近似保証を達成する。 0.55
which is greater than E(M,S∗,T ∗)−τS∗ E(M,S∗,T ∗)−τS∗ よりも大きいもの 0.83
E(M,S∗,T ∗)−R(M,u,T ∗) E(M,S∗,T ∗)−R(M,u,T ∗) 0.76
(|S∗−1|)|T ∗| (|S∗−1|)|T∗| 0.64
√ √ (cid:113)|Scur|τS∗|Tcur|τT ∗ √ √ (cid:113)|scur|τs∗|tcur|τt ∗ 0.70
Proof. Leveraging the proof from [49], we greedily remove the row (or column) with minimum ∀u ∈ Scur;∀v ∈ row-sum (or column-sum). 証明。 証明を [49] から活用し、最小の su ∈ scur; v ∈ row-sum (または column-sum) で行(または列)を取り除く。 0.70
At some iteration of the greedy process, Tcur, R(M, u, Tcur) ≥ τS∗ and C(M, Scur, v) ≥ τT ∗. 欲求過程のいくつかの反復において、Tcur, R(M, u, Tcur) ≥ τS∗ と C(M, Scur, v) ≥ τT ∗ である。 0.80
Therefore, E(M, Scur, Tcur) ≥ |Scur|τS∗ and E(M, Scur, Tcur) ≥ |Tcur|τT ∗. したがって、E(M, Scur, Tcur) ≥ |Scur|τS∗ および E(M, Scur, Tcur) ≥ |Tcur|τT ∗ である。 0.77
This implies that the density D(M, Scur, Tcur) ≥ √ τS∗ τT ∗. これは密度 D(M, Scur, Tcur) ≥ τS∗ τT ∗ を意味する。 0.88
Putting values of τS∗ and τT ∗ from Lemma 1, and setting sin2 β , we get D(M, Scur, Tcur) ≥ E(M,S∗,T ∗) sin2 α, |T ∗| = 1 ≥ |S∗||T ∗| Lemma 1 から τS∗ と τT ∗ の値を設定し、 sin2 β を設定して D(M, Scur, Tcur) ≥ E(M, S∗,T ∗) sin2 α, |T ∗| = 1 ≥ |S∗||T ∗| を得る。 0.89
|S∗| = 1 (1−cos α)(1−cos β) |S∗| = 1 (1−cosα)(1−cosβ) 0.79
|Scur||Tcur| |Scur||Tcur| 0.34
sin α sin β sin α sin β 0.85
√ √ = 2 cos α √ √ = 2 cos α 0.85
dopt 2 cos β dopt 2 cos β 0.85
2 ≥ dopt 2 . Proposition 5. 2 ≥2。 命題5。 0.63
Time complexity of Algorithm 3 is O(|G| ∗ nr ∗ n2 アルゴリズム3の時間複雑性は O(|G| ∗ nr ∗ n2 である 0.74
b + |E | ∗ nr). b + |E | ∗ nr)。 0.89
15 15 0.85
英語(論文から抽出)日本語訳スコア
Proof. Procedure ANOGRAPH-DENSITY iteratively removes row (or column) with minimum row-sum (or column-sum). 証明。 手順 ANOGRAPH-DENSITY は最小の行サム(または列サム)を持つ行(または列)を反復的に除去する。 0.59
Maximum number of rows and columns that can be removed is nb + nb − 2. 削除できる行と列の最大数は nb + nb − 2 である。 0.76
We keep nb-sized arrays to store the current submatrix rows and columns, and row-sums and column-sums. nbサイズの配列を保持して、現在のサブマトリックス行と列、行サムと列サムを格納します。
訳抜け防止モード: nb - サイズの配列を保持する to store the current submatrix rows and columns, and row - sums and column - sums。
0.70
At each iteration, selecting the row (or column) with minimum row-sum (or column-sum) takes O(nb) time, and updating the dependent row-sums (or column-sums) also O(nb) time. 各イテレーションでは、最小の行サム(またはカラムサム)で行(または列)を選択するとo(nb)時間かかり、依存する行サム(またはカラムサム)もo(nb)時間を更新する。 0.66
Density is calculated in O(nb) time based on the current submatrix row-sum and column-sum. 密度は、現在のサブマトリックス行-sumとカラム-sumに基づいてo(nb)時間で計算される。 0.69
Each iteration takes O(nb + nb + nb) = O(nb) time. 各反復は O(nb + nb + nb) = O(nb) である。 0.74
Hence, the total time complexity of ANOGRAPH-DENSITY procedure is O((nb + nb − 2) ∗ nb) = O(n2 b). したがって、ANOGRAPH-DENSITY 手順の総時間複雑性は O((nb + nb − 2) ∗ nb) = O(n2 b) である。 0.91
Initializing the H-CMS data structure takes O(nr ∗ n2 b) time. H-CMSデータ構造の初期化にはO(nr ∗ n2 b)時間を要する。 0.75
When a graph arrives, ANOGRAPH: (a) resets counts that take O(nr ∗ n2 b) time; (b) updates counts taking O(1) time for every edge update; (c) computes submatrix density that follows from procedure ANOGRAPH-DENSITY and takes O(n2 b) time. ANOGRAPH: (a) resets counts that take O(nr ∗ n2 b) time; (b) updates counts take O(1) time for every edge update; (c) computes submatrix density that following procedure ANOGRAPH-DENSITY and take O(n2 b) time。 0.77
Each of these operations is applied for nr matrices. これらの操作はそれぞれ nr 行列に適用される。 0.74
Therefore, the total time complexity of Algorithm 3 is O(nr ∗ n2 b + |E | ∗ nr), where |E | is the total number of edges over graphs G . したがって、アルゴリズム3の総時間複雑性は O(nr ∗ n2 b + |E | ∗ nr) であり、ここで |E | はグラフ G 上の辺の総数である。 0.83
Proposition 6. Memory complexity of Algorithm 3 is O(nr ∗ n2 b). 第6話。 アルゴリズム3のメモリ複雑性は O(nr ∗ n2 b) である。 0.61
b + |E | ∗ nr + |G| ∗ nr ∗ n2 b + |E | ∗ nr + |G| ∗ nr ∗ n2 0.90
b) = O(|G| ∗ nr ∗ n2 b) = O(|G| ∗ nr ∗ n2 0.92
b + |G| ∗ nr ∗ n2 b + |G| ∗ nr ∗ n2 0.86
Proof. For procedure ANOGRAPH-DENSITY, we keep nb-sized array to flag rows and columns that are part of the current submatrix, and to maintain row-sums and column-sums. 証明。 プロシージャANOGRAPH-DENSITYでは、nbサイズの配列を現在のサブマトリクスの一部であるフラグ行と列に保持し、行サムと列サムを維持する。 0.65
Hence, memory complexity of ANOGRAPH-DENSITY procedure is O(4 ∗ nb) = O(nb). したがって、ANOGRAPH-DENSITY手順のメモリ複雑性は O(4 ∗ nb) = O(nb) である。 0.82
H-CMS data structure requires O(nr ∗ n2 Density computation relies on ANOGRAPH-DENSITY procedure, and takes O(nb) memory. H-CMSデータ構造には、O(nr ∗ n2)密度計算はANOGRAPH-DENSITY法に依存し、O(nb)メモリを必要とする。 0.68
Therefore, the total memory complexity of Algorithm 3 is O(nr ∗ n2 b). したがって、アルゴリズム3の総メモリ複雑性はO(nr ∗ n2 b)である。 0.82
b) memory. E.2 Proofs: ANOGRAPH-K Proposition 7. b) 記憶 E.2 証明: ANOGRAPH-K Proposition 7。 0.63
Time complexity of Algorithm 4 is O(|G| ∗ K ∗ nr ∗ n2 アルゴリズム4の時間複雑性は O(|G| ∗ K ∗ nr ∗ n2 である 0.78
b + |E | ∗ nr). b + |E | ∗ nr)。 0.89
in operations Procedure ANOGRAPH-K-DENSITY has O(n2 b) イン 操作 プロシージャAnoGRAPH-K-DENSITYはO(n2b)を有する 0.61
Proof. Relevant follow from EDGE-SUBMATRIX-DENSI TY procedure, which complexity. 証明。 EDGE-SUBMATRIX-DENSI TYの手順は複雑である。 0.67
EDGE-SUBMATRIX-DENSI TY procedure is called K times, therefore, the total time complexity of ANOGRAPH-K-DENSITY procedure is O(K ∗ n2 b). EDGE-SUBMATRIX-DENSI TY の手順を K times と呼ぶので、ANOGRAPH-K-DENSITY の手順の総時間は O(K ∗ n2 b) である。 0.66
For Algorithm 4, we initialize an H-CMS data structure that takes O(nr ∗ n2 b) time. アルゴリズム4では、O(nr ∗ n2 b)時間を要するH-CMSデータ構造を初期化する。 0.82
When a graph arrives, ANOGRAPH-K: (a) resets counts that take O(nr ∗ n2 b) time; (b) updates counts taking O(1) time for every edge update; (c) computes submatrix density that follows from procedure ANOGRAPH-K-DENSITY and takes O(K ∗ n2 b) time. グラフが到着すると、(a) は O(nr ∗ n2 b) に要するカウントをリセットし、(b) 更新は エッジ更新毎に O(1) に要するカウントを計算し、(c) ANOGRAPH-K-DENSITY から続くサブ行列密度を計算し、O(K ∗ n2 b) に要する。 0.82
Each of these operations is applied for nr matrices. これらの操作はそれぞれ nr 行列に適用される。 0.74
Therefore, the total time complexity of Algorithm 4 is O(nr ∗ n2 b + |G| ∗ K ∗ nr ∗ n2 b + b + |E | ∗ nr), where |E | is the total number of edges |E | ∗ nr + |G| ∗ nr ∗ n2 b) = O(|G| ∗ K ∗ nr ∗ n2 over graphs G . したがって、アルゴリズム 4 の総時間複雑性は O(nr ∗ n2 b + |G| ∗ K ∗ nr ∗ n2 b + |E | ∗ nr) であり、ここで |E | は辺の総数 |E | ∗ nr + |G| ∗ nr ∗ n2 b) = O(|G| ∗ K ∗ nr ∗ n2 である。 0.89
Proposition 8. Memory complexity of Algorithm 4 is O(nr ∗ n2 b). 命題8。 アルゴリズム4のメモリ複雑性は O(nr ∗ n2 b) である。 0.65
directly time Proof. The density of K submatrices is computed independently, and the memory complexity of Algorithm procedure ANOGRAPH-K-DENSITY is the same as the memory complexity of EDGE-SUBMATRIX-DENSI TY procedure i.e. 直接時間 証明。 Kサブマトリクスの密度は独立に計算され、アルゴリズム手順ANOGRAPH-K-DENSITYのメモリ複雑性はEDGE-SUBMATRIX-DENSI TYのメモリ複雑性と同じである。 0.73
O(nb). Maintaining the H-CMS data structure requires O(nr ∗ n2 b) memory. O(nb)。 H-CMSデータ構造を維持するには、O(nr ∗ n2 b)メモリが必要である。 0.69
Density computation relies on ANOGRAPH-K-DENSITY procedure, and it requires O(nb) memory. 密度計算はANOGRAPH-K-DENSITYプロシージャに依存しており、O(nb)メモリを必要とする。 0.66
Therefore, the total memory complexity of Algorithm 4 is O(nr ∗ n2 b). したがって、アルゴリズム4の総メモリ複雑性はO(nr ∗ n2 b)である。 0.83
F Experimental Setup All experiments are carried out on a 2.4GHz Intel Core i9 processor, 32GB RAM, running OS X 10.15.3. F 実験装置 すべての実験は、2.4ghz intel core i9プロセッサ、32gb ram、os x 10.15.3で動作する。 0.71
For our approach, we keep nr = 2 and temporal decay factor δ = 0.9. nb = 32 to have a fair comparison to MIDAS which uses nb 2 = 1024 buckets. このアプローチでは、nr = 2 と時間減衰係数 δ = 0.9.nb = 32 を、nb 2 = 1024 バケットを使用するMIDASと公正に比較する。 0.75
We keep K = 5 for Algorithm 4. アルゴリズム 4 に対して K = 5 を保持する。 0.75
AUC for graph anomalies is shown with edge thresholds as 50 for DARPA and 100 for other datasets. グラフ異常のAUCは、DARPAでは50、他のデータセットでは100としてエッジしきい値で示される。 0.61
Time window is taken as 30 minutes for DARPA and 60 minutes for other datasets. 時刻ウィンドウはDARPAで30分、その他のデータセットで60分と設定されている。 0.61
16 16 0.85
英語(論文から抽出)日本語訳スコア
G Additional Results Table 6 shows the performance of ANOGRAPH and ANOGRAPH-K for different time windows and edge thresholds. G 追加結果 表6は、異なる時間窓とエッジしきい値に対するANOGRAPHとANOGRAPH-Kの性能を示す。 0.80
The edge threshold is varied in such a way that a sufficient number of anomalies are present within the time window. エッジしきい値は、時間ウィンドウ内に十分な数の異常が存在するように変化する。 0.69
ANOGRAPH and ANOGRAPH-K have performance similar to that in Table 4. ANOGRAPHとANOGRAPH-Kは、Table 4と同様の性能を持つ。 0.80
Table 6: AUC when detecting graph anomalies. 表6: グラフ異常を検出する際のAUC。 0.73
Dataset DARPA データセット DARPA 0.74
ISCX-IDS2012 ISCX-IDS2012 0.47
CIC-IDS2018 CIC-IDS2018 0.47
CIC-DDoS2019 CIC-DDoS2019 0.47
Time Edge Window Threshold 25 50 50 100 時間 Edge Window Threshold 25 50 50 50 100 0.85
15 30 60 60 15 30 60 60 0.85
15 30 60 60 15 30 60 60 0.85
15 30 60 60 15 30 60 60 0.85
15 30 60 60 15 30 60 60 0.85
25 50 50 100 25 50 50 100 0.85
25 50 50 100 25 50 50 100 0.85
25 50 50 100 25 50 50 100 0.85
ANOGRAPH ANOGRAPH-K アノグラフアノグラフk 0.47
0.835 ± 0.001 0.835 ± 0.002 0.747 ± 0.002 0.823 ± 0.000 0.945 ± 0.001 0.949 ± 0.001 0.935 ± 0.002 0.950 ± 0.001 0.945 ± 0.004 0.959 ± 0.000 0.920 ± 0.001 0.957 ± 0.000 0.864 ± 0.002 0.861 ± 0.003 0.824 ± 0.004 0.946 ± 0.002 0.835 ± 0.001 0.835 ± 0.002 0.747 ± 0.002 0.823 ± 0.000 0.945 ± 0.001 0.949 ± 0.001 0.935 ± 0.002 0.950 ± 0.001 0.945 ± 0.004 0.959 ± 0.000 0.920 ± 0.001 0.957 ± 0.000 0.864 ± 0.002 0.861 ± 0.003 0.824 ± 0.004 0.946 ± 0.002 0.51
0.838 ± 0.001 0.839 ± 0.002 0.748 ± 0.001 0.825 ± 0.001 0.945 ± 0.000 0.948 ± 0.000 0.933 ± 0.002 0.950 ± 0.001 0.947 ± 0.006 0.959 ± 0.001 0.920 ± 0.001 0.957 ± 0.000 0.863 ± 0.003 0.861 ± 0.003 0.825 ± 0.005 0.948 ± 0.002 0.838 ± 0.001 0.839 ± 0.002 0.748 ± 0.001 0.825 ± 0.001 0.945 ± 0.000 0.948 ± 0.000 0.933 ± 0.002 0.950 ± 0.001 0.947 ± 0.006 0.959 ± 0.001 0.920 ± 0.001 0.957 ± 0.000 0.863 ± 0.003 0.861 ± 0.003 0.825 ± 0.005 0.948 ± 0.002 0.51
H Baselines We use open-source implementations of DENSESTREAM [1] (Java), SEDANSPOT [11] (C++), MIDAS-R [3] (C++), PENminer [12] (Python), F-FADE [13] (Python), DENSEALERT [1] (Java), and ANOMRANK [14] (C++) provided by the authors, following parameter settings as suggested in the original paper. Hベースライン DENSESTREAM [1] (Java)、SEDANSPOT [11] (C++)、MIDAS-R [3] (C++)、PENminer [12] (Python)、F-FADE [13] (Python)、DENSEALERT [1] (Java)、ANOMRANK [14] (C++)のオープンソース実装を使用し、原論文で提案されているパラメータ設定に従う。 0.77
For SPOTLIGHT [2], we used open-sourced implementations of Random Cut Forest [55] and Carter Wegman hashing [56]. SPOTLIGHT [2]では、Random Cut Forest [55] と Carter Wegman hashing [56] のオープンソース実装を使用しました。 0.78
H.1 Edge Anomalies 1. H.1エッジ異常1。 0.63
SEDANSPOT: • sample_size = 10000 • num_walk = 50 • restart_prob 0.15 セダンポット • sample_size = 10000 • num_walk = 50 • restart_prob 0.15 0.44
2. MIDAS: The size of CMSs is 2 rows by 1024 columns for all the tests. 2. MIDAS: CMSのサイズは、すべてのテストで2行×1024列です。 0.80
For MIDAS-R, the MIDAS-Rについて 0.66
decay factor α = 0.6. 崩壊係数α = 0.6。 0.69
3. PENminer: • ws = 1 • ms = 1 • view = id • alpha = 1 • beta = 1 • gamma = 1 3. PENminer: • ws = 1 • ms = 1 • view = id • alpha = 1 • beta = 1 • gamma = 1 0.85
4. DENSESTREAM: We keep default parameters, i.e., order = 3. 4. DENSESTREAM: デフォルトパラメータ、すなわちorder = 3を維持します。 0.80
17 17 0.85
英語(論文から抽出)日本語訳スコア
5. F-FADE: • embedding_size = 200 • W_upd = 720 • T_th = 120 • alpha = 0.999 • M = 100 5. F-FADE • embedding_size = 200 • W_upd = 720 • T_th = 120 • alpha = 0.999 • M = 100 0.82
For t_setup, we always use the timestamp value at the 10th percentile of the dataset. t_setupでは、常にデータセットの10分の1のタイムスタンプ値を使用します。 0.66
H.2 Graph Anomalies 1. H.2グラフ異常 1. 0.73
SPOTLIGHT: • K = 50 • p = 0.2 • q = 0.2 SPOTLIGHT: • K = 50 • p = 0.2 • q = 0.2 0.93
2. DENSEALERT: We keep default parameters, i.e., order = 3 and window=60. 2. DENSEALERT: デフォルトパラメータ、すなわちorder = 3とwindow=60を保持します。 0.83
3. ANOMRANK: We keep default parameters, i.e., damping factor c = 0.5, and L1 changes of node score vectors threshold epsilon = 10−3. 3. ANOMRANK: デフォルトパラメータ、すなわちダンピング係数 c = 0.5 とノードスコアベクトルの L1 変化は、しきい値 epsilon = 10−3 を保持する。 0.81
We keep 1/4th number of graphs for initializing mean/variance as mentioned in the respective paper. 各論文で述べた平均/分散を初期化するグラフの1/4数を保持する。 0.64
18 18 0.85
                                     ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。