# Distributed Anomaly Detection in Edge Streams using Frequency based Sketch
Datastructures

###### Abstract.

Often logs hosted in large data centers represent network traffic data over a
long period of time. For instance, such network traffic data logged via a TCP
dump packet sniffer (as considered in the 1998 DARPA intrusion attack)
included network packets being transmitted between computers. While an online
framework is necessary for detecting any anomalous or suspicious network
activities like denial of service attacks or unauthorized usage in real time,
often such large data centers log data over long periods of time (e.g., TCP
dump) and hence an offline framework is much more suitable in such scenarios.
Given a network log history of edges from a dynamic graph, how can we assign
anomaly scores to individual edges indicating suspicious events with high
accuracy using only constant memory and within limited time than state-of-the-
art methods? We propose MDistrib and its variants which provides (a) faster
detection of anomalous events via distributed processing with GPU support
compared to other approaches, (b) better false positive guarantees than state
of the art methods considering fixed space and (c) with collision aware based
anomaly scoring for better accuracy results than state-of-the-art approaches.
We describe experiments confirming that MDistrib is more efficient than prior
work.

PVLDB Reference Format:
PVLDB, 15(1): XXX-XXX, 2021.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 15, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/prateekiiest/mdistrib.

##  1\. Introduction

Anomaly detection in dynamic complex graphs has a wide range of applications
including intrusion detection, denial of service attacks and in the financial
sector. Methods like (su2019robust), (zheng2021generative), (he2020mtad)
provide anomaly detection framework mostly in an offline scenario for
timeseries multivariate graphs using recent advancements like Graph Neural
Networks while some methods like (odiathevar2019hybrid) provide a framework
for a hybrid offline-online analysis for finding anomalies using Support
Vector Machines (SVM).

Most large data centers include historical logs of network traffic data over
long stretches of time like monthwise or daywise network activity. Such data
might also be distributed across several nodes / partitions, for instance in a
high performance computing cluster. Since often such distributed data is time
series in nature, hence it is challenging to process and analyze them in
parallel also since there might exist some inter-dependency across several
nodes (see Fig. 1).

Figure 1. Network traffic data distributed across different nodes.

While in an online setting, there has been several proposals in recent years
that can detect anomalous edges with a high accuracy like MIDAS
(bhatia2020midas), Spotlight (eswaran2018spotlight) , there has not been any
rigorous work done for an offline setting phase. While (bhatia2020midas)
performs better than all the recent state of the art methods and can even
process edges in the order of millions in seconds. But in the case of large
network logs that are hosted over months time, and which can consist of
billions of edges, methods like MIDAS still take considerable time to execute.
(For example, for 1 billion edges, MIDAS takes 250 seconds).

In this paper, we thus propose a distributed version of anomalous edge
detection for large time series graphs using constant memory space called
MDistrib as an extension to previous work on MIDAS (bhatia2020midas), thereby
reducing overall edge processing time and faster execution. In addition, we
extend our method for any generalized frequency based sketch data structure
with better theoretical guarantees for frequency estimates and better
theoretical bounds on false positive probability as compared to MIDAS.

Our main contributions in the paper are as follows:

  1. (1)

Distributed Framework: We propose a distributed framework for anomaly
detection in large graphs with better accuracy and performance than state-of-
the-art approaches.

  2. (2)

Constant Memory Space: The corresponding framework provides a constant space
solution to anomaly detection via using sketch based data structures.

  3. (3)

Better Theoretical Guarantees: In subsequent theorems we showcase how the
false positive probability is more tightly bound in case of MDistrib as
compared to MIDAS, while other methods in Table 1 does not showcase such
theoretical bounds.

  4. (4)

Extension to Generalized Frequency based sketches We describe our model based
on a generalized frequency sketch and then showcase it via Count-Min-Sketch :
$\textsc{MDistrib}_{CMS}$ and Apache Frequent Item Sketch :
$\textsc{MDistrib}_{FIS}$.

  5. (5)

GPU enabled anomaly detection In addition to the distributed framework, we
also extend MDistrib to support GPU and showcase via further experiments how
MDistrib performs better in a GPU enabled environment.

  6. (6)

Effectiveness Our experimental results also showcases that MDistrib and its
variants show a high performance in terms of execution (382 - 815 times faster
than other baseline algorithms ) and a high accuracy comparable or better (42%
- 48%) than state of the art methods.

Table 1. Comparison of relevant methods |  SedanSpot ’18 |  (ranshous2016scalable) |  Spotlight |  PENminer |  F-Fade |  MIDAS-R |  MDistrib
---|---|---|---|---|---|---|---
Microcluster Detection | - | - | - | - | - | ✓ | ✔
Constant Memory | ✓ | ✓ | ✓ | - | ✓ | ✓ | ✔
Constant Update Time | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✔
Distributed Processing | - | - | - | - | - | - | ✔
GPU support | - | - | - | - | - | - | ✔

##  2\. Related Work

