# Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 57 references that are in the map.
- First posted on arXiv 10 Sep 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Group Normalization](https://mlsanity.com/paper/1803.08494/) (2018)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Learning Deep CNN Denoiser Prior for Image Restoration](https://mlsanity.com/paper/1704.03264/) (2017)
- [Model-Based Deep Learning](https://mlsanity.com/paper/2012.08405/) (2020)
- [An Exploration of Softmax Alternatives Belonging to the Spherical Loss Family](https://mlsanity.com/paper/1511.05042/) (2015)
- [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)
- [Locally Linear Embedding and its Variants: Tutorial and Survey](https://mlsanity.com/paper/2011.10925/) (2020)
- [Differentiating through Log-Log Convex Programs](https://mlsanity.com/paper/2004.12553/) (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)
- [Fast ADMM for sum-of-squares programs using partial orthogonality](https://mlsanity.com/paper/1708.04174/) (2017)
- [Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2106.01642/) (2021)

## Abstract (arXiv)

Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. However, unfolding a proximal splitting algorithm with a positive semi-definite (PSD) cone projection operator per iteration is expensive, due to the required full matrix eigen-decomposition. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph classifier, where the PSD cone constraint is replaced by a set of "tightest possible" linear constraints per iteration. As a result, each iteration only requires computing a linear program (LP) and one extreme eigenvector. Inside the unrolled network, we optimize parameters via stochastic gradient descent (SGD) that determine graph edge weights in two ways: i) a metric matrix that computes feature distances, and ii) a sparse weight matrix computed via local linear embedding (LLE). Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.