Evaluating Explainability for Graph Neural Networks

In plain words

Explanation tools for graph neural networks (GNNs) say which parts of a graph led the model to its answer. To tell whether such a tool is right, you need graphs where the correct answer is known in advance. Real datasets rarely provide that, so people have been checking explanations on a handful of graphs, and those graphs have their own quirks.

This paper builds a generator of artificial graphs. It plants small known shapes, such as houses or triangles, into a larger random network. The label of each node depends on how many of these shapes sit next to it, so the correct explanation is known by construction. The generator can also make graphs where the features are mostly uninformative, where the neighbours tend to be unlike the node, or where a protected attribute is linked to the label.

The authors put this generator and some real molecular and credit graphs into a Python library called GraphXAI. The library also includes explainers and scoring functions. They use it to compare eight explainers and report that the best one changes with the question asked, and that none of them handles every case well.

TL;DR

• ShapeGGen generates graphs with planted motifs and exact ground-truth masks for node, node-feature and edge explanations § Methods.
• GraphXAI bundles these graphs, several real datasets, eight explainers and metrics for accuracy (GEA), faithfulness (GEF), stability (GES) and fairness (GECF, GEGF) § Results.
• Author-reported: SubgraphX scores best on accuracy and faithfulness for node masks on the base graph, while PGExplainer scores best on stability and counterfactual fairness tab. 1.
• Before you rely on the fairness numbers or the exact metric definitions, read Pitfalls: several details in the released code differ from the paper.

Problem

Post hoc explanations of GNN predictions are hard to score, because most graph benchmarks lack reliable ground truth. Earlier work used a few real or synthetic graphs with few explanations § Introduction. The authors say that several such ground truths can be recovered by trivial baselines, that some graphs have many equally valid explanations, and that a model may not use the planted explanation at all § Introduction. A benchmark needs ground truth that matches the model's actual behaviour, and it should cover different graph types such as homophilic and heterophilic graphs, small and large explanations, and fair and unfair ones § Introduction § Methods.

Method

Generator (ShapeGGen). The input is a motif S, a number of starting subgraphs N_s, a connection probability p, an expected subgraph size n_s, a number of classes K, feature settings, a homophily coefficient eta and the GNN depth L § Methods: ShapeGGen dataset generator. The output is a graph, a node-feature matrix and three ground-truth masks per node.

1. Structure. Each of the N_s subgraphs starts from a copy of the motif. Its size grows by n' extra nodes, where n' is Poisson with mean n_s minus the motif size. Each new node attaches to an existing node with probability proportional to that node's degree (preferential attachment) § Methods: Generating graph structure alg. 2.
2. Joining subgraphs. Candidate edges between pairs of subgraphs are added one at a time, drawn in proportion to the degrees of their endpoints. An edge is undone if any node would then have f(v) > K-1 in eq. 1 terms, that is, more than K motifs in its 1-hop neighbourhood alg. 2. The output is the largest connected component.
3. Labels. A node's label is the number of distinct motifs in its 1-hop neighbourhood, minus one eq. 1 § Methods: Generating labels for prediction. With K = 2, each node sees one or two motifs.
4. Node features. Informative features are drawn around K times c_f cluster centres placed on a hypercube whose size is set by s_f. The remaining n_f minus n_i features are Gaussian noise. A protected feature is set to the node's label and flipped with probability phi alg. 1 [§ Methods: Generating node feature vectors].
5. Homophily. The redundant (non-informative) feature dimensions are optimised so that connected nodes with the same label become more similar and other pairs less similar, scaled by eta. eta > 0 gives homophily and eta < 0 gives heterophily alg. 3 § Methods: Generating node feature vectors.
6. Ground truth. For each node v, the L-hop enclosing subgraph is taken. The node mask is 1 for nodes that lie in a motif. The feature mask is 1 for informative features. The edge mask is 1 for edges whose two endpoints both lie in the motif or at v eq. 2 alg. 1 § Methods: Generating ground-truth explanations.

Key equations:

f(v) = \sum_{S_i \in \mathbf{S}} \mathbb{1}_{V_{S_i}}(\mathcal{N}_v) - 1 eq. 1

\mathbb{1}_{\mathcal{E}_{S_v}}(e) = \begin{cases} 0 & \text{if } v_i \notin (V_{S_v} \cup \{v\}) \lor v_j \notin (V_{S_v} \cup \{v\}) \\ 1 & \text{if } v_i \in (V_{S_v} \cup \{v\}) \land v_j \in (V_{S_v} \cup \{v\}) \end{cases} eq. 2

Explanation masks and metrics. An explainer returns a mask over nodes, node features or edges. Masks are scored against the ground truth as follows.

• GEA, accuracy: Jaccard index between predicted and ground-truth masks eq. 3. When several ground truths exist, take the maximum over them eq. 4 § Results: Graph explanation accuracy.
• GEF, faithfulness: keep the top-k attributes, compare the GNN output on the masked input with the original, and report 1 minus exp(minus KL) eq. 5 § Results: Graph explanation faithfulness.
• GES, stability: cosine distance between masks of a graph and its perturbed copies, maximised over a ball in which the model output stays the same eq. 6 § Results: Graph explanation stability.
• GECF, counterfactual fairness mismatch: cosine distance between masks for a graph and its counterfactual with the protected feature changed eq. 7 § Results: Counterfactual fairness mismatch.
• GEGF, group fairness mismatch: absolute gap in statistical parity between predictions on all inputs and on the explanation-restricted inputs eq. 8 § Results: Group fairness mismatch.

Key equations for the metrics:

\mathrm{JAC}(M^g, M^p) = \frac{TP}{TP + FP + FN} eq. 3

\mathrm{GEA}(\zeta, M^p) = \max_{M^g \in \zeta} \mathrm{JAC}(M^g, M^p) eq. 4

\mathrm{GEF}(f, S_u, S_u') = 1 - \exp(-\mathrm{KL}(f(S_u) \,\|\, f(S_u'))) eq. 5

