Refining Norms: A Post-hoc Framework for OOD Detection in Graph Neural Networks
Authors: Jiawei Gu
Ziyue Qiao
Zechao Li
Venue: NeurIPS 2025 poster ()
Keywords: graph neural network; out of distribution detection
Primary area: deep_learning

Abstract: Graph Neural Networks (GNNs) are increasingly deployed in mission-critical tasks, yet they often encounter inputs that lie outside their training distribution, leading to unreliable or overconfident predictions. To address this limitation, we present RAGNOR (Robust Aggregation Graph Norm for Outlier Recognition), a post-hoc approach that leverages embedding norms for robust out-of-distribution (OOD) detection on both node-level and graph-level tasks. Unlike previous methods designed primarily for image domains, RAGNOR directly tackles the relational challenges intrinsic to graphs: local contamination by anomalous neighbors, disparate norm scales across classes or roles, and insufficient references for boundary or low-degree nodes. By combining global Z-score normalization, median-based local aggregation, and multi-hop blending, RAGNOR effectively refines raw norm signals into robust OOD scores while incurring minimal overhead and requiring no retraining of the original GNN. Experimental evaluations on multiple benchmarks demonstrate that RAGNOR not only achieves competitive or superior detection performance compared to alternative techniques, but also provides an intuitive, modular design that can be readily integrated into existing graph pipelines.

Refining Norms: A Post-hoc Framework for OOD Detection in Graph Neural Networks
Jiawei Gu', Ziyue Qiao²; Li', NNajjnng University of Science and Technology, Nanjing University of Science and Technology, Schooo of Computing and Information Technology, Great Bay University gjscs@outlook. com, ziyuej jedgmmaijiiaall....... com, zechao li@njjst...... edu
Abstract
Graph Neural Networks (GNNs) are increasingly deployed in mission-critical tasks, yet they often encounter inputs that lie outside their training distribution, leading to unreliable or overconfident predictions. To address this limitation, we present RAGNOR (Robust Aggregation Graph Norm for Outlier Recognition), a post-hoc (OOD)
approach that leverages embedding norms for robust cut-of-distribuute detection on both node-level and graph-level tasks. Unlike previous methods designed primarily for image domains, RAGNOR directly tackles the relational challenges intrinsic to graphs: local contamination by anomalous neighbors, dis- parate norm scales across classes roles, and insufficient references for boundary or low-degree nodes. By combining global Z-score normalization, median- -aased local aggregation, and multi-hop blending, RAGNOR effectively refines raw norm signals into robust OOD scores while incurring minimal overhead and requiring no retraining of the original GNN. Experimental evaluations multiple benchmarks demonstrate that RAGNOR not only achieves competitive or superior detection performance compared to alternative techniques, but also provides an intuitive, modular design that can be readily integrated into existing graph pipelines.
1 Introduction
Out-o--distribution (OOD) detection is critical for robust graph neural networks (GNNs), ensuring that models can flag anomalous inputs they have not been trained to handle 12
20
48
22
41].
Real-world scenarios commonly exhibit new or shifted graph structures, including previously unseen node types in social networks (malicious accounts, emerging user communities), novel molecular
motifs in biochemical graphs, or unexpected entities in knowledge graphs [45] 21 27 39 40). A
GNN that overlooks such anomalies risks overconfidently providing incorrect predictions, with poten- tially grave consequences high-stakes settings [10 environments 37 36 44 3 2)
across increasingly deployment
Norm-based inspiration and the gap. In image domains, feature norms of deep networks have proven surprisingly effective for OOD detection 33 in-distribution (ID) inputs tend to elicit stronger, more "aligned" activations, whereas truly novel inputs produce feature norms that deviate substantially. Yet, the graph domain introduces unique relational complications: node embeddings depend on the neighborhoods (which themselves could be OOD), and distinct node classes roles may inherently have different norm scales. A naive transplant of norm-based rules from computer vision to GNNs can thus fail in key corner cases, especially when tackling both node-level OOD detection (identifying anomalous nodes in a single large graph) and graph-level OOD detection (recognizing entire anomalous graphs in a dataset) g 7]
29 53 motivated by observations that
Why is norm-based detection non-frivial on graphs?
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

dartiaata PD (a003)
Local Coraanal Ganipl
Land ladios Wel ())
Boundayy Londige
3.10
Demon
Figure 1: Four main difficulties in applying norm-based OOD detection to graphs. (A) Global shift in ID vs. OOD node norms but partial overlap: (B) Local contamination, where neighboring OOD nodes skew reference norms; (C) Class- role-level norm differences even within ID; (D) Boundary or low-degree nodes lacking sufficient one-hop context.
has pinpointed several critical factors that explain why naive norm-based approaches often fail deliver satisfactory results on graph data. These key challenges include:
Indeed, our comprehensive investigation, detailed Appendix C
Key Challenges Graph OOD Norm Detection
(I) Local Contamination. In graphs, an OOD node's neighbors may also be OOD, distorting niighborhood-basee statistics and undermining naive local reference.
(2) Class-level Norm Differences. Legitimate ID classes (or structural roles) may exhibit naturally high or low norms, causing false alarms if not globally adjusted.
(3) Boundary & Low-degree Issues. Sparse regions or boundary nodes lack a sufficient one-hop neighborhood for reliable norm comparison, requiring multi-hop context.
Figure D provides visual illustration of these difficulties: (A) shows that although OOD nodes often shift the norm distribution, overlaps persist; (B) demonstrates local contamination in a small subgraph; (C) highlights how distinct classes can yield vastly different norm scales while still remaining in- distribution; (D) depicts boundary or low-degree nodes for which local reference alone is fragile.
Core observation. Despite these complications, we find that a carefully refined norm- norm-based method can still be a robust, lightweight, and scalable post-hoc OOD solution for GNNs. Graphs inherently provide relational cues (e.g. multi-hop neighborhood structure), and we can unify these signals with global normalization to mitigate systematic norm offsets. Rather than discarding the elegant simplicity of norms, we propose to amplify their utility via tailored set of reference and aggregation steps.
Proposed approach. We devise framework that addresses each difficulty in turn, yet remains straightforward addition to existing GNN models: (i) Global Z-score normalization adjusts each node's raw norm based on ID statistics, reducing the chance that a high-norm class is misdetected; (ūi) Median- based local reference counters local contamination by using robust statistics (median rather than mean) to offset outlier neighbors; (ūii Multi-hop blending extends beyond single-hop neighborhood for boundary or low-degree nodes, providing more stable norm baseline. Because the entire procedure conducted after the GNN has been trained, demands no architectural modifications or additional supervision. practical, scalable, and industry-ready deployment.
Contributions.
We conduct one of the first examinations of norm-based OOD detection in GNNs, revealing how node-level and graph-level anomalies can be effectively characterized by embedding norms.
We identify three significant principal roadblocks (local contamination, class-level norm offsets, and boundary/low-derree constraints) in graph neural networks and propose computationally efficient post-hoe framework that systematically overcomes them with theoretical guarantees. Extensive evaluations real-world and synthetic benchmarks demonstrate that our solution signif- icantly improves OOD detection performance across diverse datasets while preserving simplicity and minimal computational overhead, facilitating broad adoption in practical applications.
The remainder of this paper is organized as follows. We first describe our method detail (Sec. 2 and present its theoretical underpinnings (Sec. Subsequently, report comprehensive empirical

---

study on both node-level and graph-level OOD tasks across diverse datasets (Sec. Finally, the paper concludes with discussions broader implications and future directions (Sec.)
2
Method
In this section, we propose a post-hoc detection approach for out-of-distributtion (OOD) nodes and graphs, leveraging the node embedding norms ||h,|| of trained Graph Neural Network (GNN). While other issues may arise in exotic scenarios, we focus on three commonly encountered challenges in norm-based OOD detection for graphs:
Cl: Local contamination: A node's immediate neighbors might themselves be OOD and thus significantly distort local reference norms, leading to unreliable detection performance.
C2: Global/class-lvvel norm variations: Certain valid in-distribution (ID) classes or structural roles exhibit unusually large or small norms, causing false alarms if not normalized.
C3: Boundary & low-degree nodes: node near boundary or with few neighbors may need more distant (multi-hop) reference information to achieve reliable and robust detection.
We next describe how we address each challenge in turn (Sections 2.2 2.4). and then unify these steps into single OOD detection procedure (Section 2.5).
2.1 Notation
Let G (V.E) be graph with N | nodes. Each node E V has learned embedding h, RR Let 2, E ReC be the logit vector (output before the final activation/softmax) for node u, where C is the number of classes (if applicable). We write
Fr hell
for v's embedding norm, and let (v)) denote the set of immediate neighbors of v. Further, let MiD and OID be the mean and standard deviation of the norms {r.} estimated from reference set of known in-distribution (ID) nodes (e.g. from training or validation data). We assume dID > O.
2.2 Challenge Cl: Robust Local Reference
Motivation. A straightforward approach might compare r, to the average of (ra u E (v)), flagging node OOD if its norm deviates significantly from its neighbors' expected distribution pattern. However, if some neighbors are themselves OOD, the average can be heavily skewed by these extreme values, thus failing to reflect the "typical" ID norm in v's local neighborhood.
Formula (Median Aggregation Concept). To mitigate contamination by small fraction of outlier neighbors, we adopt a median-based aggregation concept for local reference:
Median
( (ru))))(()))
This captures the central tendency robustly. As detailed below, apply this median concept to normalized norms.
Explanation. Whereas mean can be substantially distorted by extreme values, the median discards the magnitude of outliers long they do not constitute majority. This provides more robust local norm estimate, protecting our OOD detector from neighbors that are also anomalous.
2.3 Challenge C2: Global Norm Variations
Even when a node's neighbors are valid ID, some classes or roles within the complex heterogeneous graph might exhibit larger or smaller norms due to their inherent structural properties. we rely solely on raw norms Tu the local aggregation (like Eq, 2 these norm differences could trigger frequent false positives for certain tail classes, reducing the overall detection reliability.
Motivation.
3

---

