HYPA：时序网络数据中高效的异常路径检测框架

论文标题｜ HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks
论文来源｜ ICDM 2020
论文链接｜ http://www.eliassi.org/papers/hypa-sdm2020.pdf
源码链接｜ https://github.com/tlarock/hypa

TL;DR

由于现实复杂网络系统中节点的异构性(特指节点与边的频率统计分布)，单纯地基于频率统计进行异常检测不再适用。论文中提出了一种无监督路径异常检测框架 HYPA (Higher-order Hyper-geometric path anomaly detection) 来检测图中不同长度的异常路径，即由于节点访问时序问题造成的路径访问频率次数异常，主要用于入侵检测、异常轨迹识别等。主要想法是将路径异常检测问题转化为 $k$ 维德·布鲁因图的节点进行图上的边异常检测问题，注意仅是判断图中的长度为 $k$ 路径是否频率异常。实验部分在交通运输系统数据中验证了算法的有效性。

Algorithm/Model

论文中提出 HYPA 框架如下图所示，

Path Anomaly Detection

首先明确论文中定义的路径异常检测问题：给定序列集合 $S$ ，异常路径检测是指统计序列中包含通过图的路径其频率高于或者低于期望值。形式化定义如下：

给定有向图 $G=(V,E)$ 和包含 $n$ 个序列 $s_i=v_0,v_1,\cdots, v_{l_i}$ 序列集合 $S$ ，其中 $v_j\in V, j \in\left[0, \ldots, l_{i}\right]$ 并且 $(v_j, v_{j+1}) \in E$ 。对于 $k>1$ ，检测所有包含在 $G$ 中的路径 $\vec{p}=\overline{v_{0} \ldots v_{k}}$ 频率是否明显偏离 $k-1$ 阶路径模型的期望。

论文的主要想法是将一阶图中的路径异常检测问题转化为高阶德·布鲁因图 $G^k$ 中的边异常检测问题，涉及到一个德·布鲁因图转化过程。

德·布鲁因图转化可以参考我的另一篇博文：德布鲁因图 (De Bruijn graph) 与线图 (Line graph)

转化为高阶德·布鲁因图的好处是：可以将路径长度为 $k$ 的路径异常检测问题转化为 $k$ 阶德·布鲁因中异常边权重异常检测问题。

k-th order model of paths

对于给定的图 $G$ ，令 $G^k=(V^k, E^k)$ 表示 $k$ 阶路径德·布鲁因图，对于每条边 $e:=\left(\overline{v_{0} \ldots v_{k-1}}, \overline{v_{1} \ldots v_{k}}\right) \in E^k$ 利用权重 $f(e)$ 表示 $S$ 中子路径 $\overline{v_{0} \ldots v_{k}}$ 的频率， $\mathbf{T}^k$ 表示 $G^k$ 的概率转移矩阵为 $\mathbf{T}_{\vec{v}\vec{w}}^{k}:=\frac{f(\vec{v}, \vec{w})}{\sum_{\vec{x} \in V^{k}} f(\vec{v}, \vec{x})}$ ，因此 $k$ 阶模型中路径 $\vec{p}=\overline{v_{0} v_{1} \ldots v_{l}}$ 的概率为 $\prod_{i=k}^{l} \mathbf{T}_{\bar{v}_{i-k} \cdots v_{i-1}}^{k} \overline{v_{i-k+1} \ldots v_{i}}$ 。

论文中假设随机路径图中的边权重分布符合多变量超几何分布，因此使用这个分布的边缘概率来计算每条边的权重：

$\operatorname{Pr}\left(X_{\vec{v} \vec{w}}=f(\vec{v}, \vec{w})\right)=\left(\begin{array}{c}\sum_{i j} \Xi_{i j} \\ m\end{array}\right)^{-1}\left(\begin{array}{c}\Xi_{v w} \\ f(\vec{v}, \vec{w})\end{array}\right)\left(\begin{array}{c}\sum_{i j} \Xi_{i j}-\Xi_{v w} \\ m-f(\vec{v}, \vec{w})\end{array}\right)$