基于图的异常检测算法OddBall详解

创作时间:

作者:

@小白创作中心

基于图的异常检测算法OddBall详解

引用

CSDN

https://m.blog.csdn.net/beingstrong/article/details/143819107

OddBall异常检测算法出自2010年的论文《OddBall: Spotting Anomalies in Weighted Graphs》，它是一个在加权图(weighted graph)上检测异常点的算法，基本思路为计算每一个点的一度邻域特征，然后在整个图上用这些特征拟合出一个函数，再根据拟合出来的参数计算每个点的异常分数，所以它可以用于无监督场景。

OddBall检测的异常情况如论文图1所示的四种情况：

Near-cliques: 节点的邻居之间紧密联系，典型的情况可能是恐怖组织或者成员之间非常活跃的讨论组。（clique是图里的团，一个clique里的节点两两之间都有一条边）
Near-starts: 星状结构，节点的邻居之间几乎没有什么联系，典型的情况有中介、电话销售、机器营销号码等。
Heavy vicinities: 节点的邻居个数固定，但是这些边对应的权重之和异常地大。比如在一个电话网络里，一个节点只有有限的n个联系人，但是总的呼叫次数非常大，与n不成比例，说明可能存在强制重拨的异常设备，或者在伪造通话记录等。
Dominant heavy links：图里有某一条边的权重占主导地位。比如在一个电话网络里，一个stalker可能会在短时间内不停地给某个联系人打非常多的电话。

论文借用社交网络分析(social network analysis, SNA)的术语，将图中每一个节点称为’ego’，将一个节点与其1-step邻居节点组成的网络称为egonet。一个节点k-step邻居即从节点出发k步能到达的邻居节点集合，这些邻居节点之间组成了一个子图。关于k的选择，论文推荐使用k=1，有之前的论文表明现实中的图有比较小的直径，论文实验时也发现k>1没有提供更多的信息。（不过在想随着这些年社交媒体和移动互联网的快速发展，现在的数据来说k>1在一些场景下是可能提供更多信息的）

对一个egonet，选择什么特征来描述它呢？比如很容易能想到的特征有：节点个数、边个数、特征值、三角形个数、度为1的邻居的个数等。论文经过试验，最终选择了如下4个特征来刻画egonet:

N i N_iNi ： ego i对应的邻居个数，即节点i的度。
E i E_iEi ：egonet i包含的边的数目。
W i W_iWi ：egonet i的总权重。
λ w , i \lambda_{w,i}λw,i ：egonet i的带权邻接矩阵的主要特征值。

接着，论文用这4个特征组成特征对来检测前面提到的几种异常：

E EEvsN NN：用来检测near-cliques和near-stars。
W WWvsE EE：用来检测Heavy Vicinity。
λ w \lambda_wλw vsW WW：用来检测Dominant heavy links。

在检测异常时，自然地就会问一个正常的邻居节点是什么样子的呢？基于上述特征对，Oddball作者们总结了下文的一些模式。对于一个给定的图G \mathcal{G}G，其节点ii ∈ V ( G ) i \in \mathcal{V(G)}i∈V(G)，节点的i的egonet记为G i \mathcal{G}_iGi 。（注：如果只想知道Oddball是如何计算异常分数的，下面这些模式可先略过不看，不过这些模式有助于理解Oddball的异常分数计算思路）

观察1(EDPL: Egonet Density Power Law) ：G i \mathcal{G}_iGi 的邻居个数N i N_iNi 和边的条数E i E_iEi 满足幂率:
E i ∝ N i α , 1 ≤ α ≤ 2 E_i \propto N^{\alpha}_i, \ 1 \le \alpha \le 2Ei ∝Niα , 1≤α≤2

在论文实验时的指数α \alphaα大小为1.10到1.66。论文图2示意了这个观察（图是在对数维度画的），当斜率为2时，代表图为一个clique，而斜率为1，代表图为star。

