Characterizing the Discrete Geometry of ReLU Networks

INTRODUCTION It is well established that ReLU networks defne continuous piecewise-linear functions, and that their linear regions are polyhedra in the input space. These regions form a complex that fully partitions the input space. The way these regions ft together is fundamental to the behavior of the network, as nonlinearities occur only at the boundaries where these regions connect. However, relatively little is known about the geometry of these complexes beyond bounds on the total number of regions, and calculating the complex exactly is intractable for most networks. In this work, we prove new theoretical results about these complexes that hold for all fully-connected ReLU networks, specifcally about their connectivity graphs in which nodes correspond to regions and edges exist between each pair of regions connected by a face. We fnd that the average degree of this graph is upper bounded by twice the input dimension regardless of the width and depth of the network, and that the diameter of this graph has an upper bound that does not depend on input dimension, despite the number of regions increasing exponentially with input dimension. We corroborate our fndings through experiments with networks trained on both synthetic and real-world data, which provide additional insight into the geometry of ReLU networks. Code to reproduce our results can be found at https://github.com/bl-ake/ICLR-2026 . * Empirical Observations Experimental results with networks of different sizes trained on synthetic data and three benchmark datasets show that: 1. The average degree of the connectivity graph quickly approaches the upper bound as the size of the network increases. 2. The number of neighbors for every polyhedral region follows a unimodal distribution that skews right and peaks just below 2d. 3. Regions that contain data points tend to be more connected on average compared to those that do not.