Pathway Explanation Sets with Rerun Coverage for Cancer Graph Models

Graph neural networks (models that update each node's representation by pooling information from its neighbors) are now used to classify cancer patients over networks of biological pathways, and clinicians are invited to read the highlighted pathways as disease drivers. Those highlights are single point estimates. If you retrain the model with a different random seed, rerun a stochastic explainer, or drop a few low-confidence interactions from the pathway database, a different pathway may come out on top. This proposal asks how often that happens on a real pathway model. It then replaces the single "top pathway" with a small set of pathways that has a guaranteed probability of containing whatever an independent rerun of the whole pipeline would name. A set of size one means the explanation is trustworthy for that patient. A set of size five means the model's rationale is not identified at the single-pathway level.

The opportunity is that patient cohorts give conformal prediction a clean setting. Conformal prediction is a distribution-free method that calibrates a threshold on held-out examples to get finite-sample coverage. Graph-based uncertainty work usually stumbles on the fact that nodes in one connected network are not interchangeable samples. Here the network is a fixed pathway-pathway graph, and the exchangeable units are the patients, who are plausibly independent draws from a cohort. Applying conformal calibration to the randomness of re-explanation, rather than to labels, gives explanation sets with coverage that holds under that exchangeability assumption. No existing graph explanation method provides this.

Core Claim

We make two claims and test both. The first is empirical. Wiring a model to known biology does not remove explanation multiplicity, meaning the existence of several equally valid explanations for one prediction. Instead, the instability concentrates among densely connected pathways within the same functional module. This would resolve a tension in the literature. One review of biologically informed cancer models argues that sparse biological wiring stabilizes biomarker sets across data splits (systematic review). Work on tabular SHAP shows that top-$k$ feature sets churn across seeds even when the model is 99% confident (Explanation Multiplicity in SHAP). Nobody has measured this kind of churn on a biological graph model.

The second claim is methodological. A conformal "rerun set" over pathways reaches its nominal coverage on held-out patients while staying small. Its per-patient size detects unreliable explanations better than three alternatives: the model's own softmax confidence, ensemble attribution variance, and the aleatoric/epistemic scores of EU-GNN.

Research Program

The base model is GraphPath, a graph attention network over a KEGG-derived pathway-pathway interaction graph. GraphPath stratifies prostate cancer patients from copy-number and mutation features and reports AUC 0.933±0.028 against P-NET's 0.905±0.038 on the Armenia et al. cohort (GraphPath). We chose it because its graph has a few hundred pathway nodes. Retraining dozens of copies is therefore cheap, which keeps the cost objection to sampling-based uncertainty from deciding the outcome.

We define one stochastic explanation pipeline $E$. Each run draws three independent sources of randomness. The first is a model training seed. The second is an explainer seed; we use GNNExplainer masks and gradient-based attributions on the pathway nodes, and also GraphPath's own attention weights. The third is a structured edge resample. Each pathway-pathway edge is kept with probability tied to its database support, rather than perturbed by the uniform random-walk noise EU-GNN uses (Quantifying uncertainty in GNN explanations). Following the dual-seed protocol of the SHAP multiplicity study, we vary these factors separately and jointly. This attributes churn to model, explainer, or topology. We measure the churn with top-$k$ Jaccard overlap and rank-biased overlap, a top-weighted agreement score between rankings. That study showed magnitude errors such as $\ell_2$ hide rank instability (Explanation Multiplicity in SHAP), so we use rank metrics.

The conformal construction is short. For a patient $x$, average $m$ runs of $E$ to get a reference ranking $\pi_x$ of pathways. Draw one further independent run and let $t_x$ be its top pathway. The non-conformity score is the position of that fresh top pathway in the reference ranking:

$$s(x) = \text{rank of } t_x \text{ in } \pi_x .$$

On $n$ calibration patients we compute $s$. We then take $\hat q$ as the $\lceil (n+1)(1-\alpha) \rceil$-th smallest score, where $\alpha$ is the tolerated miss rate. For a test patient we report the explanation set

$$C(x) = \{\text{the top } \hat q \text{ pathways of } \pi_x\}.$$

Patients are exchangeable and the fresh run is independent. Standard split-conformal arguments therefore give probability at least $1-\alpha$ that an independent rerun's top pathway lands in $C(x)$. This guarantee is marginal over patients and pipeline randomness. It does not say the set contains the true biological driver. It says how much of the explanation is reproducible, and we state that limit plainly.

We then add an adaptive variant that makes set size depend on the patient. It scores with cumulative rerun frequency instead of raw rank, in the style of adaptive classification sets. We also add a module-level variant that ranks KEGG functional modules instead of individual pathways. If the first claim holds, the module-level sets should be much smaller at the same coverage.

Baselines

The naive reference is a single deterministic run: one trained GraphPath, one explainer pass, and the top pathway reported as a set of size one. Its empirical rerun coverage, the fraction of patients whose fresh rerun agrees, is the number to beat. It also directly measures the problem.

The second baseline is ensemble attribution variance, the approach of Wodrich et al. (Predictive and Explanatory Uncertainties). That study masks substructures across deep-ensemble members and treats attribution variance as explanatory uncertainty. It found this variance correlates with predictive uncertainty yet carries complementary information on ESOL and Mutagenicity. We give it the same $m$ trained models our method uses, so it costs nothing extra. We turn it into sets in two ways: by thresholding empirical top-1 frequencies at $1-\alpha$, and by taking the smallest set whose ensemble frequency mass reaches $1-\alpha$. This is the most important comparison. Our method beats it only if its sets undercover on held-out patients while ours hold nominal coverage at similar size.

The strongest existing method for graph explanation uncertainty is EU-GNN (Quantifying uncertainty in GNN explanations). It combines feature and random-walk perturbations for aleatoric uncertainty with a variational parameter decoder for epistemic uncertainty. It reports misclassification-detection AUC gains over prior uncertainty methods of 11.9% on BBBP, 8.5% on BACE, and 19.7% on TOX21, and an AUC of 0.623 on BACE under 5% noise. To check our reimplementation, we first run it on TOX21 with scaffold splits. We then port it to GraphPath with the same base models and an equal tuning budget measured in GPU-hours. On the Armenia cohort we found no reported result on Lacuna for explanation uncertainty. Beating EU-GNN means a higher AUC for flagging misclassified patients and unstable explanations using set size, plus a coverage guarantee that EU-GNN does not offer.

ConfExplainer (Confidence-Aware Explanation) trains a small network to output edge confidences inside a graph information bottleneck and reports calibration via NLL, Brier score, and ECE on motif and molecule graphs. It serves as a parametric-confidence comparison. It is tuned with the same budget, and its confidences are thresholded into sets.

Two ablations isolate our key ingredients. The first replaces structured, database-weighted edge resampling with EU-GNN's uniform random-walk perturbation. The second drops conformal calibration and keeps raw frequency thresholds.

Why not just…?

Why not just trust the softmax confidence? If the model is sure of the class, perhaps the rationale is stable. The SHAP multiplicity study found severe rank churn at 99% confidence (Explanation Multiplicity in SHAP), but that was on tabular models. We test it directly by reporting the rank correlation between softmax confidence and conformal set size on Armenia patients. If set size is nearly a monotone function of confidence, we will say the set adds little beyond confidence.

Why not just count how often each pathway wins across an ensemble? This is the real threat. With enough seeds, empirical frequency sets may already be close to calibrated, in which case the conformal step is cosmetic. Our position is that with the small $m$ affordable on larger biological models, the naive sets will undercover. The second baseline and the second ablation settle this. If frequency sets match nominal coverage on held-out patients across $m \in \{5, 10, 20\}$, we will report that the contribution is the measurement and the module-level finding, not the calibration.

Why not just read GraphPath's attention weights? They come from the model directly, with no explainer noise. They do not, however, come without seed or topology noise. Attention weights are retrained along with everything else, and the systematic review warns that dense pathway connectivity makes such internal signals hard to read (systematic review). Attention is one of our explainers, so its multiplicity is measured alongside the post-hoc ones. If attention churns less than post-hoc explanations, that is a useful finding in its own right.

Why not just apply EU-GNN unchanged? EU-GNN is restricted to graph-level classification of small molecules and gives scores, not sets with coverage. Its uniform perturbations ignore the fact that pathway edges have very uneven evidential support. Patient-level pathway classification is itself a graph-level task, so EU-GNN does transfer. That is why it is a full baseline here rather than something we argue around.

Proposed Experiments

The first experiment is the multiplicity measurement on the Armenia cohort of 1,013 patients, split into training, calibration (about 200 patients), and test sets. It reports top-1 agreement, top-5 Jaccard overlap, and rank-biased overlap under each source of randomness alone and combined. The decisive test of the first claim is whether pairs of pathways that churn sit inside the same KEGG module significantly more often than a degree-matched random baseline. The second claim also predicts that module-level sets are much smaller than pathway-level sets at equal coverage.

The second experiment checks coverage and set size at $\alpha \in \{0.05, 0.1, 0.2\}$ on internal test patients. It also checks the external primary ($n=130$) and metastatic ($n=40$) cohorts. These external cohorts break exchangeability, so we expect undercoverage there, and measuring how much is the point of the experiment. The third experiment tests detection: whether set size flags misclassified patients and explanations that change under held-out database versions, compared by AUC against all baselines. The final sanity check asks whether pathways that stay in size-one sets coincide with those GraphPath reports as prominent, such as "Pathways in cancer" and "Prostate cancer". If not, the stable part of the explanation may be stable for reasons unrelated to biology, and we would report that.