Scalable Explanation of Inferences on Large Graphs

Abstract

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.

arXiv commentAccepted to ICDM 2019

References in corpus (9)

• European Union regulations on algorithmic decision-making and a "right to explanation"
• Understanding Black-box Predictions via Influence Functions
• Predicting multicellular function through multi-layer tissue networks
• Composing graphical models with neural networks for structured representations and fast inference
• An Evaluation of the Human-Interpretability of Explanation
• Increasing the Interpretability of Recurrent Neural Networks Using Hidden Markov Models
• "Influence Sketching": Finding Influential Samples In Large-Scale Regressions
• Smoke Screener or Straight Shooter: Detecting Elite Sybil Attacks in User-Review Social Networks
• Efficient Search for Diverse Coherent Explanations