Bridging OOD Detection and Generalization: A Graph-Theoretic View

Authors: han  wang
yixuan  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-06 18:06:42

Abstract: In the context of modern machine learning, models deployed in real-world scenarios often encounter diverse data shifts like covariate and semantic shifts, leading to challenges in both out-of-distribution (OOD) generalization and detection. Despite considerable attention to these issues separately, a unified framework for theoretical understanding and practical usage is lacking. To bridge the gap, we introduce a graph-theoretic framework to jointly tackle both OOD generalization and detection problems. By leveraging the graph formulation, data representations are obtained through the factorization of the graph's adjacency matrix, enabling us to derive provable error quantifying OOD generalization and detection performance. Empirical results showcase competitive performance in comparison to existing methods, thereby validating our theoretical underpinnings.

Main paper: 
 introduction: 
 Machine learning models deployed in real-world applications often confront data that deviates from the training distribution in unforeseen ways. As depicted in Figure 1 , a model trained on in-distribution (ID) data (e.g., seabirds) may encounter data exhibiting covariate shifts, such as birds in forest environments. In this scenario, the model must retain its ability to accurately classify these covariate-shifted out-of-distribution (OOD) samples as birds-an essential capability known as OOD generalization [1, 2] . Alternatively, the model may encounter data with novel semantics, like dogs, which it has not seen during training. In this case, the model must recognize these semantic-shifted OOD samples and abstain from making incorrect predictions, underscoring the significance of OOD detection [3, 4] . Thus, for a model to be considered robust and reliable, it must excel in both OOD generalization and detection, tasks that are often addressed separately in current research.Recently, Bai et al. [5] introduced a framework that addresses both OOD generalization and detection simultaneously. The problem setting leverages unlabeled wild data naturally arising in the model's operational environment, representing it as a composite distribution of ID, covariate-shifted OOD, and semantic-shifted OOD data. While such data is ubiquitously available in many real-world applications, harnessing the power of wild data is challenging due to the heterogeneity of the wild data distribution-the learner lacks clear membership (ID, Covariate-OOD, Semantic-OOD) for samples drawn from the wild data distribution. Despite empirical progress made, a formalized understanding of how wild data impacts OOD generalization and detection is still lacking.In this paper, we formalize a graph-theoretic framework for understanding OOD generalization and detection problems jointly. We begin by formulating a graph, where the vertices are all the data points and edges connect similar data points. These edges are defined based on a combination of supervised < l a t e x i t s h a 1 _ b a s e 6 4 = " L z 8 y 6 G S h w 3 q O J a s F I h c v 3 N A X Q 1 s = " > 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 a h X s p u K e q x 6 M V j B f s B 7 V K y a b a N z S Z L k h X L 0 v / g x Y M i X v 0 / 3 v w 3 p u 0 e t P a c u j M H X i V u Q W p Q o D W o f n n D h G Y x k 4 Y K o n X f d V L j 5 0 Q Z T g W b V r x M s 5 T Q M Y l Y 3 1 J J Y q b 9 f H 7 x F J 9 Z Z Y j D R N m S B s / V 3 x M 5 i b W e x I H t j I k Z 6 W V v J v 7 n 9 T M T 3 v g 5 l 2 l m m K S L R W E m s E n w 7 H 0 8 5 I p R I y a W E K q 4 v R X T E V G E G h t S x Y b g L r + 8 S j o X d f e q f n l / W W s 0 i z j K c A K n c A 4 u X E M D 7 q A F b a A g 4 RY i s K q / b n c c a E Y 7 E k d Q l p A 6 E g = " > A A A B 6 H i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e x K U I 9 B L 5 4 k A f O A Z A m z k 9 5 k z O z s M j M r h J A v 8 O J B E a 9 + k j f / x k m y B 0 0 s a C i q u u n u C h L B t X H d b y e 3 t r 6 x u Z X f L u z s 7 u 0 f F A + P m j p O F c M G i 0 W s 2 g H V K L j E h u F G Y D t R S K N A Y C s Y 3 c 7 8 1 h M q z W P 5 Y M Y J + h E d S B 5 y R o 2 V 6 v e 9 Y s k t u 3 O Q V e J l p A Q Z a r 3 i V 7 c f s z R C a Z i g W n c 8 N z H + h C r D m c B p o Z t q T C g b 0 Q F 2 L J U 0 Q u 1 P 5 o d O y Z l V + i S M l S 1 p y F z 9 P T G h k d b j K L C d E T V D v e z N x P + 8 T m r C a 3 / C Z Z I a l G y x K E w F M T G Z f U 3 6 X C E z Y m w J Z Y r b W w k b U k W Z s d k U b A j e 8 s u r p H l R 9 i 7 L l X q l V L 3 J 4 s j D C Z z C O X h w B V Wa c u j M H X i V u Q W p Q o D W o f n n D h G Y x k 4 Y K o n X f d V L j 5 0 Q Z T g W b V r x M s 5 T Q M Y l Y 3 1 J J Y q b 9 f H 7 x F J 9 Z Z Y j D R N m S B s / V 3 x M 5 i b W e x I H t j I k Z 6 W V v J v 7 n 9 T M T 3 v g 5 l 2 l m m K S L R W E m s E n w 7 H 0 8 5 I p R I y a W E K q 4 v R X T E V G E G h t S x Y b g L r + 8 S j o X d f e q f n l / W W s 0 i z j K c A K n c A 4 u X E M D 7 q A F b a A g 4 R+ 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 v X y 4 r N R u 8 z i K c A K n c A 4 e X E M N 7 q E O D W A w g G d 4 h T d H O C / O u / O x a C 0 4 + c w x / I H z + Q M L k o 2 n < / l a t e x i t >v1 < l a t e x i t s h a 1 _ b a s e 6 4 = " p d 6 C G + f g X j P a 9 T r I / + S v i f D 5 V x Y = " > A A A B 6 n i c b V D L T g J B E O z F F + I L 9 e h l I j H x R H Y J U Y 9 E L x 4 x y i O B D Z k d e m H C 7 O x m Z p a E E D 7 B i w e N 8 e o X e f N v H G A P C l b S S a W q O 9 1 d Q S K 4 N q 7 7 7 e Q 2 N r e 2 d / K 7 h b 3 9 g 8 O j 4 v F J U 8 e p Y t h g s Y h V O 6 A a B Z f Y M N w I b C c K a R Q I b A W j u 7 n f G q P S P J Z P Z p K g H 9 G B 5 C F n 1 F j p c d y r 9 I o l t + w u Q N a J l 5 E S Z K j 3 i l / d f s z S C K V h g m r d 8 d z E + F O q D G c C Z 4 V u q j G h b E Q H 2 L F U 0 g i 1 P 1 2 c O i M X V u m T M F a 2 p C E L 9 f f E l E Z a T 6 L A d k b U D P W q N x f / 8 z q p C W / 8 K Z d J a l C y 5 a I w F c T E Z P 4 3 6 X O F z I i J J Z Q p b m 8 l b E g V Z c a m U 7 A h e K s v r 5 N m p e x d l a s P 1 V L t N o s j D 2 d w D p f g w T X U 4 B 7 q 0 A A G A 3 i G V 3 h z h P P i v D s f y 9 a c k 8 2 c w h 8 4 n z 8 N F o 2 o < / l a t e x i t > v2 < l a t e x i t s h a 1 _ b a s e 6 4 = " b 2 t E e K l W W v / D N O 1 w X N 9 n z f 0 5 O 4 M = " > A A A B 6 n i c b V D L T g J B E O z F F + I L 9 e h l I j H x R H a V q E e i F 4 8 Y 5 Z H A h s w O v T B h d n Y z M 0 t C C J / g x Y P G e P W L v P k 3 D r A H B S v p p F L V n e 6 u I B F c G 9 f 9 d n J r 6 x u b W / n t w s 7 u 3 v 5 B 8 f C o o e N U M a y z W M S q F V C N g k u s G 2 4 E t h K F N A o E N o P h 3 c x v j l B p H s s n M 0 7 Q j 2 h f 8 p A z a q z 0 O O p e d o s l t + z O Q V a J l 5 E S Z K h 1 i 1 + d X s z S C K V h g m r d 9 t z E + B O q D G c C p 4 V O q j G h b E j 7 2 L Z U 0 g i 1 P 5 m f O i V n V u m R M F a 2 p C F z 9 f f E h E Z a j 6 P A d k b U D P S y N x P / 8 9 q p C W / 8 C Z d J a l C y x a I w F c T E Z P Y 3 6 X G F z I i x J Z Q p b m 8 l b E A V Z c a m U 7 A h e M s v r 5 L G R d m 7 K l c e K q X q b R Z H H k 7 g F M 7 B g 2 u o w j 3 U o A 4 M + v A M r / D m C O f F e X c + F q 0 5 J 5 s 5 h j 9 w P n 8 A D p q N q Q = = < / l a t e x i t > v3 … < l a t e x i t s h a 1 _ b a s e 6 4 = " u 1 S i p M O A s 8 Y e s 7 u 4 M P V C d m T p u z o = " > A A A B 6 n i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e x K U I 9 B L 5 4 k o n l A s o T Z S W 8 y Z H Z 2 m Z k N h J B P 8 O J B E a 9 + k T f / x k m y B 0 0 s a C i q u u n u C h L B t X H d b y e 3 t r 6 x u Z X f L u z s 7 u 0 f F A + P G j p O F c M 6 i 0 W s W g H V K L j E u u F G Y C t R S K N A Y D M Y 3 s 7 8 5 g i V 5 r F 8 M u M E / Y j 2 J Q 8 5 o 8 Z K j 6 P u f b d Y c s v u H G S V e B k p Q Y Z a t / j V 6 c U s j V A a J q j W b c 9 N j D + h y n A m c F r o p B o T y o a 0 j 2 1 L J Y 1 Q + 5 P 5 q V N y Z p U e C W N l S x o y V 3 9 P T G i k 9 T g K b G d E z U A v e z P x P 6 + d m v D a n 3 C Z p A Y l W y w K U 0 F M T G Z / k x 5 X y I w Y W 0 K Z 4 v Z W w g Z U U W Z s O g U b g r f 8 8 i p p X J S 9 y 3 L l o V K q 3 m R x 5 O E E T u E c P L i C K t x B D e r A o A / P 8 A p v j n B e n H f n Y 9 G a c 7 K Z Y / g D 5 / M H N 4 a N x A = = < / l a t e x i t > vN < l a t e x i t s h a 1 _ b a s e 6 and self-supervised signals, incorporating both labeled ID data and unlabeled wild data. By modeling the connectivity among data points, we can uncover meaningful sub-structures in the graph (e.g., covariate-shifted OOD data is embedded closely to the ID data, whereas semantic-shifted OOD data is distinguishable from ID data). Importantly, this graph serves as a foundation for understanding the impact of wild unlabeled data on both OOD generalization and detection, enabling a theoretical characterization of performance through graph factorization. Within this framework, we derive a formal linear probing error, quantifying the misclassification rate on covariate-shifted OOD data. Furthermore, our framework yields a closed-form solution that quantifies the distance between ID and semantic OOD data, directly elucidating OOD detection performance (Section 4).4 = " R p Y Q 6 Q a 1 5 X a P 7 2 m B B G i 7 i 2 2 d q X M = " > A A A B 8 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 I t Q 9 O K x g v 2 A N p b N d t M u 3 W T D 7 k Q o o T / D i w d F v P p r v P l v 3 L Y 5 a O u D g c d 7 M 8 z M C x I p D L r u t 1 N Y W V 1 b 3 y h u l r a 2 d 3 b 3 y v s H T a N S z X i D K a l 0 O 6 C G S x H z B g q U v J 1 o T q N A 8 l Y w u p 3 6 r S e u j V D x A 4 4 T 7 k d 0 E I t Q M I p W 6 j Q f s y 6 q Z E K u S a 9 c c a v u D G S Z e D m p Q I 5 6 r / z V 7 S u W R j x G J q k x H c 9 N 0 M + o R s E k n 5 S 6 q e E J Z S M 6 4 B 1 L Y x p x 4 2 e z k y f k x C p 9 E i p t K 0 Y y U 3 9 P Z D Q y Z h w F t j O i O D S L 3 l T 8 z + u k G F 7 5 m Y i T F H n M 5 o v C V B J U Z P o / 6 Q v N G c q x J Z R p Y W 8 l b E g 1 Z W h T K t k Q v M W X l 0 n z r O p d V M / v z y u 1 m z y O I h z B M Z y C B 5 d Q g z u o Q w M Y K H i G VBeyond theoretical analysis, our graph-theoretic framework can be used practically. In particular, the spectral decomposition can be equivalently achieved by minimizing a surrogate objective, which can be efficiently optimized end-to-end using modern neural networks. Thus, our approach enjoys theoretical guarantees while being applicable to real-world data. Experimental results demonstrate the effectiveness of our graph-based approach, showcasing substantial improvements in both OOD generalization and detection performance. In comparison to the state-of-the-art method Scone [5] , our approach achieves a significant reduction in FPR95 by an average of 8.34% across five semantic-shift OOD datasets (Section 5). We summarize our main contributions below:1. We introduce a graph-theoretic framework for understanding both OOD generalization and detection, formalizing it by spectral decomposition of the graph containing ID, covariateshift OOD data, and semantic-shift OOD data.2. We provide theoretical insights by quantifying OOD generalization and detection performance through provable error, based on the closed-form representations derived from the spectral decomposition on the graph.3. We evaluate our model's performance through a comprehensive set of experiments, providing empirical evidence of its robustness and its alignment with our theoretical analysis. Our model consistently demonstrates strong OOD generalization and OOD detection capabilities, achieving competitive results when benchmarked against the existing state-of-the-art. 
