PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphSVX: Shapley Value Explanations for Graph Neural Networks

Alexandre Duval, Fragkiskos D. Malliaros

arXiv:2104.10482v2cs.LG

TL;DR

GNNs perform well on geometric data, but their graph-based representations are difficult for humans to understand, and existing explainers have shortcomings. The paper presents a unified framework and GraphSVX, a post hoc method that learns explanations from perturbed data using graph-extended Shapley values. It reports state-of-the-art performance across graph and node classification tasks, alongside theoretical and human-centric properties.

  • Problem

    GNNs are difficult for humans to understand, while existing explainers have limitations in graph-topology handling and human-centric comprehensibility.

    Source: §1 · pp. 1–2

  • Method

    GraphSVX learns a surrogate explanation from a perturbed dataset of binary node and feature masks and model predictions, producing graph-extended Shapley values.

    Source: §5 · p. 5

  • Results

    GraphSVX achieves state-of-the-art performance on various graph and node classification tasks, outperforming leading baselines on all but one task.

    Source: §6.1 · p. 9, §7 · p. 10

  • Takeaways & Limitations

    The Shapley-value construction gives explanations theoretical properties by definition, while extensions make them more human-centric.

    Source: §1 · p. 2

    The marginal-contribution interpretation assumes model linearity and feature independence.

    Source: §5.3 · p. 6

Abstract

from arXiv · show

Graph Neural Networks (GNNs) achieve significant performance for various learning tasks on geometric data due to the incorporation of graph structure into the learning of node representations, which renders their comprehension challenging. In this paper, we first propose a unified framework satisfied by most existing GNN explainers. Then, we introduce GraphSVX, a post hoc local model-agnostic explanation method specifically designed for GNNs. GraphSVX is a decomposition technique that captures the "fair" contribution of each feature and node towards the explained prediction by constructing a surrogate model on a perturbed dataset. It extends to graphs and ultimately provides as explanation the Shapley Values from game theory. Experiments on real-world and synthetic datasets demonstrate that GraphSVX achieves state-of-the-art performance compared to baseline models while presenting core theoretical and human-centric properties.

1 Introduction

GNNs model geometric data through graph structure but are difficult for humans to understand. Existing explainers have limitations in graph-topology handling, theoretical grounding, evaluation, and human-centricity; the paper proposes a unified framework and GraphSVX to address these gaps.

1 Introduction

  • GNNs encode relational information through message passing, but their complex functioning is opaque to humans.Understanding them matters for privacy, fairness, efficiency, and safety.Source: §1 · p. 1
  • Many existing explanation methods handle graph topology poorly, while proposed GNN extensions have limited performance, require model internals, and can suffer gradient saturation.Source: §1 · p. 1
  • Existing explainers often lack theoretical grounding, sophisticated evaluation, and attention to human-centric comprehensibility.The introduction also notes that many do not jointly consider node features and graph structure.Source: §1 · pp. 1–2
  • The paper proposes a unified framework and GraphSVX, which jointly captures node and feature contributions and computes graph-extended Shapley values.The authors evaluate it on real-world and synthetic node- and graph-classification tasks, reporting stronger explanation accuracy than baselines and desirable robustness or certainty.Source: §1 · p. 2

2 Related Work

The paper organizes GNN explainers into five categories and describes limitations across them. It positions GraphSVX as a bridge that combines local surrogate explanations with decomposition and can also provide model-level insights.

2 Related Work

  • The paper adopts five explainer categories: gradient-based, perturbation, decomposition, surrogate, and model-level methods.Source: §2 · p. 2
  • Decomposition methods allocate prediction scores using network weights but are not GNN-specific and may require model parameters or be sensitive to small input changes.Source: §2 · p. 2
  • Perturbation methods learn continuous importance masks but can introduce evidence, while surrogate approaches approximate a local GNN using features or topology, not both.Source: §2 · p. 2
  • GraphSVX learns a surrogate on perturbed data to decompose predictions across nodes and features, and can derive model-level insights by explaining node subsets.Source: §2 · p. 2
  • Good explanations are described as accurate, faithful, meaningful, robust, decomposable, representative, and human-centric, with selective, contrastive, and social qualities also emphasized.Source: §2 · p. 2

