Graph-based active learning: A new look at expected error minimization

Kwang-Sung Jun, Robert D. Nowak

Abstract

Active learning on graphs often relies on Expected Error Minimization (EEM), but exact EEM is computationally NP-hard. This paper introduces TSA (Two-Step Approximation), a novel algorithm that approximates EEM with $O(n^2)$ complexity, effectively balancing the "exploration-exploitation" trade-off that causes existing state-of-the-art methods to fail.

Introduction

In graph-based active learning, the objective is to strategically query labels for a small subset of nodes to minimize overall prediction error. The gold standard for this is Expected Error Minimization (EEM). However, for binary labels in a Markov Random Field (BMRF), calculating EEM exactly is a combinatorial challenge. Existing approximations typically suffer from being either too exploitation-heavy (e.g., ZLG), failing to explore hidden clusters, or too exploration-heavy (e.g., SOpt, VOpt), ignoring discovered labels and querying inefficiently.

Methodology: Two-Step Approximation (TSA)

The proposed TSA algorithm bridges the gap between exploration and exploitation. TSA approximates the posterior marginal probability of a node's label using a two-step mathematical relaxation:

  1. Upper-bounding: The log-sum-exp function in the posterior marginal calculation is upper-bounded, converting the problem into an integer optimization task.
  2. Relaxation: Integer constraints are relaxed to real values, yielding a concave quadratic maximization problem with a closed-form solution.

A key insight of TSA is the incorporation of node variance. In the resulting formula, nodes with high variance (those distant from labeled data) have their marginal probabilities pushed toward 0.5. This mechanism naturally encourages the algorithm to explore uncertain regions, while the label-dependent component ensures exploitation of known boundaries. To maintain efficiency, the authors utilize a "dongle node" trick and one-step covariance updates, achieving a computational complexity of $O(n^2)$ per query.

Experimental Results

The authors evaluated TSA against several baselines, including Random, ZLG, VOpt, SOpt, and exact BMRF, using both synthetic and real-world datasets.

Performance comparison of TSA against baselines on toy and real-world datasets.

Synthetic Benchmarks

On a Linear Chain (18 nodes), TSA was the only approximation that matched the behavior of the exact BMRF, successfully exploring the entire chain while ZLG remained localized. Similarly, on the Jittered Box dataset, TSA demonstrated the ability to discover multiple distinct label clusters.

Real-World Datasets

TSA's performance was further validated on citation and co-authorship networks:

  • DBLP: A co-authorship network.
  • CORA & CITESEER: Scientific paper citation networks.

Across these datasets, TSA consistently outperformed or matched the best-performing baselines at every stage of the query process. It demonstrated robustness by performing competitively with exploration-focused methods in early stages and exploitation-focused methods in later stages.

Discussion and Future Work

While TSA demonstrates strong performance, the BMRF model relies on a smoothness parameter $\beta$. In these experiments, $\beta=1$ was used, but automatic tuning of this parameter in an active learning context remains an open challenge. Additionally, while TSA can be applied to multi-class problems via a one-vs-rest strategy, future work could explore more integrated multi-class probabilistic models.

Conclusion

TSA offers a significant improvement for graph-based active learning by providing a high-quality, $O(n^2)$ approximation of EEM. By integrating node variance into the decision process, it effectively navigates the exploration-exploitation trade-off, outperforming existing state-of-the-art approximations across a variety of network structures.

Summary updated

BibTeX
@inproceedings{jun2016graph,
  author = {Kwang-Sung Jun and Robert D. Nowak},
  title = {{Graph-based active learning: A new look at expected error minimization}},
  booktitle = {GlobalSIP},
  year = {2016},
  doi = {10.1109/globalsip.2016.7906056},
}
Figure