ML Security PapersLipschitz-aware Linearity Grafting for Certified Robustness
Published on arXiv
2510.25130
Input Manipulation Attack
OWASP ML Top 10 — ML01
Key Finding
Grafting linearity into influential ReLU neurons identified by the weighted interval score tightens the l_∞ local Lipschitz constant to levels comparable to certifiably robust models, improving certified robustness even without certified training.
Lipschitz-aware Linearity Grafting (weighted interval score)
Novel technique introduced
Lipschitz constant is a fundamental property in certified robustness, as smaller values imply robustness to adversarial examples when a model is confident in its prediction. However, identifying the worst-case adversarial examples is known to be an NP-complete problem. Although over-approximation methods have shown success in neural network verification to address this challenge, reducing approximation errors remains a significant obstacle. Furthermore, these approximation errors hinder the ability to obtain tight local Lipschitz constants, which are crucial for certified robustness. Originally, grafting linearity into non-linear activation functions was proposed to reduce the number of unstable neurons, enabling scalable and complete verification. However, no prior theoretical analysis has explained how linearity grafting improves certified robustness. We instead consider linearity grafting primarily as a means of eliminating approximation errors rather than reducing the number of unstable neurons, since linear functions do not require relaxation. In this paper, we provide two theoretical contributions: 1) why linearity grafting improves certified robustness through the lens of the $l_\infty$ local Lipschitz constant, and 2) grafting linearity into non-linear activation functions, the dominant source of approximation errors, yields a tighter local Lipschitz constant. Based on these theoretical contributions, we propose a Lipschitz-aware linearity grafting method that removes dominant approximation errors, which are crucial for tightening the local Lipschitz constant, thereby improving certified robustness, even without certified training. Our extensive experiments demonstrate that grafting linearity into these influential activations tightens the $l_\infty$ local Lipschitz constant and enhances certified robustness.
Key Contributions
- Theoretical analysis linking linearity grafting of unstable ReLUs to tighter l_∞ local Lipschitz constants and improved certified robustness
- Weighted interval score criterion identifying influential neurons whose replacement with linear functions maximally reduces approximation errors in Lipschitz bound computation
- Slope loss and backward neuron selection algorithm to further stabilize unstable neurons and improve certified robustness without requiring certified training
🛡️ Threat Analysis
Primary contribution is a certified defense against adversarial examples — the Lipschitz-aware linearity grafting method provides provable robustness guarantees by reducing approximation errors in neural network verification, directly targeting inference-time input manipulation attacks.