Linearity Grafting: How Neuron Pruning Helps Certifiable Robustness

Abstract

Certifiable robustness is a highly desirable property for adopting deep neural networks (DNNs) in safety-critical scenarios, but often demands tedious computations to establish. The main hurdle lies in the massive amount of non-linearities in large DNNs. For ReLU networks under input perturbations, the ReLU neurons that may cross zero (referred to as ``unstable'' neurons) are often the key factor to determine the difficulty of certification. To trade-off the DNN expressiveness (which calls for more non-linearities) and robustness certification scalability (which prefers more linearities), we propose a novel solution to strategically manipulate neurons, by ``grafting" appropriate levels of linearity. The core of our proposal is to first linearize insignificant and unstable ReLU neurons, to eliminate the non-linear components that are both redundant for DNN performance and harmful for its certification. We then optimize the associated slopes and intercepts of the replaced linear activations for restoring the performance while maintaining certifiability. Hence, typical neuron pruning could be viewed as a special case of grafting a linear function of the fixed zero slope and intercept, that might overly restrict the network flexibility and sacrifice its performance. We conduct extensive experiments on multiple datasets and network backbones. Our proposal of linearity grafting is demonstrated to: (1) effectively tighten certified bounds; (2) achieve competitive certifiable robustness without certified robust training (i.e., over 30% improvements on CIFAR-10 models); and (3) scale up complete verification to large adversarially trained models with 17M parameters. Codes are provided in supplements.