3 Preliminary Concepts and Background

The background establishes graph notation and message passing, then introduces Shapley values as fair average marginal contributions. It notes both their axiomatic basis and the computational need for sampling.

3 Preliminary Concepts and Background

  • A graph is represented by feature matrix X and adjacency matrix A, with N nodes and F features; the notation also distinguishes node and feature values.Source: §3 · p. 3

3.1 Graph Neural Networks

  • GNN layers propagate messages between nodes, aggregate neighborhood messages, and update node representations for downstream tasks.Source: §3.1 · p. 3

3.2 The Shapley value

  • A Shapley value averages a player's marginal contribution across possible coalitions, and the framework has been extended from games to machine-learning predictions.Source: §3.2 · p. 3
  • The Shapley value uniquely satisfies efficiency, dummy, symmetry, and additivity, but its coalition sum grows exponentially with feature count, motivating sampling approximations.Source: §3.2 · p. 3

4 A Unified Framework for GNN Explainers

The paper places existing GNN explainers in a shared pipeline whose components differ by method. GraphSVX is presented as a more comprehensive design that learns an explanation from perturbed inputs and model predictions.

4 A Unified Framework for GNN Explainers

  • The unified framework groups GNNExplainer, PGExplainer, GraphLIME, PGM-Explainer, XGNN, and GraphSVX, with differences centered on three pipeline blocks.Source: §4 · p. 3
  • Mask creates node, edge, or feature masks; Gen converts them with the original graph into a perturbed input, and Expl uses the resulting prediction to produce an explanation.The process repeats to form a dataset from which generator blocks learn; usually one block is optimized using new and original predictions.Source: §4 · pp. 3–4, Figure 1 · p. 4
  • GNNExplainer optimizes feature and edge masks by mutual information, whereas PGExplainer uses learned node representations and a reparameterization trick to optimize an edge mask.Source: §4 · p. 4
  • GraphLIME uses neighborhood masks and an HSIC Lasso surrogate, while PGM-Explainer learns a Bayesian network from masked-node predictions.Source: §4 · p. 4
  • XGNN iteratively generates graphs with reinforcement learning for model-level explanations, while GraphSVX is designed to combine the framework's generators and improve performance and explanation properties.Source: §4 · p. 5

5 Proposed Method

GraphSVX explains GNN predictions by learning a surrogate on perturbed graph inputs and assigning Shapley-value contributions to node features and graph nodes. Its design combines a graph-specific decomposition with efficient sampling and several explanation properties and extensions.

5 Proposed Method

  • GraphSVX learns a surrogate on a perturbed dataset to jointly explain graph structure and node features for an instance.The method is post hoc and model-agnostic, and its explanation decomposes the prediction into Shapley values.Source: §5 · p. 5

5.1 Mask and graph generators

  • Binary masks select features and neighboring nodes; omitted features take dataset-mean values, while excluded nodes are isolated.For multi-hop neighbors, the generator can restore a shortest path to the explained node while setting intermediate-node features to mean values.Source: §5.1 · pp. 5–6

5.2 Explanation generator

  • A weighted linear regression surrogate is fitted to perturbed predictions, and its coefficients estimate each node's or feature's influence.The kernel gives greater weight to sampled coalitions with few or many selected variables.Source: §5.2 · p. 6

5.3 Decomposition model

  • Under the stated linearity and feature-independence assumptions, the explanation model computes graph-extended Shapley values.Theorem 1 states that the specified optimization has a unique solution whose parameters compute those values.Source: §5.3 · pp. 6–7

