Revisiting Score Propagation in Graph Out-of-Distribution Detection

Authors: longfei  ma
yiyou  sun
kaize  ding
zemin  liu
fei  wu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:48:18

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.

Main paper: 
 introduction: 
 Graph-like data structures are ubiquitous in many domains, such as social networks [87, 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: Out-of-Distribution (OOD) node detection. Imagine a recommender system suggesting irrelevant or even harmful products to users, or a bioinformatics algorithm misusing an unknown protein. This gives rise 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. To 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 ). Although this strategy has shown promising results on some datasets, 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 OOD score propagation always help graph OOD Detection?" The short answer is no. This method can be ineffective on graphs where inter-edges (ID-to-OOD) are predominant. 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, as shown in Figure 2 (b), score propagation would 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.Question 2: "How to derive a better score propagation strategy for graph OOD detection?" Building on our prior findings, we propose a 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 our contributions as below:• Theoretical understanding: We delve deeply into the mechanism of score propagation to understand its potential for graph OOD detection and elucidate the conditions under which it thrives, providing an understanding that extends beyond existing knowledge.• Practical solution: To counter the identified challenge of inter-edges' domination, we propose GRaph-Augmented Score Propagation (GRASP), an innovative edge augmentation strategy with theoretical guarantee. By strategically adding edges to a 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 of the proposed method on extensive graph OOD detection benchmarks, different pre-trained methodologies [34, 69, 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 are also provided to validate the effectiveness of the proposed approach and the correctness of the theoretical findings. 
preliminaries: 
 Problem setup. We consider a traditional semi-supervised node classification setting with the additional unlabeled nodes from the out-of-distribution 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 ∈ R N ×d . The structure of graph G is described by the adjacency matrix A ∈ {0, 1} N ×N . We let the corresponding row-stochastic matrices as Ā = D -1 A, where D is the diagonal matrix with D ii = j A ij . The N nodes are partially labeled, so we let V l and V u represent the labeled and unlabeled node sets respectively, i.e, V = V l ∪ V u . Given a training set D tr = (x i , y i ) i∈V l with x i as the i-th row of X and y i ∈ Y ≜ {1, • • • , C}, the goal of node classification is to learn a mapping f : V → R C from the nodes to the probability of each class. Two illustrative examples when scoring propagation is harmful/helpful. We consider ID nodes in green and OOD nodes in red. Inter-edges are defined to be ID-to-OOD edges and Intra-edges are ID-to-ID or OOD-to-OOD edges. The value represents the respective OOD scores. Consequently, the propagated scores in these cases will be the mean of the scores of adjacent nodes as shown in Figure 1 .Out-of-distribution detection. When deploying a model in the real world, a 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 u = V uid ∪ V uood where V uid and V uood represent the in-distribution (ID) node and OOD node respectively. The goal of the graph OOD detection is to derive an algorithm to decide if a node i ∈ V u is from V uood or V uid . 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 is to decide whether an unlabeled node i ∈ V u is from ID or OOD. The decision can be made via a level set estimation:F OODD (i, G; λ) = ID g(x i ) ≥ λ OOD g(x i ) < λ ,where nodes with higher scores g(x i ) are classified as ID and vice versa, and λ is the threshold commonly chosen so that a high fraction (e.g., 95%) of ID data is correctly classified.In this paper, we consider post hoc OOD detection methods to produce g(x i ) which does not require expensive re-training. As an example, a classical way to compute g(x i ) 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, we formally delineate the conditions under which OOD score propagation works. We start by showing the formal definition of propagation.Define OOD scoring propagation. Given a raw OOD scoring vector ĝ ∈ R N with ĝi = g(x i ), the propagated scoring vector is given by: Propagated OOD Scoring Vector:EQUATIONwhere k ∈ N + are hyperparameters.Is it necessarily the case that g outperforms ĝ?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-ID and OOD-to-OOD edges surpasses that of ID-to-OOD 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-OOD edges are more than the other types of edges, the scores for both ID and OOD nodes become undistinguishable post-propagation.The example above offers the insight that the relative performance of g compared to ĝ is contingent upon the structural dynamics of the network, specifically the distribution of edges. To formally articulate this relationship, we adopt a probabilistic framework for modeling edges. Specifically, we assume that the edge follows a Bernoulli distribution characterized by parameters η intra and η inter for intra-edges (ID-to-ID and OOD-to-OOD) and inter-edges (ID-to-OOD), respectively:A ij ∼ Ber(η intra ), if i, j ∈ V uid or i, j ∈ V uood Ber(η inter ), if i ∈ V uid , j ∈ V uood or j ∈ V uid , i ∈ V uoodIn the context of probabilistic modeling, the subsequent Theorem 3.1 can be established to formalize the inherent understanding.Theorem 3.1. (Informal) (a) When η intra ≫ η inter , it is highly likely that the propagation algorithm will yield enhanced performance in OOD detection. (b) When η intra ≈ η inter or even η intra < η inter , the score propagation is likely to be either ineffective or 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 test ID/OOD node set S id ⊂ V uid , S ood ⊂ V uood with equal size N s , let the ID-vs-OOD separability M sep defined on an OOD scoring vectorĝ ∈ R N as M sep (ĝ) ≜ E i∈S id ĝi -E j∈S ood ĝj .If M sep (ĝ) > 0 and η intraη inter > 1/N s , for some ϵ > 0 and constant c, we haveP M sep (Aĝ) ≥ M sep (ĝ) -ϵ ≥ 1 -exp(-cϵ 2 ∥ĝ∥ 2 2).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 the critical factor in enhancing post-propagation performance lies in improving the ratio of intra-edges within the graph structure. These insights serve as a direct motivation for the augmentation strategy in the next section. 
