Efficient and Robust Semi-Supervised Learning Over a Sparse-Regularized Graph


Graph-based Semi-Supervised Learning (GSSL) has limitations in widespread applicability due to its computationally prohibitive large-scale inference, sensitivity to data incompleteness, and incapability on handling time-evolving characteristics in an open set. To address these issues, we propose a novel GSSL based on a batch of informative beacons with sparsity appropriately harnessed, rather than constructing the pairwise affinity graph between the entire original samples. Specifically, (1) beacons are placed automatically by unifying the consistence of both data features and labels, which subsequentially act as indicators during the inference; (2) leveraging the information carried by beacons, the sample labels are interpreted as the weighted combination of a subset of characteristics-specified beacons; (3) if unfamiliar samples are encountered in an open set, we seek to expand the beacon set incrementally and update their parameters by incorporating additional human interventions if necessary. Experimental results on real datasets validate that our algorithm is effective and efficient to implement scalable inference, robust to sample corruptions, and capable to boost the performance incrementally in an open set by updating the beacon-related parameters.

Meeting Name

14th European Conference on Computer Vision, ECCV (2016: Oct. 8-16, Amsterdam, The Netherlands)


Computer Science

Research Center/Lab(s)

Intelligent Systems Center

Keywords and Phrases

Computer Vision; Graphic Methods; Inference Engines; Beacon; Evolving Characteristic; Human Intervention; Online Learning; Original Sample; Real Data Sets; Semi-Supervised Learning; Sparse Representation; Supervised Learning; Beacon

International Standard Book Number (ISBN)


International Standard Serial Number (ISSN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2016 Springer Verlag, All rights reserved.

Publication Date

01 Jan 2016