Influence-Anchored Computation Graphs for Explaining GNNs at Scale

A graph neural network (GNN) predicts a node's label by repeatedly mixing information from its neighbors, its neighbors' neighbors, and so on outward. On large networks this "computation graph" around a single node can reach tens of thousands of nodes. The explainers we trust most, which remove pieces of the graph and watch the prediction move, become unaffordable at that size. The usual fixes are borrowed from scalable graph algorithms: sample a fixed number of neighbors, or treat high-degree hubs as dead ends. Both decide what to throw away from the graph's shape alone. They ignore what the trained model actually relies on, and hubs are often exactly the conduits a prediction depends on.

This note proposes a different order of operations. For each node whose prediction we want to explain, first estimate cheaply, with one gradient pass, how much each node in its computation graph would shift that prediction if removed. Keep the few high-influence "anchor" nodes, plus the message paths that connect them to the target. Collapse everything else into absorbing placeholders. Then run an expensive, faithful explainer on this much smaller graph. The claim is that explanations computed on the shrunken graph closely match those computed on the full graph, at a fraction of the cost. Shrinking the graph by structure alone, whether by degree, PageRank, or random sampling, at the same size budget should distort explanations measurably more, and most visibly on targets near hubs.

Core Claim

Influence-based seed selection has so far been structural. NISE seeds community expansion from cluster centroids and spread-out hubs. It inflates each seed with its immediate neighborhood so that random walks do not get stuck. HoSIM finds dense cores near a boundary query node with a walk that pushes probability mass away from the seed. On the scalability side, RWDISK proves that turning high-degree hubs into absorbing sinks costs little error for random-walk proximity and saves 5x in page faults. Those results concern walk-based proximity, not a neural model's decision. NORA supplies the missing ingredient. It estimates, for every node at once, how much removing it would shift a trained GNN's predictions. It does this with a three-term first-order approximation (the vanished message, the changed degree normalization, and propagation through layers), reaching Pearson correlation of 0.90 to 0.98 with brute-force removal while cutting 41 hours to under a minute on ogbn-arxiv. NORA also reports that PageRank fails to track this model-specific influence.

NORA's scores are a global scalar ranking that aggregates over all predictions. Nobody has used a target-specific version of them as the criterion for deciding which part of a computation graph an explainer may ignore. That is the proposal. We will build an influence-anchored reduction of each target's computation graph. Write $f_t(G)$ for the model's output on target $t$ given graph $G$. Write $\hat{I}_t(v)$ for the first-order estimate of $|f_t(G) - f_t(G \setminus \{v\})|$, obtained from a single backward pass from $t$ using NORA's decomposition. We choose the smallest anchor set $A_t$ such that

$$\sum_{v \notin A_t} \hat{I}_t(v) \;\le\; \epsilon \sum_{v} \hat{I}_t(v),$$

where $\epsilon$ is the fraction of estimated influence we allow ourselves to discard. Influence is not additive, so this is a stopping rule and not a guarantee. Whether it behaves like one is the first thing we test. The reduced graph keeps $A_t$, the shortest message paths from each anchor to $t$ (so the graph stays connected, which avoids the disconnected-subgraph failure of soft edge masks), and NISE-style one-hop inflation around each anchor. Every other node is collapsed into a per-layer sink that carries its frozen aggregate message. The model's prediction on $t$ is therefore approximately preserved rather than abruptly changed.

Research Program

The first component is the reduction itself, built for GCN, GraphSAGE and GAT backbones. We will measure how well $\hat{I}_t$ tracks brute-force single-node removal for a specific target. NORA validated aggregate influence, not per-target influence. We will also measure how the stopping rule's $\epsilon$ maps onto actual prediction drift $|f_t(G) - f_t(G_{A_t})|$. NORA flags first-order approximation as weakest on attention aggregators, so GAT is deliberately included as a stress case. If the approximation fails there, we will fall back to a second short pass that re-scores the top candidates by exact removal on the already-reduced graph.

The second component is a plug-in study. The reduced graph is handed, unchanged, to existing explainers that are faithful but expensive. These are GNNShap, which samples Shapley coalitions over edges after pruning edges that cannot reach the target; EiG-Search, which sorts edges by a gradient along a path from an empty graph and checks only prefix subgraphs; and exact removal-based attribution on graphs small enough to enumerate. GNNShap's reachability pruning is exact and model-agnostic, so it keeps every edge that touches the target. Our reduction is approximate and model-aware, and it composes with GNNShap's pruning rather than replacing it.

The third component tests the "hub dilemma" directly. We bucket targets by the maximum degree in their two-hop neighborhood. We then compare how each reduction treats hubs: our method keeps a hub only when its estimated influence is high, whereas RWDISK-style sinking removes every hub above a degree threshold. This answers a question no paper in the corpus addresses. Do degree-based truncations, adopted for speed, make explanations systematically unfaithful by deleting the conduits the model uses?

Baselines

