﻿ 一种增量并行式动态图异常检测算法<sup>*</sup>
 文章快速检索 高级检索

Incremental and parallel algorithm for anomaly detection in dynamic graphs
HAN Tao, LAN Yuqing, XIAO Limin, LIU Yanfang
School of Computer Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
Received: 2017-01-16; Accepted: 2017-02-06; Published online: 2017-03-23 16:47
Corresponding author. LAN Yuqing, E-mail: lanyuqing@buaa.edu.cn
Abstract: Financial fraud behavior, network intrusion and suspicious social actions can be detected by structural anomaly detection in graphs. The existing anomaly detection algorithms require high computational complexity and cannot process large-scale dynamic graphs. So an incremental and parallel algorithm is proposed to discover and detect abnormal patterns in dynamic graphs effectively and efficiently. The whole graph was partitioned into subgraphs by time sliding windows. N subgraphs in time sliding windows were processed in parallel by minimum description length (MDL) principle to discover both normal and abnormal patterns. Structural outliers can be detected gradually in parallel based on normal patterns. The results of experiments conducted in multiple large-scale graphs show that the precision rate for detecting the abnormal patterns of dynamic graph reaches 96%, recall rate reaches 85%, and running time reduces by an order of magnitude. The impact of the size of sliding windows and the number of parallel on running time of the algorithm is also discussed.
Key words: anomaly detection     incremental     parallel     sliding window     minimum description length (MDL) principle

1 相关工作

1) 当有2个模式都能很好地匹配原始图时，MDL原理选择“最简单”的模式，即选择压缩率更高的描述。这也反映了奥卡姆剃刀对简单理论的优先选择。

2) MDL原理是一致的。随着数据量的不断增加，中间过程产生的正常模式收敛于真正的正常模式。

1) 初始化

a.每个子图发现top-M正常模式。

b.每个子图等待所有子图都完成发现它们正常模式。

2) 迭代处理

a.如果序号在最前面的子图超过了阈值T(基于一定的标准，例如可处理的子图数量，或者子图的时间戳)，那么把这些子图移除，不进行下一步分析。

b.判断是否重新生成正常模式，若为TRUE，则跳转到步骤d。

c.否则，从新子图中找到top-M标准模式。

d.从所有活动的子图中判定基准模式S′。

e.如果(S′！=S)，每个子图基于S′找到新的异常子结构。

f.否则只有新子图检测异常的子结构。

g.评估所有子图的异常子结构，并且找到最可能是异常的子结构。

h.重复上述过程。

2.2 算法分析

1) 正常模式描述代价

A.结点个数N，属性数量L，需要的信息量为(lb N+lb L)bit。

B.记录正常模式的个数M，需要lb M bit。

C.记录在寻找正常模式过程中，对l个属性进行检测，需要lb l bit。

D.描述每个正常模式中的结点信息，需要

E.描述正常模式之间的连接关系，理论上它们之间的连接越少越好，eij表示正常模式之间的边个数。描述的代价为

F.描述每个正常模式中所包含的属性信息，需要

2) 图描述代价

A.用期望来描述正常模式内部的联系，表示正常模式中结点之间的关系。正常模式S的结点数为n，边数为e，因此，pi=p(S=1)=e/n2，描述所需要的代价为

B.对每个正常模式中的属性信息，设每个正常模式中属性包含ai的结点个数n(ai)，则p(ai)=n(ai)/ni，则在每个正常模式中的属性描述代价为

3 实验和评估

 数据名称 类型 结点个数 边个数 YouTube 无向图 1 134 890 2 987 624 LiveJ 有向图 484 751 68 993 773 Math 有向时序图 24 818 50 650

3.1 效率

3.2 准确率、召回率和ROC

 图 4 准确率和召回率 Fig. 4 Accurate rate and recall rate

ROC曲线是一种对于灵敏度进行描述的功能图像。ROC曲线可以通过描述真阳性率(True Positive Rate，TPR)和假阳性率(False Positive Rate，FPR)来实现。最好的检测方式是在左上角的点，即ROC空间坐标轴(0, 1)点，它代表 100%灵敏(没有假阴性)和100%特异(没有假阳性)。完全随机的检测的任一结果对应的准确度都是50%。如图 5所示，虚线表示真阳性率和假阳性率都为0.5的随机结果，在此虚线上方的结果都比随机结果的效果好；坐标上(0，1)点的实心三角表示理想的结果，3个实心圆点分别是3个数据集的ROC结果，分别为0.95、0.94和0.98。这3个值都接近(0，1)点，即都接近理想的结果。

 图 5 ROC曲线 Fig. 5 ROC curve
3.3 M值对准确率和召回率的影响

M值表示每个子图中正常模式选取的个数，即top-M。正常模式根据L(S)+ L(G|S)计算的值进行从小到大排序，前M个作为top-M的正常模式。M是根据经验设定的固定值。如果M取值过小，导致每次检测没有包含足够的正常模式，则准确率和召回率下降。如果M取值到一定范围，不会影响算法的准确率和召回率，如图 6所示。

 图 6 M值对准确率和召回率的影响 Fig. 6 Influence of M value on accurate rate and recall rate
4 案例分析

1) 静态图的异常检测算法

 图 7 正常模式和异常模式 Fig. 7 Normal pattern and abnormal pattern

 图 8 DPADS算法在每个子图上的运行时间并标记发现异常的子图 Fig. 8 Running time of DPADS algorithm in each subgraph and marked subgraphs with abnormal pattern

