mlsanityData to 14 Oct 2026

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

arXiv 2111.08922 ↗First posted 17 Nov 2021cs.LG math.OC stat.MLcited by 13

Not on the map. Why?

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.

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

31 of 45 references.

References · 31

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2013Intriguing properties of neural networkscited by 5,155
  3. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,998
  4. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  5. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  6. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  7. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
  8. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  9. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 255
  10. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 242
  11. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  12. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
19 more
  1. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 161
  2. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  3. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  4. 2016Measuring Neural Net Robustness with Constraintscited by 90
  5. 2018Provable Robustness of ReLU networks via Maximization of Linear Regionscited by 51
  6. 2020Certified Monotonic Neural Networkscited by 51
  7. 2020Reachable Polyhedral Marching (RPM): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Componentscited by 36
  8. 2018Exact and Consistent Interpretation for Piecewise Linear Neural Networks: A Closed Form Solutioncited by 32
  9. 2020Unwrapping The Black Box of Deep ReLU Networks: Interpretability, Diagnostics, and Simplificationcited by 32
  10. 2019Enhancing Explainability of Neural Networks through Architecture Constraintscited by 29
  11. 2017Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Studycited by 25
  12. 2017Reachable Set Computation and Safety Verification for Neural Networks with ReLU Activationscited by 22
  13. 2019How to Incorporate Monotonicity in Deep Networks While Preserving Flexibility?cited by 21
  14. 2019Scaling up the randomized gradient-free adversarial attack reveals overestimation of robustness using established attackscited by 11
  15. 2020Reachability Analysis for Feed-Forward Neural Networks using Face Latticescited by 11
  16. 2018A randomized gradient-free attack on ReLU networkscited by 8
  17. 2020Testing Monotonicity of Machine Learning Modelscited by 8
  18. 2019Dissecting Deep Neural Networkscited by 7
  19. 2021Self-interpretable Convolutional Neural Networks for Text Classificationcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 5; 2023: 3; 2024: 3; 2025: 0; 2026: 2.

13 papers.

Sort:

By area:

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2022Interpreting Neural Networks through the Polytope Lenscited by 33
  3. 2024FairProof : Confidential and Certifiable Fairness for Neural Networkscited by 13
  4. 2023ReLU Neural Networks, Polyhedral Decompositions, and Persistent Homologcited by 10
  5. 2022Reachable Polyhedral Marching (RPM): An Exact Analysis Tool for Deep-Learned Control Systemscited by 6
  6. 2026Regime Change Hypothesis: Foundations for Decoupled Dynamics in Neural Network Trainingcited by 3
  7. 2022Dual Graphs of Polyhedral Decompositions for the Detection of Adversarial Attackscited by 2
  8. 2024Defining Neural Network Architecture through Polytope Structures of Datasetcited by 2
  9. 2022Verifying Attention Robustness of Deep Neural Networks against Semantic Perturbationscited by 1
  10. 2023Neural Polytopescited by 1
  11. 2024The Topos of Transformer Networkscited by 1
  12. 2022Support Vectors and Gradient Dynamics of Single-Neuron ReLU Networkscited by 0
1 more
  1. 2026Causal Explanations from the Geometric Properties of ReLU Neural Networkscited by 0