Discrete Functional Geometry of ReLU Networks via ReLU Transition Graphs

2025/09/03 by Sahil Rajesh Dhayalkar, Dhayalkar, Sahil Rajesh
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2509.03056

openalex publication_date 2025/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• The Geometry of ReLU Networks through the ReLU Transition Graph
• A Combinatorial Theory of Dropout: Subnetworks, Graph Geometry, and Generalization
• Gradient Descent on Neural Networks Typically Occurs at the Edge of\n Stability
• Neural Logic Reasoning
• Deep Learning Techniques for Inverse Problems in Imaging
• Distance-Based Regularisation of Deep Networks for Fine-Tuning
• Neural Tangents: Fast and Easy Infinite Neural Networks in Python
• Complexity of Linear Regions in Deep Networks
• Reconciling modern machine learning practice and the bias-variance trade-off
• Interpretable Deep Learning under Fire
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks
• Visualizing the Loss Landscape of Neural Nets
• Bounding and Counting Linear Regions of Deep Neural Networks
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Spectrally-normalized margin bounds for neural networks
• Emergence of Invariance and Disentanglement in Deep Representations
• Interpreting Blackbox Models via Model Extraction
• Information-theoretic analysis of generalization capability of learning algorithms
• Geometric Deep Learning: Going beyond Euclidean data
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Semi-Supervised Classification with Graph Convolutional Networks
• On the Expressive Power of Deep Neural Networks
• Exponential expressivity in deep neural networks through transient chaos
• Benefits of depth in neural networks
• Deep Learning and the Information Bottleneck Principle
• On the Number of Linear Regions of Deep Neural Networks
• Flat Minima

Related

• The Geometry of ReLU Networks through the ReLU Transition Graph
• ReLU Networks as Random Functions: Their Distribution in Probability Space
• Deep ReLU Networks Have Surprisingly Simple Polytopes
• Unwrapping All ReLU Networks
• Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verification