The naive reference point is to run each explainer on the full $L$-hop computation graph with no reduction. Where that is affordable (Cora, CiteSeer, PubMed, synthetic BA-shapes and Tree-Grid, and sampled targets on ogbn-arxiv), it is the ground truth our reduction must reproduce. Where it is not, we report the explainer's failure or timeout. The strongest existing scalable Shapley explainer is GNNShap. On Cora it reports Fidelity+ of 0.206±0.000 with 10k samples (against 0.178 for GraphSVX) and Fidelity− of 0.008±0.000 with 50k samples (GNNShap). For ogbn-products the file gives only a qualitative statement of lower explanation times, with no reported number. We will run GNNShap with its own pruning and the same sample budget on full and reduced graphs, on the same GPU. "Beating" it means matching its Cora Fidelity± within one standard deviation on the reduced graph, while cutting wall-clock time by at least 5x on ogbn-arxiv and ogbn-products.

The strongest amortized competitor is LARA. It trains source and target embeddings whose inner product scores each edge's removal effect, and it reports a 3.5x speedup over the best amortized baseline on ogbn-arxiv with higher Fidelity+. The file gives no exact fidelity number for LARA on Lacuna. We will train LARA on the same backbone and splits, with a tuning budget matched to the total GPU hours our method spends on reduction plus explanation, and compare per-target Fidelity+ and Fidelity− at equal explanation size. EiG-Search serves as the training-free linear-time baseline, run on full graphs.

Three ablations isolate the key ingredient, model-aware anchor choice, holding the reduced-graph node budget fixed: degree-based hub sinking in the style of RWDISK; personalized PageRank from the target, as structural centrality; and GraphSAGE-style uniform neighbor sampling. Further ablations remove path retention and neighborhood inflation separately, to show whether connectivity matters for explainer agreement.

Why not just…?

Why not just use the top-$k$ influence scores as the explanation and skip the explainer? This is the most serious threat. If the first-order scores already rank nodes as well as Shapley values do, the second stage is wasted computation. The case against it is that $\hat{I}_t$ scores nodes one at a time and cannot see interactions such as redundant paths. Two parallel routes to the target each look unimportant alone yet matter jointly. That is precisely what coalition-based explainers capture. We will settle it empirically. Top-$k$ $\hat{I}_t$ is itself a reported baseline at every explanation size. If it matches explainer-on-reduced-graph within noise on Fidelity± and ground-truth AUC, we will report that the reduction's value lies in making cheap explanations credible, and drop the claim that expensive explainers are needed.

Why not just sample neighbors or sink hubs, as scalable training already does? These reductions are model-oblivious. NORA reports that PageRank-style centrality misses which nodes actually move predictions. RWDISK's error bound concerns walk proximity, not a nonlinear classifier. The equal-budget ablations above test this directly. If degree sinking matches our fidelity even for hub-adjacent targets on ogbn-products, the hub dilemma is not real and we will say so.

Why not just train LARA, which is already fast at scale? LARA scores edges independently and returns no connected subgraph. Its amortized embeddings may also lag on targets unlike those seen in training. We compare at equal compute. LARA could plausibly win on throughput alone, so the claim we defend is fidelity and agreement with exact attribution per unit of compute, not raw speed.

Why not just use attention weights from a GAT? Evaluating Attribution for Graph Neural Networks found that attention weights perform worse as explanations than dedicated attribution such as CAM or Integrated Gradients. We include attention as a weak reference on the GAT backbone and do not expect it to compete.

Proposed Experiments

The datasets are Cora, CiteSeer and PubMed for exact comparisons; BA-shapes and Tree-Grid for ground-truth motif AUC; and ogbn-arxiv (169k nodes) and ogbn-products (2.4M nodes) from the Open Graph Benchmark for scale. On ogbn-products the reference GraphSAGE reaches 78.50% test accuracy, so our backbones should be near that before we explain them. Metrics are Fidelity+ and Fidelity−, explanation AUC on synthetic motifs, Spearman correlation between edge attributions on full versus reduced graphs, reduced-graph size, prediction drift, and wall-clock time per target. Following Probing GNN Explainers, we also run a sanity check. Explanations from a randomized-weight model must change, and the reduction must not mask that change by retaining the same structural anchors regardless of the weights.

Three checks decide whether the idea holds. The first is calibration. On 1,000 sampled ogbn-arxiv targets, where brute-force removal within each computation graph is feasible, $\epsilon$ must predict actual prediction drift monotonically. If influence-anchored reduction does not track drift better than PageRank reduction at the same size, the method fails at its foundation. The second is agreement. GNNShap attributions on reduced graphs must correlate above 0.9 Spearman with full-graph attributions on Cora and on arxiv targets, while the structural ablations at equal size fall measurably below. The third is the hub-dilemma curve. Plotting fidelity loss against neighborhood hub degree, degree sinking should degrade sharply for hub-adjacent targets on ogbn-products while our reduction stays flat. A flat curve for degree sinking would refute the motivating tension, and we would report it as a negative result on the reach of RWDISK's bound.