观察2(EWPL: Egonet Weight Power Law)：G i \mathcal{G}_iGi 的总权重W i W_iWi 和边的条数E i E_iEi 满足幂率:
W i ∝ E i β , β ≥ 1 W_i \propto E^{\beta}_i, \ \beta \ge 1Wi ∝Eiβ , β≥1

论文图3展示了数据集的EWPL示意，β \betaβ最大达到了1.29，β > 1 \beta>1β>1表明随着边的增加，权重之和的增加有超线性的增长。

观察3(ELWPL: Egonetλ w \lambda_wλw Power Law)：G i \mathcal{G}iGi 的带权邻接矩阵的主要特征值λ w , i \lambda{w,i}λw,i 和总权重W i W_iWi 满足幂率:
λ w , i ∝ W i γ , 0.5 ≤ γ ≤ 1 \lambda_{w,i} \propto W^{\gamma}_i, \ 0.5 \le \gamma \le 1λw,i ∝Wiγ , 0.5≤γ≤1

论文图4示意了数据集的ELWPL，实验中λ \lambdaλ范围为0.53至0.98。γ = 0.5 \gamma=0.5γ=0.5表示均匀的权重分布，γ ∼ 1 \gamma \sim 1γ∼1表示在egonet中有显著权重边。γ = 1 \gamma=1γ=1表示egonet只有一条边。

观察4(ERPL: Egonet Rank Power Law)：G i \mathcal{G}iGi 中的边j的排序R i , j R{i,j}Ri,j 和权重W i , j W_{i,j}Wi,j 满足幂率:
W i , j ∝ R i , j θ , θ ≤ 0 W_{i,j} \propto R^{\theta}_{i,j}, \ \theta \le 0Wi,j ∝Ri,jθ , θ≤0

R i , j R_{i,j}Ri,j 是边j按照边权重排序之后的排名。ERPL表明在egonet中边的权重分布是倾斜的。这个是符合直觉的，比如在一个朋友网络中，一个人会有许多不亲近的朋友，但只有少数几个亲近的朋友。接着论文证明了如果ERPL成立，则EWPL也成立。

有了前面这些铺垫，现在让我们看看Oddball是如何计算异常分数的。对于前面提到的特征对（根据检测异常类型选择特征对），设节点i的对应的y值记为y i y_iyi ，对应的x值为x i x_ixi ，假设对于数据集可以拟合得到一个幂率方程y = C x θ y = C x^{\theta}y=Cxθ，定义节点i的异常分数为：
out-line ( i ) = max ⁡ ( y i , C x θ ) min ⁡ ( y i , C x θ ) ∗ log ⁡ ( ∣ y i − C x θ ∣ + 1 ) \text{out-line}(i) = \frac{\max(y_i, C x^{\theta})}{\min(y_i, C x^{\theta})} * \log(|y_i - C x^{\theta}| + 1)out-line(i)=min(yi ,Cxθ)max(yi ,Cxθ) ∗log(∣yi −Cxθ∣+1)

直观上，Oddball的异常分数度量“偏离拟合曲线的距离”，当真实值y i y_iyi 与期望值C x θ C x^{\theta}Cxθ相等时，异常分数为最小值0。

作者发现Oddball有时候检测不到一些异常点，比如在图2(a)中的左三角标记的点，它们与其他点隔的很远但是几乎就在拟合线上。所以作者提出将Oddball异常分数与基于密度的异常检测方法一起结合使用。在论文中，使用的基于密度的异常检测方法是LOF方法，将Oddball分数和LOF分数进行归一化后(通过除以最大值的方式)求和得到最终的异常分数，即out-score ( i ) = out-line ( i ) + out-lof ( i ) \text{out-score}(i) = \text{out-line}(i) + \text{out-lof}(i)out-score(i)=out-line(i)+out-lof(i)。

实践经验：1. 在计算一个egonet里的边的数目时，可以通过计算egonet里三角形个数和其度之和来得到。因为现有的工具比如Spark GraphX里已经有三角形个数和度计算的现成接口。2. 计算LOF时，在图里怎么算距离呢? 把选定的特征对数据作为LOF的特征再计算距离。