5.4 Efficient approximation specific to GNNs

  • The approximation discards nodes beyond the GNN's k-hop neighborhood and features within a specified confidence interval around their means.These variables receive zero importance under the stated dummy-axiom rationale.Source: §5.4 · p. 7
  • Separate node and feature mask sampling reduces the stated complexity from O(2^(B+D)) to O(2^B + 2^D), while still modeling them jointly.The paper reports empirically identical explanations with fewer samples for this strategy.Source: §5.4 · p. 7
  • GraphSVX's sampling prioritizes coalitions with few or many selected players and favors unseen players when the sample budget is limited.It increases coalition size after sampling all coalitions of the current size.Source: §5.4 · p. 7

5.5 Desirable properties of explanations

  • The explanation is described as unique, consistent, stable, truthful, and robust to noise.Extensions cover contrastive explanations, explanations for node subsets, global feature importance, and graph classification.Source: §5.5 · pp. 7–8

6 Experimental Evaluation

The evaluation tests GraphSVX on synthetic and real-world node and graph classification tasks, using ground-truth explanations where available and noisy-variable filtering otherwise. It reports strong baseline comparisons on the ground-truth tasks and near-zero selection of noisy features on Cora and PubMed.

6.1 Synthetic and real datasets with ground truth

  • Ground-truth tests use motif-based synthetic node and graph tasks plus MUTAG, where motif membership or mutagenic groups provide explanation targets.Explainer accuracy is measured on top-k explanations, with k set to the ground-truth dimension.Source: §6.1 · p. 8
  • GraphSVX identifies essential graph structure and outperforms leading baselines on all but one ground-truth task; edge explainers capture slightly more information on MUTAG.For BA-Community, it also identifies important node features with 100% accuracy.Source: Table 1 · p. 9, §6.1 · p. 9

6.2 Real-world datasets without ground truth

  • The real-world noise evaluation adds synthetic features and neighbors, then checks whether explainers include these variables despite the trained GNN not using them.The feature experiment adds 20% noisy features and evaluates explanations for 50 test samples.Source: §6.2 · pp. 9–10
  • On Cora and PubMed, GraphSVX selects close to zero noisy features across GNNs and datasets, generally fewer than existing baselines.The paper presents this result as evidence of robustness to noise.Source: §6.2 · p. 10, Figure 2 · p. 10
  • For noisy-node explanations, GraphSVX outperforms the baselines and includes nearly no noisy nodes, while GNNExplainer performs almost as well in several settings.The comparison is reported for the Cora and PubMed evaluation.Source: §6.2 · p. 10

7 Conclusion

The paper concludes that GraphSVX combines a unified view of GNN explainers with a graph-extended Shapley decomposition. Its evaluation reports strong task performance and desirable theoretical and human-centric properties.

7 Conclusion

  • The conclusion presents GraphSVX as a perturbed-data decomposition method that explains graph topology and node features with extended Shapley values.The paper reports state-of-the-art performance across graph and node classification tasks, alongside desirable theoretical and human-centric properties.Source: §7 · p. 10

C GraphSVX

  • The mask generator builds weighted binary-mask samples by studying features with no selected nodes and nodes with all features included.The appendix explains this separation as a way to capture feature and neighbor influence in their respective settings.Source: C GraphSVX · p. 14
  • SmarterSeparate favors coalitions with small or large size, lowers selection weights for already sampled variables, and reserves 10% of samples for random coalitions.When the full set of coalitions at a given size will not fit, it samples iteratively to fill the budget.Source: C GraphSVX · p. 16

D Proof of Theorem 1

The proof identifies GraphSVX’s weighted-regression coefficients with extended Shapley values for graphs. It derives the regression matrix’s form and notes that exact computation requires all coalitions.

D Proof of Theorem 1

  • The coalition matrix Z represents node-and-feature coalitions, while the regression responses y are GNN outputs for generated instances.The fitted coefficients are used as the explanation; each player is a node or feature.Source: D Proof of Theorem 1 · p. 16
  • Assigning the empty and complete coalitions a large finite weight c gives Z⊤WZ the form M I + cJ.The proof then studies the inverse as c tends to infinity.Source: D Proof of Theorem 1 · pp. 16–17
  • The proof assumes model linearity and feature independence when identifying the regression coefficient with the graph Shapley-value expression.The coefficient is derived from the weighted least-squares fit over coalition predictions.Source: D Proof of Theorem 1 · p. 18
  • GraphSVX’s weighted-regression coefficients yield the extended Shapley values for graphs, with exact computation requiring all 2^M coalitions.The paper resorts to approximation because evaluating every coalition is computationally expensive.Source: D Proof of Theorem 1 · pp. 16, 18

