mlsanityData to 7 Oct 2026

On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks

arXiv 2312.02372 ↗First posted 4 Dec 2023eess.SP cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

Analyzing the stability of graph neural networks (GNNs) under topological perturbations is key to understanding their transferability and the role of each architecture component. However, stability has been investigated only for particular architectures, questioning whether it holds for a broader spectrum of GNNs or only for a few instances. To answer this question, we study the stability of EdgeNet: a general GNN framework that unifies more than twenty solutions including the convolutional and attention-based classes, as well as graph isomorphism networks and hybrid architectures. We prove that all GNNs within the EdgeNet framework are stable to topological perturbations. By studying the effect of different EdgeNet categories on the stability, we show that GNNs with fewer degrees of freedom in their parameter space, linked to a lower representational capacity, are more stable. The key factor yielding this trade-off is the eigenvector misalignment between the EdgeNet parameter matrices and the graph shift operator. For example, graph convolutional neural networks that assign a single scalar per signal shift (hence, with a perfect alignment) are more stable than the more involved node or edge-varying counterparts. Extensive numerical results corroborate our theoretical findings and highlight the role of different architecture components in the trade-off.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 48 of its 60 references that are in the map. First posted on arXiv 4 Dec 2023.

Builds on

48 of 60 references.

References · 48

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  7. 2019Graph Neural Networks for Social Recommendationcited by 711
  8. 2017Graph Signal Processing: Overview, Challenges and Applicationscited by 409
  9. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  10. 2018Session-based Recommendation with Graph Neural Networkscited by 312
  11. 2018Adversarial Attack on Graph Structured Datacited by 300
  12. 2015Deep Convolutional Networks on Graph-Structured Datacited by 246
36 more
  1. 2019Stability Properties of Graph Neural Networkscited by 125
  2. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 94
  3. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  4. 2019Graph Neural Networks for Decentralized Multi-Robot Path Planningcited by 84
  5. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  6. 2019Learning Decentralized Controllers for Robot Swarms with Graph Neural Networkscited by 62
  7. 2019Certifiable Robustness to Graph Perturbationscited by 62
  8. 2020Unfolding WMMSE using Graph Neural Networks for Efficient Power Allocationcited by 61
  9. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  10. 2022Graph Filters for Signal Processing and Machine Learning on Graphscited by 53
  11. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  12. 2018Graph Convolutional Neural Networks via Scatteringcited by 46
  13. 2018Diffusion Scattering Transforms on Graphscited by 43
  14. 2020EdgeNets:Edge Varying Graph Neural Networkscited by 36
  15. 2020The Emergence of Adversarial Communication in Multi-Agent Reinforcement Learningcited by 28
  16. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
  17. 2020On the Stability of Graph Convolutional Neural Networks under Edge Rewiringcited by 25
  18. 2021Training Robust Graph Neural Networks with Topology Adaptive Edge Droppingcited by 20
  19. 2021Stability of Graph Convolutional Neural Networks to Stochastic Perturbationscited by 18
  20. 2013Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency Framescited by 15
  21. 2020Graph and graphon neural network stabilitycited by 15
  22. 2021Wide and Deep Graph Neural Network with Distributed Online Learningcited by 14
  23. 2018Advances in Distributed Graph Filteringcited by 13
  24. 2021Training Stable Graph Neural Networks Through Constrained Learningcited by 12
  25. 2019Stability of Graph Neural Networks to Relative Perturbationscited by 11
  26. 2020Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networkscited by 11
  27. 2014Authorship Attribution through Function Word Adjacency Networkscited by 10
  28. 2021Robust Graph Neural Networks via Probabilistic Lipschitz Constraintscited by 10
  29. 2022Graph-Time Convolutional Neural Networks: Architecture and Theoretical Analysiscited by 10
  30. 2023Online Control Barrier Functions for Decentralized Multi-Agent Navigationcited by 10
  31. 2021Node-Variant Graph Filters in Graph Neural Networkscited by 7
  32. 2022Decentralized Channel Management in WLANs with Graph Neural Networkscited by 7
  33. 2022Environment Optimization for Multi-Agent Navigationcited by 6
  34. 2023Constrained Environment Optimization for Prioritized Multi-Agent Navigationcited by 6
  35. 2022Learning Stochastic Graph Neural Networks with Constrained Variancecited by 5
  36. 2022Learning Stable Graph Neural Networks via Spectral Regularizationcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024Fair CoVariance Neural Networkscited by 6
  2. 2024Sparse Covariance Neural Networkscited by 6