# Learning Latent Graph Structures and their Uncertainty

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 68 references that are in the map.
- First posted on arXiv 30 May 2024.

## Builds on (most cited first, 30 of 34)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Demystifying MMD GANs](https://mlsanity.com/paper/1801.01401/) (2018)
- [When Does Label Smoothing Help?](https://mlsanity.com/paper/1906.02629/) (2019)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [Accurate Uncertainties for Deep Learning Using Calibrated Regression](https://mlsanity.com/paper/1807.00263/) (2018)
- [Calibrating Deep Neural Networks using Focal Loss](https://mlsanity.com/paper/2002.09437/) (2020)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Discrete Graph Structure Learning for Forecasting Multiple Time Series](https://mlsanity.com/paper/2101.06861/) (2021)
- [Bayesian Structure Learning with Generative Flow Networks](https://mlsanity.com/paper/2202.13903/) (2022)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Learning in Implicit Generative Models](https://mlsanity.com/paper/1610.03483/) (2016)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [Bayesian graph convolutional neural networks for semi-supervised classification](https://mlsanity.com/paper/1811.11103/) (2018)
- [Differentiable Graph Module (DGM) for Graph Convolutional Networks](https://mlsanity.com/paper/2002.04999/) (2020)
- [Spherical Latent Spaces for Stable Variational Autoencoders](https://mlsanity.com/paper/1808.10805/) (2018)
- [Graph-Revised Convolutional Network](https://mlsanity.com/paper/1911.07123/) (2019)
- [Dirichlet Variational Autoencoder](https://mlsanity.com/paper/1901.02739/) (2019)
- [Variational Autoencoder with Learned Latent Structure](https://mlsanity.com/paper/2006.10597/) (2020)
- [Learning to Learn Graph Topologies](https://mlsanity.com/paper/2110.09807/) (2021)
- [GLSR-VAE: Geodesic Latent Space Regularization for Variational AutoEncoder Architectures](https://mlsanity.com/paper/1707.04588/) (2017)
- [Sparse Graph Learning from Spatiotemporal Time Series](https://mlsanity.com/paper/2205.13492/) (2022)

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

- [Relational Conformal Prediction for Correlated Time Series](https://mlsanity.com/paper/2502.09443/) (2025)
- [Beyond Softmax: A Natural Parameterization for Categorical Random Variables](https://mlsanity.com/paper/2509.24728/) (2025)
- [Bilevel Graph Structure Learning, Revisited: Inner-Channel Origins of the Reported Gain](https://mlsanity.com/paper/2605.07577/) (2026)
- [Calibrating Generative Models to Feature Distributions with MMD Finetuning](https://mlsanity.com/paper/2606.19496/) (2026)

## Abstract (arXiv)

Graph neural networks use relational information as an inductive bias to enhance prediction performance. Not rarely, task-relevant relations are unknown and graph structure learning approaches have been proposed to learn them from data. Given their latent nature, no graph observations are available to provide a direct training signal to the learnable relations. Therefore, graph topologies are typically learned on the prediction task alongside the other graph neural network parameters. In this paper, we demonstrate that minimizing point-prediction losses does not guarantee proper learning of the latent relational information and its associated uncertainty. Conversely, we prove that suitable loss functions on the stochastic model outputs simultaneously grant solving two tasks: (i) learning the unknown distribution of the latent graph and (ii) achieving optimal predictions of the target variable. Finally, we propose a sampling-based method that solves this joint learning task. Empirical results validate our theoretical claims and demonstrate the effectiveness of the proposed approach.