1) T=1个时，最新的小图总是检测到当前的异常子模式(如果存在)。

2) T=5个时，由于插入的异常模式比较少，窗口中仅有一个小图包含一个异常子结构，使得新的子图总是包含当前的最可能为异常的子结构。

3) T=10个时，当异常子结构在小图 85发现的时候，它的异常值低于之前的异常子结构的异常值，所以变成了当前的异常模式(当T=15个时，结果相同)。

 图 9 DPADS算法在合成数据集上随窗口大小变化的运行时间 Fig. 9 Running time of DPADS algorithm on synthetic datasets with different windows size
5 结论

1) 算法大大缩短了运行时间，例如处理结点数为一百万，边数量为三百万的动态图的运行时间为5 h，而其他算法运行时间为21 h。

2) 算法可实现较为优异的检测性能，例如处理边数量约七千万动态图数据检测异常结构准确率达到96%，召回率达到85%。

3) 滑动窗口大小约束了并行处理子图的数量，滑动窗口越大，算法运行时间越少。

4) 动态图不仅由结点和边随时间不断增加，而且还会不断减少。算法先增量并行处理大规模动态图的增加模式，再在此基础上处理边和结点减少的情况。

 [1] AHMED N K, NEVILLE J, KOMPELLA R. Network sampling:From static to streaming graphs[J]. ACM Transactions on Knowledge Discovery from Data(TKDD), 2014, 8 (2): 7:1–7:56. [2] EBERLE W, HOLDER L. Anomaly detection in data represented as graphs[J]. Intelligent Data Analysis, 2007, 11 (6): 663–689. [3] EBERLE W, HOLDER L, GRAVES J. Insider threat detection using a graph-based approach[J]. Journal of Applied Security Research, 2011, 6 (1): 32–81. [4] NOBLE C C, COOK D J. Graph-based anomaly detection[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2003: 631-636. [5] AKOGLU L, MCGLHON M, FALOUSTSOS C. OddBall: Spotting anomalies in weighted graphs[C]//Proceedings of the 14th Pacific-Asia conference on Advances in Knowledge Discovery and Data Mining. Berlin: Springer-Verlag, 2010, 3: 410-421. [6] FEIGENBAUM J, KANNAN S, MCGREGOR A, et al. On graph problems in a semi-streaming model[J]. Theoretical Computer Science, 2005, 348 (2-3): 207–216. DOI:10.1016/j.tcs.2005.09.013 [7] DEMETRESCU C, FINOCCHI I, RIBICHINI A. Trading off space for passes in graph streaming problems[J]. ACM Transactions on Algorithms(TALG), 2009, 6 (1): 6:1–6:17. [8] AGGARWAL G, DATAR M, RAJAGOPALAN S, et al. On the streaming model augmented with a sorting primitive[C]//Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science(FOCS). Washington, D. C. : IEEE Computer Society, 2004: 540-549. [9] SARMA A, GOLLAPUDI S, PANIGRAHY R. Estimating PageRank on graph streams[C]//Proceedings of the 27th ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems. New York: ACM Press, 2008: 69-78. [10] SHIN K, ELIASSI-RAD T, FALOUTSOS C. CoreScope: Graph mining using k-core analysis-Patterns, anomalies and algorithms[C]//2016 IEEE 16th International Conference on Data Mining (ICDM). Washington, D. C. : IEEE Computer Society, 2017: 469-478. [11] BRIDGES R A, COLLINS J P, FERRAGUT E M, et al. Multi-level anomaly detection on time-varying graph data[C]//2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). New York: ACM Press, 2016: 579-583. [12] EBERLE W, HOLDER L. A partitioning approach to scaling anomaly detection in graph streams[C]//2014 IEEE International Conference on Big Data. Washington, D. C. : IEEE Computer Society, 2014: 17-24. [13] AKOGLU L, TONG H, KOUTRA D. Graph based anomaly detection and description:A survey[J]. Data Mining and Knowledge Discovery, 2015, 29 (3): 626–688. DOI:10.1007/s10618-014-0365-y [14] 吴烨, 钟志农, 熊伟, 等. 一种高效的属性图聚类算法[J]. 计算机学报, 2013, 36 (8): 1704–1713. WU Y, ZHONG Z N, XIONG W, et al. An efficient method for attributed graph clustering[J]. Chinese Journal of Computers, 2013, 36 (8): 1704–1713. (in Chinese) [15] EBERLE W, HOLDER L. Incremental anomaly detection in graphs[C]//2013 IEEE 13th International Conference on Data Mining Workshops. Washington, D. C. : IEEE Computer Society, 2013: 521-528. [16] EPASTO A, LATTANZI S, SOZIO M. Efficient densest subgraph computation in evolving graphs[C]//Proceedings of the 24th International Conference on World Wide Web. Geneva: International World Wide Web Conferences Steering Committee, 2015: 300-310. [17] YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth[C]//Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. New York: ACM Press, 2012, 3: 1-3: 8.

#### 文章信息

HAN Tao, LAN Yuqing, XIAO Limin, LIU Yanfang

Incremental and parallel algorithm for anomaly detection in dynamic graphs

Journal of Beijing University of Aeronautics and Astronsutics, 2018, 44(1): 117-124
http://dx.doi.org/10.13700/j.bh.1001-5965.2017.0019