\mathrm{GES}(M^p_{S_u}, M^p_{S_u'}) = \max_{S_{u'} \in \mathcal{B}(S_u)} D(M^p_{S_u}, M^p_{S_{u'}}) eq. 6

\mathrm{GECF}(M^p, M^p_s) = D(M^p, M^p_s) eq. 7

\mathrm{GEGF}(\hat{y}_{\mathcal{K}}, \hat{y}^{E_u}_{\mathcal{K}}) = |\mathrm{SP}(\hat{y}_{\mathcal{K}}) - \mathrm{SP}(\hat{y}^{E_u}_{\mathcal{K}})| eq. 8

Here D is cosine distance § Results: Graph explanation stability, and the KL direction is as printed in eq. 5.

ShapeGGen algorithms, written in Python-like form. Names are ours.

# ShapeGGen overview  [alg. 1]
# Input:  motif, num_subgraphs, p, n_s, K, n_f, n_i, s_f, c_f, phi, eta, L
# Output: graph, features, node_masks, edge_masks

def shapeggen(motif, num_subgraphs, p, n_s, K, n_f, n_i, s_f, c_f,
              phi, eta, L):
    # Build the structure and the planted motifs  [alg. 2]
    graph = structure(motif, num_subgraphs, p, n_s, K)
    # Label = number of motifs in the 1-hop neighbourhood, minus 1  [eq. 1]
    labels = [motifs_in_one_hop(graph, v) - 1 for v in graph.nodes]
    # Informative, noise and protected features  [alg. 1]
    features, informative_mask = node_features(
        graph.nodes, labels, K, n_f, n_i, s_f, c_f, phi)
    # Shape the homophily of the non-informative dimensions  [alg. 3]
    features = optimize_homophily(graph, features, labels, eta)
    # Ground-truth masks over each node's L-hop enclosing subgraph  [eq. 2]
    node_masks, edge_masks = ground_truth(graph, L)
    return graph, features, node_masks, edge_masks

# Graph structure  [alg. 2]
# Input:  motif, num_subgraphs, p, n_s, K
# Output: largest connected component of the generated graph

def structure(motif, num_subgraphs, p, n_s, K):
    # Start num_subgraphs copies of the motif and grow each one
    subgraphs = []
    for copy_index in range(num_subgraphs):
        subgraph = copy_of(motif)
        # Extra nodes: Poisson with mean n_s minus motif size  [alg. 2]
        extra = poisson(n_s - size(motif))
        for _ in range(extra):
            # Attach to a node with probability proportional to its degree
            target = sample_by_degree(subgraph)  # [alg. 2]
            add_node_with_edge(subgraph, target)
        subgraphs.append(subgraph)
    graph = union(subgraphs)
    # Join pairs of copies; the paper's pseudocode reads "if p: continue"
    # here, which is ambiguous (see Pitfalls)  [alg. 2]
    for each pair (i, j) of copies:
        if skip_pair(p):
            continue
        candidates = all_edges_between(subgraphs[i], subgraphs[j])
        while candidates:
            # Pick an edge with probability by the degrees of its ends  [alg. 2]
            edge = sample_by_degree_sum(candidates)
            candidates.remove(edge)
            add_edge(graph, edge)
            # Undo the edge if some node now has f(v) > K-1  [alg. 2] [eq. 1]
            if max_label(graph) > K - 1:
                remove_edge(graph, edge)
            else:
                break
    return largest_connected_component(graph)

# Homophily optimisation over redundant features  [alg. 3]
# Input:  graph, features, labels, eta
# Output: features with the requested homophily

def optimize_homophily(graph, features, labels, eta):
    # Connected pairs with the same label  [alg. 3]
    same_label_edges = sample_edges(graph, same_label=True)
    # Disconnected pairs; the paper says these have different labels  [alg. 3]
    disconnected_pairs = sample_non_edges(graph, same_label=False)
    # Connected pairs with different labels  [alg. 3]
    different_label_edges = sample_edges(graph, same_label=False)
    # D is the paper's pairwise term; the code uses cosine similarity
    loss = (
        -eta * mean_D(features, same_label_edges)
        + eta * mean_D(features, disconnected_pairs)
        + eta * mean_D(features, different_label_edges)
    )  # [alg. 3]
    return minimise(loss, over=features)

Hyperparameters

Base ShapeGGen configuration and its variants tab. 6. Code citations are for the paper's configuration script test_scripts/make_data/remake_SG.py.

Variants described in the text § Methods: Datasets in GraphXAI:

Other settings:

Real-world datasets tab. 7 tab. 8:

Real-world node datasets: average degree 44.48 ± 26.51 (German credit), 34.04 ± 46.65 (Recidivism), and 95.79 ± 85.88 (Credit defaulter) tab. 8.

Results

Author-reported. Setup: GIN with three layers and hidden size 16 is the base predictor, trained on SG-Base. Explanations keep the top 25% of attributes and are scored on the test split § Results: Experimental setup. Explainers: Grad, GradCAM, GuidedBP, IG, GNNExplainer, PGExplainer, PGMExplainer and SubgraphX, plus three random baselines § Results: GNN explainers. Values are mean ± std; the paper does not say what the spread is over.

Node masks, SG-Base, GIN tab. 1

Node masks, SG-Base, GCN tab. 2

Edge masks, SG-Base, GIN tab. 3. Only four explainers return edge masks.

Node-feature masks, SG-Base, GIN tab. 4. Only five explainers return feature masks.

Real molecular datasets with ground truth tab. 5. Stability and fairness are not reported here, because plausible perturbations of molecules are not straightforward and these datasets have no protected feature.

The Fluoride-Carbonyl Random row prints its GEF spread as 0.26, which is much larger than in every other row. This is as printed.

Findings the authors report § Results: Evaluation and analysis:

• Node masks are more reliable than edge or feature masks. SubgraphX gives 145.95% more accurate and 64.80% less unfaithful explanations than the other methods on average tab. 1. PGExplainer gives the least unstable explanations, 35.35% below the average of the other explainers tab. 1.
• Explainers are 55.98% more faithful on homophilic than on heterophilic ground truth fig. 4.
• Averaged over the eight explainers, the GEF on the larger house motif is 0.7476. Explanations for the smaller triangle motif are 59.98% less unfaithful fig. 5.
• On the unfair graph, GradCAM and PGExplainer preserve counterfactual fairness best on weakly unfair ground truth. PGMExplainer does best on strongly unfair ground truth fig. 6. Most explainers fail to show the enforced unfairness.
• As the share of informative features falls, unfaithfulness rises for all five feature explainers fig. 7 tab. 4.
• Gradient, the best node-feature explainer in faithfulness tab. 4, is only 0.001 more faithful than random § Results: Faithfulness shift.

Visualisations are available for nodes and graphs fig. 8 fig. 9.

Paper vs code

Official code: https://github.com/mims-harvard/GraphXAI, linked from the paper's Code availability statement § Methods: Code availability. It is owned by the authors' lab, MIT-licensed, and was cloned at commit a11e65ffbc4df737f35522a8accf2283a8aeaa37 (HEAD at clone time). The Tables in the paper may come from an earlier state of the code, and that is not checked. Code paths below are relative to the repository root at this commit.

Discrepancies:

• Protected feature. Paper: the protected feature equals the label and is flipped with probability phi alg. 1 § Methods. Code: attribute_sensitive_feature defaults to False, so the protected feature is drawn uniformly at random and does not depend on the label shape_graph.py. The paper's configuration script sets it to False remake_SG.py. With that setting, phi never enters the code, so the paper's SG-Unfair (phi = 0.75) is not reproduced by the shipped configuration script. When the flag is True, the code flips with sens_attribution_noise = 0.25, not with phi shape_graph.py.
• Node-level ground truth. Paper: the node mask is 1 for motif nodes within the L-hop enclosing subgraph, so S_v = S ∩ Sub(v) § Methods eq. 2 alg. 1. Code: a motif counts only if it touches the 1-hop neighbourhood of v shape_graph.py shape_graph.py. Motifs that sit only in hops 2 to L are excluded from the mask.
• Homophily sampling. Paper: disconnected pairs have different labels alg. 3. Code: the rejection loop keeps only pairs with the same label opt_homophily.py. The sign pattern in the code is minimised with cosine similarity opt_homophily.py.
• Edge connection rule. Paper: "if p: continue" alg. 2. Code: each pair is connected with binomial(n=2, p) drawn as a boolean, so the chance of connecting is 1 − (1 − p)² ≈ 2p, not p bound_graph_pref_att.py.
• Motif-count bounds. Paper: each node sees between 1 and K motifs § Methods alg. 2. Code: the bounds are hard-coded to 1 and 2 bound_graph_pref_att.py, so K > 2 is not supported.
• Feature construction. Paper: informative features are drawn from N(h_i, 1) and noise from N(0, 1) alg. 1. Code: informative features are mixed through a random matrix that adds covariance structured_feature.py, and class centres are scaled as 2·class_sep·v − class_sep structured_feature.py. The default flip_y of 0.01 is not in the paper feature_generators.py.
• Feature count. Code: n_features = 10 plus one sensitive feature gives 11 total shape_graph.py shape_graph.py. The paper calls this n_f = 11 tab. 6.
• GEA binarisation. Paper: top-k with k = 25% § Results: Implementation details. Code: graph_exp_acc thresholds at 0.8 by default base.py base.py. The graph-level function thresholds at 0.1 × max metrics_graph.py metrics_graph.py. The GCN table tab. 2 is labelled top-k; the 0.1 × max variant appears only as commented-out LaTeX, so which variant Table 1 uses is not stated.
• GEF direction. Paper: KL(f(S_u) ‖ f(S_u')) eq. 5. Code: F.kl_div(org.log(), pert) computes KL(pert ‖ org), which is the reverse base.py metrics_graph.py.
• Fairness metrics. Paper: GECF and GEGF are reported in Tables 1 to 4 tab. 1 eq. 7 eq. 8. Code: a search of graphxai/ for counterfactual, parity, GECF and GEGF returned no matches, so these metrics are not in the released package.
• Split. Paper: 70/5/25 § Results. Code: three independent random.sample calls with a global random.seed(1234), so train, validation and test sets can overlap shape_graph.py.
• GIN architecture. Paper: three GIN convolution layers, ReLU, softmax output, hidden 16 § Results. Code: each GINConv uses a single linear layer as its MLP. The full model adds BatchNorm, and the basic model has none. The forward pass returns logits, and softmax is applied outside the model, in the metrics testing.py testing.py.
• Training schedule. Paper: 1000 epochs at lr 1e-2 for GIN, and 1500 epochs at lr 3e-2 for "GNN models" § Results. Shipped example: lr 0.01 for 100 epochs, with no weight decay test_subgraphx_SG.py test_subgraphx_SG.py.
• Explainer hyperparameters. Paper: "following the authors' recommendations", values not given § Results. Not checked in the code.
• Not checked. Real-world dataset loaders, the random explainers, the SubgraphX and PGExplainer internals, and the perturbation ball used for GES. The stability numbers depend on these.

Searches: the paper links the repository directly, so no further search was needed. Only one repository was used. No other official code is known.

Pitfalls

• Fairness numbers. The unfair setting (phi = 0.75) is not reproduced by the shipped configuration, because the protected feature is random unless attribute_sensitive_feature is True, and then phi is replaced by 0.25. The GECF and GEGF metrics are not in the released package shape_graph.py. Treat the fairness rows as author-reported and unreproduced.
• Metric definitions. The GEF KL direction is reversed relative to the printed equation base.py. The GEA binarisation is a fixed threshold, not top-k 25% base.py. A reimplementation following the printed text will not match the released numbers.
• Ground truth scope. Node masks count only motifs touching the 1-hop neighbourhood, which is narrower than the L-hop definition in the paper shape_graph.py. A coding agent should use this definition if it wants to match the released data, and should say so.
• Edge connection rate. The connection rate is about 2p, not p, so the expected graph density is roughly twice what the table suggests bound_graph_pref_att.py. The node and edge counts in tab. 6 depend on the seed, which the paper does not state, so a regenerated graph may not match them.
• Homophily optimisation. The paper's D is not defined. Read as a distance, the signs in alg. 3 push connected same-label nodes apart. The code instead minimises a loss based on cosine similarity opt_homophily.py. Pairs are sampled once before 1000 Adam steps at lr 0.3, and are not resampled opt_homophily.py opt_homophily.py.
• Global RNG state. The generator seeds NumPy and Python's random module globally. The split uses random.seed(1234) shape_graph.py. Other code in the same process will see the reseeded state.
• Generation can fail. If no valid graph is found within max_tries_verification (default 5), the constructor raises a RuntimeError shape_graph.py. Budget for retries and parameter tuning.
• Overlapping splits. Train, validation and test sets are sampled independently and can share nodes shape_graph.py.
• Unknown spread. The ± values are not said to come from seeds or from test samples. Compare only within one table, with that caveat.
• Explainer settings. The paper does not state explainer hyperparameters, and "authors' recommendations" is not a value. Results depend on them, so replicating the table needs the settings from the code, which were not checked.
• Real-world data. MUTAG was trimmed from 4,337 graphs to 1,768 § Methods: Datasets in GraphXAI. The trimming rule is part of the benchmark and should be kept.

Lineage

• Builds on: the pitfalls of earlier ground truth, as listed by Faber et al. and probing work by Agarwal et al. (both cited in the paper, neither on this wiki) § Introduction.
• Builds on: the BA-Shapes construction from GNNExplainer (cited in the paper, not on this wiki) § Methods: BA-Shapes.
• Compared against: the eight explainers in tab. 1. PGExplainer is on this wiki: /papers/2011.04573. Other explainers are not on this wiki.
• Superseded by: not known from content on this wiki.