Data-Adaptive Active Sampling for Efficient Graph-Cognizant Classification

DOI10.1109/TSP.2018.2866812zbMATH Open1414.62229arXiv1705.07220OpenAlexW2624258999MaRDI QIDQ4628154FDOQ4628154

Authors: Dimitris Berberidis, Georgios B. Giannakis 

Publication date: 6 March 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: The present work 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. Such a strategy subsumes several measures of expected model change, including uncertainty sampling, variance minimization, and sampling based on the $Sigma-$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 taking into account 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.

Full work available at URL: https://arxiv.org/abs/1705.07220

Recommendations

• A Scalable Algorithm for Graph-Based Active Learning
• Learning an efficient constructive sampler for graphs
• Graph-Based Active Learning Based on Label Propagation
• scientific article; zbMATH DE number 1929161
• Adaptive graph construction using data self-representativeness for pattern classification
• Adaptive Diffusions for Scalable Learning Over Graphs
• Adaptive Hypergraph Learning and its Application in Image Classification
• A Sampling Theory Perspective of Graph-Based Semi-Supervised Learning

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Applications of graph theory (05C90)

Cited In (1)

• Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations

This page was built for publication: Data-Adaptive Active Sampling for Efficient Graph-Cognizant Classification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628154)