zhj 【KDD2016】FRAUDER Bounding Graph Fraud in the face of camouflage

任务场景

在社交媒体中，有非常多的二部图。比如推特中，有关注者和被关注者两种节点，关注关系形成一个二部图；在大众点评中，有用户和商家两种节点，用户对商家的点评关系形成一个二部图；在淘宝里，用户购买商品，也形成一个二部图。

Fraudar可以解决哪些问题呢？（二部图的问题）
\1. 用户在电商平台，购买商品（刷单）
\2. 用户评论电影，美食，游戏评分（刷评分）
\3. 推特，博客关注信息（购买粉丝）

为了在二部图中检测出上述的欺诈行为，以往的方法（在此篇论文发表的2016年以前）是检测二部图中的稠密子图。以购买粉丝为例，购买者会突然增加许多粉丝，在二部图中，购买者这个节点的边突然增多（稠密子图）。

解决的问题

欺诈者会想办法伪装自己的欺诈行为。以大众点评为例，某个商家向欺诈者购买了大量好评。欺诈者通过操控大量的账户，给商家好评，从而提高该商家的人气。为了不那么容易被检测出来，欺诈者会伪装自己的欺诈行为。本文提出的方案针对3种伪装方法：

随机伪装。除了给目标商家好评，也随机给其他商家好评。
有偏的伪装。除了给目标商家好评，也随机给其他比较热门的商家好评。
劫持用户。通过劫持正常用户的账号，给目标商家好评。

解决方案

首先明确抗伪装的定义，定义$g$为一个子图的密集程度指标（越密集越可疑），抗伪装的要求是：即使欺诈者做了一些伪装，这个指标$g$不会因此下降。

看看作者设计的解决方案。作者设计的子图异常指标$g$（稠密程度）如下（左侧公式，右侧例子），其中$\mathcal{V}$是点集，$\mathcal{E}$是边集, $\mathcal{S}$是一个子图。

这个指标满足几个欺诈检测中对异常指标的要求：

子图规模相同的情况下，包含高危节点的子图更可疑。
子图的边增加，将会增加该子图的可疑性。
当点和边的权重相同时（并且在同样边的密度下），大图比小图更可疑（相同密度，越大越可疑）
如果总的可疑度相同，小图比大图更可疑（密度越大越可疑）

算法流程：

是一个贪心算法。令$\mathcal{X}$是所有节点，每次寻找一个节点$i$,使得下面这条式子最大：$\Delta_{i}=f(\mathcal{X} \backslash{i})-f(\mathcal{X})$

直观理解：每次选出一个节点，去除这个节点后，剩余的节点构成的子图的异常指标$f$最大。

遍历完成之后，取其中的一个子图作为异常子图，这个子图使得异常指标$g(S)=\frac{f_{S}}{|S|}$最大。

这个算法是如何对抗伪装的？

回顾异常计算指标：

$\begin{aligned} f(\mathcal{S}) &=f_{\mathcal{V}}(\mathcal{S})+f_{\mathcal{E}}(\mathcal{S}) \\ &=\sum_{i \in \mathcal{S}} a_{i}+\sum_{i, j \in \mathcal{S} \wedge(i, j) \in \mathcal{E}} c_{i j} \end{aligned}$

其中$ai$是节点的权重，$c{i, j}$边的权重。通过调整$c_{i, j}$来抗伪装。

即通过令边权重$c_{i j}=\frac{1}{log (d_j+c)}$来达到抗伪装的目的，其中$d_j$是商品节点$j$的度。这样调整权重的含义时，一个商品的度越高，它的边的权重越低。

为什么这个权重$c_{i,j}$是抗伪装的？

实验结果

0. 本文使用的数据集

1. 在生成数据中的实验。

在亚马逊的关于评论的图中，提取2000个用户和2000个商品的子图。往这个子图中注入欺诈块。

2. 在真实数据中的实验。

数据是推特的”关注者-被关注者“图。2009年采集数据，包含了4170万用户和14.7亿用户。在这张图上，Fraudar检测到4031关注者和4313被关注者的子图。

总结：通过迭代图中所有节点，检测出异常稠密的子图，这个子图就是有欺诈行为嫌疑的群体。

优点：

是一个无监督的方法。
针对的是通过操纵大量用户进行欺诈的行为。

不足之处：

没有从时序的角度对用户和商品进行建模。用户和商品如果跟欺诈有关，会有特定的行为模式。
没有考虑用户、商品、和连边的内部特征。用户的个人特征、商品的特征、连边（评论）的特征也可以用来提高欺诈检测效果。这里可以引入GNN来实现这个目的。
不适用于检测个别用户的欺诈行为。

附：本文中使用的数据集调研