There have been substantial amount of works done in the area of anomaly
detection from static network data (chandola2009anomaly; bhuyan2013network),
including the current focus on deep learning based predictions (pang2021deep).
The recent deep learning approaches toward anomaly detection have shown
immense promise in learning feature representations or anomaly scores via
neural networks. Many of these models, including the GAN-based models like
EBGAN (zenati2018efficient), fast AnoGAN (schlegl2019f) and BiGAN
(donahue2016adversarial), demonstrate a significantly better performance than
conventional approaches in diverse real-life applications. However, there
exist some limitations that are encountered by deep learning methods
(pang2021deep). The most important of this is dealing with high-dimensional
data. Anomaly detection from large-scale data is challenging with deep
learning approaches. Moreover, given the fact that, as there are limited
amount of labeled anomaly data, it remains a challenge to learn expressive
normality/abnormality representations from the data. Often in an offline
setting, models like neural networks may provide better accuracy but take a
huge amount of time to compute.

The recent interest in anomaly detection from data streams has also
contributed quite a few studies in the literature (tam2019anomaly). The
studies on anomaly detection from streaming graphs is relatively newer. Prior
to this, when anomaly detection was confined to only static data, there were
three types of variants of this problem. This was based on the anomalous
entities appearing in the graph, be it nodes, edges or subgraphs. However,
based on the way the graph is received in a streaming setting, additional
problems emerged in due course of time.

A recent study by Liu et al. performs streaming anomaly detection with
frequency and patterns (liu2021isconna). Their work proposes online algorithms
(termed as Isconna-EO and Isconna-EN) that measure the consecutive presence
and absence of edge records. Though the variants of Isconna demonstrates a
comparatively better accuracy than the state-of-the-art, however it suffers
from parameter tuning. Very recently, Chang et al. have proposed a frequency
factorization approach (termed as F-fade) for anomaly detection in edge
streams (chang2021f).

The novelty that we introduce in the current paper is providing a fast and
scalable parallel framework for distributed sketch based anomaly detection in
edge streams in GPU environment with collision aware optimization.

##  3\. Problem Setting

Let there be a dynamic time-evolving graph $G$ characterized by the stream of
edges $\varepsilon=(e_{1},e_{2},\dots)$, $e_{i}$ denoting
$(u_{i},v_{i},t_{i})$. Here, $u_{i}$ and $v_{i}$ symbolize source and
destination nodes respectively and $e_{i}$ denotes the incoming edge between
them in timestamp $t_{i}$. Given $G$, the concern is how can we detect
anomalous edges and micro-cluster activities in a distributed fashion. In a
network setting, $u_{i}$ and $v_{i}$ may indicate source and destination IP
addresses respectively and edge denoting a connection rpapequest occurring at
timestamp $t_{i}$. Also the graph $G$ can be modelled as a directed multi-
graph indicating that $(u_{i},v_{i})\neq(v_{i},u_{i})$ and edges might appear
more than once between any two specific nodes.

###  3.1. Temporal Scoring

We first present here the temporal scoring approach proposed by our baseline
method (bhatia2020midas).

Figure 2.  Time series of a single source-destination pair (u, v), with a
large burst of activity at time tick 10.

We start by proposing a motivating example via Figure 2 on how MIDAS computes
the anomaly score for each incoming edges. As per Figure 2, considering a
single source destination pair ($u$,$v$), there is a sudden occurrence of
large burst of activity at time instant t=10. So the main motivation is to
detect the immediate displacement in the item frequency from its corresponding
mean. Hence a higher the displacement indicates a higher chances of being an
actual anomaly. Taking forward this intuition, (bhatia2020midas) maintains two
types of Count-Min Sketch (CMS) (cormode2005improved) data structures.
Considering $s_{uv}$ as the total number of edges from node $u$ and $v$ up to
current time tick $t$, this can be stored in a single CMS called Current Sum
Sketch (CS) and likewise all $s_{uv}$ for all possible combinations of nodes
will be stored.

Similarly for the current number of edges between node $u$ and $v$ existing
during the current time tick $t$ can be denoted as $a_{uv}$, which can be
again similarly tracked in a separate CMS called Current Edge Sketch (CE). The
major difference between the two sketches lies only in the fact that after
every time tick $t$, the values in CE needs to be resetted back to 0 in order
to accommodate new information for the next timestamp.

So now, given the estimated frequencies $\hat{s_{uv}}$ and $\hat{a_{uv}}$, how
can we assign corresponding anomaly scores to the edge $u-v$? MIDAS proposes
to use chi-squared goodness-of-fit test as the hypothesis testing framework to
compute such anomaly scores. A major reason to go forward using chi-squared
test is due to avoid the assumption that the edge frequencies follow some
distribution and that using that underlying distributing information some
likelihood estimate for the edge indicating anomaly can be formulated.

The past edges can be divided into two classes: current time tick (t=10) i.e.
$a_{uv}$ and all past time ticks (t¡10) i.e $s_{uv}-a{uv}$.

Hence, the chi-squared statistic which is defined as sum over categories of
$\frac{(observed-expected)^{2}}{expected}$ can be further written as