problem setup: 
 We consider the empirical training set D l ∪ D u as a union of labeled and unlabeled data. The labeled set D l = {x i , y i } n i=1 , where y i belongs to known class space Y l . Let P in denote the marginal distribution over input space, which is referred to as the in-distribution (ID). Following Bai et al. [5] , the unlabeled set D u = {x i } m i=1 consists of ID, covariate OOD, and semantic OOD data, where each sample xi is drawn from a mixture distribution defined below.Definition 2.1. The marginal distribution of the wild data is defined as: Learning goal. We aim to learn jointly an OOD detector g θ : X → {IN, OUT} and a multi-class classifier f θ , by leveraging labeled ID data D l and unlabeled wild data D u . Let ŷ(f θ (x)) := argmax y f (y) θ (x), where f (y) θ (x) denotes the y-th element of f θ (x), corresponding to label y. We notate g θ and f θ with parameters θ to indicate that these functions share neural network parameters. In our model evaluation, we are interested in three metrics: Definition 2.2. We define ID generalization accuracy (ID-Acc), OOD generalization accuracy (OOD-Acc), and OOD detection error as follows:↑ ID-Acc(f θ ) := E (x,y)∼Pin (1{ y(f θ (x)) = y}), ↑ OOD-Acc(f θ ) := E (x,y)∼P covariate out (1{ y(f θ (x)) = y}), ↓ FPR(g θ ) := E x∼P semantic out (1{g θ (x) = IN}),where 1{•} represents the indicator function, and the arrows indicate the directionality of improvement (higher/lower is better). For OOD detection, ID samples are considered positive and FPR signifies the false positive rate.3 Graph-Based Framework for OOD Generalization and Detection 
