Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment

In semi-supervised graph-based binary classifier learning, a subset of known labels hatxi 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 xi 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 M onto the positive semi-definite (PSD) cone (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 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 barH. We repose the SDR dual for solution barH, then replace the PSD cone constraint barH succeq 0 with linear constraints derived from GDPA -- sufficient conditions to ensure barH is PSD -- so that the optimization becomes an LP per iteration. Finally, we extract predicted labels from converged solution barH. Experiments show that our algorithm enjoyed a 28× speedup over the next fastest scheme while achieving comparable label prediction performance.