# Robust Graph Neural Networks via Probabilistic Lipschitz Constraints

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 31 references that are in the map.
- First posted on arXiv 14 Dec 2021.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Natural Adversarial Examples](https://mlsanity.com/paper/1907.07174/) (2019)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Training robust neural networks using Lipschitz bounds](https://mlsanity.com/paper/2005.02929/) (2020)
- [Convolutional Neural Network Architectures for Signals Supported on Graphs](https://mlsanity.com/paper/1805.00165/) (2018)
- [Examining COVID-19 Forecasting using Spatio-Temporal Graph Neural Networks](https://mlsanity.com/paper/2007.03113/) (2020)
- [Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks](https://mlsanity.com/paper/1903.10527/) (2019)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Transferring Robustness for Graph Neural Network Against Poisoning Attacks](https://mlsanity.com/paper/1908.07558/) (2019)
- [Gated Graph Recurrent Neural Networks](https://mlsanity.com/paper/2002.01038/) (2020)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Model-Based Robust Deep Learning: Generalizing to Natural, Out-of-Distribution Data](https://mlsanity.com/paper/2005.10247/) (2020)
- [Graph Neural Networks for Decentralized Controllers](https://mlsanity.com/paper/2003.10280/) (2020)
- [Training Stable Graph Neural Networks Through Constrained Learning](https://mlsanity.com/paper/2110.03576/) (2021)
- [Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks](https://mlsanity.com/paper/2006.15005/) (2020)
- [Communication Topology Co-Design in Graph Recurrent Neural Network Based Distributed Control](https://mlsanity.com/paper/2104.13868/) (2021)

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

- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [A Lagrangian Duality Approach to Active Learning](https://mlsanity.com/paper/2202.04108/) (2022)
- [Sparse Covariance Neural Networks](https://mlsanity.com/paper/2410.01669/) (2024)
- [Stability of Graph Convolutional Neural Networks through the lens of small perturbation analysis](https://mlsanity.com/paper/2312.12934/) (2023)
- [Learning Globally Smooth Functions on Manifolds](https://mlsanity.com/paper/2210.00301/) (2022)
- [Learning Stable Graph Neural Networks via Spectral Regularization](https://mlsanity.com/paper/2211.06966/) (2022)
- [On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks](https://mlsanity.com/paper/2312.02372/) (2023)
- [Stability of Flow Models for Graph Signals](https://mlsanity.com/paper/2607.07510/) (2026)
- [On the Convergence and Size Transferability of Continuous-depth Graph Neural Networks](https://mlsanity.com/paper/2510.03923/) (2025)
- [CLARGA: Multimodal Graph Representation Learning over Arbitrary Sets of Modalities](https://mlsanity.com/paper/2512.11901/) (2025)

## Abstract (arXiv)

Graph neural networks (GNNs) have recently been demonstrated to perform well on a variety of network-based tasks such as decentralized control and resource allocation, and provide computationally efficient methods for these tasks which have traditionally been challenging in that regard. However, like many neural-network based systems, GNNs are susceptible to shifts and perturbations on their inputs, which can include both node attributes and graph structure. In order to make them more useful for real-world applications, it is important to ensure their robustness post-deployment. Motivated by controlling the Lipschitz constant of GNN filters with respect to the node attributes, we propose to constrain the frequency response of the GNN's filter banks. We extend this formulation to the dynamic graph setting using a continuous frequency response constraint, and solve a relaxed variant of the problem via the scenario approach. This allows for the use of the same computationally efficient algorithm on sampled constraints, which provides PAC-style guarantees on the stability of the GNN using results in scenario optimization. We also highlight an important connection between this setup and GNN stability to graph perturbations, and provide experimental results which demonstrate the efficacy and broadness of our approach.