Active Learning on Adversarially Corrupted Graphs

Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d’Orsi, Emmanuel Esposito, Silvio Lattanzi
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:859-895, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-bressan26b, title = {Active Learning on Adversarially Corrupted Graphs}, author = {Bressan, Marco and Cesa-Bianchi, Nicol{\`o} and d'Orsi, Tommaso and Esposito, Emmanuel and Lattanzi, Silvio}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {859--895}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/bressan26b/bressan26b.pdf}, url = {https://proceedings.mlr.press/v336/bressan26b.html}, 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.} }
Endnote
%0 Conference Paper %T Active Learning on Adversarially Corrupted Graphs %A Marco Bressan %A Nicolò Cesa-Bianchi %A Tommaso d’Orsi %A Emmanuel Esposito %A Silvio Lattanzi %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-bressan26b %I PMLR %P 859--895 %U https://proceedings.mlr.press/v336/bressan26b.html %V 336 %X 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.
APA
Bressan, M., Cesa-Bianchi, N., d’Orsi, T., Esposito, E. & Lattanzi, S.. (2026). Active Learning on Adversarially Corrupted Graphs. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:859-895 Available from https://proceedings.mlr.press/v336/bressan26b.html.

Related Material