type
status
date
slug
summary
tags
category
icon
password
 
 

摘要

检测动态图中的异常情况引起了广泛关注，因为它们在社交网络、电子商务和网络安全等领域有广泛的应用。最近基于深度学习的方法在浅层方法之上表现出了有希望的结果。然而，它们未能解决动态图中异常检测的两个核心挑战：未具有信息丰富的编码来处理未标记的节点，以及从耦合的时空动态图中学习判别知识的困难。为了克服这些挑战，本文提出了一种新颖的基于Transformer的动态图异常检测框架（TADDY）。我们的框架构建了一个全面的节点编码策略，以更好地表示每个节点在不断演化的图流中的结构和时间角色。与此同时，TADDY通过动态图Transformer模型从动态图中捕获了具有耦合时空模式的信息丰富的表示。广泛的实验结果表明，我们提出的TADDY框架在六个真实数据集上明显优于最先进的方法。
 

1. 介绍

（动态图重要性）在各种动态图的分析问题中，检测不断演化的图流中的异常边是一项关键任务[9]，[10]。动态图困难：
  • 挑战1。动态图缺乏原始属性信息。很难从主流的原始动态图数据集中构建用于表示每个节点的属性信息，需要一种有效的编码方法，构建人工特征来表示不断演化的节点。
绿色边缘倾向于正常，因为在之前的时间戳中它们的邻域之间存在密切的结构通信。相反，红色边缘具有很高的异常概率，因为两个红色节点在之前的快照中始终保持距离。
绿色边缘倾向于正常，因为在之前的时间戳中它们的邻域之间存在密切的结构通信。相反，红色边缘具有很高的异常概率，因为两个红色节点在之前的快照中始终保持距离。
  • 挑战2。从动态图中学习具有辨别性的知识，其中空间（结构）信息和时间信息相互关联。
（老方法不行，深度学习彳亍）但是之前的研究没解决上面两个问题。
NetWalk [9]、H-VGRAE [14]独热编码，AddGraph[10] 中的随机初始化特征都无法表达每个节点的结构或时间特性。 StrGNN [13] 中基于距离的节点标记策略仅考虑了局部结构信息，限制了其表达能力。 AddGraph [10]和StrGNN [13] 使用两个独立模块信息的孤立处理导致了耦合的空间-时间特征的丢失
本文克服挑战1，设计了一个全面的节点编码，由三个功能项组成，用于提取全局空间、局部空间和时间信息。对于挑战2，开发了一个动态图Transformer模型，同时学习空间和时间知识。通过基于边的子结构抽样来捕获跨时间的上下文信息，作为Transformer模型的输入。然后，通过跨结构和时间的注意机制提取耦合的空间-时间信息。贡献如下：
  • 端到端的基于Transformer的学习框架。首个用于动态图学习和图异常检测的基于Transformer的方法。
  • 为节点设计了一个综合编码方法。
  • 动态图 Transformer 模型，同时聚合了空间和时间知识，利用一种新颖的基于边的子结构抽样策略
文章结构：第 2 章相关工作，第 3 章描述问题定义，第 4 章介绍模型组件，第 5 章实验，第 6 章贡献和未来工作
 
 

2. 相关工作

2.1 动态图的异常检测

  • GOutlier [11]采用结构连接模型来检测图流中的异常值，并构建动态网络分区以维护连接行为模型。
  • CAD [16]通过跟踪结合了图结构变化和边权重变化信息的度量来检测节点关系。
  • CM-Sketch [12]考虑了本地结构信息和历史行为，以区分边的异常属性。
  • StreamSpot [17]是一种基于聚类的方法，利用一种新颖的相似性函数进行异构图属性比较，并利用基于质心的聚类方法来建模图流的行为。
  • SpotLight [18]使用 randomized sketching 技术来保证映射空间中异常和正常实例之间的大映射距离。
深度学习的方法：
  • NetWalk [9]利用基于随机游走的编码器生成具有团簇嵌入目标的节点嵌入，然后动态更新团簇
  • AddGraph [10] 使用 GCN 作为结构特征提取器，GRU-attention 模块来结合短期和长期的动态演化。
  • StrGNN [13] 提取了h-hop封闭子图的边缘，并利用堆叠的GCN [19]和GRU来捕捉空间和时间信息。
  • HVGRAE [14]通过结合变分图自编码器和循环神经网络构建了一个分层模型。为了检测异常边，利用边重构概率来衡量异常性。
