# Robust Graph Learning Under Wasserstein Uncertainty

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 50 references that are in the map.
- First posted on arXiv 10 May 2021.

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

- [Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation](https://mlsanity.com/paper/2010.16061/) (2020)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [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)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [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)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes](https://mlsanity.com/paper/1810.02403/) (2018)
- [Robust Hypothesis Testing Using Wasserstein Uncertainty Sets](https://mlsanity.com/paper/1805.10611/) (2018)
- [Learning Sparse Graphs Under Smoothness Prior](https://mlsanity.com/paper/1609.03448/) (2016)
- [Graph Learning from Filtered Signals: Graph System and Diffusion Kernel Identification](https://mlsanity.com/paper/1803.02553/) (2018)
- [Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator](https://mlsanity.com/paper/1805.07194/) (2018)
- [Distributionally Robust Formulation and Model Selection for the Graphical Lasso](https://mlsanity.com/paper/1905.08975/) (2019)
- [node2coords: Graph Representation Learning with Wasserstein Barycenters](https://mlsanity.com/paper/2007.16056/) (2020)

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

- [Uncertainty-Aware Robust Learning on Noisy Graphs](https://mlsanity.com/paper/2306.08210/) (2023)
- [Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty](https://mlsanity.com/paper/2105.05458/) (2021)
- [Uncertainty Quantification on Graph Learning: A Survey](https://mlsanity.com/paper/2404.14642/) (2024)

## Abstract (arXiv)

Graphs are playing a crucial role in different fields since they are powerful tools to unveil intrinsic relationships among signals. In many scenarios, an accurate graph structure representing signals is not available at all and that motivates people to learn a reliable graph structure directly from observed signals. However, in real life, it is inevitable that there exists uncertainty in the observed signals due to noise measurements or limited observability, which causes a reduction in reliability of the learned graph. To this end, we propose a graph learning framework using Wasserstein distributionally robust optimization (WDRO) which handles uncertainty in data by defining an uncertainty set on distributions of the observed data. Specifically, two models are developed, one of which assumes all distributions in uncertainty set are Gaussian distributions and the other one has no prior distributional assumption. Instead of using interior point method directly, we propose two algorithms to solve the corresponding models and show that our algorithms are more time-saving. In addition, we also reformulate both two models into Semi-Definite Programming (SDP), and illustrate that they are intractable in the scenario of large-scale graph. Experiments on both synthetic and real world data are carried out to validate the proposed framework, which show that our scheme can learn a reliable graph in the context of uncertainty.