Active sampling for graph-aware classification

Dimitris Berberidis, Georgios B. Giannakis

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

1 Citation (Scopus)

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

Fingerprint

Labels
Sampling

Keywords

  • Active learning
  • classification
  • expected change
  • graphs

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

Active sampling for graph-aware classification. / Berberidis, Dimitris; Giannakis, Georgios B.

2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. p. 648-652 (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings; Vol. 2018-January).

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

Berberidis, D & Giannakis, GB 2018, Active sampling for graph-aware classification. in 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings, vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 648-652, 5th IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017, Montreal, Canada, 11/14/17. https://doi.org/10.1109/GlobalSIP.2017.8309039
Berberidis D, Giannakis GB. Active sampling for graph-aware classification. In 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2018. p. 648-652. (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings). https://doi.org/10.1109/GlobalSIP.2017.8309039
Berberidis, Dimitris ; Giannakis, Georgios B. / Active sampling for graph-aware classification. 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 648-652 (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings).
@inproceedings{a6f04c60e60142c9bd9dab0915e0adc4,
title = "Active sampling for graph-aware classification",
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.",
keywords = "Active learning, classification, expected change, graphs",
author = "Dimitris Berberidis and Giannakis, {Georgios B.}",
year = "2018",
month = "3",
day = "7",
doi = "10.1109/GlobalSIP.2017.8309039",
language = "English (US)",
series = "2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "648--652",
booktitle = "2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings",

}

TY - GEN

T1 - Active sampling for graph-aware classification

AU - Berberidis, Dimitris

AU - Giannakis, Georgios B.

PY - 2018/3/7

Y1 - 2018/3/7

N2 - 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.

AB - 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.

KW - Active learning

KW - classification

KW - expected change

KW - graphs

UR - http://www.scopus.com/inward/record.url?scp=85048031988&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048031988&partnerID=8YFLogxK

U2 - 10.1109/GlobalSIP.2017.8309039

DO - 10.1109/GlobalSIP.2017.8309039

M3 - Conference contribution

AN - SCOPUS:85048031988

T3 - 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings

SP - 648

EP - 652

BT - 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -