Active sampling for graph-aware classification

Dimitris Berberidis, Georgios B. Giannakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The present work deals with data-adaptive 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 over 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 expected mean-square deviation on the GMRF, a strategy which subsumes the existing variance-minimization-based sampling method. A simple yet effective heuristic is also introduced for increasing the exploration capabilities, and reducing bias of the resultant estimator, by taking into account the confidence on the model label predictions. The novel sampling strategy is based on quantities that are readily available without the need for model retraining, rendering it 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)
Title of host publication2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages648-652
Number of pages5
ISBN (Electronic)9781509059904
DOIs
StatePublished - Mar 7 2018
Event5th IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Montreal, Canada
Duration: Nov 14 2017Nov 16 2017

Publication series

Name2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings
Volume2018-January

Other

Other5th IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017
CountryCanada
CityMontreal
Period11/14/1711/16/17

Keywords

  • Active learning
  • classification
  • expected change
  • graphs

Fingerprint Dive into the research topics of 'Active sampling for graph-aware classification'. Together they form a unique fingerprint.

  • Cite this

    Berberidis, D., & Giannakis, G. B. (2018). Active sampling for graph-aware classification. In 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings (pp. 648-652). (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/GlobalSIP.2017.8309039