  In recent years, post-hoc local instance-level and global dataset-level
explainability of black-box models has received a lot of attention. Much less
attention has been given to obtaining insights at intermediate or group levels,
which is a need outlined in recent works that study the challenges in realizing
the guidelines in the General Data Protection Regulation (GDPR). In this paper,
we propose a meta-method that, given a typical local explainability method, can
build a multilevel explanation tree. The leaves of this tree correspond to the
local explanations, the root corresponds to the global explanation, and
intermediate levels correspond to explanations for groups of data points that
it automatically clusters. The method can also leverage side information, where
users can specify points for which they may want the explanations to be
similar. We argue that such a multilevel structure can also be an effective
form of communication, where one could obtain few explanations that
characterize the entire dataset by considering an appropriate level in our
explanation tree. Explanations for novel test points can be cost-efficiently
obtained by associating them with the closest training points. When the local
explainability technique is generalized additive (viz. LIME, GAMs), we develop
a fast approximate algorithm for building the multilevel tree and study its
convergence behavior. We validate the effectiveness of the proposed technique
based on two human studies -- one with experts and the other with non-expert
users -- on real world datasets, and show that we produce high fidelity sparse
explanations on several other public datasets.
