The reviewed record of science sign in
Pith

arxiv: 2207.07696 · v1 · pith:DXVVL4ES · submitted 2022-07-15 · cs.LG · cs.CG· math.AT

Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks

Marissa Masden This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:DXVVL4ESrecord.jsonopen to challenge →

classification cs.LG cs.CGmath.AT
keywords complexstructurecanonicaldimensionsnetworkspolyhedralacrossalgorithm
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Complete Symmetry Classification of Shallow ReLU Networks

    cs.LG 2026-04 unverdicted novelty 8.0

    A complete classification of symmetries in shallow ReLU networks is achieved by using the non-differentiability of ReLU.

  2. Functional Similarity Metric for Neural Networks: Overcoming Parametric Ambiguity via Activation Region Analysis

    cs.LG 2026-04 unverdicted novelty 6.0

    A functional similarity metric for ReLU networks uses normalized activation region signatures and MinHash to overcome parametric symmetries like neuron permutation and scaling.