an augmented score propagation strategy: 
 The findings from the preceding section give rise to a subsequent thought: "Can we improve the propagation strategy for graph OOD detection performance?" In an ideal scenario, if an oracle were to indicate that a particular subset in the test set belongs exclusively to the ID or OOD, one could augment the graph by adding intra-edges or removing inter-edges. This would consequently improve the ratio of intra-edges η intra , leading to enhanced OOD detection performance post-propagation.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, 55] . 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 a subset of the training set V l , which is assured to be in-distribution data. We start by showing the theoretical underpinnings that adding such a subset can, under specified conditions, contribute to improved OOD detection performance after propagation.Our approach involves adding the edges to a subset G of training data and then propagating the out-of-distribution (OOD) scoring vector using the enhanced adjacency matrix. Specifically, when edges are added to G, this action can be mathematically represented as incorporating a perturbation matrix E = e G e ⊤ G into A, as demonstrated in Figure 3 . Here, e S ∈ R N denotes an indicator vector for a set S ⊂ V, where the vector takes the value of 1 if the index i ∈ S and value 0 otherwise. A sufficient condition for the efficacy of this augmentation strategy in enhancing post-propagation OOD detection performance is outlined in Theorem 4.1. < l a t e x i t s h a 1 _ b a s e 6 4 = " h Q c X F a 7 Y h H j s P D 8 C l o 9 a X L 3 D k T 8 = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l E 1 G P R i y e p a D + g D W W z 3 b R L N 5 u w O y m U 0 J / g x Y M i X v 1 F 3 v w 3 b t s c t P p g 4 P H e D D P z g k Q K g 6 7 7 5 R R W V t f W N 4 q b p a 3 t n d 2 9 8 v 5 B 0 8 S p Z r z B Y h n r d k A N l 0 L x B g q U v J 1 o T q N A 8 l Y w u p n 5 r T H X R s T q E S c J 9 y M 6 U C I U j K K V H s a 9 u 1 6 5 4 l b d O c h f 4 u W k A j n q v f J n t 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 can positively influence the propagation algorithm's ability to enhance OOD detection. For the sake of the main intuition, we provide the analysis on A instead of Ā for simplicity. We provide the detailed proof in Appendix A.+ g f H j U 1 H G q G D Z Y L G L V D q h G w S U 2 D D c C 2 4 l C G g U C W 8 H o b u a 3 x q g 0 j + W T m S T o R 3 Q g e c g Z N V Z 6 H P e 8 X r n i V t 0 5 y C r x c l K B H P V e + a v b j 1 k a o T R M U K 0 7 n p s Y P 6 P K c C Z w W u q m G h P K R n S A H U s l j V D 7 2 f z U K T m z S p + E s b I l D Z m r v y c y G m k 9 i Q L b G V E z 1 M v e T P z P 6 6 Q m v P E z L p P U o G S L R W E q i I n J 7 G / S 5 w q Z E R N L K F P c 3 k r Y k C r K j E 2 n Z E P w l l 9 e J c 2 L q n d V 9 R 4 u K 7 X b P I 4 i n M A p n I M H 1 1 C D e 6 h D A x g M 4 B l e 4 c 0 R z o v z 7 n w s W g t O P n M M f + B 8 / g A K n I 2 k < / l a t e x i t > v 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " Q p D M v q M u P U 7 5 G X z Q 0 x Q D G k N s Y n I = " > A A A B 6 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k R 9 V j 0 4 r G i / Y A 2 l M 1 2 0 i 7 d b M L u p l B C f 4 I X D 4 p 4 9 R d 5 8 9 + 4 b X P Q 1 g c D j / d m m J k X J I J r 4 7 r f z t r 6 x u b W d m G n u L u 3 f 3 B Y O j p u 6 j h V D B s s F r F q B 1 S j 4 B I b h h u B 7 U Q h j Q K B r W B 0 N / N b Y 1 S a x / L J T B L 0 I z q Q P O S M G i s 9 j n v V X q n s V t w 5 y C r x c l K G H P V e 6 a v b j 1 k a o T R M U K 0 7 n p s Y P 6 P K c C Z w W u y m G h P K R n S A H U s l j V D 7 2 f z U K T m 3 S p + E s b I l D Z m r v y c y G m k 9 i Q L b G V E z 1 M v e T P z P 6 6 Q m v P E z L p P U o G S L R W E q i I n J 7 G / S 5 w q Z E R N L K F P c 3 k r Y k C r K j EI J / Q l e P C j i 1 V / k z X / j t s 1 B q w 8 G H u / N M D M v S K Q w 6 L p f T m F l d W 1 9 o 7 h Z 2 t r e 2 d 0 r 7 x 8 0 T Z x q x h s s l r F u B 9 R w K R R v o E D J 2 4 n m N A o k b w W j 2 5 n f G n N t R K w e c Z J w P 6 I D J U L B K F r p Y d w 7 7 5 U r b t W d g / w l X k 4 q k K P e K 3 9 2 + z F L I 6 6 Q S W p M x 3 M T 9 D O q U T D J p 6 V u a n h C 2 Y g O e M d S R S N u / G x + 6 p S c W K V P w l j b U k j m 6 s + J j E b G T K L A d k Y U h 2 b Z m 4 n / e Z 0 U w 2 s / E y p J k S u 2 W B S m k m B M Z n + T v t C c o Z x Y Q p k W 9 l b C h l R T h j a d k g 3 B W 3 7 5 L 2 m e V b 3 L q n d / U a n d 5 H E U 4 Q i O 4 R Q 8 u I I a 3 E E d G s B g A E / w A q + O d J 6 d N + d 9 0 V p w 8 p l D + A X n 4 x s N p I 2 m < / l a t e x i t > v 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " h Q c X F a 7 Y h H j s P D 8 C l o 9 a X L 3 D k T 8 = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l E 1 G P R i y e p a D + g D W W z 3 b R L N 5 u w O y m U 0 J / g x Y M i X v 1 F 3 v w 3 b t s c t P p g 4 P H e D D P z g k Q K g 6 7 7 5 R R W V t f W N 4 q b p a 3 t n d 2 9 8 v 5 B 0 8 S p Z r z B Y h n r d k A N l 0 L x B g q U v J 1 o T q N A 8 l Y w u p n 5 r T H X R s T q E S c J 9 y M 6 U C I U j K K V H s a 9 u 1 6 5 4 l b d O c h f 4 u W k A j n q v f J n t x + z N O I K m a T G d D w 3 Q T + j G g W T f F r q p o Y n l I 3 o g H c s V T T i x s / m p 0 7 J i V X 6 J I y 1 L Y V k r v 6 c y G h k z C Q K b G d E c W i W v Z n 4 n 9 d J M b z y M 6 G S F L l i i 0 V h K g n G Z P Y 3 6 Q v N G c q J J Z R p Y W 8 l b E g 1 Z W j T K d k Q v O W X / 5 L m W d W 7 q H r 3 5 5 X a d R 5 H E Y 7 g G E 7 B g 0 u o w S 3 U o Q E M B v A E L / D q S O f Zx + z N O I K m a T G d D w 3 Q T + j G g W T f F r q p o Y n l I 3 o g H c s V T T i x s / m p 0 7 J i V X 6 J I y 1 L Y V k r v 6 c y G h k z C Q K b G d E c W i W v Z n 4 n 9 d J M b z y M 6 G S F L l i i 0 V h K g n G Z P Y 3 6 Q v N G c q J J Z R p Y W 8 l b E g 1 Z W j T K d k Q v O W X / 5 L m W d W 7 q H r 3 5 5 X a d R 5 H E Y 7 g G E 7 B g 0 u o w S 3 U o Q E M B v A E L / D q S O f ZC V K F A y z O / n E F M 0 p B G i n A s Z d + 2 E u X m W C h G O J 1 W n F T S B J M x H t K + p h E O q X T z + e V T d K a V A Q p i o S t S a K 7 + n s h x K O U k 9 H V n i N V I L n s z 8 T + v n 6 r g 2 s 1 Z l K S K R m S x K E g 5 U j G a x Y A G T F C i + E Q T T Ak i 0 W h a k g J i a z r 0 m f K 2 R G j C 2 h T H F 7 K 2 F D q i g z N p u C D c F b f n m V N C / K 3 m W 5 U q + U q j d ZTheorem 4.2. (Formal) For any two test ID/OOD node set S id ⊂ V uid , S ood ⊂ V uood with size N s , let the ID-vs-OOD separability M sep defined on a non-negative OOD scoring vectorĝ ∈ R N as M sep (ĝ) ≜ E i∈S id ĝi -E j∈S ood ĝj .Let E S↔S ′ ⊂ E to denote the edge set of edges between two node sets S and S ′ , whereS, S ′ ⊂ V. If we can find a node set G ⊂ V l such that |E G↔S id | > |E G↔S ood |, we have M sep ((A + δE) 2 ĝ) > M sep (A 2 ĝ),where E = e G e ⊤ G and δ > 0.The Theorem 4.2 shows a critical principle for enhancing propagation: the optimal strategy entails the addition of edges to the subset G such that there are more edges to ID data than OOD data. For some S id , S ood in the test set, the goal is to find the setEQUATIONwhere N g is a hyperparameter to control the size of G * . Inspired by the optimization target, we proceed to present our pragmatic algorithmic approach.Our augmentation approach hinges on the selection of a subset, G, from the training set, as exemplified in Equation 2. Two principal challenges arise in 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 to find a subset is 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 S id /S ood . Our discussion begins by detailing the methodology to select the subset from the test ID/OOD dataset, symbolized by S id and S ood in Equation 2. A straightforward approach to obtain the most likely ID is 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 a representation of confidence. The selected sets can be defined as:EQUATIONwhere λ α denotes the α-th percentile of the MSP scores corresponding to nodes in V u . To offer a clear view, Figure 4 portrays S id and S ood in the marginal regions highlighted in orange. Selecting a OOD ID < l a t e x i t s h a 1 _ b a s e 6 4 = "+ I a J e k v K B F c Z 7 j l N A C 0 D E e 1 7 R h 8 = " > A A A B + 3 i c b V D L S s N A F J 3 U V 6 2 v W J d u B o v g x p J I U Z d F N y 4 r 2 A c 0 I d x M J u 3 Q y Y O Z i V h C f s W N C 0 X c + i P u / B u n b R b a e m D g c M 6 5 3 D v H T z m T y r K + j c r a + s b m V n W 7 t r O 7 t 3 9 g H t Z 7 M s k E o V 2 S 8 E Q M f J C U s 5 h 2 F V O c D l J B I f I 5 7 f u T 2 5 n f f 6 R C s i R + U N O U u h G M Y h Y y A k p L n l l 3 u A 4 H 4 O X 2 u Q M 8 H U P h m Q 2 r a c 2 B V 4 l d k g Y q 0 f H M L y d I S B b R W B E O U g 5 t K 1 V u D k I x w m l R c z J J U y A T G N G h p j F E V L r 5 / P Y C n 2 o l w G E i 9 I s V n q u / J 3 K I p J x G v k 5 G o M Z y 2 Z u J / 3 n D T I X X b s 7 i N F M 0 J o t F Y c a x S v C s C B w w Q Y n i U 0 2 A C K Z v x W Q M A o j S d d V 0 C f b y l 1 d J 7 6 J p X z Z b 9 6 1 G + 6 a s o 4 q O 0 Q k 6 Q z a 6 Q m 1 0 h z q o i w h 6 Q s / o F b 0 Z h f F i v B s f i 2 j F K G e O 0 B 8 Y n z + z A J Q 8 < / l a t e x i t > 1 ↵ < l a t e x i t s h a 1 _ b a s e 6 4 = " x i o N o t 9 B s E v J v D + D q 0 2 Y C t k K o 0 M = " > A A A B + X i c b V D L S s N A F J 3 U V 6 2 v q E s 3 g 0 V w V R I p 6 r L o x m U F + 4 A m h J v J p B 0 6 m Y S Z S a G E / o k b F 4 q 4 9 U / c + T d O 2 y y 0 9 c D A 4 Z x z u X d O m H G m t O N 8 W 5 W N z a 3 t n e p u b W / / 4 P D I P j 7 p q j S X h H Z I y l P Z D 0 F R z g T t a K Y 5 7 W e S Q h J y 2 g v H 9 3 O / N 6 F S s V Q 8 6 W l G / Q S G g s W M g D Z S Y N s e N + E I g s I D n o 1 g F t h 1 p + E s g N e J W 5 I 6 K t E O 7 C 8 v S k m e U K E J B 6 U G r p N p v w C p G e F 0 V v N y R T M g Y x j S g a E C E q r 8 Y n H 5 D F 8 Y J c J x K s 0 T G i / U 3 x M F J E p N k 9 A k E 9 A j t e r N x f + 8 Q a 7 j W 7 9 g I s s 1 F W S 5 K M 4 5 1 i m e 1 4 A j J i n R f G o I E M n M r Z i M Q A L R p q y a K c F d / f I 6 6 V 4 1 3 O t G 8 7 F Z b 9 2 V d V T R G T p H l 8 h F N 6 i F H l A b d R B B E / S M X t G b V V g v 1 r v 1 s Y x W r H L m F P 2 B 9 f k D 0 E S T y g = = < / l a t e x i t > ↵ < l a t e x i t s h a 1 _ b a s e 6 4 = " I i l A w / j 9 / u Y A q y v r V B p k 0 o W O E V k = " > A A A B 7 X i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R b B U 9 m V U j 0 W v X i s a D + g X U o 2 m 2 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Q c K Z N q 7 7 7 R T W 1 j c 2 t 4 r b p Z 3 d v f 2 D 8 u F R W 8 t U E d o i k k v V D b C m n A n a M s x w 2 k 0 U x X H A a S c Y 3 8 z 8 z h N V m k n x Y C Y J 9 W M 8 F C x i B B s r t e 8 H G Q u n g 3 L F r b p z o F X i 5 a Q C O Z q D 8 l c / l C S N q T C E Y 6 1 7 n p s Y P 8 P K M M L p t N R P N U 0 w G e M h 7 V k q c E y 1 n 8 2 v n a I z q 4 Q o k s q W M G i u / p 7 I c K z 1 J A 5 s Z 4 z N S C 9 7 M / E / r 5 e a 6 M r P m E h S Q w V Z L I p S j o x E s 9 d R y B Q l h k 8 s w U Q x e y s i I 6 w w M T a g k g 3 B W 3 5 5 l b Q v q l 6 9 W r u r V R r X e R x F O I F T O A c P L q E B t 9 C E F h B 4 h G d 4 h T d H O i / O u / O x a C 0 4 + c w x / I H z + Q O u K Y 8 2 < / l a t e x i t > S id< l a t e x i t s h a 1 _ b a s e 6 4 = " e 9 8 E + q t / 7 R l q 9 p s / Selection of G. Upon establishing S id and S ood , the next step is to determine G using Equation 2.C S N v r D v W J l E = " > A A A B 7 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m k q M e i F 4 8 V 7 Q e 0 o W w 2 m 3 b p Z j f s b o Q S + i O 8 e F D E q 7 / H m / / G b Z q D t j 4 Y e L w 3 w 8 y 8 I O F M G 9 f 9 d k p r 6 x u b W + X t y s 7 u 3 v 5 B 9 f C o o 2 W q C G 0 T y a X q B V h T z g R t G 2 Y 4 7 S W K 4 j j g t B t M b u d + 9 4 k q z a R 4 N N O E + j E e C R Y x g o 2 V u g / D T M p w N q z W 3 L q b A 6 0 S r y A 1 K N A a V r 8 G o S R p T I U h H G v d 9 9 z E + B l W h h F O Z 5 V B q m m C y Q S P a N 9 S g W O q / S w / d 4 b O r B K i S C p b w q B c / T 2 R 4 V j r a R z Y z h i b s V 7 2 5 u J / X j 8 1 0 b W f M Z G k h g q y W B S l H B m J 5 r + j k C l K D J 9 a g o l i 9 l Z E x l h h Y m x C F R u C t / z y K u l c 1 L 3 L e u O + U W v e F H G U 4 Q R O 4 RK S i 1 v k H L U z P 2 z d W H B 6 5 I P I Y 0 M = " > A A A B 9 H i c b V D L S g M x F L 1 T X 7 W + q i 7 d B I v g q s y I q M u i G 5 c V 7 A P a o d x J 0 z Y 0 k x m T T K E M / Q 4 3 L h R x 6 8 e 4 8 2 / M t L P Q 1 g O B w z n 3 c k 9 O E A u u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 1 F G i K G v Q S E S q H a B m g k v W M N w I 1 o 4 V w z A Q r B W M 7 z K / N W F K 8 0 g + m m n M / B C H k g 8 4 R W M l v x u i G V E U a X P W S 3 r l i l t 1 5 y C r x M t J B X L U e + W v b j + i S c i k o Q K 1 7 n h u b P w U l e F U s F m p m 2 g W I x 3 j k H U s l R g y 7 a f z 0 D N y Z p U + G U T K P m n I X P 2 9 k W K o 9 T Q M 7 G Q W U i 9 7 m f i f 1 0 n M 4 M Z P u Y w T w y R d H B o k g p i I Z A 2 Q P l e M G j G 1 B K n i N i u h I 1 R I j e 2 p Z E v w l r + 8 S p o X V e + q e v l w W a n d 5 n U U 4 Q R O 4 R w 8 u I Y a 3 E M d G k D h C Z 7 h F d 6 c i f P i v D s f i 9 G C k + 8 c w x 8 4 n z 8 n 7 J J d < / l a t e x i t > V uDirectly enumerating every possible G is impractical. Instead, we adopt a greedy approach, prioritizing the node with the highest "likelihood" score. To elucidate, for each node i ∈ V l , the score can be computed as the ratio of the edge count to S id over S ood :EQUATIONwhere we incorporate an addition of 1 in the denominator to circumvent division by zero. Subsequently, G can be expressed as:EQUATIONwhere τ β stands for the β-th percentile of h(i) scores for nodes in V l . Once G is defined, edge augmentation can be executed as demonstrated in Section 4.1. The OOD score is then propagated with the new adjacency matrixA + = A + e G e ⊤G in place:EQUATIONwhere k ∈ 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 in terms of runtime and memory usage with O(N + 2k|E| + n) and O(N + |E| + 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. Remark on homophily/heterophily. In Table 1 , datasets are also categorized based on the attribute of 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 a challenge for node classification but also for graph OOD detection. The underlying reason is 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. 
