- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes REND, a graph OOD detection method that learns to identify OOD nodes without relying solely on the classifier's representations. REND consists of: 1) a reject encoder trained using raw features and the graph structure, and 2) a personalized PageRank kernel, which propagates OOD scores across the graph while retaining part of each node's original score. The reject encoder's output is combined with the classifier's energy score to produce the final OOD score after diffusion, without affecting in-distribution node classification. Experiments on twelve graph datasets under leave-out-class shifts demonstrate improvements over existing graph OOD detection methods. I have several concerns regarding the method's motivation and experimental settings. However, I would consider increasing my score if these concerns are adequately addressed.
Critical strengths
-
REND presents a novel novelty-learning framework for graph OOD detection, separating OOD detection from node classification to capture better OOD detection signals.
-
The paper provides theoretical analysis of the limitations of logit-based OOD scores and the score retention properties of personalized PageRank diffusion.
-
The authors have benchmarked against a wide range of baselines, achieving consistent performance gains across diverse datasets.
Critical weaknesses
-
The paper focuses only on leave-out-class OOD detection, with only a small feature corruption study (Figure4) in the appendix. However, existing works typically evaluate on more types of shifts, such as structural perturbations and combined feature-structure shifts. It is recommended to either explore the performance of REND on more commonly evaluated shift scenarios or clearly discuss why they are not compared.
-
Additionally, Line 316 states that REND evaluates label-leave-out shifts by withholding the last half of the classes. Although Appendix Figure 4 investigates different held-out class selections, it doesn't evaluate different numbers of held-out classes or analyse the distributional similarity between ID and OOD classes. This is important because the paper explicitly argues that logit-based OOD scores become more limited when fewer classes are observed.
-
The reject encoder is trained with a shuffled feature (Lines 269-271), which can introduce inconsistencies between node attributes and their neighborhoods. However, OOD nodes may have internally consistent features and structural relationships. The paper has not discussed whether the learned detector captures general distributional novelty or primarily recognizes the artifacts introduced by its training procedure.
-
Proposition 1 identifies a limitation of logit-based OOD scores, but it does not show how the reject encoder captures novelty information unavailable in the classifier's full representation. More direct representation analysis would be helpful to bridge the connection between the theoretical findings and the proposed design.
-
Missing more recent graph OOD detection discussions in the related work, such as:
- Song et al., Breaking One-Size-Fits-All: Revisiting Out-of-Distribution Detection on Graphs Under Diverse Distribution Shifts. AAAI 2026
- Wang et al., What Information Matters? Graph Out-of-Distribution Detection via Tri-Component Information Decomposition. ICML 2026.
- Chen et al., Decoupled Graph Energy-based Model for Node Out-of-Distribution Detection on Heterophilic Graphs. ICLR 2025
General Notes: It would be helpful to include some intuitive explanations for each theoretical claim, the current writing can be difficult to understand and follow.
Questions for authors
-
Why is a completely separate GNN encoder necessary (which is what REND can essentially be viewed as)? Could a simpler auxiliary detector, a shared encoder with an additional OOD objective, or a capacity-matched alternative achieve comparable performance. Although the ablation studies demonstrate its effectiveness, it does not fully establish whether the improvements come from learning more informative novelty representations, additional model capacity, or the separate optimization objective.
-
What evidence shows that the reject encoder actually learns information unavailable in the classification representation? The null space argument does not seem to full address this. Can the authors directly measure and compare the novelty information retained by the two representations?
-
Appendix Figure 4c shows that REND performs similarly to softmax under Gaussian corruption, despite showing stronger improvements under Bernoulli corruption. Why and when does the dedicated reject encoder would provide limited benefits (which also connects to weakness 1)?
5 comments
Q1. Is a separate GNN encoder necessary? New controls, all with the same surrogate and losses (Fig. 7b):
| Variant (same surrogate and losses) | AUROC | ID accuracy |
|---|---|---|
| Head on detached classifier embedding | 71.9 | 81.7 |
| Same, classifier widened to 128 units / deepened to 5 layers | 69.5 / 63.4 | 81.8 / 75.1 |
| Shared encoder (stop-gradient removed) | 77.6 | 70.3 |
| NODESAFE++ with our surrogate as exposure set | 79.9 | 77.3 |
| Graph-free (MLP) reject encoder | 81.5 | 81.9 |
| One-layer reject encoder | 79.3 | 81.7 |
| REND | 83.0 | 81.9 |
Capacity-matched alternatives (wider or deeper classifier with a novelty head) score 69.5 and 63.4. A shared encoder with the additional OOD objective reaches 77.6 but accuracy falls from 81.7% to 70.3%. A simpler graph-free reject encoder reaches 81.5 and a one-layer one 79.3, against 83.0. Most of the gain comes from a separate representation trained by the novelty objective; reading the graph adds the rest (Facebook: 75.1 graph-free against 88.1).
Q3. Gaussian versus Bernoulli corruption. Scale-matched Gaussian noise lowers the classifier's confidence, which the energy already reports, so a second representation has little to add. Bernoulli vectors produce large activations that the classifier reads as confident, and only a representation trained for novelty flags them. The reject encoder helps most when a shift leaves classifier confidence intact or inflates it, and adds little when confidence already drops and the shifted nodes are isolated, consistent with the new shift study. This explanation is now in the appendix.
General note on intuition. Proposition 1 is now followed by a plain-language sentence with a worked count of the invisible directions, Proposition 2 is read as a stopping random walk and now points to the separation result it supports, and Proposition 3 comes with an interpretation paragraph and a measured value of its factor on every benchmark.
Thank you for the detailed rebuttal and additional experiments, I appreciate the authors' efforts. Some of my original concerns are adequately addressed, however, three critical concerns remain. Thus, i would like to maintain my rating:
-
The new experiments provide valuable evidence but also shows an important limitation in the W1 Table, where REND underperforms both its local variant and free energy across all three additional shift types. I appreciate the theoretical explanation that diffusion is designed for connected OOD populations. However, this narrows the demonstrated effectiveness of the method primarily to leave-out-class shifts, which affects the practicality of the method.
-
Moreover, i am still not fully convinced on the response to W4. Particularly, while the linear probe results show better OOD separability in the reject embedding, i do not think this necessarily establish that the reject encoder captures novelty information unavailable in the classifier's full representation, so the connection to Proposition 1 still appears insufficiently established.
-
Also, the graph-free reject encoder achieves 81.5 AUROC compared with REND's 83.0 in the Q1 response, suggesting that much of the improvement comes from the separate novelty objective rather than graph-based encoding. I believe the architecture complexity is thus not well explained given this performance comparison.
We thank the reviewer for the careful reading. All changes in the revised PDF are marked in blue.
W1. More shift types. We added structure, feature-interpolation, and combined shifts on all twelve graphs in the single-graph protocol of the paper (one tenth of the test nodes perturbed in place; Fig. 8c). Mean AUROC:
We report this result as it is. The shifted nodes here are isolated, not a connected population, so by Proposition 3 diffusion has nothing to separate, and every propagated score falls below its local counterpart. REND loses less to diffusion than averaging and stays ahead of the two propagation detectors on structure and combined shift, and adding rewiring and interpolation to its surrogate adds two points (65.1, 67.8). The best score on isolated perturbations is the undiffused free energy, which REND's untouched classifier supplies unchanged. The revision states this scope in the main text: the reject channel targets novelty that arrives as a population, such as unseen classes, and the local energy of the same model covers isolated perturbations.
W2. Number of held-out classes and ID/OOD similarity. We varied the number of held-out classes on five graphs, from one class to all but two (22 configurations, Fig. 8d). REND has the highest AUROC in all 22 against free energy, GNNSafe, NODESAFE, and Mahalanobis. Its margin over the best of the four is 4.2 points when the fewest classes are held out and 12.1 when only two classes remain for training (Amazon-Photo 94.1 against 73.9; Wiki 86.2 against 75.5), which is the trend Proposition 1 predicts. For similarity, across the 78 held-out classes of the twelve benchmarks, per-class detection shows no significant association with the cosine similarity between the class's feature centroid and the nearest training class (Spearman 0.20, p = 0.08); the thirds by similarity score 83.0, 80.8, and 85.1 from least to most similar.
W3. Surrogate artifacts versus general novelty. New paragraph "What the Surrogate Teaches". The nodes REND is evaluated on are genuine held-out-class nodes, with consistent features and edges within their class, not shuffled nodes. A linear probe separates them at 86.0 on the reject embedding. A surrogate with labeled-ID donors only still reaches 79.7. Under pure structure shift, where no feature is altered and rewiring was never seen in training, the local reject score still reaches 67.6. The ID anchor rewards any direction along which labeled nodes are tight and corrupted ones are not, and such directions also set apart unseen classes.
W4 / Q2. Direct representation analysis. Fig. 7c. Linear probe for ID versus OOD (diagnostic only, it uses OOD labels): logits 63.6, classifier embedding 75.3, reject embedding 86.0, with the reject embedding ahead on all twelve graphs. Label-free Mahalanobis: 67.6 on the classifier embedding, 78.6 on the reject embedding. Only 4% of the classifier embedding's variance lies in the null space of the head, so classification training leaves those directions nearly empty, as part (ii) of Proposition 1 suggests.
W5. Related work. Song et al. (AAAI 2026), Wang et al. (ICML 2026), and Chen et al. (ICLR 2025) are now cited and discussed in Related Work.