# Streaming Weak Submodularity: Interpreting Neural Networks on the Fly

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2017.

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

- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Improving Attribution Methods by Learning Submodular Functions](https://mlsanity.com/paper/2104.09073/) (2021)
- [A Review of Explainable Artificial Intelligence in Manufacturing](https://mlsanity.com/paper/2107.02295/) (2021)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Explainability-aided Domain Generalization for Image Classification](https://mlsanity.com/paper/2104.01742/) (2021)
- [DynaAct: Large Language Model Reasoning with Dynamic Action Spaces](https://mlsanity.com/paper/2511.08043/) (2025)
- [GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions](https://mlsanity.com/paper/2403.10332/) (2024)

## Abstract (arXiv)

In many machine learning applications, it is important to explain the predictions of a black-box classifier. For example, why does a deep neural network assign an image to a particular class? We cast interpretability of black-box classifiers as a combinatorial maximization problem and propose an efficient streaming algorithm to solve it subject to cardinality constraints. By extending ideas from Badanidiyuru et al. [2014], we provide a constant factor approximation guarantee for our algorithm in the case of random stream order and a weakly submodular objective function. This is the first such theoretical guarantee for this general class of functions, and we also show that no such algorithm exists for a worst case stream order. Our algorithm obtains similar explanations of Inception V3 predictions 10 times faster than the state-of-the-art LIME framework of Ribeiro et al. [2016].