experiments: 
 Implementation Details. Our graph OOD detection technique operates in a post hoc fashion utilizing a 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 a layer depth of 2. With the pre-trained network, we proceed to execute the graph OOD detection. By default, we report the performance of the augmented propagation (GRASP) on the MSP score [23] . The compatibility with other OOD scoring functions is also shown in Table 6 . We set the propagation number k as 8, with percentile values α = 5 and β = 50. The sensitivity analysis of the hyperparameters is included in Appendix D.4.Metrics. Following the convention in literature [23, 47, 65] , we use AUROC and FPR95 as evaluation metrics for OOD detection.GRASP consistently achieves superior performance. We provide results of 5 common small-scale benchmarks and 5 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 Out-of-Distribution (OOD) detection techniques in existing literature and training-based methods tailored for graph OOD detection. We categorize the baseline methods into two groups: (a) Traditional OOD detection methods including MSP [23] , Energy [47] , ODIN [43] , Mahalanobis [37] , and KNN [67] ; (b) Graph OOD detection methods including GKDE [92] , GPN [64] , OODGAT [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 on common and large-scale benchmarks, respectively. This outcome is anticipated given their lack of specificity in design towards graph data. (b) GRASP outperforms existing baselines by a 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.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 a 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-based baselines. In addition to contrasting with post hoc methods, we extend our comparison to a parallel line of graph Out-Of-Distribution (OOD) detection research, which focuses on refining the training strategy to improve graph OOD detection performance. The compared methods include GKDE [92] , GPN [64] and OODGAT [63] . While these approaches necessitate a 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 on challenging heterophily datasets. As indicated in Table and 3, GNNSafe, which performs well on homophily datasets, experiences significant degradation on the difficult heterophily benchmarks due to its naïve propagation mechanism. In contrast, GRASP maintains optimal performance on these hard scenarios. 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 h(i), 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) selecting 50% of training nodes with the lowest h(i) values (left side of Figure 5 ), (2) randomly selecting 50% of training nodes, corresponding to randomly picking node indices from the x-axis of Figure 5 , (3) directly adding edges to S id and S ood within the test set (i.e., TestAug), and (4) a 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:Q Z r H g Z B k q f / Q Q V B a B J U = " > A A A B H i c b V B N S N A E J U r q / q h L B b B U m k q M e i F t F p o Q l s J + a z S b s b o Q S + g u e F D E q z / J m / / G b Z u D t j Y e L w w y I B F c G f d g p r x u b W X t s u v B + f C o r e N U M W y x W M S q E C N g k t s G W E d h K F N A o E P g T j n / I R K j e m m C f k S H k o e c U W O l J u + X K V n Y O s E i n F c j R J e / e o O Y p R F K w w T V u u u i f E z q g x n A q e l X q o x o W x M h i V N I I t Z / N D S M s M S B g r W K Q u f p I q O R p M o s J R N S O M E / x u a s J r P + M y S Q K t l g U p o K Y m M y + J g O u k B k x s Y Q y x e t h I o o s z Y b E o B G / V X S v q h l V a s a p + R x F O E E T u E c P L i C O t x B A r A A O E Z X u H N e X R(a) Selection by h(i) is effective. For example, our strategy using the top 50% scores of h(i) outperforms that uses random 50%, which, in turn, outperforms the low 50% way. This is because a higher score of h(i) implies higher edge count towards ID data than to OOD data, which can increase the ratios of intra-edges and improve OOD detection performance after propagation. In contrast, the alternative augmentation method GAug, which does not consider the score h(i) at all, performs even worse than the Low 50% policy.(b) Directly adding edges to S id and S ood 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 to OOD detection performance. GRASP can effectively boost performance of challenging nodes connected by inter-edges. As stated in the introduction 1, the reason OOD score propagation does not always work is 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, we 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 on MSP (MSP+prop), and our proposed augmentation propagation (MSP+GRASP) respectively. From the results we can see that naive propagation performs well only on strong homophily datasets, while on strong heterophily datasets (datasets highlighted in bold in the table), its performance is even worse than without propagation, as expected. In 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. In 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. Remark on other empirical findings. We include other empirical findings in Appendix. Specifically, in Table 14 , we prove that GRASP also achieves superior performance on the other GNN architectures in the literature. In Figure 7 , we demonstrate a strong positive correlation between ratios of intraedges 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 of 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, 21] , and (2) featurebased 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.Out-of-distribution 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 to perform OOD detection. Given the merits of post hoc methods, our study first provides a comprehensive understanding of the OOD score propagation in Graphs, extending beyond existing knowledge.Graph Data Augmentation. Graph Data Augmentation is a 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 situations where the ratio of intra-edges surpasses that of inter-edges. Motivated by this finding, our edge augmentation strategy selectively adds edges to a 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: Appendix D.6Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal 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., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied 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.• 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a best faith effort.12. Licenses for existing assets Question: 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?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: https://github.com/longfei-ma/GRASP Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of 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 is used. • 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. 
 
 Appendix: Theorem A.1. (Recap of Theorem 3.2) For any two test ID/OOD node set S id ⊂ V uid , S ood ⊂ V uood with equal size N s , let the ID-vs-OOD separability M sep defined on a OOD scoring vector ĝ ∈ R N as M sep (ĝ) ≜ E i∈S id ĝi -E j∈S ood ĝj .If M sep (ĝ) > 0 and η intraη inter > 1/N s , for some ϵ > 0 and constant c, we haveP M sep (Aĝ) ≥ M sep (ĝ) -ϵ ≥ 1 -exp(- cϵ 2 ∥ĝ∥ 2 2).Proof. Without losing the generality, we set the ĝi = 0, if i ∈ S ood ∪ S id , since we only care about the detection results in the given test node set S ood and S id .The M sep (ĝ) can be re-written as M sep (ĝ) = ĝ⊤ (e S ide S ood ).Then we haveM sep (Aĝ) = ĝ⊤ A(e S id -e S ood )According to General Hoeffding's inequality (Theorem 2.6.3) in [70] , we know thatP E[ĝ ⊤ A(e S id -e S ood )] -ĝ⊤ A(e S id -e S ood ) ≤ ϵ ≥ 1 -exp(- cϵ 2 ∥ĝ∥ 2 2 ),where c is some constant value. Since ĝi = 0, if i ∈ V l , E[ĝ ⊤ A(M sep ((A + δE) 2 ĝ) > M sep (A 2 ĝ),where E = e G e ⊤ G and δ > 0.Proof. The M sep (ĝ) can be re-written asM sep (ĝ) = 1 N s ĝ⊤ (e S id -e S ood ).We can then directly derive the proof by expandingM sep ((A + δE) 2 ĝ) -M sep (A 2 ĝ) = 1 N s (e S id -e S ood ) ⊤ (A + δE) 2 ĝ -A 2 ĝ = 1 N s (e S id -e S ood ) ⊤ δ(AE + EA)ĝ + δ 2 e G e ⊤ G e G e ⊤ G ĝ = δ N s (e S id -e S ood ) ⊤ Ae G e ⊤ G ĝ + e G e ⊤ G Aĝ = δ N s (e S id -e S ood ) ⊤ Ae G e ⊤ G ĝ = δ N s (e ⊤ G ĝ)(e ⊤ S id Ae G -e ⊤ S ood Ae G ) = δ(e ⊤ G ĝ) |G|N s (|E G↔S id | -|E G↔S ood |)> 0, where the second and the third equation are derived by the fact that G ⊂ V l and then we have e ⊤S id e G = 0 and e ⊤ S ood e G = 0.For the reader's convenience, we summarize in detail a few common techniques for defining OOD scores that measure the degree of ID-ness on a given input. By convention, a higher (lower) score is indicative of being in-distribution (out-of-distribution).MSP [23] This method proposes to use the maximum softmax score as the OOD score. For each node i, we useF OODD (i) = max c∈[C] f c (i) as the OOD score.ODIN [43] This method improves OOD detection with temperature scaling and input perturbation.In all experiments, we 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 we set ϵ = 0.Mahalanobis [37] This method uses multivariate Gaussian distributions to model class-conditional distributions of softmax neural classifiers and uses Mahalanobis distance-based scores for OOD detection. The mean µ c of each multivariate Gaussian distribution with class c and a tied covariance Σ are estimated based on training samples. We define the confidence score M (x) using the Mahalanobis distance between test sample x 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 a scalar E(x i ; 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) is higher (lower) for ID (OOD) data.KNN [67] This method uses the k-th nearest neighbor distance between a test graph node and the training set as the OOD score. We use k = 10 for all experiments in this paper.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-Photo, Coauthor-CS, Reddit2 and ogbn-products, we use the data loader provided by the Pytorch Geometric package 3 . 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 a citation relationship, and the label class is each paper's topic, which is the goal to predict.Amazon-Photo [52] is an 8-class item co-purchasing network on Amazon, which contains 7,650 nodes, 238,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 a 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 if co-authored a paper. And the label represents the study field for the authors.Reddit2 [88] is 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] is 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 are used for target labels.Chameleon 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] is 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 a 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 so that class ratios are approximately balanced [44] .snap-patents [39, 38] is a big dataset of utility patents in the US. Each node represents a 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 is 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 7 . 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 2 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 9 respectively. In addition, we present the ID ACC results of three training-based methods on the ten benchmarks. It is important to note that these training-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 . GRASP can seamlessly be applied to various GNN backbones. In this section, we report the OOD detection performance of all baselines on various popular architectures in Table 14 We show the sensitivity of hyper-parameters α, β and k in Figure 6 . The vertical axis in the figure represents the average AUROC values across common datasets. The performance comparison in the bar plot for each hyper-parameter is reported by fixing other hyper-parameters. We see that within the range of chosen hyperparameter values, our proposed method's performance does not vary significantly, which constantly outperforms baselines by a large margin. As shown in Figure 7 , the ratio of 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 we can see that after using our proposed augmentation, the ratio of intra-edges increases and in turn boosts the OOD detection performance. 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, we adeptly transform the complex and time-consuming structural computations into simple matrix-vector multiplication operations, making original expensive operation tractable and leading to efficient linear complexity. Below, we provide the support from both mathmatical and empirical points.$852& $852& k $852&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, I id and I ood , both with a length of nodes number N , to represent the number of connections each node has with S id and S ood , respectively. The initial values of I id are set to 1 at the indices corresponding to S id and 0 at the remaining indices (corresponding to S ood ). The initial value of I id is denoted asI (0)id . Similarly, I ood has a initial value of 1 at all indices corresponding to S ood and 0 at the indices corresponding to S id . We also represent the initial value of I ood as I (0) ood . After propagation for k times, the connections between each node with S id are:I (k) id = A k I (0) id = A k-1 • AI (0) id = A k-1 • I (1) id = (run k -1 times ...)In the above equation, AI 6in the main paper, given a raw OOD scoring vector ĝ ∈ R N , the propagated scoring vector using augmentated adjacency matrix after propagation for k times is given by:g GRASP = ( Ā+ ) k ĝ = (D -1 + A + ) k ĝ = (D -1 + A + ) k-1 • (D -1 + (A + E))ĝ = (D -1 + A + ) k-1 • (D -1 + Aĝ + D -1 + E ĝ ) = (run k -1 times ...)In the above equation,• E ĝ can be computed with time/space complexity O(n) by a simple summation operation (g i in Gwill be replaced by i∈G g i ) to get rid of the matrix multiplication.• Aĝ can be computed in O(|E|) with sparse matrix multiplication. Integrating the above two considerations, the time complexity of our algorithm after propagation for k times is O(N + 2k|E| + n), while the space complexity is O(N + |E| + n). Notably, the utilization of space reuse results in a linear space complexity.Empirical results. Then we 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 our algorithm is highly efficient across all datasets.Based on the experimental results in Table 16 and Table 17 , we have: 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 on these large-scale datasets underscores the strong practicality of our approach. 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) [1] , and Generalized PageRank (GPR) [10] . The emperical observations are as follows:• From the analysis of the hyper-parameter (order of propagation) and its impact on the AUROC in Figure 6 , we find that OOD detection performance benefits from propagation orders within a 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. While the proposed method of OOD score propagation shows promise in improving OOD detection in graph learning, there are limitations worth noting. The effectiveness of the method heavily relies on the connectivity and structure of the graph. In scenarios where the graph exhibits random connectivity patterns, the propagation of OOD scores with the proposed solution may no longer be effective. Addressing these limitations will be crucial for ensuring the robustness and generalizability of the proposed OOD detection approach in graph learning.This paper on detecting Out-of-Distribution (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 a promising avenue for enhancing the robustness and reliability of graph-based machine learning systems. The implications extend beyond the realm of graph learning, as OOD detection is a critical component in many realworld 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-based machine learning and contribute to the development of more robust and reliable AI systems with broader societal impact.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 to learn the invariant aspects behind ID and OOD. By enhancing these invariant points, the gap between ID and OOD data is reduced to 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 a 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 to learn stable associations, raising the graph OOD generalization capability. [78] boosts generalization 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.• 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.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 (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).https://pytorch-geometric.readthedocs.io/en/latest/modules/datasets.html 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?  

W2. 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.
questions: questions: Q1. Is the classification accuracy in Appendix D.1 assessed before or after employing GRASP? Is there a comparison between the two?  

Q2. Do similar cases discussed in Figure 2 exist within real-world datasets?  

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?
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 


2. 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.
questions: 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: limitations: The authors mention the limitations of their work in Appendix section E and societal impact in Appendix Section F.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1) it is strongly suggested to release the source code of experiments.

