WSDM 2024 | 持续同调优化的图异常检测

10月前

©作者 | 袁子淇

单位 | 北京航空航天大学

来源 | ACTBIGDATA

本文主要介绍我们在图异常检测方向的工作 PhoGAD: Graph-based Anomaly Behavior Detection with Persistent Homology Optimization，工作已被 WSDM 2024 接收。

网络攻击、垃圾邮件等一系列异常网络行为干扰了正常的网络使用。由于网络行为天然地拥有发起者和接收者，因此基于图的方法常被用以检测异常行为。然而，真实世界应用环境中，正常行为和异常行为之间的界限并不清晰，图的局部异配性干扰了检测，使得现有基于节点或边的检测方法会对表征结果引入噪声，影响检测效果。

为应对这些问题，本文提出基于图的异常行为检测框架 PhoGAD。其采用持续同调的优化方式以清晰化行为边界。在此基础上，邻接边权重被设计以应对图的局部异配性。随后，本文对噪声问题进行了形式化分析并设计了表征分离的显示嵌入方式，从而最终实现异常行为检测。

实验结果表明，在三个基准数据集上，PhoGAD 相比于先前方法均取得了更好的综合检测效果，并能够适应真实场景中极低的异常占比。

论文链接：

http://arxiv.org/abs/2401.10547

研究背景

网络行为是天然的时序数据，大量研究对正常行为序列进行建模，实现了基本的异常行为检测。在此基础上，得益于网络行为天然具有发起者与目标的性质，长于表达数据关联的图结构被引入这一领域进行数据表示。一系列基于节点、边检测方法利用攻击图、溯源图等图模型实现了更精准的异常行为检测。

然而在真实场景中，异常行为的发起者往往会调整自身的行为模式来回避检测，例如攻击者会模仿正常访问的频次，垃圾邮件会模仿正常邮件的内容。使得正常行为与异常行为之间的边界在对应的图结构中不再清晰，即异常边不再集中分布，而是与正常边相互邻接。

这导致了图的局部异配性。在这种情况下，现有基于节点的边表征方法为目标边引入了不直接与之相连的节点的属性，这些不相关的节点属性构成了属性噪声。另一方面，现有直接对边进行卷积的方法同样在卷积过程中向异常边的表征引入了邻接的正常边属性，产生属性噪声。具体如下图所示。

为解决这一问题，我们形式化地分析了当前图异常行为检测中存在的属性噪声，并针对性地提出了 PhoGAD，一个利用持续同调进行优化并基于图的异常行为检测框架。

具体地，我们采用基于持续同调的拓扑方法分析边的特征空间中持续存在的结构，以此作为正常信号并对相关的边进行属性相似度鼓励，从而强化异常边属性与正常边属性之间的差异。在此基础上，我们为检测网络设计了分离表征机制，并利用与邻接边相关联的二阶邻居节点计算邻居权重，从而适应图的局部异配性，进而避免引入影响检测的属性噪声。

问题分析

2.1 局部异配性

图异常检测任务中，由于异常占比极低，因此整张图的异配性很低，这意味着相连接的节点或边大多具有相同的标签。但在异常边存在的局部结构中，异配性急剧提高。部分图学习的研究针对性地分析了异配图的学习问题，经典的异配图研究着眼于一条边连接两个不同顶点的情况，对顶点所关联的边的同配性、异配性研究相对较少。

而在异常检测的领域中，常规的同配学习方法会导致表征趋同问题，使得异常结构的嵌入结果被正常特征覆盖，异配学习方法在大量存在的同配结构中表现不佳，不能很好地适应异常检测任务。

2.2 噪声问题

以下图中的结构为例，记节点的初始属性为，经过 k 层网络后的属性为。

以最为通行的嵌入方法对边进行表征时，会首先按照下式计算节点的嵌入向量：

其中为节点的第阶邻居节点，为节点在嵌入对第阶邻居节点采用的 mask 矩阵。的计算同理于此。

常用的图学习方法，例如 DGI、GDN 等，采用了不同的、和以适应不同场景中的任务。现有方法大多基于节点嵌入结果计算边的表示向量：

对于边 e 而言，节点、的邻居节点中与不邻接的节点对其并没有直接的影响。但在上式中，特别是当时，高阶邻居节点在很大程度上参与到了的嵌入向量的计算中，即的部分。此外，随着网络层数升高，嵌入向量也会融入越来越远的节点的信息。这些都为 e 的嵌入向量引入了噪声。

一些现有检测方法不显式计算边的表征向量，但同样存在噪声问题。以极具代表性的 UGED 为例，其对每个节点的一阶邻居节点进行抽样，从而按照下式计算边的异常分数。

