# Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 12 May 2021.

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

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [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)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Regularization via Mass Transportation](https://mlsanity.com/paper/1710.10016/) (2017)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [Large Scale Graph Learning from Smooth Signals](https://mlsanity.com/paper/1710.05654/) (2017)
- [Learning Sparse Graphs Under Smoothness Prior](https://mlsanity.com/paper/1609.03448/) (2016)
- [Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine](https://mlsanity.com/paper/2010.12865/) (2020)
- [Distributionally Robust Optimization with Decision Dependent Ambiguity Sets](https://mlsanity.com/paper/1806.09215/) (2018)
- [A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1910.12778/) (2019)
- [Robust Graph Learning Under Wasserstein Uncertainty](https://mlsanity.com/paper/2105.04210/) (2021)

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

- [Uncertainty Quantification on Graph Learning: A Survey](https://mlsanity.com/paper/2404.14642/) (2024)
- [Distributionally Robust Skeleton Learning of Discrete Bayesian Networks](https://mlsanity.com/paper/2311.06117/) (2023)
- [Learning Time-Varying Graphs from Incomplete Graph Signals](https://mlsanity.com/paper/2510.17903/) (2025)
- [Multi-Source Wasserstein Distributionally Robust Graph Learning](https://mlsanity.com/paper/2608.19914/) (2026)

## Abstract (arXiv)

We consider the problem of learning a graph from a finite set of noisy graph signal observations, the goal of which is to find a smooth representation of the graph signal. Such a problem is motivated by the desire to infer relational structure in large datasets and has been extensively studied in recent years. Most existing approaches focus on learning a graph on which the observed signals are smooth. However, the learned graph is prone to overfitting, as it does not take the unobserved signals into account. To address this issue, we propose a novel graph learning model based on the distributionally robust optimization methodology, which aims to identify a graph that not only provides a smooth representation of but is also robust against uncertainties in the observed signals. On the statistics side, we establish out-of-sample performance guarantees for our proposed model. On the optimization side, we show that under a mild assumption on the graph signal distribution, our proposed model admits a smooth non-convex optimization formulation. We then develop a projected gradient method to tackle this formulation and establish its convergence guarantees. Our formulation provides a new perspective on regularization in the graph learning setting. Moreover, extensive numerical experiments on both synthetic and real-world data show that our model has comparable yet more robust performance across different populations of observed signals than existing non-robust models according to various metrics.