# Learning Stochastic Graph Neural Networks with Constrained Variance

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 65 references that are in the map.
- First posted on arXiv 29 Jan 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks](https://mlsanity.com/paper/1909.01865/) (2019)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks](https://mlsanity.com/paper/1704.06803/) (2017)
- [Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks](https://mlsanity.com/paper/2003.03777/) (2020)
- [Discrete Signal Processing on Graphs: Frequency Analysis](https://mlsanity.com/paper/1307.0468/) (2013)
- [Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks](https://mlsanity.com/paper/1903.10527/) (2019)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [Bandit Samplers for Training Graph Neural Networks](https://mlsanity.com/paper/2006.05806/) (2020)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)
- [On the Stability of Graph Convolutional Neural Networks under Edge Rewiring](https://mlsanity.com/paper/2010.13747/) (2020)
- [Latent Space Model for Road Networks to Predict Time-Varying Traffic](https://mlsanity.com/paper/1602.04301/) (2016)
- [Algebraic Neural Networks: Stability to Deformations](https://mlsanity.com/paper/2009.01433/) (2020)
- [Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping](https://mlsanity.com/paper/2106.02892/) (2021)
- [Stability of Graph Convolutional Neural Networks to Stochastic Perturbations](https://mlsanity.com/paper/2106.10526/) (2021)
- [Wide and Deep Graph Neural Network with Distributed Online Learning](https://mlsanity.com/paper/2107.09203/) (2021)
- [Advances in Distributed Graph Filtering](https://mlsanity.com/paper/1808.03004/) (2018)

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

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Sparse Covariance Neural Networks](https://mlsanity.com/paper/2410.01669/) (2024)
- [Graph Neural Networks over the Air for Decentralized Tasks in Wireless Networks](https://mlsanity.com/paper/2302.08447/) (2023)
- [On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks](https://mlsanity.com/paper/2312.02372/) (2023)
- [GKNet: Graph Kalman Filtering and Model Inference via Model-based Deep Learning](https://mlsanity.com/paper/2506.22004/) (2025)

## Abstract (arXiv)

Stochastic graph neural networks (SGNNs) are information processing architectures that learn representations from data over random graphs. SGNNs are trained with respect to the expected performance, which comes with no guarantee about deviations of particular output realizations around the optimal expectation. To overcome this issue, we propose a variance-constrained optimization problem for SGNNs, balancing the expected performance and the stochastic deviation. An alternating primal-dual learning procedure is undertaken that solves the problem by updating the SGNN parameters with gradient descent and the dual variable with gradient ascent. To characterize the explicit effect of the variance-constrained learning, we conduct a theoretical analysis on the variance of the SGNN output and identify a trade-off between the stochastic robustness and the discrimination power. We further analyze the duality gap of the variance-constrained optimization problem and the converging behavior of the primal-dual learning procedure. The former indicates the optimality loss induced by the dual transformation and the latter characterizes the limiting error of the iterative algorithm, both of which guarantee the performance of the variance-constrained learning. Through numerical simulations, we corroborate our theoretical findings and observe a strong expected performance with a controllable standard deviation.