PaperlayerView exact revision on arXiv

Source-linked AI summary

PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks

Minh N. Vu, My T. Thai

arXiv:2010.05788v1cs.LG

TL;DR

GNNs’ graph structure makes their predictions difficult to explain, while existing approaches have limitations in modeling dependencies and practical applicability. PGM-Explainer uses a model-agnostic probabilistic graphical model to approximate predictions and identify crucial components. The method theoretically captures the target’s Markov blanket and performs accurately and intuitively across synthetic and real-world evaluations.

  • Problem

    GNN predictions are difficult to explain, while existing explainers have limited evidence, model-access requirements, and linear-independence assumptions.

  • Method

    PGM-Explainer queries a black-box GNN and constructs an interpretable Bayesian network that approximates the target prediction and represents feature dependencies.

  • Results

    Experiments on synthetic and real-world node- and graph-classification datasets show accurate, precise, and intuitive explanations, with PGM-Explainer outperforming other methods in several evaluations.

  • Takeaways & Limitations

    PGM-Explainer provides explanations that capture non-linear feature contributions and are favored by end-users within the evaluated settings.

  • Takeaways & Limitations

    Optimal PGM structure learning from sampled data is intractable, constraining practical optimization of the explanation model.

Abstract

from arXiv · show

In Graph Neural Networks (GNNs), the graph structure is incorporated into the learning of node representations. This complex structure makes explaining GNNs' predictions become much more challenging. In this paper, we propose PGM-Explainer, a Probabilistic Graphical Model (PGM) model-agnostic explainer for GNNs. Given a prediction to be explained, PGM-Explainer identifies crucial graph components and generates an explanation in form of a PGM approximating that prediction. Different from existing explainers for GNNs where the explanations are drawn from a set of linear functions of explained features, PGM-Explainer is able to demonstrate the dependencies of explained features in form of conditional probabilities. Our theoretical analysis shows that the PGM generated by PGM-Explainer includes the Markov-blanket of the target prediction, i.e. including all its statistical information. We also show that the explanation returned by PGM-Explainer contains the same set of independence statements in the perfect map. Our experiments on both synthetic and real-world datasets show that PGM-Explainer achieves better performance than existing explainers in many benchmark tasks.

1 Introduction

GNN explanations are needed for transparency, safety, and bias detection, but existing GNN explainers have important methodological and practical limitations. PGM-Explainer addresses these issues with a model-agnostic probabilistic graphical model that captures feature dependencies and yields accurate, intuitive explanations.

  • Understanding GNN decisions supports transparency, failure detection, and discovery of unwanted biases before deployment.
  • GNN explainers lag behind CNN explainers, and GNNExplainer’s quality and mutual-information basis remain insufficiently established.
  • Existing gradient-based and mutual-information methods may require model internals, fractional adjacency matrices, or linear independence assumptions.
  • PGM-Explainer is a model-agnostic explainer that approximates a GNN prediction with an interpretable Bayesian network.
  • Its Bayesian-network explanation represents dependencies among explained features and theoretically includes the target prediction’s Markov blanket when a perfect map exists.
  • Experiments on synthetic and real-world node- and graph-classification datasets show accurate and intuitive explanations.

2 Preliminaries

The paper frames explanations as interpretable models selected under compactness constraints, choosing probabilistic graphical models to represent dependencies in GNN predictions. Bayesian networks provide the primary representation, with an optional constraint making the target a leaf for efficiency and interpretability.

  • The black-box setting permits explainers to query predictions but forbids back-propagation and access to the GNN’s internal parameters.
  • The explanation framework selects an interpretable model by optimizing a score over a domain, optionally restricting solutions for compactness.
  • Probabilistic graphical models encode complex distributions compactly and expose dependencies among underlying random variables.
  • Bayesian networks represent conditional dependencies with directed acyclic graphs and support established structure-learning procedures.
  • The Bayesian-network optimization bounds the number of variables and requires inclusion of the target prediction.
  • A no-child constraint can make the target a leaf, improving conditional-probability query efficiency and explanation intuitiveness.

3 PGM-Explainer: Probabilistic Graphical Model Explanations for GNNs