2) 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.
questions: questions: 1. How does the performance of GRASP vary with different OOD distributions (e.g., uniform, normal, outliers)?

2. Can the authors provide further insights into how GRASP works and how it interprets the graph structure?

3. How does the performance of GRASP scale with the size of the graph and the number of nodes? Is there any systemic analysis?
limitations: 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..
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. The baselines selected in the experiments may not be sufficiently novel. This makes the experimental results are not convincing enough.
3. 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?
questions: 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?
2. Does the assumption that edges follow a Bernoulli distribution receive support in most real-world datasets, practical applications, or previous studies?
3. 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?
4. Is there any underlying pattern in the ratio of intra-edges to inter-edges when achieving the best OOD detection performance across different datasets?
5. 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: limitations: The authors have discussed the limitations of the proposed method in the Appendix.

Comments: title: Response to Reviewer's Concerns - Part 3
Response to Reviewer's Concerns - Part 2
Response to Reviewer's Concerns - Part 1
Thanks for your reply
Appreciate Your Feedback
Response to authors' rebuttal
Appreciate Your Feedback
Thanks for the detailed responses
Part 3 of the rebuttal
Part 2 of the rebuttal
Part 2 of the rebuttal (Table with error bar)
Part 2 of the rebuttal
comment: |  | Datasets | cora   |        | amazon |        | coauthor |        | chameleon |        | squirrel |        |
|----------|-------------|--------|--------|--------|--------|----------|--------|-----------|--------|----------|--------|
| Backbone |  Method     | FPR95  | AUROC  | FPR95  | AUROC  | FPR95    | AUROC  | FPR95     | AUROC  | FPR95    | AUROC  |
| H2GCN    | MSP         | 67.00  | 86.50  | 59.23  | 86.88  | 99.37    | 40.35  | 91.00     | 62.79  | 94.34    | 57.21  |
|          | Energy      | 68.06  | 86.84  | 57.05  | 86.21  | 97.85    | 51.65  | 92.66     | 63.24  | 96.75    | 53.18  |
|          | KNN         | 80.00  | 79.68  | 63.85  | 80.54  | 60.66    | 77.25  | 95.13     | 56.89  | 95.62    | 57.45  |
|          | ODIN        | 65.21  | 87.10  | 56.25  | 86.97  | 99.43    | 41.58  | 91.07     | 63.52  | 95.08    | 55.69  |
|          | Mahalanobis | 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.23  | 100.00    | 50.35  | 100.00   | 36.26  |
|          | **GRASP** | **33.54** | **92.63** | **16.57** | **96.48** | **14.23** | **96.08** | **66.38** | **74.72** | **86.04** | **60.83**  |
| MixHop   | MSP         | 83.94  | 78.60  | 53.56  | 90.97  | 48.66    | 90.91  | 92.95     | 56.77  | 95.60    | 49.07  |
|          | Energy      | 83.67  | 77.15  | 57.04  | 89.28  | 28.49    | 94.67  | 94.10     | 57.21  | 95.61    | 48.87  |
|          | KNN         | 93.36  | 69.93  | 65.41  | 86.45  | 62.40    | 85.91  | 89.52     | 57.64  | 93.44    | 54.00  |
|          | ODIN        | 83.14  | 79.10  | 50.00  | 91.25  | 41.39    | 92.65  | 93.45     | 56.48  | 95.68    | 47.58  |
|          | Mahalanobis | 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  | 39.72  | 93.54  | 33.83    | 92.46  | 100.00    | 50.35  | 100.00   | 36.42  |
|          | **GRASP** | **32.11** | **92.77** | **10.07** | **96.99** | **9.41** | **97.31** | **76.92** | **66.12** | **85.92** | **60.69**  |
| GPR-GNN   | MSP         | 64.90  | 87.44  | 62.84  | 87.66  | 23.96    | 95.64  | 96.09     | 47.65  | 95.78    | 44.62  |
|          | Energy      | 72.85  | 83.86  | 64.23  | 85.28  | 16.42    | 96.50  | 93.78     | 49.09  | 95.16    | 42.63  |
|          | KNN         | 74.24  | 81.46  | 48.47  | 90.48  | 38.83    | 92.31  | 94.39     | 55.31  | 94.18    | 51.74  |
|          | ODIN        | 62.58  | 88.13  | 55.49  | 88.41  | 17.24    | 96.51  | 96.16     | 47.50  | 95.51    | 42.32  |
|          | Mahalanobis | 79.56  | 84.53  | 97.25  | 69.75  | 49.93    | 91.56  | 87.01     | 55.95  | 87.24    | 61.10  |
|          | GNNSafe     | 51.65  | 85.91  | 13.63  | 96.46  | 14.73    | 95.96  | 100.00    | 50.32  | 100.00   | 36.25  |
|          | **GRASP** | **26.71** | **94.02** | **5.30** | **97.14** | **8.28** | **97.70** | **76.53** | **72.43** | **85.40** | **61.33**  |
| GCNII    | MSP         | 72.85  | 83.02  | 51.72  | 88.13  | 23.18    | 95.21  | 96.03     | 55.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  | 59.25  | 86.74  | 36.05    | 93.43  | 94.72     | 52.86  | 94.65    | 53.47  |
|          | ODIN        | 71.49  | 83.31  | 49.44  | 88.35  | 19.44    | 95.75  | 95.61     | 56.63  | 94.73    | 48.34  |
|          | Mahalanobis | 73.90  | 82.01  | 77.63  | 80.87  | 44.01    | 92.63  | 96.68     | 46.57  | 91.66    | 53.62  |
|          | GNNSafe     | 66.70  | 83.12  | 27.08  | 93.13  | 17.87    | 94.47  | 100.00    | 50.35  | 100.00   | 36.32  |
|          | **GRASP** | **27.92** | **93.51** | **23.53** | **93.72** | **8.82** | **97.61** | **76.79** | **66.44** | **86.27** | **60.62**  |
Regarding the impact of other based models, we have shown in Table 13 that GRASP achieves optimal performance on various base models in the literature. For the reviewer’s convenience, we have included the relevant results below and in the third part of the response, which clearly attests to the versatility and practicality of GRASP:

