Projection-free Graph-based Classifier Learning using Gershgorin Disc
  Perfect Alignment
  In semi-supervised graph-based binary classifier learning, a subset of known
labels $\hat{x}_i$ are used to infer unknown labels, assuming that the label
signal $x$ is smooth with respect to a similarity graph specified by a
Laplacian matrix. When restricting labels $x_i$ to binary values, the problem
is NP-hard. While a conventional semi-definite programming (SDP) relaxation can
be solved in polynomial time using, for example, the alternating direction
method of multipliers (ADMM), the complexity of iteratively projecting a
candidate matrix $M$ onto the positive semi-definite (PSD) cone ($M \succeq 0$)
remains high. In this paper, leveraging a recent linear algebraic theory called
Gershgorin disc perfect alignment (GDPA), we propose a fast projection-free
method by solving a sequence of linear programs (LP) instead. Specifically, we
first recast the SDP relaxation to its SDP dual, where a feasible solution $H
\succeq 0$ can be interpreted as a Laplacian matrix corresponding to a balanced
signed graph sans the last node. To achieve graph balance, we split the last
node into two that respectively contain the original positive and negative
edges, resulting in a new Laplacian $\bar{H}$. We repose the SDP dual for
solution $\bar{H}$, then replace the PSD cone constraint $\bar{H} \succeq 0$
with linear constraints derived from GDPA -- sufficient conditions to ensure
$\bar{H}$ is PSD -- so that the optimization becomes an LP per iteration.
Finally, we extract predicted labels from our converged LP solution $\bar{H}$.
Experiments show that our algorithm enjoyed a $40\times$ speedup on average
over the next fastest scheme while retaining comparable label prediction
performance.
