# Robust Offline Active Learning on Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 15 Aug 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [A Survey of Deep Active Learning](https://mlsanity.com/paper/2009.00236/) (2020)
- [Active Learning for Graph Embedding](https://mlsanity.com/paper/1705.05085/) (2017)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Signal Recovery on Graphs: Variation Minimization](https://mlsanity.com/paper/1411.7414/) (2014)
- [RIM: Reliable Influence-based Active Learning on Graphs](https://mlsanity.com/paper/2110.14854/) (2021)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach](https://mlsanity.com/paper/1711.05174/) (2017)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [Information Gain Propagation: a new way to Graph Active Learning with Soft Labels](https://mlsanity.com/paper/2203.01093/) (2022)
- [Random sampling of bandlimited signals on graphs](https://mlsanity.com/paper/1511.05118/) (2015)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [Partition-Based Active Learning for Graph Neural Networks](https://mlsanity.com/paper/2201.09391/) (2022)
- [Active Semi-Supervised Learning Using Sampling Theory for Graph Signals](https://mlsanity.com/paper/1405.4324/) (2014)
- [Active Learning on Attributed Graphs via Graph Cognizant Logistic Regression and Preemptive Query Generation](https://mlsanity.com/paper/2007.05003/) (2020)
- [A Structural-Clustering Based Active Learning for Graph Neural Networks](https://mlsanity.com/paper/2312.04307/) (2023)

## Built on by (most cited first, 3 of 3)

- [RANA: Robust Active Learning for Noisy Network Alignment](https://mlsanity.com/paper/2507.22434/) (2025)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)
- [Active Learning on Adversarially Corrupted Graphs](https://mlsanity.com/paper/2607.04869/) (2026)

## Abstract (arXiv)

We consider the problem of active learning on graphs, which has crucial applications in many real-world networks where labeling node responses is expensive. In this paper, we propose an offline active learning method that selects nodes to query by explicitly incorporating information from both the network structure and node covariates. Building on graph signal recovery theories and the random spectral sparsification technique, the proposed method adopts a two-stage biased sampling strategy that takes both informativeness and representativeness into consideration for node querying. Informativeness refers to the complexity of graph signals that are learnable from the responses of queried nodes, while representativeness refers to the capacity of queried nodes to control generalization errors given noisy node-level information. We establish a theoretical relationship between generalization error and the number of nodes selected by the proposed method. Our theoretical results demonstrate the trade-off between informativeness and representativeness in active learning. Extensive numerical experiments show that the proposed method is competitive with existing graph-based active learning methods, especially when node covariates and responses contain noises. Additionally, the proposed method is applicable to both regression and classification tasks on graphs.