|  | Datasets | cora   |        | amazon |        | coauthor |        | chameleon |        | squirrel |        |
|----------|-------------|--------|--------|--------|--------|----------|--------|-----------|--------|----------|--------|
| Backbone |  Method     | FPR95  | AUROC  | FPR95  | AUROC  | FPR95    | AUROC  | FPR95     | AUROC  | FPR95    | AUROC  |
| GAT      | MSP         | 55.33  | 88.82  | 29.88  | 94.39  | 28.15    | 94.26  | 91.27     | 61.94  | 95.21    | 47.50  |
|          | Energy      | 80.71  | 79.16  | 26.48  | 95.24  | 20.96    | 95.65  | 92.71     | 61.11  | 96.47    | 45.69  |
|          | KNN         | 71.14  | 81.28  | 46.42  | 90.74  | 42.51    | 91.51  | 89.02     | 61.13  | 95.37    | 53.16  |
|          | ODIN        | 55.27  | 89.06  | 26.92  | 94.89  | 24.61    | 94.95  | 90.83     | 62.89  | 96.11    | 45.68  |
|          | Mahalanobis | 67.92  | 86.37  | 14.28  | 95.80  | 26.27    | 94.46  | 95.35     | 50.65  | 91.36    | 57.67  |
|          | GNNSafe     | 58.97  | 85.64  | 29.12  | 93.16  | 25.41    | 93.91  | 100.00    | 50.39  | 100.00   | 36.21  |
|          | **GRASP**  | **22.76**  | **94.28**  | **14.21**  | **96.79**  | **8.59**     | **97.51**  | **70.15**     | **73.40**  | **85.84**    | **61.18**  |
| GCNJK    | MSP         | 81.33  | 80.40  | 32.45  | 94.64  | 26.43    | 94.44  | 86.42     | 68.19  | 94.93    | 51.83  |
|          | Energy      | 96.56  | 70.16  | 40.90  | 93.80  | 18.75    | 95.75  | 91.92     | 65.16  | 95.36    | 49.68  |
|          | KNN         | 90.98  | 73.81  | 64.47  | 85.18  | 50.95    | 89.98  | 94.45     | 59.04  | 94.64    | 53.49  |
|          | ODIN        | 81.04  | 80.68  | 28.35  | 95.13  | 21.12    | 95.41  | 86.03     | 68.58  | 95.04    | 50.64  |
|          | Mahalanobis | 60.84  | 86.20  | 61.61  | 87.11  | 83.04    | 87.34  | 87.23     | 66.61  | 91.52    | 57.24  |
|          | GNNSafe     | 65.01  | 83.11  | 22.41  | 96.28  | 13.27    | 96.47  | 100.00    | 50.40  | 100.00   | 36.21  |
|          | **GRASP**  | **29.69**  | **92.98**  | **12.66**  | **96.86**  | **8.03** | **97.74** | **59.61** | **75.78** | **86.02** | **60.70**  |
| GATJK    | MSP         | 69.56  | 84.51  | 47.21  | 91.32  | 24.66    | 95.37  | 94.39     | 55.43  | 94.67    | 50.98  |
|          | Energy      | 62.27  | 85.75  | 34.75  | 92.89  | 17.23    | 96.38  | 91.11     | 59.01  | 95.61    | 48.76  |
|          | KNN         | 82.54  | 74.32  | 70.98  | 83.48  | 38.95    | 92.56  | 92.21     | 61.14  | 95.20    | 54.32  |
|          | ODIN        | 64.25  | 85.21  | 39.29  | 92.19  | 18.16    | 96.30  | 93.56     | 56.10  | 95.24    | 48.62  |
|          | Mahalanobis | 79.60  | 79.33  | 52.79  | 88.53  | 34.60    | 93.68  | 91.59     | 52.38  | 91.52    | 56.19  |
|          | GNNSafe     | 44.43  | 90.01  | 22.46  | 95.45  | 17.54    | 95.32  | 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** | **61.17**  |
| APPNP    | MSP         | 59.37  | 89.01  | 64.64  | 86.51  | 18.38    | 96.45  | 94.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         | 75.33  | 81.21  | 49.55  | 89.76  | 38.44    | 91.71  | 92.14     | 54.19  | 94.12    | 53.14  |
|          | 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     | 59.70  | 85.45  | 19.26  | 95.08  | 12.10    | 96.60  | 100.00    | 50.45  | 100.00   | 36.24  |
|          | **GRASP** | **26.45** | **94.16** | **5.69** | **97.11** | **8.69** | **97.59** | **83.41** | **63.02** | **86.42** | **60.76**  |
Dear Reviewer hQev,

