在恶意篡改图中高效定位被污染顶点，仅需少量标签查询。
Active Learning on Adversarially Corrupted Graphs
- 通过约束顶点扩张度设计可高效恢复污染顶点的主动学习算法。
- 查询复杂度与攻击者能力及图的顶点扩张度呈多项式关系。
- 首次揭示顶点扩张度对鲁棒主动学习查询复杂度的关键作用。
针对现实场景中恶意实体篡改网络的问题，本文提出一种模型：攻击者试图将一组'污染顶点'隐藏在图 $G^*$ 内。攻击者可向污染顶点间及其与 $G^*$ 之间添加边，其攻击能力由污染顶点在 $G^*$ 中的邻域大小衡量。目标是设计一个主动学习算法，以极少标签查询高效识别出污染顶点子集。本文提出一种高效算法，其近似恢复性能的查询复杂度关于攻击者能力及图 $G^*$ 的顶点扩张度（vertex expansion）呈多项式依赖。核心在于，通过精心调整平方和算法，实现多项式时间求解满足基数约束的最小顶点扩张集。据我们所知，这是首次证明顶点扩张度在决定对抗性结构攻击下主动学习算法查询复杂度中起关键作用。
原文摘要 · Abstract (English)
Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} inside a graph $G^*$. To this end, the adversary can add edges between the corrupted vertices, as well as edges between the corrupted vertices and $G^*$, and its power is then measured by the size of the \emph{neighborhood} of the corrupted vertices in $G^*$. Our goal is to design an active learning algorithm that efficiently finds the subset of corrupted vertices using a small number of label queries. We devise an efficient algorithm that approximately recovers the corrupted vertices with a query complexity that depends polynomially on both the power of the adversary and the \emph{vertex expansion} of $G^*$, a fundamental measure of graph connectivity. At the heart of this result is a polynomial-time algorithm, obtained by carefully adapting sum-of-squares algorithms for approximating minimum expansion, that finds a set with small vertex expansion subject to cardinality constraints. To the best of our knowledge, this is the first time that the vertex expansion is shown to play a key role in determining the query complexity of active learning algorithms robust to structural adversarial attacks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。