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

2021/06/03 by Cheng Yang, Yang, Cheng, Gene Cheung +3
Computer Science · Engineering · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Metaheuristic Optimization Algorithms Research #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2106.01642

openalex publication_date 2021/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite Relaxation of Quadratic Optimization Problems
• Algorithm 778: L-BFGS-B
• Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method
• Structural balance: a generalization of Heider's theory.
• Artificial intelligence: a modern approach
• Learning Graphs From Data: A Signal Representation Perspective

Related

• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization
• Graph Metric Learning via Gershgorin Disc Alignment
• Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment
• Graph Construction with Label Information for Semi-Supervised Learning
• Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights