Revisiting Score Propagation in Graph Out-of-Distribution Detection
Authors: Longfei Ma
Yiyou Sun
Kaize Ding
Zemin Liu
Fei Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Network
Out-of-distribution Detection
Primary area: graph_neural_networks

Abstract: The field of graph learning has been substantially advanced by the development of deep learning models, in particular graph neural networks. However, one salient yet largely under-explored challenge is detecting Out-of-Distribution (OOD) nodes on graphs. Prevailing OOD detection techniques developed in other domains like computer vision, do not cater to the interconnected nature of graphs. This work aims to fill this gap by exploring the potential of a simple yet effective method -- OOD score propagation, which propagates OOD scores among neighboring nodes along the graph structure. This post hoc solution can be easily integrated with existing OOD scoring functions, showcasing its excellent flexibility and effectiveness in most scenarios. However, the conditions under which score propagation proves beneficial remain not fully elucidated. Our study meticulously derives these conditions and, inspired by this discovery, introduces an innovative edge augmentation strategy with theoretical guarantee. Empirical evaluations affirm the superiority of our proposed method, outperforming strong OOD detection baselines in various scenarios and settings.

Revisiting Score Propagation in Graph Out-of-Distrluution Detection
Longfei Ma'; Yiyou Sun Kaize Ding", Zemin Liu' Fei Wu'
'Zhejiang University, UUniversity of Wisconsin-Madison NNothwestern University flongfeima, liu. zemin, wufei) edu. en, sunyiyoulcs. wisc.edu, kaize. weeeeedinnnndnneee sing@northvestern.c.
Abstract
The field of graph learning has been substantially advanced by the development of deep learning models, in particular graph neural networks. However, one salient yet largely under-explored challenge is detecting on graphs. Prevailing OOD detection techniques developed in other domains like computer vision, do not cater to the interconnected nature of graphs. This work aims to fill this gap by exploring the potential of a simple yet effective method OOD score propagation, which propagates OOD scores among neighboring nodes along the graph structure. This post hoc solution can be easily integrated with ex- isting OOD scoring functions, showcasing its excellent flexibility and effectiveness most scenarios. However, the conditions under which score propagation proves beneficial remain not fully elucidated. Our study meticulously derives these condi- tions and, inspired by this discovery, introduces an innovative edge augmentation strategy with theoretical guarantee. Empirical evaluations affirm the superiority of proposed method, outperforming strong OOD detection baselines in various scenarios and settings. To ensure reproducibility, we have made our code and relevant data publicly available at https: //ttt/gtttt/tt//// com/ com/longf longfeti
(OOD) nodes
Introduction
Graph-like data structures are ubiquitous in many domains, such as social networks [87,40), 40), molecular chemistry [19, 82], and recommendation systems [84, 45). As graph neural networks increasingly serve as powerful tools for navigating this complex data landscape, a compelling yet under-explored issue emerges: Diito---istribttion (OOD) node detection. Imagine recommender system suggesting irrelevant or even harmful products to users, or a bioinformatics algorithm misusing an unknown protein. This gives risc to the importance of OOD detection in graph data, which determines whether an input is in-distribution (ID) or OOD and enables the model to take precautions.
While existing OOD detection methods have shown promising re- sults in computer vision [66, 27, 18, 15, 95], natural language pro- cession [11, 57] and tabular data analytics [68], their effectiveness diminishes when applied to graph data [77]. These conventional techniques operate under the assumption that data points are indepen- dently sampled, which misaligns with the interconnected nature of graphs. better leverage the structural knowledge from the graph, OOD score propagation [77] has been employed to enhance graph OOD detection performance by directly propagating the computed OOD scores along the graph structure (as shown in Figure 1). Al- though this strategy has shown promising results some datasets,
ID
OOD
Raw 000 Score
92
+
Propagation
Post- propagation 000 Score
+
Figure 1: Illustration of OOD propagation.
"qqual Contribution
t Corresponding author
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