graph formulation: 
 We start by formally defining the graph and adjacency matrix. We use x to denote the set of all natural data (raw inputs without augmentation). Given an x, we use T (x|x) to denote the probability of x being augmented from x, and T (•|x) to denote the distribution of its augmentation. For instance, when x represents an image, T (•|x) can be the distribution of common augmentations [6] such as Gaussian blur, color distortion, and random cropping. We define X as a general population space, which contains the set of all augmented data. In our case, X is composed of augmented samples from both labeled ID data X l and unlabeled wild data X u , with cardinality |X | = N .We define the graph G(X , w) with vertex set X and edge weights w. Given our data setup, edge weights w can be decomposed into two components: (1) self-supervised connectivity w (u) by treating all points in X as entirely unlabeled, and (2) supervised connectivity w (l) by incorporating labeled information from X l to the graph. We define the connectivity formally below. Definition 3.1 (Self-supervised connectivity). For any two augmented data x, x ′ ∈ X , w (u) xx ′ denotes the marginal probability of generating the positive pair [7] :EQUATIONwhere x and x ′ are augmented from the same image x ∼ P, and P is the marginal distribution of both labeled and unlabeled data. A larger w (u)xx ′ indicates stronger similarity between x and x ′ .Moreover, when having access to the labeling information for ID data, we can define the edge weight by adding additional supervised connectivity to the graph. We consider (x, x ′ ) a positive pair when x and x ′ are augmented from two labeled samples xl and x′ l with the same known class i ∈ Y l . The total edge connectivity can be formulated as below: Definition 3.2 (Total edge connectivity). Considering both self-supervised and supervised connectivities, the overall similarity for any pair of data (x, x ′ ) is formulated as:EQUATIONwhere P li is the distribution of labeled samples with class label i ∈ Y l , and the coefficients η u , η l modulate the relative importance between the two terms.Adjacency matrix. Having established the notion of connectivity, we can define the adjacency matrix A ∈ R N ×N with entries A xx ′ = w xx ′ . The adjacency matrix can be decomposed into the summation of self-supervised adjacency matrix A (u) and supervised adjacency matrix A (l) :EQUATIONAs a standard technique in graph theory [8] , we use the normalized adjacency matrix:EQUATIONwhere D ∈ R N ×N is a diagonal matrix with D xx = w x = x ′ ∈X w xx ′ , indicating the total edge weights connected to a vertex x. The normalized adjacency matrix defines the probability of x and x ′ being considered as the positive pair. The normalized adjacency matrix allows us to perform spectral decomposition as we show next.In this section, we perform spectral decomposition or spectral clustering [9] -a classical approach to graph partitioning-to the adjacency matrices defined above. This process forms a matrix where the top-k eigenvectors are the columns and each row of the matrix can be viewed as a k-dimensional representation of an example. The resulting feature representations enable us to rigorously analyze the separability of ID data from semantic OOD data in a closed form, as well as the generalizability to covariate-shifted OOD data (more in Section 4).Towards this end, we consider the following optimization, which performs low-rank matrix approximation on the adjacency matrix:EQUATIONwhere ∥ • ∥ F denotes the matrix Frobenious norm. According to the Eckart-Young-Mirsky theorem [10] , the minimizer of this loss function isF k ∈ R N ×k such that F k F ⊤ k contains the top-k components of Ã's eigen decomposition.A surrogate objective. In practice, directly solving objective (5) can be computationally expensive for an extremely large matrix. To circumvent this, the feature representations can be equivalently recovered by minimizing the following contrastive learning objective [11] , which can be efficiently trained end-to-end using a neural network:EQUATIONwhereL 1 (f ) = i∈Y l E xl ∼P l i ,x ′ l ∼P l i , x∼T (•|x l ),x + ∼T (•|x ′ l ) f (x) ⊤ f x + , L 2 (f ) = E xu∼P, x∼T (•|xu),x + ∼T (•|xu) f (x) ⊤ f x + , L 3 (f ) = i,j∈Y l E xl ∼P l i ,x ′ l ∼P l j , x∼T (•|x l ),x -∼T (•|x ′ l ) f (x) ⊤ f x -2 , L 4 (f ) = i∈Y l E xl ∼P l i ,xu∼P, x∼T (•|x l ),x -∼T (•|xu) f (x) ⊤ f x -2 , L 5 (f ) = E xu∼P,x ′ u ∼P, x∼T (•|xu),x -∼T (•|x ′ u ) f (x) ⊤ f x -2 .Importantly, this contrastive loss allows drawing a theoretical equivalence between learned representations and the top-k singular vectors of Ã, and facilitates theoretical understanding of the OOD generalization and detection on the data represented by Ã. The equivalence is formalized below. Theorem 3.3 (Theoretical equivalence between two objectives). We define each row f ⊤ x of F as a scaled version of learned feature embedding f :X → R k , with f x = √ w x f (x).Then minimizing the loss function L mf (F, A) in Equation 5is equivalent to minimizing the surrogate loss in Equation 6. Full proof is in Appendix A.Interpretation for OOD generalization and detection. The loss learns feature representation jointly from both labeled ID data and unlabeled wild data, so that meaningful structures emerge for both OOD generalization and detection (e.g., covariate-shifted OOD data is embedded closely to the ID data, whereas semantic-shifted OOD data is distinguishable from ID data). At a high level, the loss components L 1 and L 2 contribute to pulling the embeddings of positive pairs closer, while L 3 , L 4 and L 5 push apart the embeddings of negative pairs. In particular, loss components on the positive pairs can pull together samples sharing the same classes, thereby helping OOD generalization. At the same time, loss components on the negative pairs can help separate semantic OOD data in the embedding space, thus benefiting OOD detection.Difference from prior works. Spectral contrastive learning has been employed to analyze problems such as self-supervised learning [7] , unsupervised domain adaptation [12] , novel category discovery [13] , open-world semi-supervised learning [11] etc. These works share the underlying loss form by pulling together positive pairs and pushing away negative pairs. Despite the shared loss formulation, our work has fundamentally distinct data setup and learning goals, which focus on the joint OOD generalization and detection problems (cf. Section 2). We are interested in leveraging labeled ID data to classify both unlabeled ID and covariate OOD data correctly into the known categories while rejecting the remainder of unlabeled data from new categories, which was not studied in the prior works. Accordingly, we derive a novel theoretical analysis for our setup and present empirical verification uniquely tailored to our problem focus, which we present next. 
theoretical analysis: 
 In this section, we present a novel theoretical analysis of how the learned representations via graph spectral can facilitate both OOD generalization and detection.To obtain the representations, one can train the neural network f : X → R k using the spectral loss defined in Equation 6. Minimizing the loss yields representation Z ∈ R N ×k , where each row vector z i = f (x i ) ⊤ . According to Theorem 3.3, the closed-form solution for the representations is equivalent to performing spectral decomposition of the adjacency matrix. Thus, we haveF k = √ DZ, where F k F ⊤ k contains the top-k components of Ã's SVD decomposition and D is the diagonal matrix. We further define the top-k singular vectors of Ã as V k ∈ R N ×k , so we have F k = V k √ Σ k, where Σ k is a diagonal matrix of the top-k singular values of Ã. By equalizing the two forms of F k , the closed-formed solution of the learned feature space is given by Z= [D] -1 2 V k √ Σ k .Linear probing evaluation. We assess OOD generalization performance based on the linear probing error, which is commonly used in self-supervised learning [6] . Specifically, the weight of a linear classifier is denoted as M ∈ R k×|Y l | , which is learned with ID data to minimize the error. The class prediction for an input x is given by h(x; f, M) = argmax i∈Y l (f (x) ⊤ M) i . The linear probing error measures the misclassification of linear head on covariate-shifted OOD data:EQUATIONwhere y(x) indicates the ground-truth class of x. E(f ) = 0 indicates perfect OOD generalization.Separability evaluation. Based on the closed-form embeddings, we can also quantify the distance between the ID and semantic OOD data:EQUATION)The magnitude of S(f ) reflects the extent of separation between ID and semantic OOD data. Larger S(f ) suggests better OOD detection capability.Setup. We use an illustrative example to explain our theoretical insights. In Figure 2 to the augmented view x:EQUATIONHere d(x) is the domain of sample x, and y(x) is the class label of sample x. α indicates the augmentation probability when two samples share the same label but different domains, and β indicates the probability when two samples share different class labels but with the same domain. It is natural to assume the magnitude order that follows ρ ≫ max(α, β) ≥ min(α, β) ≫ γ ≥ 0.Adjacency matrix. With Eq. 9 and the definition in Section 3.1, we can derive the analytic form of adjacency matrix A.EQUATIONEQUATIONwhere C is the normalization constant to ensure the summation of weights amounts to 1. Each row or column encodes connectivity associated with a specific sample, ordered by: angel sketch, tiger sketch, angel painting, tiger painting, and panda. We refer readers to Appendix D.1 for the detailed derivation.Main analysis. We are primarily interested in analyzing the representation space derived from A.We mainly put analysis on the top-3 eigenvectors V ∈ R 5×3 and measure both the linear probing error and separability. The full derivation of Theorem 4.1 and Theorem 4.2 can be found in Appendix D.1. Theorem 4.1. Assume η u = 5, η l = 1, we have:EQUATIONInterpretation. The discussion can be divided into two cases: (1) 9 8 α > β.(2) 9 8 α < β. In the first case when the connection between the class (multiplied by 9 8 ) is stronger than the domain, the model could learn a perfect ID classifier based on features in the first two rows in V and effectively generalize to the covariate-shifted domain (the third and fourth row in V ), achieving perfect OOD generalization with linear probing error E(f ) = 0. In the second case when the connection between the domain is stronger than the connection between the class (scaled by 9 8 ), the embeddings of covariate-shifted OOD data are identical, resulting in high OOD generalization error. Theorem 4.2. Denote α ′ = α ρ and β ′ = β ρ and assume η u = 5, η l = 1, we have: EQUATION 
