  Symbolic techniques based on Satisfiability Modulo Theory (SMT) solvers have
been proposed for analyzing and verifying neural network properties, but their
usage has been fairly limited owing to their poor scalability with larger
networks. In this work, we propose a technique for combining gradient-based
methods with symbolic techniques to scale such analyses and demonstrate its
application for model explanation. In particular, we apply this technique to
identify minimal regions in an input that are most relevant for a neural
network's prediction. Our approach uses gradient information (based on
Integrated Gradients) to focus on a subset of neurons in the first layer, which
allows our technique to scale to large networks. The corresponding SMT
constraints encode the minimal input mask discovery problem such that after
masking the input, the activations of the selected neurons are still above a
threshold. After solving for the minimal masks, our approach scores the mask
regions to generate a relative ordering of the features within the mask. This
produces a saliency map which explains "where a model is looking" when making a
prediction. We evaluate our technique on three datasets - MNIST, ImageNet, and
Beer Reviews, and demonstrate both quantitatively and qualitatively that the
regions generated by our approach are sparser and achieve higher saliency
scores compared to the gradient-based methods alone. Code and examples are at -
https://github.com/google-research/google-research/tree/master/smug_saliency
