[LG]《Active Learning on Adversarially Corrupted Graphs》M Bressan, N Cesa-Bianchi, T d`Orsi, E Esposito… [Università degli Studi di Milano & Bocconi University] (2026)

在图机器学习领域，识别被恶意篡改或伪造的节点是一个悬而未决的难题。过去的方法受困于对图结构完整性的过度依赖（如假设良性节点是强扩展图），本质原因是忽略了攻击者可以通过操纵边缘连接，将恶意节点巧妙地“隐藏”在图结构稀疏的区域，使传统主动学习算法的查询效率在面对结构性攻击时失效。

本文的核心洞见是：把识别恶意节点的过程重新看作是在受损图中寻找“非平衡顶点扩展”子集的问题。由此，通过引入一种改进的四阶和之乘积（Sum-of-Squares）半正定规划松弛算法，并配合一种新颖的舍入技术，使得算法能以多项式时间复杂度找到扩展性极小且规模符合预期的候选集，从而在有限的标签查询预算下实现对恶意节点的弱恢复。

这项工作真正留下的遗产是首次在理论上建立了主动学习查询复杂度与图顶点扩展（Vertex Expansion）属性之间的量化联系。它为后来者打开的新门是利用图论的结构特征来对抗复杂的对抗性结构扰动，但尚未跨过的门槛是在不牺牲计算效率的前提下，进一步缩小该算法在信息论意义上的恢复精度差距。

arxiv.org/abs/2607.04869 机器学习 人工智能 论文 AI创造营