  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 $\mathbf{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 relaxation (SDR) can
be solved in polynomial time using, for example, the alternating direction
method of multipliers (ADMM), the complexity of projecting a candidate matrix
$\mathbf{M}$ onto the positive semi-definite (PSD) cone ($\mathbf{M} \succeq
0$) per iteration 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 SDR to its dual, where a feasible
solution $\mathbf{H} \succeq 0$ is interpreted as a Laplacian matrix
corresponding to a balanced signed graph minus the last node. To achieve graph
balance, we split the last node into two, each retains the original positive /
negative edges, resulting in a new Laplacian $\bar{\mathbf{H}}$. We repose the
SDR dual for solution $\bar{\mathbf{H}}$, then replace the PSD cone constraint
$\bar{\mathbf{H}} \succeq 0$ with linear constraints derived from GDPA --
sufficient conditions to ensure $\bar{\mathbf{H}}$ is PSD -- so that the
optimization becomes an LP per iteration. Finally, we extract predicted labels
from converged solution $\bar{\mathbf{H}}$. Experiments show that our algorithm
enjoyed a $28\times$ speedup over the next fastest scheme while achieving
comparable label prediction performance.
