title: Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment
abstract: 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.
authors: Cheng Yang Gene Cheung Wai-tian Tan Guangtao Zhai
hIndex: Guangtao Zhai 44