E Evaluation

The evaluation ran on a Linux machine with an Nvidia Tesla V100 GPU, using CUDA 11.1 and PyTorch 1.6.0.

E Evaluation

  • Experiments ran on Linux with an Nvidia Tesla V100-PCIE-32GB GPU and driver version 455.32.00.The reported hardware environment includes the GPU model and driver version.Source: E Evaluation · p. 18
  • The evaluation environment used CUDA 11.1.This is the CUDA version specified for the experiments.Source: E Evaluation · p. 18
  • GraphSVX was implemented using PyTorch 1.6.0.The paper reports this implementation version for the evaluation.Source: E Evaluation · p. 18

E.1 Synthetic and real datasets with ground truth

The evaluation uses four node-classification datasets and two graph-classification datasets with ground truth, alongside a shared GNN training setup. The datasets include synthetic motif-based cases and MUTAG, a real-life molecular dataset.

E.1 Synthetic and real datasets with ground truth

  • The benchmark suite comprises BA-Shapes, BA-Community, Tree-Cycles, and Tree-Grids for node classification, plus BA-2motifs and MUTAG for graph classification.The datasets are presented as having ground-truth statistics.Source: §E.1 · p. 18, Table 2 · p. 19
  • BA-Shapes assigns labels by structural role in house motifs, while BA-Community adds community membership and yields eight classes.BA-Shapes has constant node features; BA-Community samples features from two Gaussian distributions.Source: §E.1 · p. 19
  • Tree-Cycles and Tree-Grids attach cycle or 3-by-3 grid motifs to a balanced binary-tree base graph.BA-2motifs labels graphs by house versus five-node-cycle motifs; MUTAG is a real-life molecular graph dataset.Source: §E.1 · p. 19
  • A shared three-layer GNN architecture was trained for 1,000 epochs with Adam and an 80/10/10 train/validation/test split.The graph-classification architecture adds max pooling before the fully connected classification layer.Source: §E.1 · p. 19

E.2 Real-life datasets without ground truth

This section evaluates GraphSVX on Cora and PubMed without ground-truth explanations by adding noisy features or nodes and checking whether they appear in explanations. It reports the distribution of noisy variables selected across 50 test predictions.

E.2 Real-life datasets without ground truth

  • Cora and PubMed were evaluated in their original forms and after adding noisy features or nodes, yielding six datasets in total.Cora is a seven-category document-classification citation graph; PubMed is a three-class publication dataset.Source: §E.2 · p. 20
  • Noisy features were added to all nodes, while noisy-node variants added nodes connected to existing nodes with low probabilities.Cora received 287 binary noisy features sampled with Bernoulli(p), p = 0.013, and 541 noisy nodes; PubMed received 100 continuous noisy features and noisy nodes.Source: §E.2 · p. 20
  • Results are summarized with KDE plots of noisy-variable counts in top-k explanations across 50 explained test predictions using a trained GAT.The top-k setting uses k equal to the ground-truth dimension, as described for the evaluation protocol.Source: §E.2 · p. 21

E.3 Ablation study and hyperparameters tuning

The ablations examine sampling, coalition order, candidate selection, and other GraphSVX design choices, while the following sections characterize explanation properties from machine-learning and human-centric perspectives.

