Robust Semi-Supervised Graph Classifier Learning with Negative Edge
  Weights
  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 $\mathbf{L}$ can be indefinite,
and previously proposed graph-signal smoothness prior $\mathbf{x}^T \mathbf{L}
\mathbf{x}$ for candidate signal $\mathbf{x}$ can lead to pathological
solutions. In response, we derive an optimal perturbation matrix
$\boldsymbol{\Delta}$ - based on a fast lower-bound computation of the minimum
eigenvalue of $\mathbf{L}$ via a novel application of the Haynsworth inertia
additivity formula---so that $\mathbf{L} + \boldsymbol{\Delta}$ 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.
