# Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verification

arXiv: https://arxiv.org/abs/2111.08922 · HTML: https://mlsanity.com/paper/2111.08922/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 45 references that are in the map.
- First posted on arXiv 17 Nov 2021.

## Builds on (most cited first, 30 of 31)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)
- [Certified Monotonic Neural Networks](https://mlsanity.com/paper/2011.10219/) (2020)
- [Reachable Polyhedral Marching (RPM): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Components](https://mlsanity.com/paper/2011.11609/) (2020)
- [Exact and Consistent Interpretation for Piecewise Linear Neural Networks: A Closed Form Solution](https://mlsanity.com/paper/1802.06259/) (2018)
- [Unwrapping The Black Box of Deep ReLU Networks: Interpretability, Diagnostics, and Simplification](https://mlsanity.com/paper/2011.04041/) (2020)
- [Enhancing Explainability of Neural Networks through Architecture Constraints](https://mlsanity.com/paper/1901.03838/) (2019)
- [Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study](https://mlsanity.com/paper/1712.06174/) (2017)
- [Reachable Set Computation and Safety Verification for Neural Networks with ReLU Activations](https://mlsanity.com/paper/1712.08163/) (2017)
- [How to Incorporate Monotonicity in Deep Networks While Preserving Flexibility?](https://mlsanity.com/paper/1909.10662/) (2019)
- [Scaling up the randomized gradient-free adversarial attack reveals overestimation of robustness using established attacks](https://mlsanity.com/paper/1903.11359/) (2019)
- [Reachability Analysis for Feed-Forward Neural Networks using Face Lattices](https://mlsanity.com/paper/2003.01226/) (2020)
- [A randomized gradient-free attack on ReLU networks](https://mlsanity.com/paper/1811.11493/) (2018)
- [Testing Monotonicity of Machine Learning Models](https://mlsanity.com/paper/2002.12278/) (2020)
- [Dissecting Deep Neural Networks](https://mlsanity.com/paper/1910.03879/) (2019)

## Built on by (most cited first, 13 of 13)

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Interpreting Neural Networks through the Polytope Lens](https://mlsanity.com/paper/2211.12312/) (2022)
- [FairProof : Confidential and Certifiable Fairness for Neural Networks](https://mlsanity.com/paper/2402.12572/) (2024)
- [ReLU Neural Networks, Polyhedral Decompositions, and Persistent Homolog](https://mlsanity.com/paper/2306.17418/) (2023)
- [Reachable Polyhedral Marching (RPM): An Exact Analysis Tool for Deep-Learned Control Systems](https://mlsanity.com/paper/2210.08339/) (2022)
- [Regime Change Hypothesis: Foundations for Decoupled Dynamics in Neural Network Training](https://mlsanity.com/paper/2602.08333/) (2026)
- [Dual Graphs of Polyhedral Decompositions for the Detection of Adversarial Attacks](https://mlsanity.com/paper/2211.13305/) (2022)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [Verifying Attention Robustness of Deep Neural Networks against Semantic Perturbations](https://mlsanity.com/paper/2207.05902/) (2022)
- [Neural Polytopes](https://mlsanity.com/paper/2307.00721/) (2023)
- [The Topos of Transformer Networks](https://mlsanity.com/paper/2403.18415/) (2024)
- [Support Vectors and Gradient Dynamics of Single-Neuron ReLU Networks](https://mlsanity.com/paper/2202.05510/) (2022)
- [Causal Explanations from the Geometric Properties of ReLU Neural Networks](https://mlsanity.com/paper/2605.10396/) (2026)

## Abstract (arXiv)

Although neural networks (NNs) with ReLU activation functions have found success in a wide range of applications, their adoption in risk-sensitive settings has been limited by the concerns on robustness and interpretability. Previous works to examine robustness and to improve interpretability partially exploited the piecewise linear function form of ReLU NNs. In this paper, we explore the unique topological structure that ReLU NNs create in the input space, identifying the adjacency among the partitioned local polytopes and developing a traversing algorithm based on this adjacency. Our polytope traversing algorithm can be adapted to verify a wide range of network properties related to robustness and interpretability, providing an unified approach to examine the network behavior. As the traversing algorithm explicitly visits all local polytopes, it returns a clear and full picture of the network behavior within the traversed region. The time and space complexity of the traversing algorithm is determined by the number of a ReLU NN's partitioning hyperplanes passing through the traversing region.