ML CLUB | 面向图数据的异常检测综述概述

我们首先从图数据异常说起，图数据(Graph Data)能够表达现实世界中复杂的交互关系，近年来得到了研究者们的广泛关注，而图数据异常检测也是相关数据挖掘领域一项重要任务，但是面向图数据的异常定义和检测方法都有别于传统的数据挖掘算法范式，这里我们举三个例子简要说明。

在金融交易领域，传统的异常检测挖掘范式只统计单交易渠道的统计异常值检测信用卡套现，但是随着比特币、跨境电商、电子支付的流行，电子交易日趋复杂，如上图即为EA公司支付交易数据，可见金融交易网络节点涉及多属性(游戏titile，交易货币，支付方式，支付地点)、多连接（交易渠道、IP代理）等异构图结构,我们需要引入多视角嵌入(Multi-view Embedding)的方法检测其中的异常交易信息避免损失。

如果金融图数据呈现属性与交互复杂的趋势，那么社交网络图结构则呈现规模扩大、交互复杂、应用广泛的特性，上文即为《权力的游戏》中不同势力的分布图，其中一项有意思的工作就是寻找不同聚类，也就是不同势力之间的活跃人物，在图结构中被称为margin node/edge，他们对故事的发展通常起关键性作用。

第三个例子较为经典：安然电子邮件数据集，将安然公司的电子邮件图结构转化为最上文树状图，可以看出图拓扑结构的变化通常与安然公司的管理层变迁相对应，所以基于图拓扑结构的异常检测可以为我们的事件异常检测提供有力的辅助。

异常检测的应用极其广泛，然而针对图数据的应用相对较少，我们将在下文的研究难点部分给出相关研究的瓶颈。

图数据异常检测在图数据任务体系中与图分类任务、Graph Entropy与graph edit distance理论、图模式挖掘这些任务关联较大。在整理相关研究内容与综述时，我们也重点关注了这些关键词。

•异常检测(Anomaly Detection)

•动态网络(Dynamic network/Time-evolving graph/Dynamic Graph)

•图神经网络与深度学习(Graph Neural Network)

•新颖模式检测(Novelty Detection)

•社群检测(Community Detection)

•图论方法(Graph Entropy Theory/Graph Edit Distance)

相关研究同时存在以下的研究难点：

1. 当异常实体或者异常事件是恶意行为的结果时，恶意对象通常会调整自己，使异常的观察结果看起来类似正常分布，从而使定义正常行为的任务变得更加困难，这一部分主要体现于社交网络的异常社群检测与金融诈骗检测

2. 正常行为的概念随时间演化可能会发生变化，产生概念漂移(Concept Shift) 。概念漂移起源于数据挖掘领域，指正常分布的概念随时间不断发生变迁，如电信网络的运营商策略与套餐变化等。

3. 针对图数据的嵌入空间， 定义一个演化过程中包含所有可能的正常行为的正常分布区域是非常困难的，且难以可视化。

这一部分体现于SVM分类器等，传统的超平面不再适用，需要引入超球面、共享的子空间等工具，并在软约束(Soft Constraint)条件下学习一个紧超球体，从而使用单分类支持向量机区分正常与异常实体。

我们简单地汇总了针对图数据的一些异常定义：

很多图异常检测的数据异常样本占比极低，上述三个图分别展示了一种高维嵌入、超平面、聚类定义下的稀疏性体现，稀疏性也意味着异常检测与传统的分类算法范式存在不同之处。

异常检测任务的数据通常没有或缺少异常标注，且在高维空间中寻找准确的标签通常是不可行的，在深度学习范式下通常可以通过表征迁移学习(Representation Transfer Learning)或者数据增强(Data Augmentation)解决，这里不再赘述，但是数据增强方法在图数据实现通常较为困难。

由于属性和拓扑结构信息的复杂组合，例如超图、异构图、复杂网络等涉及多属性、 多连接的图结构较难处理，针对上述网络的异常检测算法较少，如基于幂律定理的社交网络异常检测OddBall:提出的 OddBall 算法即基于复杂网络 (Complex Network) 下幂律性质的假设，计算 每个节点在其邻域的幂律性质，检测异常节点与显性边，此类方法计算效率较高，适用大规模网络分析，但如果分布不满足幂律性质则会失效。

我们整理了一份关于图异常检测工程的常见研究框架，从上而下的顺序通常代表了相关研究顺序。

这里我们将已有方法按照静态图与动态图两部分进行方法分类，但是相同方法对数据分布的假设是大致相同的，受限于篇幅我们仅按照方法类别整理了已有的应用，对静态图、动态图不做区分，并略去了应用较为广泛的基础方法介绍。

这里需要强调，每一类异常检测方法相对依赖对分布数据的先验假设。

假设：给定一个序列的图，序列中相似的图共享部分特征，基于上述特征计算度量距离，针对序列图中邻接的图作为研究对象，正常对象距离较近，而异常对象往往偏离他们的近邻。

