On Efficiently Explaining Graph-Based Classifiers
  Recent work has shown that not only decision trees (DTs) may not be
interpretable but also proposed a polynomial-time algorithm for computing one
PI-explanation of a DT. This paper shows that for a wide range of classifiers,
globally referred to as decision graphs, and which include decision trees and
binary decision diagrams, but also their multi-valued variants, there exist
polynomial-time algorithms for computing one PI-explanation. In addition, the
paper also proposes a polynomial-time algorithm for computing one contrastive
explanation. These novel algorithms build on explanation graphs (XpG's). XpG's
denote a graph representation that enables both theoretical and practically
efficient computation of explanations for decision graphs. Furthermore, the
paper proposes a practically efficient solution for the enumeration of
explanations, and studies the complexity of deciding whether a given feature is
included in some explanation. For the concrete case of decision trees, the
paper shows that the set of all contrastive explanations can be enumerated in
polynomial time. Finally, the experimental results validate the practical
applicability of the algorithms proposed in the paper on a wide range of
publicly available benchmarks.
