# Signed Graph Learning: Algorithms and Theory

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 13 Jul 2025.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [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)
- [Global Convergence of ADMM in Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1511.06324/) (2015)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [Large Scale Graph Learning from Smooth Signals](https://mlsanity.com/paper/1710.05654/) (2017)
- [Identifying the Topology of Undirected Networks from Diffused Non-stationary Graph Signals](https://mlsanity.com/paper/1801.03862/) (2018)
- [Balance in signed networks](https://mlsanity.com/paper/1809.05140/) (2018)
- [Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming](https://mlsanity.com/paper/2409.07794/) (2024)
- [Community-Aware Graph Signal Processing](https://mlsanity.com/paper/2008.10375/) (2020)

## Abstract (arXiv)

Real-world data is often represented through the relationships between data samples, forming a graph structure. In many applications, it is necessary to learn this graph structure from the observed data. Current graph learning research has primarily focused on unsigned graphs, which consist only of positive edges. However, many biological and social systems are better described by signed graphs that account for both positive and negative interactions, capturing similarity and dissimilarity between samples. In this paper, we develop a method for learning signed graphs from a set of smooth signed graph signals. Specifically, we employ the net Laplacian as a graph shift operator (GSO) to define smooth signed graph signals as the outputs of a low-pass signed graph filter defined by the net Laplacian. The signed graph is then learned by formulating a non-convex optimization problem where the total variation of the observed signals is minimized with respect to the net Laplacian. The proposed problem is solved using alternating direction method of multipliers (ADMM) and a fast algorithm reducing the per-ADMM iteration complexity from quadratic to linear in the number of nodes is introduced. Furthermore, theoretical proofs of convergence for the algorithm and a bound on the estimation error of the learned net Laplacian as a function of sample size, number of nodes, and graph topology are provided. Finally, the proposed method is evaluated on simulated data and gene regulatory network inference problem and compared to existing signed graph learning methods.