experiments: 
 Beyond theoretical insights, we show empirically that our approach is competitive. We present the experimental setup in Section 5.1, results in Section 5.2, and further analysis in Section 5.3.Datasets and benchmarks. Following the setup of [5] , we employ CIFAR-10 [14] as P in and CIFAR-10-C [15] with Gaussian additive noise as the P covariate out . For P semantic out , we leverage SVHN [16] , LSUN [17] , Places365 [18] , Textures [19] . To simulate the wild distribution P wild , we adopt the same mixture ratio as in Scone [5] , where π c = 0.5 and π s = 0.1. Detailed descriptions of the datasets and data mixture can be found in the Appendix E.1. To demonstrate the adaptability and robustness of our proposed method, we extend the framework to more diverse and challenging datasets. Large-scale results on the ImageNet dataset can be found in Appendix E.2. Additional results on the Office-Home [20] can be found in Appendix E.3. More ablation studies can be found in Appendix E.4.Implementation details. We adopt Wide ResNet with 40 layers and a widen factor of 2 [21] . We use stochastic gradient descent with Nesterov momentum [22] , with weight decay 0.0005 and momentum 0.09. We divide CIFAR-10 training set into 50% labeled as ID and 50% unlabeled. And we mix unlabeled CIFAR-10, CIFAR-10-C, and semantic OOD data to generate the wild dataset. Starting from random initialization, we train the network with the loss function in Eq. 6 for 1000 epochs. The learning rate is 0.03 and the batch size is 512. η u is selected within {1.00, 2.00} and η l is within {0.02, 0.10, 0.50, 1.00}. Subsequently, we follow the standard approach [12] and use labeled ID data to fine-tune the model with cross-entropy loss for better generalization ability. We fine-tune for 20 epochs with a learning rate of 0.005 and batch size of 512. The fine-tuned model is used to evaluate the OOD generalization and OOD detection performance. We utilize a distance-based method for OOD detection, which resonates with our theoretical analysis. Specifically, our default approach employs a simple non-parametric KNN distance [23] , which does not impose any distributional assumption on the feature space. The threshold is determined based on the clean ID set at 95% percentile. For further implementation details, hyper-parameters, and validation strategy, please see Appendix F.Competitive empirical performance. The main results in Table 1 demonstrate that our method not only enjoys theoretical guarantees but also exhibits competitive empirical performance compared to existing baselines. For a comprehensive evaluation, we consider three groups of methods for OOD generalization and OOD detection. Closest to our setting, we compare with strong baselines trained with wild data, namely OE [36] , Energy-regularized learning [26] , Woods [37] , and Scone [5] .The empirical results provide interesting insights into the performance of various methods for OOD detection and generalization. (1) Methods tailored for OOD detection tend to capture the domainvariant information and struggle with the covariate distribution shift, resulting in suboptimal OOD accuracy. (2) While approaches for OOD generalization demonstrate improved OOD accuracy, they cannot effectively distinguish between ID data and semantic OOD data, leading to poor OOD detection performance. (3) Methods trained with wild data emerge as robust OOD detectors, yet display a notable decline in OOD generalization, highlighting the confusion introduced by covariate Better adaptation to the heterogeneous distribution. We conduct a comparative analysis of our methods against other state-of-the-art spectral learning approaches within their respective domains. Specifically, Haochen et al. [7] investigate unsupervised learning, Shen et al. [12] delve into unsupervised domain adaptation, and Sun et al. [13] explores novel class discovery. The baseline methods all assume unlabeled data exhibits a homogeneous distribution, either entirely from P covariate out in the case of unsupervised domain adaptation or entirely from P semantic out in the case of novel class discovery. As depicted in Table 2 , our results reveal a significant improvement over competing baselines on both OOD generalization and detection. We attribute this empirical success to our better adaptation to the heterogeneous mixture of wild distributions. Additional results can be found in Table 6 . More ablation studies can be found in Appendix E.4.Visualization of OOD detection score distributions. In Figure 4 (a), we visualize the distribution of KNN distances. The KNN scores are computed based on samples from the test set after contrastive training and fine-tuning stages. There are two salient observations: First, our learning framework effectively pushes the semantic OOD data to be apart from the ID data in the embedding space, which benefits OOD detection. Moreover, as evidenced by the small KNN distance, covariate-shifted OOD data is embedded closely to the ID data, which aligns with our expectations. [39, 24, 40] , energy-based methods [26, 41, 42, 43, 44, 29] , distancebased methods [45, 46, 47, 23, 48, 49, 50] , and gradient-based method [51] . On the other hand, regularization-based methods aim to train the OOD detector by training-time regularization. Most approaches require auxiliary OOD data [52, 53, 54, 36, 55, 56, 57] . However, a limitation of existing methods is the reliance on clean semantic OOD datasets for training. To address this challenge, WOODS [37] first explored the use of wild data, which includes unlabeled ID and semantic OOD data. Building upon this idea, SCONE [5] extended the characterization of wild data to encompass ID, covariate OOD, and semantic OOD data, providing a more generalized data mixture in practice. In our paper, we provide a novel graph-theoretic approach for understanding both OOD generalization and detection based on the setup proposed by Scone [5] .Out-of-distribution generalization. OOD generalization aims to learn domain-invariant representations that can effectively generalize to unseen domains, which is more challenging than classic domain adaptation problem [58, 59, 60, 61] , where the model has access to unlabeled data from the target domain. OOD generalization and domain generalization [62] focus on capturing semantic features that remain consistent across diverse domains, which can be categorized as reducing feature discrepancies across the source domains [63, 64, 31, 65, 66, 67] , ensemble and meta learning [68, 69, 70, 71, 72] , robust optimization [73, 74, 75, 76, 77] , augmentation [78, 79, 80, 81] , and disentanglement [82] . Distinct from prior literature about generalization, Scone [5] introduces a framework that leverages the wild data ubiquitous in the real world, aiming to build a robust classifier and a reliable OOD detector simultaneously. Following the same problem setting in [5] , we contribute novel theoretical insights into the understanding of both OOD generalization and detection. Spectral graph theory. Spectral graph theory is a classical research field [8, 83, 84, 85, 86] , concerning the study of graph partitioning through analyzing the eigenspace of the adjacency matrix. The spectral graph theory is also widely applied in machine learning [87, 88, 89, 90, 91, 92] . Recently, Haochen et al. [7] presented unsupervised spectral contrastive loss derived from the factorization of the graph's adjacency matrix. Shen et al. [12] provided a graph-theoretic analysis for unsupervised domain adaptation based on the assumption of unlabeled data entirely from P covariate out . Sun et al. [13] first introduced the label information and explored novel category discovery, considering unlabeled data covers P semantic out . All of the previous literature assumed unlabeled data has a homogeneous distribution. In contrast, our work focuses on the joint problem of OOD generalization and detection, tackling the challenge of unlabeled data characterized by a heterogeneous mixture distribution, which is a more general and complex scenario than previous works.Contrastive learning. Recent works on contrastive learning advance the development of deep neural networks with a huge empirical success [6, 93, 94, 95, 96, 97, 98, 99, 100, 101] . Simultaneously, many theoretical works establish the foundation for understanding representations learned by contrastive learning through linear probing evaluation [102, 103, 104, 105, 106, 107] . Haochen et al. [7, 108] , Sun et al. [13] extended the understanding and providing error analyses for different downstream tasks. Orthogonal to prior works, we provide a graph-theoretic framework tailored for the wild environment to understand both OOD generalization and detection. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Please refer to the Section 5.1 and Appendix E.1.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 In this paper, we present a graph-theoretic framework to jointly tackle both OOD generalization and detection problems. Based on the graph formulation, the data representations can be derived by factorizing the graph's adjacency matrix, allowing us to draw theoretical insight into both OOD generalization and detection performance. In particular, we analyze the closed-form solutions of linear probing error for OOD generalization, as well as separability quantifying OOD detection capability via the distance between the ID and semantic OOD data. Empirically, our framework demonstrates competitive performance against existing baselines, closely aligning with our theoretical insights. We anticipate that our theoretical framework and findings will inspire further research in unifying and understanding both OOD generalization and detection.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We report the standard deviation in our main experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that 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. 
broader impact: 
 In the rapidly evolving landscape of machine learning, addressing the dual challenges of OOD generalization and detection has become paramount for deploying robust and reliable models in real-world scenarios. Our work provides a novel spectral learning solution, which not only improves model performance but also ensures its reliability and safety in diverse, dynamic environments. The implications of our research extend beyond theoretical advancements, with potential applications in healthcare, autonomous systems, and finance. The ability to deploy models with superior OOD generalization and detection capabilities addresses a critical bottleneck in the adoption of machine learning technologies, fostering trust among end-users and stakeholders.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: We provide details regarding the hardware specifications in Appendix F.Guidelines:• 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). 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). 