Score Propagation (with More Inter-edges)
Score Propagation (with More Intra-edgee)
Q+
OCO Node Noci
0,07
edges
0,50
Soore Devioutto
Intra-odges:
Score
Worse
Better
Bror
Enror 100%
16%
Annotation
(6) The case when propagation is harmful.
(b) The case when propagation is helpful.
Figure 2: Two illustrative examples when scoring propagation is harmful/helpful. We consider ID nodes in green and OOD nodes in red. Inter-edges are defined ID-to-O0D edges and Intra-edges are ID-to-ID or O0D-to- to-0to these cases will be the mean of the scores of adjacent nodes as shown in Figure 1.
00D edges. The value represents the respective OOD scores. Consequently, the propagated scores in
the reasons behind its effectiveness and the conditions under which it works are not clear. To dive deep into it, our research embarks on addressing two research questions related to OOD score propagation:
Question 1: "Will naive 0OD score propagation always help graph OOD Detection?" The short answer is no. This method can be ineffective on graphs where inter-edges (ID-to-00D) (OD) predom- inant. Using the examplse in Figure 2(a), where only inter-edges exist, prior to conducting score propagation, all ID and OOD nodes can be fully distinguished. However, after performing score propagation along these edges, the ID and OOD nodes are completely misclassified. Conversely, after adding intra-edges and making them donimate, be beneficial to distinguish ID and OOD nodes. These two examples intuitively illustrate how the ratio of intra-edges and inter-edges can impact the effectiveness of OOD score propagation. We substantiate this intuition in Section 3. This finding naturally paves the way for subsequent questions.
shown in Figure 2(b), score propagation would
Question 2: "How to derive a better score propagation strategy for graph OOD detection?" Building on our prior findings, propose graph augmentation strategy as presented in Section 4. Specifically, our strategy selects a subset G of the training set and puts additional edges to the nodes within G. Beyond its practical implications, our solution is theoretically supported: When G' predominantly connects to ID data over OOD data, our strategy can provably enhance the post-propagation OOD detection outcomes.
We summarize contributions below:
Theoretical understanding: We delve deeply into the mechanism of score propagation under- stand its potential for graph OOD detection and elucidate the conditions under which thrives, providing an understanding that extends beyond existing knowledge.
Practical solution: To counter the identified challenge of inter-edges' domination, we propose GRaph-Aus Braaph-Augmntte Score Propagation (GRASP), an innovative edge augmentation strategy with theoretical guarantee. By strategically adding edges to chosen subset G of the training set, as detailed in Section 4, our method aims to enhance the intra-edge ratio, thereby boosting OOD detection outcomes post-propagation.
Empirical studies: We demonstrate the superior performance the proposed method on extensive graph OOD detection benchmarks, different pre-trained methodologies [34, 69, 7, 7.94,, and different OOD scoring functions. Under the same condition, our proposed strategy substantially reduces the FPR95 by 17.87% and 32.21% % compared to the strongest graph OOD detection baselines on common and large-scale benchmarks respectively. Comprehensive analyses also provided to validate the effectiveness the proposed approach and the correctness the theoretical findings.
Preliminaries
Problem setup. We consider traditional semi-supervised node classification setting with the additional unlabeled nodes from the out-o--distribuutin class. Let g = (V, E} denote the graph with nodes V and edges E, where the node set V/ with size N are attributed with data matrix X e Nd The structure of graph G is described by the adjacency matrix A E [0,1] NxN We let the corresponding row-stochastic matrices as A = D-1 1-1A A, where D is the diagonal matrix with

---

Du Dn= The N nodes are partially labeled, so we let V and Va represent the labeled and unlabeled node sets respectively, i.e, V V.V. Given a training set D (x,, vi) iev, with x; the i-th row of X and y1 E y & {1..... ,C}, the goal of node classification learn mapping f: V + RC from the nodes to the probability of each class.
Out-of-distribution detection. When deploying model in the real world, reliable classifier should not only accurately classify known in-distribution (ID) nodes, but also identify "unknown" nodes or OOD nodes. Formally, we can represent the unlabeled node set by V. Vusd Vnood where Vuid and V wood represent the in-distribution (ID) node and OOD node respectively. The goal of the graph OOD detection is to derive algorithm to decide if a node i V. is from Vuood or Vuid-
This can be achieved by having an OOD detector, in tandem with the node classification model f. OOD detection can be formulated as a binary classification problem. At test time, the goal of OOD detection decide whether an unlabeled node i V. is from ID or OOD. The decision can be made via a level set estimation:
g(x)) 2 X OOD g(x:) X
ID
FOODD(i,G:A)
where nodes with higher scores gxx)) are classified IDD and vice versa, and À is the threshold commonly chosen so that a high fraction (c.g., 95%) of ID data is correctly classified.
In this paper, we consider post hoc OOD detection methods to produce g(x;) which does not require expensive re-training. As an example, a classical way to compute g(x:) is Maximum Softmax Probability (MSP) [23] which is given by the maximum softmax value. We include details of the considered OOD detection methods in Appendix B.
3 Will propagation always help Graph OOD Detection?
In the introduction, we delineate the limitations of OOD score propagation using a concrete example and elucidate the intuition that it may fail when inter-edges dominate. In this section, formally delineate the conditions under which OOD score propagation works. We start by showing the formal definition of propagation.
Define OOD scoring propagation. Given OOD scoring vector R-V with g. g(x;), the propagated scoring vector is given by:
Propagated OOD Scoring Vector: g Ah
where & E N+ are hyperparameters.
Is it necessarily the case that g outperforms g? The answer is NO. We elucidate with the theoretical insight below.
Theoretical Insight. As discussed in the Introduction from Figure 2. when the number of ID-to-B ID and 00D-to edges surpasses that of ID-to- -OD edges, the propagation mechanism tends to "aggregate" the scores associated with the ID and OOD nodes respectively, which further amplify the separability between them. Conversely, when the number of ID-to ID-to-O0D edges types edges, the scores for both ID and OOD nodes become undistinguishable post propagation.
than the other
The example above offers the insight that the relative performance of g compared to g is contingent upon the structural dynamics of the network, specifically the distribution of edges. To formally articulate this relationship, we adopt probabilistic framework for modeling edges. Specifically, we assume that the edge follows Bernoulli distribution characterized by parameters Mintra and fjnter for intra-edges (ID-to- ID and DOD-to-OOD) and inter-edges LID-to-000 respectively:
{
Ber Ber (iintra), Ber
if i,j E Vuid or i, E Vuood if Vuid; E Vuood or Vusdş E V Vuood
Aij
In the context of probabilistic modeling, the subsequent Theorem 3.1 can be established to formalize the inherent understanding.
3

---

Theorem 3.1. (Informal) (a) When Tettra Venters is highty likely that the propagation algorithm will yield enhanced performance in OOD detection. (b) When Tintra se Tenter or even Myntro < qenter, the score propagation is likely to be either ineffective detrimental to the performance.
We also provide the formal version below (Theorem 3.2) which provides a mathematical foundation for understanding how varying the Bernoulli parameters influence the efficacy of the propagation in the context of OOD detection. We provide the detailed proof in Appendix A.
Theorem 3.2. (Formal) For any two IDIOOD node Sid Vuids Sood Vuood with equal size No. let the ID-vs-OOD separability Msep defined on an OOD scoring vector E B as
Msep - EiES..8i Ese Ej-
If Maep (g) and Tintrr Mitte > 1/N,, for some 0 and constant c, we have P (Maep (Ag) 2 Maep(g) 2 - exp(
c²
Summary. This section has presented a comprehensive theoretical evidence to substantiate the claim that propagation through the adjacency matrix A does not necessarily enhance out-of-distribution (OOD) detection in graphs. Moreover, Theorem 3.2 reveals that critical factor enhancing post-propti post-propagation performance lies in improving the ratio of intra-edges within the graph structure. These insights serve direct motivation for the augmentation strategy in the next section.
4 An Augmented Score Propagation Strategy
The findings from the preceding section give rise to a subsequent thought: "Can we improve the propagation strafegy for graph OOD detection performance?" In an ideal scenario, if an oracle were to indicate that particular subset in the test set belongs exclusively to the OOD, one could augment the graph by adding intra-edges removing inter-edges. This would consequently improve the ratio of intra-edges Vintres leading enhanced OOD detection performance pospppoppaation.
However, such an oracle does not exist in practical settings, and even approximating such a subset proves to be a difficult task. Existing literature has suggested the use of pseudo-labels assigned to nodes [36, 79, 2, 73, 55J. Nonetheless, these studies also caution that this approach is susceptible to "confirmation bias", whereby errors in estimation are inadvertently amplified.
To circumvent it, this paper proposes the solution for adding edges to subset of the training set Vi, which is assured to be in-distribution data. We start by showing the thcoretical underpinnings that adding such subset can, under specified conditions, contribute to improved OOD detection performance after propagation.
4.1 Theoretical Insight
Our approach involves adding the edges subset of training data and then propagating the out-of iittof-diitribution (OOD) scoring vector using the enhanced adjacency matrix. Specifically, when edges added to G, this action be mathematically represented as incorporating perturbation matrix F. = e into A, as demonstrated in Figure 3. Here, es E N denotes an indicator vector for set S V, where the vector takes the value of 1 if the index i and value O otherwise. A sufficient condition for the efficacy this augmentation strategy in enhancing post-prop propaaropantionn OOD detection performance is outlined in Theorem 4.1.
Theorem 4.1. (Informal) For a subset G in the training set, augmenting by adding edges to all its nodes can lead to improved post-propagation OOD detection performance, provided that the following condition is met: G has more edges to ID data than OOD data.
We also provide the formal version below (Theorem 4.2) that incorporates a perturbation analysis. This analysis elucidates how edge augmentation in the training set positively influence the

---

U1 U2
U3
UN
U1
1/2
0g
ON
A
Add edges to {vi, U2)
Figure 3: The augmentation procedure.
propagation algorithm's ability to enhance OOD detection. For the sake of the main intuition, provide the analysis on instead of Ā for simplicity. We provide the detailed proof in Appendix A.
Theorem 4.2. (Formal) For any two test ID/OOD node set Sid C Vuid. Sood C Vuood with size N., let the ID-vs-OOD separability Msep defined non-negafive OOD scoring vector IRN
Maep(g) BiES, EjESsoudj-
Let Esessr C E to denote the edge set of edges between two node sets S and S', where S,S' C.V. we can find node set G C such that |EGusaa > @EGerSnoal have
Msep (eep((A)) (A+ (A+8E) (g) > (Ase((2g))
where = =eGe and 8 > O.
The Theorem 4.2 shows critical principle for enhancing propagation: the optimal strategy entails the addition of edges the subset G such that there are more edges to ID data than OOD data. For some Std, Sood in the test set, the goal is to find the set
|EseSSul
G. = arg max SCV. [Eses
(2)
where Ng hyperparameter to control the size of G.. Inspired by the optimization target, we proceed to present our pragmatic algorithmic approach.
4.2 Graph-Augmented Score Propagation (GRASP)
Our augmentation approach hinges the selection of a subset, G, from the training set, exemplified Equation 2. Two principal challenges arise implementing this: (1) We cannot directly determine the number of edges linked to ID/OOD data because these reside in the test set and their labels remain unknown. (2) An exhaustive search find a subset computationally expensive, as the number of combinatorial possibilities increases in a factorial manner. In this paper, we tackle these challenges by providing the practical approximation method.
Selection of Sja/ /Sont Our discussion begins by detailing the methodology to select the subset from the test ID/OOD dataset, symbolized by Sia and Sood in Equation 2. A straightforward approach to obtain the most likely ID by selecting nodes with the largest confidence and the least for OOD in class predictions. Following [23], we employ the max softmax probability (MSP) as representation of confidence. The selected sets be defined
Sed ii Val max fe(i) >a Sood (j Vul max fe(i) < A100-a cE[C]
(3)
cE(C]
where Aa denotes the a-th percentile of the MSP scores corresponding to nodes in V., To offer clear view, Figure portrays Sia and Sood in the marginal regions highlighted in orange. Selecting a subset in the leftmost and rightmost regions reduces the error when identifying the ID/OOD subsets, given that overlapping between ID and OOD predominantly occurs around the central region of the distribution.
Selection of G. Upon establishing Su and Sood. the next step is determine G using Equation 2. Directly enumerating every possible is impractical. Instead, we adopt greedy approach, prioritiz- ing the node with the highest "likelihood" score. To elucidate, for each node i Vi, the score can be
5

---

Distribution of MSP Score in V4
000
ID
Frequency
Sood
Sia
Max Softmax Probability
Figure 4: Illustration of the rationale in selecting Sta and Sond- MSP score reported on Dataset
Coauther-CK with the division of ID and OOD classes introduced in Appendix C.
computed as the ratio of the edge count to Saa over Sood:
h(i) (1))==al((((()) + 1),
where we incorporate an addition of 1 in the denominator to circumvent division by zero. Subse- quently, G' can be expressed as:
{i Vi(h(i) > TB)
(5)
where ти stands for the 8-th percentile of /xii) scores for nodes in Vi. Once G' is defined, edge augmentation can be executed as demonstrated in Section 4.1. The OOD score then propagated with the new adjacency matrix A+ A egec in place:
SGRASP (g+)*g.
where & N+ are hyperparameters.
Complexity analysis. While our algorithm introduces the fully connected matrix E, our method can be effciently implemented by matrix-vector multiplication, leading to computational footprint terms of runtime and memory usage with ONN 2 + n) and O(N + + + n) respectively after propagation for k times, where n is node count of subset G. We provide the comprehensive complexity analysis in Appendix D.6.
5 Experiments
We conduct extensive experiments us- ing 10 real-world datasets that span diverse do- mains, scales, and structures (homophily or het- erophily). A high-level summary of the dataset statistics provided in Table 1, with detailed information of the datasets and the comprehen- sive description of ID/OOD split in Appendix C. Specifically, Cora [61] serves as a widely rec- ognized citation network. Amazon-Photo [52] represents a co-purchasing network on Amazon. Coauthor-CS [62] portrays coauthor network within the realm of computer science. More- over, Chameleon and Squirrel [59] are two notable Wikipedia networks, predominantly uti- lized heterophilic graph benchmarks. We
Datasets.
Table 1: Summary statistics of the datasets: size of the training set [Vi]. test set [uual, OOD set [Voooll number of classes C, scale of the dataset, and whether the graph is homophily.
Dutaset
[1]
[Vond
Scale
Homph
Cara
180
724
18K
SM
Amazon- Photo
618
2K
4K
SM
Couuthoe
Chameleon
272
IK
916
SM
Squirrel
622
2K
2K
SM
Reddiı2
133K
oghn-products
130K
522K
IM
11
L.G
ArXiv-yeur
23K
92K
53K
LG
Snap-patents
351K
LG
Wiki
212K
850K
862K
LG
additionally incorporate 5 large-scale graphs to evaluate our proposed methods: Reddit2 [88] and ogbn- products [24] are large homophily datasets; ArXiv-year, Snap-patents, and Wiki [44] are recently proposed large-scale heterophily benchmarks.
Remark on homophily, denoting the tendency of nodes with the same class to connect. Conversely, the heterophily graph demonstrates a tendency for nodes of disparate classes to connect. This characteristic not only presents challenge for node classification but also for graph OOD detection. The underlying
Table datasets are also categorized based on the attribute of

---

Table 2: Main results common benchmarks. Comparison with competitive out-of-distribution detection methods on pre-trained GCN. We take the average values that are percentages over 5 independently trained backbones. 1 (L) indicates larger (smaller) values are better.
Method
Cora
Amazon
Datasets Coauthor
Chameleon
Squirrel AUROCT
Average
FPR.
AUROCT
AUROC1
FPR]
AUROCT
FPR.
AUROC1
AUROC1
MSP
70.86
84.56
49.26
89.34
28.82
94.34
85.70
57.96
94,68
48.51
65.86
74.94
Energy
67.54
K5.47
42.13
90.
20.29
95.67
88.06
59:20
93.98
45.87
62.40
75. 14
KNN
90.20
70.94
65.19
84.71
51.24
90.13
93.38
57.90
94.72
54.68
78.95
71.67
ODIN
Mahalanobis
69.68
96.99
58
85.71
95.55
53.19
94,90
88.47
70.84
GKDE
63.71
86.27
81.29
77.
25.48
95.13
92.93
50.14
96.71
49.38
72.022
71 64
GPN
58.45
82,93
72.95
82.63
34,11
93,82
82.25
68.20
95.58
48.38
68.67
75.
OODGAT
94.59
53.63
71.34
66.95
96.53
52.18
94.43
59.67
95.27
46.13
90.43
55.71
GNNSafe
96.27
16.64
100,00
100.00
GRASP (Ours)
29.70
93.50
14.38
96.68
7.84
97.75
66.88
76.93
85.59
61.09
40.88
85.19
reason that the OOD data is from different classes with ID, and heterophily exacerbates the ratio of inter-edge connections between ID and OOD, which is deemed undesirable for graph OOD detection according to Theorem 3.2.
Implementation Details. Our graph OOD detection technique operates a post hoc fashion utilizing pre-trained network and so can be used in various pre-trained network seamlessly. We present results evaluated on Graph Convolutional Network (GCN) [34] in the main paper to save space and put detailed results of other architectures in Appendix D.3. All pre-trained models possess layer depth of 2. With the pre-trained network, we proceed to execute the graph OOD detection. By default, report the performance of the augmented propagation (GRASP) compatibility with other OOD scoring functions is also shown Table 6. We set the propagation number i as 8, with percentile values = 5 and 3 50. The sensitivity analysis of the hyper- parameters included Appendix D.4.
the MSP score [23]. The
Metries. Following the convention in literature [23, 47, 65], we use AUROC and FPR95 as evaluation metrics for OOD detection.
5.1 Main Results
GRASP consistently achieves superior performance. We provide results of 5 common small-scale benchmarks and large-scale datasets in Table 2 and Table 3 respectively, wherein only the averaged results over 5 runs are presented to save space and the detailed results with standard errors of these two scale datasets are shown in Table 12 and Table 13 respectively. From the results we can see that our proposed methodology (GRASP) consistently demonstrates promising performance. The comparative analysis encompasses a broad spectrum of post hoc competitive Dit---f--istiiuttion (OOD) detection techniques in existing literature and training-basse OOD detection. We categorize the bascline methods into two groups: (a) Traditional OOD detection methods including MSP [23], Energy [47], ODIN [43], Mahal anobis [37], and KNN [67]; (b) Graph OOD detection methods including GKDE [92], GPN [64], DODGAT [63], and GNNSafe [77]. In these tables, we present GRASP results based on the MSP score. Noteworthy findings include: (a) The traditional OOD detection methods exhibit suboptimal performance in the realm of graph OOD detection. For instance, GRASP reduced the average FPR95 by 17.87% and 32.21% compared to the strongest traditional OOD detection method GNNSafe and Mahalanobis benchmarks, respectively. This outcome is anticipated given their lack of specificity design towards graph data. (b) GRASP outperforms existing baselines by large margin, surpassing the best baseline GNNSafe by 17.87% and 40% concerning average FPR95 on two scale benchmarks respectively. These results further corroborate that the theoretically motivated solution GRASP is also appealing to use in practice.
methods tailored for graph
common and large-scale
GRASP is also competitive on large-scale graph datasets. Contrasted with the small-scale benchmarks in Table 2, the large-scale scenario in Table 3 presents more challenges due to large number of nodes and edges. From Table 3 we can see that all baseline OOD detection methodologies exhibit suboptimal performance on large-scale benchmarks, while our method GRASP robustly performs the best.
GRASP exhibits significant advantages over training- -ased baselines. addition to contrasting with post hoc methods, we extend our comparison to parallel line of graph Of
7

---

Table 3: Main results large-seale benchmarks. Comparison with competitive oui-of-distribution detection methods on pre-trainee pre-trained method GCN. We take average values that are percentages over independently trained backbones. OOM means Out-Of-Memory and OOT denotes that no results have heen got after running over 48 hours for each run. ()) indicates larger (smaller) values are better.
Datasets
Method
roddit2
oghn-produccs AUROCT
snap-paaentt AUROC
Averuge
FPR
AUROC;
AUROCT
FPR
AUROCI
AUROCI
MSP
96,59
16.61
86.87
70.19
95.03
47.21
94.31
46.99
95.46
$1.70
93.65
53.15
Eaergy
96.77
44.13
85.09
68.13
94,10
51.35
96.82
46.03
97.31
29.02
94.02
47.73
KNN
90.78
73.98
95.35
57.96
90.54
51.45
59.08
ODIN
96.74
14.69
83.65
68.95
95.06
47.36
94.27
45,20
97.88
29.91
93.92
47.22
Mahalanobis
71.73
74.89
0OM
0OM
88.60
59.57
96.03
58.50
72.33
67.95
82.17
65.25
GKDR
00/
0OM
(OM
(OM
(OM
0OM
OOM
(OM
0OM
GPN
0OM
0OM
00M
0OM
95.62
OOM
00M
0OM
00M
95.62
50.97
OODGAT
GNNSafe
99:49
31,99
77.86
85.66
100.00
35,30
99.92
27.35
72.63
60.32
89.98
48.12
GRASP (Ours)
2.41
98.50
39,77
93,79
73.93
81.24
75.22
72.13
$8.49
77.97
49.96
84.73
(OOD) detection research, which focuses refining the training strategy to improve graph OOD detection performance. The compared methods include GXDE [92], GPN [64] and OODGAT [63]. While these approaches necessitate costly re-training procedure, they perform mediocrely across all small-scale datasets and even run out-of-memory on almost all large-scale benchmarks, rendering them impractical for real-world deployment.
GRASP is performant challenging heterophily datasets. As indicated in Table 2 and GNNSafe, which performs well on homophily datasets, experiences significant degradation on the difficult heterophily benchmarks due to its naive propagation mechanism. In contrast, GRASP maintains optimal performance on these hard scenarios.
5.2 A Comprehensive Analysis of GRASP
Ablation study on augmentation policy. Recall that the key part of our method GRASP is the augmentation policy that consists in adding edges to the training nodes with top 50% scores of f()).. which corresponds to the nodes on the right side of Figure 5. We ablate the contributions of h(i)) by comparision with alternative augmentation approaches that utilize h(i) differently in Table 4, specifically, (1)
200
Sorted training node indices
selecting 50% of training nodes with the lowest h(i) val-
Figure 5: Illustration of the number of edges from cach training node i to Su and Sood on Chameleon dataset. The x-axis denotes the training node indices, ordered by h(i) from low to high.
ues (left side of Figure 5), (2) randomly selecting 50% of
training nodes, corresponding to randomly picking node in- dices from the x-axis of Figure 5, (3) directly adding edges to Sia and Sood within the test set (i.e., TestAug), and (4) classic graph augmentation method named GAug [91],
which adds or removes edges based on an edge predictor that disregards h(i) completely. We have the following key observations:
(a) Selection by h(i) is effective. For example, our strategy using the top 50% scores of h(ii outperforms that uses random 50%, which, in turn, outperforms the low 50% way. This is because a higher score of h(() implies higher edge count towards ID data than to OOD data, which can increase the ratios intra-edges and improve OOD detection performance after propagation. In contrast, the alternative augmentation method GAug, which does not consider the score h(1) all, performs worse than the Low 50% policy.
Table 4: Ablation study on OOD detection performance by different augmentation policy, We report averaged AUROC over independently pre- pe-trained GCN models.
Strategy
Cora
Amazon
Coauthor
Chameleon
Squirrel
Average
GAug
64. 94
74.38
91.41
63.79
47.90
68,50
TestAug
59.24
75.78
95.00
50.58
48.64
65.85
Low 50%
88.84
95.02
97.21
54.60
53.52
77.84
Random 50%
90.23
95.37
97.45
65.32
57.59
81.19
Top 50% (Ours)
93.50
96.68
97.75
76.93
61.09
85.19
8

---

Table 5: GRASP consistently enhances the OOD detection performance of nodes connected by both inter-edges and intra-edges datasets characterized by strong degree of heterophily (datasets highlighted in bold in the table). However, naive propagation tends to compromise the performance of these nodes.
MSP
MpPpp
MSP+GRASP
Datasets
intra
inter
intra
inter
intra
inter
cora
48.06
46.90
60.91
48.31
78.42
50.48
amazon
66.70
57.82
81.80
68.58
89.56
78.66
coauthor
87.72
73.30
93.88
81.37
94.85
83,21
chameleon
57.48
51.22
55.63
51.02
70.79
55.19
squirrel
44.76
38.45
43.74
37.04
49.89
41.69
reddit2
64.85
54.85
65.70
54.99
96.56
93.63
ogbn-product
31.72
37.73
37.10
43.63
67.95
64.30
arxiv-year
60.18
8.34
62.93
4.27
70.42
16.21
snap-patents
61.49
5.76
64.12
0.37
67.24
9.89
wiki
56.58
48.39
60.62
52.06
69.13
61.19
(b) Directly adding edges to Stá and Sood within the test set is sub-optimal. Specifically, employing this method leads to nearly 20% lower than that achieved with GRASP, which substantiates the notion that "confirmation bias" can adversely affect the graph OOD detection.
Overall, the ablation study suggests that our proposed augmentation policy is crucial OOD detection performance.
GRASP can effectively boost performance of challenging nodes connected by inter-edges. As stated in the introduction I, the reason OOD score propagation does not always work the confusion between ID and OOD nodes resulting from propagation along the inter-edges. For example in heterophily datasets, where connected nodes tend to possess different labels, OOD nodes are more likely to appear on the inter-edges. To assess the capability of our proposed augmentation propagation method to address this challenge, present in Table 5 the accuracy of detecting OOD nodes connected by intra-edges (intra) and inter-edges (inter) respectively, using the original MSP without any propagation, naive propagation based MSP (MSP+prop), and proposed augmentation propagation (MSP+GRASP) respectively. From the results we can see that naive propagation performs well only strong homophily datasets, while strong heterophily datasets (datasets highlighted in bold in the table), its performance is even worse than without propagation, as expected. contrast, employing our augmentation method still results in substantial performance gain after propagation on these challenging datasets.
GRASP is compatible with a wide range of OOD scoring methods. Table 6, we demonstrate the compatibility of GRASP with various alternative scoring functions. Each method generates OOD scores to form a scoring vector; GRASP is then applied to facilitate score propagation. The use of GRASP markedly surpasses the performance of its non-augmented counterpart across all datasets.
Table 6: GRASP is compatible with different OOD scoring functions. We compare OOD detection methods and the performance after the simple propagation in Equation 1 (denoted by "+ prop") ) and with GRASP respectively. We report AUROC results that are averaged over 5 independent pre-trained GCN models.
Method
Cora
Amazon
Coauthor
Chameleon
Squirrel
MSP
84.56
89.34
94.34
57.96
48.51
MSP+prop
88.02
95.32
97.15
50.35
36.21
MSP+GRASP
93.50
96.68
97.75
76.93
61.09
Energy
85.47
90.28
95.67
59.20
45.07
Energy+propp
87.52
96.27
95 82
50.42
36.49
Fnergy+GRASP
88.34
96.35
96.64
62.04
60.66
KNN
70,94
84.71
90.13
57,90
54.68
KNN+prop
73.70
92.36
95.47
49.76
53.99
KNNSP
91.48
97.43
96,52
76.32
60.24
Remark on other empirical findings. We include other empirical findings in Appendix. Specifically, in Table 14, prove that GRASP also achieves superior performance the other GNN architectures in the literature. In Figure 7, we demonstrate a strong positive correlation between ratios of intra- edges and the corresponding OOD detection performance, validating the correctness of Theorem 3.2.

---

We also show in Table 15 that GRASP can increase the ratio of intra-edges after augmentation, consequently boosting OOD performance. This substantiates the correctness Theorem 4.2. What's more, we conduct a thorough accounting of computation/memory demands compared to baselines on all scale datasets in Table 16 and Table 17 respectively, which underscore the strong practicality of our approach. Lastly, in Appendix D.7, we investigate the other propagation mechanisms in the literature and their impact on graph OOD detection performance emperically.
Related Work
Out-of-distribution Detection. The primary focus within this realm has been on the development of scoring functions for OOD detection. These works can be broadly categorized into two main streams: (1) output-based methods [23, 43, 47, 71, 25, 72, 95, 26, 15, 90, 16, 21J, and (2) feature- based methods including the Mahalanobis distance [37, 60, 56] and KNN distance [67]. These methodologies are predominantly applied in domains such as computer vision, where samples are inherently independent of each other. However, these techniques are not designed to adeptly handle data structures like graphs, where samples are inter-connected.
Ofttt--dist detection for graph data. Graph anomaly detection has a rich history [12, 74, 89, 75, 48, 14, 50, 32, 46, 51]. In recent years, the OOD detection in graph data introduced fresh challenges, particularly with multi-class classification for in-distribution data, escalating the difficulty in discerning outlier data. Some of the works focus on graph-level OOD detection [42, 49, 4, 76]. For node-level OOD detection, GKDE [92] and GPN [64] apply Bayesian Network models to estimate uncertainties to detect OOD nodes. However, Bayesian-based approaches can encounter impediments such as inaccurate predictions and high computational demands, which limit their broader applicability [83]. GNNSafe [77] emerges as the work employing post hoc energy- based score perform OOD detection. Given the merits of post hoc methods, our study first provides comprehensive understanding of the OOD score propagation in Graphs, extending beyond existing knowledge.
Graph Data Augmentation. Graph Data Augmentation is common technique in graph machine learning [20, 6, 58, 29, 93, 91, 33, 53, 13, 3] to improve the node classification performance. Existing methods operate exclusively on in-distribution (ID) data. Furthermore, their test set data also originates from the in-distribution and shares the same classes as the training set. In contrast, our data augmentation is purposefully crafted for OOD detection, supported by the theoretical explanation.
Conclusions
In this research, we delve into an important yet under-explored challenge in the realm of graph data: Out-of-Distribution (OOD) detection. Recognizing the inadequacies of traditional OOD detection techniques in the context of graph data, our exploration centered on the potential of score propagation as a viable and efficient solution. Our findings reveal the specific conditions under which score propagation will be helpful-in in situations where the ratio of intra-edgee mntra-edges surpasses that of inter-edges. Motivated by this finding, our edge augmentation strategy selectively adds edges to specific subset G of the training set, which provably improves post-propagation OOD detection outcomes under certain conditions. Extensive empirical evaluations reinforced the merit of our approach.
8 Acknowledgements
This work supported by the National Natural Science Foundation of China (62441605), and the Starry Night Science Fund of Zhejiang University Shanghai Institute for Advanced Study (SN- ZJUSIAS-0010).
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
10

---

[2] Eric Arazo, Diego Ortego. Paul Albert, Noel E O' O'Connor, and Kevin McGuinness. Pseudo- labeling and confirmation bias in deep semi-supervised learning. In 2020 International Joint Conference on Neural Networks (LJCNN), pages 1-8. IEEE, 2020.
[3] Mehdi Azabou, Venkataramana Ganesh, Shantanu Thakoor, Chi-Heng Lin, Lakshmi Sathidevi, Ran Liu, Michal Valko, Petar Veličković, and Eva L Dyer. Half-hop: graph upsampling approach for slowing down message passing. 2023.
[4] Gleb Bazhenov, Sergei Ivanov, Maxim Panov, Alexey Zaytsev, and Evgeny Burnaev. Towards ood detection in graph classification from uncertainty estimation perspective. arXiv preprint arXiv:2206. I0691, 2022.
[5] Gleb Bazhenov, Denis Kuznedelev, Andrey Malinin, Artem Babenko, and Liudmila Prokhorenkova. Evaluating robustness and uncertainty of graph models under structural distri- butional shifts. Advances in Neural Information Processing Systems, 36, 2024.
[6] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference artificial intelligence, volume 34, pages
2020.
[7] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-11 1735. PMLR, 2020.
[8] Yonggiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. Does invariant graph learning via environment augmentation learn invariance? Advances in Neural Information Processing Systems, 36, 2024.
[9] Zhengyu Chen, Teng Xiao, Kun Kuang, Zheqi Lv, Min Zhang, Jinluan Yang, Chengqiang Lu, Hongxia Yang, and Fei Wu. Learning to reweight for generalizable graph neural network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 8320-8328, 2024.
[10] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, 2021.
[11] Pierre Colombo, Eduardo Dadalto, Guillaume Staerman, Nathan Noiry, and Pablo Piantanida. Beyond mahalanobis distance for textual ood detection. Advances in Neural Information Processing Systems, 35:17744411777 17759, 2022.
[12] Kaize Ding, Kai Shu, Xuan Shan, Jundong Li, and Huan Liu. Cross-domain graph anomaly detection. IEEE Transactions on Neural Networks and Learning Systems, 336))2200-2445, 2021.
[13] Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey. ACM SIGKDD Explorations Newsletter, 24(2):61-77, 2022.
[14] Kaize Ding, Qinghai Zhou, Hanghang Tong, and Huan Liu. Few-shot network anomaly detection via cross-network meta-learning. In Proceedings of the Web Conference 2021, pages 2448-2456, 2021.
[15] Andrija Djurisic, Nebojsa Bozanic, Arjun Ashok, and Rosanne Liu. Extremely simple activation shaping for -fitt--iitttibuttion detection. In The Eleventh International Conference Learning Representations, 2022.
[16] Xuefeng Du, Yiyou Sun, and Yixuan Li. When and how does in-distribution label help out-of- distribution detection? In Forty-first International Conference on Machine Learning, 2024.
[17] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[18] Ido Galil, Mohammed Dabbah, and Ran El- Yaniv. A framework for benchmarking class-out-of- distribution detection and its application to imagenet. In The Eleventh International Conference on Learning Representations, 2022.

---

[19] Johannes Gasteiger, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs. In International Conference on Learning Representations, 2019.
[20] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
[21] Soumya Suvra Ghosal, Yiyou Sun, and Yixuan Li. How to overcome curse-of- dimensionint for out-of-distribution detection? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 19849-19857, 2024.
[22] Shurui Gui, Meng Liu, Xiner Li, Youzhi Luo, and Shuiwang Ji. Joint learning of label and environment causal independence for graph -iitri-disti generalization. Advances in Neural Information Processing Systems, 36, 2024.
[23] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of- examples in neural networks. In International Conference on Learning Representations, 2016.
[24] 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 11-88222133331 2020.
[25] Rui Huang, Andrew Geng, and Yixuan Li. On the importance of gradients for detecting distributional shifts in the wild. Advances Neural Information Processing Systems, 34:677- 689, 2021.
[26] Wenjian Huang, Hao Wang, Jiahao Xia, Chengyan Wang, and Jianguo Zhang. Density-driven regularization for -uttof-disttibution detection. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[27] Paul F Jaeger, Carsten Tim Lüth, Lukas Klein, and Till J Bungert. A call to reflect on evaluation practices for failure detection image classification. In The Eleventh International Conference on Learning Representations, 2022.
[28] 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 8562-8570, 2024.
[29] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference knowledge discovery & data mining, pages 66-74, 2020.
[30] Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. In The Eleventh International Conference Learning Representations, 2022.
[31] Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, and Yanfang Ye. Graphpatcher: Mitigat- ing degree bias for graph neural networks via test-time augmentation. Advances in Neural Information Processing Systems, 36, 2024.
[32] Hwan Kim, Byung Suk Lee, Won-Yong Shin, and Sungsu Lim. Graph anomaly detection with graph neural networks: Current status and challenges. IEEE Access, 2022.
[33] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1rXiv:1611.07308. 2016.
[34] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[35] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations, 2019.
[36] Dong- Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning. ICML, volume 3, page 896. Atlanta, 2013.
12

---

[37] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
[38] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. pages 177-187, 2005.
[39] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
[40] Chang Li and Dan Goldwasser. Encoding social information with graph convolutional networks forpolitical perspective detection in news media. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2594-26088 2019.
[41] Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure and feature extrapolation for ofi-t--distribution generalization. arXiv preprint arXiv:2306.0800 2023.
[42] Zenan Li, Qitian Wu, Fan Nie, and Junchi Yan. Graphde: generative framework for debiased learning and out-of-distributioo detection on graphs. Advances in Neural Information Processing Systems, 35:30277-30290, 2022.
[43] Shiyu Liang, Yixuan Li, and R Srikant. Enhancing the reliability of diitti--ittiittoonnn image detection in neural networks. In International Conference on Learning Representations, 2018.
[44] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20900 2021.
[45] Changshu Liu, Liangjian Wen, Zhao Kang, Guangchun Luo, and Ling Tian. Self-supervised consensus representation learning for attributed graph. In Proceedings of the 29th ACM international conference multimedia, pages 2654 2662, 2021.
[46] Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, et al. Bond: Benchmarking unsupervised outlier node detection on static attributed graphs. Advances in Neural Information Processing Systems, 35:27021-27035, 2022.
[47] Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Li. Energy-based out-of-distribution detection. Advances neural information processing systems, 23:21564-221755, 2020.
[48] Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Pick and choose: a gnn-based imbalanced learning approach for fraud detection. In Proceedings of the web conference 2021, pages 3168-3177, 2021.
[49] Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. Good-d: On unsupervised graph out-of- distribution detection. In Proceedings of the Sixteenth ACM International Conference Web Search and Data Mining, pages 339-347, 2023.
[50] Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection attributed networks via contrastive self-supervised learning. IEEE transactions on neural networks and learning systems, (3(6):2378-2392 2021.
[51] Xiaoxiao Ma, Ruikun Li, Fanzhen Liu, Kaize Ding, Jian Yang, and Jia Wu. Graph anomaly detection with few labels: data-centric approach. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2153-2164, 2024.
[52] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pages 43-52, 2015.
[53] Hyeonjin Park, Seunghun Lee, Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung- Min Kim, Jung-War Woo Ha, and Hyunwoo Kim. catropolis-hasting data augmentation for graph neural networks. Advances in Neural Information Processing Systems, 34:19010-19020, 2021.
13

---

[54] 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.
[55] Hieu Pham, Zihang Dai, Qizhe Xie, and Quoe V Le. Meta pseudo labels. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages 11557-11568, 2021.
[56] Jie Ren, Stanislav Fort, Jeremiah Liu, Abhijit Guha Roy, Shreyas Padhy, and Balaji Laksh- minarayanan. A simple fix to mahalanobis distance for improving near-ood detection. arXiv preprint arXiv:2106.09022 2021.
[57] Jie Ren, Jiaming Luo, Yao Zhao, Kundan Krishna, Mohammad Saleh, Balaji Lakshminarayanan, and Peter J Liu. Out-of-distribution detection and selective generation for conditional language models, In The Eleventh International Conference on Learming Representations, 2022.
[58] Yu Rong, Wenbing Huang. Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. 2020.
(59) Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnnab014, 2021.
[60] Vikash Sehwag, Mung Chiang, and Prateek Mittal. Ssd: A unified framework for self supervupe outlier detection. In Proceedings of the International Conference on Learning Representations, 2021.
[61] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
[62] Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference world wide web, pages 243 143-246,279 2015.
[63] Yu Song and Donglin Wang. Learning on graphs with diitr--diittibttion nodes. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1635-1645, 2022.
[64] Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Gün- nemann. Graph posterior network: Bayesian predictive uncertainty for node classification. Advances Neural Information Processing Systems, 18033-18044, 2021.
[65] Yiyou Sun, Chuan Guo, and Yixuan Li. React: Out-of-distribution detection with rectified activations. Advances in Neural Information Processing Systems, 34:144-151 2021.
[66] Yiyou Sun, Yifei Ming, Xiaojin Zhu, and Yixuan Li. distr---istiitution detection with deep nearest neighbors. In International Conference on Machine Learning, pages 20827-20840. PMLR, 2022.
[67] Yiyou Sun, Yifei Ming, Xiaojin Zhu, and Yixuan Li. Out-of-distribution detection with deep nearest neighbors. In International Conference on Machine Learning (ICML). PMLR, 2022.
[68] Dennis Ulmer, Lotta Meijerink, and Giovanni Cinà. Trust issues: Uncertainty estimation does not enable reliable ood detection on medical tabular data. In Machine Learning for Health, pages 341-354. PMLR, 2020.
[69] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2017.
[70] Roman Vershynin. High-dimensional probability: An introduction with applications data science, volume 47. Cambridge university press, 2018.
[71] Haoqi Wang, Zhizhong Li, Litong Feng, and Wayne Zhang. Vim: citoof-distribution with virtual-logit matching. In Proceedings of the IEEÉ/CVF Conference on Computer Vision and Pattern Recognition, pages 4921-4930, 2022.
14

---

[72] Qizhou Wang, Feng Liu, Yonggang Zhang, Jing Zhang, Chen Gong, Tongliang Liu, and Bo Han. Watermarking for out-of-distribution detection. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[73] Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. Advances in Neural Information Processing Systems, 34:23768-23777 23779, 2021.
[74] Xuhong Wang, Baihong Jin, Ying Du, Ping Cui, Yingshui Tan, and Yupu Yang. One-class graph neural networks for anomaly detection in attributed networks. Neural computing and applications, 1o:12073-120855 2021.
[75] Yanling Wang, Jing Zhang, Shasha Guo, Hongzhi Yin, Cuiping Li, and Hong Chen. Decoupling representation learning and classification for gnn-based anomaly detection. In Proceedings of the 44th international ACM SIGIR conference research and development in information retrieval, pages 1239-1248, 2021.
[76] Yili Wang, Yixin Liu, Xu Shen, Chenyu Li, Kaize Ding, Rui Miao, Ying Wang, Shirui Pan, and Xin Wang. Unifying unsupervised graph-level anomaly detection and outoof-distribution detection: a benchmark, arXiv preprint vrXiv:2406.15522 2024.
[77] Qitian Wu, Yiting Chen, Chenxiao Yang, and Junchi Yan. Energy-based out-of-distribtioon detection for graph neural networks. In The Eleventh International Conference on Learning Representations, 2022.
[78] Qitian Wu, Fan Nie, Chenxiao Yang, Tianyi Bao, and Junchi Yan. Graph out-of-distribttion generalization via causal intervention. arXiv preprint arXiv:2402.114999 2024.
[79] Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoe V. Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[80] Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning.
[81] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pages 5453-5462. PMLR, 2018
[82] Yujun Yan, Jiong Zhu, Marlena Duda, Eric Solarz, Chandra Sripada, and Danai Koutra. Groupinn: Grouping- based interpretable neural network for classification of limited, noisy brain data. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 772-782, 2019.
[83] Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey. arXiv preprint 10Xiv:2/10.11332 2021.
[84] Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[85] Junchi Yu, Jian Liang, and Ran He. Mind the label shift of augmentation-based graph ood generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11620-11630 2023.
[86] Haonan Yuan, Qingyun Sun, Xingcheng Fu, Ziwei Zhang, Cheng Ji, Hao Peng, and Jianxin Li. Environment-aware dynamic graph learning for dut-o--distribution generalization. Advances in Neural Information Processing Systems, 36, 2024.
[87] Reza Zafarani, Mohammad Ali Abbasi, and Huan Liu. Social media mining: an introduction. Cambridge University Press, 2014.
15

---

[88] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2019.
[89] Ge Zhang, Jia Wu, Jian Yang, Amin Beheshti, Shan Xue, Chuan Zhou, and Quan Z Sheng. Fraudre: Fraud detection dual-resistant graph inconsistency and imbalance. In 2021 IEEE International Conference on Data Mining (ICDM), pages 867-876. IEEE, 2021.
[90] Jinsong Zhang, Qiang Fu, Xu Chen, Lun Du Zelin Li, Gang Wang. xiaoguang Liu, Shi Han, and Dongmei Zhang. Out-of- catoof-distribution detection based in-distribution data patterns memorization with modern hopfield energy. The Eleventh International Conference on Learning Representations, 2023.
[91] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. Proceedings of the aaai conference on artificial intelligence, volume 35, pages 11015-10233 2021.
[92] Xujiang Zhao, Feng Chen, Shu Hu, and Jin Jin-Hee Cho. Uncertainty aware semi-supervised learning on graph data. Advances in Neural Information Processing Systems, 13:12827- 2020.
[93] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. International Conference on Machine Learning, pages 1458-11468. PMLR, 2020.
[94] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
[95] Yao Zhu, YueFeng Chen, Chuanlong Xie, Xiaodan Li, Rong Zhang, Hui Xue', Xiang Tian, bolun zheng, and Yaowu Chen. Boosting out-of-distribution detection with typical features. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
16

---

A Proofs
Theorem A.1. (Recap of Theorem 3.2) any two test ID/OOD node set Sid C Vuid: Sood C V Vuoad with equal size No, let the ID-vs-OD separability Maey defined on OOD scoring vector g E R as
Maep (g) EiES,as Bj
If M Meep(e
②
> 0 and Nintra
Minter 1/Nor for some > O and constant we have
cE
IP (MMsep(A8) Mssp(() t) exp(
1g
Proof. Without losing the generality, set the gi 0, if E Sood U Sid, since only care about the detection results in the given test node set Sood and Sea.
The Mee can be re-written as
Maep(g) =g (es... @sood)
Then we have
Msep (Ag) = =g AAess @S
According to General Hoeffding's inequality (Theorem 2.6.3) in [70], we know that
CE
PP A(es,, -Ssoaal )1 -g7 A(ess esooo) se) 2 exp(
|gl
where c is constant value.
Since g, 0. if Vi.
Egg T A(es,a es = &TE[AA(ess: - es
= $ No (Jllintra - Minter (es -S
g (es eS
Combining together, have
(g A(es., @Sond) 1 T (esis @S -
-c) 2 exp(
cE
|
Theorem A.2. (Recap of Theorem 4.2) For any two test ID/OOD node set Sia C Vuid, Sood C Vuood with equal size No. let the ID-vs-OOD separability Msep defined on non-negative OOD scoring vector g E N as
Mge EiES.,8; EEES.onB;
Let Esuss C E to denote the edge set of edges between two node sets S and S', where S,S' C C.. If we can find node set G Vi such that (EGessal > EEGes we have
Maep Meep((A+ (A+8E)) > Maep (A2g),
where E =eced and 8 O.
Proof. The Meep (g) can be re-written
Msep g = N.
g (Ce.. CS
17

---

We can then directly derive the proof by expanding
Masp (AA+ 8E) -Maep (APg))
N, (esia esowe)" ( -A88)
N (esia esond) (Ó(AL'+ EA) + 0 decegeceas)
1
8
(cs.a esand) I AAcao + cg
No
8
(esi eSoud) Aege
N
(c
AeG - -sou Acc)
N
5(c(8)
((Ecesial Sent)
|G|N,
0,
where the second and the third equation are derived by the fact that G C V/ and then we have eg = 0 and e eg 0.
B Details of Baselines
For the reader's 's convenience, summarize in detail few common techniques for defining OOD scores that measure the degree of ID-ness on given input. By convention, a higher (lower) score indicative of being in-distribution cout-of-distribution)
MSP [23] This method proposes to the maximum softmax score the OOD score. For each node i, we use (I)DD( = max,s[C] fi) as the OOD score.
ODIN [43] This method improves OOD detection with temperature scaling and input perturbation. In all experiments, set the temperature scaling parameter T 1000. For graph neural network, we found the input perturbation does not further improve the OOD detection performance and hence
0.
Mahalanobis [37] This method uses multivariate Gaussian distributions model class-conditional distributions of softmax neural classifiers and uses Mahalanobis distance- scores for OOD detection. The mean Pe of each multivariate Gaussian distribution with class and a tied covariance Σ are estimated based on training samples. We define the confidence score M (x) using the Mahalanobis distance between test sample and the closest class-conditional Gaussian distribution.
Energy [47] This method proposes using energy score for OOD detection. The energy function maps the logit outputs to scalar Exx;; f) R, which is relatively lower for ID data. Note that [47] used the negative energy score for OOD detection, in order to align with the convention that S(x) higher (lower) for ID (OOD) data.
KNN [67] This method uses the k-th nearest neighbor distance between test graph node and the training set as the OOD score. use 10 for experiments this paper.
C Dataset Details
We adopt ten publicly available benchmarks used for graph learning, covering diverse domains, scales, and structures (homophily or heterophily). For five homophily datasets Cora, Amazon-Phott Coauthor-CS, Reddit2 and ogbn-prz ppoduutss,,, we use the data loader provided by the Pytorch Geometric package For the remaining five heterophily datasets, we directly use the pickle file or download from the given hyperlinks proposed by [44].
Cora [61] is a 7-class citation network comprising 2,708 nodes, 5,429 edges and 1,433 features. In this network, each node represents a published paper, each edge signifies citation relationship, and label class each paper's topic, which is the goal to predict.
18

---

Amazon-Phan Photo [52] is an 8-class item co-purchasing network on Amazon, which contains 7,650 nodes, 268.162 edges and 745 features. In this network, each node denotes a product, each edge indicates that two linked products are frequently purchased together, and the node label denotes the category of the product.
Coauthor-CS [62] is 15-class coauthor network of computer science, which contains 18,333 nodes, 163,788 edges and 6,805 features. In this network, nodes denote authors and there is an edge between two authors co-authored a paper. And the label represents the study field for the authors.
Reddit2 [88] a large homophily post network with 41 classes, where nodes are posts based on user comments and the task is to predict communities of online posts based on user comments.
ogbn-products [24] a super large homophily undirected and unweighted graph with 47 classes, representing an Amazon product co-purchasing network. Nodes represent products sold in Amazon, and edges between two products indicate that the products are purchased together. The task is to predict the category of a product in a multi-class classification setup. where the 47 top-level categories used for target labels.
Chameleor and Squirrel [59] are two Wikipedia networks with 5 classes, where nodes represent web pages and edges represent hyperlinks between them. Node features represent several informative nouns in the Wikipedia pages and the task is to predict the average daily traffic of the web page [17).
arXiv-year [24] the ogbn-arXiv network with different labels and is altered to be heterophily, in which the class labels are set to be the year that the paper is posted, instead of subject area in the original paper. The nodes are arXiv papers, and directed edges connect paper to other papers that it cites. The node features are averaged word2vec token features of both the title and abstract of the paper. The five classes are chosen by partitioning the posting dates that class ratios approximately balanced [44].
snap patents [39, 38] is big dataset of utility patents in the US. Each node represents patent and edges connect patents that cite each other. Node features are derived from patent metadata [44]. Like arXiv-year this dataset is changed to set the task to predict the time at which a patent was granted, which also five classes.
wiki [44] is a super big dataset of Wikipedia articles, which are crawled and cleaned from the internet. Nodes represent pages and edges represent links between them. Node features are derived from the average GloVe embeddings [54] of the titles and abstracts and labels indicate total page views over a 60-day period, categorized into five classes based on quintiles.
The complete information and statistics of all these datasets aforementioned are summarized in Table
Table 7: Statistics of all the graph datasets. # the total number of distinct node classes.
Dataset
# Nodes
Edges
Features
# C
Domain
Homoph
OOD Class
ID Class
Cora
2,708
5,429
1,433
7
citation
/
[0.
[4, 5, 6}
Amazon- Amazon-Photo
7,650
238,162
745
8
product
/
[0, ......44 4]
[5, 6, 7]
Coauthor-CS
18,333
163,788
6,805
15
citation
[0. 3)
[4...., 14)
Reddir2
232,965
23,213,838
602
post
/
[0,
[11,-.., 40)
ogbn-products
2,449,029
61,859,140
100
47
product
/
[0, 111
[12, .22,...,6)
Chameleon
2.277
31,421
2.325
5
Wikipedia
X
(0. 1]
[2
Squirrel
5,201
198,493
2,089
5
Wikipedia
X
(0, 1]
12.3.4
arXiv-year
169,343
1,166,243
citation
[0, 11
12,
snap-patents
2.923,922
13,975,788
269
5
patent
[0. 1]
3,
wiki
1.925.342
303.434.860
600
5
Wikipedia
X
10.
[2.
19

---

D Additional Experiments
D.1 Graph ID Classification Details
In this section, we provide a detailed report on the ID ACC results of nine popular GNN pretrained backbones used in our paper, including GCN [34], GAT [69], GCNJK [81], GATJK [81], APPNP [35], MixHop [1], GPR-GNN [10], GCNII [7], and H₂GCN [94]. The results of all the nine architectures on five common benchmarks and architecture GCN on five large-scale benchmarks are presented in Table 8 and Table respectively. In addition, we present the ID ACC results of three training- -aasd methods on the ten benchmarks. It is important to note that these training- vaining-based methods only yield results on five small- scale datasets and the moderately sized arxiv-year dataset. They fail to produce results on the remaining four large datasets, as shown in Tables 10 and Table 11.
Table 8: ID ACCs six pre-trained methods on common benchmarks. For each pre-trained method, we take the average values that are percentages over 5 independently trained backbones.
Backbone
Cora
Amazon
Coauthor
Chameleon
Squirrel
GCN
93,89 = 1.31
96.72 + 0.76
96.21 = 0.61
71.20 + 2.07
72.32 = 2.02
GAT
93.89 + 1.64
96.44 + 0.92
95.67 0.35
73.43 + 3.42
75.88 + 1.73
GCNJK
92.92 + 2.03
96.88 + 0.56
95.93 + 0.32
71.03 + 2.41
72.22 + 0.71
GATJK
93.27 + 1.91
96.31 0.38
95.78 0.26
74.55 + 1.95
76.47 + 1.45
GCNII
94.07 = 1.28
96.62
96.97 + 0.37
73.08 + 1.78
72.57 + 1.92
H,GCN
94.07 = 1.84
9.72
94.57 0.43
71.85 2.21
74.73
+ 1.11
APPNP
91.44 + 1.48
0.19
95.79 0.28
54.77 + 1.66
42.87 2.07
MixHop
86.05 + 4.01
03.47
93.80 0.28
59.48 3.15
53.18 0.69
GPR-GNN
91.02 + 1.76 95.35 + 0.14
96.04 0.16
46.24 + 10.26
45.73 + 0.95
Table 9: ID ACCs of pre-trained GCN models on five large-scale datasets. We report the average values that are percentages over 5 independently trained backbones.
Backbone
reddit2
ogbn-products
arxiv-year
snap-patents
wiki
GCN
51.36 + 0.35 74.39 0.09 56.67 + 0.33 62.48 + 0.10 54.89 + 0.16
Table 10: ID ACCs of three training-bra based ood detection methods five small- scale datasets. For each method, we take the average values that are percentages over 5 independently runs.
Method
Cora
Amazon
Coauthor
Chameleon
Squirrel
GKDE
91.40 + 1.39
91.30 + 2.30
96.14 = 0,50
65.22 + 1.67
53.29 2.97
GPN
91.49 = 1.51
93.96 = 2.39
89.83 = 4.25
62.40 + 1.40
46.27 5.37
OODGAT
76.02 = 7.77
61.88 + 1.19
31.71 = 1.06
61.00 + 2.84
50.88 2.35
Table 11: ID ACCs of three training-barc based methods on five large-scale datasets, where OOM means Out-Of- and OOT denotes that results have been got after running over 48 hours for each run. All the training-based methods only have results on the moderately sized arXiv-year dataset. For each method, we take the average values that are percentages over 5 independently runs.
Method
reddit2
ogbn-products
arxiv-year
snap-patents
wiki
GKDE
OOM
OOM
OOT
OOM
OOM
GPN
OOM
OOM
43.07 + 2.02
OOM
00M
OODGAT
OOM
OOM
43.43 + 0.36
0OM
OOM
20

---

D.2
Detailed Main Graph OOD Detection Results
Table 12: Detailed main results common benchmarks. Comparison with competitive out-of-distribune detection methods pre-trained GCN. We take the average values with standard errors that percentages over 5 independently trained backbones. 1 (L) indicates larger (smaller) values are better.
Chamllen AURUCT
Squieed
FPR.
AUROC
AUROCT
AUROC
AUROU
MSP
70.86
55
$4.56 1 5:39
49.30
10.51
19 54
1.40
25.82
194
94.66 D.0
$5.10
7.09
57.6 1:11
94 1:01
65.51 1.46
Ensrgy
67.51 2: 22.58
55.47 2: 4.95
42:13
9.96
30:25
3.42
21.29 1.49
95.67 2
85.06 2:
4:31
50.15
1.42
1.68
Mahulanobi
09.08
14.00
5.96
7.97
84.8
95.55
0.51
0.70
GRDE
03:71 8: 14.36
86.27 x: 2.69
11.29 = 3.36
77:25-5.55 5.50
25.45 1:48
0:.13-2:1:29
92.99 4:399
2.50
96.71 9.07
09.36 2: 3.58
GPN
39:45
51.08
82:03 4: 11:20
72.05
19.77
82.63
34.11
22.46
03.82 8: 2.63
82:23
6.55
68.20 6.50
95.58 1.85
63.38 4.43
GODGAT
8.25
NODESafe
25.23
13.31
0,00
0.56
100,00 0.000
0.23
IDBD
81.56 8 10.45
56.77 +: 12.97
$1.87 13,99
73.31
7.86
99.68
3.50
63.10:1 1.01
89.85 2: 11,50
50.85 14.89
94.78 1.30
53.17
GRASP
26.70 6 12.35
93.90
8: 1.65
14 6.683
96.68
0.38
734
0.16
99.38
0:138
66.88 11 6.48
76.91
4.18
$5.89
3.61
61:09 1.49
Table 13: Detailed main results large-scale benchmarks. Comparison with competitive out-o--distributiin detection methods on pre-trained method GCN. take average values with standard errors are percentages over independently trained backbones. OOM means Out-Of-Memory and OOT denotes no (1) indicates larger (smaller) values are better.
results have been got after running over 48 hours for each run. t
Dacasets
Methed
stsp-pulents
wikd
FPR
AUROCT
FVR
AUROC
FPR
AUROC
FVRC
AUROC!
FPR
AUROCT
44.13
1.07
29.02
66.26
64.22 2,00
35
57.95
90.4
1.09
0.93
63.99
OPIN
96.74
44.69
85.60 9.3
06.95 0.52
47.95
96.27
0.30
0187
9788
29.11
Mahslamobi
71.73 1,55
74.89 =: 1.01
0OM
58.60 2: 1.27
59.57 2: 1.27
96.03 0.22
58.50
0.81
72.33 2: 2.15
67.95
1.56
GKDR
DETF
DOM
O0M
00M
0OM
CPN
DOM
DOM
95.63 3: 3.29
50.9T 2: 14,98
0OM
OOM
DOM
NODESaf:
10:45
OCT
35.32
100.00
55.72
63.41
0.20
1.23
GRASP
98.50
19.07
0.24
81.22
75.22 0.09
0.06
3:
21

---

D.3 Graph OOD Detection Results on Various Backbones
GRASP can seamlessly be applied various GNN backbones. In this section, report the OOD detection performance of all baselines on various popular architectures in Table 14
Table 14: Results of various GNN pretrained backbones on common benchmarks.
Pre- truined
OOD
Datasets Coauthor
Detection
Cora
Amazon
Chameleon
Squirrel
Buckhone
Method
FPR.
AUROC1
FPR.
AUROCT
FPR.
AUROC
FPR
AUROCT
FPR.
AUROCT
MSP
70.86
84.56
49.26
89.34
28.82
94.34
85.70
57.96
94.68
48.51
Energy
67.54
85.47
42.13
90.28
20.29
95.67
88.06
59.20
93.98
45.07
KNN
90.20
70.94
84.71
51.24
90.13
93.38
57.90
94.72
54.68
GCN
ODIN
68.41
84.98
44.05
89.90
22.59
95.27
85.31
57.94
94.17
44.08
Mahalanobis
69.68
85.48
96.49
75.58
85.71
84.98
95:55
53.19
94.90
54, 54,99
GNNSafe
GRASP (ours)
29.70
93.50
14.38
96.68
7.84
97.75
66.88
76.93
85.39
61.09
MSP
55,33
88 58.82
29 88
94.39
28.15
94.26
91.27
61.94
21
47.50
Energy
80.71
92.71
KNN
71.14
81.28
46.42
90.74
42.51
91.51
89.02
61.13
95.37
53.16
GAT
ODIN
35,27
89.05
26.92
94,89
24.61
94.95
90.83
62.89
916.11
45.68
GNNSafe
58.97
85.64
29.12
93.16
25.41
93.91
100.00
50.39
100.00
36.21
GRASP (ours)
22.76
94,28
14.21
96.79
8.59
97.51
70.15
73.40
85.84
61.18
MSP
81.33
80.40
32.45
94,
26.43
94.44
86.42
68.
94.93
$1.83
Energy
96.56
70.16
40.90
93. 80
18.75
95.75
91.92
65.16
95.36
49.68
KNN
94.64
GCNJK
ODIN
81.04
80.68
35
95.13
21.12
95.41
86.03
68.58
95.00 04
50.64
Mahalanobis
60,84
86.20
G1.61
87.11
83.04
87.
87.23
66.61
91.52 52
57.24
GNNSafe
GRASP (ours)
29.69
92.98
12.66
96.86
8.03
97.74
$9.61
75.78
86.02
60.70
MSP
69.56
84.51
47.21
91.32
24.66
95.37
94.39
55.43
94.67
50.98
Energy
85.75
KNN
82,54
74.32
70.98
83.48
38.95
92.56
92.21
61.14
95.20
54.32
GATJK
ODIN
64,25
85.21
39.23
96.30
93.56
Mabalanobis
79.60
79.33
$2.79
88.53
34,60
93.68
91.59
$2.38
91.52
56.19
GNNSafe
44.43
90.01
22.46
95.45
17.54
95.12
100.00
50.39
100.00
36.15
GRASP
29.04
92.57
14.78
96.70
8.32
97.70
78.65
71.09
85.88
MSP
59.37
89.01
64.64 64
86.51
18.38
96:45
24
48.87
94.41
50,91
Energy
81.82
81.21
62.87
84.36
14.57
97.01
90.55
55.75
90.91
53.04
KNN
81.21
APPNP
ODIN
56.72
89.47
60.67
86.76
15.02
96.98
94.63
50.71
94.41
50,60
Mahalanobis
73.64
86.02
98.75
62.13
30,20
93.91
92.38
58.15
93.29
56.65
GNNSafe
96.60
GRASP (ours)
26.45
94.16
5.69
97.11
8.69
97.59
83.41
63.02
86.42
60.76
67.00
86.50
59.23 23
40.35
62.79
94.34
$7.21
Energy
68.06
86.84
$7.05
86.21
97.85
$1.65
66
63.24
96.75
53.18
KNN
$0.00
79.68
63.885
80.54
60.66
77.25
95.13
$6.89
62
57.45
H&GCN
ODIN
65,21
87.10
99.43
91.07
63.52
Mabalanobis
81.67
80.55
86.26
77.33
97.92
61.02
97.62
58.29
96.36
53.54
GNNSafe
43.97
88.83
33.40
90.87
93.00
43.22
100.00
50.35
100.00
36.26
(ours)
MSP
83.94
78.60
$3.56
90.97
48.66
90.91
92.95
56.77
95 60
49.07
Energy
83.67
77.15
57.04
89.28
288.49
94.67
94.10
57.21
61
48.87
KNN
93.36
85.
89.52
MixHop
ODIN
83.14
79.31
50.00
91,25
41.39
92.65
93.45
56.48
95 68
47.58
Mabalanobis
82.35
80.04
90.05
81.85
47.41
91.67
93.93
56.30
91.33
56.56
GNNSafe
66,86
83.77
GRASP (ours)
32.11
92.77
10.07
96.99
9,41
97.31
76.92
66.12
85.92
60.69
64.90
87.44
87.66
23,96
95.
47
Enengy
72.85
83.86
64.23
85,28
16.42
96.50
93.78
49.09
95.16
42.63
KNN
74.24
81.45
48.47
90.48
38.83
92.11
94.39
55.31
94. 18
11.74
GPR-GNN
Mahalanohis
79.56
84.53
97.25
69.75
49.93
91.56
87.01
55.95
87.24
61.10
GNNSafe
$1.65
85.91
13.63
96.46
14.73
95.96
100.00
50.32
100.00
36.25
(ours)
MSP
72.85
83.02
51.72
88.13
23.18
95.21
96.03
$5.46
94.13
49.46
Energy
83.15
75.24
48.28
88.78
17.72
96.03
95.87
56.75
94.61
48.63
KNN
83.99
76.02
86.74
36.05
93.43
94.72
94.65
$3.47
GCNI
ODIN
71.49
83.31
49.44
88.35
19.44
95.75
95.61
56.63
94.73
48.34
Mabalanohis
73.90
82.01
77.63
80.87
44.01
92.63
96.68
46.57
91.66
53.62
GNN
66.70
83.12
27.00 00.08
93.13
17.87
94.47
100.00
50.35
100.00
36.32
GRASP (ours)
27.92
93.51
23.53
93.72
8.82
97.61
76.79
66.44
$6.27
60.62
22

---

D.4 Analysis of Syper-parameters Sensitivity
We show the sensitivity of hyper-parameters a, 8 and k in Figure 6. The vertical axis in the figure represents the average AUROC values across common datasets. The performance comparison in is reported by fixing other hyper- rrpee-parameters We see that the bar plot for each hyperparameter values, our proposed method's performance does not vary within the range of chosen significantly, which constantly outperforms baselines by large margin.
84
84.8
85.2
83.9
84
84
84.8
85.2
86
84
84
84.6
85.2
84.4
AUROC
AUROO
AUROC
82
82
82
81.6
80
80
80
78
78
78
1.0
2.5
5.0
10.0
15.0
2
10
k
Figure 6: Sensitivity analysis of all the hyper-parameters and the averaged AUROC values of common benchmarks on model GCN with MSP are displayed. The middle bar in each plot corresponds to the hyperparameter value used in main experiments.
D.5
Relationship between Ratio of Intra-Edges and OOD Detection performance
Pearson Correlation 0.996
80
AUROC (%)
60
40
40
100
Ratio of intra-edges (%)
Figure 7: Ratio of intra-edges and OOD detection performance have strong positive correlation.
As shown in Figure the ratio intra-edges and OOD detection performance have strong positive correlation. This validates the correctness of Theorem 4.2. The detailed the number in Figure 7 are listed in Table 15. From the table can that after using our proposed augmentation, the ratio of intra-edges increases and in turn boosts the OOD detection performance.
23

---

Table 15: Ration of intra-edges kntra and respective OOD detection performance on all benchmarks before and after employing graph augmenaatii iimeenation
emp
Before Aug
After Aug
Datasets
Tintra
AUROC
Tjitta
AUROC
cora
82.31
87.52
92.23
93,50
amazon
93.44
96.27
96.56
96.68
coauthor
92.68
95.82
97.18
97.75
chameleon
57.03
50.42
78.81
76.93
squirrel
39.45
35.88
62.54
61.09
reddit2
40.30
31.99
97.90
98.50
anapa
ogbn- igbn-products
81.98
85.66
93.56
93.79
arxiv-year
41.93
35.30
82.15
81.24
snap-patents
34.74
27.35
71.74
72.13
wiki
60.31 6
60.32
79.64
77.97
D.6 Computational Complexity Analysis
Our method's computational footprint in terms of runtime and memory usage after propagation for k: times is:
Time Complexity: O(N 2k|E| n)
Memory Complexity: O(N + [E| +2)
While our algorithm introduces the fully connected matrix E, which brings about explosive growth of connections after each propagation and results in challenges in performing related computations, adeptly transform the complex and time-consuming structural computations into simple matrix-vector multiplication
boormingg
coomeii openation operations, making original expensive operation tractable and leading to efficient linear complexity. Below, we provide the support from both mathmatical and empirical points.
com
mathmatica
Complexity analysis. Our method consists of two major computational modules, specifically, (a) calculating connections between training nodes and testing nodes; (b) augmentation propagation.
(a) Calculating connections between training nodes and testing nodes. We utilize two indicator vectors, Tia and I oods both with length of nodes number N, to represent the number of connections each node has with St and Sood. respectively. The initial values of Lid are set to at the indices modending corresponding corresponding to Sta and 0 at the remaining indices (corresponding to Sooa). The initial value of
resppiiiing
La is denoted as 1(0) Similarly, Inod has initial value of all indices corresponding to Sood
proppe Daeeggaann for & times, the connections between each node with Sta are:
and 0 at the indices corresponding to Sid- We also represent the initial value of Lood as I (0) ood After
(k) id
A
(0) sd
A 1-1
AT (0)
Ak-1 (()
id
(run 1 times... ...)
In the above equation, AT( can be computed in O(Era) with sparse matrix multiplication for each proppaa deeagattona where [Eal represents number of edges connected to Sea nodes.
The above abalysis and conclusion also applys to computing (k) ((Exod)) ), where [Eooa] number of edges connected to Sood nodes. This leads to time and memory costs O( + [Eooa)) = O(EE) for calculating needed number of connections in each propagation and O Ell and O(El) for time and memoory costs after propagation for & times, respectively:
resulting computational complexity
(b) Augmentation propagation. As described by Equation in the main paper, given a raw OOD Auggmeet
scoring vector g E N the propagates scoiing vector using augmentated aetaccency matrix after

---

propagation for & times is given by:
EGRASP \
(D (
( E)g
Ag
D4
Eg
= (run k times ...)
In the above equation,
Eg can be computed with time/space complexity Onn) by simple summation operation (gi in G will be replaced by Eieg to get rid of the matrix multiplication.
Ag can be computed in O(EE) with sparse matrix multiplication.
D..'' is ((N) operation since it is scaling over all elements in the vector.
Above all, the time/memory complexity of augmentated propagation is O(N + |8 n) for each propagation and the time and memory costs are O(N + k|εl + n) and O(N + |ε] + n) for k times respectively with memory reutilization.
Integrating the above considerations, the time complexity of our algorithm after propagation for times is O(N + [ + n), while the space complexity is O(N + n)). Notably, the utilization of space reuse results in linear space complexity.
Empirical results. Then conduct comprehensive experiments comparing the time and space costs of our algorithm with various baselines (both post-hoc and training- based approaches) in Table 16 and Table 17. From the experimental results, it is evident that algorithm highly efficient across all datasets.
Based on the experimental results in Table 16 and Table 17, we have:
comparison to training-baan based methods, post-hoc methods exhibit significantly lower runtime and memory consumption.
Considering that the minimum time and space complexity required to run a graph algorithm is O(N + |,)) as outlined in our algorithm complexity analysis, our algorithm incurs limited addi- tional time and space costs, specifically O(E)) and O(n) on time and memory costs respectively in each propagation. This can be validated by the small extra overhead incurred by our algorithm compared to MSP Energy from the table.
Compared with training- based methods, our algorithm demonstrates substantially lower time and space demands on five large-scale datasets. And when compared to post-hoc baselines on these datasets, the overhead of our method is also reasonable. The performance of our method these large-scale datasets underscores the strong practicality of our approach.
Table 16: Time (s) and Memory (M) costs of all algorithms with backbone GCN on common benchmarks.
Datasess Coanthor
Chameleon
Squirrel
time
memory
time
memory
time
memory
time
memory
time
memory
GKDE
26.720 73078
3366 0078
160.00044
3388. 58.59
1004,73209
4199.8438
37. 37.24027
3310:9219
170.25729
3134 3828
GPN
28 63996
58,71772
3719.19977
50665488
36201968
50.69752
3650.5761
OODGAT
77,98510
395887711
411.43511
6289
3319.9883
MSP
0.02508
622.7852
0.03915
635.4102
0.13018
1092.0469
0.04835
634.0508
0.05129
657 9961
Energy
0.04687
624.
0.09624
636.5156
0.11084
1094,7227
0.10995
634.7500
0.11732
660.5039
KNN
0.24068
630.9219
0.12629
658.2109
0.29778
1101.2969
0.17118
636.4375
0.14258
660.1755
0.06357
Mahalanobis
0.14636
627.3945
0.22022
641.2070
0,28833
1099,3750
0.20611
637.1797
0.18573
4375
GNNNSffe
(.05700
626.2344
0.14713
652,7969
0.34739
1105.1875
0. 12292
637.9551
10544
662 4766
GRASP(OErS)
0.053015
628,7933 7930
0,14779
677.2617
0,25272
1118.0156
0.14554
644.0938
0,12774
668 0742
25

---

Table 17: Time (s) and Memory (M) costs of all algorithms with backbone GCN large-scale benchmarks.
Datasels arsiv-year
Method
reddit2
eghnn-proucct
snap-galents
wiki
time
mimory
time
memory
time
time
memory
time
GRDE
OOM
GOM
GPN
0OM
OOM
3808.722
OODGAT
00M
0OM
1214,97670
3491.1055
0OM
OOM
MSP
0.26172
258 9844
D.4509
4571 1289
0.3554)
726. 5898
8.91248
4014
431 68647
9765.8008
Energy
0,26987
2590.5273
0.19158
1.567.3398
0.51500
726.1719
11.840266
4039.9102
296 09063
9788.4153
KNN
3,48512
2697. 37889
4247 99327
4699. 30-17
3.77242
732. 132.8984
6241,00550
1933.3164
3180.91954
9812.8906
0,28500
4562.1719
30793
9761)
2703
1.27940
GNNSafc
0.85515
2621 5547
1.19187
1589.900 938999609
0.97220
1902
17,00348
1187 6680
39017
9655. 1055
GRASP(vers)
1,86665
2628.3633
3633
9.62959
4647.5273
0.67847
768.2070
20,97008
4279.9219
649.71668
9724.7852
D.7 Explore How Different Propagation Mechanisms Impact the Findings.
In this section, we investigate the effect of different propagation mechanisms on graph OOD detection performance, like higher-order diffusion and the other various classical propagation mechanisms in the literature, including Personalized PageRank (PPR) [35], Heat Kernel Diffusion (GraphHeat) [80], Graph Diffusion Convolution (GDC) [20]. Mixing Higher-Order Propagation (MixHop) [I]. and Generalized PageRank (GPR) [10]. The emperical observations
follows:
From the analysis of the hyper-parameter (order of propagation) and its impact the AUROC in Figure 6, we find that OOD detection performance benefits from propagation orders within reasonable range. However, excessive propagation (greater than 16) may be detrimental.
The AUROC results of the other various classical propagation mechanisms on graph OOD detection are shown in Table 18 and Table 19. We can see that these propagation mechanisms perform inconsistently among various datasets. In contrast, our propagation mechanism GRASP constantly demonstrates superior performance among all datasets.
Table 18: Various classical propagation mechanisms on each dataset.
Method
Cora
Amazon
Coauthor
Chameleon
PPR
91.98
95.45
97.29
49.22
GraphHeat
63.72
63.39
67.52
50.67
GDC
89.33
90.47
95.29
59.91
MixHop
91.49
94.42
97.09
49.33
GPR
91.87
94.81
97.23
48.62
GRASP
93.50
96.68
97.75
76.93
Table 19: Various classical propagation mechanisms on each dataset.
Method
Squirrel
arXiv-year
snap-patents
wiki
PPR
52.31
56.87
46.70
34.83
GraphHeat
53.92
38.40
41.00
0OM
GDC
48.17
0OM
0OM
0OM
MixHop
51.29
34,41
28.93
39.22
GPR
52.49
34.30
29.66
36.98
GRASP
61.09
81.24
72.13
77.97
E Limitations
While the proposed method of OOD score propagation shows promise in improving OOD detection in graph learning, there limitations worth noting. The effectiveness of the method heavily relies on the connectivity and structure of the graph. scenarios where the graph exhibits random connectivity patterns, the propagation of OOD scores with the proposed solution may longer be effective. Addressing these limitations will be crucial for ensuring the robustness and generalizability of the proposed OOD detection approach in graph learning.
26

---

F
Broader Impact
This paper on detecting
(OOD) nodes in graph learning holds significant potential for various fields and applications. By addressing a salient yet under-explored challenge in graph neural networks, the proposed method of OOD score propagation offers promising avenue for enhancing the robustness and reliability of graph-based machine learning systems. The implications extend beyond the realm of graph learning, OOD detection is a critical component in many real- world applications, including anomaly detection, fraud detection, and network security. Improving OOD detection in graph structures can lead to more accurate and reliable decision-making in domains such as social network analysis, recommendation systems, and biological network analysis. Overall, this research has the potential to drive advancements in graph graph-based based machine learning and contribute the development of more robust and reliable Al systems with broader societal impact.
G Other Related Works
Graph OOD Generalization. Unlike graph OOD detection, which aims to increase the gap between ID and OOD for effective OOD detection, graph OOD generalization aims learn the invariant aspects behind ID and OOD. By enhancing these invariant points, the gap between ID and OOD data is reduced improve the robustness of graph models on OOD data. The distinction among different proposed methods lies in identifying different invariant factors. GTRANS [30] leverages contrastive learning to learn the optimal perturbations of features and structures to enhance the GNN model's robustness against OOD. GRAPHPATCHER [31] improves GNN's robustness against low-degree scenarios during testing by corrupting portion of nodes and reconstructing the original structure. LiSA [85] employs variational subgraph generators to generate label-invariant subgraphs for data augmentation, thereby enhancing the robustness of GNN models. [9] leverages the stability of correlation and employs a graph decorrelation method learn stable associations, raising the graph OOD generalization capability. [78] boosts gencralization by eliminating confounding bias. [41] extrapolates structure and feature spaces to generate OOD graph data, which is then used for data augmentation to improve OOD generalization. [28] strengthens graph OOD generalization by extracting invariant subgraphs and learning invariant patterns behind graphs based on these subgraphs. [8] introduces a set of minimal assumptions for feasible invariant graph learning. [5] investigates OOD generalization under different structural shifts. [22] incorporates label and environment causal independence to discover causal subgraphs for intensifying OOD generalization. [86] improves the OOD generalization of dynamic graphs by learning spatio-temporal invariant patterns from an environment learning perspective.
27

---

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: We provide theoretical contribution in Section 3 and Section 4, and experimen- tal results in Section 5.
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 NA answer to this question will not be 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. It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification:
We present the limitation discussion in Appendix E.
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 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 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.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged 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.
the paper. The authors should use their best
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:
We provide the assumptions and complete proof in Appendix A.
28

---

Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' 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 short proof sketch to 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 properly referenced.
4. Experimental Result Reproducibility
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 of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Section 5 and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it 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) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.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 or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. 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 faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: https: //tpt/tbttttttt//// www wwwm/oogfeiimaal///cccooo..oo
29

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
guides/CodeSubmi
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 (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips... cc/ cctppccccc/c//cccccccccccccc.lll pppppc/guuudeeeee httpa//guiieee/oeeuuuiiiiiii /woo//eebbiiiiiiiioe. cttpiiiissioooiiiyy...o for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
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).
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
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: See Section 5.
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 a level of detail that is necessary 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: [No]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. 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.
30

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еттог rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix D.6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of 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
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htppp::///eurrs...// httpa////errrps.cpppllll/a.. wec//uulic//eee / csGuidel ines?
Question:
Answer: [Yes]
Justification:
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 a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Appendix F
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 no 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., deeloyymem 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 tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to train models that generate Deepfakes faster.
31

---

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 as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms 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 high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or 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: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use 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, if possible, include URL.
The name of the license (e.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, saperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- 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 is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: https: httpt/gtttttttttt/e/e//ett www.://w...omononnneinnaaaa////a
32

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model 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 used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
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)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: 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?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not 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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "Y3ywfBmWbO", "reviewer": "Reviewer_hQev", "summary": "This work aims to detect out-of-distribution (OOD) nodes on a graph by exploring useful OOD score propagation methods. It introduces a novel edge augmentation strategy, with a theoretical guarantee. The approach's superiority is empirically demonstrated, outperforming OOD detection baselines in various scenarios and settings.", "questions": "Q1. Is the classification accuracy in Appendix D.1 assessed before or after employing GRASP? Is there a comparison between the two?  \n\nQ2. Do similar cases discussed in Figure 2 exist within real-world datasets?  \n\nQ3. What is the accuracy of the edge-adding method presented in the text, specifically how many to intra-edges, and how many to inter-edges? What impact would incorrectly added edges have on the results?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "S1. The paper conducts an in-depth analysis and empirically validates the beneficial conditions for  OOD score propagation in a graph.\n\nS2. The paper introduces the GRASP methodology, which addresses the limitations of previous score propagation methods and demonstrates superior performance in node-level OOD detection tasks.", "weaknesses": "W1. Does the strategy of utilizing GRASP with additional edges compromise classification accuracy within the distribution? In other words, how can you balance the homogeneity of graph classification with the homogeneity of OOD detection tasks when adding edges?  \n\nW2. While this method is suitable for node-level OOD detection, it appears to be more challenging to adapt it to subgraph-level tasks or graph-level tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:\n\n>**W1. Relationship between GRASP and the in-distribution classification accuracy.**\n\nFair concern! GRASP is a post hoc OOD detection method that does not interfere with the classification process. Therefore, the classification accuracy of in-distribution (ID) data remains unchanged.\n\n>**W2. Extension to subgraph-level tasks or graph-level tasks.**\n\nWe appreciate the reviewer's suggestion to extend our work to different tasks! While our primary focus is on the node-level setting, we are open to discussing how GRASP can be adapted for subgraph-level or graph-level tasks. One potential approach is to treat a subgraph or graph as a single node, with the similarity between subgraphs or graphs represented by the weights of edges. This adaptation would enable the application of our method to these broader contexts.\n\n\n\n>**Q1. Is the classification accuracy in Appendix D.1 assessed before or after employing GRASP? Is there a comparison between the two?**\n\n(Related to W1) The classification accuracy presented in Appendix D.1 is from the pretrained ID model before employing GRASP. Since our method is post hoc, the classification accuracy remains the same across all post hoc methods.\n\n\n>**Q2. Do similar cases discussed in Figure 2 exist within real-world datasets?**\n\nYes, they do. Figure 2 is designed to intuitively illustrate our theoretical findings, which are authentically reflective of real-world scenarios. Our theory suggests that score propagation enhances OOD detection performance when intra-edges are predominant. This behavior is captured in real-world datasets, as supported by the empirical evidence presented in Table 14.\n\n\n>**Q3. What is the accuracy of the edge-adding method presented in the text, specifically how many to intra-edges, and how many to inter-edges? What impact would incorrectly added edges have on the results?**\n\nThe accuracy of the added edges on the common datasets is shown in the table below:\n\n| Datasets  | Added Edges' ACC         |\n|-----------|-------------|\n| cora      | 0.94 |\n| amazon    | 0.94 |\n| coauthor  | 0.99 |\n| chameleon | 0.80 |\n| squirrel  | 0.80 |\n\nWe investigate the impact on GRASP's performance by adding varying proportions of incorrect edges. The results are presented in the table below, with the \"ratio\" column indicating the proportion of incorrect edges added. The results show that GRASP's performance deteriorates significantly when the proportion of incorrect edges exceeds 0.3.\n| Datasets | cora   |        | amazon |        | coauthor |        | chameleon |        | squireel |        |\n|----------|--------|--------|--------|--------|----------|--------|-----------|--------|----------|--------|\n| ratio    | AUROC  | FPR95  | AUROC  | FPR95  | AUROC    | FPR95  | AUROC     | FPR95  | AUROC    | FPR95  |\n| 0        | 98.78  | 0.42   | 99.85  | 0.21   | 99.79    | 0.00   | 95.06     | 5.79   | 92.27    | 7.99   |\n| 0.1      | 87.04  | 54.57  | 90.86  | 47.73  | 90.03    | 39.10  | 77.91     | 55.09  | 70.04    | 66.20  |\n| 0.3      | 57.33  | 77.98  | 65.04  | 80.70  | 66.63    | 79.13  | 63.89     | 76.94  | 49.63    | 91.78  |\n| 0.5      | 42.52  | 80.94  | 37.09  | 90.60  | 40.75    | 88.16  | 45.79     | 90.72  | 23.43    | 96.29  |\n| 0.7      | 38.88  |  86.97 | 30.27  | 95.63  | 34.64    | 92.78  | 28.41     | 97.34  | 12.20    | 99.91  |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jdN9M3Clus", "reviewer": "Reviewer_xmGd", "summary": "The paper proposes a methodology called Graph-Augmented Score Propagation to improve OOD detection performance on graphs. The key idea of the paper is an edge augmentation strategy which selectively adds edges to a subset of training nodes, which is combined with score propagation for the OOD node detection task on the graphs. Theoretical analyses is provided which links the OOD score propagation to the intra-edge vs inter-edge ratios between ID and OOD samples. Experimental results are provided on several real world graph datasets with the measurement of OOD detection metrics for demonstrating the effectiveness of their method.", "questions": "How would the authors ensure robustness of their detection method when the confidence could vary? (see weakness pt 1 above) Did the authors do any experiments to evalute the robustness of their method and how would they address it?", "limitations": "The authors mention the limitations of their work in Appendix section E and societal impact in Appendix Section F.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper is generally well written, well motivated and easy to follow. \n\n2. Theoretical analysis of the setting when OOD score propagation will be effective is helpful for future work in this direction, and for developing OOD detection methods for graphs. \n\n3. The key idea of the work for OOD detection is presented as a post hoc strategy, hence the practical applicability of the method is good. \n\n4. Results in Table 2 and 3 are convincing.", "weaknesses": "1. The creation of the subset G is dependent on the selection of S_id and S_ood examples which uses the MSP as a measure of for creation of these sets. However it has been well-discussed that MSP suffers from several practical issues such as overconfidence [Hendrycks and Gimpel,  ICLR ‘17], poor generalization [Lee et. al, NeurIPS ‘18] and calibration issues [Guo et al, ICML ‘17]. Because of GRASP’s dependence on the MSP for creating the set G, the overall method can be non-robust. \n\n\n2. Error bars are missing from all the results, which is important for assessing the consistency of the proposed method, since the data augmentation could be significantly affected by the randomness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:\n\n>**W1&Q1. Concern about using MSP score to select S_id and S_ood.**\n\nThank you for this insightful question! We acknowledge the concern that the model can sometimes exhibit overconfidence for certain OOD nodes. However, this does not undermine the applicability of GRASP when ID nodes' MSP scores are generally higher than those of OOD nodes. As demonstrated in Figure 4, we selectively utilize the highest MSP scores for ID and the lowest for OOD. This selection strategy results in more accurate estimations of $S\\_{id}$ and $S\\_{ood}$. \n\nWe empirically support this approach with results presented in Tables 2, 3, and 5, across five datasets (Squirrel, Reddit2, arXiv-Year, snap-patents, and Wiki). These results show significant performance improvements with GRASP, particularly where original MSP scores were ineffective, ensuring more accurate distinctions between $S_{id}$ and $S_{ood}$ in each iteration.\n\nAdditionally, our method offers high flexibility—**it can integrate any existing OOD scoring function**. While we use MSP in our primary demonstrations to explain GRASP's principles, substituting MSP with other well-known OOD scoring methods in our framework also yields competitive results, as shown in Table 7. This highlights GRASP’s adaptability and robustness.\n\n>**W2. Suggestion of including error bars.**\n\nThis is an excellent suggestion! We have now included the main results with standard errors for all datasets in the revised manuscript and the table below. It is important to note that the FPR95 metric displays a relatively high standard error across methods on the Cora, Amazon, and Chameleon datasets due to their small sizes, which makes the outcomes sensitive to variations in data splits. Nonetheless, our method consistently remains competitive across all five runs, as detailed in the updated table in the second part of the response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "axepZmguEX", "reviewer": "Reviewer_aWhs", "summary": "This study investigates the effectiveness of score propagation in graph raph Out-of-Distribution (OOD) detection. It explores the conditions under which score propagation can be beneficial and proposes an edge augmentation strategy (GRASP) to improve its performance. The authors provide theoretical guarantees for GRASP and demonstrate its performance compared to existing OOD detection methods on several graph datasets.", "questions": "1. How does the performance of GRASP vary with different OOD distributions (e.g., uniform, normal, outliers)?\n\n2. Can the authors provide further insights into how GRASP works and how it interprets the graph structure?\n\n3. How does the performance of GRASP scale with the size of the graph and the number of nodes? Is there any systemic analysis?", "limitations": "I did not find significant limitation of this study, one point may concern me that the effectiveness of GRASP relies on the connectivity and structure of the graph. In scenarios with random connectivity patterns, the method may not be as effective..", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The study delves into the mechanisms of score propagation and derives conditions for its effectiveness. This theoretical foundation is solid and extends the understanding of graph OOD detection.\n\n2) The proposed GRASP method is a practical and efficient solution for improving OOD detection performance. The results showed that GRASP has achieves the SOTA performance.\n\n3.) The paper is generally in well-written and easy to follow.", "weaknesses": "1) it is strongly suggested to release the source code of experiments.\n\n2) Considering the imporvement is margin in Table 2 and 3, it is also suggested that the authors should provide a standard error with statistical significance analysis in the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:\n\n>**W1. it is strongly suggested to release the source code of experiments.**\n\nSure! We have made the source code available at the following link: https://anonymous.4open.science/r/GRASP-EEA3/README.md. \n\n\n>**W2. Considering the imporvement is margin in Table 2 and 3, it is also suggested that the authors should provide a standard error with statistical significance analysis in the results.**\n\n\nWe appreciate your observations regarding the improvements in Table 2 and 3! We'd like to emphasize that the overall improvement of our method is substantial. Nevertheless, your suggestion about including the standard error (STD) to provide statistical significance analysis is well taken. We have updated the manuscript to include standard errors for all datasets. It is important to note that the FPR95 metric displays a relatively high standard error across methods on the Cora, Amazon, and Chameleon datasets due to their small sizes, which makes the outcomes sensitive to variations in data splits. Nonetheless, our method consistently remains competitive across all five runs, as detailed in the updated Table.\n\n| Datasets    | cora          |               | amazon        |               | coauthor     |               | chameleon    |               | squirrel     |               |\n|-------------|---------------|---------------|---------------|---------------|--------------|---------------|--------------|---------------|--------------|---------------|\n| method      | AUROC         | FPR95         | AUROC         | FPR95         | AUROC        | FPR95         | AUROC        | FPR95         | AUROC        | FPR95         |\n| MSP         | 84.56 ± 5.39  | 70.86 ± 15.88 | 89.34 ± 3.49  | 49.26 ± 10.51 | 94.34 ± 0.41 | 28.82 ± 1.94  | 57.96 ± 3.31 | 85.70 ± 7.09  | 48.51 ± 0.46 | 94.68 ± 1.01  |\n| Energy      | 85.47 ± 4.98  | 67.54 ± 22.98 | 90.28 ± 3.42  | 42.13 ± 9.96  | 95.67 ± 0.25 | 20.29 ± 1.49  | 59.20 ± 4.31 | 88.06 ± 7.50  | 45.07 ± 1.68 | 93.98 ± 1.42  |\n| KNN         | 70.94 ± 5.62  | 90.20 ± 4.35  | 84.71 ± 3.28  | 65.19 ± 7.26  | 90.13 ± 0.50 | 51.24 ± 1.83  | 57.90 ± 6.48 | 93.38 ± 5.48  | 54.68 ± 2.25 | 94.72 ± 2.84  |\n| ODIN        | 84.98 ± 5.59  | 68.41 ± 18.48 | 89.90 ± 3.65  | 44.06 ± 10.69 | 95.27 ± 0.33 | 22.59 ± 1.76  | 57.94 ± 3.75 | 85.31 ± 7.64  | 44.08 ± 0.35 | 94.17 ± 0.44  |\n| Mahalanobis | 85.48 ± 1.69  | 69.68 ± 14.60 | 75.58 ± 7.97  | 96.49 ± 5.96  | 84.98 ± 0.58 | 85.71 ± 1.82  | 53.19 ± 4.30 | 95.55 ± 2.36  | 54.99 ± 0.70 | 94.90 ± 0.51  |\n| GKDE        | 86.27 ± 2.69  | 63.71 ± 14.36 | 77.26 ± 5.54  | 81.29 ± 3.36  | 95.13 ± 0.29 | 25.48 ± 1.48  | 50.14 ± 5.50 | 92.93 ± 4.89  | 49.38 ± 3.58 | 96.71 ± 0.67  |\n| GPN         | 82.93 ± 11.20 | 58.45 ± 31.98 | 82.63 ± 5.87  | 72.95 ± 19.77 | 93.82 ± 2.63 | 34.11 ± 22.46 | 68.20 ± 6.70 | 82.25 ± 6.55  | 48.38 ± 4.43 | 95.58 ± 1.65  |\n| OODGAT      | 53.63 ± 5.13  | 94.59 ± 6.38  | 66.95 ± 16.02 | 71.34 ± 15.34 | 52.18 ± 8.26 | 96.53 ± 3.39  | 59.67 ± 6.37 | 94.43 ± 3.43  | 46.13 ± 3.10 | 95.27 ± 1.00  |\n| GNNSafe     | 87.52 ± 6.16  | 54.71 ± 31.41 | 96.27 ± 0.31  | 22.39 ± 4.90  | 95.82 ± 0.28 | 16.64 ± 1.90  | 50.42 ± 0.65 | 100.00 ± 0.00 | 35.88 ± 0.24 | 100.00 ± 0.00 |\n| GRASP       | 93.50 ± 1.65  | 29.70 ± 12.25 | 96.68 ± 0.28  | 14.38 ± 6.63  | 97.75 ± 0.18 | 7.84 ± 0.58   | 76.93 ± 4.18 | 66.88 ± 6.48  | 61.09 ± 1.49 | 85.59 ± 3.61  |\n\n| Datasets    | reddit2      |              | odbn-product |              | arxiv-year    |               | snap-patents |              | wiki         |              |\n|-------------|--------------|--------------|--------------|--------------|---------------|---------------|--------------|--------------|--------------|--------------|\n| Method      | AUROC        | FPR95        | AUROC        | FPR95        | AUROC         | FPR95         | AUROC        | FPR95        | AUROC        | FPR95        |\n| MSP         | 46.61 ± 0.66 | 96.59 ± 0.14 | 70.19 ± 0.92 | 86.87 ± 0.35 | 47.24 ± 3.70  | 95.03 ± 1.46  | 46.99 ± 0.83 | 94.31 ± 0.30 | 54.70 ± 0.68 | 95.46 ± 0.32 |\n| Energy      | 44.13 ± 0.14 | 96.77 ± 0.03 | 68.13 ± 0.38 | 85.09 ± 0.45 | 51.35 ± 5.91  | 94.10 ± 2.76  | 46.03 ± 4.59 | 96.82 ± 1.07 | 29.02 ± 2.78 | 97.31 ± 1.54 |\n| KNN         | 66.74 ± 0.55 | 90.78 ± 0.75 | 73.58 ± 1.21 | 84.22 ± 2.00 | 57.96 ± 2.19  | 95.35 ± 0.92  | 53.45 ± 0.93 | 90.54 ± 1.09 | 43.69 ± 4.83 | 93.43 ± 2.57 |\n| ODIN        | 44.69 ± 0.24 | 96.74 ± 0.07 | 68.95 ± 0.52 | 85.65 ± 0.31 | 47.36 ± 3.46  | 95.06 ± 1.47  | 45.20 ± 0.87 | 94.27 ± 0.30 | 29.91 ± 0.47 | 97.88 ± 0.18 |\n| Mahalanobis | 74.89 ± 1.01 | 71.73 ± 1.55 | OOM          |              | 59.57 ± 1.27  | 88.60 ± 1.27  | 58.50 ± 0.81 | 96.03 ± 0.22 | 67.95 ± 1.56 | 72.33 ± 2.15 |\n| GKDE        | OOT          |              | OOM          |              | OOM           |               | OOM          |              | OOM          |              |\n| GPN         | OOM          |              | OOM          |              | 50.97 ± 14.98 | 95.62 ± 3.29  | OOM          |              | OOM          |              |\n| OODGAT      | OOM          |              | OOM          |              | 59.38 ± 3.44  | 92.90 ± 0.94  | OOM          |              | OOM          |              |\n| GNNSafe     | 31.99 ± 0.26 | 99.49 ± 0.07 | 85.66 ± 1.16 | 77.86 ± 1.09 | 35.30 ± 0.06  | 100.00 ± 0.00 | 27.35 ± 0.18 | 99.92 ± 0.18 | 60.32 ± 4.51 | 72.63 ± 2.05 |\n| GRASP       | 98.50 ± 0.02 | 2.41 ± 0.09  | 93.79 ± 0.24 | 39.77 ± 1.25 | 81.24 ± 0.39  | 73.93 ± 0.60  | 72.13 ± 0.06 | 75.22 ± 0.09 | 77.97 ± 1.38 | 58.49 ± 1.07 |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nT1k0K2VrA", "reviewer": "Reviewer_hXZy", "summary": "In this paper, the authors attempt to tackle the task of detecting Out-of-Distribution (OOD) nodes in graph data. To this end, the authors propose an augmentation method, namely Graph-Augmented Score Propagation (GRASP). GRASP performs the task of OOD detection in graphs by increasing the ratio of intra-edges (i.e., edges only connecting in-distribution nodes or OOD nodes). Theoretical analysis is also provided to support the effectiveness of the proposed approach. Experimental results show that GRASP can outperform existing OOD detection methods in various datasets.", "questions": "1. The authors emphasize multiple times the importance of the number of intra-edges and inter-edges in OOD detection, providing theoretical proof. However, could a concrete example be provided to illustrate this concept more intuitively?\n2. Does the assumption that edges follow a Bernoulli distribution receive support in most real-world datasets, practical applications, or previous studies?\n3. In Table 3, the FPR on the dataset reddit2 is significantly lower than that of its comparison models. Could the author provide further explanation for this remarkable improvement?\n4. Is there any underlying pattern in the ratio of intra-edges to inter-edges when achieving the best OOD detection performance across different datasets?\n5. Can authors conduct broader investigations of recent related works, explicitly discuss the differences between the proposed and other related methods, and adjust the contributions of the paper (if possible)?", "limitations": "The authors have discussed the limitations of the proposed method in the Appendix.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method is introduced in an informative manner.\n2. The paper is easy to follow.\n3. The comparative experiments are comprehensive.\n4. The hyperparameter sensitivity analysis is thorough, providing readers with valuable insights.", "weaknesses": "1. At the beginning of the article, the author might overly emphasize the contribution of this article, to some extent giving the impression to readers that it is the first study on graph OOD detection. However, there have already been some papers in this area.​ For instance, 1) \"Learning on Graphs with Out-of-Distribution Nodes,\" in KDD 2022 (cited); 2) \"Generalizing graph neural networks on out-of-distribution graphs,\" in TPAMI 2023 (not cited); 3) \"Good-d: On unsupervised graph out-of-distribution detection (cited),\" in WSDM 2023. While their core idea differs from this paper, their contributions should not be overlooked. Given these observations, it is highly suggested that the authors conduct broader investigations of existing works, discuss the differences between the proposed methods and other related methods, and adjust the contributions of the paper.\n2. The baselines selected in the experiments may not be sufficiently novel. This makes the experimental results are not convincing enough.\n3. The proposed method needs more motivation from both theoretical and practical aspects. For example, are there any observations or previous studies supporting the assumptions that edges follow a Bernoulli distribution? Are there concrete (or real-world) examples that can demonstrate the importance of the number of intra-edges and inter-edges in OOD detection?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:\n\n>**W1&Q5. Suggestion on providing more discussion w.r.t the exisiting graph OOD works and comments on the paper's contribution position.**\n\nWe appreciate your comments and the opportunity to clarify and further discuss the positioning!\n\nFirstly, we acknowledge the contributions of previous works in this field and have made it clear from the introduction (line 29) that our approach is inspired by prior research [72]. If any part of the text inadvertently suggested that we were the first to address graph OOD detection, we are welcome with advices to eliminate possible confusion and better position our contributions.\n\nRegarding the discussion with references and existing works on graph OOD:\n\n1. **OOD Generalization vs. OOD Detection**. The uncited paper [A] suggested by the reviewer addresses a different problem -- OOD generalization rather than OOD detection. This distinction is crucial as OOD generalization focuses on correctly classifying domain-shifted data, which involves a different kind of \"OOD\" than the semantic shift concerns of OOD detection. Our work specifically targets scenarios where data does not conform to any in-domain class. \n2. **Graph-level vs. node-level**. We also note a significant body of research [B-G] that focuses on graph-level OOD detection. Our work, however, contributes to the less-explored area of node-level OOD detection, where current literature remains sparse [H-L]. Our findings help fill this gap by providing new insights and methodologies.\n3. **Training-required vs. post hoc method**. Methodologically, our approach differs significantly from those in existing literature, which often require extensive re-training [I-L]. Our post hoc solution (demonstrated in Tables 2, 3, 15, and 16) enables effective and efficient OOD detection, facilitating easier deployment and practical application in real-world scenarios.\n4. **New theoretical contribution**. Our paper introduces fundamental theoretical analysis, a first in the realm of node-level graph OOD detection. We elucidate key factors such as the importance of intra-edge dominance, providing a new theoretical framework that aids in understanding and addressing the unique challenges of OOD detection on graphs.\n\n\nWe hope these clarifications and expansions will address the concerns raised and better articulate the value and positioning of our work in the literature.\n\n[A] Generalizing graph neural networks on out-of-distribution graphs. TPAMI'23\n\n[B] GraphDE: A Generative Framework for Debiased Learning and Out-of-Distribution Detection on Graphs. NeurIPS'22\n\n[C] Towards OOD Detection in Graph Classification from Uncertainty Estimation Perspective.ICML'22\n\n[D] On Estimating the Epistemic Uncertainty of Graph Neural Networks using Stochastic Centering. ICML'23\n\n[E] GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection. WSDM'23\n\n[F] A Data-centric Framework to Endow Graph Neural Networks with Out-Of-Distribution Detection Ability. KDD'23\n\n[G] HGOE: Hybrid External and Internal Graph Outlier Exposure for Graph Out-of-Distribution Detection. MM'23\n\n[H] Energy-based out-of-distribution detection for graph neural networks. ICLR'23\n\n[I] Uncertainty aware semi-supervised learning on graph data. NeurIPS'20\n\n[J] Graph posterior network: Bayesian predictive uncertainty for node classification. NeurIPS'21\n\n[K] Learning on graphs with out-of-distribution nodes. KDD'22\n\n[L] Bounded and Uniform Energy-based Out-of-distribution Detection for Graphs. ICML'24\n\n\n\n>**W2. The baselines selected in the experiments may not be sufficiently novel. This makes the experimental results are not convincing enough.**\n\nTo address this concern, we have incorporated two latest  baselines, NODESafe [A] and fDBD [B], into our experiments on both common datasets (5 datasets) and large-scale datasets (3 datasets). NODESafe aims to reduce the generation of extreme scores when traing ID models on graphs, and fDBD detects OOD samples based on their feature distances to decision boundaries. Our results reveal that the performance of these methods lags significantly behind ours due to their inability to increase the proportion of intra-edges.\n\n\n\n| Datasets | cora   |        | amazon |        | coauthor |        | chameleon |        | squirrel |        |\n|----------|--------|--------|--------|--------|----------|--------|-----------|--------|----------|--------|\n| method   | AUROC  | FPR95  | AUROC  | FPR95  | AUROC    | FPR95  | AUROC     | FPR95  | AUROC    | FPR95  |\n| NODESafe | 84.09  | 68.73  | 68.65  | 91.51  | 80.26    | 71.74  | 50.72     | 92.29  | 49.26    | 94.60  |\n| fDBD     | 56.77  | 81.56  | 73.31  | 51.87  | 63.10    | 59.68  | 50.85     | 89.85  | 53.17    | 94.78  |\n| GRASP    | 93.50  | 29.70  | 96.68  | 14.38  | 97.75    | 7.84   | 76.93     | 66.88  | 61.09    | 85.59  |\n\n| Datasets | arxiv-year |        | snap-patents |        | reddit2 |        |\n|----------|------------|--------|--------------|--------|---------|--------|\n| method   | AUROC      | FPR95  | AUROC        | FPR95  | AUROC   | FPR95  |\n| NODESafe | 47.41      | 94.92  | 51.51        | 93.02  | 43.60   | 97.11  |\n| fDBD     | 48.87      | 95.82  | 43.27        | 94.99  | 55.72   | 89.78  |\n| GRASP    | 81.24      | 73.93  | 72.13        | 75.22  | 98.50   | 2.41   |\n\n[A] Bounded and Uniform Energy-based Out-of-distribution Detection for Graphs. ICML'24\n\n[B] Fast Decision Boundary based Out-of-Distribution Detector. ICML'24", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers and ACs,

We are grateful for the insightful comments and valuable suggestions from all reviewers. In the following, we would like to summarize the contributions and revisions of this paper. As abbreviations, we refer to Reviewer hQev as R1, Reviewer xmGd as R2, Reviewer aWhs as R3, and Reviewer hXZy as R4 respectively.

**Contributions**:

- We study score propagation in-depth, theoretically elucidating the conditions under which score propagation is effective. Multiple reviewers value the theoretical contribution of our paper: ```conducts an in-depth analysis``` (R1), ```theoretical analysis is helpful for future work in this direction, and for developing OOD detection methods for graphs``` (R2), ``` theoretical foundation is solid and extends the understanding of graph OOD detection``` (R3). 
- We propose a graph augmentation method aimed at increasing the ratio of intra-edges to enhance OOD detection performance without the need for training from scratch and without requiring knowledge of true OOD nodes. Multiple reviewer recognized the effectiveness  and practical values of our method, ```demonstrates superior performance``` (R1), ```results are convincing``` (R2), ```has achieves the SOTA performance``` (R3); ```the practical applicability is good``` (R2), ```the solution is practical and efficient``` (R3), ```experiments are comprehensive, the hyperparameter sensitivity analysis is thorough, providing readers with valuable insights``` (R4).
- Our paper is ```well motivated``` (R2), ```introduced in an informative manner``` (R4), ```well written``` (R2, R3), and ```easy to follow``` (R2, R3, R4).

**Responses and Revisions:**

- For Reviewer R1's concerns:
  - We clarify the relationship between GRASP and ID classification accuracy.
  - We discuss the extension of GRASP to subgraph-level and graph-level tasks.
  - We elucidate the applicability of Figure 2 in real-world datasets.
  - We investigate the impact of incorrectly added edges on the results.
- For Reviewer R2's concerns:
  - We explain the effectiveness and robustness of our method in using MSP.
  - We add error bars to the results.
- For Reviewer R3's concerns:
  - We release the source codes and pre-trained checkpoints for the reproducibility of our work.
  - We add error bars to the results.
  - We conduct additional experiments to analyze how GRASP's performance varies with different OOD distributions.
  - We provide further insights into the rationale behind GRASP and how it interprets the graph structure.
  - We analyze the relationship between GRASP and the graph size.
  - We explain the effect of random connectivity on GRASP.

- For Reviewer R4's concerns:
  - We provide a more detailed discussion of existing graph-OOD works and position our paper's contributions.
  - We add comparative experiments with two latest baselines.
  - We justify the use of the Bernoulli distribution to model edge weights.
  - We present a concrete and intuitive example to illustrate the motivation behind our approach.
  - We offer further explanation for the remarkable improvement of GRASP on FPR in reddit2.
  - We highlight the key factors in achieving optimal OOD detection performance.


Thanks again for your efforts in reviewing our work, and we hope our responses can address any concerns about this work.

Warm regards,

The Authors of Submission 12283.

Meta-review: This paper theoretically understands the propagation mechanism that leads to performance degradation in OOD detection on graph data and presents a simple yet effective post-hoc methodology called GRASP to address this issue. This approach focuses on increasing the intra-edge ratio, based on the observation and theoretical insight that OOD detection becomes more difficult as the inter-edge ratio between ID and OOD nodes increases. By dividing unlabeled nodes into ID and OOD sets based on maximum softmax probability, the method identifies a subset with a high connection ratio to the ID set from labeled nodes and links the nodes within this subset. Extensive experiments demonstrate the effectiveness of the proposed method.
The reviewers initially suggested the following strong points and concerns.

Strong points:
- The paper conducts an in-depth analysis and empirically validates the beneficial conditions for OOD score propagation in a graph.

- The key idea of the work for OOD detection is presented as a post hoc strategy, hence the practical applicability of the method is good.

- The study delves into the mechanisms of score propagation and derives conditions for its effectiveness. This theoretical foundation is solid and extends the understanding of graph OOD detection.

Concerns:

- Several issues such as overconfidence and poor generalization can cause degradation of GRASP performance.

- Standard error with statistical significance analysis should be provided.

- The baselines selected in the experiments may not be sufficiently novel.

The authors have adequately addressed the reviewers' concerns, but one concern remains.
The performance of the latest baseline, NODESafe [1], presented in the authors' rebuttal differs from the results reported in the original NODESafe paper by approximately 9 in AUROC and 39 in FPR. Similarly, the baseline GNNSafe [2] included in the main table shows a discrepancy of about 5 in AUROC and 24 in FPR compared to its original paper.
Although the settings are slightly different (e.g., in the Cora dataset, the paper used 3 classes as ID and 4 classes as OOD, while NODESafe used 4 classes as ID and 3 classes as OOD, with the same GCN backbone), the performance gap seems notable even considering this. It is unclear why such a significant performance difference has occurred.

[1] Yang, Shenzhi, et al. "Bounded and Uniform Energy-based Out-of-distribution Detection for Graphs." Forty-first International Conference on Machine Learning.

[2] Wu, Qitian, et al. "Energy-based Out-of-Distribution Detection for Graph Neural Networks." The Eleventh International Conference on Learning Representations.
Decision: Accept (poster)