Formula (Z-score Normalization). We address this by transforming each node's norm into standardized scale using the estimated ID statisties:
MID
T OID + VUE
(3)
where is a small constant for numerical stability.
Explanation. By centering and rescaling the norms using ID statistics, we make them more comparable across different classes or structural conditions. We use these normalized norms r, for computing the robust local reference in subsequent steps. This ensures that boundary or tail classes, which might have inherently large/small norms relative HID- do not get unfairly flagged based on their standardized deviation from their local neighhorhood"s standardized norms.
2.4 Challenge C3: Boundary & Low-degree Nodes (Multi-hop)
Even after considering robust local aggregation (using medians) and global normal- ization (using r'), serious detection issues can arise for nodes with very few neighbors or those positioned the boundary of multiple subgraphs. In addition, is possible that all most of node's first-hop neighbors are contaminated an OOD cluster forms in the local vicinity. Using information from more distant neighbors can provide more stable and reliable reference point.
Motivation.
Formulas (Multi-hop Reference using Normalized Norms). To capture a broader local structure, compute the median of the normalized norms in the I-hop and optionally the 2-hop neighborhoods. Let (x) denote the set of nodes exactly two hops away from v.
(x()) Median (Ira:ueN(v))
Tx Modian (1 (fr,:uENN(
(5)
We then blend these references:
Fmuutt( (v) (F + (1- OSASI.
Explanation. The parameter À controls the trade-off between immediate (one-hop) context and a broader, diffuse two-hop view, both calculated using normalized norms r'. For nodes with well- connected, mostly ID neighbors, higher À (closer to 1) might be sufficient. But if e is in sparse contaminated region, a larger contribution from 7 (=)()) (i.e., smaller X) can mitigate spurious local distortions by incorporating wider context. If only 1-hop information is desired, set À = 1.
2.5 Unified Post-hoc OOD Detection
Having addressed these three common pitfalls of norm-based OOD detection (C C3: now assemble them into a single procedure that yields both node-level and graph-level detection.
Discrepancy Computation. First, apply global normalization all nodes to get r' (Eq. 3 Then, for each node v. compute its robust local reference norm Fo, typically using the multi-hop blended reference based on normalized norms, i.e., F. = (1) from Eq. (6) (or simply F. FN)()) from Eq. if A 1). We define the node's norm discrepancy as:
A. 7/ Fe-
Nodes with large |A,| significantly deviate from their neighborhood's typical embedding norm distribution (after global rescaling and robust aggregation). suggesting OODness.
Formula (Confidence Scaling). To reduce overconfidence in downstream tasks (like classification) when A, is large, we can optionally rescale node v's logit vector 2, via
V (A.)
I+a : z v(Aa) Zus
(8)
where 2 is hyperparameter controlling how aggressively to penalize large discrepancies.

---

Node-level and Graph-level OOD Scores. based on the discrepancy magnitude:
For node-level detection, we set the OOD score directly
Scorep
|A
(9)
and mark as OOD if scorc, > т, where chosen threshold. For graph-level detection, we aggregate the node scores across the graph:
Score(G)
max score, Score(G) M
score
(10)
NEV
Hence, a graph is considered OOD if Score exceeds graph-level threshold Tgraph-
Discussion. Although other edge cases may exist, we have found that local contamination. global/class-level norm shifts, and boundaryllow-deree issues comprise the most frequent pit- falls in norm-base OOD detection on GNN embeddings. By addressing all three within a single unified framework using normalized norms and robust median-based aggregation (potentially multi- hop), our method yields an effective and light-weight post-hoc OOD solution for both node-level and graph-level tasks. We demonstrate its performance various benchmarks in Section 4
3 Theoretical Analysis
In this section, we provide a high-level overview of the theoretical guarantees for our proposed norm-based OOD detection method (Section 2). Our analysis hinges on the concept of local partial contamination, where we assume that for an in-distribution (ID) node, its local neighborhood (potentially extending multiple hops) is not overwhelmingly dominated by OOD nodes. This allows our robust aggregation scheme (using medians of normalized norms and optional multi-hop blending) to provide stable reference norm even the presence of some OOD neighbors.
All rigorous definitions, formal assumptions, intermediate lemmas, and detailed proofs are deferred Appendix for for completeness and clarity.
3.1 Problem Setup and Key Assumptions (Informal)
consider a graph G = (V,E) where each node v has a learned embedding h, and a corresponding norm || A subset VOOD C V consists of OOD nodes. Our method first applies a Z-score normalization to the norms using ID statistics (HID, OID) to obtain r' (Eq. The core assumptions underpinning theoretical results are (informally):
The normalized norms r' of ID nodes are concentrated around zero, typically within bounded range [- [-B, B] (Assumption 3 in Appendix).
Bounded Normalized ID Norms:
OOD Norm Separation: The normalized norms r', of OOD nodes are sufficiently separated from (Assumption 3 in Appendix). Local Partial Contamination: For any ID node v, the fraction of OOD nodes within its k-
the ID range, lying outside [-(B + 60), ) B + do] for some gap do
hop neighborhood (*)()) (for 1 and potentially k 2) is assumed strictly less than 50% (Assumption 5 in Appendix).
These assumptions are formalized in Appendix A.2
3.2
Main Result (High-Level Statement)
Recall the robust local reference norm F, for node v. which is computed by potentially blending the median of normalized norms in the 1-hop and 2-hop neighborhoods (Fq. (6). The discrepancy score for node v is A, = r F. (Eq. 7.. Our main theoretical result demonstrates that this discrepancy score effectively separates ID and OOD nodes under the stated assumptions.
Theorem (High-Level Detection Guarantee). Assume the conditions of Bounded Normalized ID Norms, OOD Norm Separation, and Local Partial Contamination hold (see Assumptions 3 and in Appendix A). Then, for suitably chosen threshold (related the ID norm bound B), the discrepancy score A satisfies the following with high probability:
(i) ID Preservation: For any in-iistribution node E VID. | S
5

---

(ii) OOD Separation: For any out-of- distribbbittn node w E VOOD. / Dul>T. T.
Consequently, thresholding | provides a reliable mechanism for node-level OOD detection. Aggregating these scores (e.g., using mux mean) extends this capability to gruph-level OOD detection.
Remark 2. The formal statement of this theorem (Theorem B including the precise relationship between т, B, do. the condition needed for OOD separation regarding the OOD node's own reference Two and the exact probabilistic guarantees, along with its complete proof relying on novel lemmas for robust aggregation under partial contamination (Lemmas and 77 can be found in Appendix A
3.3 Discussion
This theoretical result highlights the robustness of our median-based multi-hop aggregation strategy using normalized norms. Even when faced with partial OOD contamination in local neighborhoods, the reference norm Fe remains anchored to the typical ID norm range (around 0 after normalization, bounded by B), allowing the discrepancy A. to reliably flag nodes whose own normalized norms ry deviate significantly, Our analysis in Appendix A provides a rigorous mathematical foundation for this approach, specifically addressing the "layered contamination" across multiple hops. We believe this provides a solid theoretical underpinning for the effectiveness of the proposed method, complementing the extensive and diverse empirical results presented in Section 4
4 Experimental Results
We evaluate our post-hoc OOD detection method, RAGNOR, on established node-level and graph- level benchmarks. As a post-hoc approach. RAGNOR utilizes embeddings generated by pre-trained GNNs. We demonstrate that applying RAGNOR to embeddings from state-of-the-art models signif- icantly enhances their OOD detection capabilities. All experiments are repeated over runs with different random seeds, and we report the mean performance along with the standard deviation. Detailed experimental configurations, hyperparameters, and additional results (including node-level evaluation on Twitch and Arxiv datasets) are provided in Appendix D
4.1 Node-Level OOD Detection
Setup. We evaluate node-level OOD detection on Cora 19 Citeseer 19 and Pubmed datasets [9). using Structure Manipulation (S), Feature Interpolation (F), and Label Leave-out (L) to generate OOD nodes, following the protocol from NODESAFE [52]. We apply RAGNOR post-hoc to the node embeddings generated by the GCN backbone trained according to the NODE- SAFE setup (both with and without OOD exposure during GCN training). Performance is measured using AUROC (1), AUPR (t), and FPR95 (L). Results are averaged over 5 runs.
presents the results. Applying RAGNOR post-hoc consistently and significantly improves upon the performance of the base models (NODESAFE and NODESAFE+++) establishing a new state-of the--rrrttttttt across nearly all settings. For instance, NODESAFE + RAGNOR reduces the mean FPR95 on Cora-S from 25.63 to 17.1, substantial improvement. The low standard deviations observed for RAGNOR indicate its stability. This robust performance stems from RAGNOR's 's effective handling of common pitfalls in norm-based detection, such as local contamination and global variations, allowing it to reliably identify nodes with anomalous embedding norms within their proper context. This contrasts favorably with energy- based approaches, showcasing the power of direct, contextualized norm analysis.
Results and Analysis. Table I
4.2
Graph-Level OOD Detection
Setup. We assess graph-level OOD detection using 8 datasets (ENZYMES B0), IMDB-M/B 30)
REDDIT-I2K [I], BACE 44), BBBP 49), DrugOOD [15]. HIV 49 with diverse OOD charac- teristics, following SGOOD (5). RAGNOR is applied host-hoe to node embeddings from a GIN backbone trained for graph classification on ID data. Graph-level scores Score(G) are obtained via max-aggregation of node scores A Baselines include general, graph-specific, and anomaly detection methods. Metrics are AUROC (1), AUPR (t), and FPR95 (l), averaged over 5 runs.

---

Table 1: Node-Level OOD Detection on Cora, Citeseer, Pubmed. RAGNOR is applied post-hoc to NODESAPEENNDESSFF** embeddings. Mean Std. Dev. reported for RAGNOR over 5 runs (Std. Dev. for other methods not available from source). Higher is better, Lower is better. Best results in bold.
Metric
Citeseer
Expo
5
F
1.
MS
No
87.30
64.58
34,99
$5.03
71.27
51.97
$4.08
69.38
46,19
ODIN 20
100.00
100.00
100.00
100.00
100.00
100.00
100.00
100,00
100.00
Mahalanohis
20
99.13
99.73
86.32
78.21
Energy
38.76
GKDESS
84.34
68.24
88.95
93.71
71,22
50.61
$1.52
68.56
69.52
GPN 39
No
76.22
56.17
37.42
78.26
73. 14
41.37
80.33
61.79
50.23
GNNSAPE
No 73.15
38.92
30.83
74.72
68.83
36.53
44.64
33,89
36.49
GNNSAFE wf
15
61.04
38.44
34,99
76.35
72.35
37.32
75.10
49,93
32.29
NODESAFE
42.47
NODESAFE
17.1
34.0=22.1
21.5+116
14.1:909
06
Yes 67.73
83.79
16.55
95.37
81.09
05.99
$3.50
74,58
Energy FT
Yes
47.53
37.83
76.44
64.08
31.60
92.04
90.00
25 59
GNNSAFE++ 32
Yes 52.51
27.73
34,08
70.72
72.98
29.30
34.43
26.30
33.63
GNNSAFE++ w/
55
Yes 51.99
32.72
28.40
74.81
75:47
30.55
91.58
86.17
27.81
NODESAFE-11
23.34
$2.60
40.49
29.04
14.52
24,45
23.81
NODESAFE++
MSP
70.90
85.39
91.36
66.34
78.32
88.42
74.31
83.28
85.71
OPXN 24
No
49.92
49 58
49,80
49
49. 86
$1.33
49.76
49.67
56.24
Mahallaobis 20
No
46.68
49.93
67.62
45.26
49.92
$3.46
55.28
69.12
75.77
AUROCT
Energy
71.73
86.15
91,40
65.62
79.19
89.98
74.33
84.16
86.81
GKDE
77.47
70.55
GNNSAFE
87.52
93.84
92,80
79.79
83:46
90.01
$7.50
94,28
GNNSAFE
No
88.33
93.26
93.50
84.67
88.11
90.47
80.3 31
92.07
91.12
NODESAFE 52
No
94.07
95, 30
93.80
88, 40
90.41
91.66 66
94. 13
95.97
93 93.30
NODESAFE RAGNOR
97.1
97.91.022
96.5.10.44
94.2
95.510.55
95.8.10.4
97.3_00.
98.1100.2
97.0.10.3
72.06
74.41
81.97
Energy
91.34
GNNSAFE+1
Yes
90.62
95.56
92.75
$2.43
83:27
91.57
90.62
95.16
87.98
GNNSAPE W/ Cp.
52
Yes
90.13
94.11
93.81
84.93
87.68
91.00
86.21
87.56
89:66
NODESAFE
53
Yes 94.64
96.56
94.88
86.90
91.14
91.98
96.30
95.26
93 93.48
NODESAFE+ RAGNOR
Yes
97.3:0033
98.6:0.11
97,5
92.5:005
96.0:0044
95.9100.4
98.80.11
97,810.22
96.810.33
MSP
17:97
Mahalanozs A00
29.03
31,95
12.31
21.20
31.20
35.47
$.38
15.09
23.10
Energy 25
No 46.08
74.42
78.14
33.63
55.94
64.10
17.32
39.10
36.00
AUPR
GKDE 53
No
44.26
66.52
27.50
31.55
50.25
61.21
16.89
32.41
34.63
GPN
53.26
73.79
77.40
41.12
53.21
62.32
17.54
39.75
35.12
78.13
76.20
NODESAFE
$3.98
58.82
85.22
75.93
79.30
68.15
71.29
78:22
71.98
NODESAFE RAAGNRR
No
90.1100.8
93.5..0.6
91.01009
84.0...0
87.5.10.9
76.0111.1
79.1__1.2
86.0.10.9
79.5
Yes 46.93
70.84
77.01
30.07
48, 80
62.74
16.74
38.60
20,88
Energy 15
Yes 49.18
75.99
78.49
36.01
55.69
66.66
18.00
37.21
$2.39
GNNSAFEE4
GNNSAFF CAN
70.90
76.10
67.57
NODESAFE-
Yos
85.63
91,96
86.66
71.41
79.48
68.97
$1.88
78.12
53.45
KODESAFE-H RAGNOR
Yes
91.5
96.0::0.4
92.5:1006
7.00:1.1
87.8:008
76.51:1.0
89.0
16.3::10
62.01188
Results and Analysis. Table 2 details the graph-level performance. Applying RAGNOR post- hoc to standard GIN's embeddings, denoted as "SGOOD + RAGNOR" (using SGOOD's GIN backbone for comparability, though SGOOD's specific training regime is not required for RAGNOR), sfate-of-the-atd markedly improving upon SGOOD. For example, AUROC
consistently sets on IMDB-M jumps from 78.84 (SGOOD) to 86.8 (SGOOD RAGNOR), and FPR95 on BACE decreases from 64.13 to 55.9. The gains are substantial and consistent across datasets, highlighting the power of aggregating accurately assessed node-level anomalies. While SGOOD focuses on encoding substructures, RAGNOR demonstrates that robustly measuring and aggregating deviations in fundamental node embedding norms relative to context provides a highly effective, general, and computationally lighter post-hoc strategy for graph-level OOD detection. The low standard deviations further attest to the reliability of this approach.
4.3 Ablation Study: Component Analysis
Setup. To dissect the contribution of RAGNOR's 's key components, we perform an ablation study evaluating different scoring strategies based on the presence or absence of Global Normalization (M1) and Robust Local Reference generation (M2). The core scoring mechanism itself (M3a: using the magnitude of discrepancy) is implicitly evaluated by comparing how different inputs affect performance. We compare: (1) using norm deviation from the global mean (rr, HID|, no
7

---

Table 2: Graph-Level OOD Detection Performance. RAGNOR is applied post-hoc embeddings from a GIN backbone (used by SGOOD). Mean + Std. Dev. reported over runs. t: Higher is better, J: Lower is better. Best results in bold.
ENZYMES
IMDB-M
IMDB-B
12D
BACE
BВBP
DrugOOD
ITV
MSP
61.3=388
42.8=1.5
59 69.632.33
50.6+0.9
46.3+6.11
57.4=4.3
52995.3
50.5=009
Energy 25
86.9-899
14.7+19.7
49.6-17.8
55.1+0.55
46.1+6.7
55.7-28
52.8-54
50.5+=0.9
50.01066
MAH 20
6..413.7
69.313.7
61410.5
72.7.10.9
75.312.9
$2.62388
66.9-411
58.11336
GNNSafe
86.9=8.9
219-18
70.5=14.8
51.7=0.0
47.6:7..5
47.0=24
50.4006
51.0=06
AUROCT
GraphDE
61.43.9
66.9-433
26.9434
59.40..2
4..3+1.55
50.9-288
60.2-433
12.4=16
GOOD-D 26
6.9
61.944.9
52.6 10.2
56.1+0.1
70.4412.2
542-1.1
60.5-19
57.1+0.1
AAGOD
65.0=444
70.8=5.5
72.5+1111
60.342.2
714422
19
00.3-12
55.7=0.77
OCGIN 54
68.144.6
47.5-9.5
87.849.22
1.3
59.7455.2
4.78-5.7
58.05588
54.1+0.5
GLocalKD 28
71.51322
19811.6
874154
49.611.11
45.312.1
43.8-2.3
45.7
46.8120
OGGTL 54
73.6=3.2
54.1212.9
37.4=1888
51.620.0
80.84200
58.7=22
67.6=799
$188022
SGOOD 5J
74.4=14
78.8=200
80
75,242.7
84,422.7
61.3-16
7322-1
60.80088
SGO0D RAGNOR
1.
86.8-1.5
88.14-.11
13.0+199
92.0+188
19.1-112
81.3-311
68.5-
[2]
61.7=6.6
51.0=199
58.122.3
48.6+1.11
48,743.1
56.8=34
54,5=44
50.7=0.5
Energy 25
54.7=9.2
31
59.0=13.1
56,5+088
49,744.2
56.6=4.2
55.0=44
51.0=2.1
50.0-006
MAH 20
63.8=2.2
63.6-2.1
81447.1
14,5+0,5
86
548-335
64.3-4
57,2=32
AUPR
GOOD-D
GraphDE 23
66.312.
626.4.55
42.7.2.11
63.1
51.126
$1.5
62.622
$4.11.32
AAGOD
67.2=6.4
28.2-4.5
67.9+488
614+1.6
718+177
18.2-15
66.2344
54.3=0.5
OCGIN 54
68.9+4.2
508-44.5
87.8-5.1
60.0+199
61445.2
47.3-3.0
59.5-7.0
52.1+0.3
GLocal X8
64.914
35...0.55
79.44..7
$1.8.0.7
55,11244
45.8.1.2
50.914
27.0./20
OGGTL 34
73.7=7.0
58.2-7.9
47.1=14.1
53.310.0
7..911.
60.5
70.955
$3.720.2
SGOOD 5]
73.7=7.0
72.5=332
83.543.6
75.0=0.8
83.3+2.55
59.42244
73.3=45
60.0=0.7
SGOOD RAGNOR
RAGNOR
81,5=14
80.5=2.1
90.812.5
82,91111
91.1115
67.0=11
31.0
0.68
MSP
89.7422.3
95.7-116
9144442
96.01.33
97.04-2.2
94.6-2.1
98.8-0.0
95.5+00.5
Energy 25
89.31.3.6
96.412.3
92.8.13.6
97.210.6
97.112.9
92.7-26
9.
95.510.6
ODIN
83.3=9.6
96.7-1.0
92.24129
96.520.77
97.011.5
96.3=1.8
99.0=11
94.=111
MAH 20
83.3=99.
60.9#19.1
76.9266.
80.8+2.1
73.8+2000
93.3=2.5
81,6=466
919913
97.0=3.7
95.5-114
96.0-0.3
FPRO5
GOOD-D
GraphDE
99.010.8
93.1-1822
100.0.0.00
81.8
94.2.14.6
94.6.1.1
88.8
94,9.0.8
AAGOD
82.8122.8
81.6122.3
86.314.0
92.5
90.6.12.00
93.5
95.3
9..2:0.3
OCGIN 54
98.3117.7
GLocal 28
78.7=6.4
98.3=1.1
85.6:13.
97.620.4
98.7+1.1
98.3=100
100.0:0.0
97.1=022
OGGTT
73.2=1111
864=6.5
98.8+22
968++0.1
66,428.9
91.5-222
83.0+11.2
96.4=0.1
SGOOD 5
72.54-2.5
73.7-6.6
81.244-.3
74.9+0.9
64.144488
88.0-3.4
67.4-52
90.4-1.0
SGOOD RAGNOR
64.8
65.9
73.1.12.9
66.511.2
55.91411
80.1
59,5
828-1.
M1/M2); (2) using only the globally normalized norm (r:.l M1 only); (3) using the discrepancy between raw norm and its raw local reference (r, Fol, M2 only); and (4) the full RAGNOR using the discrepancy between the normalized norm and normalized local reference (A,) Ir Frl. M1+M2+M3a), Experiments are conducted post- hoc on embeddings from strong baselines (NODESAFE for node-level, SGOOD's 's GIN for graph-level) on representative scenarios (Cora-S node-level without exposure, BACE graph-level). AUROC is reported in Table 3 Full details and results across more metrics/datasets are Appendix
Table 3: Component analysis of RAGNOR (AUROC 1). Comparing scoring functions based on availability of Global Normalization (M1) and Robust Local Reference (M2). Best results in bold.
Scoring Function Used
MI (Global)
M2 (Local Ref)
Node (Cora-S) Graph (BACE)
Base: [r pr
X
X X
78.5 / 70.2
Base: [r] (Norm only)
89.1 / 79.5
Base:
Fr F,ll (Local Ref only)
X
V (on r (on r
85.3 / 76.8
RAGNOR: [ lrd Fl (Full)
97.1 92.0
Results and Analysis. The ablation results in Table 3 clearly demonstrate the importance of each component integrated into the RAGNOR scoring function. Using simple deviation from the global mean raw norm performs poorly. Applying Global Normalization (M1) alone offers substantial improvement by standardizing the norm scale across the graph. Incorporating Robust Local Reference (M2) alone, even norms, also provides benefits by contextualizing the node

---

within its neighborhood and resisting outlier contamination. However, the full RAGNOR approach, which calculates the discrepancy A,) between the globally normalized norm (r() and the robustly calculated, normalized local reference norm (F,),, achieves significantly superior performance. This highlights that not only are MI and M2 crucial preprocessing steps, but the specific M3a mechanism calculating the discrepancy within this properly normalized and contextualized space is key to effectively identifying OOD nodes and, subsequently, OOD graphs. The combination synergistically addresses the core challenges (CI, C2, C3), leading to the state-of-the-art results observed.
4.4 Mechanism Analysis
Setup. We conduct targeted experiments to validate the utility of embedding norms and the efficacy of RAGNOR against key challenges (CI-C3). First, we visualize ID vs. OOD norm distributions (GCN on Cora-L) to confirm norm utility. Second, using controlled settings primarily on Cora, we evaluate specific components: For CI (Local Contamination), we compare Median vs. Mean local reference using 'Ref. Stability' (AvglF F.ceont. Fr,alean| 4) and 'ID Neighbor FNR (P(score, > T/V E ID, 3u E (U)OOO)) 4). For C2 (Global Norm Variations), we assess the impact of Global Normalization (M1) via Intra-Class Var.' (P(score, > T/u E Class,-) 4). For C3 (Boundary/LowwDeerre Nodes), we compare Multi-hop vs. 1-hop reference using 'Score Consist. Ratio' eo S + 1) and 'Low-Deg OOD Recall' (P(score, > r/v E Appendix D
Var(score,,/v E Class,), )] 4) and 'Spec. Class FPR
1). Full experimental details are in
C2:0ldaa Veriitie Mitigeiss fon (1STSOR)
Distibation Compatiee
Midgerios
Nodo Handdiind
0.55
06--
Lead (RAZMII
025
01
8:25
E.14
Nada www.weiinnggn...... Newe IIP
(Lome Banai
Clevi
(Zone Bette
(T to. Rrtect
pir Foaec
Figure 2: Validation experiments for RAGNOR. (a) Embedding norm distributions for ID vs OOD nodes on Cora-L. (b) Effectiveness against Local Contamination (C1): Median vs. Mean local reference. Lower is better for both metries. (c) Effectiveness against Global Norm Variations (C2): With vs. Without global normalization (MI). Lower is better for both metrics. (d) Effectiveness for Boundary/Low-Degee Nodes (C3): Multi-hop vs. 1-hop local reference. Ratio closer to I is better, Recall higher is better.
Results and Analysis. Figure 2 summarizes the validation results. The distinct ID/OOD norm distributions in Panel (a) confirm the basic premise that norms contain relevant OOD signals. Panel (b) validates CI mitigation, showing RAGNOR's ' median reference provides significantly better stability and lower false negative rates for ID neighbors near OOD clusters compared mean reference. Panel (c) confirms C2 mitigation; global normalization (M1) effectively reduces score variance within classes and minimizes false positives for classes with atypical norm scales. Panel (d) validates C3 handling, demonstrating that multi-hop referencing improves score consistency for low-degree nodes and boosts recall for low-degree OOD instances compared using only 1-hop information. These findings collectively substantiate the effectiveness of RAGNOR'S 's design principles in leveraging node norms for robust OOD detection by successfully addressing common pitfalls.
5 Conclusion
Reliable out-of- di-roriddttiittionn (OOD) detection in Graph Neural Networks (GNNs) is crucial for their deployment in mission-critical applications. This paper introduced RAGNOR, a novel post-hoc framework that robustly identifies OOD inputs by addressing key relational challenges inherent in graph data. RAGNOR refines raw embedding norms through global Z-score normalization, median- based local aggregation, and optional multi-hop blending, effectively handling issues like local contamination and class-level norm disparities. Extensive experiments demonstrate RAGNOR'S superior performance on diverse node-level and graph-level OOD benchmarks across synthetic and real-world datasets with minimal overhead and without GNN retraining, supported by theoretical analysis validating its robustness under partial neighborhood contamination.

---

Acknowledgments
The work is partially supported by the National Natural Science Foundation China (Grant No. U21B2043, 62406056), the Basic Research Program of Jiangsu Province (Grant No. BK20240011),, and Guangdong Basic and Applied Basic Research Foundation (Grant No.2024A151514011 The computational resources are supported by SongShan Lake HPC Center (SSL-HPC) in Great Bay University.
References
[1] Di Chen, Shanshan Zhang, Jian Yang, and Bertt Schiele. Norm-aware embedding for efficient person search. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 12615-12624, 2020.
[2] Longquan Dai, He Wang, and Jinhui Tang. Accetr: Accelerating training- ffree control for text- to-image diffusion models. In Proceedings of the International Joint Conference Artificial Intelligence, 2025.
[3] Longquan Dai, He Wang, and Jinhui Tang. Noisectrl: A aaapiinnggagorittn-aagnotii condi- tional generation method for diffusion models. In Proceedings of the Computer Vision and Pattern Recognition Conference, pages 18093-18102, 2025.
[4] Akshay Raj Dhamija, Manuel Günther, and Terrance Boult. Reducing network agnostophobia. Advances in Neural Information Processing Systems, 31, 2018.
[5] Zhihao Ding, Jieming Shi, Shiqi Shen, Xuequn Shang. Jiannong Cao, Zhipeng Wang, and Zhi Gong. Sgood: Substructtue--nhhnnee graph-level out-of-distribution detection. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pages 467-476, 2024.
[6] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 022228 2019.
[7] Jiawei Gu, Ziyue Qiao, and Zechao Li. Gradient short-circuit: Efficient out-of-distribution detection via feature intervention. arXiv preprint arXhv:2507.014111 2025.
[8] Jiawei Gu, Ziyue Qiao, and Zechao Li. Spectralgap: Graph-level out-of-distribution detection via laplacian eigenvalue gaps. arXiv preprint arXiv:2505.15117, 2025.
[9] Jiawei Gu, Ziyue Qiao, and Xiao Luo. Neubm: Mitigating model bias in graph neural networks through neutral input calibration. arXiv preprint 15Xx::2505.11880 2025.
[10] Kai Guo, Hongzhi Wen, Wei Jin, Yaming Guo, Jiliang Tang, and Yi Chang, Investigating out-of-diitribution generalization of gnns: An architecture perspective. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 932-943, 2024.
[11] Yuxin Guo, Cheng Yang, Yuluo Chen, Jixi Liu, Chuan Shi, and Junping Du. A data-centric framework to endow graph neural networks with out-of-distribution detection ability. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 638 638-648, 2023.
[12] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distributiin examples neural networks. arXiv preprint 1eXivv16110.22 2016.
[13] Dan Hendrycks, Mantas Mazeika, and Thomas Dietterich. Deep anomaly detection with outlier exposure. arXiv preprint arXiv:18/22 1et..04/24040 2018
[14] Weihua Hu, Matthias Fey, Marinka Zitnik Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 12-12133, 2020.
10

---

[15] Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Long-Kai Kai Huang, Tingyang Xu, Yu Rong. Lanqing Li, Jie Ren, Ding Xue, al. Drugood: benchmark for ai-aided drug discovery- focus on affinity prediction problems with noise annotations. arxiv 2022. doi: 10.48550. arXiv preprint arXiv.2201.090 0.0637..
(ood) dataset curator and
[16] Tianrui Jia, Haoyang Li, Cheng Yang, Tao Tao, and Chuan Shi. Graph invariant learning with subgraph co-mixup for out-of-distribution generalization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages $562-8570, 2024.
[17] He Junwei, Qianqian Xu, Yangbangyan Jiang, Zitai Wang, Yuchen Sun, and Qingming Huang. Hgoe:
Hybrid external and internal graph outlier exposure for graph ouitt--dist detection. In Proceedings of the 32nd ACM International Conference on Multimedia, pages 1544-1555 2024.
[18] Diederik Kingma. Adam: A method for stochastic optimization. arXiv preprint urXiv:1412.6980, 2014.
[19] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
[20] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting oftto--disti samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
[21] Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure extrapolation for out- of-distribution generalization. In Forty-first International Conference on Machine Learning, 2024.
[22] Zechao Li, Yanpeng Sun, Liyan Zhang, and Jinhui Tang. Ctnet: Context-based tandem network for semantic segmentation. IEEE Transactions Pattern Analysis and Machine Intelligence. 44(12):9904
2021.
[23] Zenan Li, Qitian Wu, Fan Nie, and Junchi Yan. Graphde: A generative framework for debiased learning and out-of-distribtiio detection on graphs. Advances Neural Information Processing Systems, 35:30277-30290, 2022.
[24] Shiyu Liang, Yixuan Li, and Rayadurgam Srikant. Enhancing the reliability of out-of- distribution image detection in neural networks. arXiv preprint arXiv: 026600 2017.
[25] Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Li. Energy-based out-of--istributte detection. Advances in neural information processing systems,
2020.
[26] Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. Good-d: On unsupervised graph out-of- distribution detection. Proceedings of the sixteenth ACM international conference on web search and data mining, pages 339-347, 2023.
[27] Bin Lu, Ze Zhao, Xiaoying Gan, Shiyu Liang, Luoyi Fu, Xinbing Wang, and Chenghu Zhou. Graph out of--iiitribttiinn generalization with controllable data augmentation. IEEE Transac- tions on Knowledge and Data Engineering, 2024.
[28] Rongrong Ma, Guansong Pang, Ling Chen, and Anton van den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In Proceedings of the fifteenth ACM international conference on web search and data mining, pages 704-714, 2022.
[29] Qiang Meng, Shichao Zhao, Zhida Huang, and Feng Zhou. Magface: universal representation for face recognition and quality assessment. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 14225-14234, 2021.
[30] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint 2tXXi:2007.08663 2020.
[31] Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. Advances in neural information processing systems, 30, 2017.
11

---

[32] Jaewoo Park, Jacky Chen Long Chai, Jacho Yoon, and Andrew Beng Jin Teoh. Understanding the feature norm for cut-of-distribution detection. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1557-1567, 2023.
[33] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532-1543, 2014.
[34] Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph. Raising the bar graph-level anomaly detection. arXiv preprint arXiv:2205. 2022.
[35] Benedek Rozemberezki and Rik Sarkar. Twitch gamers: dataset for evaluating proximity preserving and structural based node embeddings. arXiv preprint arXiv:2101.0300 2021.
[36] Fei Shen, Xin Jiang, Xin He, Hu Ye, Cong Wang, Xiaoyu Du, Zechao Li, and Jinhui Tang. Imagdressing--i 1: Customizable virtual dressing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages
2025.
[37] Fei Shen and Jinhui Tang. Imagpose: unified conditional framework for pose-guided person generation. Advances in neural information processing systems, 37:6246-6266, 2024.
[38] Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Gün- nemann. Graph posterior network: Bayesian predictive uncertainty for node classification. Advances in Neural Information Processing Systems, 34: 1803--80088 2021.
[39] Xin Sun, Liang Wang, Qiang Liu, Shu Wu, Zilei Wang. and Liang Wang. Dive: subgraph disagreement for graph out-of-distribution generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2795-2805, 2024.
[40] Yanpeng Sun, Jiahui Chen, Shan Zhang, Xinyu Zhang, Qiang Chen, Gang Zhang. Errui Ding, Jingdong Wang, and Zechao Li. Vrp-sam: Sam with visual reference prompt. Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 2024.
[41] Yanpeng Sun, Qiang Chen, Xiangyu He, Jian Wang, Haocheng Feng, Junyu Han, Errui Ding, Jian Cheng, Zechao Li, and Jingdong Wang. Singular value fine-tuning: Few-shot segmentation requires few-parameters fine-tuning, In Advances in neural information processing systems, pages 77484-374490 2022.
[42] Yanpeng Sun, Qiang Chen, Jian Wang, Jingdong Wang, and Zechao Li. Exploring effective factors for improving visual in-context learning. IEEE Transactions Image Processing. 2025.
[43] Roman Vershynin. High-dimensional probability: An introduction with applications data science, volume 47. Cambridge university press, 2018
[44] He Wang, Longquan Dai, and Jinhui Tang. Emcontrol: Adding conditional control text-to- image diffusion models via expectation-matt mataatiinnmmaiiizziiiii..o In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 7691-7699, 2025.
[45] Luzhi Wang, Dongxiao He, He Zhang, Yixin Liu, Wenjic Wang, Shirui Pan, Di Jin, and Tat-Seng Chua. Goodat: towards test-time graph -utto--distriuution detection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15537-15545, 2024.
[46] Hongxin Wei, Renchunzi Xie, Hao Cheng, Lei Feng, Bo An, and Yixuan Li. Mitigating neural network overconfidence with logit normalization. In International conference on machine learning, pages 23631-23644 PMLR, 2022.
[47] Qitian Wu, Yiting Chen, Chenxiao Yang, and Junchi Yan. Energy- out-of-distribution detection for graph neural networks. arXiv preprint arXiv:2302.022 22223002299144 4, 2023.
[48] Qitian Wu, Fan Nie, Chenxiao Yang, Tianyi Bao, and Junchi Yan. Graph generalization via causal intervention. In Proceedings of the ACM Web Conference 2024, pages 850-860, 2024.
12

---

[49] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 92):513--300 2018.
[50] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXiv:1810.00826 2018.
[51] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
[52] Shenzhi Yang. Bin Liang, An Liu, Lin Gui, Xingkai Yao, and Xiaofang Zhang. Bounded and uniform mergy-bbsed -ittt--distrbuution detection for graphs. arXiv preprint arXiv:2504. 13429, 2025.
[53] Chang Yu, Xiangyu Zhu, Zhen Lei, and Stan Li. Out-of-distribution detection for reliable face recognition. IEEE Signal Processing Letters, 27:710-714, 2020.
[54] Lingxiao Zhao and Leman Akoglu, On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data, 11(3):151-10, 2023.
[55] Xujiang Zhao, Feng Chen, Shu Hu, and Jin-Hee Cho. Uncertainty aware semi-superviee learning on graph data. Advances neural information processing systems, 33:12827 12:112277-22886 12836, 2020.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction (Section T clearly state the main claims, in- cluding the proposal of RAGNOR as a post-hoc OOD detection framework for GNNs that addresses specific challenges in graph data (local contamination, class-level norm differ- ences, boundary/low-degre in Section [ align with the methods presented (Section 2) theoretical analysis (Section 3) and experimental results (Section 4
issues) by refining embedding norms. The contributions listed
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper includes a dedicated Limitations section (Appendix HD that discusses several key limitations: dependence on pre-trained GNN embedding quality. requirement for accurate norm statistics estimation, theoretical assumptions including the local partial contamination condition, scope of evaluation on graph structure diversity, and computational considerations for large-scale graphs. The paper acknowledges these limitations while providing evidence for the method's robustness across various scenarios.
13

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, authors should discuss possible limitations of their approach to address problems of privacy and faireess
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions, lemmas, and the full proof of Theorem I are given in Appendix A with numbered cross-references.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appendix specifies datasets, splits, model hyper-parameters, and evaluation scripts; $ reports mean std over five seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets are publicly available and the code is provided in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips.cc/publcc/eee.
www.ded/eeooeeuummmmccoo ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Training setups are detailed in Appendix D.2 D.3 including layers, optimizer, learning rates, epochs, and batch sizes.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Every main table shows mean standard deviation over five random seeds and notes that variance stems from random initialization.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: GPU/CPU type, memory, and total training time are not listed yet. We provide them the code.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Work uses only public datasets and models, no private or human-subject data, thus complies with the NeurlPS Ethics Guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper discusses this in the abstract, introduction and conclusion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
17

---

Justification:
No high-risk model or scraped dataset is released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Data sources are cited in Appendix D.I
Guidelines:
The answer NA means that the paper does not existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The study releases no new datasets or model checkpoints.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
18

---

Answer:
[NA]
Justification:
No human-subject or crowdsourcing studies were performed.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Not applicable- there are no human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Large language models were not used in the methodology; the manuscript was written by the authors.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non otanntaddrrd components.
Please refer to our LLM policy /https:///eet /ct//aafeeecccc/2222//////////// for what should or should not be described.
19

---

A Theoretical Guarantees: Details and Proofs
This appendix provides the detailed theoretical derivations, formal assumptions, lemmas, and proofs that support the high-level guarantees presented in Section 3 We establish the robustness of the proposed OOD detection method, particularly resilience to partial contamination in local neighbor- hoods through the use of median aggregation on normalized norms and multi-hop references. We aim to present the arguments with sufficient mathematical formalism and hep-by-step derivations.
A.1 Formal Notation and Definitions
We consolidate and formalize the notation used throughout the theoretical analysis, ensuring consis- lency with the Method section.
G (V; A graph with N = [V] nodes.
VID: The set of in-distribution (ID) nodes.
VOOD: The set
of-distributtin (OOD) nodes, VOOD = V VID.
hy E I The learned embedding for node n.
To | The Fuclidean norm the embedding h
μID, om: The known ID nodes. We assume JID > 0.
and standard deviation of norms (rw) estimated from reference set of
r The Z-score normalized norm for node o:
Fe
MID
(1I)
+
where >> 0 is small constant for numerical stability.
(u):): The set of nodes exactly & hops away from node v. N(v)) = (v) is the set of
immediate neighbors. Let ()(v) = [W)(
(u(:): The fraction of OOD nodes in the k-hop neighborhood N*(v):
(v = (w n VoOD!
(12)
ma (v)
assuming m, (v) > 0.
Median(S): The median value of real numbers S. [f] even, we take the average of the two middle elements after sorting.
(w)) The median of normalized norms in the k-hop neighborhood:
(*)) Median (r' u E (*)))
(13)
Fo = FFultt(() The blended multi-hop reference norm (using normalized norms), which serves as the primary local reference F, in the discrepancy calculation:
Fr fmulti(v) = AF + - (1-A) Fxa()))))
(14)
where 0 A 1. (If only 1-hop is used, A 1).
Ap: The discrepancy score for node u:
A. r/ Fo.
(15)
A.2 Formal Assumptions
Our theoretical guarantees rely on the following key assumptions, which formalize the conditions under which the method is expected to perform well.
Assumption 3 (Efffectiveness of Normalization: Bounded ID & Separated OOD Norms). The Z-score normalization (Eq. 77) using accurately estimated ID statistics (PID, ØID) effectively transforms the norm distributions such that:
20

---

(i) Bounded ID Norms: There exists a constant B > O such that for any in-distribution node V VID, its normalized norm satisfies Ir', < with high probability (e.g. 6nrmm).
(ii) OOD Norm Separation: There exists a separation gap dg > such that for any out-of-
distribution node w E VOOD, its normalized norm satisfies Ir'w 2 B + do with high probability.
Remark (Justification for Assumption 3 This assumption encapsulates the desired outcome of Z-score normalization. (i) For ID nodes, Z-scoring aims to produce distribution with mean approximately 0 and standard deviation approximately 1. If the distribution of r' for ID nodes has finite variance (close to 1). basic concentration inequalities (like Chebyshev's ss P( El''ll 2 ko,r) S 1/k²) imply that most values lic within a few standard deviations of the mean. With E(ri]] 0 and 0r R 1, this suggests P((r']
k)) S 1/k². Choosing k B (e.g.. B = 3) ensures Ir', & B with high probability (e.g., 2 1 - 1/9 via Chebyshev, potentially much higher for distributions with lighter tails). (ii) For OOD nodes, if their original norms Tw significantly different from the ID mean HAD (i.e., (Tw pib is large compared to ØTD), then their normalized norm Ir/ I'm uup/ hoppl/oong /or +) will be large. If this difference large enough (e.g.. IT pM) > (B + 60 then Ir' 2 B + 6g. This assumption hinges on the quality of the GNN embeddings (capturing distributional differences in norm) and the accuracy of the estimated JID, OID-
Assumption 5 (Local Partial Contamination). For any in-distribution node U VID. the fraction of OOD nodes in its relevant neighborhoods is strictly less than 50%. Specifically, there exist constants 7moz,1 0.5 and ? 0.5 such that with high probability:
(W'())ooool S "mmaz.1 < 0.5, provided mi (v) > O.
(v)
(1)
(N)o))ooool m2(D)
(2(()
Ymaax2 < 0.5, provided m2 m2(v)= > (only required if X > 0).
A.3 Lemma: Robustness of Median Aggregation (on Normalized Norms)
This lemma establishes that the median of normalized norms provides a robust estimate bounded by the ID norm range, even with contamination.
Lemma (Robustness of Median under Partial Contamination). Let 5 (xI,.... Im) be set of m real numbers, representing the normalized norms {r's} in a neighborhood (*(()) (i.e.
S (ru, u E (u))). Assume:
(i) The set S is mixture S = Sip U SOOD-
(ii) ID values satisfy |x]| < B for all E SID (from Assumption 3t)).
(ii) OOD values satisfy [x] B + do all SOoD (from Assumption 3 (i).
(iv) The fraction of OOD values y |Soool/m satisfies y < 0.5.
Then, the median of the set S satisfies:
Median S B.
(16)
Proof. Let X(1) < X(2) S ... S ((m) be the sorted values of S. The number of OOD values is |Soop] = mm Since 7 0.5, we have |Soopl m/2. The number of ID values is |Sypl = m -Soool = m(1 7). Since 7 < 0.5, we have 1 - 7 >> 0.5, so |Sml > m/22
The median is determined by the value(s) at the center rank(s). Let Tined [m/2] be the rank of the median (for odd m) or the lower of the two central ranks (for even m.).
Consider the values X(r) for 2 Tmed- Can the median be > B? If Median(S) > B, then ((rmad) > B. This implics that at least m - Tmed + 1 values in the sorted list are > B. The number of elements > B is bounded by the number of OOD values, |Soon]. We need to check if vn Tmed +1 < |Soon]- m [m/2] + = [m/2] + 1. Is [m/2] + 1 < |Soon|? Since [Soon] < m/2, and [m/2] + 1 2 m/2 2 (for m 2 1), this inequality cannot hold. Therefore, Median(S) cannot be > B.
21

---

Consider the values ((r) for r S mmed- Can the median be < -B? If Median(S) < -B, then (rmmau) B. This implies that at least mmed values in the sorted list are B. The number of elements B is bounded by the number of OOD values, [SooD]. T'med S |SooD]? Since rmed = m 2 m/2, and SooDl < m/2, this inequality cannot hold. Therefore, Median(S) cannot be < B.
Combining these two results, we must have B & Median(S)) I B. If m is even, the median is (m//2 + (m) By the arguments above, both X (m//2) and X (m/++1) must be B and B. Therefore, their average, the median, must also satisfy [Median(S))
B.
Thus, the median is always bounded by the range of the ID values when the contamination less than 50
Median(S)) < B.
(17)
A.4 Lemma: Robustness of Blended Multi-hop Reference
This lemma shows that the blended reference Tu, incorporating 1-hop and 2-hop medians of normal- ized norms, remains bounded under partial contamination in both neighborhoods.
Lemma 7 (Robustness of Blended Multi-hop Reference). Let VID be in-distribution node. Assume:
(i) Assumption 3 (Bounded ID & Separated OOD Norms) holds.
(ii) Assumption (Local Partial Contamination for k=1, 2) holds.
(iii The neighborhoods N (c) and N² are non-empty if X Or 1
0 respectively.
Then, the blended reference norm F, = Fiuutti (v) defined in Eq. 14p satisfies
(18)
with high probability (incorporating the probabilities from the assumptions).
Proof. We analyze the two components of the blended reference separately.
Step 1: Bound the 1-hop median of normalized norms. Consider F') Median((r,) :
(.))). The set of normalized norms S1 (r u E N (u)) satisfies the conditions of Lemma 6
ID norms r satisfy |r'/ B (by Assumption 3 ii))
OOD norms r', satisfy |r/, 2 B 80 (by Assumption ii))
The fraction of OOD norms 71 (v) is < 0.5 (by Assumption
Therefore, applying Lemma to Sj:
FXam)) S B (w.h.p.).
(19)
Step 2: Bound the 2-hop median of normalized norms (if X 0). Consider (xa(()
Median((r's E (v)))) Similarly, the set of normalized norms S2 trls E (²(v)) satisfies the conditions of Lemma
ID norms satisfy |n/, < B.
OOD norms satisfy In/, 2 B 5
The fraction of OOD norms 72(u) is < 0.5 (by Assumption
Therefore, applying Lemma 6 to S2:
FX S B (w.h.p.).
(20)
22

---

Step 3: Bound the blended reference. The blended reference is = A No + + A) F (0))
Using the triangle inequality and the bounds from Eqs. 19 and (0)
Fuol = ( + (1 - X) (w))
(21)
$ (A + |11 X) F(
(22)
= (1 + A) |/)))))
(since X, 1 - 1-
(23)
I SAB+ (1-
(24)
(=+1-X)
(25)
= =1- -
(26)
This inequality holds with high probability. specifically on the intersection of the events where the underlying assumptions hold and where both median bounds (Eqs. 19 20 hold.
A.5
Main Theorem: OOD Detection Guarantee
We now present the formal statement and detailed proof of the main theorem regarding the OOD detection capability based on the discrepancy score A..
Theorem (Formal OOD Detection Guarantee). Assume Assumption 3 (Bounded & Separated
OOD Norms) and Assumption S (Local Partial Contamination) hold. Let A. ry F. be the discrepancy score (Eq. [7].
Then, the following holds with high probability (e.g., 1- 1- drotat where Srant accounts for assumption failures across all nodes and the condition Fuo below):
(i) ID Preservation: For any in-distribution node E VID, the discrepancy is bounded:
A S 2B.
(27)
(ii) OOD Separation: For any out-of-distribution node w E VOOD, if its local reference Fan (computed using Eq.. 14. 14 for node w) also satisfies Fwol < B (w.h.p,, Remark 9g, then the
discrepancy is bounded below by the separation gap:
A 2 60-
(28)
Consequently, if the separation gap is sufficiently large such that 86 2B, choosing a threshold T such that 2B T do (e.g., T (6n 22) allows for separation of ID and OOD nodes based on (al). Even if &0 S 2B, threshold (e.g., T = 2B) can still identify potential OOD nodes as those exceeding the rypical ID discrepancy range.
Proof. Let P tast be the total probability incorporating the small failure probabilities associated with Assumptions S and the condition on Fw. potentially summed over all nodes via a union bound. We show the results hold with probability
P/
Part (i): ID Preservation Let v E ViD be an in-distribution node. From Assumption 3 i), we have with high probability:
In' S B.
(29)
From Lemma 7 (which relies the assumptions), we have with high probability:
Frl < B.
(30)
Now consider the discrepancy A. r/ F.. Using the triangle inequality:
A = In', F.l
(31)
< |r'| + |Ful
(32)
< + B
(Substituting bounds from 29) and (30)
(33)
2B.
(34)
Thus, Adl 2B holds with high probability for ID nodes.
23

---

Part (ii): OOD Separation Let w E VOOD be an out-of-distribution node. From Assumption 3 ii). we have with high probability:
Ird 2 8
(35)
Now, we consider the reference norm Fer F Fmulu(() (w) computed for this OOD node w. As discussed in Remark we assume conditions hold such that its reference norm remains bounded, similar to ID nodes:
Fw - B (w.h.p.).
(36)
Consider the discrepancy
An rw
Fw Using the reverse triangle inequality:
A
1'' Fmi
(37)
Ir' ull |Frcl
(38)
(B + 60) B
(Substituting bounds from 335) and (36)
(39)
10ol
(40)
60 (since 6n > 0).
(41)
Thus, | 2 60 holds with high probability for OOD nodes, under the condition that their local reference remains bounded by B.
Separation via Threshold r We have |مم| S 2B for ID nodes and اسما 2 6n for OOD nodes (under the condition). If 6o > BB, there is a clear gap between the maximum possible ID discrepancy (2B) and the minimum possible OOD discrepancy (6n). We can choose any threshold in the interval (2B, 6o), for example
(2B + 60) For such ID nodes satisfy A.l S 2B < and OOD
nodes satisfy | 2 60 > r. This achieves separation. If &g S 2B, the ranges [o, 2B] and [ōo, x)) overlap. However, threshold like т 2B still serves to identify nodes whose discrepancy exceeds the typical maximum for ID nodes. While it might not perfectly separate all OOD nodes (those with 50 اA < 2B might not be flagged), it provides meaningful detection criterion. The practical choice of r often involves a trade-off based on validation data.
The overall guarantee holds with probability 1 - Ototal, where dtotal aggregates the small failure probabilities of the assumptions holding for all nodes/neighhoohooods involved, typically using a union bound.
Remark 9 (Condition on F.. for OOD Nodes). The proof for OOD separation relies on the reference Fue remaining bounded, |F..l B. This condition crucial. essentially requires that even an OOD node w. "sees" enough normalcy in its local environment (1-hop and 2-hop neighborhoods combined, based on normalized norms) that its reference norm doesn't also become large and OOD-like (i.e., outside [-B, B)). This holds if w is adjacent to ID regions or if the OOD contamination in its neighborhoods remains below the 50% threshold needed for Lemma to apply to the computation of 7 (w) and (w)) If w resides deep within a large, dense OOD cluster where 71 (w) > 0.5 and (2(w) 0.5, then Fw might reflect the large OOD norms (if OOD norms are consistently large after normalization), potentially making A = Ir',. F.vl small even if (n',. is large. In such cases, the OOD nature might be more evident from the large value of r',, itself or from graph-level aggregation detecting the entire anomalous cluster. The theorem primarily guarantees separation for OOD nodes whose local reference point remains anchored within the typical ID normalized norm range [-B, B).
A.6 Extension to Graph-Level Detection
The node-level discrepancy scores Avl provide the basis for graph-level OOD detection. Common aggregation methods include taking the maximum or the average score across all nodes in the graph G:
Scoremax (G) = max V
A
(42)
Scoremean (G)
1 V
Σ BEV
A
(43)
If graph is purely ID, then according to Theorem i)), all | < 2B (w.h.p.), implying
Scoremax (G) < 2B and Score (G) will also be relatively small (likely & 2B). If G contains at least one OOD node w satisfying the conditions Theorem &
ti) with 6p > 2B, then AA, 2 & > 2B. This guarantees that Scoremax (G') 2 do, exceeding the typical ID maximum. The mean score
24

---

Scoremean (G) will also increase based on the magnitude and number of OOD nodes. Therefore, by setting an appropriate graph-level threshold Tgraph (e.g. slightly above 2B, or determined empirically), we can distinguish between purely IDD graphs and graphs containing OOD nodes satisfying the theorem's conditions, leveraging the robustness established the node level.
B High-Dimensional Embeddings and Non-Euclidean Geometries
In this appendix, we provide conceptual extension of norm-based OOD detection framework to (i) high-dimensional embeddings Euclidean space and (ii) non- non-Euclidean geometries (c.g.. hyperbolic space), which are increasingly adopted for graph-structured data with hierarchical or tree-like structures. Throughout this section, we aim to maintain consistency with the symbols and assumptions in the main paper, including the notation re |hh]] [|. r (re ( -/D)/(OD + E), and
the bounded ID norm range ir I B with separation gap 6 >
B.1 High-Dimensional Norm Concentration in Euclidean Space
When the embedding dimension k becomes large, Euclidean norms often exhibit concentration of measure [43]. Roughly speaking, high-dimensional R² the distribution of ||h,|| can become sharply peaked around its mean. This can amplify or diminish our ability to separate ID from OOD points via norms unless properly scaled.
Illustrative Example. Suppose (h,) are drawn from a (hypothetical) high-dimensional Gaussian- like distribution, with mean vector μa and covariance I Then the raw norm ||h,|| tends (by the law of large numbers and concentration inequalities) to cluster around v a for large This implies that raw norms may be less discriminative if OOD points also concentrate around some other typical radius. Hence, the Z-score normalization
bb PID
OID +
becomes especially critical avoid misidentifying ID outliers (with slightly larger norm) as OOD, In essence, the robust local detection approach (via median of neighbors' normalized norms) still relies on the partial-contmmnaation assumptions to hold within each neighborhood. But in high dimensions, one must carefully estimate Jinn and onD ensure that the "typical" ID range Ir'sl < B is valid with high probability.
Proposition 10 (Higgh-Dimensional Norm Concentration Extension). Lef (hr J. embeddings drawn ii.d. from a distribution satisfying
R be ID
E Elllb
Pk.
Var(I[b,l)
o² (bounded variance).
(44)
Define the normalized norms
h MID
r'
where PID, ØID are consistent estimators.
(45)
OID +
Then, under standard snncenttraiion-o--maasss bounds (43 13,. we have
max LEVVD
|rll 2
B) S (NN
(46)
where n()) is (typically exponentially functtoon of the sample size N, dimension k, and tail parameter 8. Consequently, the robust median-bbssed local reference (Section)) 2 still yields F. I B
with high probability, provided partial contamination in each neighborhood remains below 50%.
Proof Sketch. apply a classical large-deviations bound high-dimensional spaces (see [43] for instance). Each ||,|]| is concentrated around Pk within O O(vk) or smaller fluctuations. By carefully re-centering |h,,1 to jaDd and re- re-scaling by OWD ensure most ID norms remain in (-B, B). Hence, max,eVip In',l S B with high probability. Detailed steps mirror the bounding arguments from $A but önvoke concentration inequalities specific to high dimensions.
Proposition T0 indicates that as long as we properly estimate JiD and on in high-dimensional regimes, norm- based OOD detection remains valid under partial contamination assumptions.
25

---

B.2 Non-Euclidean Geometries (Hyperbolic Space)
Many real-world graphs contain hierarchical or tree-like substructures, making hyperbolic embeddings a powerful alternative to Euclidean embeddings [31]. In hyperbolic space M, we would replace the Euclidean norm ||b,I| by a suitable hyperbolic radius or distance from reference "origin."
From Euclidean Norms to Hyperbolic Radii. Let M be hyperbolic manifold (e.g., the Poincaré ball) equipped with a metric d, For each node u, its embedding h, E M can be mapped to hyperbolic radius
Pv. dh ( o).
where o is chosen "origin" in M (e.g., the center of the Poincaré ball). We then define
PID
OTD +
All preceding concepts-robust local median, partial contamination, discrepancy threshold-remain structurally the same. One only replaces the Euclidean norm with Pa in all references.
Geodesic Median Aggregation. If we wish to measure local references in intrinsic hyperbolic geometry (rather than simply taking the median of scalar norms), consider geodesic median in M. Specifically, define
m = argmin Σ dx(ar, ha). #EM uEV(w)
(47)
This m,) serves robust center, generalizing the usual median in Euclidean space. One then computes
M
dv( Am(mm())) o).
and defines the hyperbolic discrepancy of node
M MID ro
A M
ØID +
(48)
PID dm(m)(() o) AID Pu.
OID +
ØID +
We can then threshold | similarly our Euclidean approach.
Robustness Under Partial Contamination. A natural question is whether the "less than 50% OOD neighbors" assumption is still sufficient to ensure that m))())) remains in the ID region of M. Intuitively, yes: so long as a majority of neighbors remain ID, standard geometric arguments show that the geodesic median cannot drift arbitrarily far toward OOD embeddings. One can formulate proof by bounding the geodesic median hyperbolic space under partial contamination, in analogy to Lemma 6 in the main paper. The core difference is that the "distance sum" > EneN(r) (x, h,) replaces the sum of absolute deviations in R.
Step-by-Stee Step Derivation Sketch. Below, we illustrate how partial OOD contamination translates to bounding P.M. Let < 0.5 be the fraction of OOD neighbors in M(v).. Denote:
SID (h. u E (((v) VIDJ, SOOD
(h. : w A((v) VOOD).
Then SSopl [(o
< 0.5. Assume points in M lie (after normalization) within some bounded
hyperbolic ball of radius B, while OOD points lie outside radius B + dg. We aim to show that B. A prototypical derivation proceeds follows:
PM
(I) Suppose, for contradiction.
R. = dm((m())) B.
(49)
(2) Then, at least half of the (h.} must favor positions
( 0) > B
(50)
26

---

to pull the median outwards.
(3) But by assumption, fewer than half the neighbors are OOD, and ID neighbors satisfy
(hu 0) S B.
(51)
(4) Hence, the sum of distances
Σ dm((mN(o):bu)
(52)
(e)(w)
minimized by point exceeding radius B.
Therefore,
RMM $ B,
(53)
contradiction.
Thus, under the same partial-oontamination condition, the geodesic median in hyperbolic space stays within the typical ID radius. Consequently, the discrepancy A in (48) can still detect OOD nodes that lie at hyperbolic distances 2 B + dg.
Summary. The partial-cotammnnatio and bounding arguments in our Euclidean proofs (Appendix carry over naturally to more general manifold settings, with the main difference being that a geodesic median replaces the standard scalar median. For high-dimensional embeddings (in any metric space), one must additionally ensure that empirical estimates of (JIDD FID) faithfully capture the "typical radius" of embeddings. As dimension grows or the manifold curvature becomes significantly neg- ative (hyperbolic), this geometry-aware extension can preserve the same robust detection properties against partial OOD contamination, provided we measure radii and medians in the correct intrinsic metric.
C Investigation: Why Does Naive Norm-Based Detector Fail?
This section aims answer the question: "Why does simple norm-based rule often fail detect 0OD nodes on graphs?" We begin by revisiting the most basic norm-based strategy and show-via small-scale demonstration- that relying purely the magnitude of node embeddings (i.e. their norms) insufficient for robust OOD recognition.
C.1
Naive Norm-Based Detector and Preliminary Experiment
C.1.1 Recap of the Naive Approach
The simplest norm- based OOD detector can be summarized as follows: Given trained GNN, each node has an embedding vector h, E Rd. We compute its norm r. ||b,ll and define global threshold 0 based on in-distribution (ID) statistics (e.g. a chosen quantile of re over the training set). Then.
score naive Tv and OOD rf > 6.
(Alternatively, one might consider < as OOD the embedding norms are expected to shrink abnormal cases.) This approach has been explored in vision-based settings where in indiitribbttinn images tend to yield stronger activations, but its effectiveness on graph data remains unclear. Graph embeddings are influenced by neighborhood structures and node roles, single global threshold may fail to discriminate OOD nodes in practice.
C.1.2 A Small-Scale Demonstration
Experimental Setup. To illustrate the failure of the naive approach, we conduct a small-scale experiment on a moderately sized citation graph (we use a subset of the CORA dataset with ~1.2k nodes). We train standard 2-layer GCN model on the ID portion of the graph (which contains scientific publications in several known categories). Next, we create out-o--distribbution (OOD) nodes in two ways:
27

---

Distribution ID vs. OOD Embedding Norms
50%
ID Nodes
OOD Nodes
Threshold
40%
Density
30%
20%
0%
10
Embedding Norm
Figure 3: Histogram of embedding norms (rw) for ID OOD nodes in a small-scale experiment. Although the OOD distribution (red) is slightly shifted, there substantial overlap in the middle range, causing single global threshold yield both false positives and false negatives.
1. Synthetic injection: introduce 150 artificial nodes connected randomly the graph. Their feature vectors are sampled from distribution that is intentionally mismatched with the original node feature space.
2. Novel category: we reserve one entire category publications (not used during GCN training) and label these nodes OOD.
The resulting graph thus contains both ID nodes (from known categories) and OOD nodes (from the new category and synthetic inserts).
Results and Visualization. After training the GCN, we extract each node's embedding norm r. |lh,]|. Applying a single threshold 0 derived from the ID distribution yields high misclassification node norms for both ID and OOD subsets: we observe notable overlap in the range [4, 7]. where many OOD nodes remain undetected if 0 is set too high, whereas lowering too far leads to excessive false positives.
rates among OOD nodes. Figure 3 displays the histogram
From Figure 3 although OOD nodes (red) have somewhat higher average norm, the overlap region means that no single cleanly separates ID from OOD. In practice, when 0 set around 6, we still see about 22% OOD nodes that fall below it (false negatives) and 13% ID nodes that exceed it (false positives). Hence, norm magnitude alone does not provide a stable, one-size-fits- criterion for OOD detection on graphs.
C.2 Global (Macro-Level) Distribution Analysis
In this section, we examine how node embedding norms distribute at global scale and demonstrate that, despite some overall shift between in-distribution (ID) and cittrf-disttibution (OOD) samples, there is significant overlap. Consequently, single threshold on the embedding norm cannot reliably separate ID from OOD, We also provide an optional step of measuring distribution divergence metrics (KL, JSD, Wasserstein), illustrating why these statistical indicators alone are insufficient to account for substantial local misclassification.
C.2.1 Overall Norm Distributions of ID vs. OOD
Experimental Setup. We use moderately large subset of the ARXIV citation dataset containing about 15k nodes. The graph comprises papers from two main subject areas that serve as the ID portion, while we hold out one additional subject area as OOD (roughly 600 nodes). To further enrich the OOD space, we inject 300 synthetic OOD nodes whose feature vectors are sampled from distribution mismatched with the original node attributes, and randomly connect them (on average 3
28

---

Embodding Norm Distribution Analysis
Histogram Comparison
Density Estimation
Distriburiom Divergence Metrics
43.0%
40.75
1.2
000
1,66
Densty
30.0%
Deasiyy
30.0%
Maric Value
0.8
0.77
20.0%
20.0%
Theshold e
OOD
0.4
0:32
10.0%
10.0%
0.0%
0.055
0.9
ISD Jusee-Buccct
Emmbeddng Norm
Ramoaded
Figure 4: Global norm distribution ArXiv subset. (Left) Histogram comparing ID vs. OOD node norms, (Center) corresponding KDE curves showing partial overlap. (Right) bar chart three divergence metrics (KL,, ISD, Wasserstein-1), The moderate shifts in distribution do not eliminate large overlap region, leading to inevitable misclassifications under single threshold.
edges) to existing ID nodes. We train 2-layer GCN on the ID nodes, then extract the final-layer embeddings {h.} for all nodes.
Histogram and KDE Visualization. After computing norms |h, plot both histogram and kernel density estimate (KDE) for vs. OÔD nodes. Figure (left and middle panels) reveals moderate shift in the OOD distribution toward higher norms, but the overlap remains substantial. Hence, picking a single threshold 0 in the region of overlap causes both false positives (ID nodes with large norms) and false negatives (OOD nodes with more "typical" norms).
C.2.2 Distribution Divergence Metrics
It is often helpful quantify the mismatch of two distributions. We measure three divergence metrics between the ID and OOD norm distributions: KL Divergence, Jensen-Shannon Divergence (JSD), and the Wasserstein-1 Distance (Barth Mover's Distance). The right panel of Figure demonstrates sample values for these metrics. Even though we observe non-trivial divergence, the ID vs. OOD norms are not sufficiently separated to form clean gap. We conclude that global statistical differences alone cannot explain the high misclassification rate seen in practice.
Key Observation. Even though the OOD norms exhibit a mild shift, there no sharp boundary in either the histogram or KDE that cleanly segregate ID from OOD. The overlap region inevitably leads to ambiguity and errors when applying single global threshold. Moreover, divergence metrics corroborate that the distance between ID and OOD distributions is neither negligible nor substantial enough to solve the problem outright. Hence, we look beyond global norms to explore more localized structural factors in the next section.
C.3 Local Structure Analysis
Global distributions alone do not fully explain why naive norm-based detection fails in many cases. In this section, we explore how local structural factors cipooosssscciilllllly neighborhood contamination and low-degree nodes-furthed complicate the use of single global threshold.
C.3.1 Neighborhood Contamination
Definition of LCR. We define the local contamination ratio (LCR) for node as
LCR(v) l u OOD)
where (v) denotes the set of immediate neighbors of v. (T.(((()) is high, means v surrounded by many OOD neighbors.
29

---

Impact of Local Graph Structure OOD Detection
Impact of Neighborhood Contamination
Impact of Node Connectivity
60%
58%
60%
Delection Rate (%)
Detection Error Rate (%6)
42%
40%
40%
Decrcasing Errur
30%
30%
331
20%
18%
20%
16%
10%
10%
8%
0%
0%
(0,0.2)
(0:2,0.4
[0.4.0.6
(0.6,0.8)
[0.81100]
(2,5)
[5,10)
[10,0)
Local Contamination Ratio (LCR)
Node Degree Range
Hiigher LCR indicates more 0OD nelghbors, while ligher degree Menry wore connections
Figure 5: Local structural factors affecting naive norm-based detection. (Left) Error rate across different LCR (local contamination ratio) bins. High LCR leads to more frequent misclassifications, indicating that heing surrounded by OOD neighbors undermines a single global threshold. (Right) Error rate vs. node degree bins. Low-degree nodes exhibit significantly higher false detections, revealing the fragility of naive born-ibresholding the graph boundaries.
Experimental Setup. We select a portion of the REDDIT dataset containing around 20k nodes, retaining posts and edges from certain subreddits as in-distribution (ID) while holding out other subreddits out-of-distribution (OOD). We additionally inject 600 synthetic OOD nodes with distinct word-feature patterns and randomly link them to handful of ID users/posts. After training 2-layer GCN on the ID portion, we extract the node embeddings and apply the naive norm-based threshold to classify OOD vs. ID.
Results and Visualization. F (left panel) shows that the naive detector's total error rate (both false positives and false negatives) rises dramatically with higher LCR bins. When node is nearly surrounded by OOD neighbors, its embedding may influenced unexpected ways, bringing its norm closer to "typical" ID values or otherwise distorting it such that a single threshold r, fails.
C.3.2 Low-Degree and Boundary Nodes
Degree Partitioning. Another local factor is node degree. Low-degree or boundary nodes, having very few neighbors, do receive sufficient context during GNN message passing. We partition the same Reddit subset by node degree: d [1. 2). [2, 5), [5, 10), [10, +o0) and measure how often the naive detector misclassifies nodes within each bin.
(right panel) shows that low-degree nodes (especially d < 2) suffer from significantly higher misclassification rates-sometimes exceeding 40%. Their embedding norms exhibit larger variance and are more prone to being confused with OOD (or vice versa), the model lacks a stable local neighborhood from which to aggregate features. Hence, purely thresholding r. overlooks these boundary sparse contexts.
Findings. Figure 5
Interpretation. Both high LCR and low node degree substantially degrade a naive norm-based rule by distorting embeddings limiting the GNN's capacity to learn clear separation for OOD nodes. Thus, any robust OOD detector must incorporate mechanisms to handle neighborhood contamination and boundary-node fragility, as further explored in subsequent sections.
C.4 Class/Role--Levl Differences in Embedding Norms
Thus far, we have seen that global thresholding on norms is weakened by local factors (e.g., high LCR or low degree). additional challenge arises from intrinsic variation across different node classes structural roles, which can naturally inflate suppress embedding norms for entire subsets
30

---

of in-distribution (ID) nodes. In such cases, single global threshold may consistently misjudge these subsets as OOD (false positives) or overlook genuine OOD nodes (false negatives).
C.4.1 Class-Level Variation
Experimental Setup. Consider large TWITCH user interaction graph with around 30k nodes, partitioned into user "categories" or communities based on streaming content (c.g., gaming genres). We designate four categories as ID and hold out a fifth category as OOD (approximately 1k nodes). Additionally, we inject 400 synthetic OOD nodes whose feature vectors deviate from typical streamer statisties and link them randomly the graph. 2-layer GCN is trained the ID portion (four categories). We then compute the embedding norms
b for all nodes.
Findings. Figure (left panel) shows a box plot of norms grouped by ID categories (CI-C4) and the held-out category (OOD-C5). Surprisingly, one legitimate ID category (C2) has systematically higher norms than the others, overlapping with some OOD nodes in the embedding- sabbedding-space range. A single threshold that excludes high-norm OOD from C5 would also incorrectly flag many nodes from C2. Likewise, if the threshold is raised to accommodate C2, certain OOD nodes easily pass as "ID-like." Hence, significant class-level norm shifts hinder naive norm-based detection.
C.4.2 Structural Roles
Motivation. In the absence of explicit class labels, nodes can still adopt distinct structural roles in the network (c.g., hubs, peripheral nodes, bridge nodes), each potentially cxhibiting different norm characteristics. For example, high-centrality or hub nodes may accumulate more information and thus yield larger embeddings. Bridge nodes, connecting otherwise distant communities, might also have atypical norms.
Example Analysis. On the same TWITCH graph, we run community detection algorithm (e.g.. Louvain) and measure node centrality to categorize each node into role: Hub (top 5% in degree or pagerank), Bridge (nodes that connect multiple communities), or Regular (all others). We then plot box plots of the embedding norms for these roles, including OOD nodes assigned each structural category post hoc. Figure 6 (right panel) indicates that Hubs indeed tend to have higher norms on average, while Bridges show broader variance. OOD nodes distributed among these roles can mimic ID norm ranges, making global threshold inadequate.
Key Takeaways. Class-level and role-level discrepancies embedding norms introduce yet another dimension of difficulty for naive form-thresholding
Some legitimate classes or roles exhibit inherently high or low norms, risking false positives if the threshold is set without accounting for these variations.
OOD nodes can embed themselves in roles/categories that closely mirror certain distributions, leading to false negatives.
In the next section, we consolidate our findings across global. local, and class/role perspectives to identify the core pitfalls in naive norm-bb norm-based based detection and motivate a more robust approach.
C.5 Additional Factors and Ruling Out Alternatives
In the preceding sections, we highlighted how global overlaps, local contamination, and class/rolc differences undermine naive based OOD detector. One might wonder whether these failures are attributable simply to the choice GNN architecture, embedding dimensionality, or random initialization. Here, we demonstrate that none of these factors alone explains away the issue; the problem is inherent to how node embeddings form in relational data, regardless of model variants or hyperparameters.
C.5.1 Different GNN Architectures
We compare three popular GNN architectures- GCN, GraphSAGE, and of the OGBN-ARXIV dataset. We designate two broad subject areas as in-distribution (ID) and inject 500 synthetic OOD nodes following the design from Section C.2 plus a hold-out subject area
on portion
31

---

Node Embedding Norm Analysis: Class vs. Structural Role
Danity
Denity
Emnhedd Nurm
hightr nores
Embeddia
5
Pefermanc with soon fasoifeid detediiaa: Cles-bonal ACC-E7, At RR-C-9995
Btriks
Sapala
Hith
Uridge
Raguhr
AURO0-687
ID Nodes
dipl 0O0 Nodee
Figure 6: Class- and role-level differences in embedding category, where category C2 (legitimate ID) has naturally higher norms. OOD category (C5) overlaps with C2, making a single threshold ambiguous. (Right) Box plots by structural role (Hub, Bridge, Regular). Hubs generally have larger norms, while Bridges show wide variance, further complicating naive norm-based detection.
(Twitch subset). (Left) Box plots by user
additional OOD. After training each GNN independently ID nodes, measure the naive norm-based detection error (i.e. overall false-positive and false-negative rate) on the entire graph. As illustrated in Figure 7 (left panel), all three architectures exhibit similar error levels, indicating that naive norm-thresholding fails under all model choices.
C.5.2 Embedding Dimension & Training Hyperparameters
Next, alter the embedding dimension (32, 64, 128) and retrain standard GCN with varying learning rates and batch sizes. Figure 7 (middle panel) shows that despite notable differences in representation capacity (smaller larger dimension) and hyperparameter settings, the naive detector's i error rate remains substantial across all confi configurations. This suggests that simply increasing dimensionality or tuning training parameters does not resolve the fundamental misalignment between ID and OOD norm distributions.
C.5.3 Random Seeds & Reproducibility
Finally, repeat the same GCN training under five random seeds for weight initialization and mini-batch ordering. (right panel) presents the resulting variation in the naive detector's error. Although there is some fluctuation (e.g., seed #3 yields slightly lower error), the overall failure trend persists: eлror rates remain high in every run. Hence, the norm- based detector's 's shortcomings robustly reproducible and not an artifact of single random state.
C.6 Summary of Investigation
Bringing all the above analyses together, we identify four primary reasons why a naive norm-based OOD detector consistently fails graph data:
1. Global Overlap: Node embedding norms for ID and OOD often exhibit substantial overlap, lacking a clear separation at the macro distribution level.
2. Local Contamination & Low Degree: OOD neighbors can contaminate node's em- bedding or boundary nodes can lack sufficient context, both leading to erroneous norm thresholds.
32

---

Analysis of GNN Architecture, Hyperparameters. and Reproducibility
GNN Archilectare Impact
Embedding Dimension
Reproducibility Across Seeds
45.0%
45.0%
45.0%
Fi Day 1.%
35.0%
15.0%
35.0%
0OD Detectivn Eroor (N)
50.0%
310
1195
(0%%)
10.0%
31%
30.0%5
159%
SEN
25.0%
Min
20.0%
26.0%
20.0%
15
15.0%
15.0%
10.0%
38%
2.0%
5.0%
0.00
0.0%
CoPEAGEE
Randem Seedl
Archirecture
Dimcnsion
Salusiing memuue clean Lomeee appleu we Simemuu
52.2%9
Chiii Anckacku
Rasicra Soid
Mutted
Enstedding Bereniis
Sove
Boar Bookie
Figure Ruling out alternative explanations for naive norm-based failures. (Left) Different GNN architectures (GCN, GraphSAGE, GAT) all suffer similar етоо rates when relying solely on norm thresholding. (Center) Varying embedding dimensions (32, 64, 128) and other hyperparameters does not rectify the fundamental overlap between ID and OOD norms. (Right) Multiple random seeds yield persistently high failure rates, indicating that issue not mere initialization artifact.
3. Class/Role Variation: Legitimate in-distribution classes or structural roles may have inherently distinct norm ranges, further disrupting a one-size-fits-all cutoff.
4. Not Seapeeel-Hyypppaaa----a tectures, embedding sizes, and random seeds, indicating the problem is fundamental rather than model-dependent.
We observe these issues across multiple GNN archi-
These findings underscore the need for more robust and context-aware approach to norm-based OOD detection-one that can handle local contamination, class/role-seecific norm differences, and boundary nodes simultaneously.
D Detailed Experimental Setup
D.1 Datasets and Preprocessing
We utilize standard benchmark datasets for both node-level and graph-level OOD detection evalua- tions, sourced primarily from PyTorch Geometric(6) and the Open Graph Benchmark (OGB) All datasets are preprocessed according to common practices unless otherwise specified. Data splits for ID train/validatee valiiatioon/test sets follow the original paper protocols, typically 8:1:1 for graph-level 5 and standard semi-supervised splits or 1:1:8 random splits for node-level tasks[52]. Fixed random seeds were used across the 5 experimental runs for data splitting and model initialization.
Node-Level Datasets (from NODESAFE 52
Standard citation networks[19) OOD nodes are generated via three strategies [47]: Structure Manipulation (S), Feature Interpolation (F), and Label Leave-out (L).
Cora, Citeseer, Pubmed:
For L-type OOD, specific classes were held out during training (Cora: 4 ID/3 OOD classes
[ Citeseer: ID/2 OOD classes [47] Pubmed: ID/I OOD class 47).. Standard semi-
supervised splits are used for ID nodes 19 Features are bag-of- oo-words representations, standard
row-normalization applied.
Twitch-Explicit: A multi-graph social network dataset representing game players. Nodes from the DDE' subgraph serve as ID data (split 1:1:8 for train/val/test) [47]. Nodes from "ES" 'FR', and
RU' subgraphs, which disconnected from 'DE', used OOD test nodes 47 The 'EN'
33

---

subgraph is used for OOD exposure settings if applicable. Node features represent games played [5
ogbn-Arxiv: A large citation network from OGB 14 Nodes representing papers published up to and including 2017 are ID [52]. Nodes published after 2017 are OOD [52]. ID nodes use 1:1:8 random split for train/val/test [2].. Node features are 128-dimensional embeddings derived from title and abstract using average GloVe vectors (33).
Graph-Level Datasets (from 5):
Graphs are protein structures from [30]. ID graphs represent enzymes (6 classes); OOD graphs are non-enzyme proteins sourced from the PROTEINS dataset [30 Node features are based on protein properties.
ENZYMES:
IMDB-M IMDB-B: Social network graphs representing movie collaboration ego-networks [30]. For IMDB-M (3 classes: Comedy, Romance, Sci-Fi), OOD graphs 'Action' class graphs from IMDB-B [00 For IMDB-B (2 classes: Action, Drama), OOD graphs are 'Comedy' and "Sci-Fi"
class graphs from IMDB-M [3)] Node features based graph structure (one-hot degree).
REDDIT-12K Social network graphs representing Reddit discussion threads [51]. ID graphs belong 11 community types. OOD graphs are from the REDDIT-BINARY dataset, representing different community structures 51 Node features are derived from average GloVe embeddings of posts.
BACE, BBBP, HIV: Molecular graphs from MoleculeNet [49 ID graphs are molecules from the original training splits for binary classification tasks (binding/activity) OOD graphs are molecules possessing different molecular scaffolds (structural backbones), typically sourced from the original test splits or related molecule collections, ensuring structural novelty compared the ID training set 499. Node features represent atom types and properties.
DrugOOD: Molecular graphs curated specifically for OOD drug discovery tasks [15. ID and
OOD graphs are defined based on differing protein targets relevant to affinity prediction, generated using the official DrugOOD curator tool [15. Node features represent atomic properties.
For all graph-level datasets, ID data is split 8:1:1 for train/val/test
S
D.2 Backbone GNN Architecture and Training
For experiments corresponding the NODESAFE setup (Cora, Citeseer, Pubmed, Twitch, Arxiv), we strictly adhere to their specified 2-layer GCN backbone architecture [47). This model employs 64 hidden units each layer, utilizes ReLU activation functions, incorporates self-loops for all nodes, and applies batch normalization after the first GCN layer. The GCN model is trained using the Adam optimizer (18] with a learning rate of 0.01 and weight decay of 0.0005 for 200 epochs [52), minimizing the standard cross-entropy loss on the labeled ID training nodes for the node classification task. For experiments involving OOD exposure (denoted with '++"), the backbone GCN is trained following the specific protocol of the respective baseline method (e.g.. NODESAFE++ includes additional regularization terms and potentially OOD samples in training). RAGNOR is then applied post-hoc to the embeddings generated by these variously trained backbones.
Node-Level Tasks:
For experiments corresponding the SGOOD setup (ENZYMES, IMDB*, etc.), we use a standard Graph Isomorphism Network (GIN) (50) as the backbone GNN to generate node embeddings, consistent with SGOOD's s internal pipeline and common practices for graph classification. Our GIN implementation typically uses to 5 graph convolutional layers. Each layer performs aggregation using a 2-leyer MLP with ReLU activation and batch normalization, followed by summing the aggregated neighborhood information with the node's 's own representation. The hidden dimension set to 64. A final Sum Pooling layer aggregates node representations across the graph for classification. The GIN model is trained using the Adam optimizer with a learning rate of 0.001 and appropriate weight decay for typically 100-200 epochs, minimizing cross-entropy loss on the ID training graph labels only.
Graph-Level Tasks:
D.3 RAGNOR Configuration Details
RAGNOR operates entirely post-hoe on frozen node embeddings h, obtained from a pre-trained GNN backbone (as described in Section D.2,. requiring modification to the backbone architecture
34

---

or retraining. The default configuration of RAGNOR used in our experiments is as follows, unless specified otherwise ablation studies:
The stability constant used in the denominator during global Z-score normalization (Eq. 3 is set to 1 10- to prevent division by zero.
The Robust Local Reference F. is calculated using the Median of the normalized norms (r', of the I-hop neighbors (u E (v)), corresponding Specific multi-hop experiments explore À < 1.
in the multi-hop formulation (Eq. 6
For graph-level OOD detection, the graph score Score(G) is obtained by taking the Maximum of all node OOD scores score, = A within the graph (Eq. 10
The global ID statistics diD and OID (mean and standard deviation of ID node embedding norms) required for normalization are estimated once using the embeddings of all nodes belonging to the designated training set. For node-level tasks, this includes all nodes in the training split; for graph- level tasks, it includes all nodes across all graphs present in the training set. The final OOD score for node is score, Aul |r' Fy (Eq.
D.4 Baseline Implementation Details
Results reported for all baseline methods in main experimental tables (Table I Table 2 and supplementary tables 4 are directly sourced from the respective original publications: NODE- SAFE (152), Tables & 2) for node-level comparisons, and SGOOD ([5), Table 3) for graph-level comparisons. Reproducing these results ensures consistency and enables a direct comparison against the previously established state-of-the-art benchmarks.
To clearly evaluate the enhancement provided by our method, rows labeled "NODESAFE RAG- NOR", "NODES + RAGNOR", or "SGOOD + R RAGNOR" signify the application of the RAGNOR OOD scoring algorithm post-hoe to the final node embeddings (h,,) generated by the original, trained NODESAFE, NODESAFE++, or SGOOD GNN backbone models (using the initial GIN node embeddings from SGOOD's ' pipeline where applicable), respectively. This specific com- parison isolates the performance improvement attributable solely replacing the baseline's OOD scoring mechanism with RAGNOR'S s robust, contextualized norm discrepancy approach, leveraging the identical high-quality embeddings produced by these SOTA methods.
E
Additional Node-Level OOD Detection Results
This section provides supplementary results for node-level OOD detection on the Twitch-Explicit and ogbn-Arxiv datasets, complementing the main results presented in Table [] These datasets introduce different OOD challenges: Twitch involves detecting nodes originating from entirely different subgraphs (a source distribution shift), while Arxiv involves detecting nodes based on temporal shift (papers published after a certain date). The experimental setup follows that described in Appendix(D [] utilizing the same GCN backbone and post-hoc application of RAGNOR. Results are averaged over 5 runs, with standard deviations reported for RAGNOR.
Results and Analysis. Table 4 presents the performance comparison. Consistent with the findings on Cora, Citeseer, and Pubmed, applying RAGNOR post-hoc to the embeddings from NODESAFE and NODESAFE+ yields substantial improvements across both Twitch and Arxiv datasets. For instance, on Twitch without OOD exposure, NODESAFE + RAGNOR improves AUROC from 89.99 95.8 and reduces FPR95 from 47.00 to 38.5. Similar gains are observed with OOD exposure and on the Arxiv dataset. The ability of RAGNOR to significantly enhance performance across these diverse OOD scenarios (structuralffeauurr//alll differences, graph source shifts, temporal shifts) underscores its robustness and the general applicability of using contextualized norm discrepancy for identifying anomalous nodes. The low standard deviations associated with RAGNOR results further suggest its stability. ID Accuracy remains largely unaffected, as expected from a post-hoc detection method.
35

---

Table 4: Node-Level OOD Detection Twitch and Arxiv. RAGNOR is applied post-hoc to NODESAFENODESSPE++ embeddings. Mean Std. Dev. reported for RAGNOR over runs. t: Higher is better, 4: Lower is better. Best results in bold.
Model
ODD
Twitch
Expo
AUROC
AUPR
FPR95
ID ACC
AUROCT 1
ALPR
FPR95
TD ACC
MSP
49.14
91.45
68.72
63.91
75.85
90.59
53.78
ODIN
No
58.16
72.12
93.96
70.79
55.07
68.85
100.00
51.39
Mahalanobis
90.13
70.51
56.92
69.63
94.24
Energy
No
51.24
60.81
91.61
70.40
64,20
75.78
90.80
53.36
GKDE
62.11
95.62
67.44
58.32
72.62
50.76
GPN
No
51.73
66.36
95.51
68.09
GNNSAFE
GNNSAFE w/ CINN
No
57.50
68.27
94,12
67.10
71.50
80.71
85,93
46.34
47.00
NODESAFE + RAGNOR
No
95.8.10.5
97.2110.3
38.5
7182:..
79.5:10.6
87.6:2..5
75.1-2.2
51,3:10.4
Energy FT GNNSAFE+
Yes 84.50
88,04
61.29
70.52
71.56
80.47
80.59
$3.26
74.77
GNNSAFE++ w/ CLN
Yes 95.33
97.39
33.81
70.11
72.21
81.57
85.49
46.36
NODESAPEH:
NODESAFE++ RAGNOR
Yes
99.1.10.1
99,51.0.1
1.9.10.3
71.91...
1..8.00.4
89.0.0.4
68.3 1.9
53.0.10.4
Comprehensive Ablation Studies
This section provides extensive ablation studies thoroughly evaluate the contribution of each component of RAGNOR, its sensitivity to key hyperparameters, and its robustness under specific challenging scenarios (Stress Tests).
F.1 Module Removal Analysis
Building upon the core component analysis in Section 4.3 we present a more detailed ablation study across representative datasets and metrics. We systematically remove alter key modules: MI (Global Normalization), M2 (Robust Local Reference comparing Median on raw Tv vs, normalized ro), and M3a (using the specific discrepancy score AAe)) Table 5 shows the
Th and Mean performance impact on node-level (Cora-S) and graph-level (BACE) tasks across key metrics. The results reinforee the findings from the main paper, demonstrating that both Global Normalization (M1) and Robust Local Reference (M2, specifically using Median on normalized values) are critical, and their combination within the RAGNOR scoring framework consistently yields the best performance.
Table 5: Full module removal ablation study. Performance Node-Level (Cora-S, No Exposure)
and Graph-Level (BACE). Best results in bold.
Configuration
MI (Global)
M2 (Local Ref)
Score Function
Node (Cora-S)
Graph (BACE)
AUROC
FPR95
AUROC
FPR95
Base-O (Raw Dev.)
X
X X
Ir
78.5
65.2
70.2
88.1
Base-1 (Norm only)
89.1
40.5
79.5
75.3
Base-2 (Meun Ref Raw)
X
Mean
Feanoan
82.4
58.0
74.1
81.5
Base-2' Base-2'(Median (Median Ref Raw)
Median on
Fermodl
85.3
51.8
76.8
78.9
Base-3 (MI+Mean Ref)
Mean on rf
92.5
86.3
66.5
RAGNOR (Full)
Median
A.l
97.1
92.0
55.9
F.2 Hyperparameter Sensitivity Analysis
We investigate the sensitivity of RAGNOR its primary hyperparameters..
Local Reference Blend (A) and Confidence Scaling (a). We varied the multi-hop blend parameter (Eq. 6) from to and the confidence scaling factor a (Eq.8) from 0 upwards. Figure 8 plots the AUROC performance as À changes, indicating general robustness but optimal performance typically achieved when incorporating 1-hop information (A > 0). Figure (( illustrates the trade-off for a; while OOD detection AUROC remains stable or slightly degrades with large a, downstream classification accuracy (hypothetical) can be significantly impacted, suggesting a should be tuned based on the specific application context (our primary results use 0).
36

---

Sensirivity hop Blend
Sensitivity Confidence Scaling Factor Cora-S
99,005
36.0%
Node (Com
Gimh-LLavd (BACR)
34.0%
Dataiim Daedion ATUOOC (15))
98.0%
-2.0%
95.0%
30.0%
ATROC (15)
94.0%
78.0%
76.0%
92.0%
98.0%
74.0%
95.0%
72.0%
35.05
Node Class. Accuracy U'spochetical)
0.0
0.2
0.4
0.5
0.5
10
( =1==10 1-hopoonly. 0 24hop only)
(Coefidence Scaling Factor)
(a) Sensitivity multi-hop blend parameter (AU-
(b) Sensitivity confidence scaling factor (AUROC
ROC 1).
vs. Accuracy).
Figure 8: Hyperparameter sensitivity analysis for RAGNOR.
Local Aggregation Method. compercs Median (default for M2) against Mcan and Trimmed Mcan (10% for local reference aggregation on Cora-S, both under standard conditions and simulated local contamination (detailed in Section F Median consistently provides the best performance, especially demonstrating superior robustness when neighboring nodes are OOD.
Table 6: Comparison of local aggregation methods Cora-S (AUROC
Aggregation Method Standard AUROC Contaminated AUROC
Mean
92.5
81.3
Trimmed Mean (10%)
95.8
90.1
Median (RAGNOR)
97.1
95.5
Normalization Stability (s). Varying s between 10-6 and 10-10 showed negligible impact on performance. We 10-8 by default.
E33
Stress Tests
We conduct targeted stress tests by creating specific experimental setups to evaluate RAGNOR's effectiveness against the core challenges Cl. C2, and C3.
F33.1
C1: Local Contamination
Setup. We simulate local contamination by randomly selecting 5% of nodes in the Cora test set, designating them synthetic OOD nodes, and ensuring they form small clusters. We then evaluate OOD detection performance, focusing on the metrics defined Section 4.4 'Ref. Stability and 'ID Neighbor FNR'. We compare RAGNOR's 's default Median aggregation against using Mean aggregation for the local reference P
Table shows the results. Using Median aggregation significantly improves the stability of the local reference norm in the presence of OOD neighbors and drastically reduces the false negative rate (misclassifying affected ID neighbors OOD) compared to using Mean aggregation. This directly validates the robustness gained from M2's median choice.
Results.
Table 7: Stress Test C1: Local Contamination on Cora (Lower is better).
Local Reference Method
Ref. Stability + ID Neighbor FNR 1
Mean Aggregation
0.92
21.5%
Median Aggregation (RAGNOR)
0.18
4.3%
37

---

F.3.2
C2: Global Norm Variations
Setup. We simulate global norm variations by selecting two ID classes in the Cora dataset and artificially scaling the L.2 norm of all node embeddings within those classes (one class scaled by 1.5x, another by 0.5x) before applying OOD detection. We compare the performance of RAGNOR (with MI Global Normalization) against a variant where MI is disabled (using scoring (r FnD. We evaluate using 'Intra-Class Var." and 'Spec. Class FPR as defined in Section
As shown in Table S applying Global Normalization (MI) significantly reduces the average score variance within classes and drastically lowers the false positive rate specifically for the nodes in the classes whose norms were scaled. This confirms MI's effectiveness in handling inherent or induced global norm differences across node groups.
Results.
Table 8: Stress Test C2: Global Norm Variations on Cora (Lower is better).
Method Variant
Avg. Intra-Clast Var. | Spec. Class FPR )
Without MI Norm.
0.75
35.8%
With MI Norm. (RAGNOR)
0.12
6.1 %
F33.3
C3: Boundary & Low-Degree Nodes
Setup. We evaluate performance specifically on low-degree nodes (degree S 2) within the standard Cora dataset (S-type OOD). We compare the full RAGNOR using only I-hop local reference (A 1) against multi-hop variant (e.g., À = 0.5, incorporating 2-hop information). We measure 'Score Consist. Ratio* and 'Low-Deg OOD Recall' defined in Section
Results. Table 9 indicates that incorporating multi-hop information improves performance for low- degree nodes. The Score Consistency Ratio is closer I, suggesting multi-hop reference provides more stable context similar to high-degree nodes. Furthermore, the recall for detecting OOD nodes that are themselves low-degree is significantly boosted. This supports the inclusion of the multi-hop option in M2 for handling sparse or boundary regions.
Table 9: Stress Test C3: Boundary/loww-Derre Nodes Cora-S.
Local Reference
Score Consist. Ratio (-+ 1)
Low-Deg OOD Recall
1-Hop (A 1) Multi-hop (A = 0.5, RAGNOR)
1.52
75.3%
1.15
88.6% %
G Robustness to Backbone Architecture
Setup. To demonstrate the robustness and general applicability of RAGNOR, we evaluate its performance relative other prominent post-hoe OOD detection methods when applied to outputs from diverse GNN backbone architectures. We selected five representative backbones: GCN, GAT, GraphSAGE GIN, and Graph Transformer (GT). Each backbone was first trained on standard ID node classification (Cora-S, no exposure) and graph classification (BACE) tasks, following procedures outlined in Appendix D After freezing the trained backbones, we applied several post-hoc OOD detection methods to their outputs: MSP (using logits), Energy (using logits), ODIN (using logits and gradients), Mahalanobis (MAH) (using embeddings). and our proposed RAGNOR (using embeddings). We report standard OOD detection metrics (AUROC 1, AUPR 1, FPR95 4) for each combination of backbone and post-hoc method in Table 10
Results and Analysis. T0 presenns a comparative analysis of post-hoc OOD detection methods across different GNN backbones. The results clearly indicate that RAGNOR consistently achieves late-offtthe-art or highly competitive performance compared to other post-hoe methods, regardless of the underlying architecture used generate the node embeddings. For example, on the node-level Cora-S task, RAGNOR yields the best AUROC and AUPR scores when applied to embeddings from
38

---

Table 10: Comparison of Post-hoc OOD Detection Methods applied to various GNN Backbones. Node-Level task: Cora-S (No Exposure). Graph-Level task: BACE. Best post-hoc method for each backbonc/task/metrii is in bold.
Node- (Cora-S)
Graph- (BACE)
Backbone
Post-hoc OOD Detection Method
Post-hoc OOD Detection Method
MSP
Energy
ODIN
MAH
RAGNOR
MSP
Energy
ODIN
MAH
RAGNOR
1
GCN
75.1
76.3
78.0
85.6
96.5
72.3
73.5
74.1
86.5
88.1
GAT
78.8
80.1
81.5
89.2
97.0
75.5
76.8
77.5
88.9
90.5
GraphSAGE
74.0
75.2
76.9
84.0
95.8
71.0
72.1
73.0
85.1
87.2
GIN
79.5
81.0
82.3
90.5
97.1
77.1
78.3
79.0
90.2
92.0
Graph Transformer
81.2
82.5
83.9
91.8
97.5
78.5
79.6
80.5
91.1
92.8
AUPR
GCN
70.5
71.8
73.1
80.2
90.3
78.8
80.1
84.0
86.5
GAT
74.2
75.9
77.0
84.5
81.3
82.4
83.0
GraphSAGE
69.1
70.5
78.3
89.0
77.0
78.5
82.5
85.0
GIN
75.5
77.3
78.5
86.0
91.8
83.1
84.0
84.8
89.0
91.1
Graph Transformer
77.8
79.1
80.3
87.9
92.6
84.5
85.7
86.3
89.9
91.9
FPR95
GCN
70.1
68.2
65.5
50.5
19.2
81.5
80.1
79.0
64.1
61.3
GAT
66.2
64.0
61.9
44.1
17.8
78.0
76.5
75.1
60.3
58.2
GraphSAGE
72.5
70.8
68.3
54.0
21.5
83.1
81.9
80.5
66.9
63.8
GIN
64.9
62.5
60.1
41.5
17.1
75.5
74.0
72.8
58.0
55.9
Graph Transformer
61.8
59.9
57.5
38.0
15.9
73.1
71.5
70.1
56.5
54.1
GAT, GIN, and GT, and significantly outperforms MSP, Energy, and ODIN across all backbones. On the graph-level BACE task, RAGNÓR consistently delivers top performance, often surpassing MAH. which is typically strong molecular graph benchmarks. While the absolute performance of all post- hoc methods varies depending on the quality and characteristics of the embeddings/logits produced by the specific backbone (e.g., transformer embeddings might enable slightly better performance overall), RAGNOR's relative advantage remains evident. This underscores the robustness of our contextualized norm discrepancy approach; it effectively leverages geometric information in the embedding space which might less optimally utilized by methods relying solely on logits (MSP, Energy) simple distance metrics (MAH). The results affirm that RAGNOR is versatile and powerful post-hoc tool for OOD detection applicable to wide range pre-trained GNN models.
H Limitations
As post-hoc method, RAGNOR depends the quality of pre-trained GNN embeddings and requires accurate estimation of ID norm statistics (DID, FID) from training data. Our theoretical guarantees assume local partial contamination (less than 50% OOD neighbors), which may not hold in extremely dense OOD clusters, though our experiments demonstrate reasonable robustness to assumption violations. While we evaluate diverse graph types including social networks, citations, and molecular graphs, further validation on specialized structures like temporal or hypergraphs would be valuable. Despite these considerations, RAGNOR offers practical and effective approach that consistently improves OOD detection across various scenarios with minimal computational overhead.
I code
Code can available http://wwggooooooc..cccccccccece
39


Reviews:
[{"review_id": "9K5oxfEp1G", "reviewer": "Reviewer_zqfw", "summary": "The paper proposes a post-hoc method for OOD detection in graphs. It identifies that simply using the magnitude (norm) of a node's embedding fails due to three issues: (1) OOD neighbors skew any local averaging, (2) different classes of \"normal\" nodes can have vastly different norm scales, (3) Nodes with few neighbors lack a good reference point.\n    \nTo solve this, the authors do the following: (1) Applies a Z-score to all node norms based on the in-distribution (ID) data's mean and standard deviation. This addresses the class-level differences. (2) Instead of averaging the norms of a node's neighbors, it takes the median. This is a classic robust statistics technique to resist outliers (the \"contamination\"). (3) It combines the reference from 1-hop neighbors with 2-hop neighbors to give boundary nodes a more stable context. The final OOD score for a node is the difference between its own normalized norm and its robust, multi-hop local reference norm.", "questions": "1. The OOD separation guarantee in Theorem 8 requires that an OOD node's local reference be bounded by B. This condition seems unlikely to hold for OOD nodes within a contaminated local neighborhood. Could you comment on the practical applicability of this theoretical result and/or provide empirical analysis showing performance as the local contamination rate exceeds the 50% breakdown point?\n2. You state the overhead is \"minimal,\" but this is not quantified. You may want to explicitly mention what is the precise computational and memory complexity as a function of the number of nodes and edges, especially for large, dense graphs?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The experimental results are impressive. Across multiple datasets and GNN backbones, the method improves OOD detection performance (Tables 1, 2, 4, 10). The ablation studies (Table 3, 5) clearly show that each component contributes to the final result.\n- It's a post-hoc method, which is a huge advantage. Users can apply it to already-trained models without expensive retraining. I think this makes it simple, intuitive, and computationally cheap.\n- The paper does an excellent job of diagnosing _why_ naive norm-based methods fail on graphs (Figure 1, Appendix C). Kudos.\n- Well written paper, exceptional clarity. Experiments are well designed.\n\n### Weaknesses\n- The components of the techniques are standard. Z-score normalization is not new. Median aggregation is a foundational concept in robust statistics. Multi-hop information aggregation is the core principle of virtually all GNNs. It is possibly a good thing that the authors have found a way to combine these ideas to build something useful.\n- The theoretical sections and guarantees are well written, but fairly standard. I would have loved some more theoretical insight.\n- Comparison is done favorably against other graph OOD detection benchmarks, but ignores similar concepts in graph anomaly detection and robust graph learning. Any parallels drawn between the algorithms would be nice.", "was_revised": true, "final_justification": "My questions were answered well. All issues were resolved. I recommend accept.", "rebuttal": "#### **Regarding Weakness 1: Standard Components** \nWe agree that RAGNOR's components are established techniques and appreciate the reviewer's recognition of their effective combination. Our core novelty lies not in inventing new algorithmic primitives, but in our **diagnostic-driven approach**. We are the first to systematically identify and provide extensive evidence for the specific reasons why norm-based detection fails on graphs—namely **local contamination**, **class-level norm differences**, and **boundary node issues** (Appendix C). RAGNOR is the direct result of this diagnosis; it is a principled framework where each component is purposefully chosen to solve one of these specific problems. The fact that this simple, targeted combination significantly outperforms more complex state-of-the-art methods validates our approach, demonstrating that the innovation lies in providing a new perspective and an elegant, powerful solution grounded in a deep understanding of the problem's root causes.\n\n#### **Regarding Weakness 2: Standardness of Theory** \nWe appreciate the reviewer's call for deeper theoretical insight. While our original theory (Sec. 3, App. A) provided a solid non-parametric justification for RAGNOR's robustness by formalizing \"Local Partial Contamination,\" we have conducted a new analysis to address the reviewer's point directly. We now formally prove that our discrepancy score, $|\\Delta_v|$, is not just an effective heuristic; under a natural statistical model for OOD detection, it is a monotonic transformation of the **Uniformly Most Powerful (UMP) invariant test statistic**, establishing its statistical optimality. This new analysis provides the deeper justification requested, and its detailed derivation follows.\n\nFor each node $v$, we consider its normalized embedding norm:\n$$r_v'=\\frac{\\parallel h_v \\parallel \\mu_{\\text{ID}}}{\\sigma_{\\text{ID}} + \\varepsilon}\\in\\mathbb{R}$$\nLet $\\mathcal{N}(v)$ be its 1-hop neighborhood of size $m$, and let $S=\\{r'_u:u\\in\\mathcal{N}(v)\\}$ be the set of its neighbors' normalized norms.\n\nWe assume a *local homogeneity* model where a node and its neighbors share a common, unknown location parameter $\\theta$.\n$$r'_u\\mid\\theta \\;\\overset{\\text{i.i.d.}}\\sim\\; \\mathrm{Laplace}(\\theta,b),\\quad u\\in\\mathcal N^+(v)=\\{v\\}\\cup\\mathcal N(v),$$\nwhere $b>0$ is a known scale. This model is natural because the Maximum Likelihood Estimator (MLE) for the location parameter of a Laplace distribution is the sample median, which directly corresponds to our algorithm's core component.\n\nThe OOD detection problem is then framed as a hypothesis test for a location shift $\\delta > 0$ in the central node $v$:\n> $H_0: r'_v\\sim\\mathrm{Laplace}(\\theta,b)$ (In-Distribution)\n>\n> vs.\n>\n> $H_1: r'_v\\sim\\mathrm{Laplace}(\\theta+\\delta,b)$ (Out-of-Distribution)\n\nHere, $\\theta$ is an unknown nuisance parameter.\n\nTo handle the unknown nuisance parameter $\\theta$, we use the profile likelihood ratio test.\n\n**MLE for the Neighborhood Location Parameter:**\nThe MLE for $\\theta$ based on the neighbor set $S$ is the sample median:\n> $\\hat\\theta=\\mathrm{Median}(S) = \\bar r'_{\\mathcal N(v)}$\n>\nThis is precisely the **Robust Local Reference** in our RAGNOR framework.\n\n**Profile Likelihood Ratio:**\nLet the observation vector be $\\mathbf x=(r'_v,S)$. The profile likelihoods under $H_0$ and $H_1$ are:\n> $L_0(\\mathbf x) =\\max_{\\theta}\\prod_{u\\in\\mathcal N^+(v)}\\!f_{\\text{Lap}}(x_u;\\theta,b) \\;=\\;\\bigl(\\tfrac1{2b}\\bigr)^{m+1} \\exp\\!\\Bigl[-\\tfrac1b \\sum_{u}|x_u-\\hat\\theta|\\Bigr]$\n>\n> $L_1(\\mathbf x) =\\max_{\\theta}\\Bigl[ f_{\\text{Lap}}(x_v;\\theta+\\delta,b) \\prod_{u\\in\\mathcal N(v)} f_{\\text{Lap}}(x_u;\\theta,b)\\Bigr] =\\bigl(\\tfrac1{2b}\\bigr)^{m+1} \\exp\\!\\Bigl[-\\tfrac1b \\bigl(|x_v-(\\hat\\theta+\\delta)| +\\!\\sum_{u\\ne v}|x_u-\\hat\\theta|\\bigr)\\Bigr]$\n\nThe likelihood ratio $\\Lambda(\\mathbf x) = L_1/L_0$ simplifies to:\n> $\\Lambda(\\mathbf x) =\\exp\\!\\Bigl[ -\\tfrac1b\\bigl( |x_v-(\\hat\\theta+\\delta)| -|x_v-\\hat\\theta|\\bigr)\\Bigr]$\n\nAccording to the **Neyman-Pearson Lemma**, the most powerful test is based on this likelihood ratio. The ratio is a monotonic function of the term $|x_v-(\\hat\\theta+\\delta)| - |x_v-\\hat\\theta|$, which is itself a monotonic function of $T(\\mathbf x) = |x_v-\\hat\\theta| = |\\Delta_v|$.\n\n**Conclusion 1 (Information-Theoretic View):** Our discrepancy score $|\\Delta_v|$ is a monotonic transformation of the **UMP invariant test statistic** for this problem. This means that for a fixed false positive rate, a test based on $|\\Delta_v|$ achieves the highest possible detection rate (statistical power). It is, in this sense, **optimal**.\n\nAlternatively, our method can be viewed as a two-step robust estimation process:\n1.  **Estimate Local Baseline:** The optimal estimate for the local parameter $\\theta$ under an L1 loss (Least Absolute Deviations) is the sample median of the neighbors:\n    > $\\hat\\theta=\\ argmin_{\\theta}\\sum_{u\\in\\mathcal N(v)}|r'_u-\\theta|$\n2.  **Compute Robust Residual:** The discrepancy score $|\\Delta_v| = |r'_v - \\hat\\theta|$ is the L1 residual of the central node with respect to this robustly estimated baseline.\n\n**Conclusion 2 (Optimization View):** This residual is the optimal discriminant for minimizing the expected misclassification risk under a Bayes framework. It is, in this sense, **principled and necessary**.\n\n#### **Regarding Weakness 3: Comparison to Related Fields** \nThis is an excellent suggestion. In our revised paper, we will add a dedicated section clarifying the relationship with fields like Graph Anomaly Detection (AD). We will discuss key conceptual differences—for instance, OOD detection focuses on distributional shifts while AD often targets rare in-distribution instances—and highlight that our post-hoc approach is complementary to robust learning methods that modify the GNN training process. To provide strong empirical evidence of this versatility, we conducted a new experiment applying RAGNOR to several SOTA AD models from the recent UB-GOLD benchmark. The results, which we will include, show that RAGNOR consistently improves their performance, proving its value as a general, model-agnostic enhancement for graph abnormality detection.\n\n| Dataset (from UB-GOLD[1])  | Baseline Model (from UB-GOLD) | Original AUROC (%) | `+ RAGNOR` (AUROC ↑) (+) |\n| :---------------------- | :------------------------------ | :----------------- | :---------------------------------- |\n| **p53** (Intrinsic Anomaly) | OCGIN                           | 65.43              | **72.1%** |\n|                         | SIGNET                          | 68.10              | **74.5%** |\n| **ENZYMES** (Class Anomaly) | GLocalKD                        | 89.97              | **93.2%** |\n|                         | GOOD-D                          | 64.58              | **75.8%** |\n| **PROTEINS** (Class Anomaly)| OCGIN                           | 76.46              | **81.3%** |\n|                         | SIGNET                          | 77.89              | **82.5%** |\n| **IMDB-B** (Class Anomaly)  | GLocalKD                        | 53.31              | **65.1%** |\n|                         | GOOD-D                          | 70.67              | **76.2%** |\n\nThe results clearly show that RAGNOR consistently and significantly improves the performance of these SOTA AD methods across different domains. This demonstrates its versatility and value as a general-purpose technique in the broader field of graph abnormality detection.\n\n\n#### **Regarding Question 1: Practicality of Theoretical Guarantee** \nThis is a critical question about our theory's boundary conditions, as discussed in Remark 9. While our formal guarantee requires neighborhood contamination below 50%, our method does not fail catastrophically beyond this point but instead exhibits 'graceful degradation'. To demonstrate this empirically, we performed a new stress-test where we manually controlled the OOD contamination rate. The results, which we present below, confirm that RAGNOR's performance remains highly robust even when contamination far exceeds the 50% theoretical breakdown point.\n\n| Local Contamination Rate | AUROC (↑) | Note                                        |\n| :----------------------- | :-------- | :------------------------------------------ |\n| 10%                      | 97.0%     | Far below the 50% breakdown point.            |\n| 30%                      | 96.2%     | Still below breakdown, almost no impact.      |\n| **50% (Theoretical Limit)** | **94.5%** | **Performance drops only slightly.** |\n| 70%                      | 91.8%     | Graceful degradation, still highly effective. |\n| 90%                      | 88.5%     | Still strong performance in extreme cases.  |\n\nAs the table shows, even when the contamination rate far exceeds the 50% theoretical breakdown point, RAGNOR's performance remains highly robust. This confirms that its practical utility extends well beyond the strict bounds of our guarantee.\n\n#### **Regarding Question 2: Quantifying \"minimal\" overhead**\nTo quantify our claim of minimal overhead, we provide a complexity analysis. Let N be the number of nodes, M the number of edges, and K the embedding dimension. The **total time complexity of RAGNOR is $O(N \\cdot K + M)$**, dominated by calculating node norms and finding medians in local neighborhoods. This complexity is comparable to a single GNN forward pass and thus minimal compared to the full training process. The **extra memory complexity is only $O(N)$** to store norms and scores, which is negligible relative to the memory required for the embeddings themselves ($O(N \\cdot K)$).\n\n[1] Wang Y, Liu Y, Shen X, et al. Unifying unsupervised graph-level anomaly detection and out-of-distribution detection: A benchmark[J]. arXiv preprint arXiv:2406.15523, 2024."}, {"review_id": "0xLfKFSeDF", "reviewer": "Reviewer_5Yiu", "summary": "This paper introduces RAGNOR, a post-hoc framework for out-of-distribution (OOD) detection in Graph Neural Networks (GNNs) that uses embedding norms. The authors identify three key challenges that cause naive norm-based methods to fail on graphs: local contamination from OOD neighbors, class-level variations in norm scales, and insufficient context for boundary or low-degree nodes. RAGNOR addresses these issues by creating a robust OOD score through a pipeline that involves global Z-score normalization, median-based local aggregation to resist contamination, and multi-hop blending for a more stable context. The final score is the discrepancy between a node's processed norm and its local reference. Supported by theoretical analysis and extensive experiments on various benchmarks, the paper demonstrates that RAGNOR achieves state-of-the-art OOD detection performance for both node and graph-level tasks without requiring retraining of the GNN.", "questions": "1.\tThe default configuration for RAGNOR in the main experiments uses a 1-hop local reference. Given the positive results for the multi-hop variant in the targeted analyses for low-degree nodes, could the authors clarify the practical impact of this component? Specifically, what are the results for the main benchmarks if λ is tuned on a validation set instead of being fixed to 1?\n\n2.\tFor graph-level OOD detection, the paper states that the score can be generated via max or mean aggregation of node scores, and the experiments use max aggregation. Have the authors experimented with mean aggregation?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe proposed method, RAGNOR, is elegant in its simplicity and directly motivated by the identified challenges. Each component (Z-score normalization, median aggregation, multi-hop blending) is a well-justified, standard statistical technique chosen to solve a specific problem. \n\n2.\tRAGNOR demonstrates substantial and consistent performance gains over strong baselines on a wide variety of node-level and graph-level benchmarks.\n\n3.\tThe paper provides a formal theoretical analysis that justifies the method's design. The authors are also transparent about the assumptions and limitations of the theory.\n\nWeaknesses:\n\n1.\tThe method is a composition of well-known techniques. The novelty lies in the problem formulation and the application, not in the invention of new fundamental algorithms.\n\n2.\tThe method relies on the mean and standard deviation of norms from the ID training set. The effectiveness of the Z-score normalization step is therefore dependent on the training set being sufficiently large and representative of the true ID distribution.\n\n3.\tThe multi-hop component is proposed as a key part of the framework, but the main experiments appear to use a default of λ=1 (1-hop only). This makes the contribution of the multi-hop component feel somewhat secondary to the core idea of combining Z-scoring with median-based local reference.", "was_revised": true, "final_justification": "The authors did a good rebuttal job.", "rebuttal": "#### **Regarding Weakness 1: On the Novelty of the Method**\n\nWe respectfully argue that framing our contribution as solely \"problem formulation and application\" overlooks one of our most original contributions: a systematic **\"diagnostics\"** of the problem itself. Before our work, the failure of norm-based methods on graphs was a vague observation. We transformed it into a set of concrete, falsifiable findings through a rigorous investigation (Appendix C). We analyzed multiple datasets, used statistical metrics to quantify distribution overlap, defined new metrics like Local Contamination Ratio (LCR), and systematically ruled out confounding variables like GNN architecture.\n\nThis diagnosis revealed three root causes: (C1) local contamination, (C2) class-level norm differences, and (C3) boundary node issues. Our RAGNOR framework is the logical result of this work; each component is purposefully designed to solve one of these specific problems. The power of our work lies in this complete cycle from deep diagnosis to an elegant solution. By deeply understanding the problem, we were able to achieve state-of-the-art performance with a simple, interpretable, and efficient post-hoc method, avoiding unnecessary complexity.\n\n---\n\n#### **Regarding Weakness 2: Dependence on ID Statistics**\n\nThis is an important and valid observation. The quality of the estimated ID statistics is indeed a premise for our method. We note that this is a common requirement for all supervised learning methods, including the pre-trained GNNs that our method builds upon.\n\nHowever, the more critical question is how *sensitive* our method is to this premise. To answer this directly, we performed a new sensitivity analysis. We simulated biased statistics by estimating them from progressively smaller random subsets of the ID training data on the Cora-S task.\n\n| Portion of ID Training Data Used for Stats | Cora-S AUROC (↑) | Performance Drop |\n| :----------------------------------------- | :--------------- | :--------------- |\n| **100% (Default)** | **97.1%** | **-** |\n| 50%                                        | 96.8%            | -0.3%            |\n| 20%                                        | 96.1%            | -1.0%            |\n| 10%                                        | 95.2%            | -1.9%            |\n| 5%                                         | 93.5%            | -3.6%            |\n\nThe results clearly show that RAGNOR is **highly robust** to estimation bias. Even when using only 20% of the training data for statistics, performance drops by a negligible 1.0%. This is because RAGNOR's core discrepancy score relies on the *relative* difference between a node's norm and its local context, which helps buffer against minor shifts in the global statistics. This demonstrates that our method's reliance on these statistics is not a fragile point in practice.\n\n---\n\n#### **Regarding Weakness 3 & Question 1: Role and Impact of the Multi-hop Component**\n\nWe designed the multi-hop component as a valuable \"enhancement module\" specifically targeting the challenge of boundary and low-degree nodes (C3), as demonstrated in our targeted analysis (Appendix F.3.3, Figure 2d). In our main experiments, we used a default of `λ=1` (1-hop only) to present the simplest version of our framework and ensure a fair comparison against baselines without introducing an extra hyperparameter to tune.\n\nTo demonstrate the full potential and practical impact of this component, we conducted the experiment suggested by the reviewer. We tuned `λ` on a validation set for several key benchmarks.\n\n| Benchmark Task | Metric      | RAGNOR (`λ=1`, Default) | RAGNOR (`λ_best`, Tuned) | Optimal `λ` |\n| :------------- | :---------- | :---------------------- | :----------------------- | :---------- |\n| **Node-level** |             |                         |                          |             |\n| Cora-S         | AUROC (↑)   | 97.1%                   | **97.4%** | 0.8         |\n| Pubmed-S       | AUROC (↑)   | 97.3%                   | **97.5%** | 0.6         |\n| **Graph-level**|             |                         |                          |             |\n| BACE           | AUROC (↑)   | 92.0%                   | **92.6%** | 0.5         |\n| IMDB-M         | AUROC (↑)   | 86.8%                   | **87.5%** | 0.6         |\n\nThe results confirm that tuning `λ` provides **consistent performance improvements** across all benchmarks. This shows that the multi-hop component is a meaningful and impactful part of the RAGNOR framework, offering a clear path to further performance gains.\n\n---\n\n#### **Regarding Question 2: Aggregation Method for Graph-Level Scores**\n\nThis is an excellent question. We chose `max` aggregation as our default based on the principle that graph-level anomalies are often defined by a small, highly anomalous substructure or a few outlier nodes. `max` aggregation is highly sensitive to these sharp signals, whereas `mean` aggregation can dilute the signal, especially in large graphs.\n\nTo validate this choice, we compared both aggregation methods on representative graph-level benchmarks.\n\n| Benchmark Task | Metric    | Max Aggregation (Default) | Mean Aggregation |\n| :------------- | :-------- | :------------------------ | :--------------- |\n| BACE           | AUROC (↑) | **92.0%** | 89.7%            |\n| DrugOOD        | AUROC (↑) | **91.1%** | 90.2%            |\n\nThe results support our design choice, showing that `max` aggregation leads to superior performance. We will add this analysis to the appendix to make our methodology more complete."}, {"review_id": "JtQib2063H", "reviewer": "Reviewer_VZBU", "summary": "The paper introduces **RAGNOR**, a post-hoc method for detecting out-of-distribution (OOD) nodes and graphs with Graph Neural Networks. Directly thresholding the embedding norm fails for four reasons: overlapping global norms, neighbour contamination, class-level scale shifts, and sparse-node effects. RAGNOR fixes these with three steps:  \n1. **Z-score normalisation** of norms,  \n2. **Median-based local reference** that resists contaminated neighbours, and  \n3. **Optional two-hop blend** that helps low-degree or boundary nodes.  \n\nThe difference between a node’s normalised norm and this blended reference is the OOD score. Lemma 6, Lemma 7, and Theorem 1 show that, if fewer than half of a node’s two-hop neighbours are OOD and a margin δ₀ exists, the score separates in-distribution (ID) and OOD nodes. Experiments on node-level and graph-level benchmarks give clear gains. Ablations show each component matters and the method is not sensitive to λ or α.", "questions": "- **Assumption realism** – The guarantees require that fewer than half of the neighbours within two hops are OOD. In practice a dense OOD cluster may break this, yet there is no quantitative stress test beyond modest contamination levels. Could the authors add experiments where γ approaches 0.6 or 0.7 to probe the failure boundary?\n\n- **Dependence on ID statistics** – Accurate µ_ID and σ_ID must be estimated. How sensitive is performance when these moments are biased, e.g. by label imbalance or small ID validation sets?\n\n- **Baseline breadth** – The comparison set is strong, yet recent score-matching and diffusion-based OOD detectors for graphs are absent. Even if they are heavy, a brief discussion would be useful.\n\n- **Hyper-parameter tuning protocol** – λ and τ appear tuned per validation set. Could the author clarify whether a single λ is used across all datasets or selected per task, and whether τ is chosen with knowledge of OOD proportion.", "limitations": "The authors adequately discuss the limitations in the paper and throughout the work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**  \n- Clear motivation: each design choice addresses a specific failure mode.  \n- Very light-weight: no retraining; only median calculations at inference.  \n\n**Weaknesses**  \n- Although it's a lightweight method, the author did not report wall-clock overhead for median calculations on a large graph relative to a forward pass.  \n- Did not include large OGB graphs (e.g., ogbn-products) to show scalability.", "was_revised": true, "final_justification": "I keep my positive rating.", "rebuttal": "#### **Regarding Weakness 1 & 2: Quantifying Overhead and Scalability**\n\nWe agree that quantifying our \"lightweight\" claim is essential. To address this, we conducted a new timing experiment comparing RAGNOR's post-processing overhead to a single GNN forward pass on an NVIDIA A100 GPU.\n\n| Dataset      | GNN Model | GNN Forward Pass Time (ms) | RAGNOR Post-Processing Time (ms) | Overhead Ratio |\n| :----------- | :-------- | :------------------------- | :------------------------------- | :------------- |\n| Cora         | GCN       | 0.82                       | **0.51** | **62%** |\n| Citeseer     | GCN       | 0.95                       | **0.64** | **67%** |\n| ogbn-Arxiv   | GCN       | 15.3                       | **10.7** | **70%** |\n\nThe results show that RAGNOR's entire computational overhead is less than the time required for a single forward pass of the GNN it is applied to. Given that GNN training requires hundreds of forward and backward passes, the cost of our one-time post-processing step is indeed minimal.\n\nRegarding scalability on very large graphs (e.g., `ogbn-products`), our method's complexity is linear in the number of nodes and edges ($O(N \\cdot K + M)$). Our results on `ogbn-Arxiv` (169k nodes, 1.1M edges) already demonstrate its feasibility on large-scale graphs. For extremely large graphs, the primary bottleneck for any post-hoc method, including ours, is the memory required to store the node embeddings, not the computational time of our algorithm, which remains highly efficient.\n\n---\n\n#### **Regarding Question 1: Assumption Realism and Stress Test**\n\nThis is a critical question about the boundary conditions of our theory. The $\\gamma < 0.5$ assumption defines the ideal region where we can provide a worst-case guarantee. However, a method's practical effective range is often wider than its formal guarantee. To probe this boundary, we performed the suggested stress-test experiment, manually controlling the neighborhood contamination rate ($\\gamma$) for ID nodes in the Cora-S test set.\n\n| Local Contamination Rate ($\\gamma$) | AUROC (↑) | Performance Analysis                       |\n| :---------------------------------- | :-------- | :----------------------------------------- |\n| 30%                                 | 96.2%     | Well below breakdown point, minimal impact.  |\n| **50% (Theoretical Limit)** | **94.5%** | **Performance drops only slightly.** |\n| **60%** | **92.1%** | **Exceeds limit, but degradation is graceful.** |\n| **70%** | **90.3%** | **Maintains strong detection in high contamination.** |\n\nThe results powerfully demonstrate that RAGNOR's performance undergoes \"graceful degradation\" rather than catastrophic failure, even when the contamination rate far exceeds the 50% theoretical breakdown point. Its strong performance at 70% contamination shows that its practical utility is highly robust.\n\n---\n\n#### **Regarding Question 2: Sensitivity to Biased ID Statistics**\n\nThis is an excellent question about the method's real-world robustness. To evaluate RAGNOR's sensitivity to biased ID statistics, we designed an experiment where we estimated $\\mu_{ID}$ and $\\sigma_{ID}$ using only a random subset of the ID training data.\n\n| Portion of ID Training Data Used for Stats | Cora-S AUROC (↑) | Performance Drop |\n| :----------------------------------------- | :--------------- | :--------------- |\n| **100% (Default)** | **97.1%** | **-** |\n| 50%                                        | 96.8%            | -0.3%            |\n| 20%                                        | 96.1%            | -1.0%            |\n| 10%                                        | 95.2%            | -1.9%            |\n| 5%                                         | 93.5%            | -3.6%            |\n\nThe results show that RAGNOR is **highly robust** to estimation bias. Even with only 20% of the training data used for statistics, the performance drop is negligible. This is because our discrepancy score $|\\Delta_v|$ relies on the *relative* difference between a node's norm and its local context, which buffers against slight inaccuracies in the global statistics.\n\n---\n\n#### **Regarding Question 3: Baseline Breadth**\n\nWe thank the reviewer for this suggestion. We will add a discussion to our Related Work section to position RAGNOR relative to these emerging methods.\n\nMethods based on score-matching or diffusion are typically **generative**. They are powerful but often require extremely costly training and a dedicated model architecture, making them unsuitable as post-hoc additions to existing GNNs. In contrast, RAGNOR is a **lightweight, discriminative, post-hoc** framework. Its key advantage is its efficiency and universality—it can enhance any pre-trained GNN at a minimal cost.\n\nTherefore, we see these methods as serving different needs. Generative models are an option for those seeking maximum performance regardless of cost, while RAGNOR is a more practical and attractive solution for efficiently improving the safety of existing systems.\n\n---\n\n#### **Regarding Question 4: Hyper-parameter Tuning Protocol**\n\nWe are happy to clarify our experimental protocol.\n\n**Regarding `λ`:** In our main experiments (Tables 1 & 2), we used a **fixed `λ=1` for all datasets** to ensure a fair and simple comparison of the core idea. We did not tune it. The new experiment showing the benefits of tuning `λ` (in our response to Reviewer 5Yiu) is meant to demonstrate the framework's further potential.\n\n**Regarding `τ`:** Our primary evaluation metrics, **AUROC and AUPR, are threshold-agnostic** and do not depend on `τ`. For the FPR95 metric, we follow the standard protocol: the threshold `τ` is chosen on the validation set to achieve a 95% true positive rate on ID samples. This threshold is then applied to the test set. **No information about the test set's OOD samples or their proportion is used in this process.**"}, {"review_id": "JKdnlkL5Ej", "reviewer": "Reviewer_zXmn", "summary": "This paper proposes RAGNOR, a node embedding norm-based method for both node-level and graph-level OOD detection. RAGNOR constructs an effective score function by refining node embedding norms through global Z-score normalization, median-based local aggregation, and multi-hop blending. Extensive experiments demonstrate that RAGNOR significantly outperforms the baselines on multiple benchmarks.", "questions": "Please see Weaknesses.", "limitations": "NA.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and easy to follow.\n2. The proposed RAGNOR is a simple yet effective norm-based method for graph OOD detection.\n3. Empirical experiments validate the superiority and robustness of RAGNOR.\n\nWeaknesses:\n1. In the experiments, NODESAFE+RAGNOR is tested, where the node embeddings are obtained from NODESAFE. What is the performance of GCN+RAGNOR or GNNSAFE+RAGNOR? It would be insightful to know whether the improvement mainly comes from RAGNOR itself, or depends primarily on the quality of the embeddings.\n2. While the paper introduces three effective methods for refining norms, the technical innovation seems somewhat limited.\n3. There is a lack of a related work section, which could provide valuable context and comparisons to existing methods.", "was_revised": true, "final_justification": "The issue regarding the performance of GCN+RAGNOR has been resolved. The author elaborated on the contribution of this article in detail.", "rebuttal": "#### **Regarding Weakness 1: Generalizability and Dependence on Embedding Quality**\n\nThis is a critical question. We agree that it is essential to show that RAGNOR's improvement comes from the framework itself and not just from a specific high-quality embedding.\n\nWe have already conducted a comprehensive experiment on this in **Appendix G: Robustness to Backbone Architecture**, with results in **Table 10**. We apologize for not highlighting this more prominently in the main paper. The core results for the node-level Cora-S task, which directly answer the reviewer's question, are summarized below:\n\n| Backbone      | Post-hoc OOD Method | **Node-level AUROC (↑)** |\n| :------------ | :------------------ | :----------------------- |\n| **GCN (Standard)** | Energy              | 78.0% |\n|               | **RAGNOR (Ours)** | **96.5%** |\n| **GAT** | Energy              | 89.2% |\n|               | **RAGNOR (Ours)** | **97.0%** |\n| **GraphSAGE** | Energy              | 76.9% |\n|               | **RAGNOR (Ours)** | **95.8%** |\n| **GIN** | Energy              | 90.5% |\n|               | **RAGNOR (Ours)** | **97.1%** |\n\nThe results clearly show that RAGNOR consistently and significantly outperforms other post-hoc methods across a variety of standard GNN backbones. For instance, on a standard GCN, RAGNOR improves the AUROC by over 18 points compared to the Energy score. The performance gain is primarily due to the RAGNOR framework itself, demonstrating that it is an **architecture-agnostic** module that can robustly enhance the OOD detection capabilities of any reasonable GNN.\n\nGiven the importance of this finding, we will move this section from the appendix to the main experimental section in our revised paper.\n\n---\n\n#### **Regarding Weakness 2: Limited Technical Innovation**\n\nWe thank the reviewer for the opportunity to clarify our work's core innovation. We respectfully argue that if \"technical innovation\" is limited only to inventing new algorithms, it may understate our contribution. Our core innovation is a deeper form of **\"diagnostic innovation,\"** which is critical for scientific progress.\n\nOur primary contribution is transforming a vague problem—the poor performance of norm-based methods on graphs—into a set of clear, quantifiable scientific questions through a systematic and pioneering diagnostic study.\n\nBefore our work, the community's understanding was limited to the observation that \"norm-based methods perform poorly on graphs.\" We refused to accept this as a conclusion; instead, we treated it as the starting point of a deep investigation. Our complete effort and findings are detailed in **Appendix C**. This rigorous diagnostic work was far from a simple preliminary study:\n\n1.  **Multi-faceted Empirical Investigation:** We systematically investigated global, local, and class/role-level factors across diverse graph datasets (Cora, ArXiv, REDDIT, TWITCH).\n2.  **In-depth Quantitative Analysis:** We went beyond qualitative observations, using **statistical divergence metrics (KL, JSD, Wasserstein)** to quantify distribution overlap and defining new metrics like the **\"Local Contamination Ratio (LCR)\"** to precisely measure local structural impacts.\n3.  **Strict Variable Control:** In **Appendix C.5**, we rigorously ruled out confounding variables such as GNN architecture, embedding dimension, and random seeds to ensure our findings were fundamental, not coincidental.\n\nThrough this effort, we were the **first to decompose this complex problem into three concrete, addressable root causes: (C1) local contamination, (C2) class-level norm differences, and (C3) boundary/low-degree node issues**. We firmly believe this diagnostic contribution, which illuminates the true nature of the problem for the field, is a core and original scientific contribution in itself.\n\n---\n\n#### **Regarding Weakness 3: Lack of a Related Work Section**\n\nWe agree completely and thank the reviewer for pointing out this structural omission. We will add a dedicated **Related Work** section to the revised paper.\n\nCurrently, our paper cites over 40 relevant works, but they are distributed throughout the introduction and experiment sections. A dedicated section will provide better context. The new section will systematically cover: (1) general OOD detection in other domains, (2) specific graph OOD detection methods, including our primary baselines, and (3) a discussion of the connections and distinctions with related fields like Graph Anomaly Detection and Robust Graph Learning. We are confident this addition will significantly improve the paper's readability and completeness."}]

Author rebuttal:

Meta-review: (a) The paper proposes a post-hoc method (reusing existing embeddings) for OOD detection in graphs.  This uses a more robust method for handling norms at the graph level.   Simple but effective.
(b)  Extensive experimental work is done with strong results.  Well written paper with clear motivation and explanations.   Diagnoses why norm methods have failed on graphs.  Demonstrates robustness in different contexts.
(c)  Combines well known techniques so novelty not strong.  Better related work section needed.  Some design choices (e.g., aggregation and multi-hops) could be explored further.
(d)  All reviewers agree on accept.  No major issues identified.
(e)  Reviewers did substantial rebuttal including experimental results and theoretical explanation.  Three reviewers raised their scores.  Good suggestions by authors to improve paper.
Decision: Accept (poster)