（作者方法也是深度学习技术的一种，不同的是使用 transformer 综合了空间时间信息，使用综合编码，其他人都是两个模块分别提取时间空间特征，而TADDY则使用了一个Transformer网络来同时建模空间和时间信息。）

2.2 Transformers

（介绍 transformer）

3 问题定义

（动态图定义、图中异常定义，使用分数评估。符号在表1）
 

4 方法论

TADDY的总体框架由四个部分组成：基于边的子结构采样（edge-based substructure sampling）、空间-时间节点编码（spatial-temporal node encoding）、动态图Transformer（dynamic graph transformer）和区分性异常检测器（discriminative anomaly detector）。
首先执行基于边的子结构采样，以获取多个时间戳中的目标节点和上下文节点。空间-时间节点编码生成节点编码，作为Transformer模型的输入，每个节点的空间和时间信息都被整合到一个固定长度的编码中。之后，动态图Transformer通过由Transformer模块和池化模块组成的单一Transformer模型提取边的空间-时间知识。最后，在判别式异常检测器中，我们执行负采样以生成伪负边，然后使用经过二元交叉熵损失训练的边得分模块来计算输出的异常分数。
TADDY的整体框架。分为四个部分：基于扩散的空间编码（diffusion-based spatial encoding）、基于距离的空间编码（distance-based spatial encoding）和相对时间编码（relative temporal encoding）。 图示是一个简单的例子。（左上）红色的是目标边，黄色的是目标节点，周围绿色的是不同时间步的上下文节点组成子结构节点集合，top 邻居和滑动窗口 设置为3。 （左下）然后为每个节点计算三种类型的编码，并进行融合。 （右下）将节点编码作为输入数据，动态图Transformer通过注意力层学习潜在的节点嵌入，并利用均值池化来计算边的嵌入。 （右上）最后，在判别异常检测器中，通过负采样获取了负边。评分模块计算正边和负边的异常得分。 整个框架以端到端的方式使用二进制交叉熵损失进行训练。
TADDY的整体框架。分为四个部分：基于扩散的空间编码（diffusion-based spatial encoding）、基于距离的空间编码（distance-based spatial encoding）和相对时间编码（relative temporal encoding）。 图示是一个简单的例子。（左上）红色的是目标边，黄色的是目标节点，周围绿色的是不同时间步的上下文节点组成子结构节点集合，top 邻居和滑动窗口 设置为3。 （左下）然后为每个节点计算三种类型的编码，并进行融合。 （右下）将节点编码作为输入数据，动态图Transformer通过注意力层学习潜在的节点嵌入，并利用均值池化来计算边的嵌入。 （右上）最后，在判别异常检测器中，通过负采样获取了负边。评分模块计算正边和负边的异常得分。 整个框架以端到端的方式使用二进制交叉熵损失进行训练。
从第4.1节到第4.4节，我们具体介绍了TADDY框架的四个主要组成部分。在第4.5节，我们分析了我们提出的框架的时间复杂度。

4.1 基于边的子结构采样（Edge-based Substructure Sampling）

正如在之前的研究[13]、[36]中注意到的那样，异常通常发生在图的局部子结构中。所以首先对子结构进行采样，由于专注于检测异常边，所以有基于边的采样：动态图中的每一个边被视为采样子结构的中心，并被称为目标边，对于每个目标边，它连接的两个源和目的节点被被称为目标节点。
以目标边获取上下文信息（周围节点信息），最容易想到k跳邻居，但是对于度占比不同的节点，可能导致性能下降和低效率，同时，使用简单的k跳会使共享邻居和独享邻居视为平等权重。
为了解决上述限制，本研究借鉴了图扩散技术[37]，[38]，以采样每个目标边的固定大小和重要性感知的上下文节点集。通过图扩散，我们获取了对图结构的全局视图，然后我们可以量化每个节点对于给定目标节点/边的重要性。
定义图扩散矩阵 ，并为了保证收敛，使所有 和为1
notion image
 