(1) $\displaystyle
X^{2}=\frac{({observed}_{curr_{t}}-{expected}_{curr_{t}})^{2}}{{expected_{curr_{t}}}}$
$\displaystyle+\frac{({observed}_{past_{t}}-{expected}_{past_{t}})^{2}}{{expected_{past_{t}}}}$
$\displaystyle=(\leavevmode\nobreak\ {a_{uv}}-\frac{\leavevmode\nobreak\
{s_{uv}}}{t})^{2}\frac{t^{2}}{\leavevmode\nobreak\ s_{uv}(t-1)}$

###### Remark 1.

We have avoided the derivation of Equation 1 for simplicity due to the same
derivation structure in Hypothesis testing framework in (bhatia2020midas).

Therefore, given an arriving edge indicated by tuple $(u,v,t)$, our anomaly
score is computed as:

$score((u,v,t))=(\hat{a_{uv}}-\frac{\hat{s_{uv}}}{t})^{2}\frac{t^{2}}{\hat{s_{uv}}(t-1)}$

##  4\. Proposed Distributed Microcluster Detection

Figure 3. MDistribArchitecture

In the offline phase, we may consider a scenario where there exists network
logs consisting of incoming requests during the past month and the data is
partitioned across nodes/clusters by its corresponding timestamp (daywise).

Instead of a linear scan, our proposed framework models the data stream
$S=(d_{1},d_{2},d_{3},\dots d_{t},\dots)$ s.t. $d_{k}=(i_{k},t_{k})$, where
$i_{k}$ indicates the corresponding item and $t_{k}$ denotes the timestamp.
Considering there are $n$ timestamps, for each single timestamp there might be
multiple items which occur. Each of the timestamps can be considered for
parallel processing rather than serially processing. Considering there are
$m+1$ hardware threads in a multi-processor, the stream can be partitioned
into m sub-streams $S_{1},S_{2},S_{3},\dots S_{m}$.

For each substream, we consider only one frequency based sketch data structure
denoted as $CE$. This is employed for maintaining the current frequency per
item. And at the end of $m$ sub-streams we maintain another sketch denoted as
$CS_{t}$ which stores the sum total frequency corresponding to each edge uptil
all such previous substreams. Each such $CE$ sketch data structure indexed by
timestamp is stored under a particular thread Id.

Figure 4. Calculation of CE and CS sketches.

Since $CS$ stores the total sum frequency for a particular source destination
pair ($u_{i},v_{i}$), for a particular time instant $T_{i}$, it can be written
as follows $CS(T_{i})=\sum_{j=0}^{j=i-1}CE(T_{j})$ i.e summation over all
previous current Edge frequency sketches.

Algorithm At the beginning, we propose the formal algorithm for the offline
phase of our proposed MDistrib. Note that, sketch data structures mentioned
here are general frequency based sketch data structures that share
mergeability property. In order to be useful in large distributed computing
environments, the sketches must be mergeable without additional loss of
accuracy. This can be formally stated as $sketch(A+B)\approx sketch(A)\cup
sketch(B)$.

Input: Stream of graph edges distributed across $K$ partitions

Output: Anomaly score of individual edges

1

2$\text{Initialize }m\text{ Current Edge(CE) Sketches}$; $\text{Initialize
}m\text{ Current Sum(CS) Sketches}$

3 while  _$\text{All }K\text{ partitions are visited}$_ do

4

5

6

7 $\text{ Assign}\text{ worker per }m\text{ partition}$

8 for  _$m$ partitions in parallel_ do

9

10

11

12 $\text{Execute }CalculateCE(partition^{m}_{i})\text{ in parallel}$

13

14 for  _$m$ partitions in parallel_ do

15

16

17

18 $\text{Execute }CalculateScore(partition^{m}_{i})\text{ in parallel}$

19

20

21

Output final anomaly scores

Algorithm 1 Distributed Microcluster Detection - Offline

Input: Stream of graph edges for Partition id $\theta$

1 while  _$\text{a new edge }(u,v,t_{\theta})\text{ arrives}$_ do

2

3

4 $\text{Assign edge }(u,v)\text{ to a thread}$

5 $\text{Update }CE^{m}_{i}\text{ data structures for the new edge }uv$

6 EndWhile

Algorithm 2 CalculateCE() – Current Edge Calculation

Input: Stream of graph edges for Partition id $\theta$

Output: Anomaly Scores per edge

1 while  _$\text{a new edge }(u,v,t_{\theta})\text{ arrives}$_ do

2

3 $\text{Assign edge }(u,v)\text{ to a thread}$

4 $\text{Perform merge operation for }CS^{m}_{i}=\sum{CE^{m}_{i}}$

5 $\text{Retrieve updated counts }\hat{a_{uv}}\text{ from }CE^{m}_{i}$

6 $\text{Retrieve updated counts }\hat{s_{uv}}\text{ from }CS^{M}_{i}$

7 Compute Edge Scores

8
$score((u,v,t))=(\hat{a_{uv}}-\frac{\hat{s_{uv}}}{t})^{2}\frac{t^{2}}{\hat{s_{uv}}(t-1)}$

9 Return $score$

10 EndWhile

