SNAPSKETCH：基于图表示学习的图流异常检测模型

论文标题｜ SNAPSKETCH: Graph Representation Approach for Intrusion Detection in a Streaming Graph
论文来源｜ MLG 2020
论文链接｜ http://www.mlgworkshop.org/2020/papers/MLG2020_paper_1.pdf
源码链接｜ https://github.com/rpaudel42/SnapSketch

TL;DR

论文中提出一种无监督的图表示学习方法 SNAPSKETCH 用于图流的异常检测问题。主要想法是基于随机游走和 Sketching 技术来生成固定大小的图向量表示，然后基于编码后的向量使用 RRCF 进行异常检测，可以达到实时异常检测效果。实验中验证本文中的方法优于其它 baselines，包括 SpotLight 和 StreamSpot。

Problem Definition

给定一个图流 $G_s = \{G_1, G_2,...,G_t,...\}$ ，目标是学习到一个 sketching function $f: G_{t} \rightarrow v_{G_{t}} \in \mathbb{S}^{d}, d<<|v|^{2}$ ，使得 $v_{G_t}$ 保留了图的结构属性和特征。

对于图流中 $t$ 时刻的图 $G_t$ ， $G_t$ 中生成长度为 $l$ 的有偏随机游走路径为 $p_{G_t} = \{v_1, v_2,... ,v_l\}$ ，论文中的名词定义如下：

shingle：路径 $p_{G_t}$ 中连续的子序列。
n-shingle：路径 $p_{G_t}$ 中长度为 $n$ 的连续子序列，针对 $G_t$ 中每个节点生成的 shingle 集合 $S_t$ ，需要选择 $k$ 个 Discriminative shingle 集合 $S_t^k$ 以随机概率 $r$ 来映射到一个 $d$ 维向量 $h_{[1,..., d]}=\{1, 0\}$ ，Discriminative shingle 是指出现频繁的 n-shingle。
Sketching：数据表示技术，例如将图 $G_t$ 映射到一个低维的向量 $v_{G_t}$ 且同时保留了图的原始属性。
Cost vector： $c_t=|S_t^k|$ ，每个元素表示 $S_t^k$ 的数量。

论文想法是以映射向量 $h_d$ 和计数向量 $c_t$ 来将图 $G_t$ 映射到低维向量 $v_{G_t}$ ，对此表示好奇 🧐，没有用到任何 deep learning 方法。

Algorithm/Model

论文主要的算法流程如下图所示：

主要包含两步：

基于有偏随机游走生成 Shingles。
Discriminative Shingle 映射成向量。

随机游走

对于图 $G_t$ 中的节点 $v_i$ ，长度为 $l$ 随机游走路径 $w_i$ 符合以下分布：

$P\left(w_{i}=x \mid w_{i-1}=v\right)=\left\{\begin{array}{ll} \frac{\pi_{v x}}{Z} & \text { if }(v, x) \in e \\ 0 & \text { otherwise } \end{array}\right.$

其中 $\pi_{vx}$ 表示节点 $v$ 和 $x$ 间未标准化的转移概率即边的权重， $Z$ 表示标准化常数。为了使邻居采样同时考虑到 BFS 和 DFS，论文中采用 node2vec 中相同的思路对于转移概率重新进行计算，

$\pi_{v x}=\alpha_{p q}(t, x) \cdot w_{v x} \\ \alpha_{p q}(t, x)=\left\{\begin{array}{ll} \frac{1}{p} & \text { if } d_{t x}=0 \\ 1 & \text { if } d_{t x}=1 \\ \frac{1}{q} & \text { if } d_{t x}=2 \end{array}\right.$

其中 $d_{tx}$ 表示节点 $t$ 和节点 $x$ 间的最短距离。

基于随机游走生成的路径，可以得到集合 $S_t$ ，接下来就需要把 $S_t$ 映射成 $d$ 维向量。

哈希向量映射

向量映射的流程如下图所示：

解释说明下：例如上图 $G_1$ 和 $G_2$ , $S$ 表示不重复的 n-shingle 集合， $c_1$ 和 $c_2$ 表示每个图中 n-shingle 频率，可以通过 $c_1$ 和 $c_2$ 来计算 $G_1$ 和 $G_2$ 的相似度。

如果仅使用 $c$ 向量来表示图，如果 $G_{t+1}$ 中生成不同的 n-shingle 那么 $c$ 的维度将会上升，因此论文是使用一种简单的哈希技术来将 topK discriminative n-shingles 进行映射而不是所有的 n-shingles 。

topK discriminative n-shingles 是指 $k$ 个最频繁的 n-shingles，表示为 $S_t^k$ ，可以理解为从图中选择具有代表性的路径来表示图， $k$ 值太大能充分地表示图但是占用内存更大， $k$ 值小能够减少内存但是不能充分地区分图，因此这个超参数选择是个技术活。

Hashing Function

现在对于集合 $S_t^k$ 进行映射，先初始化 $d$ 维向量映射向量为 $h_d = \{1, 0\}$ 符合概率为 $r$ 的随机分布：

$\forall k \in S_{t}^{k}, h_{[1, \ldots, d]}=\left\{\begin{array}{ll} 1 & \text { probability } r \\ 0 & \text { probability } 1-\mathrm{r} \end{array}\right.$