# Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 12 Sep 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [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)
- [Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images](https://mlsanity.com/paper/1607.01895/) (2016)
- [Manifold Graph Signal Restoration using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2206.04245/) (2022)
- [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)

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

- [Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming](https://mlsanity.com/paper/2506.01826/) (2025)
- [Signed Graph Learning: Algorithms and Theory](https://mlsanity.com/paper/2507.09717/) (2025)
- [Lightweight Transformer for EEG Classification via Balanced Signed Graph Algorithm Unrolling](https://mlsanity.com/paper/2510.03027/) (2025)
- [Graph Learning with Spectral Connectivity Priors for Scarce Data](https://mlsanity.com/paper/2609.27278/) (2026)

## 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 has no cycles of odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map simply to ones in a similarity-transformed positive graph Laplacian, thus enabling reuse of well-studied spectral filters designed for positive graphs. We propose a fast method to learn a balanced signed graph Laplacian directly from data. Specifically, for each node i, to determine its polarity βi ∈ -1,1 and edge weights wi,jj=1N, we extend a sparse inverse covariance formulation based on linear programming (LP) called CLIME, by adding linear constraints to enforce ``consistent" signs of edge weights wi,jj=1N with the polarities of connected nodes -- i.e., positive/negative edges connect nodes of same/opposing polarities. For each LP, we adapt projections on convex set (POCS) to determine a suitable CLIME parameter ρ > 0 that guarantees LP feasibility. We solve the resulting LP via an off-the-shelf LP solver in O(N2.055). Experiments on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables the use of spectral filters and graph convolutional networks (GCNs) designed for positive graphs on signed graphs.