acceptodds
Under review as a conference paper at ICLR 2027

Does Node-Level Out-of-Distribution Detection Need Stochastic Uncertainty?

Abstract

Node-level out-of-distribution (OOD) detection is usually addressed with stochastic uncertainty methods, but the benchmarks that rank them have received little scrutiny. We show that the most widely reused protocols reward input scale and graph-level contrast rather than uncertainty. Standard Gaussian feature noise inflates feature norms on row-normalised graphs, and scoring a synthetic graph against the original tests graph discrimination instead of node detection. We propose a controlled protocol suite with scale-matched node-level corruptions, neighbourhood rewiring, held-out classes, and a real temporal shift, together with DCE, a deterministic encoder whose classifier reads each node's normalised features beside its aggregated context. Once scale is matched, sampling barely changes detection, whereas DCE outperforms dedicated uncertainty methods on feature anomalies in a single forward pass and achieves excellent accuracy. We also prove that node-wise decoders under separable losses cannot exploit a structured prior's cross-node correlation, and our experiments show no gain from such priors.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Network, Node Classification, Normalizing Flow

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_mhF1OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper claims that common node-level graph OOD benchmarks partly reward feature-scale artifacts and graph-level discrimination. The author shows that a deterministic encoder (DCE) can outperform stochastic uncertainty methods on feature anomalies.

Critical strengths
  1. The motivation (including Figure 1) is clear and easy to follow.

  2. Theoretical analysis is broad.

  3. Experiments support the claims of the paper.

Critical weaknesses
  1. The novelty seems incremental, which mainly stems from the benchmark critique.

  2. In the theoretical analysis, the invariance claims require node-wise decoding (+ separable objectives), which seems very hard to satisfy this condition.

  3. Although several exact marginal-matching comparisons are statistically inconclusive, the paper describes structured-prior effects as absent.

Questions for authors

Please see the above weaknesses

3 comments

We thank the reviewer for the careful report. Changes in the revised PDF are printed in blue, and section, figure, and table numbers below refer to the revision.

W1. Incremental novelty. The benchmark critique is one of three results.

  1. Measured diagnosis. The best score under the standard protocol (MC-Dropout mutual information, 0.946) falls to chance (0.491) once noise moments are matched, and the catastrophic baseline rows are sign inversions that one LayerNorm removes. To our knowledge this has not been measured before.
  2. Constructive consequence. A deterministic encoder of standard parts beats every dedicated uncertainty method by 0.14 to 0.24 AUROC on the scale-matched feature protocols in one pass, and a complete 2 × 2 ablation traces the margin beyond capacity to one read-out. The revision adds that sampling this encoder contributes almost nothing.
  3. Theory. Proposition 6.1, Theorem 6.2 (a decoder-independent rank bottleneck with a tight k/n rate), and Proposition C.4 (graded certificate for r-hop decoders) are new statements about structured latent priors. The revision bounds the negative result from the other side with a trained positive control.

W2. Node-wise decoding and separable objectives seem hard to satisfy. They hold by default, and our wording obscured that. Section 6.1 now reads: "Neither condition demands a special design, since cross-entropy is separable by construction and a model is node-wise whenever message passing acts on deterministic states and the draw enters through per-node maps." Message passing over features is unrestricted. Only the random draw may not travel between nodes. Where the conditions fail, Proposition C.4 extends the certificate and Section 6.4 removes each premise experimentally.

W3. Inconclusive comparisons described as absent effects. Correct on both counts.

Evidence. We added twenty trials and analysed them alone as an independent replication, so that no verdict is tested twice.

Exact marginal matchingCells certified equivalentSignificant differences
first 10 trials (submission)4 of 90
20 added trials, analysed alone8 of 90

The ninth cell (matched-noise AUROC, Amazon Computers) has a pooled difference of +0.004 with interval [−0.002, +0.011], and we report it as uncertified.

Language. "Changes no endpoint" is now "we detect no change in any endpoint", "show no gain" is "we detect no benchmark gain", and "stays inert" is removed.

Thanks for the detailed response.

I would maintain my positive rating.

Dear Reviewer mhF1,

Thank you for your valuable and constructive feedback. We sincerely appreciate your thoughtful comments and suggestions, which have helped us significantly improve the quality, clarity, and overall presentation of our manuscript.