PGM-Explainer generates sampled perturbation data, selects important variables, and learns a compact Bayesian-network explanation of a GNN prediction. Its variable-selection guarantees preserve the target’s Markov blanket, while BIC-based structure learning captures dependencies and can achieve I-equivalence under stated assumptions.

  • Illustrative example: In the illustrative motif example, PGM-Explainer identifies all motif nodes and expresses feature contributions through conditional probabilities, including an increase from 47.2% to 65.8% when node A’s prediction is known.The Bayesian-network explanation estimates the target node E’s predicted role conditional on realizations of other nodes.
  • Data generation and variable selection: PGM-Explainer perturbs graph features, records prediction changes for target-neighborhood variables, filters unimportant variables, and learns a PGM from the remaining data.For graph classification, all nodes can influence the prediction, so the sampled data includes node variables and an additional target variable.
  • Computational considerations: Optimal PGM structure learning is intractable for typical GNN neighborhoods containing thousands of nodes, motivating further variable trimming before structure learning.The variable-selection stage is therefore used to reduce the number of variables examined by the structure-learning algorithms.
  • Data generation and variable selection: The explainer retains a variable set U(t) guaranteed to contain the target’s Markov blanket under a perfect-map assumption, preserving the target’s statistical information.The construction uses pairwise dependence tests rather than the conditional-dependence tests required by conventional Markov-blanket algorithms.
  • Structure learning: PGM-Explainer learns a Bayesian network over selected variables using a BIC objective that balances maximized likelihood against model dimension.Exhaustive search can solve the objective, while hill climbing provides good local optima with substantially lower running time.
  • Structure learning: With increasing sample size, adding the target and its optimal parents under the no-child procedure yields a Bayesian network I-equivalent to the perfect map with probability 1.The no-child constraint makes the target a leaf, supporting more efficient conditional-probability queries and a more intuitive explanation.

4 Experiments

Experiments compare PGM-Explainer with existing GNN explainers on synthetic, signed-network, and MNIST graph datasets. PGM-Explainer outperforms other methods on several benchmark measures and receives higher human scores, while selecting nodes through Markov-blanket membership in the MNIST study.

  • Datasets and Experiment Settings: Experiments compare PGM-Explainer with GNNExplainer, SHAP, and gradient-based methods across synthetic and real-world GNN tasks.The real-world tasks use Bitcoin-Alpha, Bitcoin-OTC, and MNIST SuperPixel-Graph datasets.
  • Results on Synthetic Datasets: PGM-Explainer outperforms other explanation methods, especially on synthetic datasets 2 and 6.Dataset 6 requires integrating features from multiple neighbors and, for some nodes, almost all 2-hop neighbors.
  • Results on Synthetic Datasets: PGM-Explainer can return fewer than the motif size when dependence tests show that the GNN does not require all motif nodes.This flexibility can improve overall precision on some synthetic datasets.
  • Results on Real-world Datasets: PGM-Explainer achieves significantly higher node precision than other methods on Trust weighted signed-network datasets.The experiments test explanations containing 3, 4, and 5 accounts.
  • Results on Real-world Datasets: In a human-subjective test, PGM-Explainer explanations receive much higher scores than SHAP and GRAD explanations.The test used 48 correctly classified graphs and ten end-users scored the importance of highlighted nodes from 0 to 10.

5 Conclusion

The conclusion presents PGM-Explainer as an interpretable method for explaining GNN predictions through graphical-model approximations. Experiments report high accuracy and precision, and end-users favor its explanations, while future work will examine other graphical models and learning choices.

  • Conclusion: PGM-Explainer explains predictions of any GNN by approximating the target prediction with a graphical model.The method represents non-linear contributions of explained features in an interpretable manner.
  • Conclusion: Experiments show high accuracy and precision for PGM-Explainer, and end-users favor its explanations.The conclusion also identifies support for exploring Markov networks and dependency networks as alternative interpretable models.
  • Conclusion: Future research will analyze how different objective functions and structure-learning methods affect explanation quality and running time.

Broader Impact

The paper describes PGM-Explainer as addressing non-linear feature dependencies in GNN explanations, with potential relevance to complex GNN applications across domains.

  • Broader Impact: PGM-Explainer covers non-linear dependencies between features, a key aspect of graph data, while explaining decisions of any GNN model.
  • Broader Impact: The contribution may benefit GNN-based applications deployed across varied domain fields by supporting interpretable explanations.

A Additive feature attribution methods unify existing explainers for GNNs

Existing GNN explainers are unified as additive feature attribution methods, which use linear functions and therefore assume explained features contribute independently. Gradient-based methods and GNNExplainer fit this framework, while GNNExplainer additionally requires fractional adjacency inputs that some GNNs do not support.

  • Existing explainers: Current GNN explainers, including gradient-based methods and GNNExplainer, are analyzed within the additive feature attribution framework.Gradient-based methods assign importance scores through back-propagation, while GNNExplainer optimizes a subgraph using mutual information.
  • Additive feature attribution methods: Additive feature attribution methods represent explanations as linear functions of binary feature-selection variables with associated weights.For gradient-based explanations, the weights can be chosen as summed gradients or adjusted for other gradient-based methods.
  • GNNExplainer: GNNExplainer relaxes binary adjacency selection into a fractional adjacency matrix and uses mean-field optimization to minimize conditional entropy.The explanation is selected from the optimized adjacency values.
  • GNNExplainer: GNNExplainer may fail on architectures whose adjacency information is used in discrete feature aggregation, because fractional adjacency inputs are not well-defined.The passage specifically identifies GraphSage and GIN-Graph as examples of such architectures.

B Example of PGM-Explainer with and without no-child constraint

