Discrete Functional Geometry of ReLU Networks via ReLU Transition Graphs
Not on the map. Why?
Abstract (arXiv)
We extend the ReLU Transition Graph (RTG) framework into a comprehensive graph-theoretic model for understanding deep ReLU networks. In this model, each node represents a linear activation region, and edges connect regions that differ by a single ReLU activation flip, forming a discrete geometric structure over the network's functional behavior. We prove that RTGs at random initialization exhibit strong expansion, binomial degree distributions, and spectral properties that tightly govern generalization. These structural insights enable new bounds on capacity via region entropy and on generalization via spectral gap and edge-wise KL divergence. Empirically, we construct RTGs for small networks, measure their smoothness and connectivity properties, and validate theoretical predictions. Our results show that region entropy saturates under overparameterization, spectral gap correlates with generalization, and KL divergence across adjacent regions reflects functional smoothness. This work provides a unified framework for analyzing ReLU networks through the lens of discrete functional geometry, offering new tools to understand, diagnose, and improve generalization.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 30 of its 41 references that are in the map. First posted on arXiv 3 Sep 2025.
Builds on
30 of 41 references.
References · 30
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
- 2017Visualizing the Loss Landscape of Neural Netscited by 1,126
- 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
- 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 847
- 2015Deep Learning and the Information Bottleneck Principlecited by 793
- 2017Spectrally-normalized margin bounds for neural networkscited by 681
- 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
- 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
- 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 357
- 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
18 more
- 2016On the Expressive Power of Deep Neural Networkscited by 302
- 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
- 2020Deep Learning Techniques for Inverse Problems in Imagingcited by 290
- 2016Exponential expressivity in deep neural networks through transient chaoscited by 260
- 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
- 2016Benefits of depth in neural networkscited by 248
- 2017Emergence of Invariance and Disentanglement in Deep Representationscited by 213
- 2019Complexity of Linear Regions in Deep Networkscited by 166
- 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
- 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
- 2019Neural Tangents: Fast and Easy Infinite Neural Networks in Pythoncited by 149
- 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
- 2018Interpretable Deep Learning under Firecited by 74
- 2020Distance-Based Regularisation of Deep Networks for Fine-Tuningcited by 47
- 2017Interpreting Blackbox Models via Model Extractioncited by 43
- 2020Neural Logic Reasoningcited by 38
- 2025The Geometry of ReLU Networks through the ReLU Transition Graphcited by 4
- 2025A Combinatorial Theory of Dropout: Subnetworks, Graph Geometry, and Generalizationcited by 3
Built on by
Not cited yet.