Reviewer_ANLJOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper re-examines common evaluation protocols for node-level out-of-distribution (OOD) detection on graphs. It identifies two potential confounding factors: feature-scale discrepancies introduced by Gaussian corruptions and graph-level comparisons that do not directly assess node-level detection. To address these issues, the authors develop a controlled evaluation suite and introduce DCE, a deterministic graph encoder that combines normalized node representations with aggregated neighborhood information. The paper also investigates the limitations of structured stochastic priors under node-wise decoding and separable training objectives, supported by theoretical analysis and experiments using a graph-conditional normalizing flow. The paper addresses an important evaluation problem and provides useful evidence that the reported advantages of stochastic uncertainty methods can depend heavily on the evaluation protocol. However, the findings are less conclusive beyond the examined settings, and the broader claim that stochastic uncertainty offers limited benefits for node-level OOD detection remains insufficiently supported.

Critical strengths
  1. The paper identifies meaningful confounding factors in existing node-level OOD benchmarks. The controlled experiments show how evaluation protocols can affect the relative performance of uncertainty estimators.
  2. The experiments cover multiple datasets, OOD settings, and uncertainty estimators, with architectural controls, ablations, and statistical analyses.
  3. The analysis of structured priors under node-wise decoding provides useful insights into when stochastic dependencies may not affect marginal predictions. The authors also examine settings beyond the main theoretical assumptions.
Critical weaknesses

W1. DCE differs from several stochastic baselines in both architecture and training. Although GAT-deep (LN) provides a useful control, the comparison still does not isolate the effect of stochastic uncertainty. Applying MC-Dropout and deep ensembles directly to DCE would provide a more convincing test of the central claim.

W2. The theoretical results apply to restricted decoder and objective settings, and identical marginal predictions do not imply identical joint behavior or node-ranking performance. More importantly, the learned models appear to make little use of their stochastic latent variables. It remains unclear whether structured priors are ineffective or the evaluated objectives simply fail to exploit them. A trained positive control demonstrating useful cross-node dependence would help resolve this issue.

W3. The proposed corruption protocol may not reflect realistic OOD shifts. Moment matching removes the feature-scale bias, but it does not preserve sparsity, feature dependencies, or the original feature distribution. This is particularly concerning for sparse bag-of-words features. The conclusions would be stronger with sparsity-preserving corruptions and more realistic semantic shifts.

Questions for authors
  1. How would MC-Dropout and deep ensembles perform when applied directly to DCE with identical encoder capacity and training settings?

  2. How sensitive are the results to corruption severity and sparsity-preserving perturbations?

4 comments

We thank the reviewer for the careful report. Changes in the revised PDF are printed in blue, and section, figure, and table numbers below refer to the revision.

W1 / Q1. MC-Dropout and deep ensembles on DCE. The first ensemble member is the DCE that MC-Dropout samples, so every comparison is paired on the same weights.

AUROCgraph/rawgraph/matchednode/rawnode/matchednode/interpnode/shufflenode/rewireclasses
DCE, 1 pass0.9220.8520.9030.8350.7840.7800.8280.812
MC-Dropout (DCE), 30 passes0.9210.8480.9010.8310.7800.7770.8270.810
Deep Ensemble (DCE), 5 nets0.9350.8620.9180.8460.7910.7870.8400.828
Deep Ensemble (5 GCN)0.5290.6760.4600.6010.5950.5910.8250.830
  1. MC-Dropout never helps (−0.001 to −0.005).
  2. The ensemble gain on DCE (+0.007 to +0.016) equals the ensemble gain on a two-layer GCN (+0.002 to +0.008) and is more than ten times smaller than the encoder effect.
  3. The ensemble's mutual information, the score that reads stochastic disagreement, is worse than its own entropy on every protocol (−0.02 to −0.06). The gain is a more accurate mean predictor, not an uncertainty signal.

The text now says "sampling adds little" instead of "no longer improves".

W2. Restricted theory; unused latents; trained positive control.

Positive control (Appendix G.3). We train the unchanged GCNF with the pairwise objective on a block graph whose labels are one fair coin per block, redrawn every step, so cross-node dependence is the only learnable signal.

Arm, 3 generated graphsPairwise NLL
independent predictions / perfect joint model1.386 / 0.693
structured prior, pairwise objective1.238, 1.244, 1.244
optimum of any node-wise decoder at the learned smoothness1.237, 1.241, 1.235
isotropic prior, same objective1.386
structured prior, separable objective1.386

