Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks

1 INTRODUCTION

• The paper focuses on post-hoc, model-agnostic explanations for trained GNNs that attribute predictions to features, neighboring nodes, or both.The authors motivate this focus by the opacity of GNNs that learn through neighborhood aggregation.Source: §1 · p. 1
• The paper formalizes validity, sparsity, and stability as desired properties because existing approaches may not satisfy them.Validity preserves the prediction using only selected inputs; stability requires the prediction to remain unaffected by perturbations to unselected inputs.Source: §1 · pp. 1–2
• RDT-Fidelity combines validity, sparsity, and stability using rate-distortion principles, and ZORRO uses a greedy combinatorial procedure to optimize it.The optimization problem is NP-hard.Source: §1 · p. 2
• The study evaluates explanations across several regimes, three real-world datasets, and four GNN architectures, using multiple existing evaluation measures.Measures include validity, sparsity, RDT-Fidelity, GNNExplainer’s regime, the faithfulness measure in, and ROAR [10].Source: §1 · p. 2
• ZORRO outperforms all baselines across different evaluation regimes on real-world and synthetic datasets.The authors also report insights about feature relevance, local homophily, and the possibility of disjoint explanations.Source: §1 · p. 2

2 RELATED WORK

• Graph representation learning encodes graph structure, with or without node features, into low-dimensional vectors through unsupervised or semi-supervised learning.Semi-supervised approaches can use neighborhood aggregation and task-based objectives.Source: §2 · p. 2

2.1 Explainability in Machine Learning.

• Instance-wise feature selection seeks sufficient feature subsets, but applying these approaches directly to graph models is infeasible because explanations must account for associations among nodes and features.Post-hoc explainability methods include model-agnostic or model-specific feature attribution.Source: §2.1 · p. 2

2.2 Explainability in GNNs.

• GNN explainers include soft masks, Shapley-based methods, surrogate models, and gradients; most use soft masks, while several alternatives omit feature-based explanations or require model access.PGMExplainer focuses on relevant neighborhood nodes, whereas PGExplainer is not model-agnostic and does not generate feature-based explanations.Source: §2.2 · p. 3

3.1 Background on GNNs

• GNN layers aggregate neighboring node features and transform the result, using the final representation to predict a node’s label.For an L-layer GNN, the query node’s L-hop neighborhood forms its computational graph.Source: §3.1 · p. 3

3.2 Defining GNN Explanation, Validity and Sparsity

• An explanation selects nodes and features from the query node’s computational graph; validity preserves the original prediction, while sparsity measures its encoding size.The section also relates sparsity to explanation entropy and gives an upper bound of log(|M|).Source: §3.2 · pp. 3–4

3.3 Limitations of Validity and Sparsity

• Validity and sparsity under one baseline do not ensure an explanation remains valid across other assignments to unselected features.The section defines stability using variation in validity across those assignments and introduces RDT-Fidelity to account for stability.Source: §3.3 · p. 4

4 RATE-DISTORTION THEORY AND RDT-FIDELITY

• Rate-distortion theory motivates explanations that minimize retained input while preserving the model’s prediction when the remaining input is randomized.The explanation is a subset of nodes and features in the query node’s computational graph, and RDT-Fidelity measures expected agreement over assignments to its complement.Source: §4 · pp. 4–5

4.1 RDT-Fidelity

• RDT-Fidelity is the expected validity of perturbed inputs that retain selected values and randomize the rest; high values imply stability under the stated theorem.For RDT-Fidelity above 0.5, stability increases with RDT-Fidelity and reaches 1 when RDT-Fidelity reaches 1, so stability is not reported separately in experiments.Source: §4.1 · p. 5

5 MAXIMIZING RDT-FIDELITY

• ZORRO starts with an empty explanation and iteratively adds the node or feature that maximizes RDT-Fidelity until it reaches τ.At each step it evaluates the top K remaining node and feature candidates, ranked by their RDT-Fidelity values.Source: §5 · pp. 5–6
• A variant finds multiple disjoint explanations by removing previously selected nodes or features before searching again.It stops when the remaining components cannot reach the target RDT-Fidelity.Source: §5 · p. 5
• To compute RDT-Fidelity, ZORRO preserves selected feature values and replaces other values with random draws from their dataset columns across sampled inputs.It returns the average validity across these samples.Source: §5 · p. 6
• For any retrieved explanation and τ ≥ 0.5, ZORRO’s stability score is at least 1 / (1 + τ(1 − τ)).The theorem also guarantees RDT-Fidelity of at least τ and runtime independent of graph size.Source: §5 · p. 6