的一行表示一个节点对于其他节点的连通情况，例如，对于边计算两个目标节点的连通性通过对扩散矩阵的值求和，通过这个方式可以选出 top k的连通性强的上下文节点（需排除自身）。上述方法仅对于单个时间步的静态图，对于动态图的动态演变，设置一个超参数 滑动窗口，对于窗口内的每个一个图计算扩散矩阵 ，选择top k的边和节点，最后组合得到一个滑动窗口内的多个时间步的子结构节点集合。

4.2 空间-时间节点编码（Spatial-temporal Node Encoding）

我们在本文中研究的动态图通常是无属性的，需要找到一个合适的网络模型输入数据。使用one-hot无法包含结构和时间信息，并且对大规模和节点变化不友好。
受到Transformer的位置编码启发，提出了一个新编码方式，所提出的节点编码包括三个组成部分，即基于扩散的空间编码（diffusion-based spatial encoding）、基于距离的空间编码（distance-based spatial encoding）和相对时间编码（relative temporal encoding）。最终，这三个编码项被融合成输入节点编码。
需要注意的是，我们是通过可学习的线性投影来生成编码，而不是使用 [20] 中的频率感知 sin/cos 函数，原因是可以更灵活的建模时间和位置之间的相关性。
接下来按顺序介绍三种编码，以及编码融合操作。

4.2.1 基于扩散的空间编码（Diffusion-based Spatial Encoding）

为了防止由于相似扩散值引起的无法区分的编码，我们没有直接采用原始扩散值，而是使用基于排名的编码。具体做法是对单个时间步的子结构节点集合的每个节点，对它们的扩散矩阵中的值进行排序，并作为数据源，输入到一个编码函数（单层线性映射）， 类似于Transformer中的位置编码。公式：
idx索引函数，rank排序函数，linear线性函数
idx索引函数，rank排序函数，linear线性函数

4.2.2 基于距离的空间编码（Distance-based Spatial Encoding）

虽然扩散空间编码可以捕获全局结构信息，但是也应该考虑每个节点的局部信息。具体做法，对于单个时间步的所有节点，将其到目标边的距离作为编码的信息，到目标边的距离可以分解为到边两端的目标节点相对距离最小值。目标本身节点距离为0，同样使用单层线性映射作为可学习的编码函数。
min函数取两个dist函数最小值，然后线性映射
min函数取两个dist函数最小值，然后线性映射

4.2.3 相对时间编码（Relative Temporal Encoding）

时间编码是用来表示子结构节点集中每个节点的时间信息。与Attention all you need中的位置绝对编码不同，使用相对编码。具体而言，对于子结构节点集合中的每个节点，相对时间编码被定义为：目标边出现的时间和当前时间的差异。其背后的动机是我们的主要任务是预测目标边的合法性，因此与目标边的相对时间是异常检测的更重要因素。同样是线性映射
notion image

4.2.4 编码融合（Encoding Fusion）

计算三个编码项后，将融合后的节点编码定义为三个编码项的求和，避免直接拼接得到高维向量导致效率低，编码融合形式表达为：
notion image
对于目标边 我们计算其子结构节点集中每个节点的编码，并将它们堆叠成一个表示 属性的编码矩阵。编码矩阵表示为：
拼接和转置
拼接和转置

4.3 动态图Transformer

之前的方法用混合模型学习动态图空间/时间信息不彳亍，只是次优解。dynamic graph transformer 彳亍，可以同时处理空间/时间信息，注意力机制学习捕获跨领域知识，pooling 层将子结构节点集合嵌入聚合为目标边嵌入向量。

4.3.1 Transformer模块

多个attention层组合起来使不同的节点交换信息，单个attention 层表示为：
notion image
notion image
（都是attention的知识）
transformer的输入 是目标边的编码矩阵，并设置编码和嵌入维度相同保证对齐
 
相关文章
A survey on graph neural networks for intrusion detection systems: Methods, trends and challenges
TS-IDS: Traffic-aware self-supervised learning for IoT Network Intrusion Detection
Anomaly traffic detection in IoT security using graph neural networks
AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN
安全问题统计
信息安全顶级会议文章整理
安全问题统计 信息安全顶级会议文章整理
  • Valine