Active Learning on Adversarially Corrupted Graphs

arXiv:2607.04869 · cs.LG, stat.ML · Submitted 2026-07-06 · Read on arXiv

Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi, Emmanuel Esposito, Silvio Lattanzi

cs.LG, stat.ML

Submitted: 2026-07-06

Comments: 37 pages, presented at COLT 2026

Journal ref: Proceedings of Thirty Ninth Conference on Learning Theory, pages 859--895, July 2026

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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 corrupted vertices inside a graph G*.

Terminology

Abstract

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 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 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 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.

Sources

Related papers