Data-Adaptive Active Sampling for Efficient Graph-Cognizant Classification

Dimitris Berberidis, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper deals with active sampling of graph nodes representing training data for binary classification. The graph may be given or constructed using similarity measures among nodal features. Leveraging the graph for classification builds on the premise that labels across neighboring nodes are correlated according to a categorical Markov random field (MRF). This model is further relaxed to a Gaussian (G)MRF with labels taking continuous values - an approximation that not only mitigates the combinatorial complexity of the categorical model, but also offers optimal unbiased soft predictors of the unlabeled nodes. The proposed sampling strategy is based on querying the node whose label disclosure is expected to inflict the largest change on the GMRF, and in this sense it is the most informative on average. Connections are established to other sampling methods including uncertainty sampling, variance minimization, and sampling based on the Σ-optimality criterion. A simple yet effective heuristic is also introduced for increasing the exploration capabilities of the sampler, and reducing bias of the resultant classifier, by adjusting the confidence on the model label predictions. The novel sampling strategies are based on quantities that are readily available without the need for model retraining, rendering them computationally efficient and scalable to large graphs. Numerical tests using synthetic and real data demonstrate that the proposed methods achieve accuracy that is comparable or superior to the state of the art even at reduced runtime.

Original languageEnglish (US)
Article number8445612
Pages (from-to)5167-5179
Number of pages13
JournalIEEE Transactions on Signal Processing
Issue number19
StatePublished - Oct 1 2018

Bibliographical note

Funding Information:
Manuscript received February 17, 2018; revised May 20, 2018 and July 14, 2018; accepted August 13, 2018. Date of publication August 24, 2018; date of current version September 5, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Wee Peng Tay. This work was supported by National Science Foundation under Grant 1711471, under Grant 1500713, and under Grant 1442686. (Corresponding author: Georgios B. Giannakis.) The authors are with the Department of Electronic and Communication Engineering and Digital Technology Center, University of Minnesota, Minneapolis, MN 55455 USA (e-mail:,;

Publisher Copyright:
© 1991-2012 IEEE.


  • Active learning
  • classification
  • expected change
  • graph-based


Dive into the research topics of 'Data-Adaptive Active Sampling for Efficient Graph-Cognizant Classification'. Together they form a unique fingerprint.

Cite this