E.3 Ablation study and hyperparameters tuning

  • Reducing candidates from F + N to D + B removes features and nodes occupying 5% and 8% of the explainable part, respectively; indirect node effects improve Tree-Cycles and Tree-Grid performance by 19% on average.Higher-order relations matter more on those datasets, while adding indirect effects has no performance effect on BA-Shapes or BA-Community.Source: §E.3 · p. 21
  • 100% versus 65% accuracy for essential features on BA-Community supports the subgraph-perspective feature extension’s greater ability to capture global feature importance.The extension is also useful for spotting noisy features on Cora and PubMed when noise is added across nodes.Source: §E.3 · p. 21
  • WLS and WLR yield equivalent results, WLR is slightly better, and weighted Lasso is not especially useful on small, sparse synthetic datasets.Using high weights for masks 1 and 0 to satisfy the efficiency axiom is unnecessary; identical explanations are usually reached without sampling those coalitions.Source: §E.3 · p. 21
  • SmarterSeparate outperforms sampling baselines on all tasks; the ablation attributes gains to smart mask sampling, separating node and feature coalitions, and smart space allocation.The table reports improvements through Random, Smart, SmartSeparate, and SmarterSeparate.Source: §E.3 · p. 21, Table 6 · p. 22
  • For simple datasets, S = 1 and few samples suffice, while Tree-Cycles and Tree-Grid reach optimal performance with higher-order coalitions at S = 4.On Tree-Cycles, default GraphSVX scores 0.83 with 500 samples, 0.95 with 1,500, and 0.88 with 3,000; All yields 0.87.Source: §E.3 · p. 22
  • GraphSVX is slower than PGExplainer but matches GNNExplainer through efficient approximation, and a 2-hop approximation is faster than GNNExplainer while maintaining state-of-the-art performance.The runtime comparison is especially favorable on relatively sparse data such as BA-Shapes or Tree-Cycles.Source: §E.3 · p. 22, Table 7 · p. 22, Table 8 · p. 22

F.1 Desirable properties of explanations from a machine learning perspective

  • Machine-learning explanation properties include accuracy and fidelity, robustness, certainty or decomposability, meaningfulness, representativeness, and comprehensibility.Robustness concerns stability across similar models or instances; certainty asks whether an explanation reflects the model’s confidence.Source: §F.1 · p. 23

F.2 Human-centric explanations

  • Human-centric explanations are contrastive, selective, and social: they compare predictions, focus on key causes, and respond to the receiver’s context.The passages describe people as typically seeking one or two key causes rather than a complete list.Source: §F.2 · p. 23

F.3 Explainers’ properties

GraphSVX satisfies the paper’s evaluated explainer properties while achieving state-of-the-art results on all but one task. Its explanations are presented as fair feature and node contributions, with extensions for broader and human-adapted use.

F.3 Explainers’ properties

  • GraphSVX achieves state-of-the-art results on all but one task, and its local explanation model reaches R2 > 0.90 for every task.The paper describes this as high accuracy and fidelity to the GNN model locally.Source: §F.3 · p. 23
  • GraphSVX is the only fairly distributed method, and its attributions sum to fv(X, A) for every prediction.The paper says this is naturally enforced by the high weight given to null and full coalitions.Source: §F.3 · p. 24
  • GraphSVX and GraphLIME are the only meaningful methods; motif nodes receive 85% of the explainable part on Tree-Grid and Tree-Cycle, versus 20% on BA-Community.The paper says node features and relations to other motifs are also essential for prediction on BA-Community.Source: §F.3 · p. 24
  • GraphSVX can explain subsets of nodes together without aggregating local explanations and assess feature importance in the explained node’s subgraph.The paper contrasts these capabilities with XGNN’s model-level explanations and PGExplainer’s collective and inductive explanations.Source: §F.3 · p. 24
  • Explanations are stable across synthetic datasets, with variance in accuracy below 0.1; GCN and GAT explanations on Cora have an IOU of 0.76.The comparison uses the top 20% or top 10 most important features and nodes; the paper notes model differences limit a better consistency result.Source: §F.3 · p. 24
  • GraphSVX meets all three human-centric criteria—selective, contrastive, and social—with sparse explanations, instance comparisons, audience-adapted outputs, and adjustable node/feature importance.The paper describes expert-oriented complete explanations and selective visualisations for non-experts.Source: Table 9 · p. 23, §F.3 · p. 24
Loading 2104.10482v2…