FocusBranch: Combinatorial Branch-and-Bound for Neural Network Robustness Verification
Organizations: Simon Fraser University
Abstract
Verifying the local robustness of neural networks under perturbations is inherently combinatorial, as it must reason over all sparse subsets of perturbed pixels. This paper presents FocusBranch, a combinatorial branch-and-bound framework for robustness verification. The key insight is to make the -ball decomposable and branchable using a node abstraction, which consists of a focus pixel set and a level , permitting at most pixels outside . This abstraction unifies two branching mechanisms: concrete nodes branch through upper shadows to fix additional perturbed locations, while super nodes branch through covering designs to cover many perturbation cases with fewer child nodes. FocusBranch proves node safety by concretizing linear relaxations over node-constrained -balls and recursively branches on unknown nodes. Rather than relying on a fixed verification plan, it samples nodes across levels to estimate safe rates and costs, then selects a starting level and branching strategy predicted to minimize verification time. Experiments on fully connected and convolutional classifiers for MNIST, Fashion-MNIST, and CIFAR-10 show that FocusBranch verifies robustness effectively across architectures and outperforms state-of-the-art verifiers. The code is available at: https://github.com/simpl-group/FocusBranch.
Figures & tables
| Dataset | Network | Neurons | Img | CC | Cand. | FocusBranch | CoVerD + top - - GP | |||||
| R | R/Cand. | Time (s) | R | R/Cand. | Time (s) | |||||||
| MNIST | afc1 | 512 | 100 | 100 | 3 | 90 | 90 | 100.0% | 0.3 | 90 | 100.0% | 26.6 |
| 4 | 72 | 70 | 97.2% | 10.1 | 67 | 93.1% | 165.7 | |||||
| 5 | 57 | 52 | 91.2% | 17.8 | 30 | 52.6% | 203.3 | |||||
| 6 | 46 | 29 | 63.0% | 53.7 | 13 | 28.3% | 257.1 | |||||
| afc2 | 1024 | 100 | 100 | 3 | 94 | 94 | 100.0% | 0.3 | 94 | 100.0% | 37.2 | |
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Network | Neurons | Img | CC | Cand. | R | T/O | R/Cand.(%) | Time (s) | ||||
| MNIST | afc1 | 512 | 100 | 100 | 3 | 90 | 90 | 0 | 100.0% | 0.3 | 90 | 21 | 0 |
| 4 | 72 | 70 | 2 | 97.2% | 10.1 | 69 | 28 | 1 | |||||
| 5 | 57 | 52 | 5 | 91.2% | 17.8 | 52 | 30 | 0 | |||||
| 6 | 46 | 29 | 17 | 63.0% | 53.7 | 28 | 22 | 1 | |||||
| afc2 | 1024 | 100 | 100 | 3 | 94 | 94 | 0 | 100.0% | 0.3 | 94 | 14 | 0 | |
| 4 | 88 | 87 | 1 | 98.9% | 6.1 | 87 | 36 | 0 |
| Dataset | Network | Method | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| MNIST | bcv4 | CoVerD + top - - GP | 1286.4 | 1008.5 | T/O | 1002.5 | 1397.5 | T/O | 1248.2 | 905.5 | - | 784.9 |
| FocusBranch | 554.2 | 448.3 | T/O | 367.6 | 611.0 | 3145.6 | 557.1 | 363.3 | - | 299.0 | ||
| CIFAR-10 | bcv5 | CoVerD + top - - GP ∗ | 1608.0 | 1540.0 | 1698.0 | - | - | T/O | - | T/O | - | - |
| FocusBranch | 132.3 | 133.2 | 141.6 | - | - | 801.1 | - | T/O | - | - |
| Method | #Verified | Average Time (s) |
|---|---|---|
| MILP | 1245 | 58.7 |
| FocusBranch FC | 1599 | 44.6 |
| FocusBranch all | 2799 | 67.7 |
| Dataset | Network | Neurons | Img | CC | Cand. | FocusBranch | CoVerD + top - - GP | Speedup | |||||
| R/Cand. | Time (s) | R/Cand. | Time (s) | ||||||||||
| MNIST | afc1 | 512 | 100 | 100 | 5 | 57 | 38 | 66.7% | 275.0 | 26 | 45.6% | 116.4 | 4.7 |
| 6 | 46 | 20 | 43.5% | 136.8 | 10 | 21.7% | 378.0 | 5.1 | |||||
| afc2 | 1024 | 100 | 100 | 5 | 79 | 37 | 46.8% | 124.2 | 28 | 35.4% | 264.9 | 5.7 | |
| 6 | 68 | 20 | 29.4% | 211.8 | 13 | 19.1% | 649.0 | 16.7 | |||||
| afc3 | 1536 | 100 | 100 | 5 | 74 | 39 | 52.7% | 103.5 | 32 | 43.2% | 475.8 | 5.4 | |
| Verified | Instances invoking MILP | Share | |
|---|---|---|---|
| 3 | 952 | 57 | 6.0% |
| 4 | 839 | 85 | 10.1% |
| 5 | 641 | 54 | 8.4% |
| 6 | 367 | 10 | 2.7% |
| All | 2799 | 206 | 7.4% |
Neural Network Verification
Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.
See all 139 papers