但是此类方法面对大尺寸、长时间的复杂动态图异常检测任务存在计算资源消耗大、计算效率较低的问题，因为其本质上是寻找最大共通子图或特征的组合 优化问题，计算效率不能优化为多项式时间。

此类方法一般忽略了动态图的演化趋势或者周期性趋势。为了解决此类问题，一种同样基于邻近性的取代方法是基于 密度的动态图异常检测算法。

基础假设：异常节点、边或者子图的相对密度与正常实体的相对密度存在不同

密集子图检测任务：动态图序列中的密集子图块通常代表欺诈或其他异常行为，

•给定一个图 𝐺(𝑉 ,𝐸)，目标为寻找一个节点子集 𝑆 ∈ 𝑉 , 满足节点子集的平均度 𝑑(𝑆) 最大  

分布假设：假设动态图中的异常属于数量较少或者密度较低的聚类，则我们计算节点或边到距离它们最近的聚类质心的距离进行聚类计算，并假设距离越远发生异常的可能性越大

通用方法：图分划方法/聚类算法/社群检测/最大准集团检测(k-clique)

研究难点：聚类划分/大量图数据的压缩描述/社群规模/演化社群的定义/计算复杂度

分布假设：在现实的大规模稀疏图上，利用平均度衡量子图密 度的密集子图检测通常会获得一张极大的图，缺乏应用意义

基础方法：k-Clique下的最大集团检测，但是其限制过于严格，于是有了改进算法OQC,避免了最大集团检测严苛的限制条件，优化了 针对密集子图的密度度量

最优准集团检测结合了聚类算法思想与密集子图检测的度量工具，能够在实际应用中更好的在子图规模约束下寻找动态图实际应用中更 “密集” 的子图，然而该算法约束较强，其优化目标与上述社群检测算法存在本质性的不同

分类假设：满足一般的机器学习分类假设，图数据一类或多类定义为异常

分类方法通常适用于监督学习，通常模型较为简单，计算效率高，适用于网络入侵、移动互联网等在线异常检测场景。但是此类方法高度依赖训练 数据的标注与分布，模型本身稳定性较差，在近年来的工作中一般作为主模型的辅助分类器而非单独作为一种异常检测算法

基础假设：异常事件与正常事件在统计量或者统计分布上存在较大偏离

滑动窗口方法：通过滑动窗口计算统计量的方法计算每个窗口样本的异常分数，其中一类重要方法就是参数与非参数扫描统计量方法，但是扫描统计量方法极其依赖扫描统计量的选择。

代表推特网络的用户检测，蓝色方块代表推特，红色菱形代表关键词，黄色圆形方块代表地点，对\alpha=0.05的显著性，子图S包含11个低于阈值的显著点中的六个，那么我们根据p值在正常分布下均匀分布的假设，认为S具有较高的异常分数F(s)

动态贝叶斯网络：依照相邻时间步骤把不同变量联系起来

似然分布与概率估计：在传统方法加入采样估计与非参数计算结合

基础假设：正常用户的行为相对随机，信息熵较大;异常用户或者机器人行为相对有序，信息熵较低。该方法通常应用于垃圾邮件检测或网络入侵检测中。

基于图嵌入的图神经网络

•嵌入方法：DeepWalk,Line,Node2Vec

•改进嵌入：DynGEM,NetWalk

•基于GAT：AddGraph

针对动态图异常检测，图卷积网络需要进行扩展 GAT、分离时间域与空间域、堆叠邻接矩阵等方法在原模型的基础上添加时序与结构演化信息，并重新定义动态图异常以完成异常检测。

基于生成模型的重建方法

•学习动态图序列中每个图数据的隐空间表征，并基于隐空间嵌入向量重建样本，异常分数与重建效果挂钩

•基础工具：VAE与AAE-GraphVAE

•技术改进：正则化约束

•动态图演化特征建模：Dynamic Joint GVAE

•代表应用：H-VGRAE,多个图快照的多层嵌入方法

图上的自编码器方法需要配合图结构或参数共享、多层信息嵌入、统计先验假设等方法定义隐空间下的正常与异常分布。

基于循环神经网络的时序模型-预测与重建

•预测：LSTM

•基础处理：动态图看做一系列由图快照组成的时间序列

•预测与实际样本偏差较大作为异常样本

•LSTM-Node2Vec

•重建模型：基于公共子空间的重建偏离检测

•基础工具：OMNI/MASE：基于统计推断的多重随机图嵌入

•基础假设：共享图快照序列的图结构或隐参数

•代表方法：Series2Graph

我们总结了静态图和动态图的计算复杂度表格如下

•针对多类型图的异常检测算法

•可解释性与新颖模式发现

•非平衡数据集与鲁棒性

•大图上的异常检测

•扩展应用场景-城市异常检测/Crowdsourcing

•数据集-数据增强与图拓扑结构优化

撰写 / 晏梦懿、袁子淇

编辑 / 于金泽