# Computing Linear Restrictions of Neural Networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2019.

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

- [A Holistic Approach to Unifying Automatic Concept Extraction and Concept Importance Estimation](https://mlsanity.com/paper/2306.07304/) (2023)
- [What I Cannot Predict, I Do Not Understand: A Human-Centered Evaluation Framework for Explainability Methods](https://mlsanity.com/paper/2112.04417/) (2021)
- [Look at the Variance! Efficient Black-box Explanations with Sobol-based Sensitivity Analysis](https://mlsanity.com/paper/2111.04138/) (2021)
- [Provable Repair of Deep Neural Networks](https://mlsanity.com/paper/2104.04413/) (2021)
- [Don't Lie to Me! Robust and Efficient Explainability with Verified Perturbation Analysis](https://mlsanity.com/paper/2202.07728/) (2022)
- [Making Sense of Dependence: Efficient Black-box Explanations Using Dependence Measure](https://mlsanity.com/paper/2206.06219/) (2022)
- [Incremental Verification of Neural Networks](https://mlsanity.com/paper/2304.01874/) (2023)
- [SyReNN: A Tool for Analyzing Deep Neural Networks](https://mlsanity.com/paper/2101.03263/) (2021)
- [Non-Uniform Interpolation in Integrated Gradients for Low-Latency Explainable-AI](https://mlsanity.com/paper/2302.11107/) (2023)
- [Precise and Generalized Robustness Certification for Neural Networks](https://mlsanity.com/paper/2306.06747/) (2023)
- [Verifying Attention Robustness of Deep Neural Networks against Semantic Perturbations](https://mlsanity.com/paper/2207.05902/) (2022)
- [Riemann Sum Optimization for Accurate Integrated Gradients Computation](https://mlsanity.com/paper/2410.04118/) (2024)
- [Semantic Robustness Certification for Vision-Language Models](https://mlsanity.com/paper/2606.18839/) (2026)
- [Interpretable Computer Vision Models through Adversarial Training: Unveiling the Robustness-Interpretability Connection](https://mlsanity.com/paper/2307.02500/) (2023)
- [SLICE: Sequential Likelihood-Free Inference via Conformal E-Values](https://mlsanity.com/paper/2610.13855/) (2026)

## Abstract (arXiv)

A linear restriction of a function is the same function with its domain restricted to points on a given line. This paper addresses the problem of computing a succinct representation for a linear restriction of a piecewise-linear neural network. This primitive, which we call ExactLine, allows us to exactly characterize the result of applying the network to all of the infinitely many points on a line. In particular, ExactLine computes a partitioning of the given input line segment such that the network is affine on each partition. We present an efficient algorithm for computing ExactLine for networks that use ReLU, MaxPool, batch normalization, fully-connected, convolutional, and other layers, along with several applications. First, we show how to exactly determine decision boundaries of an ACAS Xu neural network, providing significantly improved confidence in the results compared to prior work that sampled finitely many points in the input space. Next, we demonstrate how to exactly compute integrated gradients, which are commonly used for neural network attributions, allowing us to show that the prior heuristic-based methods had relative errors of 25-45% and show that a better sampling method can achieve higher accuracy with less computation. Finally, we use ExactLine to empirically falsify the core assumption behind a well-known hypothesis about adversarial examples, and in the process identify interesting properties of adversarially-trained networks.