6 EXPERIMENTAL SETUP

• The study uses three evaluation regimes—real-world graphs without known ground truth, remove-and-retrain, and synthetic graphs with known ground truth—while noting that each regime relies on simplifying assumptions.The authors identify the ground-truth dilemma as a challenge and later discuss threats to result validity.Source: §6 · p. 6

6.1 Evaluation without Ground Truth

• Without ground truth, the study compares validity, sparsity, and RDT-Fidelity on Cora, CiteSeer, and PubMed across four two-layer GNN architectures and 300 randomly selected query nodes.For soft edge-mask methods, edge-mask values are distributed equally to their endpoint nodes to construct node masks.Source: §6.1 · p. 6

6.2 Remove and Retrain

• The remove-and-retrain regime removes features ranked important by each explainer, retrains a network, and measures the change in accuracy.Unlike output-only interventions, this is a global approach that removes a fixed set of features and retrains the model.Source: §6.2 · p. 7

6.3 Evaluation with Ground Truth

• The synthetic BA-Community dataset supplies known explanations: for house-node class assignments, the corresponding five-node house motif is treated as ground truth.The graph combines a Barabási–Albert base graph with an attached five-node house motif.Source: §6.3 · p. 7

6.3.1 Metrics

• For synthetic explanations, accuracy measures correctly classified nodes, precision measures returned nodes that belong to the explanation, and faithfulness is Kendall’s tau rank correlation between explanation performance and model test accuracy across epochs.Accuracy alone can be misleading when the explanation set is small relative to the computational graph.Source: §6.3.1 · p. 7

6.4 Baselines and Competitors

• The baselines span soft masks, surrogate hard masks, Shapley-based subgraphs, gradient methods, and an empty explanation; SubgraphX is evaluated only on the small synthetic dataset because of its long runtime.ZORRO explanations use thresholds τ = .85 and τ = .98 with K = 10; RDT-Fidelity is calculated from 100 samples.Source: §6.4 · p. 7

7.1 Evaluation with Real-World Data

• On real-world data, gradient-based methods have low validity and RDT-Fidelity, while ZORRO outperforms existing baselines on both measures and its greedy procedure reaches near-optimal values.The empty baseline has validity in the same range, 0.11–0.50, as gradient-based methods.Source: §7.1 · p. 8
• ZORRO produces sparser explanations than soft-masking approaches, and its node masks are sparser than PGM’s except for GIN.Higher RDT-Fidelity and validity accompany the less sparse ZORRO threshold variant τ = 0.85 compared with τ = 0.98.Source: §7.1 · pp. 8–9
• For τ = 0.98, ZORRO, relative to the best-performing baseline for each metric, model, and dataset, reduced effective node and feature explanation size by 72% and 94%, and increased RDT-Fidelity by 20% and validity by 11%.Source: §7.1 · p. 9

7.2 Evaluation with Remove and Retraining

• With only the top 10 ZORRO (τ = .98) features, retrained GCN accuracy is 0.72, compared with 0.79 using all 1433 features.Using 100 ZORRO features causes a performance drop of ∆ < 0.01; PGM could not be evaluated because it does not retrieve feature masks.Source: §7.2 · p. 9, Figure 3 · p. 9

7.3 Evaluation with Ground-Truth

• In the synthetic evaluation, gradient methods’ accuracy advantage reflects soft-mask discretization using the known ground-truth size, whereas ZORRO’s hard masks do not use that size.PGE has the lowest precision and accuracy; SubgraphX has very high runtime.Source: §7.3 · pp. 9–10
• ZORRO outperforms baselines in synthetic precision and faithfulness, while gradient-based methods achieve the highest accuracy.The authors caution that synthetic results can differ from real-world results and report that ZORRO is robust across the tested models, data, and evaluation regimes.Source: §7.3 · pp. 9–10

