mlsanityData to 14 Oct 2026

Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks

arXiv 2206.00228 ↗First posted 1 Jun 2022cs.LG cs.AI stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

The research for characterizing GNN expressiveness attracts much attention as graph neural networks achieve a champion in the last five years. The number of linear regions has been considered a good measure for the expressivity of neural networks with piecewise linear activation. In this paper, we present some estimates for the number of linear regions of the classic graph convolutional networks (GCNs) with one layer and multiple-layer scenarios. In particular, we obtain an optimal upper bound for the maximum number of linear regions for one-layer GCNs, and the upper and lower bounds for multi-layer GCNs. The simulated estimate shows that the true maximum number of linear regions is possibly closer to our estimated lower bound. These results imply that the number of linear regions of multi-layer GCNs is exponentially greater than one-layer GCNs per parameter in general. This suggests that deeper GCNs have more expressivity than shallow GCNs.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 36 of its 60 references that are in the map. First posted on arXiv 1 Jun 2022.

Builds on

36 of 60 references.

References · 36

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,139
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  8. 2016Error bounds for approximations with deep ReLU networkscited by 574
  9. 2019Provably Powerful Graph Networkscited by 389
  10. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  11. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
  12. 2016On the Expressive Power of Deep Neural Networkscited by 306
24 more
  1. 2020Can Graph Neural Networks Count Substructures?cited by 236
  2. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  3. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  4. 2013Maxout Networkscited by 187
  5. 2021Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspectivecited by 169
  6. 2019Complexity of Linear Regions in Deep Networkscited by 167
  7. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  8. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 161
  9. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 122
  10. 2017Fisher-Rao Metric, Geometry, and Complexity of Neural Networkscited by 100
  11. 2018Tropical Geometry of Deep Neural Networkscited by 95
  12. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  13. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  14. 2015Representation Benefits of Deep Feedforward Networkscited by 86
  15. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
  16. 2019The Geometry of Deep Networks: Power Diagram Subdivisioncited by 53
  17. 2020On the Number of Linear Regions of Convolutional Neural Networkscited by 49
  18. 2018On Characterizing the Capacity of Neural Networks using Algebraic Topologycited by 38
  19. 2021Deep ReLU Networks Preserve Expected Lengthcited by 17
  20. 2018A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networkscited by 15
  21. 2021On the Expected Complexity of Maxout Networkscited by 15
  22. 2021Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networkscited by 7
  23. 2019A Sober Look at Neural Network Initializationscited by 4
  24. 2019Trajectory growth lower bounds for random sparse deep ReLU networkscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 0; 2025: 1; 2026: 5.

9 papers.

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2023The Evolution of the Interplay Between Input Distributions and Linear Regions in Networkscited by 3
  3. 2023Revisiting Generalized p-Laplacian Regularized Framelet GCNs: Convergence, Energy Dynamic and Training with Non-Linear Diffusioncited by 1
  4. 2026Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networkscited by 1
  5. 2026AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networkscited by 1
  6. 2026Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networkscited by 1
  7. 2025The Space Between: On Folding, Symmetries and Samplingcited by 0
  8. 2026Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexitycited by 0
  9. 2026Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulascited by 0