# Provably Tightest Linear Approximation for Robustness Verification of Sigmoid-like Neural Networks

arXiv: https://arxiv.org/abs/2208.09872 · HTML: https://mlsanity.com/paper/2208.09872/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 21 Aug 2022.

## Builds on (most cited first, 27 of 27)

- [Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks](https://mlsanity.com/paper/1506.01497/) (2015)
- [Fully Convolutional Networks for Semantic Segmentation](https://mlsanity.com/paper/1411.4038/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [DeepPose: Human Pose Estimation via Deep Neural Networks](https://mlsanity.com/paper/1312.4659/) (2013)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [NNV: The Neural Network Verification Tool for Deep Neural Networks and Learning-Enabled Cyber-Physical Systems](https://mlsanity.com/paper/2004.05519/) (2020)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Reachability Analysis of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1805.02242/) (2018)
- [Output Reachable Set Estimation and Verification for Multi-Layer Neural Networks](https://mlsanity.com/paper/1708.03322/) (2017)
- [Trustworthy AI](https://mlsanity.com/paper/2011.02272/) (2020)
- [Lipschitz Certificates for Layered Network Structures Driven by Averaged Activation Operators](https://mlsanity.com/paper/1903.01014/) (2019)
- [CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networks](https://mlsanity.com/paper/1811.12395/) (2018)
- [The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification](https://mlsanity.com/paper/2006.14076/) (2020)
- [Fastened CROWN: Tightened Neural Network Robustness Certificates](https://mlsanity.com/paper/1912.00574/) (2019)
- [Scalable Quantitative Verification For Deep Neural Networks](https://mlsanity.com/paper/2002.06864/) (2020)
- [Reachability Is NP-Complete Even for the Simplest Neural Networks](https://mlsanity.com/paper/2108.13179/) (2021)
- [NeuroDiff: Scalable Differential Verification of Neural Networks using Fine-Grained Approximation](https://mlsanity.com/paper/2009.09943/) (2020)
- [Non-Negative Networks Against Adversarial Attacks](https://mlsanity.com/paper/1806.06108/) (2018)
- [Exposing Previously Undetectable Faults in Deep Neural Networks](https://mlsanity.com/paper/2106.00576/) (2021)
- [Mal2GCN: A Robust Malware Detection Approach Using Deep Graph Convolutional Networks With Non-Negative Weights](https://mlsanity.com/paper/2108.12473/) (2021)

## Built on by (most cited first, 8 of 8)

- [Using Z3 for Formal Modeling and Verification of FNN Global Robustness](https://mlsanity.com/paper/2304.10558/) (2023)
- [A Tale of Two Approximations: Tightening Over-Approximation for DNN Robustness Verification via Under-Approximation](https://mlsanity.com/paper/2305.16998/) (2023)
- [Achieving the Tightest Relaxation of Sigmoids for Formal Verification](https://mlsanity.com/paper/2408.10491/) (2024)
- [Tightening Robustness Verification of MaxPool-based Neural Networks via Minimizing the Over-Approximation Zone](https://mlsanity.com/paper/2211.09810/) (2022)
- [Boosting Verified Training for Robust Image Classifications via Abstraction](https://mlsanity.com/paper/2303.11552/) (2023)
- [DualApp: Tight Over-Approximation for Neural Network Robustness Verification via Under-Approximation](https://mlsanity.com/paper/2211.11186/) (2022)
- [Towards General Robustness Verification of MaxPool-based Convolutional Neural Networks via Tightening Linear Approximation](https://mlsanity.com/paper/2406.00699/) (2024)
- [Precise Verification of Transformers through ReLU-Catalyzed Abstraction Refinement](https://mlsanity.com/paper/2605.14294/) (2026)

## Abstract (arXiv)

The robustness of deep neural networks is crucial to modern AI-enabled systems and should be formally verified. Sigmoid-like neural networks have been adopted in a wide range of applications. Due to their non-linearity, Sigmoid-like activation functions are usually over-approximated for efficient verification, which inevitably introduces imprecision. Considerable efforts have been devoted to finding the so-called tighter approximations to obtain more precise verification results. However, existing tightness definitions are heuristic and lack theoretical foundations. We conduct a thorough empirical analysis of existing neuron-wise characterizations of tightness and reveal that they are superior only on specific neural networks. We then introduce the notion of network-wise tightness as a unified tightness definition and show that computing network-wise tightness is a complex non-convex optimization problem. We bypass the complexity from different perspectives via two efficient, provably tightest approximations. The results demonstrate the promising performance achievement of our approaches over state of the art: (i) achieving up to 251.28% improvement to certified lower robustness bounds; and (ii) exhibiting notably more precise verification results on convolutional networks.