limitations: 
 In our experimental setup, we focus on covariate shift as the primary form of shift in the out-ofdistribution (OOD) generalization problem, a topic extensively explored in the literature. However, it's important to acknowledge the existence of other types of distributional shifts (e.g., concept shift), which we defer for future investigation. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: Please refer to the Appendix 8.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: Our work poses no such risks.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: [Yes]Justification: Existing assets have been properly credited and mentioned.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. 
 
 Appendix: Proof. We can expand L mf (F, A) and obtainL mf (F, A) = x,x ′ ∈X w xx ′ √ w x w x ′ -f ⊤ x f x ′ 2 =const + x,x ′ ∈X -2w xx ′ f (x) ⊤ f (x ′ ) + w x w x ′ f (x) ⊤ f (x ′ ) 2 ,wheref x = √ w x f (x) is a re-scaled version of f (x). At a high level, we follow the proof in Haochen et al. [7] , while the specific form of loss varies with the different definitions of positive/negative pairs. The form of L(f ) is derived from plugging w xx ′ and w x .Recall that w xx ′ is defined byw xx ′ = η l i∈Y l E xl ∼P l i E x′ l ∼P l i T (x|x l )T (x ′ |x ′ l ) + η u E xu∼P T (x|x u )T (x ′ |x u ) ,and w x is given byw x = x ′ w xx ′ = η l i∈Y l E xl ∼P l i E x′ l ∼P l i T (x|x l ) x ′ T (x ′ |x ′ l ) + η u E xu∼P T (x|x u ) x ′ T (x ′ |x u ) = η l i∈Y l E xl ∼P l i T (x|x l ) + η u E xu∼P T (x|x u ).Plugging in w xx ′ we have,-2 x,x ′ ∈X w xx ′ f (x) ⊤ f (x ′ ) = -2 x,x + ∈X w xx + f (x) ⊤ f x + = -2η l i∈Y l E xl ∼P l i E x′ l ∼P l i x,x ′ ∈X T (x|x l )T (x ′ |x ′ l ) f (x) ⊤ f (x ′ ) -2η u E xu∼P x,x ′ T (x|x u )T (x ′ |x u ) f (x) ⊤ f (x ′ ) = -2η l i∈Y l E xl ∼P l i ,x ′ l ∼P l i , x∼T (•|x l ),x + ∼T (•|x ′ l ) f (x) ⊤ f x + -2η u E xu∼P, x∼T (•|xu),x + ∼T (•|xu) f (x) ⊤ f x + = -2η l L 1 (f ) -2η u L 2 (f ).Plugging w x and w x ′ we have, In our main analysis in Section 4, we consider semantic OOD to be from a different domain. Alternatively, instances of semantic OOD data can come from the same domain as covariate OOD data. In this section, we provide a complete picture by contrasting these two cases.x,x ′ ∈X w x w x ′ f (x) ⊤ f (x ′ ) 2 = x,x -∈X w x w x -f (x) ⊤ f x -2 = x,x ′ ∈X η l i∈Y l E xl ∼P l i T (x|x l ) + η u E xu∼P T (x|x u ) •   η l j∈Y l E x′ l ∼P l j T (x -|x ′ l ) + η u E x′ u ∼P T (x -|x ′ u )   f (x) ⊤ f x -2 =η 2 l x,x -∈X i∈Y l E xl ∼P l i T (x|x l ) j∈Y l E x′ l ∼P l j T (x -|x ′ l ) f (x) ⊤ f x -2 + 2η l η u x,x -∈X i∈Y l E xl ∼P l i T (x|x l )E xu∼P T (x -|x u ) f (x) ⊤ f x -2 + η 2 u x,x -∈X E xu∼P T (x|x u )E x′ u ∼P T (x -|x ′ u ) f (x) ⊤ f x -2 =η 2 l i∈Y l j∈Y l E xl ∼P l i ,x ′ l ∼P l j , x∼T (•|x l ),x -∼T (•|x ′ l ) f (x) ⊤ f x -2 + 2η l η u i∈Y l E xl ∼P l i ,xu∼P, x∼T (•|x l ),x -∼T (•|xu) f (x) ⊤ f x -2 + η 2 u E xu∼P,x ′ u ∼P, x∼T (•|xu),x -∼T (•|x ′ u ) f (x) ⊤ f x -2 =η 2 l L 3 (f ) + 2η l η u L 4 (f ) + η 2 u L 5 (f ).Setup. In Figure 5 , we illustrate two scenarios where the semantic OOD data has either a different or the same domain label as covariate OOD data.Other setups are the same as Sec. 4.3.Adjacency matrix. The adjacency matrix for scenario (a) has been derived in Eq. 11. For the alternative scenario (b) where semantic OOD shares the same domain as the covariate OOD, we can derive the analytic form of adjacency matrix A 1 .EQUATIONEQUATIONwhere C 1 is the normalization constant to ensure the summation of weights amounts to 1. Each row or column encodes connectivity associated with a specific sample, ordered by: angel sketch, tiger sketch, angel painting, tiger painting, and panda. We refer readers to the Appendix D.2 for the detailed derivation.Main analysis. Following the same assumption in Sec. 4.3, we are primarily interested in analyzing the difference of the representation space derived from A and A 1 and put analysis on the top-3 eigenvectorsV 1 ∈ R 5×3 .Theorem B.1. Denote α ′ = α ρ and β ′ = β ρ and assume η u = 5, η l = 1, we have:EQUATION)where a(λ)= √ 2(1-6β ′ -λ) 8β ′ , b(λ) = 4β ′ -1+λ 4β ′ , c(λ) = √ 2(1-3α ′ -6β ′ -λ) 3α ′. R is a diagonal matrix that normalizes the eigenvectors to unit norm and λ 2 , λ 3 are the 2nd and 3rd highest eigenvalues.Interpretation. When semantic OOD shares the same domain as covariate OOD, the OOD generalization error E(f 1 ) can be reduced to 0 as long as α and β are positive. This generalization ability shows that semantic OOD and covariate OOD sharing the same domain could benefit OOD generalization. We empirically verify our theory in Section E.4.Theorem B.2. Denote α ′ = α ρ and β ′ = β ρ and assume η u = 5, η l = 1, we have: S(f ) -S(f 1 ) > 0 , if α ′ , β ′ ∈ black area inCompared to spectral contrastive loss proposed by Haochen et al. [7] , we utilize ID labels in the pre-training. In this section, we analyze the impacts of ID labels on the OOD generalization and detection performance.Following the same assumption in Sec. 4.3, we are primarily interested in analyzing the difference of the representation space derived from A and A (u) and put analysis on the top-3 eigenvectors V (u) ∈ R 5×3 . Detailed derivation can be found in the Appendix D.3.Theorem C.1. Assume η u = 5, η l = 1, we have:EQUATION)Interpretation. By comparing the eigenvectors V in the supervised case (Theorem 4.1) and the eigenvectors V (u) in the self-supervised case, we find that adding ID label information transforms the performance condition from α = β to 9 8 α = β. In particular, the discussion can be divided into two cases: (1) α > β. (2) α < β. In the first case when the connection between the class is stronger than the domain, the model could learn a perfect ID classifier based on features in the first two rows in V (u) and effectively generalize to the covariate-shifted domain (the third and fourth row in V (u) ), achieving perfect OOD generalization with E(f (u) ) = 0. In the second case when the connection between the domain is stronger than the connection between the class, the embeddings of covariate-shifted OOD data are identical, resulting in high OOD generalization error.Theorem C.2. Assume η u = 5, η l = 1, we have:EQUATION)Interpretation. After incorporating ID label information, the separability between ID and semantic OOD in the learned embedding space increases as long as α and β are positive. This suggests that ID label information indeed helps OOD detection. We empirically verify our theory in Section E.4.D.1 Details for Figure 5 (a)Augmentation Transformation Probability. Recall the augmentation transformation probability, which encodes the probability of augmenting an original image x to the augmented view x:T (x | x) =      ρ if y(x) = y(x), d(x) = d(x); α if y(x) = y(x), d(x) ̸ = d(x); β if y(x) ̸ = y(x), d(x) = d(x); γ if y(x) ̸ = y(x), d(x) ̸ = d(x).Thus, the augmentation matrix T of the toy example shown in Figure 5 (a) can be given by:T =      ρ β α γ γ β ρ γ α γ α γ ρ β γ γ α β ρ γ γ γ γ γ ρ     Each row or column encodes augmentation connectivity associated with a specific sample, ordered by: angel sketch, tiger sketch, angel painting, tiger painting, and panda.Details for A (u) and A (l) . Recall that the self-supervised connectivity is defined in Eq. 1. Since we have a 5-nodes graph, A (u) would be 1 5 T T ⊤ . If we assume η u = 5, we can derive the closed-form self-supervised adjacency matrix:η u A (u) =   ρ 2 + β 2 + α 2 + 2γ 2 2ρβ + γ 2 + 2γα 2ρα + γ 2 + 2γβ 2αβ + γ 2 + 2γρ γ(γ + α + β + 2ρ) 2ρβ + γ 2 + 2γα ρ 2 + β 2 + α 2 + 2γ 2 2αβ + γ 2 + 2γρ 2ρα + γ 2 + 2γβ γ(γ + α + β + 2ρ) 2ρα + γ 2 + 2γβ 2αβ + γ 2 + 2γρ ρ 2 + β 2 + α 2 + 2γ 2 2ρβ + γ 2 + 2γα γ(γ + α + β + 2ρ) 2αβ + γ 2 + 2γρ 2ρα + γ 2 + 2γβ 2ρβ + γ 2 + 2γα ρ 2 + β 2 + α 2 + 2γ 2 γ(γ + α + β + 2ρ) γ(γ + α + β + 2ρ) γ(γ + α + β + 2ρ) γ(γ + α + β + 2ρ) γ(γ + α + β + 2ρ) ρ 2 + 4γ 2  Then, according to the supervised connectivity defined in Eq. 2, we only compute ID-labeled data.Since we have two known classes and each class contains one sample, A (l) = T :,1 T ⊤ :,1 + T :,2 T ⊤ :,2 . Then if we let η l = 1, we can have the closed-form supervised adjacency matrix:η l A (l) =      ρ 2 + β 2 2ρβ ρα + γβ αβ + γρ γ(ρ + β) 2ρβ ρ 2 + β 2 αβ + γρ ρα + γβ γ(ρ + β) ρα + γβ αβ + γρ α 2 + γ 2 2γα γ(α + γ) αβ + γρ ρα + γβ 2γα α 2 + γ 2 γ(α + γ) γ(ρ + β) γ(ρ + β) γ(α + γ) γ(α + γ) 2γ 2     Details of eigenvectors V . We assume ρ ≫ max(α, β) ≥ min(α, β) ≫ γ ≥ 0, and denoteα ′ = α ρ , β ′ = β ρ .A can be approximately given by:A ≈ A = 1 C      2 4β ′ 3α ′ 0 0 4β ′ 2 0 3α ′ 0 3α ′ 0 1 2β ′ 0 0 3α ′ 2β ′ 1 0 0 0 0 1      ,where C is the normalization term and equals to 7 + 12β ′ + 12α ′ . The squares of the minimal term (e.g.,αβ ρ 2 , α 2 ρ 2 , β 2 ρ 2 , γ ρ = γ α • α ρ , αγ ρ 2 , etc) are approximated to 0. D = 1 C diag[2 + 4β ′ + 3α ′ , 2 + 4β ′ + 3α ′ , 1 + 2β ′ + 3α ′ , 1 + 2β ′ + 3α ′ , 1] D -1 2 = Cdiag[ 1 √ 2 (1 -β ′ - 3 4 α ′ ), 1 √ 2 (1 -β ′ - 3 4 α ′ ), 1 -β ′ - 3 2 α ′ , 1 -β ′ - 3 2 α ′ , 1] D -1 2 AD -1 2 ≈ D -1 2 A D -1 2 =      1 -2β ′ -3 2 α ′ 2β ′ 3 √ 2 α ′ 0 0 2β ′ 1 -2β ′ -3 2 α ′ 0 3 √ 2 α ′ 0 3 √ 2 α ′ 0 1 -2β ′ -3α ′ 2β ′ 0 0 3 √ 2 α ′ 2β ′ 1 -2β ′ -3α ′ 0 0 0 0 0 1     Let λ 1,...,5 and v 1,...,5 be the eigenvalues and their corresponding eigenvectors of D -1 2 AD -1 2 . Then the concrete form of λ 1,...,5 and v 1,...,5 can be approximately given by:v 1 = 1 √ 6 [ √ 2, √ 2, 1, 1, 0] ⊤ λ 1 = 1 v 2 = [0, 0, 0, 0, 1] ⊤ λ 2 = 1 v 3 = 1 √ 6 [- √ 2, √ 2, -1, 1, 0] ⊤ λ 3 = 1 -4β ′ v 4 = 1 √ 6 [-1, -1, √ 2, √ 2, 0] ⊤ λ 4 = 1 -9 2 α ′ v 5 = 1 √ 6 [1, -1, - √ 2, √ 2, 0] ⊤ λ 5 = 1 -4β ′ -9 2 α ′Since α ′ , β ′ > 0, we can always have λ 1 = λ 2 > λ 3 > λ 5 and λ 1 = λ 2 > λ 4 > λ 5 . Then, we let k = 3 and V ∈ R 5×3 is given by:V =                      1 √ 3 1 √ 3 1 √ 6 1 √ 6 0 0 0 0 0 1 -1 √ 3 1 √ 3 -1 √ 6 1 √ 6 0   ⊤ , if 9 8 α ′ > β ′ ;   1 √ 3 1 √ 3 1 √ 6 1 √ 6 0 0 0 0 0 1 -1 √ 6 -1 √ 6 1 √ 3 1 √ 3 0   ⊤ , if 9 8 α ′ < β ′ .Details of linear probing and separability evaluation. Recall that the closed-form embeddingZ = [D] -1 2 V k √ Σ k .Based on the derivation above, closed-form features for ID sample Z in ∈ R 2×3 can be approximately given by:Z in =            (1-β ′ -0.75α ′ ) √ C √ 6 1 0 - √ 1 -4β ′ 1 0 √ 1 -4β ′ , if 9 8 α ′ > β ′ . (1-β ′ -0.75α ′ ) √ C 2 3   √ 2 0 -1 -9 2 α ′ √ 2 0 -1 -9 2 α ′   , if 9 8 α ′ < β ′ .Based on the least error method, we can derive the weights of the linear classifierM ∈ R 3×2 , M = ( Z ⊤ in Z in ) † Z T in y inwhere (•) † is the Moore-Penrose inverse and y in is the one-hot encoded ground truth class labels. So when 9 8 α > β, the predicted probability y covariate can be given by:y covariate out = Ẑcovariate out • M = (1 -β ′ -3 2 α ′ ) 1 -β ′ -3 4 α ′ • Iwhere I ∈ R 2×2 is an identity matrix. We notice that when 9 8 α < β, the closed-form features for ID samples are identical, indicating the impossibility of learning a clear boundary to classify classes angel and tiger. Eventually, we can derive the linear probing error:E(f ) =    0 , if 9 8 α > β; 2 , if 9 8 α < β.The separability between ID data and semantic OOD data can be computed based on the closed-form embeddings Z in and Z semantic out : Z semantic out = C • [0, 1, 0] S(f ) = (7 + 12β ′ + 12α ′ )( 1-2β ′ 3 (1 -β ′ -3 4 α ′ ) 2 + 1) , if 9 8 α > β; (7 + 12β ′ + 12α ′ )( 2-3α ′ 8 (1 -β ′ -3 4 α ′ ) 2 + 1) , if 9 8 α < β.T =      ρ β α γ γ β ρ γ α γ α γ ρ β β γ α β ρ β γ γ β β ρ     Each row or column represents augmentation connectivity of a specific sample, ordered by: angel sketch, tiger sketch, angel painting, tiger painting, and panda.A (u) 1 and A (l)1 . After the assumption η u = 5, η l = 1, we can haveη u A (u) 1 = T T ⊤ : η u A (u) 1 =   ρ 2 + β 2 + α 2 + 2γ 2 2ρβ + γ 2 + 2γα 2ρα + 3γβ 2αβ + γβ + 2γρ αβ + 2γ(β + ρ) 2ρβ + γ 2 + 2γα ρ 2 + β 2 + α 2 + 2γ 2 2αβ + γβ + 2γρ 2ρα + 3γβ αβ + 2γ(β + ρ) 2ρα + 3γβ 2αβ + γβ + 2γρ ρ 2 + 2β 2 + α 2 + γ 2 2ρβ + β 2 + 2γα 2ρβ + β 2 + γ 2 + γα 2αβ + γβ + 2γρ 2αρ + 3γβ 2ρβ + β 2 + 2γα ρ 2 + 2β 2 + α 2 + γ 2 2ρβ + β 2 + γ 2 + γα αβ + 2γ(β + ρ) αβ + 2γ(β + ρ) 2ρβ + β 2 + γ 2 + γα 2ρβ + β 2 + γ 2 + γα ρ 2 + 2β 2 + 2γ 2  And the supervised adjacency matrix A (l) 1 = T :,1 T ⊤ :,1 + T :,2 T ⊤ :,2 can be given by:η l A (l) 1 =      ρ 2 + β 2 2ρβ ρα + γβ αβ + γρ γ(β + ρ) 2ρβ ρ 2 + β 2 αβ + γρ ρα + γβ γ(β + ρ) ρα + γβ αβ + γρ α 2 + γ 2 2γα γ(γ + α) αβ + γρ ρα + γβ 2γα α 2 + γ 2 γ(γ + α) γ(β + ρ) γ(β + ρ) γ(γ + α) γ(γ + α) 2γ 2      Details for V 1 .Following the same assumption, the adjacency matrix can be approximately given by:A 1 ≈ A 1 = 1 C 1      2 4β ′ 3α ′ 0 0 4β ′ 2 0 3α ′ 0 3α ′ 0 1 2β ′ 2β ′ 0 3α ′ 2β ′ 1 2β ′ 0 0 2β ′ 2β ′ 1      D 1 = 1 C 1 • diag[2 + 4β ′ + 3α ′ , 2 + 4β ′ + 3α ′ , 1 + 4β ′ + 3α ′ , 1 + 4β ′ + 3α ′ , 1 + 4β ′ ] D -1 2 1 = C 1 • diag[ 1 √ 2 (1 -β ′ - 3 4 α ′ ), 1 √ 2 (1 -β ′ - 3 4 α ′ ), 1 -2β ′ - 3 2 α ′ , 1 -2β ′ - 3 2 α ′ , 1 -2β ′ ] D -1 2 1 A 1 D -1 2 1 ≈ D -1 2 1 A 1 D -1 2 1 =    1 -2β ′ -3 2 α ′ 2β ′ 3 √ 2 α ′ 0 0 2β ′ 1 -2β ′ -3 2 α ′ 0 3 √ 2 α ′ 0 3 √ 2 α ′ 0 1 -4β ′ -3α ′ 2β ′ 2β ′ 0 3 √ 2 α ′ 2β ′ 1 -4β ′ -3α ′ 2β ′ 0 0 2β ′ 2β ′ 1 -4β ′   where C 1 is the normalization term and C 1 = 7 + 20β ′ + 12α ′ . After eigendecomposition, we can derive ordered eigenvalues and their corresponding eigenvectors:v 1 = 1 √ 7 [ √ 2, √ 2, 1, 1, 1] ⊤ λ 1 = 1 v 2 = 1 √ 2a( λ2) 2 +2b( λ2) 2 +1 [a( λ 2 ), a( λ 2 ), b( λ 2 ), b( λ 2 ), 1] ⊤ λ 2 = 1 -3b + √ 3 √ (27a 2 -40ab+48b 2 )-9a 4 v 3 = 1 √ 2c( λ3) 2 +2 [c( λ 3 ), -c( λ 3 ), -1, 1, 0] ⊤ λ 3 = 1 -5b + √ 81a 2 +24ab+16b 2 -9a 4 v 4 = 1 √ 2a( λ4) 2 +2b( λ4) 2 +1 [a( λ 4 ), a( λ 4 ), b( λ 4 ), b( λ 4 ), 1] ⊤ λ 4 = 1 -3b - √ 3 √ (27a 2 -40ab+48b 2 )+9a 4 v 5 = 1 √ 2c( λ5) 2 +2 [c( λ 5 ), -c( λ 5 ), -1, 1, 0] ⊤ , λ 5 = 1 -5b - √ 81a 2 +24ab+16b 2 +9a 4whereλ 1 > λ 2 > λ 3 > λ 4 > λ 5 and a(λ) = √ 2(1-6β ′ -λ) 8β ′ , b(λ) = 4β ′ -1+λ 4β ′ , c(λ) = √ 2(1-3α ′ -6β ′ -λ) 3α ′. We can get closed-form eigenvectors:V 1 =   √ 2 √ 2 1 1 1 a( λ2) a( λ2) b( λ2) b( λ2) 1 c( λ3) -c( λ3) -1 1 0   ⊤ • diag[ 1 √ 7 , 1 2a( λ 2 ) 2 + 2b( λ 2 ) 2 + 1 , 1 2c( λ 3 ) 2 + 2 ]Details for linear probing and separability evaluation. Following the same derivation, we can derive closed-form embedding for ID samplesZ in = D -1 2in V in Σ in and the linear layer weightsM = ( Z ⊤ in Z in ) † Z T in y in .Eventually, we can derive the approximately predicted probability ŷcovariate out :ŷcovariate out = a 1 + b 1 a 1 -b 1 a 1 -b 1 a 1 + b 1where a 1 , b 1 ∈ R and b 1 > 0. This indicates that linear probing error E(f 1 ) = 0 as long as α and β are positive.Having obtained closed-form representation Z in and Z semantic out , we can compute separability S(f 1 ) and then prove: Z in = (1 -β ′ -3 4 α ′ ) C 1 √ 2    √ 2 √ 7 a( λ2) √ λ2 √ 2a( λ2) 2 +2b( λ2) 2 +1 -c( λ3) √ λ3 √ 2c( λ3) 2 +2 √ 2 √ 7 a( λ2) √ λ2 √ 2a( λ2) 2 +2b( λ2) 2 +1 c( λ3) √ λ3 √ 2c( λ3) 2 +2    Z semantic out = (1 -2β ′ ) C 1 [ 1 √ 7 , λ 2 2a( λ 2 ) 2 + 2b( λ 2 ) 2 + 1 , 0] S(f ) -S(f 1 ) > 0 , if α ′ , β ′ ∈ black area inOur analysis for the self-supervised case is based on Figure 5 (a), the adjacency matrix is exactly the same as Eq. 10. After approximation, we can derive:A (u) ≈ A (u) = 1 C (u)      1 2β ′ 2α ′ 0 0 2β ′ 1 0 2α ′ 0 2α ′ 0 1 2β ′ 0 0 2α ′ 2β ′ 1 0 0 0 0 0 1      D (u) -1 2 = 5 + 8β ′ + 8α ′ • diag[1 -β ′ -α ′ , 1 -β ′ -α ′ , 1 -β ′ -α ′ , 1 -β ′ -α ′ , 1] D (u) -1 2 A (u) D (u) -1 2 =      1 -2β ′ -2α ′ 2β ′ 2α ′ 0 0 2β ′ 1 -2β ′ -2α ′ 0 2α ′ 0 2α ′ 0 1 -2β ′ -2α ′ 2β ′ 0 0 2α ′ 2β ′ 1 -2β ′ -2α ′ 0 0 0 0 0 1      v 1 = 1 2 [1, 1, 1, 1, 0] ⊤ λ 1 = 1 v 2 = [0, 0, 0, 0, 1] ⊤ λ 2 = 1 v 3 = 1 2 [-1, 1, -1, 1, 0] ⊤ λ 3 = 1 -4β ′ v 4 = 1 2 [-1, -1, 1, 1, 0] ⊤ λ 4 = 1 -4α ′ v 5 = 1 2 [1, -1, -1, 1, 0] ⊤ λ 5 = 1 -4α ′ -4β ′Following the same procedure presented above, we can prove Theorem C.1 and C.2.We provide a detailed description of the datasets used in this work below: CIFAR-10 [14] contains 60, 000 color images with 10 classes. The training set has 50, 000 images and the test set has 10, 000 images.ImageNet-100 consists of a subset of 100 categories from ImageNet-1K [109] . This dataset contains the following classes: n01498041, n01514859, n01582220, n01608432, n01616318,, n04371774, n04404412, n04465501, n04485082, n04507155, n04536866, n04579432, n04606251, n07714990, n07745940.CIFAR-10-C is generated based on Hendrycks et al. [15] , applying different corruptions on CIFAR-10 including gaussian noise, defocus blur, glass blur, impulse noise, shot noise, snow, and zoom blur.ImageNet-100-C is generated with Gaussian noise added to ImageNet-100 dataset [109] .SVHN [16] is a real-world image dataset obtained from house numbers in Google Street View images. This dataset 73, 257 samples for training, and 26, 032 samples for testing with 10 classes.Places365 [18] contains scene photographs and diverse types of environments encountered in the world. The scene semantic categories consist of three macro-classes: Indoor, Nature, and Urban.LSUN-C [17] and LSUN-R [17] are large-scale image datasets that are annotated using deep learning with humans in the loop. LSUN-C is a cropped version of LSUN and LSUN-R is a resized version of the LSUN dataset.Textures [19] refers to the Describable Textures Dataset, which contains a large dataset of visual attributes including patterns and textures. The subset we used has no overlap categories with the CIFAR dataset [14] .iNaturalist [110] is a challenging real-world dataset with iNaturalist species, captured in a wide variety of situations. It has 13 super-categories and 5,089 sub-categories. We use the subset from Huang et al. [111] that contains 110 plant classes that no category overlaps with IMAGENET-1K [109] .Office-Home [20] In this section, we present results on the large-scale dataset ImageNet-100 to further demonstrate our empirical competitive performance. We employ ImageNet-100 as P in , ImageNet-100-C as P covariate out , and iNaturalist [110] as P semantic out . Similar to our CIFAR experiment, we divide the ImageNet-100 training set into 50% labeled as ID and 50% unlabeled. Then we mix unlabeled ImageNet-100, ImageNet-100-C, and iNaturalist to generate the wild dataset. We include results from Scone [5] and set π c = 0.5, π s = 0.1 for consistency. We pre-train the backbone ResNet-34 [112] with spectral contrastive loss and then use ID data to fine-tune the model. We set the pre-training epoch as 100, batch size as 512, and learning rate as 0.01. For fine-tuning, we set the learning rate to 0.01, batch size to 128, and train for 10 epochs. Empirical results in Table 4 indicate that our method effectively balances OOD generalization and detection while achieving strong performance in both aspects. While Wood [37] displays strong OOD detection performance, the OOD generation performance (44.46%) is significantly worse than ours (72.58%). More detailed implementation can be found in Appendix F. In this section, we present empirical results on the Office-Home [20] , a dataset comprising 65 object classes distributed across 4 different domains: Artistic (Ar), Clipart (Cl), Product (Pr), and Real-World (Rw). Following OSBP [113] , we separate 65 object classes into the first 25 classes in alphabetic order as ID classes and the remainder of classes as semantic OOD classes. Subsequently, we construct the ID data from one domain (e.g., Ar) across 25 classes, and the covariate OOD from another domain (e.g., Cl) to carry out the OOD generalization task (e.g., Ar → Cl). The semantic OOD data are from the remainder of classes, in the same domain as covariate OOD data. We consider the following wild data, where P wild = π c P covariate out + π s P semantic out and π c + π s = 1. This setting is also known as open-set domain adaptation [114] , which can be viewed as a special case of ours.For a fair empirical comparison, we include results from Anna [115] , containing comprehensive baselines like STA [116] , OSBP [113] , DAOD [117] , OSLPP [118] , ROS [119] , and Anna [115] .Following previous literature, we use OOD Acc. to denote the average class accuracy over known classes only in this section. We employ ResNet-50 [112] as the default backbone. As shown in Table 5 , our approach strikes a balance between OOD generalization and detection, even outperforming the state-of-the-art method Anna in terms of FPR by 11.3% on average. This demonstrates the effectiveness of our method in handling the complex OOD scenarios present in the Office-Home dataset. More detailed implementation can be found in Appendix F. Better adaptation to the heterogeneous distribution. As presented in Table 6 , the results underscore our competitive performance compared to state-of-the-art spectral learning approaches within their respective domains. For a fair comparison, SCL [7, 12] is purely unsupervised pre-trained on D l ∪ D u , where D l represents the labeled set, and D u denotes the unlabeled wild set. NSCL [13] undergoes unsupervised pre-training on D u and supervised pre-training on D l .The improvement over SCL [7, 12] in both OOD generalization and detection illustrates the tremendous help given by labeled information, which also perfectly aligns with our theoretical insights in Appendx C. The comparison with NSCL [13] indicates that unsupervised pre-training on D l ∪ D u can contribute to the adaptation to the heterogeneous wild distribution, thereby establishing the generality of our method. Training settings. We conduct all the experiments in Pytorch, using NVIDIA GeForce RTX 2080Ti. We use SGD optimizer with weight decay 5e-4 and momentum 0.9 for all the experiments. In CIFAR-10 experiments, we pre-train Wide ResNet with spectral contrastive loss for 1000 epochs. The learning rate (lr) is 0.030, batch size (bs) is 512. Then we use ID-labeled data to fine-tune for 20 epochs with lr 0.005 and bs 512. In ImageNet-100 experiments, we train ImageNet pre-trained ResNet-34 for 100 epochs. The lr is 0.01, bs is 512. Then we fine-tune for 10 epochs with lr 0.01 and bs 128. In Office-Home experiments, we use ImageNet pre-trained ResNet-50 with lr 0.001 and bs 64. We use the same data augmentation strategies as SimSiam [98] . We set K in KNN as 50 in CIFAR-10 experiments and 100 in ImageNet-100 experiments, which is consistent with Sun et al. [23] . And η u is selected within {1.00, 2.00} and η l is within {0.02, 0.10, 0.50, 1.00}. In Office-Home experiments, we set K as 5, η u as 3, and η l within {0.01, 0.05}. η u , η l are summarized in Table 8 . • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 


