Scalable Explanation of Inferences on Large Graphs
  Probabilistic inferences distill knowledge from graphs to aid human make
important decisions. Due to the inherent uncertainty in the model and the
complexity of the knowledge, it is desirable to help the end-users understand
the inference outcomes. Different from deep or high-dimensional parametric
models, the lack of interpretability in graphical models is due to the cyclic
and long-range dependencies and the byzantine inference procedures. Prior works
did not tackle cycles and make \textit{the} inferences interpretable. To close
the gap, we formulate the problem of explaining probabilistic inferences as a
constrained cross-entropy minimization problem to find simple subgraphs that
faithfully approximate the inferences to be explained. We prove that the
optimization is NP-hard, while the objective is not monotonic and submodular to
guarantee efficient greedy approximation. We propose a general beam search
algorithm to find simple trees to enhance the interpretability and diversity in
the explanations, with parallelization and a pruning strategy to allow
efficient search on large and dense graphs without hurting faithfulness. We
demonstrate superior performance on 10 networks from 4 distinct applications,
comparing favorably to other explanation methods. Regarding the usability of
the explanation, we visualize the explanation in an interface that allows the
end-users to explore the diverse search results and find more personalized and
sensible explanations.