The model reaches the node-wise optimum (Borell's theorem: half-spaces maximise Gaussian noise stability) and raises the prior's smoothness from 5 to about 30 without being asked. The pipeline can exploit a structured prior.

A stricter test of the benchmark null (Appendix G.4). Building the control led us to analyse the estimator of the pairwise score. With S draws it rewards a cross-draw correlation only above 1/(S−1), which is 1/3 at our S = 4. We therefore reran the pairwise cells at S = 32 (threshold 0.03). The null survives the stricter test:

Structured − isotropic pairwise NLL, 90% CI (margin ±0.01)node-wiseneighbour-conditioned
Cora, 10 trials−0.002 [−0.005, +0.001]−0.001 [−0.002, +0.001]
WikiCS, 5 trials+0.001 [−0.011, +0.014]−0.001 [−0.009, +0.007]
Amazon Computers, 10 / 5 trials−0.000 [−0.013, +0.012]−0.006 [−0.013, +0.002]

No contrast differs from zero, and realised dependence stays at or below 3e-4 nats per edge on every graph, more than thirty times under the margin. We claim equivalence only on Cora, where the intervals lie inside the margin.

Why the benchmarks differ from the control. The correctness of the two ends of a test edge shares 0.023 nats of mutual information on Cora and 0.004 on WikiCS and Amazon Computers, against 0.693 on the block task. The paper now concludes exactly this: no detectable gain under standard training on these benchmarks, a clear gain when the task rewards dependence, and no claim that no training procedure could extract the small dependence the benchmark labels contain.

Marginals versus joint behaviour. Agreed. This caveat moved from an appendix remark into Section 6.2: AUROC and selective risk "depend on the joint law, so for them the evidence is the retraining of Section 6.4 alone".

W3 / Q2. Sparsity, severity, semantic shifts. You are right that matched Gaussian noise densifies sparse rows (3 to 250 times as many active features, Figure 7a). We added marginal resampling: each raw feature is redrawn from its own training values, then the loader's normalisation is applied. Marginals and sparsity are preserved, only co-occurrence is destroyed. On binary bag-of-words this is Bernoulli noise at each word's training frequency.

node-level AUROCGCNDeep EnsembleGNNSafeGPNGAT-deep (LN)DCEEnsemble (DCE)
matched Gaussian0.5970.6010.5610.5730.7160.8350.846
marginal resampling0.5980.6000.5610.5720.7080.8350.845

Severity (share ρ of coordinates overwritten, marginal resampling):

ρ0.100.250.500.751.00
Deep Ensemble (5 GCN)0.5120.5270.5520.5760.600
DCE0.5450.6090.7020.7770.835

Detection is monotone in ρ and the ordering never reverses. The original suite already held two corruptions that preserve sparsity and feature dependence exactly (node/shuffle, node/interp), and DCE leads on both. On semantic shifts we make no claim for DCE: propagated energy wins held-out classes, nothing detects the temporal shift, and the abstract now names both as open.

My concerns have been addressed, and I thank the authors for their experimental verification. I will increase my score.

Dear Reviewer ANLJ,

We sincerely thank you for your valuable and constructive feedback and for your positive reassessment of our manuscript. We greatly appreciate your thoughtful comments, suggestions, and increased evaluation score. Your insightful feedback has helped us significantly improve the quality, clarity, and overall presentation of our manuscript.

Reviewer_n8dqOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper shows that node-level out-of-distribution (OOD) detection needs a stronger encoder rather than stochastic uncertainty once the benchmarks stop rewarding input scale and graph-level contrast, and provides a deterministic approach via DCE (deterministic context encoder) with a higher performance. Respectively, the authors show that the most reused node-level OOD protocols reward input scale and graph-level contrast rather than uncertainty, and turn them into a controlled suite. The authors introduce DCE whose classifier's read-out sees each node's normalized representation beside its aggregated context, outperforms dedicated uncertainty methods in one forward pass and achieves excellent accuracy. The authors further prove node-wise decoders under separable objectives cannot see a structured prior's correlation, and sees low-rank priors as nearly isotropic noise, and provide experiments that show no gain from such priors.

Critical strengths

The paper explains what most reused node-level OOD methods actually measure and reward. With experiments on scale effects of Gaussian feature noise, the author shows raw and moment-matched noise give similar detection, thus scale accounts for most of what raw noise adds; meanwhile node-level OOD scores detect the scale of the input rather than uncertainty about the class. This unconventional finding is meaningful and crucial to naturally introduce the deterministic encoder based method further proposed by the paper.

The paper introduces a competitive baseline for node-level OOD detection, demonstrating an outstanding OOD detection performance (shown in Table 1, measured on detection AUROC metric) and excellent classification accuracy (Table 2) on selected benchmarks (including citation graphs, co-purchase graphs, co-authorship graphs and hyperlink graphs) against state-of-art baseline methods (GCN, GraphSAGE, GAT, APPNP, GRAND, GPN, NodeFormer, DIFFormer, Exphormer, MaskGAE, and LGNSDE).

Critical weaknesses

The experiment doesn't demonstrate reliable detection under real-world distribution shift. For real distribution shift (or temporal shift) no existing methods including the proposed DCE (or GCNF) method can reliably detect on obgn-arxiv, which does not provide support to the main claim that OOD detection doesn't need stochastic uncertainty, and further analysis can be conducted.

The style of presentation might be overstating the findings, since evidence support a narrower conclusion: certain stochastic uncertainty methods provide little benefit under the controlled protocols examined, while the proposed strong deterministic encoder performs well on feature anomalies. The evidence doesn't establish that stochastic uncertainty is unnecessary across graph OOD detection more broadly, and above mentioned unresolved temporal and semantic settings are counterexamples to a more general claim.

Questions for authors

Do the conclusions hold when methods are compared on calibration, selective prediction, risk-coverage, or decision-making under distribution shift, rather than AUROC alone? Could stochastic methods provide benefits on these objectives even when their anomaly-ranking performance is similar?

Can you provide an overall train-time and test-time efficiency comparison not only between DCE and GCNF, but also with the existing baseline methods?

2 comments

We thank the reviewer for the careful report. Changes in the revised PDF are printed in blue, and section, figure, and table numbers below refer to the revision.

W1. No method detects the real temporal shift. New analysis (Appendix B.1, Figure 6) shows why: the shift is weak even for a detector that is told the answer.

Detector (AUROC, 3 trials)
Supervised probe fitted on half of each populationdegree 0.59, features 0.68, DCE encoder 0.77
Distance scores in DCE's representationk-NN 0.54, Mahalanobis 0.52
DCE / MC-Dropout (DCE) / Deep Ensemble (DCE)0.504 / 0.502 / 0.504

Accuracy falls by 1.3 points by 2020. The text now says this arm "favours no family of methods". It is consistent with the narrowed claim only in that sampling adds nothing there either (MC-Dropout over GCN 0.517 against 0.541 for its backbone).

W2. Overstated conclusions. Agreed and adopted. Abstract: "MC-Dropout adds nothing and ensembling adds little, even on DCE. Shifts that leave a node's features intact remain open." The introduction and conclusion confine the claims to the controlled protocols and name the temporal and semantic settings as open for all methods.

Q1. Calibration, selective prediction, risk–coverage. MC-Dropout gives no benefit on any of them. Ensembles give a small, consistent one, which the paper now states. Clean test split, eight-benchmark means:

Read-outAcc.NLL (temp.-scaled)ECE (temp.-scaled)Selective AURC
GCN88.350.3810.0240.0386
MC-Dropout (GCN)88.280.3760.0230.0383
Deep Ensemble (5 GCN)88.690.3660.0240.0369
DCE90.130.3180.0190.0312
MC-Dropout (DCE)90.100.3170.0200.0308
Deep Ensemble (5 DCE)90.360.3050.0210.0290

Ensembling lowers NLL by about 0.015 nats and AURC by 0.002 on both backbones, through +0.2 to +0.3 points of accuracy, at five times the cost. A single DCE is better on every column than the five-GCN ensemble.

Under shift, sampling changes as little as on clean graphs, and the encoder comparison is mixed. Selective AURC with a fifth of test nodes altered:

ShiftGCNDCEDeep Ensemble (DCE)
rewiring0.07290.04560.0425
matched noise0.04380.04270.0395
shuffled features0.04890.05450.0508

DCE is far better under rewiring, equal under matched noise, and worse under shuffled features, where it detects the altered nodes better (AUROC 0.78 against 0.59) but misclassifies more of them. We report this limitation in Section 5.3 and Appendix B.3. No stochastic read-out changes the ordering of the encoders in any condition.

Q2. Efficiency against all baselines. Figure 15, Appendix H.1 (geometric means over eight benchmarks):

MethodParamsTrain (s)Score a graph (ms)
GCN0.10M0.71.1
MC-Dropout (GCN / GAT)0.10M0.7 / 0.921.6 / 37.8
Deep Ensemble (5 GCN)0.52M3.23.9
GPN0.10M1.22.2
DCE0.37M3.44.0
MC-Dropout (DCE) / Ensemble (5 DCE)0.37M / 1.85M3.4 / 17.8112 / 18.3
GCNF, 30 draws1.65M5.4152
GraphSAGE, APPNP, NodeFormer, DIFFormer, Exphormer0.10–0.47M0.7–3.8n/a
GRAND, MaskGAE, LGNSDE0.11–0.25M19–26n/a

DCE costs what the five-GCN ensemble costs and scores five to nine times faster than MC-Dropout over a two-layer backbone.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal

We thank all three reviewers. This comment lists the summary of our rebuttal. Revised text is marked in blue in the PDF.

Reviewer n8dq

ConcernsComments
W1. No method detects the real temporal shiftAdded Appendix B.1 and Figure 6, which show the shift is weak even for a supervised probe that is told the answer (AUROC 0.59 from degree, 0.68 from features, 0.77 from the DCE encoder). The text now says this arm "favours no family of methods"; sampling adds nothing there either.
W2. Conclusions are overstatedAgreed and adopted. The abstract, introduction and conclusion now confine the claims to the controlled protocols and name the temporal and semantic settings as open for all methods.
Q1. Calibration, selective prediction, risk-coverageAdded NLL, ECE and selective AURC on eight benchmarks. MC-Dropout gives no benefit; ensembles give a small, consistent one at five times the cost, and a single DCE is better on every column than the five-GCN ensemble. Under shift DCE is worse on shuffled features, which we report as a limitation (Section 5.3, Appendix B.3).
Q2. Train-time and test-time efficiency against all baselinesAdded Figure 15 (Appendix H.1) with parameters, training time and scoring time for every baseline. DCE costs what the five-GCN ensemble costs and scores five to nine times faster than MC-Dropout over a two-layer backbone.

Reviewer ANLJ

ConcernsComments
W1, Q1. MC-Dropout and deep ensembles applied directly to DCERan both on DCE, paired on the same weights. MC-Dropout never helps (−0.001 to −0.005 AUROC). The ensemble gain (+0.007 to +0.016) is more than ten times smaller than the encoder effect and comes from a more accurate mean predictor, not an uncertainty signal. The text now says "sampling adds little".
W2. Restricted theory; unused latents; trained positive controlAdded a positive control (Appendix G.3): the unchanged GCNF reaches the node-wise optimum when the task rewards dependence, so the pipeline can exploit a structured prior. Reran the benchmark pairwise cells at S = 32 (Appendix G.4); no contrast differs from zero, and we claim equivalence only on Cora. The marginal-versus-joint caveat moved into Section 6.2.
W3, Q2. Sparsity-preserving corruptions, severity, semantic shiftsAdded marginal resampling, which preserves marginals and sparsity; results match matched Gaussian noise (DCE 0.835 on both). Detection is monotone in severity and the ordering never reverses. We make no claim for DCE on semantic shifts, which the abstract now names as open.

Reviewer mhF1

ConcernsComments
W1. Novelty seems incrementalClarified the three results: a measured diagnosis (the best standard-protocol score falls from 0.946 to 0.491 once noise moments are matched), a deterministic encoder that beats every dedicated uncertainty method by 0.14 to 0.24 AUROC in one pass, and new theory (Proposition 6.1, Theorem 6.2, Proposition C.4), now bounded by a trained positive control.
W2. Node-wise decoding and separable objectives seem hard to satisfyClarified in Section 6.1 that both hold by default: cross-entropy is separable by construction, and a model is node-wise whenever the draw enters through per-node maps. Proposition C.4 and Section 6.4 cover the cases where the conditions fail.
W3. Inconclusive comparisons described as absent effectsAdded twenty trials analysed alone as an independent replication: 8 of 9 cells are certified equivalent (4 of 9 before), with no significant differences, and the ninth is reported as uncertified. Reworded to "we detect no change in any endpoint" and "we detect no benchmark gain".

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.