FRAUDAR： Bounding Graph Fraud in the Face of Camouflage
（KDD 2016）
Mercor比赛中第二名用到了这篇论文。
motivation
现有的基于图的检测方法（如SPOKEN, NetProbe）主要寻找图中连接紧密（Dense）的子图 。
聪明的欺诈者会试图让自己看起来“正常”。他们不仅连接目标（如购买了假粉的客户），还会随机连接一些诚实的用户或热门产品（如流行歌手、热门电影）。这种行为被称为“伪装” 。
论文目标： 设计一种算法，不仅能检测出密集子图，还能在面对伪装时保持鲁棒性，并为欺诈者无法被检测到的上限提供理论保证 。
数学模型与密度度量
论文的核心贡献在于提出了一种新的度量标准（Metric），用于衡量一个子图的“可疑程度”。
$\mathcal{U}$：用户集合（如Twitter账号）。
$\mathcal{W}$：对象集合（如被关注的人或商品）。
$G = (\mathcal{U} \cup \mathcal{W}, \mathcal{E})$：二部图。
$S \subseteq \mathcal{U} \cup \mathcal{W}$：被检测的节点子集。
论文定义了一个通用的密度度量 $g(S)$，形式如下：
$$g(S) = \frac{f(S)}{|S|}$$
其中，$f(S)$ 是总可疑度（Total Suspiciousness），由节点权重和边权重组成 ：
$$f(S) = \sum _ {i \in S} a_i + \sum _ {i,j \in S \wedge (i,j) \in \mathcal{E}} c _ {ij}$$
- $a_i \ge 0$：节点 $i$ 的固有可疑度（如果没有先验知识，可设为0）。
- $c _ {ij} > 0$：边 $(i, j)$ 的可疑度权重 。
为了对抗伪装，FRAUDAR 不将所有边一视同仁，而是采用了列加权（Column-weighting）。
如果一个对象（如Lady Gaga）拥有极高的度（Degree，即由 $d_j$ 表示），那么一个用户关注她并不一定是可疑的，这很可能是伪装行为。相反，如果一个用户关注了一个不知名且只有少量关注者的账号，且该账号周围形成了一个密集块，这更可疑。
论文建议使用对数加权函数 $h(x)$ 来降低高度数对象的边的权重 ：
$$c _ {ij} = \frac{1}{\log(d_j + c)}$$
其中 $d_j$ 是对象 $j$ 的度，$c$ 是一个小常数（实验中设为5）。这使得连接到热门对象的边对密度的贡献变小，从而忽略伪装边，聚焦于欺诈核心。
方法
FRAUDAR 算法的目标是找到一个子集 $S$，使得 $g(S)$ 最大化。
由于精确寻找最大密度子图通常是NP-hard问题，作者采用了一种高效的贪心策略 ：
初始化： 从包含所有节点的全图 $\mathcal{X}_0 = \mathcal{U} \cup \mathcal{W}$ 开始。
迭代删除： 在每一步 $t$，找到当前集合中如果被删除能使剩余集合 $g$ 值最大的那个节点 $i^\ast$（实际上是删除对当前密度贡献最小的节点）。
$$i^\ast = \arg \max _ {i \in \mathcal{X}_t} g(\mathcal{X}_t \setminus {i})$$
更新： 将 $i^\ast$ 从集合中移除，并更新其邻居的优先级。
回溯： 算法运行 $m+n$ 步直到集合为空。最后，在生成的所有中间集合 $\mathcal{X}_0, \dots, \mathcal{X} _ {m+n}$ 中，选择 $g(\mathcal{X}_t)$ 值最大的那个作为最终结果 。
为了实现近线性时间复杂度 $O(|\mathcal{E}| \log |\mathcal{V}|)$，算法使用了**优先级树（Priority Tree）**数据结构来快速查找和更新最优删除节点 。
理论保证
近似保证 (Approximation Bound)
FRAUDAR 找到的子集的密度至少是最优解的一半 。
令 $\mathcal{A}, \mathcal{B}$ 为 FRAUDAR 返回的用户和对象集合，令 $g _ {OPT}$ 为图中可能存在的最大密度值。则：
$$g(\mathcal{A} \cup \mathcal{B}) \ge \frac{1}{2} g _ {OPT}$$
证明：
对于当前节点集合 $\mathcal{S}$ 中的任意节点 $v_i$，定义其对总可疑度 $f(\mathcal{S})$ 的“贡献权重” $w_i(\mathcal{S})$ 为：
$$w_i(\mathcal{S}) = a_i + \sum _ {j \in \mathcal{S}, (i,j) \in \mathcal{E}} c _ {ij} + \sum _ {j \in \mathcal{S}, (j,i) \in \mathcal{E}} c _ {ji}$$
简单来说，这就是当节点 $v_i$ 被移除时，$f(\mathcal{S})$ 减少的量。
假设 $\mathcal{S}^\ast$ 是全局最优（密度最大）的子集，即 $g(\mathcal{S}^\ast) = g _ {OPT}$。 对于 $\mathcal{S}^\ast$ 中的每一个节点 $v_i$，必然满足 $w_i(\mathcal{S}^\ast) \ge g(\mathcal{S}^\ast)$。
- 反证法： 如果有一个节点 $v_i$ 的贡献 $w_i(\mathcal{S}^\ast) < g(\mathcal{S}^\ast)$，那么把它移除后，剩下的密度会变大：
$$
g(\mathcal{S}^\ast \setminus {v_i}) = \frac{f(\mathcal{S}^\ast) - w_i(\mathcal{S}^\ast)}{|\mathcal{S}^\ast| - 1} > \frac{f(\mathcal{S}^\ast) - g(\mathcal{S}^\ast)}{|\mathcal{S}^\ast| - 1} = \frac{f(\mathcal{S}^\ast) - f(\mathcal{S}^\ast)/|\mathcal{S}^\ast|}{|\mathcal{S}^\ast| - 1} = g(\mathcal{S}^\ast)
$$
这与 $\mathcal{S}^\ast$ 是最优解矛盾。所以所有节点的贡献都必须大于等于平均密度。
考虑 FRAUDAR 算法的执行过程。假设在算法运行中，$v_i$ 是 第一个 被删除的属于最优集 $\mathcal{S}^\ast$ 的节点。
令 $\mathcal{S}’$ 为移除 $v_i$ 之前的集合。此时显然 $\mathcal{S}^\ast \subseteq \mathcal{S}’$。
（1）由于 $\mathcal{S}^\ast \subseteq \mathcal{S}’$，节点 $v_i$ 在 $\mathcal{S}’$ 中的连边包含了它在 $\mathcal{S}^\ast$ 中的所有连边，所以权重贡献只增不减：$w_i(\mathcal{S}’) \ge w_i(\mathcal{S}^\ast) \ge g(\mathcal{S}^\ast)$。
（2）因为算法是贪心地移除“贡献最小”的节点，而 $v_i$ 是被选中的（即 $v_i$ 是当前 $\mathcal{S}’$ 中贡献最小的），所以对于 $\mathcal{S}’$ 中留下的任何其他节点 $v_j$，都有 $w_j(\mathcal{S}’) \ge w_i(\mathcal{S}’)$。
（3）对 $\mathcal{S}’$ 中所有节点的贡献求和：$\sum _ {v_j \in \mathcal{S}’} w_j(\mathcal{S}’) = 2 f(\mathcal{S}’)$（因为每条边被算了两次）。
结合上面两点：$2 f(\mathcal{S}’) = \sum w_j(\mathcal{S}’) \ge |\mathcal{S}’| w_i(\mathcal{S}’)$。
整理得：$g(\mathcal{S}’) = \frac{f(\mathcal{S}’)}{|\mathcal{S}’|} \ge \frac{w_i(\mathcal{S}’)}{2}$。
综上，$g(\mathcal{A} \cup \mathcal{B}) \ge g(\mathcal{S}’) \ge \frac{w_i(\mathcal{S}’)}{2} \ge \frac{w_i(\mathcal{S}^\ast)}{2} \ge \frac{g(\mathcal{S}^\ast)}{2} = \frac{1}{2} g _ {OPT}$
抗伪装性 (Camouflage Resistance)
只要使用列加权（权重仅依赖于对象节点的度），度量 $g$ 就是抗伪装的。这意味着欺诈者无法通过添加指向诚实对象的边来降低其所在的欺诈子集的密度值 。
PS：行加权（Row-weighting）不具备此属性，因为欺诈者可以通过关注更多人来改变自己的度，从而稀释权重。
如果边权重 $c _ {ij}$ 是基于列度（column-weighting）定义的（即 $c _ {ij}$ 仅取决于对象 $j$ 的度数），那么度量 $g$ 是抗伪装的 。
证明：
我们定义伪装是指欺诈用户集合 $\mathcal{A}$ 添加边指向诚实对象集合（即非欺诈目标）$\mathcal{W} \setminus \mathcal{B}$。
我们关注的是欺诈块 $\mathcal{S} = \mathcal{A} \cup \mathcal{B}$ 的密度 $g(\mathcal{A} \cup \mathcal{B})$。
伪装操作增加的边是在 $\mathcal{A}$ 和 $\mathcal{W} \setminus \mathcal{B}$ 之间。这不会改变欺诈块 $\mathcal{A} \cup \mathcal{B}$ 内部的边数（即 $\mathcal{A}$ 和 $\mathcal{B}$ 之间的边）。
而，分子 $f(\mathcal{A} \cup \mathcal{B})$ 不变，分母 $|\mathcal{A} \cup \mathcal{B}|$ 也不变。因此，$g(\mathcal{A} \cup \mathcal{B})$ 的值在伪装前后保持不变。这意味着欺诈者无法通过伪装来“稀释”自己的可疑度。
欺诈上限 (Bounding Fraud)：
论文还计算了在不被检测到的情况下，欺诈者最多能添加多少条边。
一个大小为 $(m_0, n_0)$ 的欺诈块，如果不被检测到，其边数上限为 ：
$$
Edges \le 2(m_0 + n_0) g _ {log}(\hat{S}) \log(m_0/\lambda + c)
$$
证明：
根据近似保证，算法找到的密度至少是最优的一半。反过来说，如果欺诈块未被检测到（假设它比算法找到的块密度低），或者即便它是最优块，其真实密度 $g(\mathcal{S} _ {fraud})$ 最多也就大概是算法输出结果的 2 倍（这是一个保守的上界估计，即 $g _ {OPT} \le 2 g _ {returned}$）。
所以，欺诈块的总可疑度 $f(\mathcal{S} _ {fraud})$ 上限为：
$$f(\mathcal{S} _ {fraud}) \le (m_0 + n_0) \times 2 g _ {log}(\hat{\mathcal{S}})$$
我们再来计算单条边的最小权重。
对于欺诈对象 $j$，其总度数 $d_j$ 中，来自欺诈者的边数为 $d _ {fraud}$。
根据假设，欺诈边占比至少为 $\lambda$，即 $d _ {fraud} / d_j \ge \lambda \implies d_j \le d _ {fraud} / \lambda$。显然欺诈边数 $d _ {fraud}$ 最多为 $m_0$（所有欺诈用户都连它）。所以该对象的总度数 $d_j \le m_0 / \lambda$。
代入权重公式 $c _ {ij} = 1/\log(d_j + c)$，可得单条边的权重下限：
$$c _ {ij} \ge \frac{1}{\log(m_0/\lambda + c)}$$
我们再来计算计算边数上限：
总可疑度 $f$ 是所有边权重的和。如果共有 $E$ 条欺诈边，那么：
$$f(\mathcal{S} _ {fraud}) = \sum _ {edges} c _ {ij} \ge E \times \frac{1}{\log(m_0/\lambda + c)}$$
结合第1步的上限：
$$E \times \frac{1}{\log(m_0/\lambda + c)} \le 2(m_0 + n_0) g _ {log}(\hat{\mathcal{S}})$$
移项即得：
$$E \le 2(m_0 + n_0) g _ {log}(\hat{\mathcal{S}}) \log(m_0/\lambda + c)$$