The no-child constraint preserves the nodes selected for explanation but changes the Bayesian-network edges, trading a simpler faithful model for a more intuitive structure centered on the target’s Markov blanket. PGM-Explainer learns these structures from sampled data using BIC, whose consistency supports recovering the perfect-map independence structure when the relevant assumptions hold.

  • Example comparison: The no-child constraint does not change the set of nodes identified by PGM-Explainer, but it changes the edges in the Bayesian network.The example explains node C’s role "blue" prediction using networks learned with and without the constraint.
  • Without no-child constraint: Without the constraint, the network has fewer edges and parameters and more independence assertions, but it may mislead nonexperts despite being faithful to the data.In the example, C’s Markov blanket is {A, B, E}, including E without a one-direction arrow chain connecting E and C.
  • With no-child constraint: With the constraint, the example reverses C → A and adds B → A and E → C, producing a more complex network whose parents directly identify C’s Markov blanket.The constrained form also makes factorized inference queries on C more convenient when C has no child.
  • PGM structure: A perfect map satisfies I(B) = I(P), whereas a minimal I-map can omit important independence assertions even when it faithfully represents the distribution.The paper assumes a perfect map exists for the distribution generating the data.
  • Markov blanket: The variable-selection step seeks a set guaranteed to contain the target’s Markov blanket when a perfect map exists.A distributional Markov blanket is a minimal conditioning set rendering the target independent of all remaining variables.
  • BIC structure learning: PGM-Explainer uses BIC for structure learning because a consistent score favors the perfect-map independence structure as sample size grows.BIC approximates the Bayesian score for sufficiently large data, balancing log-likelihood with model dimension.

D Proof of Theorem 1

The proof shows that every variable in the target’s Markov blanket is retained by the variable-selection procedure. Parent, child, and co-parent cases are handled through active paths and perfect-map dependence relations.

  • Markov-blanket coverage: In a perfect Bayesian-network map, every Markov-blanket variable is either a parent, a child, or another parent of one of the target’s children.The proof examines an arbitrary variable v′ in the target’s Markov blanket and splits the argument across these cases.
  • Parent and child cases: For parent and child cases, an active path connects v′ and the target, so perfect-map faithfulness implies v′ is included in S(t).Because S(t) is included in the union of selected-variable neighborhoods, v′ is retained by the procedure.
  • Co-parent case: For a child’s other parent v′, active paths connect v′ to the child and the child to t, placing v′ in the neighborhood S(v) of a variable v selected for t.Thus v′ belongs to the union of neighborhoods used by the variable-selection step.

E Proof of Theorem 2

The no-child proof reduces the target’s Markov blanket to its parents, then uses perfect-map dependence to show those parents are selected. The corresponding algorithms generate perturbed data, select dependent variables, and learn a Bayesian network with BIC.

  • Proof of Theorem 2: When the target has no child, its Markov blanket equals its parent set in the perfect Bayesian-network map.This removes the child and co-parent cases from the Markov-blanket characterization.
  • Proof of Theorem 2: Every parent has an active edge into the target, so perfect-map faithfulness ensures that parent is included in S(t).Therefore, each Markov-blanket variable is retained by the variable-selection procedure.
  • Algorithmic procedure: PGM-Explainer generates sampled input-output data from perturbed graphs, recording node perturbations and corresponding GNN predictions.The sampling procedure uses the target’s L-hop neighborhood, where L is the number of GNN layers.
  • Without no-child constraint: Without the no-child constraint, the method ranks variables by dependence with t, keeps the top M, and maximizes BIC over Bayesian-network structures.The resulting structure is returned as the explanation network.
  • With no-child constraint: With the no-child constraint, the method learns a structure over variables excluding t, adds t, prunes conditionally independent candidate parents, and directs retained edges into t.This construction explicitly enforces that the target has no child.

H Proof of Theorem 3

The proof of Theorem 3 compares candidate Bayesian networks using likelihood, independence assumptions, and BIC scores. In both cases, the assumed optimality of the returned network leads to a contradiction as the sample size grows.

  • First case: If the estimated network implies an independence unsupported by B∗, it is not an I-map of the true distribution and has lower log-likelihood.The proof uses this likelihood gap to show that the estimated network cannot be optimal.
  • Network reduction: The proof removes target node t and its related edges from both networks to compare the resulting Bayesian networks.The reduced network is denoted B′∗ for B∗, with analogous notation for the estimated network.
  • First case: As n →∞, empirical-distribution convergence makes the BIC score of B′∗ exceed that of the estimated reduced network, contradicting BIC maximization.The proof states scoreBIC(B′∗ : D′t) > scoreBIC(B̂′ : D′t).
  • Second case: If the estimated network contains all independence assumptions of B∗ but omits some, equal asymptotic likelihoods and greater parameter dimension again contradict BIC maximization.The parameter-dimension difference remains positive after removing the target node and the same set of edges.

I Parameters of synthetic dataset

Table 4 presents the parameters of the synthetic datasets used in the experiments.

  • Table 4 lists parameters for the synthetic datasets.
  • The synthetic-dataset parameters are presented in tabular form.
  • The table is titled “Parameters of synthetic datasets.”
Loading 2010.05788v1…