Algorithm 3 CalculateScore() – Current Edge Score Calculation

###  4.1. MDistrib-CMS $\xrightarrow{}$ Distributed MIDAS using Count Min
Sketch

Here, we follow the exact architecture of MDistrib as proposed above and use
count min sketch for each of the $m$ Current Edge Sketch and Current Sum
Sketch, considering $m$ partitions, with each having $w$ and $b$ number of
hash functions and number of buckets respectively.

Figure 5. CMS with parameters 6x3

For example Figure 5 indicates the basic functionality in a count min sketch
where each item can be hashed into the corresponding slots.

###  4.2. MDistrib-FIS - Distributed MIDAS using Apache Frequent Item sketch

(anderson2017high) introduces Frequent Item Sketch which belongs to a class of
Apache Incubator Datasketches that deals with estimating frequency of items in
a streaming environment and is mainly aimed at applications like Heavy-Hitter
estimation or estimation of counts of objects in a streaming environment. The
Apache Incubator Datasketches framework provide a wrapper api for Frequent
Item sketch with the mergeability functionality where two Frequent Item
Datasketches $f_{1}$ and $f_{2}$ can be merged into one frequent item
datasketch $f_{r}$ with all the frequencies remaining intact
$f_{r}=f_{1}\oplus f_{2}$.

###  4.3. $\textsc{MDistrib}R$ : Distributed MIDAS-R

Similar to MDistrib, we take into account the idea of relation attribute used
in (bhatia2020midas) for both temporal and spatial relations.

Temporal Relations With the idea of most recent edges being a better
representative of the statistic score than previous early edges, for each
timestamp id $Tid$ within the partition interval we apply a decay factor
$\alpha^{\frac{1}{Tid}}$ where $\alpha\in(0,1)$. This is done keeping into
consideration the fact that edges from the recent past should compute to the
anomaly score calculation as well.

Spatial Relations

As it is also important to capture large group of spatially nearby edges: such
as a high out-degree connection from a single source IP address, following
MIDAS’s approach we also consider observing nodes with high degree as they
occur. For this, we create CMS counters $\hat{{}_{a_{u}}}$ and
$\hat{{}_{s_{u}}}$ to approximate the number of edges incident on node $u$ at
the current time tick $t$ and up till $t$ respectively. Hence, for a new
incoming edge $u,v$, we compute the anomaly score for edge $u,v$ as well as
for node $u$ and node $v$ and finally take the maximum of the three scores.

###  4.4. Time complexity Analysis

We focus on time complexity analysis and comparison with respect to MIDAS
since MIDAS has performed significantly well in comparison with SOTA models in
terms of time complexity.

Considering we have $K$ partitions, $P_{j+1},P_{j+2},\dots P_{j+k}$, where
each partition $P_{j+i}$; $\FORALL{i\in[1,K]}$ belonging to timestamp
$T_{j+i}$ includes a $CE$ datasketch. We denote the $CE$ sketch update time as
$T_{CE}$. If the average number of items during $T_{j+i}$ is $\mu$, then
$T_{CE}\approx\mu$ and the total update time for all K partitions under the
MIDAS framework would be $\mu*T_{CE}$. Similarly for calculating the sum of
the previous edges seen uptil time $T_{j+i}$ as per LABEL:eq:mergePerTime it
can be denoted as $T_{CS}=\tau_{c}*(K-1)$ where $\tau$ indicates the merge
time for two datasketches, Since in both MDistriband MIDASthere is merging of
previous current edge sketches, hence $T_{CS}$ remains the same for both.

Comparing the total computation for both the methods, yields

$T_{\textsc{MIDAS}}=\phi[\mu*T_{CE}+\tau_{c}*(K-1)]$

$T_{\textsc{MDistrib}}=\phi[\mu+\tau_{c}*(K-1)+Th_{AllocationTime}],$

s.t. $\phi*K\approx C$ where $C$ denotes the number of total partitions/nodes.

Considering thread allocation time $Th_{AllocationTime}$ to be very negligible
compared to other factors like large number of streaming data points per
partition $\mu$ and large number of partitions $K$, it can be seen that
$T_{\textsc{MIDAS}}$ is much less than $T_{\textsc{MDistrib}}$.

Further we also propose reading items per partition to be distributed across
various subthreads instead of sequential reading, since each edge under a
particular partition/ timestamp can be processed independently of the other.
As a result, update time for $CE$ denoted by $\mu$ can be further reduced to
$\hat{\mu}$ where $\hat{\mu}<\mu$ thus resulting in much faster execution
time.

###  4.5. Better theoretical guarantees

Count Min Sketch Error Estimate

###### Lemma 4.1.

The error estimate encountered via querying edge counts in MDistrib is less
than that of MIDAS by a factor of ($\sum_{x}Count-\max(Count)$)

###### Proof 1.

MDistribCMS has the same sketch architecture as MIDAS, but however presents
with a better theoretical guarantee as shown below:

As per Therrem 1 (cormode2005improved), the estimate $\hat{a}$ from a CMS has
the following guarantees: $a\leq\hat{a}$ with some probability
$1-\frac{\delta}{2}$,

