# Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 76 references that are in the map.
- First posted on arXiv 2 Jun 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Image Restoration using Total Variation Regularized Deep Image Prior](https://mlsanity.com/paper/1810.12864/) (2018)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [Feature Graph Learning for 3D Point Cloud Denoising](https://mlsanity.com/paper/1907.09138/) (2019)
- [Signal Recovery on Graphs: Variation Minimization](https://mlsanity.com/paper/1411.7414/) (2014)
- [Structured Graph Learning Via Laplacian Spectral Constraints](https://mlsanity.com/paper/1909.11594/) (2019)
- [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)
- [Untrained Graph Neural Networks for Denoising](https://mlsanity.com/paper/2109.11700/) (2021)
- [Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)](https://mlsanity.com/paper/2006.11220/) (2020)
- [Graph Signal Restoration Using Nested Deep Algorithm Unrolling](https://mlsanity.com/paper/2106.15910/) (2021)
- [Bilateral Filter: Graph Spectral Interpretation and Extensions](https://mlsanity.com/paper/1303.2685/) (2013)
- [Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors](https://mlsanity.com/paper/2406.04090/) (2024)
- [Spreading and Structural Balance on Signed Networks](https://mlsanity.com/paper/2212.10158/) (2022)
- [Robust Deep Signed Graph Clustering via Weak Balance Theory](https://mlsanity.com/paper/2502.05472/) (2025)
- [Graph Fourier Transform with Negative Edges for Depth Image Coding](https://mlsanity.com/paper/1702.03105/) (2017)
- [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)
- [Complex Graph Laplacian Regularizer for Inferencing Grid States](https://mlsanity.com/paper/2307.01906/) (2023)

## Abstract (arXiv)

Signed graphs are equipped with both positive and negative edge weights, encoding pairwise correlations as well as anti-correlations in data. A balanced signed graph is a signed graph with no cycles containing an odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map via a simple linear transform to ones in a corresponding positive graph Laplacian, thus enabling reuse of spectral filtering tools designed for positive graphs. We propose an efficient computation method to learn a balanced signed graph Laplacian directly from data. Specifically, extending a previous linear programming (LP) based sparse inverse covariance estimation method called CLIME, we formulate a new LP problem for each Laplacian column i, where the linear constraints restrict weight signs of edges stemming from node i, so that nodes of same / different polarities are connected by positive / negative edges. We derive a feasible CLIME parameter ρi for each sign-constrained column problem. We solve the LP problem efficiently by tailoring a sparse LP method based on ADMM. We theoretically prove that the row / column updates produce a non-increasing objective sequence, and show that the iterations are terminated in a finite number of steps. Extensive experimental results on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables reuse of spectral filters, wavelets, and graph neural nets (GNN) constructed for positive graphs.