Faithful and Diverse Subgraph as Explanation for Large Probabilistic Graphical Models

Probabilistic graphical models, capturing dependencies among random variables , have proven their capability in many practical tasks. However, their opaque inference mechanisms prevent broader applications. Unlike explaining deep neural networks, the explainability challenges in graphical models stem from recursive and extensive dependencies coupled with intricate inference processes. To address these challenges, the explanation of probabilistic inferences task is formulated as a faithful subgraph extraction problem, formally defined as a constrained minimization problem. We prove that the objective function with cardinality constraints is NP-hard and lacks monotonicity and submod-ularity, critical to guarantee efficient greedy solutions. A general beam search algorithm, GraphExp, is proposed to extract faithful, user-friendly, and diverse trees as explanations. We explore various instantializations of GraphExp to meet diverse practical requirements, and justify these variants by analyzing the underlying mechanism of the inference in graphs. Experimentally, GraphExp out-performs existing methods on 13 networks from 4 distinct domains. Additionally, we present the usability of the explanations within an interactive interface that enables humans to explore more diverse and personalized explanations. Code is in https://anonymous.4open.science/r/GraphExp-E1FB.