The paper claims ReLU Transition Graphs of ReLU networks are expanders whose spectral gap, region entropy, and edge KL divergence bound generalization and capacity; the proofs are sketches, and the empirical checks are weak.
The Geometry of ReLU Networks through the ReLU Transition Graph
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
citation-role summary
background 1
citation-polarity summary
fields
cs.LG 1years
2025 1verdicts
REJECT 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
Discrete Functional Geometry of ReLU Networks via ReLU Transition Graphs
The paper claims ReLU Transition Graphs of ReLU networks are expanders whose spectral gap, region entropy, and edge KL divergence bound generalization and capacity; the proofs are sketches, and the empirical checks are weak.