cs.LGNov 9, 2026

FocusBranch: Combinatorial Branch-and-Bound for ℓ0\ell_0 Neural Network Robustness Verification

Authors: Renwei Deng, Yang He, Linyi Li, Yuepeng Wang

Organizations: Simon Fraser University

Abstract

Verifying the local robustness of neural networks under ℓ0\ell_0 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 ℓ0\ell_0 robustness verification. The key insight is to make the ℓ0\ell_0-ball decomposable and branchable using a node abstraction, which consists of a focus pixel set S\mathcal{S} and a level ll, permitting at most ε−lε-l pixels outside S\mathcal{S}. 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 ℓ0\ell_0-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 ℓ0\ell_0 robustness effectively across architectures and outperforms state-of-the-art verifiers. The code is available at: https://github.com/simpl-group/FocusBranch.

Figures & tables

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Certified Robustness via Sparse Second-Order Cone Relaxations

    Oct 12, 2026Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma +3Convex RelaxationSecond-Order Cone Programming

  2. Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation

    Nov 3, 2026Yukina Nakagawa, Takami Sato, Ken Kobayashi +1Neural Network VerificationCertified Robustness