← 研踪 PaperTrailarXiv:2611.12024 · v1
FocusBranch: Combinatorial Branch-and-Bound for $\ell_0$ Neural Network Robustness Verification
首次提交 2026-11-09 16:00
版本更新 2026-11-09 16:00
雷达观测 2026-11-10 13:18
摘要
Verifying the local robustness of neural networks under $\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 $\ell_0$ robustness verification. The key insight is to make the $\ell_0$-ball decomposable and branchable using a node abstraction, which consists of a focus pixel set $\mathcal{S}$ and a level $l$, permitting at most $ε-l$ pixels outside $\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 $\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 $\ell_0$ robustness effectively across architectures and outperforms state-of-the-art verifiers. The code is available at: https://github.com/simpl-group/FocusBranch.
作者备注：Accepted to NeurIPS 2026. 32 pages, 11 figures, 6 tables
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-09 16:00 · 最新观测版本
FocusBranch: Combinatorial Branch-and-Bound for $\ell_0$ Neural Network Robustness Verification
Verifying the local robustness of neural networks under $\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 $\ell_0$ robustness verification. The key insight is to make the $\ell_0$-ball decomposable and branchable using a node abstraction, which consists of a focus pixel set $\mathcal{S}$ and a level $l$, permitting at most $ε-l$ pixels outside $\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 $\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 $\ell_0$ robustness effectively across architectures and outperforms state-of-the-art verifiers. The code is available at: https://github.com/simpl-group/FocusBranch.
查看此版本解读 →查看此版本原文 ↗