  A neural network consisting of piecewise affine building blocks, such as
fully-connected layers and ReLU activations, is itself a piecewise affine
function supported on a polyhedral complex. This complex has been previously
studied to characterize theoretical properties of neural networks, but, in
practice, extracting it remains a challenge due to its high combinatorial
complexity. A natural idea described in previous works is to subdivide the
regions via intersections with hyperplanes induced by each neuron. However, we
argue that this view leads to computational redundancy. Instead of regions, we
propose to subdivide edges, leading to a novel method for polyhedral complex
extraction. A key to this are sign-vectors, which encode the combinatorial
structure of the complex. Our approach allows to use standard tensor operations
on a GPU, taking seconds for millions of cells on a consumer grade machine.
Motivated by the growing interest in neural shape representation, we use the
speed and differentiability of our method to optimize geometric properties of
the complex. The code is available at
https://github.com/arturs-berzins/relu_edge_subdivision .
