# Abstraction based Output Range Analysis for Neural Networks

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2020.

## Built on by (most cited first, 30 of 34)

- [The Third International Verification of Neural Networks Competition (VNN-COMP 2022): Summary and Results](https://mlsanity.com/paper/2212.10376/) (2022)
- [A Review of Formal Methods applied to Machine Learning](https://mlsanity.com/paper/2104.02466/) (2021)
- [An Abstraction-Refinement Approach to Verifying Convolutional Neural Networks](https://mlsanity.com/paper/2201.01978/) (2022)
- [Formalising the Robustness of Counterfactual Explanations for Neural Networks](https://mlsanity.com/paper/2208.14878/) (2022)
- [Formally Explaining Neural Networks within Reactive Systems](https://mlsanity.com/paper/2308.00143/) (2023)
- [Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation](https://mlsanity.com/paper/2309.12545/) (2023)
- [Verification-Aided Deep Ensemble Selection](https://mlsanity.com/paper/2202.03898/) (2022)
- [SpArX: Sparse Argumentative Explanations for Neural Networks [Technical Report]](https://mlsanity.com/paper/2301.09559/) (2023)
- [Provable Preimage Under-Approximation for Neural Networks (Full Version)](https://mlsanity.com/paper/2305.03686/) (2023)
- [Abstraction and Refinement: Towards Scalable and Exact Verification of Neural Networks](https://mlsanity.com/paper/2207.00759/) (2022)
- [Verifying Generalization in Deep Learning](https://mlsanity.com/paper/2302.05745/) (2023)
- [Tighter Abstract Queries in Neural Network Verification](https://mlsanity.com/paper/2210.12871/) (2022)
- [PREMAP: A Unifying PREiMage APproximation Framework for Neural Networks](https://mlsanity.com/paper/2408.09262/) (2024)
- [Interval Abstractions for Robust Counterfactual Explanations](https://mlsanity.com/paper/2404.13736/) (2024)
- [Bisimulations for Neural Network Reduction](https://mlsanity.com/paper/2110.03726/) (2021)
- [Fully Automatic Neural Network Reduction for Formal Verification](https://mlsanity.com/paper/2305.01932/) (2023)
- [Towards a Certified Proof Checker for Deep Neural Network Verification](https://mlsanity.com/paper/2307.06299/) (2023)
- [Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations](https://mlsanity.com/paper/2407.07482/) (2024)
- [Safe and Reliable Training of Learning-Based Aerospace Controllers](https://mlsanity.com/paper/2407.07088/) (2024)
- [Learning on Abstract Domains: A New Approach for Verifiable Guarantee in Reinforcement Learning](https://mlsanity.com/paper/2106.06931/) (2021)
- [DelBugV: Delta-Debugging Neural Network Verifiers](https://mlsanity.com/paper/2305.18558/) (2023)
- [On the verification of Embeddings using Hybrid Markov Logic](https://mlsanity.com/paper/2312.08287/) (2023)
- [Verification of Bit-Flip Attacks against Quantized Neural Networks](https://mlsanity.com/paper/2502.16286/) (2025)
- [Online Verification of Deep Neural Networks under Domain Shift or Network Updates](https://mlsanity.com/paper/2106.12732/) (2021)
- [Boosting Verified Training for Robust Image Classifications via Abstraction](https://mlsanity.com/paper/2303.11552/) (2023)
- [Expediting Neural Network Verification via Network Reduction](https://mlsanity.com/paper/2308.03330/) (2023)
- [Permutation Invariance of Deep Neural Networks with ReLUs](https://mlsanity.com/paper/2110.09578/) (2021)
- [A Domain-Theoretic Framework for Robustness Analysis of Neural Networks](https://mlsanity.com/paper/2203.00295/) (2022)
- [Towards Global Neural Network Abstractions with Locally-Exact Reconstruction](https://mlsanity.com/paper/2210.12054/) (2022)
- [Efficiently Finding Adversarial Examples with DNN Preprocessing](https://mlsanity.com/paper/2211.08706/) (2022)

## Abstract (arXiv)

In this paper, we consider the problem of output range analysis for feed-forward neural networks with ReLU activation functions. The existing approaches reduce the output range analysis problem to satisfiability and optimization solving, which are NP-hard problems, and whose computational complexity increases with the number of neurons in the network. To tackle the computational complexity, we present a novel abstraction technique that constructs a simpler neural network with fewer neurons, albeit with interval weights called interval neural network (INN), which over-approximates the output range of the given neural network. We reduce the output range analysis on the INNs to solving a mixed integer linear programming problem. Our experimental results highlight the trade-off between the computation time and the precision of the computed output range.