Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision
This work addresses a computational bottleneck for researchers and practitioners in neural network analysis and neural shape representation, offering a faster and differentiable extraction method, though it is incremental as it builds on prior ideas of subdivision.
The paper tackles the challenge of extracting polyhedral complexes from ReLU neural networks, which is computationally intensive due to high combinatorial complexity, and proposes a novel edge subdivision method that reduces redundancy and enables efficient GPU-based extraction in seconds for millions of cells.
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 .