(2) $\displaystyle\hat{a}\leq a+\epsilon*V$

where the values of these error bounds can be chosen by
$w=\lceil{\frac{e}{\epsilon}}\rceil$ and
$d=\lceil\ln(\frac{1}{\delta})\rceil$, $w$ and $d$ being the dimensions of the
CMS. $V$ indicates the total sum of all the counts stored in the data
structure. Again considering $K$ partitions $P_{j+1},\dots P_{j+k}$ , let
$P_{j+\theta}$ where $\theta\in[1,K]$ denote the partition $\theta$. As per
MIDAS the sum sketch for time tick $t$ is computed by summation of all
previous current edge sketches $CE$ uptil $t-1$. Hence for partition $\theta$,
$V_{\theta}^{MIDAS}$ can be written as follows.

$V_{\theta}^{MIDAS}=\sum_{r=1}^{r=\theta-1}V_{r}^{MIDAS}$

$V_{\theta}^{MIDAS}=\sum_{r=1}^{r=\theta}\sum_{p=1,q=1}^{w,d}\text{getCount}_{r}(p,q)$

For MDistrib-$CMS$, however since for the partition $\theta$ we have
$\theta-1$ CE sketches, instead of merging them for computing the same, we can
individually query each of the $\theta-1$ sketches instead of merging them.
Hence in this case,

$V_{\theta}^{\textsc{MDistrib}}=max(V_{r}^{\textsc{MDistrib}})\text{ where
}r\in[1,\theta-1]$

Hence, as per Equation. (2) we compare the estimates of the count retrieved
from the current Sum $CS$ CMS sketch of partition $\theta$ for MDistrib and
MIDAS.

(3) $\text{MIDAS Estimate}:\hat{a_{\theta}}\leq
a+\epsilon*(\sum_{r=1}^{r=\theta-1}\text{count}_{r})$

(4) $\text{MDistrib Estimate}:\hat{a_{\theta}}\leq
a_{\theta}+\epsilon*\max(\text{count}_{1},\dots\text{count}_{\theta-1})$

Since such counts stored in the CMS being non-negative

(5)
$\max(\text{count}_{1},\dots\text{count}_{\theta-1})<=\sum_{r=1}^{r=\theta-1}\text{count}_{r}$

Hence, taking the inequality from 5 we can conclude that the error bound in
the estimate provided by MDistrib is much less than that provided by MIDAS.

(6) $\displaystyle\hat{a_{\theta}}\leq
a_{\theta}+\epsilon*\max(\text{count}_{1},\dots\text{count}_{\theta-1})$
$\displaystyle\leq
a_{\theta}+\epsilon*\sum_{r=1}^{r=\theta-1}\text{count}_{r}$

∎

Apache Frequent Item Sketch Guarantees In case of a Frequent Item Sketch with
configuration $<M,N>$, where $M$ indicates the maximum map size in power of 2
and $N$ being the total weights stored in the map, the error in the estimate
of the frequency of a particular edge is always bounded within some $T$,
$\hat{a}\leq a+T$, where $T$ can be as follows, given $\alpha$ is the load
factor :

(7) $T=\begin{cases}0,&\text{if}\ N<\alpha*M\\\
\epsilon*N,&\text{otherwise}\end{cases}$

Since Frequent Item Sketch has a similar structure as a Count Min Sketch in
terms of the error estimate, the proof for the false positive probability
bound also holds here.

###### Lemma 4.2.

The error estimate encountered via merging two sketches $A$ , $B$ is the same
as that obtained in an original sketch $C$ which contains frequencies all
items that have been inserted to $A$ and $B$ as a whole.

Establishing for Count Min Sketch

Considering count min sketches $A$ and $B$ having dimensions $w\times d$ each
and inserting an item with actual frequency $a$ in both the sketches, then the
error estimate of a particular item can be represented as follows

(8) $\displaystyle\hat{a_{A}}\leq a+\epsilon*V_{A}$

(9) $\displaystyle\hat{a_{B}}\leq a+\epsilon*V_{B}$

where $V_{A}$ and $V_{B}$ indicate the total sum of all the counts stored in
CMS $A$ and $B$ respectively.

By combining Equations. (8) and (9), and since all the elements involved are
($\geq 0$), we get the following.

(10a) $\displaystyle\hat{a_{A}}+\hat{a_{B}}\leq 2a+\epsilon*(V_{A}+V_{B})$
(10b) $\displaystyle\hat{a_{A+B}}\leq 2a+\epsilon*(V_{A}+V_{B})$ (10c)
$\displaystyle\hat{a_{C}}\leq 2a+\epsilon*(V_{C})$

where $\hat{a_{A}}+\hat{a_{B}}=\hat{a_{A+B}}$ indicates the total estimated
frequency of that particular item, had that item be inserted into the sketch
$C$ having same dimension $wxd$ which is a combination of $A$ and $B$. Hence
by this we showcase that the error estimate remains the same even after
merging two Count Min Sketches compared to an original Count Min sketch which
represents a summation of the two other sketches.