Thank you for raising the concerns regarding our claim that "GRASP still works when raw MSP fails." We appreciate the opportunity to further clarify this aspect of our study.

To delve deep into this, we conducted a visualization analysis of the MSP score distribution similar as Figure 4 across each dataset. Due to the limitations of the OpenReview platform, we are unable to upload these new figures to share the insight. (We will include in the revision) In these figures, we observe multiple distinct "heaps" in the score distribution. It is important to note that since MSP measures across the entire test set, it does not effectively capture all the local characteristics. Notably, our results indicate that selections made using Sid, which prioritizes the highest MSP scores, more composed of ID nodes rather than OOD nodes. This tendency is further reinforced with additional propagation iterations. 

We also wish to highlight additional evidence supporting the effectiveness of GRASP:

1. **GRASP is also compatible with other scoring function beyond MSP.** Substituting MSP with other well-known OOD scoring methods in our framework also yields competitive results, as shown in the table (AUROC) below. 

| 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+prop  | 87.52  | 96.27  | 95.82    | 50.42     | 36.49    |
| Energy+**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    |
| KNN+**GRASP** | **91.48** | **97.43** | **96.52** | **76.32** | **60.24**    |


2. **Enhancement of Intra-edge Ratios During Propagation.** By utilizing Sid and Sood estimates, GRASP significantly increases the proportion of intra-edges, thereby improving the overall accuracy of edge addition. The ablation study results displayed below illustrate the increased accuracy of added edges when GRASP is employed, compared to scenarios where it is not used:

| Datasets  | w/o GRASP | w GRASP |
|-----------|-----------|---------|
| cora      | 0.89      | 0.94    |
| amazon    | 0.92      | 0.94    |
| coauthor  | 0.93      | 0.99    |
| chameleon | 0.51      | 0.80    |
| squirrel  | 0.39      | 0.80    |
Thank you for your reply.

I have concerns about your claim in the paper that "GRASP still works when raw MSP fails," based on the new experiment involving the addition of incorrect edges. 
The results in Tables 2 and 3 indicate that MSP's performance is poor, which suggests that using MSP to select S_id and S_odd may introduce numerous errors. This could lead to incorrect edges being added to the augmented graph, which, based on the evidence that "GRASP's performance deteriorates significantly when the proportion of incorrect edges exceeds 0.3," could adversely impact the effectiveness of GRASP.

It's unclear under what conditions your algorithm is efficient, specifically on which kinds of graph datasets and with which base models.
Dear Reviewer xmGd,

Thank you for taking the time to read our rebuttal and for your positive feedback. We appreciate your suggestion and will incorporate these results in the revised version of our paper.

Best regards,

The Authors of Submission 12283.
Thanks for the rebuttal and sharing the additional results, I would encourage the authors to include them in the paper for a clearer indication of statistical significance of their results and contribution. 

Given my positive outlook on the paper, I would like to keep my score.
Dear Reviewer hXZy,

We are delighted that our responses have effectively addressed your concerns. Your recognition of our efforts in the paper is greatly appreciated!

Warm regards,

The Authors of Submission 12283.
Dear Authors,
        
        Thanks very much for your detailed responses. I will keep my positive score on this paper.
>**Limitation. GRASP may not be as effective in scenarios with random connectivity patterns**

We agree with the reviewer's point that when a graph has random connectivity, all methods will perform poorly because such a graph lacks any meaningful edge information, making it indeed impossible to work effectively. To validate this, we conduct a simple experiment in Cora. Specifically, we randomly shuffle the original edges of the graph while retaining the original features and labels for training the ID model. We then evaluate the performance of each baseline on the trained model. The results, presented in the table below, confirm that all methods achieve AUROC scores around 50%, comparable to random guessing. However, in real-world graphs, random connectivity is unlikely, ex. social network. In reality, there are connections between IDs, and they naturally tend to be linked together. Therefore, it is less practical to consider the network with random connectivity.

| Method      | AUROC | FPR95 |
|-------------|-------|-------|
| MSP         | 53.75 | 94.00 |
| Energy      | 53.91 | 93.91 |
| KNN         | 50.29 | 94.56 |
| ODIN        | 54.19 | 93.73 |
| Mahalanobis | 54.27 | 93.86 |
| GNNSafe     | 51.97 | 93.27 |
| GRASP       | 51.37 | 92.73 |
>**Q1. How does the performance of GRASP vary with different OOD distributions (e.g., uniform, normal, outliers)?**

We thank reviewer for the suggestion! We manually generate 2D sample points as graph nodes, with ID samples drawn from a standard Gaussian distribution and OOD samples drawn from three different distributions: a 2D uniform distribution, a different normal distribution from ID, and an outlier distribution. The outlier samples are randomly selected points outside the region of the ID sample points. We calculate the RBF kernel similarity between pairs of sample points and constructe edges between nodes with high similarity to simulate the similarity between nodes' embeddings after training GNN.

The experimental results are shown in the table below. The results indicate that GRASP performs best when the OOD is normal, worst when the OOD is uniform, and intermediate when the OOD is outlier.

| OOD           | AUROC  | FPR |
|---------------|--------|-----|
| Before GRASP  | 56.20  | 92  |
| uniform+GRASP | 74.08  | 62  |
| normal+GRASP  | 97.98  | 0   |
| outlier+GRASP | 85.81  | 47  |

We are happy to provide more experiment results for reviewer's interest!


>**Q2. Can the authors provide further insights into how GRASP works and how it interprets the graph structure?**


Thank you for your inquiry about the rationale behind GRASP! Here's a succinct overview to aid your understanding:

- **Core Principle**: The effectiveness of GRASP in enhancing graph OOD detection hinges on increasing the proportion of intra-edges before performing score propagation.
- **Implementation**: Based on this principle, GRASP identifies a subset $G$ within the graph, characterized by having more connections to ID data than to OOD data. Additional edges within $G$ are then added to enhance the score propagration for OOD detection. 

