Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations
This work addresses the problem of slow verification for provable explanations in neural networks, offering a more efficient method for researchers and practitioners in explainable AI, though it is incremental as it builds on existing verification techniques.
The paper tackles the scalability challenge of computing provably sufficient explanations for neural network predictions by introducing an abstraction-refinement technique that constructs reduced networks to speed up verification, achieving significant efficiency improvements in experiments.
Despite significant advancements in post-hoc explainability techniques for neural networks, many current methods rely on heuristics and do not provide formally provable guarantees over the explanations provided. Recent work has shown that it is possible to obtain explanations with formal guarantees by identifying subsets of input features that are sufficient to determine that predictions remain unchanged using neural network verification techniques. Despite the appeal of these explanations, their computation faces significant scalability challenges. In this work, we address this gap by proposing a novel abstraction-refinement technique for efficiently computing provably sufficient explanations of neural network predictions. Our method abstracts the original large neural network by constructing a substantially reduced network, where a sufficient explanation of the reduced network is also provably sufficient for the original network, hence significantly speeding up the verification process. If the explanation is in sufficient on the reduced network, we iteratively refine the network size by gradually increasing it until convergence. Our experiments demonstrate that our approach enhances the efficiency of obtaining provably sufficient explanations for neural network predictions while additionally providing a fine-grained interpretation of the network's predictions across different abstraction levels.