###  4.6. Why Distributed MIDAS using Apache Frequent Item sketch is better
than MIDAS using CMS

Frequent Item Sketch only stores those items at any point that’s larger in
freq than the global median frequency, whereas CMS keeps on storing Estimation
Errors. Dimitropoulos et al. have introduced the concept of transient keys,
which are items that are not active and have low frequency relative to the
group, much earlier (dimitropoulos2008eternal).

###  4.7. Space Complexity

Constant Space for MDistrib-CMS

Considering $K$ distributed partitions in our system, at any point we have
only $K$ current Edge $CE$ CMS sketches. After the end of $K$ partitions,
again when we consider the next $K$ partitions, in order to store the previous
iteration’s sum we maintain another CMS. Hence the total space complexity
$(K+1)*(wd)$ where $w$ and $d$ indicate the number of hash functions and
buckets in the CMS structure.

Constant Space for MDistrib-FIS

Similarly for Frequent Item Sketch, the total space complexity can be denoted
as $(K+1)*(M)$ where $M$ is the maximum map size of the data sketch.

###  4.8. Proofs

Proposition 1 : False Positive Probability Error is more tightly bound in case
of MDistrib

Count Min Sketch

As we know for a particular partition $\theta$, our chi-square statistic can
be written as

$\hat{\chi_{\theta}^{2}}=(\hat{a^{\theta}_{uv}}-\frac{\hat{s^{\theta}_{uv}}}{t})^{2}\frac{t^{2}}{\hat{s^{\theta}_{uv}}(t-1)}$

Theorem 1 (False Positive Probability Bound)

Let $\chi^{2}_{1-\frac{\epsilon}{2}}(1)$ be the
$(1-\frac{\epsilon}{2})$-quantile of a chi-squared random variable with 1
degree of freedom. Then:

(11) $\displaystyle P(\hat{\chi^{2}}>\chi^{2}_{1-\frac{\delta}{2}}(1))<\delta$

(bhatia2020midas) mentions that the motivation of the above theorem proposal
is to show that with a threshold of $\chi^{2}_{1-\frac{\epsilon}{2}}(1)$,
$\chi^{2}$ as a test statistic results in a false positive probability of at
most $\delta$.

For CMS guarantees 2 we have the following

(12) $\displaystyle P(\hat{a}\leq a+\tau)\geq 1-\frac{\delta}{2}$

where $\epsilon*V$ is shortened as $\tau$

We define an adjusted version of our earlier score for the total summation
score :

(13) $\tilde{s^{\theta}_{uv}}=\hat{s^{\theta}_{uv}}-\tau$

By combining Equations. 11 and 12 by union bound, with probability of at least
$1-\delta$, we obtain the following.

$\tilde{\chi_{\theta}^{2}}=(\hat{a^{\theta}_{uv}}-\frac{\tilde{s^{\theta}_{uv}}}{t})^{2}\frac{t^{2}}{\tilde{s^{\theta}_{uv}}(t-1)}\\\
$

We denote $\tilde{\chi_{\theta_{MIDAS}}^{2}}$ and
$\tilde{\chi_{\theta_{MDISTRIB}}^{2}}$ as the chi-square test statistic for
MIDAS and MDistrib methodologies respectively.

(14a)
$\displaystyle\tilde{\chi_{\theta_{MIDAS}}^{2}}=(\hat{a^{\theta}_{uv}}-\frac{\tilde{s^{\theta}_{uv_{MIDAS}}}}{t})^{2}\frac{t^{2}}{\tilde{s^{\theta}_{uv_{MIDAS}}}(t-1)}$
(14b)
$\displaystyle\tilde{\chi_{\theta_{MDISTRIB}}^{2}}=(\hat{a^{\theta}_{uv}}-\frac{\tilde{s^{\theta}_{uv_{MDISTRIB}}}}{t})^{2}\frac{t^{2}}{\tilde{s^{\theta}_{uv_{MDISTRIB}}}(t-1)}$

We simplify the equation for MDistrib as it holds the same for MIDAS. From
Equation. (13), Equation. (14b) can be simplified as follows.

(15) $\displaystyle\tilde{\chi_{\theta_{MDISTRIB}}^{2}}=$
$\displaystyle(\hat{a^{\theta}_{uv}}-\frac{\hat{s^{\theta}_{uv_{MDISTRIB}}}-\tau}{t})^{2}\frac{t^{2}}{\tilde{s^{\theta}_{uv_{MDISTRIB}}}(t-1)}$

Considering $a^{\theta}_{uv}\approx\gamma\frac{s^{\theta}_{uv}}{t}$ under the
assumption that the current edge count is always an estimation of the previous
mean plus some positive weight factor,

(16) $\displaystyle\tilde{\chi_{\theta_{MDISTRIB}}^{2}}=$
$\displaystyle(\gamma\frac{\hat{s^{\theta}_{uv_{MDISTRIB}}}}{t}-\frac{\hat{s^{\theta}_{uv_{MDISTRIB}}}-\tau}{t})^{2}\frac{t^{2}}{\tilde{s^{\theta}_{uv_{MDISTRIB}}}(t-1)}$

