Tight Neural Network Verification via Semidefinite Relaxations and Linear Reformulations

Jianglin Lan, Yang Zheng, Alessio Lomuscio

Deep neural networks are notoriously fragile; small, imperceptible perturbations to an input—known as adversarial attacks—can cause them to make confident, incorrect predictions. To deploy these networks in safety-critical domains like aviation or autonomous driving, we require formal verification: a mathematical guarantee that for a given input, no small change can flip the output label.

Verification methods generally fall into two categories. Complete methods provide exact answers but are NP-hard and fail to scale. Incomplete methods use convex relaxations to approximate network behavior; while faster, they are often too imprecise (loose), failing to prove robustness even when a network is actually safe. This paper introduces RLT-SDP, a method that significantly tightens this "relaxation gap" by combining Semidefinite Programming (SDP) with the Reformulation-Linearisation Technique (RLT).

Methods: The RLT-SDP Framework

The proposed Layer RLT-SDP builds on two mathematical pillars. First, Semidefinite Programming (SDP) handles quadratic constraints, making it a natural fit for modeling the ReLU function ($y = \max(0, x)$). Second, the Reformulation-Linearisation Technique (RLT) generates new, valid linear constraints (cuts) by multiplying existing linear constraints together.

Figure 2: Visualization of how different RLT constraints (red) tighten the feasible region of the base Layer SDP relaxation (blue).

These RLT cuts capture complex inter-layer and intra-layer dependencies between neurons that standard methods ignore. To maintain computational tractability, the authors utilize a layerwise formulation and an iterative algorithm that prioritizes cuts based on the magnitude of the network's weights.

Key Insights: The Power of Selective Cuts

A critical finding of this research is that capturing hidden dependencies does not require adding every possible RLT cut. The authors demonstrate that adding just a fraction of the most influential cuts provides the bulk of the tightening improvement. This creates a "sweet spot" between precision and speed.

Figure 4: Comparison of feasible regions when adding small, large, or all RLT cuts, illustrating that a subset of cuts can achieve near-optimal tightness.

By using RLT, the method effectively "shrinks" the space of possible adversarial errors. The authors mathematically prove that their RLT-SDP relaxation is strictly tighter than previous state-of-the-art SDP and Linear Programming (LP) relaxations.

Experimental Results

The method was evaluated on randomly generated ReLU networks and standard MNIST benchmarks. The results show a dramatic jump in certified robustness—the percentage of images for which the method can prove no adversarial attack exists. For a specific MNIST network with 10,000 nodes, previous methods certified 0% of cases, while RLT-SDP certified 82%. RLT-SDP consistently outperformed other high-performance tools like $\beta$-CROWN, PRIMA, and DeepPoly across various benchmarks.

Limitations and Future Work

While more efficient than previous "Global SDP" approaches, RLT-SDP remains more computationally intensive than simple LP methods. It is best suited for scenarios where high precision is paramount. Future work involves integrating these RLT cuts into faster dual-optimization frameworks to combine the tightness of SDP with the speed of bound propagation, potentially scaling these guarantees to even larger models.

Summary updated

Abstract

We present a novel semidefinite programming (SDP) relaxation that enables tight and efficient verification of neural networks. The tightness is achieved by combining SDP relaxations with valid linear cuts, constructed by using the reformulation-linearisation technique (RLT). The computational efficiency results from a layerwise SDP formulation and an iterative algorithm for incrementally adding RLT-generated linear cuts to the verification formulation. The layer RLT-SDP relaxation here presented is shown to produce the tightest SDP relaxation for ReLU neural networks available in the literature. We report experimental results based on MNIST neural networks showing that the method outperforms the state-of-the-art methods while maintaining acceptable computational overheads. For networks of approximately 10k nodes (1k, respectively), the proposed method achieved an improvement in the ratio of certified robustness cases from 0% to 82% (from 35% to 70%, respectively).
BibTeX
@inproceedings{lan2022tight,
  author = {Jianglin Lan and Yang Zheng and Alessio Lomuscio},
  title = {{Tight Neural Network Verification via Semidefinite Relaxations and Linear Reformulations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i7.20689},
}
Figure