Decision: All four reviewers expressed positive support to this work, which is considered to be theoretically sound and useful. Thus an accept is recommended.

Reviews: review: paper_summary: paper_summary: This paper proposes a unified framework for OOD detection and generalization, which first constructs a graph that includes both labeled and unlabeled data and derives data representations by factorizing the graph’s adjacency matrix. These representations help quantify OOD generalization and detection performance. The framework's effectiveness is demonstrated through experiments on CIFAR-10, ImageNet, and Office-Home datasets.
strength_weakness: strength_weakness: 1. The effectiveness of the methods is limited by numerous hyperparameter selections, preventing its practical application in real-world scenarios.

2. The process for determining the distribution of augmentation $\tau$, which is the key points for constructing the graph, is not clear. he appropriateness and effectiveness of the formulation in equation (9) for various datasets and other cases remain uncertain.

3. The theoretical guarantees discussed in the paper are not clearly defined, making it unclear what the specific goals of these guarantees are.
questions: questions: Please refer to the weaknesses.
limitations: limitations: N/A
paper_summary: paper_summary: The paper introduces a novel graph-theoretic framework to tackle both out-of-distribution (OOD) generalization and detection. By representing data points as vertices in a graph and using the adjacency matrix decomposition, the authors derive data representations that allow for quantifiable error rates in OOD tasks. Theoretical insights are provided through formal error bounds, and empirical results demonstrate the framework's effectiveness and robustness, showcasing significant improvements over existing methods. This framework is practical and scalable, leveraging modern neural networks for efficient optimization on real-world data.
strength_weakness: strength_weakness: 1.The paper builds on the baseline Scone for its experiments. Regarding Definition 2.2, it is unclear why four metrics are used in the experiments while only three are introduced here. Is it because Scone only introduced three? Please provide a reasonable explanation.