which can be simplified as considering large value of $t$, that is for higher
timestamps.

$\tilde{\chi_{\theta_{MDISTRIB}}^{2}}\approx\hat{s^{\theta}_{uv_{MDISTRIB}}}(\frac{\gamma-1}{t})\frac{t^{2}}{(t-1)}$

(17)
$\tilde{\chi_{\theta_{MDISTRIB}}^{2}}\approx\hat{s^{\theta}_{uv_{MDISTRIB}}}(\gamma-1)$

(18)
$\tilde{\chi_{\theta_{MIDAS}}^{2}}\approx\hat{s^{\theta}_{uv_{MIDAS}}}(\gamma-1)$

As per Lemma 4.1, we know that
${\hat{s^{\theta}_{uv_{MDISTRIB}}}}\leq{\hat{s^{\theta}_{uv_{MIDAS}}}}$

Hence, by combining both the equations, we get
$\tilde{\chi_{\theta_{MDISTRIB}}^{2}}<\tilde{\chi_{\theta_{MIDAS}}^{2}}$

##  5\. Experiments

In this section, we evaluate our proposed anomaly scoring algorithm MDistrib
and address to answer the following questions:

  1. Q1.

Accuracy: How accurately does MDistrib and its variants detect real-world
anomalies compared to baselines, as evaluated using the ground truth labels?

  2. Q2.

Scalability: How does it scale with input stream length? How does the time
needed to process each input compare to baseline approaches?

  3. Q3.

Execution Time: How fast does the proposed method perform with respect to
baseline methods while generating anomaly scores in the offline phase?

##### Baselines: MIDAS-R, SedanSpot, PENnimer, F-Fade

##### Datasets

In this section, we evaluate performance of MDistrib as compared to other
baselines in Table 3 based on 5 real world datasets : _DARPA_
(lippmann1999results) and _ISCX-IDS2012_ are popular datasets for graph
anomaly detection. According to survey [52], there has been proposal of more
than 30 datasets and it has been recommended to use _CIC-DDoS2019_ and _CIC-
IDS2018_ datasets. We also showcase the same for _CTU-13_ dataset.

Datasets | —V— | —E— | —T—
---|---|---|---
DARPA | 25,525 | 4,554,344 | 46,567
ISCX-IDS2012 | 30,917 | 1,097,070 | 165,043
CIC-IDS2018 | 33,176 | 7,948,748 | 38,478
CIC-DDoS2019 | 1,290 | 20,364,525 | 12,224
CTU-13 | 371,100 | 2,521,286 | 33,090

Table 2. Statistics of the datasets.

Table 2 shows the statistical summary of the datasets. —E— corresponds to the
total number of edge records, —V— and —T— are the number of unique nodes and
unique timestamps, respectively.

####  5.0.1. Hyperparameters chosen for baselines

We hereby mention the hyperparameters used by the corresponding baselines.

Spotlight

  * •

sample size = 10000

  * •

num walk = 50

  * •

restart prob = 0.15

MIDAS The size of CMSs is 2 rows by 1024 columns for all the tests. For
MIDAS-R, the decay factor $\alpha$ = 0.6.

PENimer

  * •

ws =1

  * •

ms =1

  * •

alpha = 1

  * •

beta =1

  * •

gamma =1

F-Fade

  * •

embedding size = 20

  * •

$W_{upd}$ = 720

  * •

$T_{th}$ = 120

  * •

alpha = 0.999

  * •

M =100

For $t_{setup}$, we always use the timestamp value at the 10th percentile of
the dataset.

All methods output an anomaly score corresponding to the incoming edge, a high
anomaly score implying more anomalousness. As part of the experiments, we
follow the same suite as the baseline papers in reporting the Area under the
ROC Curve (using the True Positive Rate TPR and the False Positive Rate FPR)
and the corresponding running time. All experiments for calculating the AUC
are averaged for 8 runs and the mean is reported along with its spread.

###  5.1. Experimental Setup

All experiments are carried out on a $1.00GHz$ Intel Core $i5$ processor,
$8GB$ RAM, running OS $Win10$ $10.0.19042$. We used an open-sourced
implementation of MIDAS, provided by the authors, following parameter settings
as suggested in the original paper ($2$ hash functions, $719$ buckets). We
implement MDistrib in python using dask framework. We follow the same
parameter settings as ($2$ hash functions, $719$ buckets).

###  5.2. Q1. Accuracy

Table 3 includes the AUC of edge anomaly detection baselines along with our
two proposed methods $\textsc{MDistrib}_{CMS}-R$ and
$\textsc{MDistrib}_{FIS}-R$. PENimer is unable to finish in large datasets
like CIC-DDos and CIC-IDS within 10 hours range, thus we do not report the
result. Among the baseline results $\textsc{MDistrib}_{FIS}-R$ and
$\textsc{MDistrib}_{CMS}-R$ both provide better accuracy results than the
baselines on datasets like DARPA, CIC-DDoS and ISCX-IDS.

