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

arXiv: https://arxiv.org/abs/2106.01642 · HTML: https://mlsanity.com/paper/2106.01642/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 3 Jun 2021.

## Builds on (most cited first, 12 of 12)

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain](https://mlsanity.com/paper/1604.07948/) (2016)
- [Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2006.08816/) (2020)
- [Chordal decomposition in operator-splitting methods for sparse semidefinite programs](https://mlsanity.com/paper/1707.05058/) (2017)
- [Large-scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications](https://mlsanity.com/paper/1411.7564/) (2014)
- [Learning Local Metrics and Influential Regions for Classification](https://mlsanity.com/paper/1802.03452/) (2018)
- [Biconvex Relaxation for Semidefinite Programming in Computer Vision](https://mlsanity.com/paper/1605.09527/) (2016)
- [A Fast Semidefinite Approach to Solving Binary Quadratic Problems](https://mlsanity.com/paper/1304.0840/) (2013)
- [Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights](https://mlsanity.com/paper/1611.04924/) (2016)
- [Fast ADMM for sum-of-squares programs using partial orthogonality](https://mlsanity.com/paper/1708.04174/) (2017)

## Built on by (most cited first, 1 of 1)

- [Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization](https://mlsanity.com/paper/2109.04697/) (2021)

## Abstract (arXiv)

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.