The Geometry of ReLU Networks through the ReLU Transition Graph
Sahil Rajesh Dhayalkar · 2025
Read The Geometry of ReLU Networks through the ReLU Transition Graph by Sahil Rajesh Dhayalkar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11692.txt.
Introduction
Sahil Rajesh Dhayalkar presents a 2025 theory of ReLU networks read as a map of their flat zones. A ReLU net cuts its input space into zones where it acts as one flat rule. The author links zones that differ by one neuron's flip into a graph, the ReLU Transition Graph. On that graph he proves tight bounds on size and span, plus a proof that the graph stays in one piece.
Zone counts and link traits become gauges for what the net can express and how well it generalizes. Entropy and mean link counts tie to test error in the results. Controlled runs across depths and widths back each claim. The graph view opens fresh routes to shrink and tame networks by shape, not just by training.
Catalog record
| CREATOR | Sahil Rajesh Dhayalkar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11692
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Geometry of ReLU Networks through the ReLU Transition Graph Sahil Rajesh Dhayalkar Abstract We develop a novel theoretical framework for analyzing ReLU neural networks through the lens of a combinatorial object we term the ReLU Transition Graph (RTG). In this graph, each node corresponds to a linear region induced by the network’s activation patterns, and edges connect regions that differ by a single neuron flip. Building on this structure, we derive a suite of new theoretical results connecting RTG geometry to expressivity, generalization, and robustness. Our contributions include tight combinatorial bounds on RTG size and diameter, a proof of RTG connectivity, and graph-theoretic interpretations of VC-dimension. We also relate entropy and average degree of the RTG to generalization error. Each theoretical result is rigorously validated via carefully controlled experiments across varied network depths, widths, and data regimes. This work provides the first unified treatment of ReLU network structure via graph theory and opens new avenues for compression, regularization, and complexity control rooted in RTG analysis. 1 Introduction ReLU neural networks glorot2011deep are known to induce highly structured piecewise-linear decision boundaries in input space. These networks partition their domain into polyhedral regions, each governed by a fixed pattern of neuron activations hanin2019complexity ; nair2010rectified . This geometric behavior is central to the expressivity, generalization, and compressibility of deep networks telgarsky2016benefits . Understanding this geometry is essential for uncovering how deep networks generalize beyond training data, resist adversarial perturbations, and remain functionally stable under compression. Yet despite extensive work on quantifying the number of such linear regions montufar2014number ; serra2018bounding ; hanin2019complexity , much less is known about the global structure connecting these regions—how they transition, cluster, and contribute to the network’s functional topology novak2018sensitivity . In this paper, we propose a new combinatorial object, the ReLU Transition Graph (RTG), to study the geometric structure of ReLU networks. The RTG is an undirected graph where each node corresponds to a distinct activation pattern (i.e., a linear region), and edges represent minimal transitions via a single ReLU flip. This framework allows us to move beyond counting regions and begin analyzing their connectivity, sparsity, and graph-theoretic properties. Our contributions are threefold. First, we provide formal definitions and constructions for the RTG and show how it can be efficiently constructed from ReLU activation patterns. Second, we derive a suite of novel theoretical results about RTG size, connectivity, diameter, entropy, and sparsity. For example, we prove that the RTG is always connected (Theorem 2 ), and that its structure tightly bounds the VC-dimension of the network (Theorem 3 ). We also show that RTGs are inherently sparse and can be pruned with minimal error, enabling provable compression (Theorem 4 ). These results provide new insights into why overparameterized networks generalize well despite their apparent capacity neyshabur2015norm ; bartlett1998sample . Third, we validate each theoretical result through a unified empirical framework. Using fully connected ReLU MLPs with varying depths and widths, we construct RTGs from synthetic 2D data and compute a variety of graph metrics. Our experiments confirm the predicted scaling laws, verify edge conditions, and quantify the impact of pruning on function fidelity. Our RTG framework synthesizes ideas from neural expressivity hanin2019complexity ; raghu2017expressive , topology guss2018characterizing , and compression frankle2018lottery , providing a unifying structure to understand ReLU networks as dynamic, graph-based systems. This perspective opens new directions for structural regularization, sparse initialization, and graph-based network analysis. The paper uses a structure with theorems, lemmas, and corollaries, similar to prior work zhang2015learninghalfspacesneuralnetworks ; hanin2018approximatingcontinuousfunctionsrelu ; neyshabur2015searchrealinductivebias ; dhayalkar2025combinatorialtheorydropoutsubnetworks ; dhayalkar2025neuralnetworksuniversalfinitestate . 2 Related Work Our work builds on and extends several lines of research that examine the expressivity, geometry, and generalization properties of ReLU neural networks. Below we review key contributions in region counting, combinatorial capacity, graph-based analysis, and network sparsification, and contrast them with our ReLU Transition Graph (RTG) framework. Expressivity via Region Counting: The number of linear regions in ReLU networks has long been a proxy for expressivity. Montúfar et al. montufar2014number provided the first polynomial bound on the number of linear regions induced by fully connected networks in terms of depth and width. Serra et al. serra2018bounding later improved these bounds using mixed-integer linear programming. Hanin and Rolnick hanin2019complexity showed that most regions are degenerate and do not contribute meaningfully to the function’s complexity. We complement this line of work by defining a graph over these regions—the RTG—and analyzing its global properties (e.g., diameter, sparsity) rather than just its size. Connectivity and Topology of ReLU Regions: Arora et al. arora2018understanding and Raghu et al. raghu2017expressive studied the role of depth in shaping the topology of linear regions. Our work formalizes these ideas through the RTG, proving that the graph is connected under mild assumptions and transitions between regions are governed by single-neuron flips. This structural lens enables new insights into traversability and robustness. Generalization and VC-Dimension: Classical bounds on VC-dimension bartlett1998sample ; neyshabur2015norm relate capacity to weight norms and architectural size. Our Theorem 3 introduces a graph-theoretic upper bound on VC-dimension in terms of RTG diameter, yielding a novel geometric-combinatorial interpretation. Unlike norm-based measures, this bound emerges from the topological layout of activation patterns. Graph-Theoretic Perspectives on Neural Networks: Recent work has applied graph-theoretic tools to neural network analysis. Poole et al. poole2016exponential examined signal propagation as a dynamical system, and Guss and Salakhutdinov guss2018characterizing analyzed region adjacency using simplicial complexes. Our RTG approach differs in its explicit encoding of region-to-region transitions via Hamming-1 activation flips, forming a sparse graph suitable for structural analysis. Sparsity, Pruning, and Functional Compression: The idea that networks can be pruned without sacrificing accuracy has received widespread attention, notably through the Lottery Ticket Hypothesis frankle2018lottery . Our Theorem 4 provides theoretical grounding for this idea by showing that low-degree nodes in the RTG can be removed with bounded functional error. This links topological sparsity to compressibility, offering a formal basis for pruning strategies based on activation structure. Spectral and Entropy-Based Measures: Entropy and spectral gap have emerged as indicators of network complexity and generalization serra2018bounding ; neyshabur2015norm . We formalize these intuitions by proving that RTG entropy grows with average degree (Lemma 2 ) and that sparsity is sufficient for functional approximation. Unlike prior work, we compute them directly from the activation-induced graph. Overall, the RTG framework provides a unified combinatorial geometry for understanding ReLU networks, integrating expressivity, generalization, and robustness into a single structural object. To our knowledge, this is the first work to do so. 3 Preliminaries and Definitions We consider fully-connected feedforward neural networks with ReLU activations. Let f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k} be a function computed by such a network of depth L and width n per layer, defined by a composition of affine transformations and ReLU nonlinearities. Our focus is on the induced piecewise-linear structure of f and its representation as a graph over the input space. 3.1 Definition 1: Activation Pattern Given an input x\in\mathbb{R}^{d} , the activation pattern a(x) is a binary vector in \{0,1\}^{m} representing the on/off status of each ReLU neuron in the network, where m is the total number of ReLU units across all layers. Each component a_{i}(x)=\mathbf{1}[z_{i}(x)>0] indicates whether the pre-activation z_{i}(x) of neuron i is positive. This binary pattern uniquely encodes the local linear behavior of the network