8 UTILITY OF EXPLANATIONS

• The analysis compares a node’s true homophily, based on neighbors’ actual labels, with predicted homophily, based on neighbors’ predicted labels.Homophily is the fraction of selected neighbors sharing the node’s label.Source: §8 · p. 10

8.1 Wrong Predictions Despite High Homophily

• Some incorrectly predicted PubMed nodes have true homophily near 1 but low predicted homophily, indicating that their influential explanation nodes do not share their labels.The authors suggest feature information may be misaligned with the structural signal in these cases.Source: §8.1 · p. 10

8.2 Incorrect High Homophily Predictions

• For GIN and APPNP, some incorrectly predicted nodes have both true and predicted homophily near 1, suggesting the model selects the right nodes but assigns the group the wrong class.Source: §8.2 · p. 10

8.3 Influence of Nodes with Low Homophily

• APPNP has fewer low-true/high-predicted-homophily cases than GCN, indicating fewer mistakes in assigning labels to neighbors of low-homophily nodes.The authors note that these nodes can be further studied in relation to degree and features.Source: §8.3 · p. 10

• The paper frames validity, sparsity, and stability as key explanation properties, and proposes a combinatorial procedure that retrieves sparse binary masks while optimizing RDT-Fidelity.Source: §9 · p. 10
• Figure 4 depicts the joint distribution of true and predicted homophily for nodes selected in ZORRO explanations on PubMed, with contours distinguishing correct from incorrect predictions.Source: Figure 4 · p. 11
• ZORRO’s experiments on synthetic and real-world datasets show improvements in RDT-Fidelity and measures used by previous work.Source: §9 · p. 11

APPENDIX A ADDITIONAL DETAILS FOR THE EXPERIMENTS

• The experiments use citation-network datasets and Amazon Computers, with specified training settings and a synthetic dataset built from house motifs attached to BA graphs.The synthetic data uses two communities, feature values drawn from normal distributions, and a three-layer GCN; GNNExplainer’s edge masks are converted to hard node masks by adding endpoints of highly ranked edges.Source: Appendix A · p. 13
• SubgraphX takes more than one hour per node on average on the small synthetic dataset, while the other methods are reported as usable in real-world post-hoc scenarios.ZORRO at τ = 0.85 is faster than at τ = 0.98, and PGM takes around twice as long as ZORRO at τ = 0.98.Source: Appendix A · p. 13
• At epoch 200, the model has learned to distinguish the two communities but still cannot identify motif nodes; most explainers’ precision peak at that epoch is described as surprising.The appendix reports accuracy for both the full test set and motif nodes across selected epochs.Source: Appendix A · pp. 13–14, Figure 5 · p. 14, Table 7 · p. 14

APPENDIX B ALGORITHMIC DETAILS

• Initialization ranks nodes and features in a maximal setting of the other element type, then selects whichever yields the higher value as the first explanation element.The next selected element must be of the other type, and initialization is repeated for each explanation.Source: Appendix B · p. 14
• Iterative search evaluates only the top K remaining nodes and features ranked using initialization, reducing the cost of evaluating all remaining elements.Evaluating all elements showed no performance gain or sometimes worse performance; adding one element may not increase fidelity.Source: Appendix B · pp. 14–15

B.1 Multiple Explanations using ZORRO

• The multiple-explanation variant recursively checks complementary node or feature sets to find further high-fidelity explanations with disjoint selected elements.Its recursive calls use the remaining node set or feature set to enforce disjointness.Source: Analysing Multiplicity of Explanations · p. 15, §B.1 · p. 15

Analysing Multiplicity of Explanations

• About 50% of the 300 studied nodes have 2 to 10 disjoint explanations of fidelity at least τ across all evaluated GNNs.The recursive variant finds multiple disjoint explanations that constitute separate evidence for the same decision.Source: Analysing Multiplicity of Explanations · p. 15

B.2 Proof of Theorem 2

• ZORRO’s runtime complexity is given as O(t · max(|Vn| + |F|)), where t is the time for one forward pass on perturbed data.Source: §B.2 · p. 15
• The global feature distribution supplies plausible noisy values without bias toward fixed values, and multiple noisy instantiations test whether irrelevant components matter.The text cautions that setting irrelevant components to zero may be problematic when zero is disallowed, meaningful, or interacts with pooling such as minpool.Source: §B.2 · p. 15

