Deep neural networks are often perceived as highly complex, non-linear black boxes. However, for architectures that rely on rectified linear units (ReLU) or max-pooling activations, this complexity possesses a highly structured geometric form. A ReLU network does not produce a smoothly curving decision surface; instead, it forms a piecewise linear function.
The input space is partitioned into a collection of convex polyhedral regions, often called activation regions. Within any single region, every neuron's activation state (whether it is active or inactive) is fixed. Consequently, inside that specific region, the entire network behaves exactly like a simple affine transformation ($y = Wx + b$).
This geometric insight is the foundation of exact verification. As Xin Zhang et al. demonstrate in Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections, this piecewise linear nature allows us to mathematically prove that any input within a defined symbolic range will yield a desired outcome. If we can reason about these linear regions systematically, we can transform the intractable problem of verifying a non-linear model into a series of linear optimization tasks.
Encoding Non-Linearities as Mixed-Integer Constraints
To evaluate a network globally across multiple regions, we must mathematically encode the "switching" behavior of the activations. For a ReLU activation $y = \max(0, x)$, the relationship is non-linear. However, we can introduce a binary indicator variable $z \in \{0, 1\}$ to represent the state of the neuron: $z=1$ if the neuron is active ($x \ge 0$), and $z=0$ if it is inactive ($x < 0$).
Using a technique known as the "big-M" formulation, we can express the ReLU behavior using a set of linear inequalities:
$$y \ge x$$ $$y \ge 0$$ $$y \le x + M(1-z)$$ $$y \le Mz$$
where $M$ is a sufficiently large positive constant representing the upper bound of the neuron's input.
By applying this transformation to every non-linear node, the entire neural network can be represented as a Mixed-Integer Linear Program (MILP). As Vincent Tjeng et al. show in Evaluating Robustness of Neural Networks with Mixed Integer Programming, formulating verification as an MILP allows off-the-shelf optimization solvers to perform exact, complete verification. The solver searches for a global optimum within a defined perturbation space, either finding a concrete counterexample or providing a mathematical guarantee that no violation exists. This approach has been successfully applied to verify critical properties like local stability in industrial applications, such as aircraft predictive maintenance explored by Mélanie Ducoffe et al. in Surrogate Neural Networks Local Stability for Aircraft Predictive Maintenance.
The Geometry of Regions and Boundaries
Why does this formulation work so effectively? It reduces continuous verification over an infinite number of points to a discrete search over linear boundaries.
Inside a single activation region, the network is linear. Therefore, the extreme behaviors (such as the maximum or minimum output value) must occur at the boundaries or vertices of that polyhedral region. As Matthew Sotoudeh demonstrates in Provable Repair of Deep Neural Networks, verifying safety properties over an infinite set of inputs within a defined polytope can be reduced to checking a finite number of vertices at the boundaries of these linear regions.
Instead of treating the network as a global optimization problem, some approaches exploit this geometry directly by traversing adjacent polyhedra. For instance, Aymeric Fromherz et al. introduce an algorithm in Fast Geometric Projections for Local Robustness Certification that treats verification as a geometric search. By systematically moving across adjacent polyhedral regions, it calculates the exact minimum distance to a decision boundary without relying on heavy global optimization machinery. When analyzing safety boundaries, Hongchao Zhang et al. show in Exact Verification of ReLU Neural Control Barrier Functions that one can identify every linear segment intersecting a safety boundary and evaluate the safety conditions on those segments individually, even at the non-differentiable "seams" where the regions meet.
Managing Complexity via Relaxations and Decompositions
While exact verification is powerful, searching through every possible combination of binary activation states is computationally expensive. In fact, Marco Sälzer et al. prove in Reachability In Simple Neural Networks that non-deterministically selecting the active linear segment for each node reduces the problem to a standard linear program solvable in polynomial time, but the underlying global problem remains inherently difficult. When extended to finite-precision environments like quantized Graph Neural Networks, the authors show in Verifying Quantized Graph Neural Networks is PSPACE-complete that the complexity can rise to PSPACE-complete.
To scale to larger networks, researchers use linear relaxations. Instead of forcing a neuron to be strictly active ($z=1$) or inactive ($z=0$), we can bound the non-linear activation function within a convex linear envelope (an upper and lower linear bound). This converts the MILP into a standard Linear Program (LP).
As Wang Lin et al. demonstrate in Robustness Verification of Classification Deep Neural Networks via Linear Programming., transforming non-linear activations into linear inclusion relaxations allows standard LP solvers to provide formal guarantees: if the relaxed linear superset is proven robust, the original model is guaranteed to be safe. Similarly, Yi Zeng et al. utilize a two-stage framework in Towards Robustness Certification Against Universal Perturbations, combining linear relaxations to bound non-linearities before passing them to an MILP solver to search for shared dataset-wide perturbations.
Another scaling strategy involves decomposing the problem into discrete logic and continuous optimization. In Efficient Counterexample-Guided Fairness Verification and Repair of Neural Networks Using Satisfiability Modulo Convex Programming, Arya Fayyazi et al. isolate activation regions from numerical bounds by coordinating a SAT solver (for discrete logical constraints) with a convex solver (for continuous optimizations), enabling efficient detection of individual fairness violations.
Broad Applications of Linear Verification
The ability to exactly or relaxedly bound a neural network's output using linear programming has unlocked verification capabilities far beyond simple adversarial robustness:
- Control and Stability: In autonomous systems, controllers must be provably safe. Hongkai Dai et al. demonstrate in Lyapunov-stable neural-network control that encoding piecewise linear networks as MILPs allows formal solvers to verify Lyapunov stability conditions by searching for counterexamples in the state space. To achieve real-time execution, Thomas A. Henzinger et al. show in Formal Verification of Neural Certificates Done Dynamically that the state space can be partitioned into convex regions on-the-fly, allowing safety checks to run as efficient linear inequality evaluations during runtime. Furthermore, Samuel Teuber et al. bridge control theory and linear verification in Provably Safe Neural Network Controllers via Differential Dynamic Logic to handle complex, non-linear safety specifications by analyzing locally affine regions.
- Monotonicity and Recourse: For high-stakes decisions like credit scoring, models must often be provably monotonic. Xingchao Liu et al. show in Certified Monotonic Neural Networks that finding the minimum gradient of a network can be framed as an MILP; if the solver proves the minimum gradient is non-negative, monotonicity is formally certified. Similarly, when providing counterfactual explanations (recourse recommendations), Junqi Jiang et al. use interval abstractions and MILP in Interval Abstractions for Robust Counterfactual Explanations to guarantee that recourse remains valid even if the underlying model undergoes slight retraining.
- Model Repair and Ensembles: When a network violates a property, MILP can be used to systematically find and fix the vulnerability. Feisi Fu et al. develop a framework in REGLO: Provable Neural Network Repair for Global Robustness Properties that uses MILP to explore piecewise linear regions for global property violations and modifies weights via robust convex optimization to eliminate them. Finally, this paradigm extends to ensembles of classifiers; Dennis Gross et al. demonstrate in Robustness Verification for Classifier Ensembles that non-linear ensemble functions can be linearized using big-M constraints to compute the exact maximum expected loss an attacker can inflict.
Key Foundational Work
Evaluating Robustness of Neural Networks with Mixed Integer Programming (2019) — contributed 1 concept elements to this direction.
Output Range Analysis for Deep Feedforward Neural Networks (2018) — contributed 1 concept elements to this direction.
Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections (2018) — contributed 1 concept elements to this direction.