AUC vs Running Time Figure 6. plots accuracy (AUC) vs. running time (log
scale, in seconds) on the Darpa dataset. As we can see both
$\textsc{MDistrib}_{FIS}-R$ and $\textsc{MDistrib}_{CMS}-R$ achieve higher
accuracy results than the base lines in considerable less time.

Figure 6. AUC vs running time when detecting edge anomalies from the DARPA
dataset.

Methods | DARPA | CIC-DDoS | CIC-IDS | CTU-13 | ISCX-IDS
---|---|---|---|---|---
MDistrib_CMS-R | 0.953 ±0.001 | 0.986 ±0.003 |  0.979 ±0.01 | 0.908 ±0.002 | 0.806 ±0.001
Spotlight | 0.89 ±0.001 | 0.67 ±0.002 | 0.42 ±0.003 | 0.74 ±0.002 | 0.63 ±0.001
MIDAS-R | 0.95 ±0.005 | 0.984 ±0.003 | 0.96 ±0.01 | 0.973 ±0.005 | 0.81
PENimer | 0.87 | - | - | 0.604 | 0.51
F-Fade | 0.91 ±0.005 | 0.72 ±0.02 | 0.61 ±0.03 | 0.802 ±0.001 | 0.62 ±0.004
MDistrib_FIS-R |  0.98 ±0.0004 |  0.986 ±0.001 | 0.96 ±0.0005 |  0.92 ±0.004 |  0.93 ±0.0001

Table 3. AUC scores of the proposed methods in comparison with the edge
anomaly detection baselines. The best values over a column (for a specific
dataset) are shown in bold.

Methods | DARPA | CIC-DDoS | CIC-IDS | CTU-13 | ISCX-IDS
---|---|---|---|---|---
MDistrib_CMS-R | 857ms | 971ms | 741ms | 436ms | 3.7s
Spotlight | 129.1s | 697.6s | 209.6s | 86s | 19.5s
MIDAS-R | 1.4s | 2.2s | 1.1s | 0.8s | 5.3s
PENimer | 5.21hrs |  $\geq$ 24hrs | 10hrs | 8hrs | 1.3hrs
F-Fade | 317.8s | 18.7s | 279.7s | 19.2s | 137.4s
MDistrib_FIS-R | 832ms | 962ms | 764.8s | 441ms | 3.1s

Table 4. Running time when detecting edge anomalies.

‘

###  5.3. Q2. Scalability

Figure 7. MDistribw.r.t MIDAS - Scalability with respect to the number of
edges

In Figure 7 we showcase how via distributed processing of individual nodes and
computing the sketch results in significant time improvement of execution. We
plot the wall clock time needed to run the first $2^{12},2^{13},2^{14}\dots
2^{22}$ number of edges of the DARPA dataset for both MDistrib and MIDAS. At
the same time, we showcase that the number of edges increase exponentially,
MDistrib shows linearity of increase in execution time similarly as compared
to MIDAS for number of partitions = 1463.

###  5.4. Q3. Execution : GPU based Execution

In addition to our proposed solution, we also extend MDistrib to a GPU
setting. For this we created a dask cluster hosted on Saturn
cloud111https://saturncloud.io/ and ran our analysis on the same. We use
Python’s JupyterLab for running our experiments with server configuration of
T4-XLarge, with 4 crores, 16GB of RAM and 1 GPU. In addition we use
cuDF222https://docs.rapids.ai/api/cudf/stable/, python’s GPU dataframe library
to store our data.

We showcase here the experiments done for the DARPA dataset here. Using the
above configurations and setting $workers=3$, we achieved an execution time of
672ms which is $1.37$ times faster than MDistrib in non-GPU environment.

(a) Saturn Cloud DashBoard Status for workers = 3

(b) GPU Utilization

Figure 8. Running MDistrib in a GPU environment with Saturn Cloud

As a separate experiment, we increased the number of workers to 10 and
achieved execution time of 438ms on DARPA dataset. Further we showcase the GPU
utilization and the task status for each of the 10 worker threads. Fig. 9(a)
shows the GPU utilization for MDistrib using partitions = 1463 and number of
workers = 10.

(a) GPU utilization

(b) Resource utilization for 10 workers

(c) Task progress status

Figure 9. Results obtained by setting the number of workers to 10 in
SaturnCloud.

Figure 8(a) and 9(c) shows the task status for worker numbers =3 and 10
respectively. Each of the task status depicts the number of underlying
processes involved like reading data from a partition and processing it and
writing it. Figure 9(b) thus depicts the resources like number of threads or
cpu cycles being utilized during the program execution by each of the 10
workers.

##  6\. Conclusion

In this paper, we proposed MDistribwhich uses a distributed strategy to detect
anomalous edges in an offline setting. We further showcase that through our
distributed sketch architecture, we achieve a better false positive
theoretical guarantee and as well as better performance in terms of running
time as compared to state of the art methods for large graphs (billion number
of edges). We also extend our method to GPU enabled environment to showcase
the applicability of our system in high performance computing environments.
Lastly we showcased a generalized model of our framework that can use any
frequency based sketch and achieve good accuracy results in detecting
suspicious anomalies.