Fast Graph-based Binary Classifier Learning via Further Relaxation of Semi-Definite Relaxation
Xiao Li, Cheng Yang, Weilin Tong, Fangyu Shi, Guangtao Zhai · 2022
Although semi-definite relaxation (SDR) can be used to solve NP-hard, semi-supervised, graph-based binary classification problems, existing solvers for SDR generally consist of projection onto a positive semi-definite (PSD) cone that has high time complexityper iteration. A faster algorithm that solves graph-based binary classification problems with a sequence of linear programs based on Gershgorin Disc Perfect Alignment (GDPA) linearization does not require PSD cone projection, but the overall time complexity can still be as high as due to the requirement of solving multiple linear programs. In this paper, we propose a fast graph-based binary classification problem solver with only time complexity. We overcome the computation burden by further relaxation of SDR (RSDR). Specifically, we first derive an upper bound of the Shur complement of the last diagonal entry of the PSD classification matrix, and then derive a trivial solution of the dual of the semi-definite program (SDP) for the graph-based binary classification problem. The only time-consuming part of the proposed solver is the computation of the first eigenvector of the PSD classification matrix, where we adopt Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG), that is known to have linear time complexity. Experimental results show that (i) our proposed RSDR performs on average faster than GDPA linearization based SDR across all experimented datasets with comparable classification error rates, and (ii) the unrolling version of our proposed RSDR that learns the PSD Mahalanobis distance metric matrix has fewer number of trainable parameters compared to conventional black-box networks, is up to faster than the unrolling version of GDPA linearization based SDR (SDR unrolling) in inference time, and has smaller average classification error rates compared to SDR unrolling.