  Probabilistic graphical models, such as Markov random fields (MRF), exploit
dependencies among random variables to model a rich family of joint probability
distributions. Sophisticated inference algorithms, such as belief propagation
(BP), can effectively compute the marginal posteriors. Nonetheless, it is still
difficult to interpret the inference outcomes for important human decision
making. There is no existing method to rigorously attribute the inference
outcomes to the contributing factors of the graphical models. Shapley values
provide an axiomatic framework, but naively computing or even approximating the
values on general graphical models is challenging and less studied. We propose
GraphShapley to integrate the decomposability of Shapley values, the structure
of MRFs, and the iterative nature of BP inference in a principled way for fast
Shapley value computation, that 1) systematically enumerates the important
contributions to the Shapley values of the explaining variables without
duplicate; 2) incrementally compute the contributions without starting from
scratches. We theoretically characterize GraphShapley regarding independence,
equal contribution, and additivity. On nine graphs, we demonstrate that
GraphShapley provides sensible and practical explanations.