其中 k 为采样次数。这一计算方法十分符合基于节点嵌入检测边异常的思路。然而在实际的网络中会引入与边无关的节点和的信息。

这种情况下和为边的检测引入了噪音。当较小时，UGED 提出的学习机制难以学习到有用的信息，反之将将引入占比较高的噪声，对边表征造成影响。

同理，AANE等方法以边附近的结构为基础计算存在的概率。并使用指示函数

作为异常检测标志。

记，从而：

其中，。显然与、均有关，指代了与边相关的节点，而计算需要对节点的邻居进行采样，不同的采样方式将引入节点乃至的信息，为边的检测引入了噪声。

其余基于图卷积等聚合方法的检测算法同样有类似的问题，卷积层数越深，引入的无关高阶邻居节点的噪声越多。事实上，当对比边与时，使用节点的特征是有意义的，因为边差异很大程度上取决于节点对与的差异。因此对与无直接关系的节点等，应将其作为对边进行显示嵌入时的权重参数计算依据，而非直接将其引入边表征，从而解决噪声问题。

模型方法

本节介绍我们提出的 PhoGAD 框架，如下图所示。为了保证对常见异常行为检测任务的泛化性，PhoGAD 首先使用无向图表示原始数据，之后采用持续同调的拓扑方法进行边特征优化。随后，PhoGAD 引入邻接边权重对边进行显式嵌入，并在这一过程中引入表征分离，最终在输出层实现异常检测。

3.1 图构建

图中的节点代表网络中的实体，例如 ip 及端口、邮件账户等，节点的属性表示该实体的特征，例如访问习惯等。图中的边表示具体的网络行为，例如入侵、匿名流量以及垃圾邮件等。边的存在代表行为的发生，边属性即该行为的属性，例如访问特征等，从而异常边即为检测目标。

在上文提及的场景中，较为特殊的是垃圾邮件检测，一些研究使用了复杂的模型来提取邮件文本特征，但这些方法较难捕捉邮件之间的关联，并且大多需要用到具体应用领域的专家知识。我们采用的构建方法仅仅依靠基础的词频作为特征以突出基于图的方法的优势，并且避免对先验知识的依赖。

3.2 持续同调

持续同调是一种计算、编码复形和拓扑空间的嵌套族的拓扑特征。为了捕获特征空间中广泛持续存在的结构，我们挖掘其中的 Vietoris-Rips 复形，如下式所示。

其中为边的属性，表示以为球心，为半径的闭球。从而随着半径的增长，可以绘制出每条边的属性组成拓扑结构的持续性。由 VR 复形在更广范围的半径下构造出的拓扑结构被视为持续存在的正常信号，因此可将涉及到的边的属性进行优化，如下式所示。

其中为持续存在的复形包含的边集合，为边更新后的属性。

通过这种计算，为正常边赋予了其对应结构中存在的其他正常边的特征，从而引入了全局性信息。同时，由于拓扑分析对于数据的变换不敏感，因此在不同数据尺度的应用场景中都能够发挥作用，有助于强化 PhoGAD 的泛化性。

3.3 显式边表征及检测

在拓扑分析之后，我们对边进行显式表征并最终完成检测。在这一过程中，我们引入了适应异常边检测的分离表征机制，并采用了邻接边的权重以应对图的局部异配性。分离表征指在每一次卷积中，将本边的表征与邻接边的表征相互分离，即对于某一边的当前嵌入，基于下式计算其下一轮的嵌入向量。

其中表示与邻接的边构成的集合。边的初始属性描述了特征空间中的全局特征，所引入的邻接边的属性描述了图的局部特征，通过卷积可以使二者融合，从而进行准确的异常检测。

为实现对邻接边的有效筛选，我们进一步引入了基于节点相似度的卷积参数惩罚，构建了权重，这使得连接相同类型节点的边的表征更快融合以实现对局部异常的检测。

其中为与聚合时的余弦相似度权重，、为与相邻且互为二阶邻居的节点，、为其对应的属性。这种方式保证了本方法在各类场景中的泛化性，实现了针对更广泛真实应用场景的检测。

由于网络异常行为检测任务中异常行为占比通常较低，因此我们将目标检测领域中的 focal loss 迁移应用至行为检测中。从而：

训练获取的边嵌入具有良好的区分度，因此仅需通过线性层将结果其映射到二维的检测结果空间。这种方式实现了对边的异常检测，从而发现原始数据中存在的异常行为。

实验验证

为了测试 PhoGAD 在不同场景中的异常行为检测能力，我们采用了网络入侵检测、匿名流量检测、垃圾邮件检测三个场景中的公开数据集，即 UNSW-NB15（UNSW）、ISCXTor2016（TOR）以及 SpamAssassin（SPAM）。

