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

Shaojie Xu, Joel Vaughan, Jie Chen, Aijun Zhang, Agus Sudjianto

Abstract

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.

Introduction

ReLU neural networks are fundamentally piecewise linear functions. They partition the input space into a complex arrangement of convex polytopes. Inside each of these polytopes, the network behaves as a simple linear model. While this structure offers a path toward interpretability, the sheer number of polytopes—which can grow exponentially with network depth—makes exhaustive exploration difficult. Previous verification methods often relied on top-down search or incomplete sampling. This work proposes a "bottom-up" approach to systematically traverse these regions by treating the input space as a collection of adjacent geometric cells.

Figure 1: Visualization of how a ReLU network partitions the input space into a 'jigsaw puzzle' of local linear polytopes.

Methodology: BFS-Based Polytope Traversal

The core of the proposed method is a Breadth-First Search (BFS) algorithm that treats polytopes as nodes in a graph. The researchers identified that moving between adjacent linear regions is mathematically equivalent to flipping a single bit in the network's activation code. Two polytopes are considered "one-adjacent" if they share a boundary and their activation codes differ by exactly one neuron's state (flipping from "on" to "off").

Figure 2: Adjacency identification in ReLU networks. Moving between adjacent polytopes corresponds to flipping bits in the activation code, enabling a graph-based search.

By identifying these boundaries using Linear Programming (LP), the algorithm can "walk" from one polytope to its neighbors. To maintain efficiency, the authors introduce a hyperplane pre-screening step. This step identifies which partitioning hyperplanes actually intersect the specific region of interest, allowing the algorithm to ignore thousands of irrelevant hyperplanes and focus on the local neighborhood.

Verification Applications and Results

The traversing algorithm provides a unified framework for several critical verification tasks across various datasets, including MNIST and the ACAS Xu collision avoidance benchmarks:

  • Adversarial Robustness: By inspecting every linear region within a defined noise budget, the algorithm can find the exact point where a network's classification flips. This provides a guaranteed safety margin and identifies adversarial samples that are nearly imperceptible to humans.
  • Formal Verification: The method was tested on the ACAS Xu benchmark, successfully verifying safety properties across all 45 networks. Unlike methods that provide a simple pass/fail, this algorithm identifies the specific polytopes where violations occur, aiding in model debugging.
  • Monotonicity Verification: For applications requiring logical consistency (e.g., ensuring that increasing a credit score never decreases loan approval probability), the algorithm verifies that the weights of the linear models in all traversed polytopes maintain the required sign.

Conclusion

This polytope traversing approach offers a mathematically rigorous way to "open the black box" of ReLU networks. By providing a theoretical guarantee that every linear region within a bounded area has been inspected, it offers a level of thoroughness that randomized sampling cannot match. While scalability remains a challenge for extremely high-dimensional models, the ability to provide a complete picture of local network behavior is a significant step forward for safety-critical AI applications.

Summary updated

Abstract

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.
BibTeX
@misc{xu2021traversing,
  author = {Shaojie Xu and Joel Vaughan and Jie Chen and Aijun Zhang and Agus Sudjianto},
  title = {{Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verification}},
  year = {2021},
  eprint = {2111.08922},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.08922},
}
Figure