Robust Semisupervised Graph Classifier Learning With Negative Edge Weights

Gene Cheung

doi:10.1109/TSIPN.2018.2819018

Return

Robust Semisupervised Graph Classifier Learning With Negative Edge Weights

2018-12-01

DOI：10.1109/TSIPN.2018.2819018

Original

Save

View PDF

Abstract

En 中文

In a semisupervised 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 construct a complete graph-based binary classifier given only samples' feature vectors and partial labels. Specifically, we first build appropriate similarity graphs with positive and negative edge weights connecting all samples based on internode feature distances. By viewing a binary classifier as a piecewise constant graph signal, we cast classifier learning as a signal restoration problem via a classical maximum a posteriori (MAP) formulation. One unfortunate consequence of negative edge weights is that the graph Laplacian matrix L can be indefinite, and previously proposed graph-signal smoothness prior x(T) Lx for candidate signal x can lead to pathological solutions. In response, we derive a minimum-norm perturbation matrix. that preserves L's eigen-structure-based on a fast lower-bound computation of L's smallest negative eigenvalue via a novel application of the Haynsworth inertia additivity formula-so that L + Delta is positive semidefinite, 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 graphs that promotes ambiguity in the classifier signal. Finally, we propose an algorithm based on iterative reweighted least squares that solves the posed MAP problem efficiently. Extensive simulation results show that our proposed algorithm outperforms both SVM variants and previous graph-based classifiers using positive-edge graphs noticeably.

Keywords:

Graph signal processing

signal restoration

classifier learning

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.