# Don't Lie to Me! Robust and Efficient Explainability with Verified Perturbation Analysis

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 78 references that are in the map.
- First posted on arXiv 15 Feb 2022.

## Builds on (most cited first, 30 of 49)

- [Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization](https://mlsanity.com/paper/1610.02391/) (2016)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [SmoothGrad: removing noise by adding noise](https://mlsanity.com/paper/1706.03825/) (2017)
- [Striving for Simplicity: The All Convolutional Net](https://mlsanity.com/paper/1412.6806/) (2014)
- [Grad-CAM++: Improved Visual Explanations for Deep Convolutional Networks](https://mlsanity.com/paper/1710.11063/) (2017)
- [RISE: Randomized Input Sampling for Explanation of Black-box Models](https://mlsanity.com/paper/1806.07421/) (2018)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Interpretable Explanations of Black Boxes by Meaningful Perturbation](https://mlsanity.com/paper/1704.03296/) (2017)
- [Towards Faithfully Interpretable NLP Systems: How should we define and evaluate faithfulness?](https://mlsanity.com/paper/2004.03685/) (2020)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Interpretation of Neural Networks is Fragile](https://mlsanity.com/paper/1710.10547/) (2017)
- [Evaluating the visualization of what a Deep Neural Network has learned](https://mlsanity.com/paper/1509.06321/) (2015)
- [The (Un)reliability of saliency methods](https://mlsanity.com/paper/1711.00867/) (2017)
- [On the (In)fidelity and Sensitivity for Explanations](https://mlsanity.com/paper/1901.09392/) (2019)
- [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)
- [Evaluating and Aggregating Feature-based Model Explanations](https://mlsanity.com/paper/2005.00631/) (2020)
- [Quantus: An Explainable AI Toolkit for Responsible Evaluation of Neural Network Explanations and Beyond](https://mlsanity.com/paper/2202.06861/) (2022)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Reliable Post hoc Explanations: Modeling Uncertainty in Explainability](https://mlsanity.com/paper/2008.05030/) (2020)

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

- [CRAFT: Concept Recursive Activation FacTorization for Explainability](https://mlsanity.com/paper/2211.10154/) (2022)
- [A Holistic Approach to Unifying Automatic Concept Extraction and Concept Importance Estimation](https://mlsanity.com/paper/2306.07304/) (2023)
- [Harmonizing the object recognition strategies of deep neural networks with humans](https://mlsanity.com/paper/2211.04533/) (2022)
- [Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks](https://mlsanity.com/paper/2210.13915/) (2022)
- [Decoupling Pixel Flipping and Occlusion Strategy for Consistent XAI Benchmarks](https://mlsanity.com/paper/2401.06654/) (2024)
- [Unlocking Feature Visualization for Deeper Networks with MAgnitude Constrained Optimization](https://mlsanity.com/paper/2306.06805/) (2023)
- [Xplique: A Deep Learning Explainability Toolbox](https://mlsanity.com/paper/2206.04394/) (2022)
- [Formally Explaining Neural Networks within Reactive Systems](https://mlsanity.com/paper/2308.00143/) (2023)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Natural Example-Based Explainability: a Survey](https://mlsanity.com/paper/2309.03234/) (2023)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [Diffusion Models as Artists: Are we Closing the Gap between Humans and Machines?](https://mlsanity.com/paper/2301.11722/) (2023)
- [Keep the Faith: Faithful Explanations in Convolutional Neural Networks for Case-Based Reasoning](https://mlsanity.com/paper/2312.09783/) (2023)
- [Tokenize Image Patches: Global Context Fusion for Effective Haze Removal in Large Images](https://mlsanity.com/paper/2504.09621/) (2025)
- [On the explainable properties of 1-Lipschitz Neural Networks: An Optimal Transport Perspective](https://mlsanity.com/paper/2206.06854/) (2022)
- [SPES: Spectrogram Perturbation for Explainable Speech-to-Text Generation](https://mlsanity.com/paper/2411.01710/) (2024)
- [Assessment of the Reliablity of a Model's Decision by Generalizing Attribution to the Wavelet Domain](https://mlsanity.com/paper/2305.14979/) (2023)
- [Feature Accentuation: Revealing 'What' Features Respond to in Natural Images](https://mlsanity.com/paper/2402.10039/) (2024)
- [A Study of Nationality Bias in Names and Perplexity using Off-the-Shelf Affect-related Tweet Classifiers](https://mlsanity.com/paper/2407.01834/) (2024)
- [Efficient Robust Conformal Prediction via Lipschitz-Bounded Networks](https://mlsanity.com/paper/2506.05434/) (2025)
- [Mitigating Low-Frequency Bias: Feature Recalibration and Frequency Attention Regularization for Adversarial Robustness](https://mlsanity.com/paper/2407.04016/) (2024)
- [FAME: Formal Abstract Minimal Explanation for Neural Networks](https://mlsanity.com/paper/2603.10661/) (2026)
- [Explainable Image Recognition via Enhanced Slot-attention Based Classifier](https://mlsanity.com/paper/2407.05616/) (2024)
- [OMENN: One Matrix to Explain Neural Networks](https://mlsanity.com/paper/2412.02399/) (2024)
- [Interpretable 3D Neural Object Volumes for Robust Conceptual Reasoning](https://mlsanity.com/paper/2503.13429/) (2025)
- [A Survey on Interpretability in Visual Recognition](https://mlsanity.com/paper/2507.11099/) (2025)
- [Deep Natural Language Feature Learning for Interpretable Prediction](https://mlsanity.com/paper/2311.05754/) (2023)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)
- [Tensor Polynomial Additive Model](https://mlsanity.com/paper/2406.02980/) (2024)

## Abstract (arXiv)

A variety of methods have been proposed to try to explain how deep neural networks make their decisions. Key to those approaches is the need to sample the pixel space efficiently in order to derive importance maps. However, it has been shown that the sampling methods used to date introduce biases and other artifacts, leading to inaccurate estimates of the importance of individual pixels and severely limit the reliability of current explainability methods. Unfortunately, the alternative -- to exhaustively sample the image space is computationally prohibitive. In this paper, we introduce EVA (Explaining using Verified perturbation Analysis) -- the first explainability method guarantee to have an exhaustive exploration of a perturbation space. Specifically, we leverage the beneficial properties of verified perturbation analysis -- time efficiency, tractability and guaranteed complete coverage of a manifold -- to efficiently characterize the input variables that are most likely to drive the model decision. We evaluate the approach systematically and demonstrate state-of-the-art results on multiple benchmarks.