4.1 持续同调分析结果

下图展现了在三个数据集上使用持续同调方法进行拓扑分析的结果。由于 0 维单纯形是基本联通结构，不具备深层拓扑特征，因此我们将其忽略，仅选用 1 维单纯形进行分析，其对应了 1 维度拓扑孔洞。

在持续性图中的一个节点越远离对角线，或条形码图中的一条横线越长，代表着其对应拓扑结构持续存在的时间更长。由于我们将所有的特征字段都进行了归一化处理，因此在可视化的意义上各点并未显著偏离对角线。但从图中依然可以看出，有一部分行为的特征构成了持续存在的结构。图(c)、(d)与其他四个不同，这是因为其边特征分布相对均匀，没有构成大量的 1 维单纯形，从而持续同调进挖掘出了少量的拓扑结构，但在其之中仍有相对持续存在的结构。

下表进一步展现了挖掘出的持续存在的拓扑结构对应的边集合中异常边或正常边的占比。

可见挖掘出的持续存在的结构中，对应的边绝大部分均为正常边，这说明在对应的图中正常信号更为持续，符合异常检测的假设。因此，基于持续同调进行属性优化能够增强同类边表征之间的相似度，使得行为边界清晰化。

4.2 异常行为检测结果

下表展现了各数据集上的检测结果，其异常占比均被降低为 10%。

PhoGAD 在几乎全部数据集的全部指标上都取得了最佳的综合检测效果。特别是在 SPAM 数据集上，由于我们仅采用了邮件文本词频作为边的初始属性，因此所获得的检测效果是不依赖领域知识的结果。这说明分离表征与邻接边权重配置有效地应对了噪声问题以及图的局部异配性。

其中的例外是 TOR 数据集，PhoGAD 和 Anomal-E 表现没有拉开差距，且 PhoGAD 的 precision 极其微小地较低。这是因为持续同调的计算中并没有挖掘出大量的持续存在的结构。从而正常特征没有被突出，容易产生假阳性结果，降低 precision。

在其余的基线方法中，Anomal-E 的表现优于 OCGNN，意味着显示表征相对隐式表征具有优势，直接的边检测算法具有优势。而 CSAWD、GNN-NIDS 表现较差，这是由于其引入的噪声较多。相对特殊的 AnomalyDAE 的 recall 普遍大于 precision，这意味着其假阴性结果较少，但是较低的 precision 拉低了 F1 这一综合指标。

在真实应用场景中，网络入侵、匿名流量等异常行为在全部行为中的占比通常极低，低于垃圾邮件一类的异常行为。因此我们对前两个检测场景进行了进一步的实验，进一步降低了数据的异常占比，以测试各检测方法在真实世界应用环境中的效果。下表展现了对应的检测结果，其中异常行为占比被降低至 5%。

可以看出，PhoGAD 在极低异常占比的条件下虽然各项指标有一定的降低，但也保持了良好的检测性能。特别低，PhoGAD 在全部指标上都超过了 Anomal-E。以 OCGNN 为代表的隐式嵌入方法的效果则产生了较大幅度的降低。值得注意的是 AnomalyDAE 方法是基于自编码器的方法，因此其受到异常占比降低的影响相比其他 baselines 较小，保持了较高的 recall。

我们进一步将异常占比降低为 3%，结果如下表所示。

可见基于隐式嵌入的方法效果急剧下降，CSAWD 等方法的检测由于过低的 recall 和 precision 已经失去了实际意义。PhoGAD 却仍然保持了相对较高的检测效果，仅在 UNSW 数据集的 recall 这一指标上落后于 AnomalyDAE，但包括综合指标在内的其他指标都保持了大幅领先。这说明在异常占比极低时基于重构损失的方法能够保持较低的假阴性率，但是易于产生大量的假阳性结果。

这些结果进一步说明 PhoGAD 能有效隔绝异常样本和正常样本之间的相互影响，从而在异常样本占比较低时保持良好的效果。

4.3 消融实验结果

为了评估 PhoGAD 所采用各项机制的实际效果，我们在入侵检测场景中进行了消融实验。

可以发现持续同调的贡献较高，所以将其去掉后结果最差，且假阳性率高，precision 更低。将邻接边权重、分离表征等机制去除后假阴性率变高，recall、precision 都有所升高。仔细分析各指标可以发现，持续同调更侧重于降低假阳性率，邻接边权重、分离表征侧重于降低假阴性率。这是因为持续同调使得正常边属性分布更为集中，而另外两者的核心作用是分离正常边与异常边，从而在异常边占比较低时保护其属性不被覆盖。