2.The field of Graph Neural Networks (GNNs) has mature tasks for OOD generalization and OOD detection. Why did the authors choose to use graphs to address tasks in computer vision instead of leveraging these existing GNN-specific tasks?

3.While the authors provide extensive theoretical insights and proofs, the experimental section seems insufficient. The main experiments are largely based on Scone, and the additional experiments only compare performance. If this work is pioneering, this might be acceptable, but given related prior work, the authors should not limit themselves to performance comparisons. They should demonstrate the advantages of their approach in other dimensions, such as time and space efficiency, to prove its superiority over Scone.

4.Figure 4 only visualizes the method proposed in this paper, lacking comparison with other methods.

5.The theoretical analysis in this paper is based on certain assumptions that may not hold in all practical situations, potentially limiting the applicability of the results. These assumptions include the accuracy and representativeness of the graph representations and spectral decompositions used to quantify OOD generalization and detection errors, as well as the ideal conditions for spectral decomposition and the relationships between ID and OOD data. Additionally, the analysis assumes specific distributions of wild data, linear separability of OOD data in the learned representation space, and the particular structure of the graph used in the analysis.
questions: questions: 1.The theoretical analysis relies on several assumptions, such as the accuracy of graph representations and spectral decompositions, and the linear separability of OOD data. Can the authors provide more details on these assumptions and discuss the potential impact if these assumptions do not hold in practical scenarios?

