# Connecting Interpretability and Robustness in Decision Trees through Separation

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 68 references that are in the map.
- First posted on arXiv 14 Feb 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [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)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [The (Un)reliability of saliency methods](https://mlsanity.com/paper/1711.00867/) (2017)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [Improving the Adversarial Robustness and Interpretability of Deep Neural Networks by Regularizing their Input Gradients](https://mlsanity.com/paper/1711.09404/) (2017)
- [Model-Agnostic Interpretability of Machine Learning](https://mlsanity.com/paper/1606.05386/) (2016)
- ["How do I fool you?": Manipulating User Trust via Misleading Black Box Explanations](https://mlsanity.com/paper/1911.06473/) (2019)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Explaining the Explainer: A First Theoretical Analysis of LIME](https://mlsanity.com/paper/2001.03447/) (2020)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Learning Optimized Risk Scores](https://mlsanity.com/paper/1610.00168/) (2016)
- [Robust and Stable Black Box Explanations](https://mlsanity.com/paper/2011.06169/) (2020)
- [Evasion and Hardening of Tree Ensemble Classifiers](https://mlsanity.com/paper/1509.07892/) (2015)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [Gradient Methods Never Overfit On Separable Data](https://mlsanity.com/paper/2007.00028/) (2020)
- [Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks](https://mlsanity.com/paper/1906.03526/) (2019)
- [An Analysis of LIME for Text Data](https://mlsanity.com/paper/2010.12487/) (2020)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)

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

- [Framework for Evaluating Faithfulness of Local Explanations](https://mlsanity.com/paper/2202.00734/) (2022)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Verification-Aided Deep Ensemble Selection](https://mlsanity.com/paper/2202.03898/) (2022)
- [Unifying Model Explainability and Robustness for Joint Text Classification and Rationale Extraction](https://mlsanity.com/paper/2112.10424/) (2021)
- [Tree Variational Autoencoders](https://mlsanity.com/paper/2306.08984/) (2023)
- [A Theory of Interpretable Approximations](https://mlsanity.com/paper/2406.10529/) (2024)
- [Dynamic Model Tree for Interpretable Data Stream Learning](https://mlsanity.com/paper/2203.16181/) (2022)
- [Standardized Evaluation of Machine Learning Methods for Evolving Data Streams](https://mlsanity.com/paper/2204.13625/) (2022)
- [There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes](https://mlsanity.com/paper/2206.04266/) (2022)
- [Robustness questions the interpretability of graph neural networks: what to do?](https://mlsanity.com/paper/2505.02566/) (2025)
- [Interpretable Decision Trees Through MaxSAT](https://mlsanity.com/paper/2110.13854/) (2021)
- [Improving Stability in Decision Tree Models](https://mlsanity.com/paper/2305.17299/) (2023)
- [Tree of Concepts: Interpretable Continual Learners in Non-Stationary Clinical Domains](https://mlsanity.com/paper/2604.17089/) (2026)
- [Finding Safe Zones of policies Markov Decision Processes](https://mlsanity.com/paper/2202.11593/) (2022)
- [Interpretable Differencing of Machine Learning Models](https://mlsanity.com/paper/2306.06473/) (2023)
- [Surrogate Interpretable Graph for Random Decision Forests](https://mlsanity.com/paper/2506.01988/) (2025)

## Abstract (arXiv)

Recent research has recognized interpretability and robustness as essential properties of trustworthy classification. Curiously, a connection between robustness and interpretability was empirically observed, but the theoretical reasoning behind it remained elusive. In this paper, we rigorously investigate this connection. Specifically, we focus on interpretation using decision trees and robustness to l∞-perturbation. Previous works defined the notion of r-separation as a sufficient condition for robustness. We prove upper and lower bounds on the tree size in case the data is r-separated. We then show that a tighter bound on the size is possible when the data is linearly separated. We provide the first algorithm with provable guarantees both on robustness, interpretability, and accuracy in the context of decision trees. Experiments confirm that our algorithm yields classifiers that are both interpretable and robust and have high accuracy. The code for the experiments is available at https://github.com/yangarbiter/interpretable-robust-trees .