C.1 Variations of Number of Samples

• On Cora with GCN, explanations using fewer than 100 samples were denser, while increasing from 10 to 50 and then to 100 samples yielded successive sparsification gains.At 150 samples, explanations were denser than the 100-sample results for τ = 0.85 but sparser for τ = 0.98.Source: §C.1 · p. 16, Table 8 · p. 16

C.2 Further Variation of the RDT-Fidelity Threshold

• Higher RDT-Fidelity thresholds require more selected elements, producing denser node and feature masks.Source: §C.2 · p. 16, Table 9 · p. 16

C.3 Further Evaluation Metrics

• The four additional fidelity variants require hard masks, so soft-mask methods need an extra transformation before evaluation.The study considers top-percentage selection and a normalization-and-threshold transformation.Source: §C.3 · p. 16, §C.3.1 · p. 16, §C.3.2 · p. 16

C.3.1 Definition and Discussion of Additional Metrics

• Fidelity+acc and Fidelity+prob can give maximum scores to the full-input trivial explanation, while Fidelity-acc and Fidelity-prob assume a complete explanation that may not exist.Source: §C.3.1 · p. 16

RDT-Fidelity

• Soft-to-hard transformations trade sparsity against explanation performance, may bias evaluation, and cannot balance additions across different masks.Source: RDT-Fidelity · p. 19

• ZORRO retrieves by far the sparsest hard-mask explanations; the next sparsest approaches are PGM and PGE.The normalizing-and-threshold transformation can yield very dense GNNExplainer masks because its soft masks resemble a normal distribution.Source: §C.3.3 · p. 19
• ZORRO outperforms all baselines on RDT-Fidelity except GNNExplainer with NT, which selects almost all input elements, and is inferior on validity in only one case.Source: §C.3.3 · p. 19
• For fidelity-prob, ZORRO achieves among the lowest scores, and accounting for its sparser masks, the authors report it outperforms the other baselines.ZORRO at τ = 0.98 scores higher than τ = 0.85 on fidelity+acc and fidelity+prob in all cases; results for fidelity+prob vary across datasets and GNN models.Source: §C.3.3 · p. 19
• The additional-metric experiments support the conclusion that ZORRO retrieves sparse explanations of high quality.Source: §C.3.3 · p. 19

C.4 Experiment on Amazon Computers

• With average degree similar, increasing the overall dataset node count does not affect ZORRO's runtime for retrieving a node explanation, even though Amazon's computational graph is an order of magnitude larger than citation graphs.Amazon Computers is denser than the citation graphs.Source: §C.4 · p. 19
• PGM and PGE stay sparse on Amazon Computers but usually have low RDT-Fidelity and validity; Grad and GradInput also score low on both, while GNNExplainer's low RDT-Fidelity indicates instability.GNNExplainer has high validity for GCN, GAT, and APPNP, despite its low RDT-Fidelity.Source: §C.4 · p. 19
• On Amazon Computers, ZORRO is sparser than GNNExplainer, Grad, and GradInput and has very high RDT-Fidelity, while its validity varies across GNNs.Validity is high for GCN and APPNP; for GIN, ZORRO's scores of 0.45 and 0.48 are the highest observed, and for GAT its validity is inferior only to GNNExplainer.Source: §C.4 · p. 19, Table 12 · p. 20

THE SYNTHETIC DATASET

• In the synthetic examples, ZORRO selects fewer than five nodes; τ=0.98 selects more than τ=0.85, and its selections match the ground-truth house only for the correctly classified node.The ground-truth explanation contains five nodes.Source: THE SYNTHETIC DATASET · p. 20
• Figure 7 shows Grad retrieving nearly perfect explanations at epoch 1, while Figure 8 illustrates that explainers disagree about correct and false predictions.GNNExplainer and SubgraphX retrieve similar masks for both nodes, including some ground-truth and community nodes.Source: THE SYNTHETIC DATASET · p. 19, Figure 7 · p. 21, Figure 8 · p. 21