General Cutting Planes for Bound-Propagation-Based Neural Network Verification

Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, J Zico Kolter

TL;DR

GCP-CROWN is a new verification framework that combines the lightning-fast, GPU-accelerated speed of bound propagation with the mathematical "tightness" of traditional Mixed-Integer Programming (MIP) solvers. By generalizing bound propagation to handle complex "cutting plane" constraints, the authors achieved a massive leap in performance, solving twice as many "hard" verification instances as previous state-of-the-art tools.

What Problem Does This Paper Address?

Formally verifying that a neural network is safe or robust (e.g., proving a self-driving car's vision system won't misclassify a stop sign under specific lighting conditions) is an NP-complete problem. Researchers generally use two types of tools to tackle this:

  1. MIP Solvers: These are mathematically rigorous and use "cutting planes" (extra linear constraints) to tighten the search space. However, they are computationally heavy, slow, and typically run only on CPUs.
  2. Bound Propagation (BP): Methods like CROWN are incredibly fast and run efficiently on GPUs. Unfortunately, they use loose relaxations that often fail to prove properties on complex, "hard" instances.

The core gap in the field has been that BP methods couldn't handle the general, complex constraints that MIP solvers generate. If you tried to add a "cut" that involved neurons from different layers or integer variables representing ReLU states, the BP math simply broke down. This paper introduces GCP-CROWN to fix that fundamental limitation.

Methods

The authors' primary contribution is a mathematical generalization of the bound propagation procedure.

  • Generalized Bound Propagation: They derived a new dual formulation for the linear programming (LP) relaxation of a neural network. Unlike previous versions, this new formulation can incorporate constraints involving any variables in the network, including the binary "indicator" variables that track whether a ReLU neuron is active or inactive.
  • The GCP-CROWN Algorithm: This updated algorithm allows the verifier to "propagate" bounds through the network while simultaneously respecting these new, tighter constraints.
System architecture of GCP-CROWN showing the hybrid parallel integration of GPU-accelerated bound propagation and CPU-based MIP solvers.
  • Hybrid Parallel Architecture: To maximize efficiency, the system runs a GPU-based branch-and-bound (BaB) process in parallel with a CPU-based MIP solver (like CPLEX). The MIP solver works in the background to find high-quality cutting planes. As soon as a new "cut" is found, it is asynchronously injected into the GPU's bound propagation process to immediately tighten the verification bounds.

Key Insights and Ideas

  • The "Best of Both Worlds": You no longer have to choose between the speed of a GPU and the tightness of a MIP solver. GCP-CROWN allows the verifier to benefit from the MIP solver's "intelligence" without being bottlenecked by its slow branching.
  • Global Dependencies: Traditional BP methods only looked at local relationships (one neuron or one layer at a time). Cutting planes allow the verifier to capture complex dependencies between neurons across completely different layers.
  • Asynchronous Integration: Because the GPU doesn't wait for the MIP solver, the verifier remains fast. If the MIP solver finds a great cut, the verifier gets stronger; if it doesn't, the verifier still performs at the baseline level of existing state-of-the-art BP tools.

Key Results

The authors evaluated their method on several standard, high-difficulty benchmarks used in the International Verification of Neural Networks Competition (VNN-COMP), including oval20, oval21, cifar10-resnet, and SDP-FO.

GCP-CROWN set a new bar for performance in the verification community:

  • oval20: It became the first verifier to completely solve all 100 instances in this benchmark, with an average time of less than 5 seconds per instance.
  • oval21: It verified 23 out of 30 instances, more than doubling the performance of the 2021 competition winner (which verified only 11).
  • VNN-COMP 2022: GCP-CROWN was a core component of the $\alpha,\beta$-CROWN verifier, which won the overall competition.
Performance comparison on CIFAR-10 benchmarks. GCP-CROWN (green line) solves more instances in less time compared to baseline methods.

Furthermore, on the SDP-FO benchmarks, it achieved higher "verified accuracy" (proving robustness) in significantly less time than specialized multi-neuron relaxation methods, showcasing its efficiency and scalability.

Limitations and Future Work

  • ReLU Focus: The current implementation is optimized for piece-wise linear ReLU networks. Extending this to non-linear activations like Sigmoid or Tanh is mathematically possible but requires further derivation.
  • External Solver Dependency: The method currently relies on off-the-shelf MIP solvers (like CPLEX or Gurobi) to generate cuts. Because these solvers are general-purpose, the authors suggest that developing "neural-network-specific" cut generators could lead to even faster and tighter verification.
  • Branching Heuristics: While the cuts help tighten bounds, the choice of which neurons to "split" during branching remains critical. Better integration between cut generation and branching heuristics is a promising path for future research.

Summary updated

Abstract

Bound propagation methods, when combined with branch and bound, are among the most effective methods to formally verify properties of deep neural networks such as correctness, robustness, and safety. However, existing works cannot handle the general form of cutting plane constraints widely accepted in traditional solvers, which are crucial for strengthening verifiers with tightened convex relaxations. In this paper, we generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints, including those involving relaxed integer variables that do not appear in existing bound propagation formulations. Our generalized bound propagation method, GCP-CROWN, opens up the opportunity to apply general cutting plane methods for neural network verification while benefiting from the efficiency and GPU acceleration of bound propagation methods. As a case study, we investigate the use of cutting planes generated by off-the-shelf mixed integer programming (MIP) solver. We find that MIP solvers can generate high-quality cutting planes for strengthening bound-propagation-based verifiers using our new formulation. Since the branching-focused bound propagation procedure and the cutting-plane-focused MIP solver can run in parallel utilizing different types of hardware (GPUs and CPUs), their combination can quickly explore a large number of branches with strong cutting planes, leading to strong verification performance. Experiments demonstrate that our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark compared to the best tool in VNN-COMP 2021, and also noticeably outperforms state-of-the-art verifiers on a wide range of benchmarks. GCP-CROWN is part of the $\alpha,\beta$-CROWN verifier, the VNN-COMP 2022 winner. Code is available at http://PaperCode.cc/GCP-CROWN.
BibTeX
@inproceedings{zhang2022general,
  author = {Huan Zhang and Shiqi Wang and Kaidi Xu and Linyi Li and Bo Li and Suman Jana and Cho-Jui Hsieh and J Zico Kolter},
  title = {{General Cutting Planes for Bound-Propagation-Based Neural Network Verification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=5haAJAcofjc},
}
Figure