2.The paper uses graphs to handle tasks in computer vision, despite the existence of well-established OOD generalization and detection tasks within the domain of Graph Neural Networks. What motivated the authors to choose this approach? Are there specific advantages that this graph-theoretic framework provides for computer vision tasks?
limitations: limitations: None
paper_summary: paper_summary: The paper proposes a graph-theoretic framework to address out-of-distribution (OOD) generalization and detection. The framework models the data using a graph, where vertices represent data points and edges indicate similarities based on supervised and self-supervised signals. By leveraging spectral decomposition of the graph's adjacency matrix, the authors derive provable errors for OOD generalization and detection performance. Empirical results demonstrate that the effectiveness of the proposed approach.
strength_weakness: strength_weakness: - despite the case studies for the proposed frameworks/analysis, the proposed method in its current form seems to be impractical for large-scale problem

- the effectiveness of the analysis and proposed method heavily rely on how the edges are/should be constructed in the graph, which itself is a challenging and open question

- there are some connections between the analysis and claims that are not very strong (see questions below for more details)

- there are some minor formatting/presentation issues in line 192-195
questions: questions: 1. what are the advantages of doing OOD generalization and detection at the same time compared to have different method for each?

2. what are the novel insight for OOD from this graph theoretic perspective?
limitations: limitations: N.A
paper_summary: paper_summary: This work proposes a framework to address OOD detection and generalization jointly for image data, using a graph representation, where edges are constructed by both self-supervised data transformation probability and supervised labels. An example is provided with theoretical analysis, to show the advantages and disadvantages of the proposed method.
strength_weakness: strength_weakness: 1. From the theoretical analysis (lines 200-216), it appears that the OOD generalization ability of this algorithm depends on the relationship between $\alpha$ and $\beta$. This may lead to failures in OOD generalization, while for OOD detection, the method is more effective.

2. As the data transformation is not learnable, $\alpha$ and $\beta$ seem to be fully determined by the data distribution. Hence, there is no guarantee for OOD generalization in some scenarios.

3. The experimental evaluation is consistent with the theoretical characterization, indicating that the model is less effective at OOD and ID classification compared with its OOD detection ability.

4. Although the authors present a theoretical analysis, which reflects the advantages and disadvantages of this approach, however, for the OOD generalization failure and limited ID classification performance, the author doesn't propose further refinement to handle this issue.
questions: questions: 1. Would more advanced data transformation in SSL enhances the OOD generalization ability?

2. What does it mean by heterogeneous distribution in line 266? It seems the major difference to previous methods is the usage of both unsupervised and supervised learning when building the graph.

3. For the FPR metric, why can the proposed algorithm perform so much better than the state-of-the-art OOD detection method? For example, 0.13 vs. 40.76 in ASH in Table 1. Is there any explanation for this significant uplift?
limitations: limitations: N/A

Comments: title: Reply
comment: Thank you for taking the time to read our response and for increasing the score! We are glad to hear that our rebuttal addressed your concerns.
Thanks for addressing my concerns. I would like to raise my score.
Dear reviewer DU8N,

We wanted to touch base with you as the deadline for the author-reviewer discussion phase is approaching soon. We trust you've had the opportunity to review our rebuttal, and we would be more than happy to address any further concerns you have.

Thank you once again for your time and dedication to this review process. We look forward to your response and to furthering the dialogue on our manuscript.

Best,

Authors
Thank you for taking the time to read our response and for increasing the score! We are glad to hear that our rebuttal addressed your concerns.
Thank you for taking the time to read our response! We are glad to hear that our rebuttal addressed your concerns.
Thank you for addressing the concerns I raised in my previous review. I have decided to increase my score for this submission.
Thanks for the authors' reply. I will keep positive score.
Thank you for taking the time to read our response! We are glad to hear that our rebuttal addressed your concerns.
Thank you for the response. I do not have further questions.