Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights
arXiv:1611.04924
Abstract
In a semi-supervised learning scenario, (possibly noisy) partially observed labels are used as input to train a classifier, in order to assign labels to unclassified samples. In this paper, we study this classifier learning problem from a graph signal processing (GSP) perspective. Specifically, by viewing a binary classifier as a piecewise constant graph-signal in a high-dimensional feature space, we cast classifier learning as a signal restoration problem via a classical maximum a posteriori (MAP) formulation. Unlike previous graph-signal restoration works, we consider in addition edges with negative weights that signify anti-correlation between samples. One unfortunate consequence is that the graph Laplacian matrix can be indefinite, and previously proposed graph-signal smoothness prior for candidate signal can lead to pathological solutions. In response, we derive an optimal perturbation matrix - based on a fast lower-bound computation of the minimum eigenvalue of via a novel application of the Haynsworth inertia additivity formula---so that is positive semi-definite, resulting in a stable signal prior. Further, instead of forcing a hard binary decision for each sample, we define the notion of generalized smoothness on graph that promotes ambiguity in the classifier signal. Finally, we propose an algorithm based on iterative reweighted least squares (IRLS) that solves the posed MAP problem efficiently. Extensive simulation results show that our proposed algorithm outperforms both SVM variants and graph-based classifiers using positive-edge graphs noticeably.
arXiv comment15 pages, revised for IEEE Transactions on Signal and Information Processing over Network
References in corpus (8)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Signal Recovery on Graphs: Variation Minimization
- A more robust boosting algorithm
- Active Semi-Supervised Learning Using Sampling Theory for Graph Signals
- Localized Iterative Methods for Interpolation in Graph Structured Data
- Guided Signal Reconstruction with Application to Image Magnification