Bridging OOD Detection and Generalization: A Graph-Theoretic View
Authors: Han Wang
Yixuan Li
Venue: NeurIPS 2024 poster (2024)
Keywords: graph spectral
distribution shift
Primary area: machine_vision

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.

Bridging OOD Detection and Generalization: A Graph-Theoree View
Han Wang"
Yixuan Li
Department of Electrical and Computer Engineering University of Illinois Urbana- Champ-hn hanw1 @eeillinois.ert
Department of Computer Sciences University of Wisconsin-Madisee sharonl @cs wisc .dd
Abstract
In the context of modern machine learning, models deployed in real-world scenar- ios often encounter diverse data shifts like covariate and semantic shifts, leading challenges in both out-of-distribution (OOD) generalization and detection. Despite considerable attention 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 through the factorization of the graph's 's adjacency matrix, enabling us derive provable eиrоr quantifying OOD generalization and detection performance. Empir- ical results showcase competitive performance comparison to existing methods, thereby validating theoretical underpinnings. Code is publicly available at -ood.
obtained
https:/ //gi thub. cww aedeepleennigg wwww
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 birds-ah essential capability known 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 remantic-shified OOD samples and abstain from making incorrect predictions, underscoring the significance of OOD detection [3, 4]. Thus, for model 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 al. [5] introduced 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 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 the heterogeneity of the wild data distribution-tte 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 graph-theorets 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 combination of supervised
Work done while visiting UW-Madde WW-Madison.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Forest bird (Covorute (0D)
min
(Fr(F,
| A FF FFFFF
Dog Gemantic OOD)
PER
Optimal Solution (Fekars- Young-Mirsky Theosonn)
SVD Decomppstion
Choose comeen Scaling
Horg
A
Scabid
Graph formulation
Graph factorization
Illustration of our graph- theoretic framework for joint out distribbbttni generalization and detection. Left: Graph formulation containing three types of data in the wild: ID (e.g.. seabird), covariate OOD (e.g.. bird in the forest), and semantic OOD (e.g., dog). Right: Graph factorization for obtaining the closed-form solution of the data representations, which are used derive OOD generalization and OOD detection
Figure I:
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 the graph (e.g.. Dovariate-shiftel OOD data embedded closely the ID data, whereas semantic-shifted OOD data is distinguishable from ID data). Importantly, this graph serves as foundation for understanding the impact of wild unlabeled data both OOD generalization and detection, enabling 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).
Beyond theoretical analysis, our graph- graph-theoretic framework can be used practically. In particular, the spectral decomposition be equivalently achieved by minimizing surrogate objective, which can be efficiently optimized end-to-end using modern neural networks. Thus, our approach enjoys theoretical guarantees while being applicable 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 the state-of-the-arr method Scone [5], 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 graph-theorete framework for understanding both OOD generalization and detection, formalizing by spectral decomposition of the graph containing ID, covariate- shift OOD data, and semantic-shift OOD data.
2. We provide theoretical insights by quantifying OOD generalization and detection perfor- mance through provable error, based on the closed-fon 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.
2 Problem Setup
We consider the empirical training set D; U D., as a union of labeled and unlabeled data. The labeled set D; {ēt, 91 ) where y/ belongs known class space Vi. Let F, 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. = { ) consists ID, covariate OOD, and semantic OOD data, where each sample E; is drawn from mixture distribution defined below.
Definition 2.1. The marginal distribution of the wild data is defined as:
IP wild
Th TP + T. T Premariate + T. Tasemmntic
where Tes ns. Tr. + W. [0, 1]. Pin, peovariate and Dssemantic represent the marginal distributions of ID, eovariat-sshifedd OOD, and semantic-shifted OOD data respectively.

---

Learning goal. We aim to learn jointly an OOD detector go: X' + {IN, OUT} and multi-class classifier fo. by leveraging labeled ID data Dj and unlabeled wild data P.. Let (f)(
argmax, p()) (æ), where f( (i) denotes the y-th element of (z), corresponding to label We notate and fo with parameters to indicate that these functions share neural network parameters. In our model evaluation,
interested in three metrics:
Definition 2.2. We define ID generalization accuracy (ID-Acc), OOD generalization accuracy (O0D-Acc), and OOD detection error as follows:
t ID-Acc(fo) == (Z, (1 (1)(f(())) - v}),
t OOD-Acc((f)) == (2))) Parriis (1(((f((z) -)),
4 FPR(go) == P. (1 (g) IN)),
where } represents the indicator function, and the arrows indicate the directionality of improve- ment (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
3.1 Graph Formulation
We start by formally defining the graph and adjacency matrix. We use denote the set of all natural data (raw inputs without augmentation). Given an Σ, we use ((x (T) to denote the probability of x being augmented from and T(- ( denote the distribution of its augmentation. For instance, when E represents an image, T(- can be the distribution of common augmentations [6] such as Gaussian blur, color distortion, and random cropping. We define X' as 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 Xj and unlabeled wild data Xx,, with cardinality | 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(() by treating all points X' entirely unlabeled, and (2) supervised connectivity w(') by incorporating labeled information from X; to the graph. We define the connectivity formally below.
Definition 3.1 -Self-supervised connectivity). For any two augmented data x. E X, whth denotes the marginal probability of generating the positive pair [7]:
A W 2x'
(a' [z),
(1)
where x and x'' are augmented from the same image Tt ~ IP, and TP is the marginal distribution of both labeled and unlabeled data. larger (u) 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 and x' are augmented from two labeled samples and oi with the same known class E 3/. The total edge connectivity can be formulated as below:
Definition 3.2 (Total edge connectivity). Considering both self seff-supe and supervised connectiv- ities, the overall similarity for any pair of data (x, (t,x") is formulated as:
(w) Vhe azz + q now where w Zz
(1)
EENNE BeG T( (1)
Wix!
(2)
IE)!
where Pt, is the distribution of labeled samples with class label E Vd and the coefficients Tu m modulate the relative importance between the two terms.
Adjacency matrix. Having established the notion of connectivity, we can define the adjacency matrix E N with entries Azg' = wez', The adjacency matrix can be decomposed into the summation of self-supervised adjacency matrix (w) and supervised adjacency matrix A();
A = A + (1)
(3)
3

---

As standard technique in graph theory [8], we use the normalized adjacency matrix:
A D AD-
(4)
where D E RRN is a diagonal matrix with D22 We -x e'ex Wax', indicating the total edge weights connected to vertex x. The normalized adjacency matrix defines the probability of a and x' being considered as the positive pair. The normalized adjacency matrix allows us perform spectral decomposition as we show next.
3.2 Learning Representations Based on Graph Spectral
In this section, perform spectral decomposition spectral clustering [9] 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 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, well the generalizability to covariate-shiffe OOD data (more in Section 4).
k-dimensional
Towards this end, we consider the following optimization, which performs low-rank matrix approxi- mation on the adjacency matrix:
Lunf (F, A) - A- FFT FERNXA
min
(5)
F
where || || denotes the matrix Frobenious norm. According to the Fokart-Young-Misss theo- rem [10]. the minimizer of this loss function is F& Nx such that F&F contains the top-k components of A'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 neural network:
C(S) A 27) - 2nn2a(1)+++ + (l) CL(m + Ls(s),
(6)
where
Li(f)
Σ
(=+))
(2(l))
EE
[f(x]
(x+)),
Pr
2 P.
iE
a~T (
Ca(f) = Σ
{
Ri 2/-Fey
iJED!
C4(f) Σ iED INT(H (T(
E R
[ co())=
a~T((1)). T(
Importantly, this contrastive loss allows drawing a theoretical equivalence between learned repre- sentations 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 fI of F as scaled version of learned feature embedding
RR with fa --===w-fff (x) Then minimizing the loss function Cmy(F', A) in Equation 5 is equivalent to minimizing the surrogate loss in Equation 6. Full proof is in Appendix
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.. novariate-shiffer 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 L1 and L2 contribute to pulling the embeddings of positive pairs closer, while L3, La and Ls push apart the embeddings 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 self-supervised learning [7], unsupervised domain adaptation [12], novel category discov- cry [13], open-world semi-supervised learning [1 I] etc. These works share the underlying loss form by pulling together positive pairs and pushing away negative pairs. Despite the shared loss formu- lation, 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 the prior works. Accordingly, we derive novel theoretical analysis for our setup and present empirical verification uniquely tailored to our problem focus, which we present next.
4 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.
4.1 Analytic Form of Learned Representations
To obtain the representations, loss defined in Equation 6. Minimizing the loss yields representation Z E RRNx where each row vector = f(x:) According to Theorem 3.3, the closed-form solution for the representations is equivalent performing spectral decomposition of the adjacency matrix. Thus, we have Fx /DZ, where F2F 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& e N so we have F& V where Σg is a diagonal matrix of the top-k singular values of Á. By equalizing the forms of Fk. the closed-formed solution the learned feature space is given by Z [D] V&vE..
can train the neural network f X' + R* using the spectral
4.2 Analysis Target
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 linear classifier is denoted as M E R which is learned with ID data to minimize the error. The class prediction for an input given by h(#;; f, M) = argmax sey, (f(z) M); The linear probing error measures the misclassification of linear head on covariate-shifted OOD data:
E(f) E Po (b( + h(;;; M)),
where v() indicates the ground-truth class of T. E(f) 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:
S(f)
A E B Premans [f( - f.
(8)
The magnitude of S(f) reflects the extent of separation between ID and semantic OOD data. Larger S(f) suggests better OOD detection capability.
4.3 An Illustrative Example
Setup. We use an illustrative example explain theoretical insights. In Figure 2, the training examples come from 5 types of data: angel in sketch (ID), tiger in sketch (ID), angel in painting (covariate OOD), tiger in painting (covariate OOD), and panda (semantic OOD). The label space ) consists of two known classes: angel and tiger. Class Panda is considered a novel class. The goal is classify between images of angels and tigers while rejecting images of pandas.
Augmentation transformation probability. Based on the data setup, we formally define the augmentation transformation, which encodes the probability of augmenting original image
5

---

to the augmented view z:
p if
- d(2);
if - =
T (x σ
=
if
y( v())
(9)
if
(z).
Here d()) is the domain of sample ž. and y()) is the class label of sample I. a 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 >> (ax 8) Z min(a, (3 > 2 O.
a
Figure 2: Illustration of graph and augmentation probability.
A Adjacency matrix. With Eq. 9 and the definition in Section 3.1, we can derive the analytic form of adjacency matrix A.
+ a 2n²
2p8 4 240
2pa + 72 2y
+ 2np
+
Au-A4))
2pB +2 2ya
2po + 1 2-y
p² + 8 + 2n²
2nd +-2 4:2
o² +
2nd + 27p
2n
2pd 4 240
2pa + 7 2-8
1 11 2p)
1 2
2nd + +2 25
2pa -7 2nd
2p8 + 7 270
0² #2 o² 2
7(1 + a +B 2p)
7( + a 2p)
7(1 + a
7(1 + a 2p)
+
(10)
+ 5a
2p8
y3
46 + #1
A = 0 (n ( mm))(W))
1 c(
2pd
78
aB
p² 4
ad + 50
o² +1
pa + 7/
27a
7 + R]
1i +7)
+ A
pa +1
+
7/0 4.)
50p
+
7(p +
8)
7(0 +00+)))
7(a+1)
2x
(11)
where 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.I 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 E R5x3 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.
Theorem 4.1. Assume Tu m
we have:
1
0
v3
v3
V6
v6
0
0
1
if ga > 8;
0
ga > B;
V3
V3
VG
VG
,E(f)
(12)
0
1f 8
< B.
V3
v3
V8
V6
(
0
0
1
if 2 < 3
0
V8
V6
v3
V3
Interpretation. The discussion can be divided into two cases: (1) Ja > 3. (2) 3 < B. In the first case when the connection between the class (multiplied by 3) is stronger than the domain, the model could learn a perfect ID classifier based on features the first two rows in and effectively generalize to the generalization with linear probing eиror E(f) O. In the second case when the connection between the domain is stronger than the connection between the class (scaled by "), the embeddings of covariate-shifted OOD data are identical, resulting high OOD generalization error.
domain (the third and fourth row in V), achieving perfect OOD
Theorem 4.2. Denote a and B'
2 and assume Thu = 5, 77 = 1, we have:
S(f)
(7 129' + 12. 2 X2-2001 (1 +11)++1
3 > A; -
(13)
(7 128 120 120 2-30 +1)

---

Interpretation. We analyze the function S(f) under dif- ferent a' and 8 values Figure Overall the distance between semantic OOD data and ID data displays a large value, which facilitates OOD detection. Note that a clear boundary in Figure 3 indicates go =
0.100
9.5
0.040
0.050
0.10
6,20
0.000
0.040
0.050
More analysis. Building upon the understanding of both OOD generalization and detection, we further discuss the influence of different semantic OOD data in Appendix B, and the impact of ID labels in Appendix C.
Figure 3: Value of function S(f)
5
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.
5.1 Experimental Setup
Datasets and benchmarks. Following the setup of [5], we employ CIFAR-10 [14] as Pi and peovariate For out LSUN [17], Places365 [18], Textures [19]. To simulate the wild distribution Piiiu we adopt the same mixture ratio as in Scone [5], where Te = 0.5 and R, 0.1. Detailed descriptions of the datasets and data mixture can be found in the Appendix E. 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 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.
CIFAR-1O-C [15] with Gaussian additive noise as the out
Preniamisc we leverage SVHN [16].
Implementation details. We adopt Wide ResNet with 40 layers and 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. for 1000 epochs. The learning rate is 0.03 and the batch size is 512. The is selected within {1.00, 2.00) and n 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 learning rate 0.005 and batch size of 512. The fine-tuned model is used to evaluate the OOD generalization and OOD detection performance. We utilize distance-based method for OOD detection, which resonates with our theoretical analysis. Specifically, default approach employs simple non-paue -onramrmetriic KNN distance [23], which does not impose any distributional assumption on the feature space. The threshold determined based on the clean ID set at 95% percentile. For further implementation details, ppper-parameters, and validation strategy, please see Appendix F.
5.2 Results and Discussion
Competitive empirical performance. The main results Table demonstrate that our method not only enjoys theoretical guarantees but also exhibits competitive empirical performance compared to existing basclines. For a comprehensive evaluation, we consider three groups of methods for OOD generalization and OOD detection. Closest to our setting, we compare with strong basclines trained with wild data, namely OE [36], Energy reguay-reg 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 capture the domain- variant 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 poor OOD detection performance. (3) Methods trained with wild data emerge as robust OOD detectors, yet display notable decline in OOD generalization, highlighting the confusion introduced by covariate
7

---

SVATN OOD OOD-AcCT
Papat, CIPAR-ICC: FAMIIAA
ESEN-C
THE MA CIPAR-ID- Por
Tuedures
Papatl CIFAR-I--C ID-C Fooriiad
Medhod
TD A.C.
FPR.
AUROCT
OOD AOD.AOC.
1D A...T
EPR.
AUROCT
OOD ACC. OOD-ACC
IDACcC
FPR.
AUBOCT
000 desccion
MSP [24]
25.09
25.05
125]
25:05
75.05
94.84
90.96
98.25
54.34
53.79
Malaslanabie (2T)
75.05
94.84
12.00
07.60
75.05
94.84
19.22
94.15
15.85
94.34
15.00
93.35
VIM [2]]
7535
94.54
21.05
95. 63
75.05
94.54
3,50
05.52
75.05
04.84
29.35
93.70
KNN [23]
75.06
04.84
25.00
95.71
75,05
94.84
28.06
95.35
73385
94.54
58.50
92:73
ASH
7535
94.84
40.76
90.16
75.05
94,54
2.39
99335
75.05
94.54
53.37
$5.03
pescratiation
BIM
75.05
35.50
90.06
15.05
96.35
73.55
52.50
HBM
77.32
59.42
87.51
Mixsp [52]
79.17
95.30
07.33
18.75
79.17
93.30
52.10
76.56
79.13
03.30
58.24
75.70
VIREX [31]
76.90
91.35
55.03
91.22
76.90
01.35
$1.50
91.33 03.56
76.90
01.
65.00 45
85.40
KQRM [14]
75.11
51.90
90.92
75:71
92.95
31.53
95.89
75.71
92.95
57.
ShurpDRO (25]
79:03
79.03
95.71
UK [36]
37.61
41.37
99.26
44.71
29.36
93.95
Easegy outlice) (25)
20.74
90.22
0.86
98.81
32.55
92.97
2.33
99.93
49.34
94.65
16.42
95.46
Woods (17)
$2.70
94.88
2.31
99
76.90
05.02
1.80
99.56
83.14
94.49
19.10
90:45
Scone (5)
$4.00
94.63
10.85
97.84
84.58
93.73
10.23
05.02
85.56
03.97
32.15
90.91
Ours
$6.02.02
9% 10
0.35
49.98.mm
85.88,13
42.01
1.76
99.75
81.40
90.50
12,08_0
98.25
Table 1: Main results: comparison with competitive OOD generalization and OOD detection methods on
CIFAR-IO. Additional results for the Places365 and LSUN-R datasets be found in Table Bold-best. (*Since the OOD detection methods use the same model trained with the CE loss Pi.. they display same ID and OOD accuracy on CIFAR-1O-C.)
OOD data. In contrast, our method excels in both OOD detection and generalization performance. Our method even surpasses the latest method Scone by 25.10 15.10% in terms FPR95 on the Textures dataset. Methodologically. Scone uses constrained optimization whereas our method brings novel graph-theorete perspective. More results can be found in the Appendix
Better adaptation to the heterogeneous distribution. We conduct compar- ative analysis of our methods against other state-of-the-art spectral learning approaches within their respective do- mains. Specifically, Haochen et al. [7] in- vestigate unsupervised learning, Shen et al. [12] delve into unsupervised domain adaptation, and Sun et al. [13] explores novel class discovery. The baseline meth- ods all assume unlabeled data exhibits a homogeneous distribution, either entirely from ppcovaiiate in the case of unsupervised domain adaptation or entirely from psoemantic the case of novel class discovery. As depicted in Table 2, results reveal significant improvement competing baselines on both OOD generalization and detection. We attribute this empirical success our better adaptation the heterogeneous mixture of wild distributions. Additional results can be found in Table 6. More ablation studies can be found in Appendix E.4.
peemantic
Method
0OD Acc.
ID Acc.f
FPR]
AUROCT
SCL 121
75.96
87.58
21.53
96.56
SVHN
NS3L[
92.42
Ours
86.62
93.10
0.13
99.98
SCL. [7. 12]
LSUN-C
NSCL (13)
77.64
90.61
18.43
97.84
Ours
SCI. [7. 12] [S3
63.05
83.07
66.86
87.59
Ours
81.40
92.50
12.05
98.25
Table 2: Comparison with spectral learning methods.
our
5.3 Further Analysis
Visualization of OOD detection score distributions. In Figure 4 (a), we visualize the distribution of KNN distances. The KNN scores are computed based 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 expectations.
Visualization of embeddings. Figure 4 (b) displays the t-SNE [38] visualization of the normalized penultimate-layer embeddings. Samples are from the test set of ID, covariate OOD, and semantic OOD data, respectively. The visualization demonstrates the alignment of ID and covariate OOD data in the embedding space, which allows the classifier learned on the ID data to extrapolate the covariate OOD data thereby benefiting OOD generalization.

---

Semantic OOD
ID Data
Covariate OOD
Count
20
Semantic OOD
ID Data
0.0
0.2
0.4
0.5
0.3
1.0
1.4 1.6
Covariate OOD
KNN Score
(a) KNN distance distribution
(b) Embedding distribution
Figure 4: (a) Distribution of KNN distance. (b) 1-SNE visualization of learned embeddings. We employ
CIFAR-IO Ps, CIFAR-IO-C as prevariate and SVHN
6 Related Works
Out-of ditto--dittiibttinn detection. OOD detection has gained soaring research attention in recent years. The current research track can be divided into post hoc and regularization-ban based methods. Post hoc methods derive OOD scores at test-time based
pre-trained model, which can be categorized as confidence-basee methods [39, 24, 40], energy- based methods [26, 41, 42, 43, 44, 29], distance- based methods [45, 46, 47, 23, 48, 49, 50], and gradient-based method [51]. On the other hand, regularization-base methods aim to train the OOD detector by training-time regularization. Most approaches require auxiliary OOD data [52, 53, 54, 36, 55, 56, 57J. However, 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 more generalized data mixture 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 sentations 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 unlabeled data from the target domain. OOD generalization and domain generalization [62] focus on capturing seman- tic features that remain consistent across diverse domains, which can be categorized reducing feature discrepancies across the source domains [63, 64, 31, 65, 66, 67], ensemble and meta learn- ing [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 framework that leverages the wild data ubiquitous the real world, aiming to build a robust classifier and reliable OOD detector simultaneously. Following the same problem setting in [5], we contribute novel theoretical insights into the understanding both OOD generalization and detection.
repre-
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 's adjacency matrix. Shen et [12] provided graph-theoretic analysis for unsupervised domain adaptation based on the assumption of unlabeled data entirely from [peovariate Sun et al. [13] first introduced the label information and explored novel category discovery, considering unlabeled data covers out All of the previous literature assumed unlabeled data has homogeneous distribution. In contrast, our work focuses on the joint problem OOD generalization and detection, tackling the challenge of unlabeled data characterized by heterogeneous mixture distribution, which a more general and complex scenario than previous works.
Contrastive learning. Recent works on contrastive learning advance the development of deep neural networks with huge empirical success [6, 93, 94, 95, 96, 97, 98, 99, 100, 101]. Simultane- ously, 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 theoretic framework tailored for the wild environment to understand both OOD generalization and detection.
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.
8 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 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 critical bottleneck in the adoption of machine learning technologies, fostering trust among end-users and stakeholders.
9 Limitations
In experimental setup, we focus on covariate shift the primary form of shift in the out-of- distribution (OOD) generalization problem, topic extensively explored in the literature. However, it's important acknowledge the existence of other types of distributional shifts (e.g.. concept shift), which we defer for future investigation.
Acknowledgement
We thank Yiyou Sun for the valuable discussion and input during the project. Li gratefully ac- knowledges the funding support by the AFOSR Young Investigator Program under award number FA9550-23-1-0188 National Science Foundation (NSF) Award No. IIS-2237037 & IIS-233 169,,669, Office Naval Research under grant number 100014-3-11-2444 Philanthropic Fund from SFF, and faculty research awards/gifts from Google and Meta.
References
[1] Ishaan Gulrajani and David Lopez-Paz. In search lost domain generalization. In ICLR. OpenReview.net, 2021.
[2] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran S. Haque, Sara M. Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. WILDS: A benchmark of wn-the-wild distribution shifts. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 5637-5664 PMLR, 2021.
[3] Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey, CoRR, abs/2110.1 1334, 2021.
10

---

[4] Mohammadreza Salehi, Hossein Mirzaei, Dan Hendrycks, Yixuan Li, Mohammad Hossein Rohban, and Mohammad Sabokrou. A unified survey on anomaly, novelty, open-set, and out of-distribution detection: Solutions and future challenges. Trans. Mach. Learn. Res., 2022, 2022.
[5] Haoyue Bai, Gregory Canal, Xuefeng Du, Jeongyeol Kwon, Robert D. Nowak, and Yixuan Li. Feed two birds with one scone: Exploiting wild data for both out-of-distribution generalization and detection. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 1454-1471. PMLR, 2023.
[6] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple frame- work for contrastive learning of visual representations. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 1597-1607. PMLR, 2020.
[7] Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-super deep learning with spectral contrastive loss. In NeurlPS, pages 5000-5011, 2021.
[8] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[9] Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
[10] Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211 (3):221-2188, 1936.
[11] Yiyou Sun, Zhenmei Shi, and Yixuan Li. A graph-theoretic framework for understanding open-world semi-supervised learning. In NeurlPS, 2023.
[12] Kendrick Shen, Robbie Jones, Ananya Kumar, Sang Michael Xie, Jeff Z. HaoChen, Tengyu Ma, and Percy Liang. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 19847-19878. PMLR, 2022.
[13] Yiyou Sun, Zhenmei Shi, Yingyu Liang, and Yixuan Li. When and how does known class help discover unknown ones? provable understanding through spectral analysis. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 33014-33043. PMLR, 2023.
[14] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[15] Dan Hendrycks and Thomas G Dietterich. Benchmarking neural network robustness to common corruptions and surface variations. arXiv preprint 1807.00 2018.
[16] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. Neural Information Processing Systems Workshops, 2011.
[17] Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao. Lsum: Construction of large-scale image dataset using deep learning with humans in the loop. arXiv preprint arXiv:1506.03338 2015.
[18] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: 10 million image database for scene recognition. IEEE transactions on pattern analysis and machine intelligence, 40(6):1452-1444 1464, 2017.
[19] Mircea Cimpoi, Subhransu Maji, Iasonas Kokkinos, Sammy Mohamed, and Andrea Vedaldi. Describing textures in the wild. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3606-3613, 2014.
[20] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In CVPR, pages 5385-5394. IEFE Computer Society, 2017.

---

[21] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC. BMVA Press, 2016.
[22] John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 12:2121-2159, 2011.
[23] Yiyou Sun, Yifei Ming, Xiaojin Zhu, and Yixuan Li. out-of-distribution detection with deep nearest neighbors. International Conference on Machine Learning, 2022.
[24] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of- distribution examples in neural networks. In ICLR (Poster). OpenReview.net, 2017.
[25] Shiyu Liang, Yixuan Li, and R Srikant. Enhancing the reliability of out-of- distribbitiiino image detection in neural networks. In International Conference on Learning Representations, 2018.
[26] Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Li. Energy-based out-o--distribution detection. Advances in Neural Information Processing Systems, 2020.
[27] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distriuttion samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
[28] Haoqi Wang, Zhizhong Li, Litong Feng, and Wayne Zhang. Vim: Out-of-distribation with virtual-logit matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4921-4930, 2022.
[29] Andrija Djurisic, Nebojsa Bozanic, Arjun Ashok, and Rosanne Liu. Extremely simple activa- tion shaping for -i-ttii-ittiittionn detection. In ICLR. OpenReview.net, 2023.
[30] Vladimir Vapnik. An overview of statistical learning theory. IEEE Trans. Neural Networks, 10(5):988-9)) 0998,99999999 1999.
[31] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk mini- 2019.
mization. arXiv preprint
[32] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.
[33] David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapolation (rex). In International Conference on Machine Learning, pages 5815-
5826. PMLR, 2021.
[34] Cian Eastwood, Alexander Robey, Shashank Singh, Julius Kügelgen, Hamed Hassani, George J. Pappas, and Bernhard Schölkopf. Probable domain generalization via quantile risk minimization. In NeurlPS, 2022.
[35] Zhuo Huang, Miaoxi Zhu, Xiaobo Xia, Li Shen, Jun Yu, Chen Gong, Bo Han, Bo Du, and Tongliang Liu. Robust generalization against photon-limited corruptions via worst-case sharpness minimization. In CVPR, pages 16175-16185. IEEE, 2023.
[36] Dan Hendrycks, Mantas Mazeika, and Thomas Dictterich. Deep anomaly detection with outlier exposure. In International Conference on Learning Representations, 2018.
[37] Julian Samuuls, Julia B Nakhleh, Robert Nowak, and Yixuan Li. Training ood detectors in their natural habitats. In International Conference on Machine Learning. PMLR, 2022.
[38] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
[39] Abhijit Bendale and Terrance E. Boult. Towards open set deep networks. In CVPR, pages 1563-1572. IEEE Computer Society, 2016.
[40] Shiyu Liang, Yixuan Li, and Srikant. Enhancing the reliability out-of-distribution image detection in neural networks. In ICLR (Poster). OpenRevie 2018.
12

---

[41] Haoran Wang, Weitang Liu, Alex Bocchieri, and Yixuan Li. Can multi-label classification networks know what they don't know? NeurlPS, pages 29074-29087, 2021.
[42] Yiyou Sun, Chuan Guo, and Yixuan Li. React: Out-of-distribution detection with rectified activations. In NeurIPS, pages
2021.
[43] Yiyou Sun and Yixuan Li. DICE: leveraging sparsification for out-of-distribution detection. In (24), volume 13684 of Lecture Notes in Computer Science, pages 691-705 Springer, 2022.
[44] Peyman Morteza and Yixuan Li. Provable guarantees for understanding out-of-distributioo detection. In AAAI, pages 7831-7840. AAAI Press, 2022.
[45] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of aut-of-distributtin samples and adversarial attacks. In NeurlPS, pages 7167-7177, 2018.
[46] Zhi Zhou, Lan-Zhe Guo, Zhanzhan Cheng, Yu-Feng Li, and Shiliang Pu. STEP: out-of- distribution detection in the presence of limited in-distribution labeled data. In NeurIPS, pages 291 29168-29188 2021.
[47] Vikash Sehwag, Mung Chiang, and Prateck Mittal. SSD: A unified framework for self- supervised outlier detection. In ICLR. OpenReview.net, 2021.
[48] Xuefeng Du, Gabriel Gozum, Yifei Ming, and Yixuan Li. SIREN: shaping representations for detecting of-issiriibttiin objects. In NeurlPS, 2022.
[49] Yifei Ming, Ziyang Cai, Jiuxiang Gu, Yiyou Sun, Wei Li, and Yixuan Li. Delving into out-of-distribution detection with vision-language representations. In NeurIPS, 2022.
[50] Yifei Ming, Yiyou Sun, Ousmane Dia, and Yixuan Li. How to exploit hyperspherical embed- dings for out-of-distribution detection? In ICLR. OpenReview.net, 2023.
[51] Rui Huang, Andrew Geng, and Yixuan Li. On the importance of gradients for detecting distributional shifts in the wild. In NeurIPS, pages 677-689, 2021.
[52] Petra Bevandic, Ivan Kreso, Marin Orsic, and Sinisa Segvic. Discriminative uut-of-distributie detection for semantic segmentation. CoRR, abs/1808.00 0000000, 2018.
[53] Yonatan Geifman and Ran EI- Yaniv. Selectivenet: A deep neural network with an integrated reject option. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 2151-2159. PMLR, 2019.
[54] Sina Mohseni, Mandar Pitale, J. S. Yadawa, and Zhangyang Wang. Self-supervised learning for generalizable out-of-distribttion detection. In AAAI, pages 5216-5223. AAAI Press, 2020.
[55] Yifei Ming, Ying Fan, and Yixuan Li. POEM: distribbittin detection with posterior sampling. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 15650-15665. PMLR, 2022.
[56] Qizhou Wang, Zhen Fang, Yonggang Zhang, Feng Liu, Yixuan Li, and Bo Han. Learning to augment distributions for duitt--distribution detection. In Advances Neural Information Processing Systems, 2023.
[57] Xuefeng Du, Zhen Fang. Ilias Diakonikolas, and Yixuan Li. How does unlabeled data provably help out-of-distribution detection? In ICLR, 2024.
[58] Yaroslav Ganin and Victor S. Lempitsky. Unsupervised domain adaptation by backpropagation. In ICML, volume 37 of JMLR Workshop and Conference Proceedings, pages 1180-1189, JMLR.org, 2015.
[59] Yuhua Chen, Wen Li, Christos Sakaridis, Dengxin Dai, and Luc Van Gool. Domain adaptive faster R-CNN for object detection in the wild. CVPR, pages 3339-3348. Computer Vision Foundation/ / IEEE Computer Society, 2018.
13

---

[60] Yabin Zhang, Hui Tang, Kui Jia, and Mingkui Tan. Domain-symmetrie networks for adversarial domain adaptation. In CVPR, pages 5031-5040. Computer Vision Foundation / IEEE. 2019,
[61] Shuhao Cui, Shuhui Wang, Junbao Zhuo, Chi Su, Qingming Huang, and Qi Tian. Gradually vanishing bridge for adversarial domain adaptation. In CVPR, pages 1-66111261.. Computer Vision Foundation/ / IEEE, 2020.
[62] Jindong Wang. Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng. and Philip S. Yu. Generalizing to unseen domains: A survey on domain generalization. IEEE Trans. Knowl. Data Eng., 35(8):8052-800 2023.
[63] Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C. Kot. Domain generalization with adversarial feature learning. In CVPR, pages 5400-5409. Computer Vision Foundation / IEEE Computer Society, 2018.
[64] Ya Li, Mingming Gong, Xinmei Tian, Tongliang Liu, and Dacheng Tao. Domain generalization via conditional invariant representations. In AAAI, pages 3579-3587, AAAI Press, 2018.
[65] Shanshan Zhao, Mingming Gong. Tongliang Liu, Huan Fu, and Dacheng Tao. Domain generalization via entropy regularization. In NewrIPS, 2020.
[66] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean- Christophh Gagnon-Audet Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out- distri--ittiittioonn generalization. In NeurIPS, pages 4438-3450, 2021.
[67] Haoyue Bai, Yifei Ming, Julian Katz-Samuels, and Yixuan Li. Hypo: Hyperspherical out-of- distribution generalization. In ICLR, 2024.
[68] Yogesh Balaji, Swami Sankaranarayanan, and Rama Chellappa. Metareg: Towards domain generalization using meta-regularizzttonn In NeurlPS, pages 1006-1016, 2018.
[69] Da Li, Yongxin Yang. Yi-Zhe Song, and Timothy M. Hospedales. Learning to generalize: Meta-learning for domain generalization. In AAAI, pages 1190-3497.. AAAI Press, 2018.
[70] Da Li, Jianshu Zhang, Yongxin Yang, Cong Liu, Yi-Zhe Song, and Timothy M. Hospedales. Episodic training for domain generalization. In ICCV, pages 1446-1455. IEEE, 2019.
[71] Marvin Zhang, Henrik Marklund, Nikita Dhawan, Abhishek Gupta, Sergey Levine, and Chelsea Finn. Adaptive risk minimization: Learning to adapt to domain shift. In NeurIPS, pages 23664-23678, 2021.
[72] Manh-H Ha Bui, Toan Tran, Anh Tran, and Dinh Q. Phung. Exploiting domain-speciff features enhance domain generalization. In NeurlPS, pages 21189-21201, 2021.
[73] Junbum Cha, Sanghyuk Chun, Kyungjae Lee, Han-Cheol Cho, Seunghyun Park, Yunsung Lee, and Sungrae Park. SWAD: domain generalization by seeking flat minima. In NeurlPS, pages 22405-22418, 2021.
[74] David Krueger. Ethan Caballero, Jörn- Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang. Rémi Le Priol, and Aaron C. Courville. Out-of-distribution generalization via risk extrapolation (rex). In ICMI. volume 139 of Proceedings of Machine Learning Research, pages 5815-5826. PMLR, 2021.
[75] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. In ICLR. OpenReview.net, 2020.
[76] Yuge Shi, Jeffrey Seely, Philip H. S. Torr, Siddharth Narayanaswamy, Awni Y. Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. In ICLR. OpenReview.net, 2022.
[77] Alexandre Ramé, Corentin Dancette, and Matthieu Cord. Fishr: Invariant gradient variances for out-o--distt generalization. ICML, volume 162 of Proceedings of Machine Learning Research, pages 18347-18377. PMLR, 2022.
14

---

[78] Kaiyang Zhou, Yongxin Yang, Timothy M. Hospedales, and Tao Xiang. Learning to generate novel domains for domain generalization. In ECCV (16), volume 12361 of Lecture Notes in Computer Science, pages 561-578. Springer, 2020.
[79] Hyeonseob Nam, HyunJae Lee, Jongchan Park, Wonjun Yoon, and Donggeun Yoo. Reducing domain gap by reducing style bias. In CVPR, pages 1190-8699, Computer Vision Foundation /IEEE, 2021.
[80] Oren Nuriel, Sagie Benaim, and Lior Wolf. Permuted adain: Reducing the bias towards global statistics in image classification. In CVPR, pages 9482-9491 Computer Vision Foundation / IEEE, 2021.
[81] Kaiyang Zhou, Yongxin Yang, Yu Qiao, and Tao Xiang. Domain generalization with mixstyle. In ICLR. OpenReview.net, 2021.
[82] Hanlin Zhang, Yi-Fan Zhang, Weiyang Liu, Adrian Weller, Bernhard Schölkopf, and Eric P. Xing. Towards principled disentanglement for domain generalization. In CVPR, pages 8014-8024. IEEE, 2022.
[83] Frank McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Sympo- sium Foundations of Computer Science, pages 529-537. IEEE, 2001.
[84] Ravi Kannan, Santosh Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. Journal of the ACM (JACM), 577551 2004.
[85] James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 616):11-3,, 2014.
[86] Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. In Problems in analysis, pages 195-200. Princeton University Press, 2015.
[87] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intel.,, 22(8):888899 900,-90,,2220 2000.
[88] Avrim Blum. Learning form labeled and unlabeled data using graph mincuts. In Proc. 18th International Conference on Machine Learning, 2001, 2001.
[89] Andrew Y. Ng. Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849 856. MIT Press, 2001.
[90] Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pages 912-919. AAAI Press, 2003.
[91] Andreas Argyriou, Mark Herbster, and Massimiliano Pontil. Combining graph laplacians for semi-supervised learning. NIPS, pages 67-74, 2005.
[92] Uri Shaham, Kelly P. Stanton, Henry Li, Ronen Basri, Boaz Nadler, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks. In ICLR (Poster). OpenReview.net, 2018.
[93] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self-supervised models are strong semi eemi-superiieed learners. In NeurlPS, 2020.
[94] Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming Hc. Improved basclines with momentum contrastive learning. CoRR, 0es/22003.44999 2020.
[95] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Piere H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent A new approach to self-supervieed learning. In NewrIPS, 2020.
[96] Qianjiang Hu, Xiao Wang, Wei Hu, and Guo-Jun Qi. Adco: Adversarial contrast for efficient learning of unsupervised representations from self-trained negative adversaries. CVPR, pages 1074-1083. Computer Vision Foundation/ / IEEE, 2021.
15

---

[97] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In NeurIPS, 2020.
[98] Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. CVPR, 2021.
[99] Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Yariance-iivaraane--vvvaaane regular- ization for self-supervised learning. In ICLR, 2022.
[100] Jure Zhontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny, Barlow twins: Self- supervised learning via redundancy reduction. In ICML., 2021.
[101] Yiyou Sun and Yixuan Li. Opencon: Open-world contrastive learning. Trans. Mach. Learn. Res., 2023, 2023.
[102] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khande- parkar. A theoretical analysis of contrastive unsupervised representation learning, In ICML, volume 97 of Proceedings of Machine Learning Research, pages 5628-5637, PMLR, 2019.
[103] Jason D. Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self- self-supervised learning. In NeurlPS, pages 509-323, 2021.
[104] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. J. Mach. Learn. Res., 22:281:1-281:33 2021.
[105] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In ALT, volume 132 of Proceedings of Machine Learning Research, pages 1199-1206. PMLR, 2021.
[106] Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods. In NeurlPS, 2022.
[107] Zhenmei Shi, Jiefeng Chen, Kunyang Li, Jayaram Raghuram, Xi Wu, Yingyu Liang, and Somesh Jha. The trade-off between universality and label efficiency of representations from contrastive learning. In ICLR. OpenReview.net 2023.
[108] Jeff Z HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. Advances in Neural Information Processing Systems, 2022.
[109] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, pages 248-255. IEEE Computer Society, 2009.
[110] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alexander Shepard, Hartwig Adam, Pietro Perona, and Serge J. Belongie. The inaturalist species classification and detection dataset. In CVPR, pages 8769-8778. Computer Vision Foundation / IEEE Computer Society, 2018
[111] Rui Huang and Yixuan Li. Mos: Towards scaling semantie space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8710-8719, 2021.
detection for large
[112] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778. IEEE Computer Society, 2016.
[113] Kuniaki Saito, Shohei Yamamoto, Yoshitaka Ushiku, and Tatsuya Harada. Open set domain adaptation by backpropagation. In ECCV (5), volume 1209 of Lecture Notes in Computer Science, pages 156-171. Springer, 2018
[114] Pau Panareda Busto and Juergen Gall. Open set domain adaptation. In Proceedings of the IEEE international conference on computer vision, pages 754-763, 2017.
[115] Wuyang Li, Jie Liu, Bo Han, and Yixuan Yuan. Adjustment and alignment for unbiased open set domain adaptation. In CVPR, pages 24110-241 IEEE, 2023.
16

---

[116] Hong Liu, Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Qiang Yang. Separate to adapt: Open set domain adaptation via progressive separation. In CVPR, pages 2927-2936. Computer Vision Foundation/ / IEFF, 2019.
[117] Zhen Fang. Jie Lu, Feng Liu, Junyu Xuan, and Guangquan Zhang. Open set domain adaptation: Theoretical bound and algorithm. IEEE Trans. Neural Networks Learn. Syst., 32(10):4309- 4322, 2021.
[118] Qian Wang, Fanlin Meng. and Toby P. Breckon. Progressively select and reject pseudo-labelles samples for open-set domain adaptation. CoRR, abs/21 11.11......... 2021.
[119] Silvia Bucci, Mohammad Reza Loghmani, and Tatiana Tommasi. On the effectiveness of image rotation for open domain adaptation. ECCV (16), volume 12361 of Lecture Notes in Computer Science, pages 422-438. Springer, 2020.
[120] Kaidi Cao, Maria Brbic, and Jure Leskovec. Open- Open-world semi-supervised learning, In ICLR. OpenReview.net, 2022.
17

---

A Technical Details of Spectral Learning
Proof. We can expand (mr(F, A) and obtain
Lut Lin (P, A)
E
Waw
f2 Sax
VWzWWs Wxx
Σ
2wax f(x) (f) f(') + W (f(=)
=const
where fo = -wzf(() is re-scaled version of fx) At high level, we follow the proof in Haochen al. [7], while the specific form of loss varies with the different definitions of positive/negative pairs. The form of L()) is derived from plugging Wazz and Wz.
Recall that Way is defined by
Σ KEDi
ER BEE~PI T(s)ai)T The E T (dl(
Wyzt 1J1
and Wr is given by
Σ Waat
Wx
Σ EgiePi BE/ (( Σ T (2/1(()) + Be, (T((Tw)
1
iE)
E Eg T(x(āt) TT. (x:()t))
1/1
Plugging in Way' we have,
Σ
Wex f(x) f (z')
E.
Σ
Wan- f(x) (x+)
x, EX
2m
Egy Bi BE(WFN
Σ T(a ((t)
iED!
2m.EE PP
T(xlaa) (x' (d'
2m
Σ
E
[x())T((>t)]
iE
x~ T a TT(1))
2m
E
ff
a~T(( T(-Ba.))
- (f) - C2(
Plugging we and war have,
18

---

Σ w f((=)"((x))
Σ
2, EX
Σ EX
Ex T(x( + nn E (ar
THI
KEDI
11t Σ JEMI
BI T(x (x%) + nu Ne (=/)) (
111 Σ
Σ
ERINPE 12 T(x Σ Be T(x (2)) (f(x) f (x7))²
2, EX' iEM!
jEJ,
+ 7m
ERINP Tx T (a.) Tf (x=))
+ 2 Σ
ER N (eeli (
EX
[
B T (T(1)))
NE JEJ/
{--))
+ mo
E S PP, 3~ (T((B.))
+ 2
{())))
a. ~P,
a-(())))) ~T(1)
Ls() + f((()
19

---

B Impact of Semantic OOD Data
In our main analysis in Section consider semantic OOD to be from different domain. Alternatively, in- stances of semantic OOD data can come from the same domain as covari- ate OOD data. In this section, we pro- vide complete picture by contrasting these two cases.
B
B
B
B
B
illustrate two scenarios where the semantic OOD data has either different or the same domain label as covariate OOD data, Other setups the same Sec. 4.3.
Setup. In Figure
(a) d(panda) # painting
(b) d(panda) = painting
Figure 5: Illustration of 5 nodes graph and the augmentation probability defined by classes and domains. Figure (a) illus- trates the scenario where semantic OOD data has different domain from covariate OOD. Figure (b) depicts the case where semantic OOD and covariate OOD share the same domain.
Adjacency matrix. The adjacency matrix for scenario (a) has been de- rived in Eq. 11. For the alternative scenario (b) where semantic OOD) shares the same domain as the covari-
ate OOD,
derive the analytic form of adjacency matrix A1
+2 g2 + + 22² 20B + 72 270
308 + 27a p² + + 222 2y²
2pa + 3r8 20 78 2xp p² + 28²
2aB + 78 + 2np 2 3yd
ag + 27(8 + pf ag 4 27( + 2p8 + 3a + tho
A (w)
200 3-8
2a8 + 18 2np
+
203 + 8² 27a pa + 25 a
20B + 27p a8 + 23(8 p)
2ap 3-8
2p3 8 27a
2p3 32 toa
a + 20(B
2pB + 5² + +
na
2n8 + 8² + 72
na
p² 28 2n (14)
2 و2
pa +
ad +op
7(9 + p)
A
1
(m +mma(1))
2pB
78
p² g
+0
og +
a² ++
pa +
2ya
+(+
7(9 + p)
+ A/
(n)),
C1
C1
of +
pa - 78
270
o² 4
7(7 +()+
768 7(9
7(++a) a)
+(++a)
27
(15)
where C is the normalization constant to ensure the summation of weights amounts to 1. Each row or column encodes connectivity associated with 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 and put analysis the top-3 eigenvectors V Rax3
Theorem B.1. Denote a' a and 3 = and assume The 5, mi we have:
V2
v2
1
Vi
a(12)
a(>2)
b(a2)
b(x2)
1
R, E(f) = 0, 1f 0.
(16)
c(Pa))
-x(as)
-1
where a(A) 22(1-63' 8,3"
b(A) = 48' -+
c(A)
22''-3n'-00' R a diagonal matrix 3n'
4/²
that normalizes the eigenvectors to unit norn and Xu Aog are the 2nd and 3rd highest eigenvalues.
Interpretation. When semantic OOD shares the same domain as covariate OOD, the 00D gen- eralization error E(fi) can be reduced to 0 as long as a and 9 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 a' - and 3 = L and assume Tj
5, m = 1, we have:
-(f) S(f) {
> 0 if f E black area in Figure 6 (b); 0 if B white area in Figure (b).
(17)
20

---

0.010
0.8
0.020
2
0.020
0.6
0.030
1
0.030
0.4
0.2
0
0.050
0.010
0.020
0.030
0.040
0.050
0.050
0.010
0.020
0.030
0.040
0.050
0.0
(a) Heatmap of S( S(h)
(b) Heatmap of ((S S(h))
Figure 6: Visualization the separability difference between two cases defined Figure (a) and
Figure 5 (b). Figure (a) utilizes heatmap depict the distribution, while Figure 6 (a) uses the indicator function.
Interpretation. If a', S black area in Figure 6 (b) and semantic OOD comes from different domain, this would increase the separability between ID and semantic OOD, which benefits OOD detection. If a', 3' white area in Figure 6 (b) and semantic OOD comes from different domain, this would impair OOD detection.
C Impacts of ID Labels on OOD Generalization and Detection
Compared to spectral contrastive loss proposed by Haochen et al. [7], we utilize ID labels in the pre-training. In this section, analyze the impacts of ID labels 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 and put analysis on the top-3 eigenvectors (u) E R5x3, Detailed derivation can be found in the Appendix D.3.
Theorem C.1. Assume T)
5, m7
1. we have:
1
07
0
0
a > 3;
2 -1
-
1
0
( 0 ifa 8; ifa < 3.
(u))
E(((())
(18)
1
0
0
ifa <
2
0
Interpretation. By comparing the eigenvectors 1/ in the supervised case (Theorem 4.1) and the eigenvectors ((() in the self-supervised case, we find that adding ID label information transforms the performance condition from a B a 8. In particular, the discussion can be divided into two cases: (1) a B. (2) a < 3. 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 (u) and effectively generalize the covariate-shifted domain (the third and fourth row in (=))), ) achieving perfect OOD generalization with {(f())) = 0. In the second case when the connection between the domain is stronger than the connection between the class, the embeddings of covariate-shiffe OOD data are identical, resulting in high OOD generalization error.
Theorem C.2. Assume Tu = 5, m = 1. we have:
S() - ( > O, 0,8
(19)
Interpretation. After incorporating ID label information, the separability between ID and semantic OOD in the learned embedding space increases as long as a and are positive. This suggests that ID) label information indeed helps OOD detection. We empirically verify our theory in Section E.4.
21

---

D Technical Details of Derivation
D.1 Details for Figure 5 (a)
Augmentation Transformation Probability. Recall the augmentation transformation probability,
which encodes the probability of augmenting original image the augmented view
P
if
y( y(z), d() d(z);
T (x
a
if
y(ï) = -(x) d d(æ);
3
if
y(z) f
d(z);
Y
if
u(z) + y(z). d(z).
Thus, the augmentation matrix T of the toy example shown in Figure 5 (a) can be given by:
B
7
p
7
a
?
T
P
3
?
a
3
P
Y
7
P]
Each column encodes augmentation connectivity associated with specific sample, ordered by: angel sketch, tiger sketch, angel painting, tiger painting, and panda.
Details for A and A Recall that the self-supervised connectivity is defined in Eq. Since have a 5-nodes graph, (()) would be TT If assume Ta 5, we can derive the closed-form self-supervised adjacency matrix:
x² + + a² 2-²
308 7 27a
2pa 7² + 238
2n8 +- + 2gp
1 2p)
Th (")
208 + 27a
p² + a² 2n
2a8
73 225
1h+ 2p)
2pa +
2-18
208 + 27p
o² a -2
20d +- 2.0
2ad + 7 27p
2pa pea-7" 2n18
2p8 +
o + +-2
oir + a 2p)
7( a 20)
>(t
2p)
+ +
6² 4
Then, according to the supervised connectivity defined in Eq.
only compute ID-labeled data.
Since we have two known classes and each class contains one sample, A = T., T, + T.2
Then if let YjI = 1, we can have the closed-form supervised adjacency matrix:
p + 82
2p8
par + 73
o + TP
+(+
2p8
0²
+ 32
78 aB
pa p
7(a (p+
pax + 43
aB
4P
a² +2
27a
aB + 77
pa 78
270
a² +2²
7(a+7)
Lypp
r(a +)+
+1)
272
Details of eigenvectors V. We assume p >> max(a, 3) > min(a, B) 7 2 0, and denote a' 2 3. p. can be approximately given by:
p
2
43'
3d'
0
4,
2
0
3a'
0
A -=
3d
0
23
0
0
3a
23''
0
0
0
1
where Ō is the normalization term and equals to 7 + 12,3' + 12x'. The squares of the minimal term
(e.g., aB a g²
p - etc) are approximated to 0.
p
p=: p
D diag(2 + 4.' + 3a', 2 43' + 3a', 1 23'
3a' .aa,1+130 1+22* + 3a',
D Vodiagl
3
3
3
(1 3 -a
3r
/2"
4
V2
2
2/'
2
vI a'
0
2
1 -
2/' -3
vza
1 DD1AD-1 D- !AD-!
0
- 2,'' 3n
28
V2 0
3a
2
23'
30
0
0
0
1.
22

---

Let A1..... and v be the eigenvalues and their corresponding eigenvectors of D D-1AD ADD the concrete form of As....5 and V can be approximately given by:
Then
1 vē valv2,
d1 =
82 [0,0,0,0,1|*
d2 =
G3 - -1,10,
d - 4
4 Ve -1, 0]
ìa 20
0 vo -1,
Às = 4 2
Since O, we can always have Đ1 = A2 > l1
to and X1 = x22 > dr As. Then, we let
k = 3 and V E R2x3 is given by:
v3
33
V6
0
0
0
1
if ga' > B':
0
V3
V3
V6
VG
V
0
V3
V3
V6
V6
0
0
0
1
if ga < B'.
V6
V6
V3
V/3
Details of linear probing and separability evaluation. Recall that the closed-form embedding Z [D)-&v,, V Based the derivation above, closed-form features for ID sample Zi R223 can be approximately given by:
(1 -1 0.750 0.
4 vI 4/
v
if g B
V6
1
0
Zin
[1- B¹ -0.700055 '
V2
0
a
if af B'.
2/3
V2 0
Based on the least error method, we can derive the weights of the linear classifier M E 12322
M = (2 Zin)
Z in Vin
where (.)² the Mloore-Penross inverse and Yiu is the one-hor not encoded ground truth class labels. So
when a B, the predicted probability Ieovariate be given by:
(1 8r
a
Fout
poovariate
soovariate
AI
I
1 - 8r
a'
where I E 222x2 is an identity matrix. We notice that when ga < 3. 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:
9 > 8; 8
8())
2 if 9 8.
The separability between ID data and semantic OOD data can be computed based on the closed-form embeddings Zn and Zpemantic, out
semantiic out
V 1,0
(7 + 128'' + 12a')
1-28' (1 - 8 - -/0 +1)
ir > B;
S(f)
(7 12,3' 12a 2-3a' - B' - 30) +1)
if < 8
23

---

D.2 Details for Figure 5 (b)
Augmentation Transformation Probability. Illustrated in Figure (b), when semantic OOD and covariate OOD share the same domain, the augmentation matrix be slightly different from the previous case:
8
a
P
7
a
?
T
Q
P
8
8
7
3
P
7
3
3
P]
Each row or column represents augmentation connectivity of a specific sample, ordered by: angel sketch, tiger sketch, angel painting, tiger painting, and panda.
Details for A(u) and A After the assumption 7/u
5, T 1, can have Th 1
TTT:
x2+ + 22²
308 + 72 21a
2pa 2a3 3 2np
2np 20a + 3x8 200 82 240 8 + 25 + a +
2a
a 2-(8 p) 2p8 2² +. 2p3 52 +.a 4.2 4.
A
2p8 + + +24
20a 3yd
o²
20 70 2-e
+ 5a a² +2
# + 20
4
a + 2n(8 + P)
20,8 + 2np
2ap + 3-8
203 + 8a 27a
a2 + 25(0 +
ag 2y(0 +
2n0 + 32 4.2
+ va
2n0 +
4.
And the supervised adjacency matrix A =T,1 T.,1 + T.2T.,2 be given by:
p 82
2pB
par 73
o + 7p
7(3 + p)
2p3
p² + 3
a tp
pa +a
7
n:410
par + 73
aB t7p
+
27a
+
aB+ 7p
pa pa + 73
27a
a² +22
7(7+a)
(/33 +
7(3 +))
7(Y
7(1 +a) 27
Details for Vj. Following the same assumption, the adjacency matrix can be approximately given by:
4
3d
0
0
4
0
30'
1
A = 2
3a
0
1
2
2,3'
C1
3a
23
1
2,'
23'
23'
D7 diag (2 + 4,' + +3', 2 43' + +30', 1 43' + +30, 1 1 43' +3a', , 4,3)]
C
1
3
DT
C1 diagi
- (1 - 8' a
(1
3 d'), 1,1 23' a' 1 2,'
a', 2
V2
V2
2
2
28
a
28'
V2
20'
20
Dj A,D Dj AAD
3
30
48'
25
23'
4.8_
where Õ the normalization term and Ō 7 20,3' + 12a'. After eigendecompposition we can derive ordered eigenvalues and their corresponding eigenvectors:
6. V2,112,1,1,11
K =1
022 (2((A)) +260,124 (0 (( ((2), ((22), 1J1),
N 1 36 +
v3 (27a 40ab+4867
V 22(22)2422 (c()s), c (s)) T
N 5b
8la 24mb 166
04 2 +200 M4), (o(\s), b())),
2 1 36
v3 100b+18000
05
V2c(A)'++ (c(5s) -1,
A 1 56
VSIa*+2labs
167

---

where d1
A2
A3
A and a(A)
12(1-68'' A) b(A)
48'-1+4 43
.((2)
8.
2211-30 -6'' 3rx
We can get closed-form eigenvectors:
V2
v2
1
1
Vi =
x(22)
((22)
b(x2)
b(x2)
1
diag
c(Aa)
(Aas)
0
V 220(22)2 + 27(22)2 +1 2c((2s) +2
Details for linear probing and separability evaluation. Following the same derivation, we can derive closed-form embedding for ID samples Z. = - VIn V and the linear layer weights gevariate,
M [ mm ) 2 Vin Eventually, we can derive the approximately predicted probability Fou
Jai + bi Q1
bi a1
goovariate
b1
+ by
where d1, d1 and by > 0. This indicates that linear probing error E(fi) 0 as long and are positive.
Having obtained closed-form representation Zin and Zsemantic and then prove:
can compute separability S(fi) out
a(x2)V
(1-3
3
mm
26(22)2-11 220(A2)²-210
V20(2))242
V2
a(22)1 22
v /2((5a)+42
seemantic = -1--
Ci
0]
out
V7
v 20(22)2 2 26(22)
if a', E black area in Figure 6 (b); 0 if a B E white area in Figure (b).
-
D.3 Calculation Details for self-supervised case
Our analysis for the self- sulf-supe case is based Figure 5 (a), the adjacency matrix is exactly the same as Eq. 10. After approximation, we can derive:
2
2a
0
2
1
0
20
0
(1)) ~ 7(0)
1
2a
0
1
23'
0
((v)
2a
2
1
0
0
0
0
1
D(u)
5 5 + 8,3' + 80 diag]
- B8
B'
0
B²
/
B' -
d'
1
2
-2d'
2
2a'
0
0
1
-
2/3'
1 2,3'
2a'
2a'
D(u)
A(u) D(u)
20'
0
1
23'
2d
28'
0
20'
23'
1
23
2a
0
0
[1, 11,1,1114 1,0
Å1 =
[0, 0, 0, 0, T
Å2 = 1
0g 1- 1,,,,
Å 1 4,3
04 1-1,-1,11111
d = 1 - 4a'
05 -1.-1,-1,,11
AS = 1 - 4a' - 4
Following the same procedure presented above,
prove Theorem C. and C.2.
25

---

E More Experiments
E.1 Dataset Statistics
We provide 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 100 consists of subset of 100 categories from ImageNet- K [109]. This dataset contains
the following classes: n01498041, n015 1485,, n01 n01582220, nO1 601608432, n01616318, n01 6879788, n01776313,
n01806567, nO1 n01833805, n01882714, n01910747, n01944390, n01985128, n02007558, n0207 n02085620.
002114855, n02123045 n02128385, n02129165, n02129604, n02165456, n02190166, n02219486, n02226429,
n02279972, n02317335, n02326432, n02342885, n02363005, n02391049, n02395406, n02403003, n02422699,
n02442845, m02444819, n02480855, n02510455, m02640242, n02672831, n02687172, n02701002, n02730930,
n02769748, n02782093, n02787622, n02793495, n02799071, n02802426, n02814860, n02840245, n02906734,
n02948072, m02980441, n02999410, n03014705, m03028079, n03032252, n03125729, nO3 n03179701,
n03220513, m03249569, n03291819, n03384352, m03388043, m03450230, n03481172, n03594734, m03594945,
n03627232, n03642806, m03649909, n03661043, m03676483, n03724870, n03733281, n03759954, n03761084,
n03773504, n03804744, n03916031, n03938244, n04004767, n04026417, n04090263, n04133789, n04153751,
n04296562, m04330267, m04371774, n04404412, m04465501, 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 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) large-scale image datasets that are annotated using deep learning with humans the loop. LSUN-C is 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 challenging real-world dataset with iNaturalist species, captured in a wide variety of situations. has 13 super-categories and 5,089 sub-categories. We use the subset from Huang et al. [111] that contains 1 10 plant classes that no category overlaps with IMAGENET- 1K [109].
Office-Home [20] is challenging dataset, which consists of 15500 images from 65 categories. is made up of domains: Artistic (Ar), Clip-Art (CI), Product (Pr), and Real-World (Rw).
Details of data split for OOD datasets. For datasets with standard train-test split (e.g., SVHN), we use the original test split for evaluation. For other OOD datasets (e.g., LSUN-C), we use 70% of the data for creating the wild mixture training data well as the mixture validation dataset. We use the remaining examples for test-time evaluation. For splitting training/validatinn validation and the remaining for training. During validation, could only access unlabeled wild data and labeled clean ID data, which means of ID Acc. the ID validation set (more in Section F).
we use 30% for
are chosen based on the performance
E.2 Results on ImageNet-100
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 IP... ImageNet- 100-C out and iNaturalist [110] as psemantic Similar to our CIFAR experiment, divide the ImageNet-100 out
peovariate
26

---

Places365
Fout CIFAR-IO-C
LSUN-R Famanii, CIFAR-I0-C Pugaaiate
Model
OOD
ID Acc.1
EPR.
AUROC
OOD Acc.t
ID Acc.
FPR.
AUROCT
0OD detection
MSP [24]
75.05
94,84
$7.40
84.49
75.05
94.84
52.15
91.37
ODIN [25]
75.05
94.84
57.40
84,49
75.05
94.84
26.62
94.57
Energy [26]
25.05
94.84
40.14
89.89
75.05
94.84
27.58
94.24
Mahalanobis [27]
75,05
94.84
68.57
84.61
75.05
94.84
42.62
93.23
VIM [28]
75.05
94.84
21.95
95.48
75.05
94.84
36.80
93.37
KNN [23)
75.05
94.84
42.67
91.07
75.05
94.84
29.75
94.60
ASH [29]
75.05
94.84
44.07
88.84
75.05
94.84
22.07
95.61
0OD generalization
ERM [30]
75.05
94.84
40.14
89.89
75.05
94,84
27.58
94.24
IRM [31]
77.92
90.85
53.79
88.15
77.92
90.85
34.50
94.54
Mixup [32]
79.17
93.30
58.24
75.70
79.17
93.30
32.73
88.86
VREx [33]
76.90
91.35
56.13
87.45
76.90
91.35
44.20
92.55
EQRM [34]
75.71
92.93
51.00
88.61
75.71
92.93
31.23
94.94
SharpDRO [35]
94.91
34.64
91.96
79.03
94,91
97.44
Learnnng Fuil
OE [36]
35,98
94.75
27.02
94.57
46.89
94,07
0,70
99.78
Energy (w/ outlier) [26]
93.60
99.94
Woods [37]
54.58
94.88
30.48
93.28
78.75
95.01
0.60
99.87
Scone [5]
85,21
94.59
37.56
90.90
80.31
94.97
99.79
Ours
87.04..0..3
93.40g.0.3
40.97
91.82g0.0
79.38
92.44
0.06
99.99.0.
Table 3: Additional results: comparison with competitive OOD generalization and OOD detection methods on CIFAR-10. 10. To facilitate a fair comparison, we include results from Scone [5] and set Tee 0.5, 0.1 by default for the mixture distribution P Pwald := (1- T t. [Peerantii +-T, ppcovariate Bold=best. (*Since all the OOD detection methods use the same model trained with the CE loss on Pin, they display the same ID and OOD accuracy CIFAR-10-C.)
out
training into 50% labeled ID and 50% unlabeled. Then we mix unlabeled ImageNet- 100, ImageNet-100-CC 100-C, and iNtturalist to generate the wild dataset. We include results from Scone [5] and set म. 0.5, म. 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- pre-training epoch as 100, batch size as 512, and learning rate 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 indicate that our method effectively balances OOD generalization and detection while achieving strong performance both aspects. While Wood [37] displays strong OOD detection performance, the OOD generation performance (44.46% significantly worse than ours (72.58%). More detailed implementation can be found in Appendix F.
Method
OOD Ace.1
ID Ace.1
FPR]
AUROCT
Woods [37]
44.46
86.49
10.50
98.22
Scone [5]
65.34
87.64
27.13
95,66
Ours
72.58
86.68
21.00
96.52
Table 4: Results on ImageNet-100 100. We employ ImageNet- noise as ipcovariate and iNaturalist as Ipsemantic Bold=Bestt out
100 as Pin. ImageNet-100-C with Gaussian
out
E.3 Results on Office-Home
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 (CI), Product (Pr), and Real-World (Rw). Following OSBP [113], 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, construct the ID data from one domain (c.g., Ar) across 25 classes, and the covariate OOD from another domain (e.g., CI) 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 psemantic and म. + π. = 1. This setting is also special case of ours.
the following wild data, where Piild = T. peovariate + .r out known open-set domain adaptation [114], which can be viewed
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].
27

---

Following previous literature, we use OOD Acc. to denote the average class accuracy over known classes only in this section. We employ ResNet-50 [1 [1] as the default backbone. As shown in Table our approach strikes balance between OOD generalization and detection, even outperforming the state-of-the-art method Anna 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.
Ar
OOD
OID
OOD
STAue [116]]
50.3
36.5
68.7
40.3
81.1
40.5
53.0
36.1
51.4
36.5
60.3
36.5
55.4
26.3
ST [116]
46.0
37.7
18.01
11.6
73.
19.6
51.4
15.0
61.0
40.9
67:0
15.5
54.7
37.6
OSBP [115]
38.9
71.8
-0.2
79.3
12.5
59.4
20.7
67.0
37.3
72.0
30.8
31.9
(117)
53.3
59.
17.8
23.8
[199
25.9
08.4
29.7
53.
05.3
Anna (115)
61.4
21.3
68.3
20.1
74.1
20.3
58.0
26.9
6422
26.4
66.9
63.0
29.7
Ours
54.2
14.1
18.7
12.7
75.6
15.8
$1.1
14.8
61
88
68.0
10.5
58.3
9.2
Method
OOD Acc-T
P
FPRR,
OOD ACC FPHEL
Pr Rv
0OD ACc-T FVNLL
Re
0OD AcciT
Ber
FPNEL
000 Acc? FYRL
Pr
(OD Acci7
Average
FFRLL
STA [1:6]
28.5
78.1
36.7
67.9
37.7
51.4
42.
77.
42.0
53.4
37.4
STA [1in]
32.9
76.2
57.5
49.0
61.8
DAOD [117]
81.8
49.4
OSLPP [L18]
53.1
32.9
77.0
28.8
60.3
25.0
$4.4
35.7
78.4
29.2
63.8
28.3
ROS 199
66.5
78.8
71.8
31.6
87
74
51.5
07.0
72111
70.0
61.0
37.6
Ansa [115]
54.6
25.2
74.3
21.1
56.1
22.7
59.7
26.0
76.4
19.0
65.6
23.3
13.4
56.1
Table 5: Results on Office-Home. Bold=Best.
E.4
Ablation Study
Better adaptation to the heterogeneous distribution. As presented in Table 6, the results underscore our competitive performance compared state-of-the-art spectral learning approaches within their respective domains. For a fair comparison, SCL [7, 12) is purely unsupervised pre-trained on DrU where D represents the labeled set, and D, denotes the unlabeled wild set. NSCL [13] undergoes unsupervised pre-trase pre-training on Du and supervised pre-training on Di.
The improvement over SCL [7, 12] in both OOD generalization and detection illustrates the tremen- dous 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 Dj UD, contribute to the adaptation to the heterogeneous wild distribution, thereby establishing the generality of our method.
psemantie
Method
OOD Acc.t
ID Acc.
FPR.
AUROCT
SCL 17, 12]
74.02
87.20
67.42
84,79
PLACES365
NSCL [13]
86.79
91.56
54.27
87.07
Ours
87.04
93.40
40.97
91.82
SCL 17, 12]
63.77
84.86
4.10
99.29
LSUN-R
NSCL [13]
78.69
89.43
0.27
99.93
Ours
79.68
92.44
0.06
99.99
Table 6: Comparison with spectral learning methods. We employ CIFAR-10 as P., and CIFAR-10-C
with Gaussian noise as |pcovariate Bold=Best.
Impact of semantic OOD data. Table 7 empirically verifies the theoretical analysis in Section B. We follow Cao al. [120] and separate classes in CIFAR-I0 into 50% known and 50% unknown classes. To demonstrate the impacts of semantic OOD data on generalization, we simulate scenarios when semantic OOD shares the same or different domain as covariate OOD. Empirical results in Table indicate that when semantic OOD shares the same domain as covariate OOD, it could significantly improve the performance of OOD generalization.
F Implementation Details
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, pre-train Wide ResNet with spectral contrastive loss for 1000 epochs.
28

---

Corruption Type of poovariate out
jusemantic out
OOD Acc.
Gaussian noise
SVHN
85,48
Gaussian noise
LSUN-C
85,88
Gaussian noise
Places365
83.28
Gaussian noise
Textures
86.84
Gaussian noise
LSUN-R
80.08
Gaussian noise
Gaussian noise
88.18
Table 7: The impact of semantic OOD data on generalization. Classes CIFAR-I0 are divided into 50% known and 50% unknown classes. The experiment in the last line uses known classes in CIFAR- 10-C with Gaussian noise as peovariate and novel classes in CIFAR-10-C with Gaussian noise psemantic Bold=best.
out
The learning rate (Ir) is 0.030, batch size (bs) 512. Then we use ID-labeled data to fine-tune for 20 epochs with Ir 0.005 and bs 512. In ImageNet-100 experiments, train ImageNet pre-trained ResNet-34 for 100 epochs. The Ir is 0.01, bs is 512. Then we fine-tune for 10 epochs with Ir 0.01 and bs 128. In Office-Homn experiments, 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 al. [23]. And T/u is selected within {1.00, 2.00] and ny is within (0.02, 0.10, 0.50, 1.00]. J. In Office-Home experiments, set 5, T/u 3, and 1 within (0.01, 0.05). Tue 7ht summarized in Table 8.
ImageNet pre-trained ResNet-50 with Ir 0.001 and bs 64.
ID/Covariate OOD
Semantics OOD
7ju
CIFAR-IO/CIFAM 10I-IOOCCIIIOOOO
SVHN
0.50
2.00
LSUN-C
0.50
2.00
CIFAR-IOICIFAR-IOCC
Textures
0.50
1.00
CIFAR-IOICIFAR-IOCC
Places365
0.50
2.00
CIAAR-I/CIFAR-1044 IingeNee--OO/mmgeeeet-0000-0
LSUN-R
0.10
2.00
iNaturalist
0.10
2.00
Office-Home Ar/CI, Pr, Rw Office-Home Cl/Ar, Pr, Rw
CI, Pr, Rw
0.01
3.00
Ar, Pr, Rw
0.01
3.00
Office-Home Pr/Ar, CI, Rw Office-Homne Rw/Ar, CI, Pr
Ar, CI, Rw
0.05
3.00
Ar, CI, Pr
0.05
3.00
Table 8: Selection of hyper-parameters YJt,
Validation strategy. For validation, could only access unlabeled mixture of validation wild data and clean validation ID data, which is rigorously adhered to Scone [5]. Hyper-parameters are chosen based the performance of ID Ace. on the ID validation set. We present the sweeping results in Table 9.
1/u
ID Acc. (validation)t
ID Acc.t
OOD Acc.t
FPR
AUROCT
0.02
2.00
88,52
87.12
70.31
52.16
90.03
0.10
2.00
95.36
91.72
77.98
20.20
96.85
0.50
2.00
95.72
91.79
78.23
17.66
97.26
1,00
2.00
94.96
90.91
81.92
24.99
94.82
0.02
1.00
89.04
87.44
60.60
46.01
92.01
0.10
1.00
93.92
90.70
74.58
21.50
96.83
0.50
1.00
96.76
92.50
81.40
12.05
98.25
1.00
1.00
94.24
90.77
65.58
14.00
97.27
Table 9: Sensitivity analysis of peovariate and Textures Ipsemaniic Bold-best.
Tu. We employ CIFAR- 10 as P... CIFAR-10-C
as out
29

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification:
We have clearly claimed our contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer Appendix 9.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification:
Please refer to Appendix A and D.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer the Section 5.1 and Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer: [Yes]
Our code is available at Anonymous-
Justification:
4open 4ww.n.scieiie..................e science/r
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. ec/
Policy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: haaliii/ggiee//ee
/ /nips...
sssisssnn wwsssssoiiiiyyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer the Section 5.1 and Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
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, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
32

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide details regarding the hardware specifications Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //ne://iesssseeeeeee http://urrrpp...pppiii.lp//////a httpp//bbbiiihthhttttteeeeeeeeee cttuiieisllllllniecc ines?
Answer: [Yes]
Justification:
Our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer 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 socictal impact 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.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
34

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "vy2Fj5zw5A", "reviewer": "Reviewer_DU8N", "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.", "questions": "Please refer to the weaknesses.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The authors discuss a new method for generalizing to covariate shifts while robustly detecting semantic shifts, providing valuable insights into OOD problem.\n\n2. In addition to mathematical equations, the paper includes an illustrative example to clarify the method, enhancing understanding.\n\n3. The proposed method achieves better performance in OOD generalization and detection compared to the baseline methods.", "weaknesses": "1. The effectiveness of the methods is limited by numerous hyperparameter selections, preventing its practical application in real-world scenarios.\n\n2. 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.\n\n3. The theoretical guarantees discussed in the paper are not clearly defined, making it unclear what the specific goals of these guarantees are.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. We are glad to hear that you found our paper insightful, clearly presented, and performing well. We address each of your concerns below in detail:\n\n> Clarification on the number of hyperparameters\n\nThank you for bringing up this point. To clarify, the practical algorithm is presented in Equation (6), which reformulates the graph factorization problem into a contrastive learning objective that can be efficiently trained end-to-end using a neural network.  **Importantly, there are only two hyperparameters involved in our learning objective: $\\eta_l$ and $\\eta_u$**. This is comparable to, or even simpler than, many existing methods in the field, which often involve multiple hyperparameters across different components of their models.\n\nTo further assist in practical application, we provide guidelines and default values for the key hyperparameters in our paper. These guidelines (Section F) can serve as a starting point, reducing the burden of hyperparameter tuning in new scenarios. Additionally, these two hyperparameters have intuitive interpretations (e.g., balancing the influence of labeled vs. unlabeled data), which can help practitioners make informed adjustments based on the specific characteristics of their data.\n\n\n> Clarification on augmentation transformation in Equation (9)\n\n**In practice, there is no need to determine manually the augmentation transformation probability in $\\mathcal{T}(x|\\bar x)$**. Our practical algorithm, as described in Section 3.2, does not rely on the explicit construction of the graph or the augmentation transformation probability, making it adaptable to different datasets. **Specifically, the graph decomposition can be equivalently achieved by minimizing a surrogate contrastive learning objective**, which operates on pairs of images. In objective (6), empirical samples of augmented images (using common augmentations [1] such as Gaussian blur, color distortion, and random cropping) are sufficient for optimization, eliminating the need to know the underlying distribution of $\\mathcal{T}(\\cdot | \\bar x)$. This not only makes the approach more practical but also adaptable to various datasets and use cases.\n\nWe explicate the augmentation transformation probability primarily to support the theoretical analysis and provide tractable guarantees on how they impact OOD generalization and OOD detection performance. By providing theoretical guarantees as a function of the parameters that define these probabilities, we ensure that our method is grounded in solid theoretical foundations. The validity of the formulation in Equation (9) can also be supported in prior work [2]. **Thus, our approach enjoys theoretical guarantees while being easily applicable to various real-world datasets, as we have shown in our extensive experiments.** \n\n[1] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 1597–1607. PMLR, 2020.\n\n[2] Kendrick Shen, Robbie M. Jones, Ananya Kumar, Sang Michael Xie, Jeff Z. HaoChen, Tengyu Ma, and Percy Liang. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. In ICML, pages 19847–19878. PMLR, 2022.\n\n> Goals of theoretical guarantees\n\n**The goals and targets of our theoretical analysis are explicitly defined in Section 4.2**. Specifically,\n- We use linear probing evaluation (Equation 7) to quantify OOD generalization performance, measuring the misclassification rate on covariate-shifted OOD data.\n- We use separability evaluation (Equation 8) to quantify OOD detection performance.\n\n_Our Theorem 4.1 and Theorem 4.2 provide closed-form guarantees on these two errors respectively_. We are happy to revise the manuscript and highlight this connection more clearly. Thanks again for your valuable comments and suggestions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qkiJMZAKKp", "reviewer": "Reviewer_ureZ", "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.", "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?\n\n2.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": "None", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The idea is novel and the model is both reasonable and sound.\n2. The intuition behind the method is clearly described, and the theoretical analysis justifies the model well.\n3. Comprehensive experiments demonstrate the effectiveness and robustness of the proposed method, with significant improvements over state-of-the-art techniques.\n4.  The framework is scalable and practical, utilizing modern neural networks for efficient optimization, making it applicable to real-world data.\n 5. The use of spectral decomposition of the graph’s adjacency matrix to derive data representations is a novel and effective approach.", "weaknesses": "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.\n\n2.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?\n\n3.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.\n\n4.Figure 4 only visualizes the method proposed in this paper, lacking comparison with other methods.\n\n5.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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive and constructive feedback! Below we address your questions and comments in detail.\n\n> Questions about the metrics\n\nWe are happy to clarify this. SCONE adopted four metrics in experiments, **which are identical to ours**. Following SCONE, we introduce the FPR as the primary metric for evaluating OOD detection in problem setup. Since both AUROC and FPR are commonly used, we also report AUROC in our experiments for comprehensive evaluation. For better clarity, we will include AUROC in Definition 2.1. \n\n> GNN-specific tasks\n\nThank you for highlighting the connection to the GNN literature! We chose to focus on computer vision tasks for several key reasons:\n\n1. **Established framework**: Image classification tasks are well-established and have been extensively studied in the OOD detection and generalization literature. This allows us to position our work within a widely recognized and classical setting.\n\n\n2. **Consistency with prior work**: Our problem setup closely builds on prior work, particularly SCONE, which also focuses on the image domain. To ensure evaluation consistency and fair comparisons, it was important for us to remain within this established framework.\n\n\n3. **Novel graph-based perspective**: Our work introduces significant insights and techniques by applying a graph-based perspective to computer vision tasks. Unlike traditional GNN-based tasks, constructing edges and graphs for image-based tasks is less straightforward and insufficiently explored. To address this, a key innovation of our paper is the introduction of a surrogate objective, which reformulates the graph factorization problem as a contrastive learning objective. This allows our practical algorithm to be efficiently optimized without explicitly operating on a graph adjacency matrix, while still benefiting from the theoretical guarantees provided by the underlying graph-theoretic formulation.\n\n> Clarification on experiments\n\nWe believe our experiments are comprehensive and offer significant advancements over SCONE.\n\n1. We conduct more extensive evaluations than SCONE. In Section E.2, we present results on the ImageNet-100 dataset, and in Section E.3, on the Office-Home dataset—which was not considered by SCONE. These results consistently demonstrate our superior performance compared to SCONE.\n\n\n2. We introduce a novel analysis and ablation study on the impact of semantic OOD data, thoroughly examining cases where semantic OOD data originates from the same or different domain as covariate OOD data. This analysis is theoretically explored in Section B and empirically validated in Section E.4, a focus that SCONE does not address.\n\n3. We investigate the effects of ID labels on OOD generalization and detection, providing new insights into how the performance improves with the incorporation of ID label information (Section C). The empirical results shown in Tables 2 and 6 also validate our theoretical insights.\n\nLastly, we would like to clarify that the inference time and space efficiency of our method are identical to those of SCONE, as both approaches utilize the same neural network backbone. Overall, our work represents a significant theoretical and empirical advancement over SCONE.\n\n> More visualizations\n\nAs suggested, we present visualizations of SCL in the attached PDF. Compared with the baseline, our learning framework effectively pushes the semantic OOD data to be apart from the ID data and pulls the covariate OOD data close to the ID data in the embedding space. Visualization of SCONE can be found in Figure 3 of their paper.\n\n> Theoretical assumptions\n\nThanks for the thoughtful question. We are happy to clarify this further.\n\n1. _Accuracy of graph representations and spectral decompositions_: Our theoretical framework indeed leverages graph representations and spectral decompositions, specifically relying on the structure induced by augmentation transformations. However, we want to emphasize that our method does not depend on perfect or exact graph representations. Instead, our approach is designed to be robust to variations in the graph structure by incorporating empirical augmentation probabilities that guide the construction of the graph. The spectral decompositions used in our analysis are derived in exact closed form, following standard singular value decomposition, without requiring any additional assumptions. \n\n2. _Linear separability of OOD data_: Contrary to the concern raised, **our theoretical analysis does not assume the linear separability of OOD data**. In fact, one of the strengths of our approach is its ability to handle cases where linear separability is not guaranteed. Our theorems explicitly account for scenarios where the linear probing error and ID-OOD separability are non-zero. This reflects real-world conditions where OOD data might not be linearly separable, yet our method can still provide meaningful guarantees and effective performance.\n\n4. _Impact of assumptions in practical scenarios_: In practical applications, it is indeed possible that some of the idealized conditions assumed in theoretical analysis might not fully hold. However, our method is designed with flexibility in mind. For example, the parameters ($\\alpha$, $\\rho$, $\\gamma$ and $\\beta$) governing the augmentation transformation probabilities are designed with generality to capture different practical scenarios. **Our guarantees are provided as a function of these parameters, which can be flexibly adjusted to fit the specific characteristics of a given dataset**. Additionally, our empirical results demonstrate that the method performs robustly across a range of datasets and conditions, indicating that the assumptions made do not overly constrain the practical applicability of our approach. We believe this balance between theoretical rigor and practical flexibility is a key strength of our work.\n\nWe will revise our manuscript to make these points clear - thank you again for your valuable comments!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fb0bdC58Iy", "reviewer": "Reviewer_6JZj", "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.", "questions": "1. what are the advantages of doing OOD generalization and detection at the same time compared to have different method for each?\n\n2. what are the novel insight for OOD from this graph theoretic perspective?", "limitations": "N.A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the connection between the OOD problem and partition/clustering analysis from graph theory is interesting\n\n- the papers are well-written with examples for illustrations", "weaknesses": "- despite the case studies for the proposed frameworks/analysis, the proposed method in its current form seems to be impractical for large-scale problem\n\n- 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\n\n- there are some connections between the analysis and claims that are not very strong (see questions below for more details)\n\n- there are some minor formatting/presentation issues in line 192-195", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive and constructive feedback on our work! Below we address your questions and comments in detail.\n\n> Practicality of the algorithm/framework\n\nYou raise an excellent point. Our graph-theoretic framework can be used practically, as detailed in Section 3.2. In particular, the spectral decomposition can be equivalently achieved by minimizing a surrogate objective in Equation (6), which can be efficiently optimized end-to-end using modern neural networks. **Empirically, we have demonstrated this on large-scale dataset including ImageNet (see Section E.2)**. Thus, our approach enjoys theoretical guarantees while being applicable to real-world data. \n\n> proposed method heavily rely on how the edges are/should be constructed in the graph.\n\nThank you for raising this important point. We acknowledge that the construction of edges in a graph is indeed a challenging and open question, and this is a crucial aspect of our work.\n\nHowever, **our approach specifically addresses this challenge by proposing a surrogate objective that effectively circumvents the need for explicitly defining and constructing graph edges in a traditional sense**. Instead, we reformulate the problem into a contrastive learning framework, where the relationships between data points are implicitly captured through the use of augmentation transformations. This allows us to leverage the power of graph-based modeling while avoiding the complexities associated with direct edge construction.\n\nMoreover, our method is designed to be flexible and adaptable to different scenarios by allowing the augmentation transformation probabilities to guide the implicit graph structure. This design choice not only makes the approach more practical but also robust to variations in the underlying data distribution. By providing theoretical guarantees as a function of the parameters that define these probabilities, we ensure that our method is both effective and grounded in solid theoretical foundations. We believe our work represents a significant advancement in how graph-based methods can be applied to OOD detection and generalization.\n\n\n\n> What are the advantages of doing OOD generalization and detection at the same time compared to have different method for each?\n\nThere are several benefits of devising a method that can jointly handle both OOD generalization and detection problems:\n\n- **Computational efficiency**: Investing in developing and maintaining a single method is typically more cost-effective than supporting two separate methods in inference time. This can be particularly important for organizations with limited resources, or dealing with large volume of data traffic. \n\n- **Deployment simplicity**: Deploying and maintaining a single model is generally simpler and less error-prone than managing multiple models. This includes considerations like updates, scaling, and monitoring.\n\n- **Improved performance**: The learning tasks of OOD generalization and detection can benefit from each other, as we have demonstrated in this paper. As shown in Table 1, our method excels in both OOD detection and generalization performance, surpassing state-of-the-art methods by a large margin. \n\n> Novel insights\n\nThere are several theoretic insights derived from the graph-theoretic perspective:\n\n+ **Effectiveness of OOD detection**: As presented in Section 4.3,  we primarily analyze the OOD performance in our proposed framework. Theorem 4.2 exhibits that the separability between semantic OOD data and ID data displays a large value, which facilitates OOD detection. The empirical results in Table 1 also validate the effectiveness of OOD detection performance.\n\n+ **Novel analysis of semantic OOD data**: As presented in Section B, we introduce a novel analysis of the impact of semantic OOD data, thoroughly examining cases where semantic OOD data originates from the same or different domain as covariate OOD data. Theorem B.1. demonstrates that semantic OOD and covariate OOD sharing the same domain could benefit OOD generalization, which can be empirically validated in Section E.4.\n\n+ **Impact of ID labels on OOD performance**: As presented in Section C, we investigate the effects of ID labels on OOD generalization and detection, providing new insights into how the linear probing accuracy of covariate OOD and separability between ID and semantic OOD data improve with the incorporation of ID label information. Theorem C.1. and C.2. show that incorporating ID labels during pre-training can facilitate both OOD generalization and detection performance, which can also be validated empirically in Tables 2 and 6.\n\n> Formatting issue in L192-L195\n\nGreat catch! We will fix that in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZLakQj5dal", "reviewer": "Reviewer_LF4w", "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.", "questions": "1. Would more advanced data transformation in SSL enhances the OOD generalization ability?\n\n2. 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.\n\n3. 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": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written with a clear motivation.\n\n2. The paper proposes a algorithm with graph-based formulation to jointly address OOD detection and generalization, achieving state-of-the-art performance.\n\n3. The paper presents an example with theoretical analysis to study the characteristics of the algorithm and better understand it.\n\n4. The paper proposes a surrogate loss to enhance computational efficiency, which is well-supported.", "weaknesses": "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.\n\n2. 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.\n\n3. 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.\n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive and constructive feedback on our work! Below we address your questions and comments in detail.\n\n> Further refinement for the OOD generalization performance\n\nWe appreciate your insightful analysis and totally agree with your perspective. Guarantees for OOD generalization may not always hold in some specific scenarios. This is not unique to our approach, but a common challenge underlying OOD generalization algorithms (e.g., when the domain gap is significant) [1]. Inspired by your suggestion, a potential future direction could involve incorporating learnable augmentations, which may further enhance OOD generalization performance.\n\n> Would more advanced data transformation in SSL enhance the OOD generalization ability?\n\nThis is an excellent question! In this paper, we chose to use the same data augmentation transformations as [2] to keep the method simple and user-friendly. We agree that exploring more advanced data transformations could be an interesting direction.\n\n> What does it mean by heterogeneous distribution in line 266? \n\nBy \"heterogeneous distribution,\" we refer to unlabeled data that includes various types of distributional shifts, such as covariate shifts and semantic shifts. This is formally defined in **Definition 2.1** in Section 2.\n\nIn contrast, the baseline methods assume the unlabeled data exhibits a homogeneous shift, either entirely due to covariate shifts (as in unsupervised domain adaptation) or semantic shifts (as in novel class discovery).\n\nFor greater clarity, we have revised the wording to \"heterogeneous shift.\" Thanks for calling that out!\n\n> 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?\n\nGreat question. To clarify, ASH is a post-hoc OOD detection method, which operates on a model trained solely with ID data. In contrast, our method is trained on a combination of ID data and unlabeled data from $\\mathbb{P}_\\text{wild}$. OOD detection methods that use auxiliary data typically achieve significantly lower FPR compared to post-hoc methods. Therefore, a fairer comparison would be with methods trained on unlabeled data, such as Outlier Exposure, WOODS, and SCONE. Our method favorably outperforms these competitive baselines, including the state-of-the-art method SCONE [3].\n \n-----\nReferences\n\n[1] Ye, Haotian, et al. Towards a theoretical framework of out-of-distribution generalization. Advances in Neural Information Processing Systems 34 (2021): 23519-23531.\n\n[2] Chen, Xinlei, and Kaiming He. Exploring simple siamese representation learning. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021.\n\n[3] Bai, Haoyue, et al. Feed two birds with one scone: Exploiting wild data for both out-of-distribution generalization and detection. International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their time and commitment to providing valuable feedback and suggestions on our work. We are encouraged that reviewers find our idea to be **novel**,  **interesting**, and **effective** (DU8N, ureZ, 6JZj), that our theoretical insights are **sound and valuable** (DU8N, ureZ), and that our results are **comprehensive and significant** (ureZ, LF4w). We are also encouraged that reviewers recognize our method to be **scalable**, **computationally efficient** and **practical** for real-world data (ureZ, LF4w). Additionally, we appreciate the acknowledgment of our **clear writing and presentation** (DU8N, 6JZj, LF4w).

As recognized by multiple reviewers, the significance of our work can be summarized as follows:

- Our work offers a new algorithmic framework that leverages graph-theoretic formulation to jointly address OOD detection and generalization problems, which is more challenging than addressing either problem alone.
- The framework is grounded in the spectral decomposition of a graph, which can be equivalently realized by minimizing a surrogate contrastive learning objective. This approach enhances the computational efficiency and practicality of our framework.
- Our framework provides theoretical guarantees while demonstrating effectiveness across various real-world datasets. We include sufficient ablations and illustrative examples to aid readers in understanding our method.


We respond to each reviewer's comments in detail below. The PDF attached includes the visualization requested by Reviewer ureZ. In response to the valuable suggestions provided by the reviewers, we will further refine our manuscript to clarify aspects that could benefit from additional explanation.

Meta-review: All four reviewers expressed positive support to this work, which is considered to be theoretically sound and useful. Thus an accept is recommended.
Decision: Accept (poster)