# Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

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

- [Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors](https://mlsanity.com/paper/2406.04090/) (2024)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming](https://mlsanity.com/paper/2409.07794/) (2024)
- [Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2106.01642/) (2021)
- [Graph Sparsification for GCN Towards Optimal Crop Yield Predictions](https://mlsanity.com/paper/2306.01725/) (2023)
- [Signal Processing in the Retina: Interpretable Graph Classifier to Predict Ganglion Cell Responses](https://mlsanity.com/paper/2401.01813/) (2024)
- [Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization](https://mlsanity.com/paper/2109.04697/) (2021)
- [Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding](https://mlsanity.com/paper/2112.07862/) (2021)
- [Unsupervised Graph Spectral Feature Denoising for Crop Yield Prediction](https://mlsanity.com/paper/2208.02714/) (2022)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [Constructing an Interpretable Deep Denoiser by Unrolling Graph Laplacian Regularizer](https://mlsanity.com/paper/2409.06676/) (2024)
- [Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming](https://mlsanity.com/paper/2506.01826/) (2025)
- [Lightweight Transformer for EEG Classification via Balanced Signed Graph Algorithm Unrolling](https://mlsanity.com/paper/2510.03027/) (2025)
- [Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation](https://mlsanity.com/paper/2606.24011/) (2026)
- [Graph Learning with Spectral Connectivity Priors for Scarce Data](https://mlsanity.com/paper/2609.27278/) (2026)

## Abstract (arXiv)

Given a convex and differentiable objective Q(M) for a real symmetric matrix M in the positive definite (PD) cone -- used to compute Mahalanobis distances -- we propose a fast general metric learning framework that is entirely projection-free. We first assume that M resides in a space cS of generalized graph Laplacian matrices corresponding to balanced signed graphs. M ∈ cS that is also PD is called a graph metric matrix. Unlike low-rank metric matrices common in the literature, cS includes the important diagonal-only matrices as a special case. The key theorem to circumvent full eigen-decomposition and enable fast metric matrix optimization is Gershgorin disc perfect alignment (GDPA): given M ∈ cS and diagonal matrix S, where Sii = 1/vi and v is M's first eigenvector, we prove that Gershgorin disc left-ends of similarity transform B = S M S-1 are perfectly aligned at the smallest eigenvalue λmin. Using this theorem, we replace the PD cone constraint in the metric learning problem with tightest possible linear constraints per iteration, so that the alternating optimization of the diagonal / off-diagonal terms in M can be solved efficiently as linear programs via the Frank-Wolfe method. We update v using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as entries in M are optimized successively. Experiments show that our graph metric optimization is significantly faster than cone-projection schemes, and produces competitive binary classification performance.