Regarding your question on how GRASP interprets the graph structure:

- GRASP is designed to amplify the score difference between $\mathcal{V}\_{uid}$  (nodes to be identified as ID) and $\mathcal{V}\_{uood}$ (nodes to be identified as OOD). By reinforcing connections within the subset $G$ that has stronger ties to ID data, and then conducting score propagation, it exert a greater influence on $\mathcal{V}\_{uid}$ compared to $\mathcal{V}\_{uood}$. This structured modification and targeted propagation are pivotal for enhancing the discriminative capability of the network against OOD nodes.

If there is any aspect of the question that we have misunderstood, or if further clarification is required, please do not hesitate to let us know!


>**Q3. How does the performance of GRASP scale with the size of the graph and the number of nodes? Is there any systemic analysis?**


The 10 datasets used in our experiments cover various scales from small scale to large scale. As shown in Tables 1-3, GRASP's performance is not significantly affected by the scale or size of the datasets. Instead, its performance is more influenced by the proportion of inter-edges in the original datasets. 

| Datasets      | #Nodes  | #Edges    | Ratio of intra-edges | Ratio of inter-edges | AUROC  |
|---------------|---------|-----------|----------------------|----------------------|--------|
| cora          | 2708    | 5429      | 92.23                | 7.77                 | 93.50  |
| amazon        | 7650    | 238162    | 96.56                | 3.44                 | 96.68  |
| coauthor      | 18333   | 163788    | 97.18                | 2.82                 | 97.75  |
| chameleon     | 2277    | 31421     | 78.81                | 21.19                | 76.93  |
| squirrel      | 5201    | 198493    | 62.54                | 37.46                | 61.09  |
| reddit2       | 232965  | 23213838  | 97.90                | 2.10                 | 98.50  |
| ogbn-products | 2449029 | 61859140  | 93.56                | 6.44                 | 93.79  |
| arxiv-year    | 169343  | 1166243   | 82.15                | 17.85                | 81.24  |
| snap-patents  | 2923922 | 13975788  | 71.94                | 28.06                | 72.13  |
| wiki          | 1925342 | 303434860 | 79.64                | 20.36                | 77.97  |
| Datasets    | cora          |               | amazon        |               | coauthor     |               | chameleon    |               | squirrel     |               |
|-------------|---------------|---------------|---------------|---------------|--------------|---------------|--------------|---------------|--------------|---------------|
| method      | AUROC         | FPR95         | AUROC         | FPR95         | AUROC        | FPR95         | AUROC        | FPR95         | AUROC        | FPR95         |
| 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  |
| 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  |
| 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  |
| 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  |
| 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  |
| 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  |
| 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  |
| 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  |
| 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 |
| 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  |

| Datasets    | reddit2      |              | odbn-product |              | arxiv-year    |               | snap-patents |              | wiki         |              |
|-------------|--------------|--------------|--------------|--------------|---------------|---------------|--------------|--------------|--------------|--------------|
| Method      | AUROC        | FPR95        | AUROC        | FPR95        | AUROC         | FPR95         | AUROC        | FPR95        | AUROC        | FPR95        |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| GKDE        | OOT          |              | OOM          |              | OOM           |               | OOM          |              | OOM          |              |
| GPN         | OOM          |              | OOM          |              | 50.97 ± 14.98 | 95.62 ± 3.29  | OOM          |              | OOM          |              |
| OODGAT      | OOM          |              | OOM          |              | 59.38 ± 3.44  | 92.90 ± 0.94  | OOM          |              | OOM          |              |
| 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 |
| 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 |
>**W3&Q2. Justification regarding using Bernoulli distribution to model edge weights.**

Fair Concern! As we are dealing with discrete graphs, where edges either exist or do not, the adjacency matrix values are binary, taking on either 0 or 1. This naturally aligns with the Bernoulli distribution, which is frequently employed in graph structure learning, as exemplified in several pertinent references in [A,B,C].

[A] Learning Discrete Structures for Graph Neural Networks. ICML'19.

[B] Variational Inference for Graph Convolutional Networks in the Absence of Graph Data and Adversarial Settings. NeurIPS'20.

[C] Data Augmentation for Graph Neural Networks. AAAI'21.

>**W3-2. Examples that demonstrate the importance of the number of intra-edges and inter-edges.**

We present detailed evidence in Table 14, which outlines the relationship between the ratio of intra-edges and OOD detection performance across 10 real datasets. The data illustrate that a higher number of intra-edges is crucial for effective OOD detection.

>**Q1. Request for an intuitive example showing the importance of intra-edges and inter-edges in OOD detection.**

Figure 2 provides a clear, intuitive example demonstrating how variations in the number of intra-edges versus inter-edges impact OOD detection. The two graphs in Figure 2 have the same nodes, but due to the differing numbers of intra-edges and inter-edges, they yield completely opposite results after score propagation. Specifically, score propagation enhances OOD detection performance only when intra-edges dominate; otherwise, it  may in turn hurt the performance. This conclusion is supported by the emperical results of our used real datasets, as shown in Table 2, Table 3, and Table 14.

>**Q3. Concern about lower FPR on the dataset Reddit2 compared to other models.**

The notable decrease in False Positive Rate (FPR) observed with GRASP on the Reddit2 dataset can be attributed to an increased proportion of intra-edges, as detailed in Table 14. After propagating score along $A\_+$, the high scores of ID nodes are transferred more to $\mathcal{V}\_{uid}$ than to $\mathcal{V}\_{uood}$, resulting in higher scores for $\mathcal{V}\_{uid}$ than for $\mathcal{V}\_{uood}$, thus widening the gap between $\mathcal{V}\_{uid}$ and $\mathcal{V}\_{uood}$ and reducing the misidentification of OOD. Figure 1 in the attached pdf  (Please refer to the Common Responses section titled "Author Rebuttal by Authors" https://openreview.net/forum?id=jb5qN3212b&noteId=HVpGXjNQ0B) shows the score distribution of $\mathcal{V}\_{uid}$ and $\mathcal{V}_{uood}$ on Reddit2 before and after using GRASP respectively. The shaded area with diagonal lines represents FPR, visually illustrating the aforementioned reasons.

>**Q4. Patterns in the ratio of intra-edges to inter-edges for better OOD detection performance.**

The following table systematically presents the impact of the intra- to inter-edge ratio ($\eta\_{intra}$/$\eta\_{inter}$) on OOD detection performance across various datasets. The results indicate that the number of intra-edges plays a crucial role in OOD detection performance. When the ratio of intra-edges is increased to dominate, score propagation can achieve excellent OOD detection performance across different datasets.

| | Before Applying GRASP |        | After Applying GRASP |        |
|---------------|-----------------------|--------|----------------------|--------|
| Datasets      | $\eta\_{intra}$/$\eta\_{inter}$ | AUROC  |$\eta\_{intra}$/$\eta\_{inter}$ | AUROC  |
| cora          | 4.65                  | 87.52  | 11.87                | 93.50  |
| amazon        | 14.24                 | 96.27  | 28.07                | 96.68  |
| coauthor      | 12.66                 | 95.82  | 34.46                | 97.75  |
| chameleon     | 1.03                  | 50.42  | 3.72                 | 76.93  |
| squirrel      | 0.65                  | 35.88  | 1.67                 | 61.09  |
| reddit2       | 0.68                  | 31.99  | 46.62                | 98.50  |
| ogbn-products | 4.55                  | 85.66  | 14.53                | 93.79  |
| arxiv-year    | 0.72                  | 35.30  | 4.60                 | 81.24  |
| snap-patents  | 0.53                  | 27.35  | 2.56                 | 72.13  |
| wiki          | 1.52                  | 60.32  | 3.91                 | 77.97  |