Bayesian Active Learning on Graphs

Kwang Sung Jun, Robert Nowak

Research output: Chapter in Book/Report/Conference proceedingChapter


We review Bayesian active learning methods for graph signal recovery with a focus on discrete signals (e.g., binary). Bayesian models assume a generative model in which the node labels (signals) are "smooth" along the edges in the graph. In other words, two nodes with an edge in between are likely to have the same label and even more so if the edge weight is large. Ultimately, one would like to accurately predict unobserved labels based on observed node labels. In active learning, a learning algorithm is able to sequentially and adaptively select nodes, with the goal of minimizing the total number of labels needed in order to make accurate predictions for all nodes. Because we assume the label generation process is known to us, one can compute the expected error rate after observing some node labels. Thus, a natural strategy is to choose the nodes that would minimize the expected error rate. This way, one can reduce the number of labeled nodes required to achieve the same level of error rate when compared to choosing the nodes uniformly at random. A popular label-generation model for continuous labels is a Gaussian distribution over the labels with a covariance matrix that encodes the graph structure, where the one-step optimal active learning has an efficient closed-form solution. For discrete labels, natural analogs of the Gaussian distribution are used. In this case, there is no known polynomial time algorithm for active learning. For this reason, there has recently been a number of studies on efficient approximations. In this chapter, we review various algorithms that overcome the computational difficulty of active learning for discrete signals on graphs. This includes relaxation and approximation techniques for marginal distributions, which results in different behaviors and characteristics such as adaptivity. We also present empirical results on toy and real-world datasets to compare various algorithms.

Original languageEnglish (US)
Title of host publicationCooperative and Graph Signal Processing
Subtitle of host publicationPrinciples and Applications
Number of pages15
ISBN (Electronic)9780128136782
ISBN (Print)9780128136775
StatePublished - Jun 20 2018
Externally publishedYes


  • Active learning
  • Classification
  • Expected error minimization
  • Semisupervised learning
  • Transduction

ASJC Scopus subject areas

  • Medicine (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Bayesian Active Learning on Graphs'. Together they form a unique fingerprint.

Cite this