Explanations That Drift Toward the Majority Class

Methods that explain a graph neural network (GNN, a model that predicts a node's label by repeatedly pooling information from its neighbors) usually work by deletion. They remove some edges and watch how much the prediction changes. The edges whose removal hurts the prediction most are called the explanation. This test quietly assumes that a network shown less evidence falls back to a neutral guess. Under class imbalance that assumption is false. A GNN trained on skewed data falls back to the majority class.

The consequence is an asymmetry. For a minority-class node, almost any deletion pushes the prediction toward the majority, so any explanation looks faithful. For a majority node, almost no deletion flips anything, so good explanations look weak. We propose to measure this drift toward the network's learned default and to remove it from both the explainer's objective and the evaluation. The test is benchmarks where imbalance is controlled and the correct explanation is known by construction.

Core Claim

Deletion-based explainers and the fidelity metrics used to score them measure two things at once: evidence and the network's class prior. Fidelity here means how much the prediction drops when the explanation is removed. Counterfactual size means how many edges must be cut to flip the prediction. Under skew, both quantities are inflated for minority nodes and deflated for majority nodes, independent of which edges are selected.

The structure mirrors a failure documented in transductive few-shot learning, which classifies a whole unlabeled set jointly. Realistic evaluation of transductive few-shot learning showed that objectives built on a uniform class assumption override feature evidence once the query set is skewed. PT-MAP lost 18–20% accuracy when class proportions were drawn from a Dirichlet distribution. Squared-loss Mutual Information Regularization shows why: information-theoretic semi-supervised objectives depend on the class-prior probabilities. In both settings a hidden reference distribution, uniform in one and the majority-heavy default in the other, is mistaken for evidence.

Our fix is to explain evidence relative to the network's default. Let $f_y(G)$ be the network's predicted probability of class $y$ for target node $v$ on input graph $G$. Let $G_S$ keep only the edge set $S$ from $v$'s neighborhood, and let $G_\emptyset$ keep none of them, so $v$ sees only its own features. We score an explanation $S$ by

$$ E(S) = \log \frac{f_y(G_S)}{1 - f_y(G_S)} - \log \frac{f_y(G_\emptyset)}{1 - f_y(G_\emptyset)}, $$

which is the log-odds of class $y$ that the edges in $S$ add beyond what the network would say with no edges at all.

On the evaluation side, the raw fidelity drop is replaced by the drop minus a per-node null. The null is the average drop from deleting $|S|$ random edges from the same node's neighborhood. This turns the Random Edge baseline from Probing GNN Explainers into a matched control instead of a competitor. That paper found random edges often score better than real explainers on unfaithfulness. We test a specific explanation for that finding: much of it is drift toward the prior, concentrated in minority and high-heterophily nodes.

Relation to Prior Work

Three groups of papers play different roles.

Papers that motivate the gap. Tackling the Imbalance for GNNs shows that minority nodes sit in neighborhoods dominated by majority nodes. It measures this with the Label Difference Index (LDI), the gap between a node's label and its neighbors' label distribution. It shows high-LDI nodes are misclassified more often, but uses LDI only to reweight training and never examines explanations. We use LDI as the stratifying variable, because drift toward the prior should be strongest exactly where LDI is high. IGL-Bench benchmarks 24 imbalance methods on accuracy alone. We add explanation quality as an outcome. Probing GNN Explainers studies demographic group fairness of explainers, not label-class skew. Its random-baseline finding is the phenomenon we try to decompose.

Papers that supply the methods we modify. These are GNNExplainer, which optimizes a mask per instance; PGExplainer, which trains one edge-scoring network shared across instances; and CF-GNNExplainer, which searches for minimal edge deletions that flip a prediction. All three were validated on synthetic motif graphs where classes were not deliberately skewed. Each is changed only in its scoring target: $E(S)$ replaces the raw prediction. ReFine already conditions explanations on class through per-class modules. It assumes enough examples per class to pretrain them, and it does not correct for the network's default prediction.

Papers that constrain the design. Evaluating Attribution for Graph Neural Networks finds that GAT attention weights are poor importance signals. It also finds that attribution quality decays late in training while accuracy holds. That rules out attention as a free fix, and it means checkpoint choice must be controlled. ConfExplainer notes that its information-bottleneck assumptions break under distribution shift. A skewed label distribution is one such shift, so we include it as a comparison rather than assuming it is robust.

Research Program

Step 1: controlled testbeds. We build synthetic motif graphs in the style of BA-SHAPES and TREE-CYCLES. The number of attached motifs, and therefore the motif-class share, is set by Dirichlet-sampled class proportions using the sampler in the Realistic_Transductive_Few_Shot code. This sweeps imbalance from near 1:1 to 100:1, the extreme regime where IGL-Bench reports that all models degrade. Ground-truth motif edges remain known at every ratio.

Step 2: measuring drift. We train a GCN on each graph and measure two things per node. The first is the default prediction $f(G_\emptyset)$. The second is the drift rate: the fraction of random $k$-edge deletions that move the prediction toward the majority class. We regress both on class membership, degree and LDI.

Step 3: corrected explainers. We run GNNExplainer, PGExplainer and CF-GNNExplainer twice, once with their original targets and once with $E(S)$. We score both versions three ways: ground-truth edge AUC, raw fidelity, and null-corrected fidelity, each reported per class.

Step 4: real data. We repeat on real data where no ground truth exists: Cora, Citeseer and PubMed under IGL-Bench-style imbalance. We also use MUTAG with one class subsampled. On MUTAG, the NO₂ and NH₂ groups that PGExplainer recovered serve as a domain-level check.

Baselines

The naive reference point is the Random Edge explainer. It selects $|S|$ random edges from the target node's neighborhood. We run it with the same explanation size as each explainer, reporting a mean over at least 20 draws per node. This baseline doubles as our null, so a method beats it only if its null-corrected fidelity is positive and its ground-truth AUC exceeds random, within each class separately.

The strongest existing explainers are PGExplainer and CF-GNNExplainer, with their published settings. PGExplainer is strong because it is shared across instances: it learns patterns over all nodes, which is exactly where majority dominance should bite. Its paper reports a 24.7% relative AUC improvement over GNNExplainer on BA-2motifs. CF-GNNExplainer reports at least 94% accuracy in selecting ground-truth motif edges, while removing 1.47 to 2.39 edges on average, on TREE-CYCLES, TREE-GRID and BA-SHAPES. At the near-balanced end of our sweep we expect to roughly reproduce these numbers, and we treat that as a sanity check of our pipeline. On real imbalanced node classification we found no reported explainer result on Lacuna, so all comparisons there are run by us.

ReFine and ConfExplainer are secondary baselines. ReFine supplies class awareness, and ConfExplainer supplies reliability scores. Neither reports a number on Lacuna on imbalanced graphs.

Fairness is enforced in three ways. Every explainer receives the same frozen GNN checkpoint, chosen by validation macro-F1, to avoid the late-training decay effect. Every explainer gets the same explanation-size budget and the same hyperparameter search budget, tuned on balanced-class validation nodes. Every explainer is scored per class and per LDI tercile.

Two ablations isolate the key ingredient:

  • Balanced-loss explainer. The explainer's training loss is reweighted by inverse class frequency, keeping the original target. This separates "the majority dominates training" from "the reference point is biased".
  • Balanced-loss backbone. The backbone GNN is retrained with the improved focal loss from Tackling the Imbalance for GNNs, and separately with TOPOAUC. IGL-Bench reports TOPOAUC reaching 83.34% accuracy against 76.36% for vanilla GCN on imbalanced Cora. This tests whether drift persists once the classifier itself is corrected.

Beating the strongest competitor means two things. The prior-relative version must raise minority-class ground-truth AUC at ratios of 10:1 and beyond. It must also not lower majority-class AUC by more than seed noise.

Why not just…?

Why not just report fidelity separately for each class? Stratification would expose the asymmetry, and we do it. It cannot say why minority fidelity is higher: the network might rely on sparse decisive evidence, or it might simply fall back to the majority. Only the matched random-deletion null and the default prediction $f(G_\emptyset)$ separate those two causes. If stratified raw fidelity and null-corrected fidelity rank explainers identically across the sweep, our evaluation correction is unnecessary, and we will report that.

Why not just reweight the explainer's training loss by class? This is a real threat for PGExplainer, whose shared training is plausibly dominated by majority nodes. It cannot help GNNExplainer or CF-GNNExplainer, which optimize each node separately and still inherit the biased reference point. The factorial ablation of target versus loss weighting settles this. If reweighting alone closes the minority AUC gap for every explainer, the reference-point claim fails.

Why not just fix the classifier with focal loss or TOPOAUC and use standard explainers? Correcting the classifier shifts its decision boundary toward minority classes. That may shrink the fallback toward the majority, and if so the finding becomes the simpler and still useful rule: "explain only balanced-trained networks." We consider this the most likely way the proposal could be partly scooped by a simpler answer. However, Evaluating Attribution for Graph Neural Networks shows that good accuracy does not guarantee faithful reasoning. Boundary shifting could also introduce its own shortcuts. The balanced-backbone ablation measures drift rate and minority explanation AUC directly under each correction.

Why not just read attention weights or oversample the minority class? Attention was shown to be a poor importance signal by Evaluating Attribution for Graph Neural Networks. Oversampling inserts synthetic edges that an explainer could then select, and IGL-Bench found many such methods run out of memory or time on ogbn-arXiv. We therefore exclude both from the main study and mention them only as context.

Decisive Checks

The hypothesis is confirmed if three things hold on the controlled sweep:

  • Drift grows with imbalance. Drift toward the majority rises monotonically with the imbalance ratio and with LDI.
  • Raw fidelity diverges from correctness. Raw fidelity for minority nodes rises with imbalance even as ground-truth AUC falls.
  • Our correction tracks correctness. Null-corrected fidelity follows ground-truth AUC, measured by rank correlation across explainers and ratios, better than raw fidelity does.

A further check is that the random baseline's advantage from Probing GNN Explainers should shrink or vanish once fidelity is null-corrected and stratified.

The hypothesis is falsified if drift stays flat across ratios, or if the balanced-loss explainer alone matches the prior-relative target. In that case we would report imbalance as a training-data problem for explainers rather than a reference-point problem.