Active Learning on Adversarially Corrupted Graphs

技术摘要：对抗性损坏图上的主动学习

问题定义
本文研究了在底层结构被对手篡改的图上进行**主动学习（active learning）**的问题。该设定涉及一个初始的“地面真值（ground-truth）”图 $G^* = (V^*, E^*)$ 和一组损坏的（恶意的）顶点集合 $I$。一个拥有预算 $b$ 的对手通过以下三个步骤构建最终的图 $G$：

1. 在一组新的顶点集 $I$ 上创建一个任意的子图（其中 $|I| \le |V^*|$）。
2. 将最多 $b$ 个来自 $V^*$ 的顶点连接到集合 $I$。这定义了对手的能力：$I$ 在 $G$ 中的边界大小受限（即 $|\partial_G(I)| \le b$）。
3. 在 $G^*$ 内部任意添加边。
   算法接收生成的图 $G$，并可以使用标签查询器（label oracle） $O_{G,I}$，该查询器会揭示被查询的顶点是否属于 $I$。目标是实现弱恢复（weak recovery）：以高概率识别出一个子集 $\hat{I}$，使得对称差 $|\hat{I} \triangle I| \le \gamma |V(G)|$，并使用最小的标签查询次数。挑战在于 $G^*$ 和损坏的子图 $G[I]$ 都可以是任意的，且对手可以显著操纵图的结构，只要其与原图的连接数量保持在较小范围内。

方法论
所提方案依赖于**顶点扩张（vertex expansion）**的结构特性和一个递归算法框架。

1. 结构洞察： 核心直觉是，如果损坏顶点集 $I$ 的顶点扩张显著小于图 $G^*$ 的“良好”部分，则它可以被隔离。具体而言，作者定义了一个条件，即 $I$ 相对于其余部分是“扩张性较差的”。如果 $I$ 满足特定的扩张间隙条件，那么任何具有小边界且规模与 $I$ 相当的集合 $S$ 都必然与 $I$ 高度相关。

2. 算法核心（平方和 Sum-of-Squares）： 为了寻找这样一个集合 $S$，作者改编了**平方和（SoS）**算法，特别是修改了 Feige 等人 (2005) 提出的用于顶点扩张的半正定规划 (SDP) 松弛。

   • 标准的顶点扩张算法通常无法保证返回集合的大小，或者提供的近似因子对于这种特定的对抗环境来说过于宽松。
   • 作者引入了一种针对度数为 4 的 SoS 松弛的创新舍入算法（rounding algorithm）。这种舍入确保了输出集合 $S$ 满足基数约束（即 $|S| = \Theta(|I|)$），同时保持较小的边界。
   • 这种改编使得算法能够找到一个在规模约束下近似最小顶点扩张的集合 $S$，这是一个独立的有趣结果（定理 4）。

3. 递归细化： 算法迭代运行：

   • 它利用基于 SoS 的过程来寻找一个与剩余损坏顶点高度相关的集合 $S$。
   • 它对 $S$ 及其补集的少量随机样本进行查询，以确定哪个集合包含多数损坏节点。
   • 识别出的集合从图中移除，并在剩余图上重复此过程。
   • 作者证明了（特别是剩余地面真值图的）结构特性在这些迭代中得到了充分的保留，从而允许算法继续恢复损坏的节点，直到识别出高比例的节点。

关键结果
主要贡献是定理 3，它确立了弱恢复的查询复杂度。如果满足以下条件，算法可实现 $(\gamma, \delta, q, b)$-弱恢复：

• 查询预算 $q$ 随 $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$ 缩放。
• 对手预算 $b$ 受限于地面真值图 $G^*$ 的顶点扩张：$b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$，其中 $\partial_{\eta n}(G^*)$ 是规模至少为 $\eta n$ 的子集的最小边界。

本质上，所需的查询次数与对手的预算 $b$ 成线性关系，并与期望精度 $\gamma$ 成反比，前提是对手的预算相对于图的连通性（顶点扩张）较小。

此外，定理 4 提出了一个辅助结果：一个随机多项式时间算法，可以在平衡范围 $[m, n-m]$ 内找到具有小顶点扩张的集合，在某些参数下达到 $O(\sqrt{\log n})$ 的近似因子。这改进或补充了现有的关于小集合扩张问题的界限。

意义与主张
本文声称，它是第一个证明顶点扩张是决定对抗性结构攻击下鲁棒的主动学习算法查询复杂度的基本度量的研究。

• 新颖性： 不同于以往关于 Sybil 攻击或图投毒的研究（通常假设“良好”的图是扩张图或限制了增加的边数），本模型允许“好”子图和“坏”子图具有任意的内部结构，仅对边界大小进行限制。
• 理论基础： 该工作提供了图连通性（顶点扩张）与检测损坏节点可行性之间的理论联系。它表明，即使地面真值图不是全局扩张图，只要对手的预算相对于足够大的子集的扩张程度较小，弱恢复就是可能的。
• 算法贡献： 本文通过利用并改编平方和技术，引入了一种在基数约束下寻找具有小顶点扩张集合的多项式时间算法，而这是一个已知计算困难的问题。

作者保持了谦逊的基调，指出其结果依赖于特定的扩张间隙，并且当期望精度 $\gamma$ 降低或对手预算 $b$ 增加时，查询复杂度会下降。他们并未声称解决了所有可能的图结构或任意对手预算下的问题，而是建立了一个关于查询成本、精度以及输入图结构属性之间的精确权衡。