# Active Learning on Adversarially Corrupted Graphs

arXiv: https://arxiv.org/abs/2607.04869 · HTML: https://mlsanity.com/paper/2607.04869/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 51 references that are in the map.
- First posted on arXiv 6 Jul 2026.

## Builds on (most cited first, 21 of 21)

- [A Survey of Adversarial Learning on Graphs](https://mlsanity.com/paper/2003.05730/) (2020)
- [A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning](https://mlsanity.com/paper/1910.14147/) (2019)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Active Learning on Trees and Graphs](https://mlsanity.com/paper/1301.5112/) (2013)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Algorithms approaching the threshold for semi-random planted clique](https://mlsanity.com/paper/2212.05619/) (2022)
- [Robust recovery for stochastic block models, simplified and generalized](https://mlsanity.com/paper/2402.13921/) (2024)
- [Semirandom Planted Clique and the Restricted Isometry Property](https://mlsanity.com/paper/2404.14159/) (2024)
- [Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues](https://mlsanity.com/paper/2203.06168/) (2022)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Robust Offline Active Learning on Graphs](https://mlsanity.com/paper/2408.07941/) (2024)
- [Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion](https://mlsanity.com/paper/1404.4575/) (2014)
- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [New Approximation Bounds for Small-Set Vertex Expansion](https://mlsanity.com/paper/2311.17001/) (2023)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)

## Abstract (arXiv)

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.