Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks
This work provides a foundational tool for understanding the geometry of ReLU networks, which is incremental for researchers in neural network theory and interpretability.
The authors tackled the problem of algorithmically determining the full combinatorial structure of linear regions in ReLU neural networks, resulting in a numerically stable, polynomial-time algorithm that accurately computes regions and facets across all dimensions, enabling analysis of decision boundary topology.
We algorithmically determine the regions and facets of all dimensions of the canonical polyhedral complex, the universal object into which a ReLU network decomposes its input space. We show that the locations of the vertices of the canonical polyhedral complex along with their signs with respect to layer maps determine the full facet structure across all dimensions. We present an algorithm which calculates this full combinatorial structure, making use of our theorems that the dual complex to the canonical polyhedral complex is cubical and it possesses a multiplication compatible with its facet structure. The resulting algorithm is numerically stable, polynomial time in the number of intermediate neurons, and obtains accurate information across all dimensions. This permits us to obtain, for example, the true topology of the decision boundaries of networks with low-dimensional inputs. We run empirics on such networks at initialization, finding that width alone does not increase observed topology, but width in the presence of depth does. Source code for our algorithms is accessible online at https://github.com/mmasden/canonicalpoly.