When and How Does In-Distribution Label Help Out-of-Distribution Detection?

Xuefeng Duyyy
Yiyou Sunyyy
Yixuan Liyyy

yyyDepartment of Computer Sciences, UW-Madison

Yixuan<EMAIL_ADDRESS>
Machine Learning, ICML

Detecting data points deviating from the training distribution is pivotal for ensuring reliable machine learning. Extensive research has been dedicated to the challenge, spanning classical anomaly detection techniques to contemporary out-of-distribution (OOD) detection approaches. While OOD detection commonly relies on supervised learning from a labeled in-distribution (ID) dataset, anomaly detection may treat the entire ID data as a single class and disregard ID labels.
This fundamental distinction raises a significant question that has yet to be rigorously explored: when and how does ID label help OOD detection? This paper bridges this gap by offering a formal understanding to theoretically delineate the impact of ID labels on OOD detection. We employ a graph-theoretic approach, rigorously analyzing the separability of ID data from OOD data in a closed-form manner. Key to our approach is the characterization of data representations through spectral decomposition on the graph. Leveraging these representations, we establish a provable error bound that compares the OOD detection performance with and without ID labels, unveiling conditions for achieving enhanced OOD detection. Lastly, we present empirical results on both simulated and real datasets, validating theoretical guarantees and reinforcing our insights.   Code is publicly available at

§ INTRODUCTION

When deployed in the real world, machine learning models often encounter unfamiliar data points that fall outside the distribution of the observed data. This problem has been studied extensively, dating from the classical anomaly detection methods [Chandola et al., 2009, Ahmed & Courville, 2020, Han et al., 2022] to contemporary out-of-distribution (OOD) approaches [Liu et al., 2020, Yang et al., 2021, Fang et al., 2022].

While both anomaly detection and OOD detection share the goal of identifying test-time input that deviates from the training distribution, a crucial distinction lies in the usage of in-distribution (ID) labels in training time. Specifically, classical anomaly detection may disregard ID labels [Yang et al., 2021], treating the entire ID dataset as a single class. In contrast, OOD detection commonly relies on supervised learning from a labeled ID dataset. It is reasonable to hypothesize that incorporating ID labels during training might influence the resulting feature representations, potentially leading to distinct capabilities in separating ID from OOD samples during test time.  This raises a significant question that has yet to be rigorously explored in the field:

RQ: When and how does ID label help OOD detection?

Answering this question offers the fundamental key to understanding and bridging two highly related fields of anomaly detection and OOD detection. In pursuit of this objective, we provide a formal understanding to theoretically delineate the influence of ID labels on OOD detection. We base our analysis on a graph-theoretic approach by modeling the ID data via a graph, where the vertices are all the data points and edges encode the similarity among data. This analytical framework is well-suited for our investigation, as data points' representation similarity can differ between the self-supervised and supervised learning setting, contingent upon the availability of ID labels. For instance, when ID labels are present, the supervisory signal facilitates connecting points belonging to the same class, resulting in each class manifesting as a distinct connected sub-graph. In both cases (with or without ID labels), the sub-structures can be revealed by performing spectral decomposition on the graph and can be expressed equivalently as a contrastive learning objective on neural net representations (expounded further in Section <ref>). Importantly, these learned feature representations allow us to rigorously analyze the separability of ID data from OOD data in a closed-form manner.

Intuitive example on the ID labels' impact on OOD detection. (a) In the near OOD scenario where the OOD data connects densely with the ID data, without ID labels, the neural network produces indistinguishable embeddings for the ID (Ragdoll and Sphynx class) and OOD data (Scottish Fold class). By harnessing the power of the ID labeling information, the model learns more distinguishable embeddings that help ID vs. OOD separation. (b) In the far OOD scenario (Dog class), ID labels can be less beneficial because the representations learned in an unsupervised manner can already be separable between ID vs OOD.

Based on the analytical framework, we provide a formal error bound in Theorem <ref>, comparing the OOD detection performance with and without the inclusion of ID labels. This theorem reveals sufficient conditions for achieving improved OOD detection performance by leveraging ID labels. To establish the error bound, we first calculate the closed-form solution of the
ID and OOD representations based on the graph factorization and then quantify the OOD detection performance by linear probing error. As a result, Theorem <ref> demonstrates that the difference in the OOD detection performance with and without ID labels can be lower bounded by a function of the adjacency matrix of ID data as well as the OOD-ID connectivity. Furthermore, we offer intuitive interpretations in Theorem <ref>, and show that the ID labels are the most beneficial when either: (i) the OOD data is relatively close to the ID data, which is also known as the near OOD scenario; (ii) the ID data are connected sparsely without ID labels; and (iii) the semantic connection between each ID data to the
labeled ID data from different ID classes is sufficiently
large. To help readers understand the key insights of our theory, we provide a simple intuitive example in Figure <ref>, which demonstrates how adding ID labels in the near OOD scenario can lead to a greater benefit compared to the far OOD scenario.

Lastly, we provide empirical verifications to support our theory. In particular, we compare the OOD detection performance with and without ID labels using both simulated data and real-world datasets (Section <ref>). The result aligns with our
theoretical guarantee, showcasing the benefits of the ID label information under proper conditions. For example, the OOD detection result can be improved by 12.3% (AUROC) in the near OOD scenario compared to 6.06% in the far OOD scenario on Cifar100, validating our theory.

Our main contributions are summarized as follows:

* We study an important but underexplored problem: when and how in-distribution labels can help OOD detection. Our exposition has fundamental value in understanding and bridging the two highly related fields of anomaly
detection and OOD detection.

* We provide an analytical framework based on graph formulation to characterize the ID and OOD representations. Based on that, we analyze the error bound for ID vs. OOD separation with and without ID labels and investigate the necessary conditions for which the labeling information can bring the most benefits.

* We present empirical analysis on both simulated and real-world datasets to verify and support our theory. The observation in practice echoes and reinforces our theoretical insights.

§ PROBLEM SETUP

Let $\mathcal{X}$ be the input space, and $\mathcal{Y}=\{1,...,c\}$ be the label space for ID data. Given an unknown ID joint distribution $\mathbb{P}_{\mathcal{X}\mathcal{Y}}$ defined over $\mathcal{X}\times \mathcal{Y}$, the labeled ID data $\mathcal{S}_{\rm id}^{(l)} = \{(\*x_1, y_1),...,(\*x_N, y_N)\}$ are drawn independently and identically from $\mathbb{P}_{\mathcal{X}\mathcal{Y}}$. Alternatively, the unlabeled ID data $\mathcal{S}_{\rm id}^{(u)} =  \{\*x_1,...,\*x_N\}$ is  drawn from $\mathbb{P}_{\rm id}$, which is the marginal distribution of $\mathbb{P}_{\mathcal{X}\mathcal{Y}}$ on $\mathcal{X}$. Furthermore, we denote $\mathbb{P}_{l_i}$ the distribution of labeled data with label $i \in \mathcal{Y}$.

[Out-of-Distribution Detection w/ ID Labels]
Given labeled ID data
$\mathcal{S}_{\rm id}^{(l)}$,
the aim is to learn a predictor $\*g: \mathcal{X}\rightarrow \mathcal{Y} \cup \{ {\rm ood} \}$ such that for any test data $\mathbf{x}$:
1) if $\mathbf{x}$ is drawn from $\mathbb{P}_{\rm id}$, then the model classifies $\mathbf{x}$ into one of ID classes $\mathcal{Y}$, and 2)
if $\mathbf{x}$ is drawn from another distribution $\mathbb{P}_{\rm ood}$ with unknown OOD class, then $\*g$ can detect $\mathbf{x}$ as OOD data [Fang et al., 2022].

[Out-of-Distribution Detection w/o ID Labels]
The definition is similar to above, except that we are using unlabeled ID data $\mathcal{S}_{\rm id}^{(u)} =  \{\*x_1,...,\*x_N\}$ to learn the binary predictor $\*g$. This is in accordance with the classical anomaly detection problem [Chandola et al., 2009].

§ ANALYSIS FRAMEWORK

Overview of rationale. In this section, we introduce our analytical framework, which allows us to formalize and understand the OOD detection performance in two cases: (1) learning without ID labels, and (2) learning with ID labels, respectively.
Our analytical framework models the ID data via a graph, where the vertices are all the data points, and edges encode the similarity among data (Section <ref>). The similarity can be defined in either a self-supervised or supervised manner, contingent on the availability of the ID labels. For example, when ID labels are present, the supervision signal can help connect points belonging to the same class, so that each class emerges clearly as a connected sub-graph. In both cases, the sub-structures can be revealed by performing spectral decomposition on the graph and can be expressed equivalently as a contrastive learning objective on neural net representations (Section <ref>). Importantly, these learned feature representations allow us to rigorously analyze the separability of ID data from OOD data in a closed form. Since the features learned can be directly impacted by the presence or absence of ID labels, the OOD detection performance can vary accordingly.

§.§ Graph Formulation

We start by formally defining the graph and
adjacency matrix. For notation clarity, we use $\Bar{\*x}$ to indicate the natural sample (raw inputs without augmentation). Given an $\Bar{\*x}$, we use $\mathcal{T}(\*x|\Bar{\*x})$ to denote the probability of $\*x$ being augmented from $\Bar{\*x}$. For instance, when $\Bar{\*x}$ represents an image, $\mathcal{T}(\cdot|\Bar{\*x})$ can be the distribution of common augmentations [Chen et al., 2020] such as Gaussian blur, color distortion, and random cropping. The augmentation allows us to define a general population space $\mathcal{X}_\text{id}$, which contains all the original ID data points along with their augmentations. We denote the cardinality of the population space with $|\mathcal{X}_\text{id}|=N$.

We define the graph $G(\mathcal{X}_{\rm id}, \zeta)$ over the finite
vertex set $\mathcal{X}_\text{id}$ with edge weights $\zeta$. To define edge weights $\zeta$, we consider two cases: (1) self-supervised connectivity $\zeta^{(u)}$ by treating all points in $\mathcal{X}_{\rm id}$ as entirely unlabeled, and (2) supervised connectivity $\zeta^{(l)}$ by utilizing
labeling information of ID data.

[Unlabeled case (u)]
When all ID points are unlabeled, two samples ($\*x$, $\*x^+$) are considered a positive pair if $\*x$ and $\*x^+$ are augmented from the same image $\Bar{\*x} \sim \mathbb{P}_{\rm id}$.
For any two augmented data $\*x, \*x' \in \mathcal{X}_{\rm id}$, the edge weight $\zeta^{(u)}_{\*x \*x'}$ is defined as the marginal probability of generating the pair [HaoChen et al., 2021]:

\begin{align}
\zeta^{(u)}_{\*x \*x^{\prime}} \triangleq \mathbb{E}_{\Bar{\*x} \sim {\mathbb{P}}_{\rm id}}  \mathcal{T}(\*x| \Bar{\*x}) \mathcal{T}\left(\*x'| \Bar{\*x}\right).
\label{eq:def_wxx}
\end{align}

The magnitude of $\zeta^{(u)}_{\*x\*x'}$ indicates the “positiveness” or similarity between  $\*x$ and $\*x'$.

Alternatively, when having access to the labeling information for ID data, we can define the edge weight by adding additional supervised connectivity to the graph.

[Labeled case (l)]
When all ID points are labeled, two samples ($\*x$, $\*x^+$) are considered a positive pair if $\*x$ and $\*x^+$ are augmented from two labeled samples $\Bar{\*x}_{l}$ and $\Bar{\*x}'_{l}$ with the same ID class $i$. The overall edge weight for any pair of data $(\*x,\*x')$ is given by:

\begin{align*}
\small
\begin{split}
&\zeta^{(l)}_{\*x \*x^{\prime}} = \phi_{u} \cdot \zeta^{(u)}_{\*x \*x^{\prime}} + \phi_{l}  \cdot \sum_{i \in \mathcal{Y}}\mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathbb{E}_{\Bar{\*x}'_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}) \mathcal{T}\left(\*x' | \Bar{\*x}'_{l}\right),
\label{eq:def_wxx_b}
\end{split}
\end{align*}

where $\phi_{u},\phi_{l}$ are the weight coefficients. Compared to the unlabeled case, the second term strengthens the connectivity for points belonging to the same class.

[Adjacency matrix for unlabeled ID data]
We define the adjacency matrix $\*A^{(u)}$ with entry value $\zeta^{(u)}_{\*x \*x^{\prime}}$ for each $(\*x, \*x')$ pair . Further, $\zeta^{(u)}_\*x = \sum_{\*x' \in \mathcal{X}}\zeta^{(u)}_{\*x\*x'}$

denotes the total edge weights connected to a vertex $\*x$.

[Adjacency matrix for labeled ID data]
Similarly, we define the adjacency matrix for labeled ID data $\*A^{(l)}$ with entry value $\zeta^{(l)}_{\*x \*x^{\prime}}$ for each $(\*x, \*x')$ pair and $\zeta^{(l)}_\*x = \sum_{\*x' \in \mathcal{X}}\zeta^{(l)}_{\*x\*x'}$.

As a standard technique in graph theory [Chung, 1997], we use the normalized adjacency matrix of $G(\mathcal{X}_{\rm id}, \zeta)$:

\begin{equation}
\tilde{\*A}\triangleq \*D^{-\frac{1}{2}} \*A \*D^{-\frac{1}{2}},
\label{eq:def}
\end{equation}

where $\*A$ can be instantiated by either $\*A^{(u)}$ or $\*A^{(l)}$ defined above. ${\*D} \in \mathbb{R}^{N \times N}$ is the corresponding diagonal matrix with ${\*D}^{}_{\*x \*x}=\zeta^{(u)}_\*x$ for unlabeled case and ${\*D}^{}_{\*x \*x}=\zeta^{(l)}_\*x$ for labeled case. The normalization balances the degree of each node,  reducing the influence of vertices with very large degrees. The normalized adjacency matrix allows us to perform spectral decomposition as we show next.

§.§ Learning Representations Based on Graph Spectral

In this section, we perform spectral decomposition or spectral clustering [Ng et al., 2001]—a classical approach to graph
partitioning—to the adjacency matrices defined above. This process forms a matrix where the top-$k$ eigenvectors are the columns and each row of the matrix can be viewed as a $k$-dimensional representation of an example. The resulting
feature representations enable us to rigorously analyze the separability of ID data from OOD data in a closed form, and formally compare the OOD detection error under two scenarios either with and without ID labels (in Section <ref>).

Specifically, taking the labeled case as an example, we consider the following optimization, which performs low-rank matrix approximation on the adjacency matrix $\tilde{\*A}^{(l)}$:

\begin{equation}
\min _{\*F^{(l)} \in \mathbb{R}^{N \times k}} \mathcal{L}(\*F^{(l)}, {\*A}^{(l)})\triangleq\left\|\tilde{\*A}^{(l)}-\*F^{(l)} \*F^{(l)\top}\right\|_F^2,
\label{eq:lmf}
\end{equation}

where $\|\cdot\|_F$ denotes the matrix Frobenious norm. According to the Eckart–Young–Mirsky theorem [Eckart & Young, 1936], the minimizer of this loss function is $\*F_k^{(l)}\in \mathbb{R}^{N \times k}$ such that $\*F_k^{(l)} \*F_k^{(l)\top}$ contains the top-$k$ components of $\tilde{\*A}^{(l)}$'s eigen decomposition.

A surrogate objective. In practice, directly solving objective <ref> 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 [Sun et al., 2023, Sun et al., 2023] as shown in Lemma <ref>, which can be efficiently trained end-to-end using a neural net parameterized by $\*w$:

\begin{align}
\begin{split}
\mathcal{L}_\text{labeled}(\*h_\*w) &\triangleq - 2\phi_{l} \mathcal{L}_1(\*h_\*w)
- 2\phi_{u}  \mathcal{L}_2(\*h_\*w)  +\\& \phi_{l}^2 \mathcal{L}_3(\*h_\*w) + 2\phi_{l} \phi_{u} \mathcal{L}_4(\*h_\*w) +
\phi_{u}^2 \mathcal{L}_5(\*h_\*w),
\label{eq:def_SORL}
\end{split}
\end{align}
where $\*h_\*w:\mathcal{X}_{\rm id}\mapsto \mathbb{R}^k$ denotes the feature representation,

\begin{equation*}
\begin{aligned}
& \mathcal{L}_1(\*h_\*w) = \sum_{i \in \mathcal{Y}}\underset{\substack{\Bar{\*x}_{l} \sim \mathbb{P}_{{l_i}}, \Bar{\*x}'_{l} \sim \mathbb{P}_{{l_i}},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_{l}), \*x^{+} \sim \mathcal{T}(\cdot|\Bar{\*x}'_l)}}{\mathbb{E}}\left[\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{+}\right)\right] , \\&
\mathcal{L}_2(\*h_\*w) = \underset{\substack{\Bar{\*x}_{u} \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_{u}), \*x^{+} \sim \mathcal{T}(\cdot|\Bar{\*x}_u)}}{\mathbb{E}}
\left[\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{+}\right)\right], \\&
\mathcal{L}_3(\*h_\*w) = \sum_{i, j\in \mathcal{Y}}
% \sum_{j \in \mathcal{Y}_l}
\underset{\substack{\Bar{\*x}_l \sim \mathbb{P}_{{l_i}}, \Bar{\*x}'_l \sim \mathbb{P}_{{l_{j}}},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_l), \*x^{-} \sim \mathcal{T}(\cdot|\Bar{\*x}'_l)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{-}\right)\right)^2\right], \\&
\mathcal{L}_4(\*h_\*w) = \sum_{i \in \mathcal{Y}}\underset{\substack{\Bar{\*x}_l \sim \mathbb{P}_{{l_i}}, \Bar{\*x}_u \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_l), \*x^{-} \sim \mathcal{T}(\cdot|\Bar{\*x}_u)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{-}\right)\right)^2\right], \\&
\mathcal{L}_5(\*h_\*w) = \underset{\substack{\Bar{\*x}_u \sim \mathbb{P}_{\rm id}, \Bar{\*x}'_u \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_u), \*x^{-} \sim \mathcal{T}(\cdot|\Bar{\*x}'_u)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{-}\right)\right)^2\right].
\label{eq:def_SORL_detail}
\end{aligned}
\end{equation*}

At a high level, $\mathcal{L}_1,$ $\mathcal{L}_2$ push embeddings of positive pairs to be closer while $\mathcal{L}_3$, $\mathcal{L}_4$
and $\mathcal{L}_5$ pull away embeddings of negative pairs. Particularly, $\mathcal{L}_1$ samples two random augmentation views of two images from labeled data with the same label. $\mathcal{L}_2$ samples two views from the same image in $\mathcal{X}_{\rm id}$. For negative pairs, $\mathcal{L}_3$ uses two augmentation views from two labeled samples in $\mathcal{X}_{l}$ with any label. $\mathcal{L}_4$ uses two views of one sample in $\mathcal{X}_{l}$ and another one in $\mathcal{X}_{\rm id}$. $\mathcal{L}_5$ uses two views from two random samples in $\mathcal{X}_{\rm id}$.

Importantly, the contrastive loss allows drawing a theoretical equivalence between learned representations and the top-$k$ singular vectors of $\tilde{\*A}^{(l)}$, and facilitates theoretical understanding of the OOD detection on the data represented by $\tilde{\*A}^{(l)}$. We formalize the equivalence below.

We define each row $\*f_\*x^{\top}$ of $\*F^{(l)}$ as a scaled version of learned feature representation $\*h_\*w$, with $\*f_\*x = \sqrt{\zeta_\*x}\*h_\*w(\*x)$. Then minimizing the loss function $\mathcal{L}(\*F^{(l)}, \*A^{(l)})$ in Equation <ref> is equivalent to minimizing the surrogate loss in Equation <ref>. Full proof is in Appendix Section <ref>.

We can extend the contrastive learning objective in Equation <ref> to the unlabeled case by setting the coefficient $\phi_l$ to 0 and keeping the remaining parts:

\begin{align}
\begin{split}
\mathcal{L}_\text{unlabeled}(\*h_\*w) &\triangleq - 2\phi_{u} \mathcal{L}_2(\*h_\*w)
+  \phi_{u}^2 \mathcal{L}_5(\*h_\*w).
\label{eq:def_SORL_unlabeled}
\end{split}
\end{align}

The loss has been employed in prior works on spectral contrastive learning [Sun et al., 2023, Sun et al., 2023], which analyzed problems such as novel category discovery and open-world semi-supervised learning. However, our paper
focuses on the problem of OOD detection, which has fundamentally different learning goals. Accordingly, we derive novel theoretical analyses uniquely
tailored to our problem focus (i.e., the impact of the ID label information), which we present next.

§ THEORETICAL RESULTS

Based on the analytical framework, we now provide theoretical insights to the core question: when and how does ID label information help OOD detection? To answer this question, we start by deriving the closed-form solution of the representations for both ID and OOD data (Section <ref>), and then quantify the OOD detection
performance by measuring the linear probing error (Section <ref>). Finally, we provide a formal bound contrasting the OOD detection performance with and without ID labels (Section <ref>).

§.§ Representation for ID and OOD Data

ID representations. We first derive the ID representations for the labeled case, which can be similarly derived for the unlabeled case. Specifically, one can train the neural network $\*h_{\*w}: \mathcal{X}_\text{id} \rightarrow \mathbb{R}^k$ using the surrogate objective in Equation <ref>.  Minimizing the loss yields representation $\*Z^{(l)}\in \mathbb{R}^{N\times k}$, where each row vector $\*z_i = \*h_{\*w}(\*x_i)$. According to Lemma <ref>, the closed-form solution for the representations is equivalent to performing spectral decomposition of the adjacency matrix. Thus, we have $\*F_k^{(l)} = [{\*D^{(l)}}]^{\frac{1}{2}}\*Z^{(l)}$, where $\*F_k^{(l)} \*F_k^{(l)\top}$ contains the top-$k$ components of $\tilde{\*A}^{(l)}$'s SVD decomposition.
We further denote the top-$k$ singular vectors of $\tilde{\*A}^{(l)}$  as $\*V_k^{(l)} \in \mathbb{R}^{N\times k}$, so we have $\*F_k^{(l)} = \*V_k^{(l)} [\*\Sigma_k^{(l)}]^{\frac{1}{2}}$, where $\*\Sigma_k^{(l)}$ is a diagonal matrix of the top-$k$ singular values of $\tilde{\*A}^{(l)}$.
By equalizing the two forms of $\*F_k^{(l)}$, the closed-formed solution of the learned feature space is given by

\begin{equation}
\*Z^{(l)} = [\*D^{(l)}]^{-\frac{1}{2}} \*V_k^{(l)} [\*\Sigma_k^{(l)}]^{\frac{1}{2}}.
\label{labeled_id_feat}
\end{equation}

Example showcasing the contrast between adjacency matrices and representations w/ (l) and w/o (u) ID labels. (a) The ID adjacency matrix in the labeled case $\*A^{(l)}$. (b) The ID adjacency matrix in the unlabeled case $\*A^{(u)}$. Here darker color indicates denser connectivity. The contrast of the OOD-ID adjacency matrix $\tilde{\*A}_{\rm OI}$ w/ and w/o ID labels in the near OOD and far OOD scenario is shown in (c) and (d), where the adjacency matrices have a larger Frobenius norm, i.e., $\|\tilde{\*A}_{\rm OI}^{(u)}\|_F=60$ in the near OOD scenario and smaller norm in the far OOD scenario, i.e., $\|\tilde{\*A}_{\rm OI}^{(u)}\|_F=24$. (e) Learned representations in the near OOD scenario, where the OOD representations are overlapped in the unlabeled case but become linearly separable from the ID representations in the labeled case. (d) Representations in the far OOD scenario. The ID and OOD representations can already be separable in the unlabeled case. The benefit of ID labels is marginal.

OOD representations. In post hoc OOD detection, the learning algorithm can only observe ID data in $\mathcal{X}_{\rm id}$ and the corresponding adjacency matrix. Hence, a key challenge in our framework is how to derive the OOD representations based on ID and OOD data connectivity in the input space. Unlike previous literature [Lee et al., 2018], we refrain from making simplified assumptions in the feature representation space (although that makes analysis much easier). More realistically, we characterize OOD data directly in the input space by the adjacency matrix $\tilde{\*A}_{\rm OI}^{(l)} \in \mathbb{R}^{M \times N}$, where $M$ is the number of OOD data points.

Each row in the matrix indicates the similarity between an OOD data w.r.t. all the ID samples. Depending on the characteristics of the OOD data, this matrix may be sparse if OOD data is far away from all the ID samples (e.g., far OOD), or can have dense entries if it is close to some ID classes (e.g., near OOD). Our characterization is thus general enough to enable analysis under different scenarios.

Now a question remains: how do we go from this matrix $\tilde{\*A}_{\rm OI}^{(l)}$ to a $k$-dimensional embedding for each OOD data? While a naive solution is to perform spectral decomposition on the stack of two matrices $\tilde{\*A}_{\rm OI}^{(l)}$ and $\tilde{\*A}^{(l)}$, this violates the principle of post hoc OOD detection as it incurs retraining. Instead, we derive the embeddings of OOD vertices using
existing ID embeddings $\*F^{(l)}$ and the OOD-ID similarity. This can be achieved by solving the following optimization:

\begin{equation}
\min _{\*F_{\rm ood}^{(l)} \in \mathbb{R}^{M \times k}} \left\|\tilde{\*A}_{\rm OI}^{(l)} - \*F_{\rm ood}^{(l)} \*F^{(l)\top}\right\|_F^2,
\label{aoi_optimization}
% \vspace{-0.5em}
\end{equation}

where $\*F_{\rm ood}^{(l)}$ denotes the OOD embeddings. Intuitively, the objective distills the similarity in the input space into the representation space.
For instance, it searches for an OOD representation, aligning it closely with ID representations when there is a dense connectivity between OOD and ID data in the adjacency matrix, and vice versa. Similar to the ID case, we have $\*Z_{\rm ood}^{(l)} =[{\*D_{\rm ood}^{(l)}}]^{-\frac{1}{2}}\*F_{\rm ood}^{(l)} $, where $\*D_{\rm ood}^{(l)}$ can be calculated in the same way as $\*D^{(l)}$ based on $\tilde{\*A}_{\rm OI}^{(l)}$. Therefore, the analytic form of the OOD representations from the neural network can be derived as
\begin{equation}
\*Z_{\rm ood}^{(l)} = [\*D_{\rm ood}^{(l)}]^{-\frac{1}{2}} \tilde{\*A}_{\rm OI}^{(l)}  \mathbf{V}_k^{(l)}  [\mathbf{\Sigma}_k^{(l)}]^{-\frac{1}{2}}.
\label{labeled_ood_feat}
\end{equation}

Detailed proof and the design rationale are in Appendix <ref>.

Representation in the unlabeled case. For the unlabeled case, we can get the representations for ID and OOD data by replacing the matrices $\*V_k^{(l)}, \*\Sigma_k^{(l)}, \*D^{(l)}, \*D_{\rm ood}^{(l)}$ and $\tilde{\*A}_{\rm OI}^{(l)}$  in Equations <ref>  and <ref> with the unlabeled version. We will show how the labeled and unlabeled representations are rigorously related in Appendix <ref>.

An illustrative example. To contrast the adjacency matrices and the corresponding representations for the unlabeled and labeled cases, we simulate an example in Figure <ref>. The simulation is constructed with simplicity in mind, to
facilitate understanding. Evaluations on complex high-dimensional data will be provided in Section <ref>. In particular, we base our analysis on the ID adjacency matrix as depicted in  Figure <ref> (a) and (b), which consists of three ID classes and 40 data points for each class. In the labeled case, the ID adjacency matrix has a denser connectivity pattern, especially for data that belongs to the same ID label. In Figure <ref> (c) and (d), we compare the OOD-ID adjacency matrices with and without ID labels in two scenarios, i.e., near OOD where there are dense connections in $\tilde{\*A}_{\rm OI}$ and far OOD where the connectivity in $\tilde{\*A}_{\rm OI}$ is sparse.

Based on the graph, we further visualize in Figures <ref> (e) and (f) the 2D data representations ($k=2$, calculated by Equations <ref>  and <ref>) for the near OOD and far OOD scenarios.  We observe that having different adjacency matrices can lead to significantly different data representations. We will provide theory to rigorously analyze the OOD detection performance and contrast between the labeled and unlabeled cases (Section <ref>). Details of the illustrative example are included in Appendix <ref>.

§.§ Evaluation Target

With the closed-form representations for both ID and OOD, we evaluate OOD detection by linear probing error. The strategy is
commonly used in representation learning [Chen et al., 2020].
Specifically, the weight of a linear classifier is denoted as $\boldsymbol{\theta}\in \mathbb{R}^{k\times 2}$. The class prediction (ID vs. OOD) is given by $\*g_{\boldsymbol{\theta}}(\*z) = {\rm argmax}_{i \in \{+,-\}} (\*h_\*w(\*x) \boldsymbol{\theta})_i$. Denote the set of ID and OOD features as ${\*Z}_{\rm all} \in \mathbb{R}^{(N+M) \times  k} = [\*Z^\top, \*Z_{\rm ood}^\top]^\top$ (either labeled (u) or unlabeled (l)), the linear probing
error $R({\*Z}_{\rm all}) $ is given by the least error of all possible linear classifiers:

\begin{equation}
R({\*Z}_{\rm all}) \triangleq \min _{\boldsymbol{\theta} \in \mathbb{R}^{k \times 2 }} \mathbb{E}_{\*z \in {\*Z}_{\rm all}} \mathds{1}[y(\*z) \neq \*g_{\boldsymbol{\theta}}(\*z)],
% \vspace{-1em}
\end{equation}

where $y(\*z)$ denotes indicates the ground-truth class of feature $\*z$ (ID or OOD). With the definition, we can bound the
linear probing error $R({\*Z}_{\rm all}) $ by the residual of the regression error as shown in Lemma <ref> with proof in Appendix <ref>.

Denote $\*y\in \mathbb{R}^{(N+M)\times 2}$ as a matrix where each row contains the one-hot label for features in ${\*Z}_{\rm all}$. We have:

\begin{equation}
% \small
\label{eq:lp_loss}
R({\*Z}_{\rm all}) \leq  \frac{2}{N+M}\operatorname{Tr}\left(\left(\mathbf{I}- {\*Z}_{\rm all} {\*Z}_{\rm all}^{\dagger}\right) \mathbf{y} \mathbf{y}^\top\right).
\end{equation}

Here $\operatorname{Tr}\left(\cdot \right)$ denotes the trace operator. $ {\*Z}_{\rm all}^{\dagger}$ is the Moore-Penrose inverse of matrix ${\*Z}_{\rm all}$. We denote this upper bound as $\overline{R}({\*Z}_{\rm all}) $, which is more tractable to analyze and behaves similarly to $R({\*Z}_{\rm all})$ as shown in Appendix <ref>. Therefore our subsequent analysis revolves around it.

§.§ Error Bound on OOD Detection Performance

With the evaluation target defined above, we now present the formal error bound on OOD detection performance
by contrasting the labeled and unlabeled cases. As an overview,
Theorem <ref>  will present the lower bound of linear probing
error difference between the unlabeled and label case, along with an intuitive version in Theorem <ref>. We specify several mild assumptions and necessary notations for our theorems in Appendix <ref>. Due to space limitation, we omit unimportant constants and simplify the statements of our theorems. We defer the full formal statements in  Appendix <ref>. All proofs can be found in Appendix <ref>.

Error difference between unlabeled and labeled cases. Formally, we investigate the following linear probing error
difference between the unlabeled and labeled case:

\begin{equation}
\mathcal{G} = \overline{R}(  {\*Z}_{\rm all}^{(u)}) - \overline{R}({\*Z}_{\rm all}^{(l)}),
% \vspace{-1em}
\label{eq:error_diff}
\end{equation}

where a larger error difference indicates that labeled ID data benefits OOD detection more substantially, and vice versa. The lower bound on $\mathcal{G}$ is given by the following theorem.

(Informal.) Suppose we have  adjacency matrices $\tilde{\*A}^{(u)}, \tilde{\*A}^{(l)}\in \mathbb{R}^{N \times N}$ and $\tilde{\*A}_{\rm OI}^{(u)}, \tilde{\*A}_{\rm OI}^{(l)} \in \mathbb{R}^{M \times N}$  for both the labeled and unlabeled cases. Under mild conditions, given positive constants $\phi_l, C$, the error difference $ \mathcal{G}$  in Equation <ref> is lower bounded by

\begin{equation}
% \small
\begin{aligned}
\mathcal{G} &\geq      \frac{C   \phi_l}{N+M} \epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} ),
\label{main_error_bound}
\end{aligned}
\end{equation}

where $\mathfrak{q} \in \mathbb{R}^{N\times c}$ with each column defined as $(\mathfrak{q}_i)_\*x = \mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}), \*x \in \mathcal{X}_{\rm id}$. Similarly, $\mathfrak{p}\in \mathbb{R}^{M\times c}$ is defined as $(\mathfrak{p}_i)_\*x = \mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}), \*x \in \mathcal{X}_{\rm ood}$. Semantically, each entry in $\mathfrak{q}$ means the connection magnitude from $\*x$ to all ID data while each entry in $\mathfrak{p}$ is the connection from $\*x$ to OOD data. Furthermore,

\begin{equation*}
% \small
\begin{aligned}
&  \epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} )  =  2 \sum_{i=1}^{c} \operatorname{Tr}\left(\mathfrak{p}_i\mathfrak{q}_i^\top \cdot   \tilde{\*A}_{\rm OI}^{(u)\top}\right)  +  \\ & \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2  \right)  \sum_{i=1}^c \|\mathfrak{q}_i\|_F^2 + \\ &
r^2\left( \|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \| \tilde{\*A}^{(u)}\|_F^2  \frac{ 2(\tau- k)}{\tau-1} -2\right)   \cdot \sum_{i=1}^c \|\mathfrak{q}_{i}\|_1,
\end{aligned}
\label{epsilon_def_main}
% \vspace{-1em}
\end{equation*}

where $\tau$ is a constant that measures the $k$-th spectral gap of matrix $\tilde{\*A}^{(u)}$, i.e., $\boldsymbol{\lambda}_{k}^{(u)} \geq \tau \boldsymbol{\lambda}_{k+1}^{(u)}$ and $\boldsymbol{\lambda}_{k}^{(u)} $ is the $k$-th largest singular value of $\tilde{\*A}^{(u)}$. $r$ is the maximum $l_2$ norm of the ID representations, i.e.,  $r = \max_{\*z \in \*Z^{(u)}} \|\*z\|_2$.

Theorem <ref> is a general characterization of the error difference in the labeled and unlabeled cases. To gain a better insight, we introduce
Theorem <ref> which provides intuition interpretations.

OOD category        OOD dataset     ID labels     FPR95$\downarrow$     AUROC$\uparrow$     LP error$\downarrow$       FPR95$\downarrow$     AUROC$\uparrow$     LP error$\downarrow$

3c $\mathbb{P}_{\rm ood}^{\rm test} =\mathbb{P}_{\rm ood}^{\rm LP} $           3c  $\mathbb{P}_{\rm ood}^{\rm test} \neq\mathbb{P}_{\rm ood}^{\rm LP} $

10*Far OOD           2*Svhn          -     0.09$^{\pm 0.02}$   99.96$^{\pm 0.01}$    0.02$^{\pm 0.00}$       75.62$^{\pm 4.74}$     77.09$^{\pm 2.17}$     0.52$^{\pm 0.21}$

+    [HTML]EFEFEF0.07$^{\pm 0.00}$   [HTML]EFEFEF99.97$^{\pm 0.03}$     [HTML]EFEFEF0.02$^{\pm 0.00}$      [HTML]EFEFEF68.73$^{\pm 5.03}$     [HTML]EFEFEF82.97$^{\pm 1.87}$      [HTML]EFEFEF0.48$^{\pm 0.28}$

2*Textures         -     0.37$^{\pm 0.20}$   99.80$^{\pm 0.15}$    0.02$^{\pm 0.00}$    86.35$^{\pm 2.47}$       70.94$^{\pm 3.77}$     1.05$^{\pm 0.17}$

+    [HTML]EFEFEF0.24$^{\pm 0.19}$   [HTML]EFEFEF99.86$^{\pm 0.11}$     [HTML]EFEFEF0.01$^{\pm 0.00}$     [HTML]EFEFEF86.44$^{\pm 0.58}$     [HTML]EFEFEF75.15$^{\pm 3.36}$      [HTML]EFEFEF0.95$^{\pm 0.10}$

2*Places365         -     0.68$^{\pm 0.10}$   99.98$^{\pm 0.00}$     0.02$^{\pm 0.01}$    75.35$^{\pm 2.78}$       79.85$^{\pm 1.85}$     0.83$^{\pm 0.27}$

+   [HTML]EFEFEF0.44$^{\pm 0.06}$   [HTML]EFEFEF99.99$^{\pm 0.01}$     [HTML]EFEFEF0.02$^{\pm 0.01}$     [HTML]EFEFEF66.60$^{\pm 1.61}$     [HTML]EFEFEF85.03$^{\pm 3.19}$     [HTML]EFEFEF0.74$^{\pm 0.09}$

2*Lsun-Resize          -     0.24$^{\pm 0.03}$   99.95$^{\pm 0.03}$      0.02$^{\pm 0.00}$      83.57$^{\pm 2.89}$     77.57$^{\pm 5.21}$    0.84$^{\pm 0.21}$

+    [HTML]EFEFEF0.24$^{\pm 0.01}$   [HTML]EFEFEF99.91$^{\pm 0.07}$     [HTML]EFEFEF0.02$^{\pm 0.01}$   [HTML]EFEFEF74.13$^{\pm 4.95}$     [HTML]EFEFEF82.71$^{\pm 1.64}$     [HTML]EFEFEF0.75$^{\pm 0.14}$

2*Lsun-C          -     1.68$^{\pm 0.36}$   99.20$^{\pm 0.17}$    0.05$^{\pm 0.01}$     63.42$^{\pm 6.16}$     83.43$^{\pm 3.48}$     0.82$^{\pm 0.38}$

+     [HTML]EFEFEF1.04$^{\pm 0.41}$   [HTML]EFEFEF99.35$^{\pm 0.08}$      [HTML]EFEFEF0.04$^{\pm 0.02}$   [HTML]EFEFEF51.36$^{\pm 2.26}$     [HTML]EFEFEF89.49$^{\pm 1.91}$      [HTML]EFEFEF0.72$^{\pm 0.41}$

2*Near OOD         2*Cifar10          -    62.20$^{\pm 3.49}$   85.93$^{\pm 1.72}$    0.27$^{\pm 0.11}$    94.54$^{\pm 0.79}$     55.42$^{\pm 1.64}$     0.97$^{\pm 0.18}$

+    [HTML]EFEFEF58.28$^{\pm 2.90}$   [HTML]EFEFEF89.01$^{\pm 0.98}$     [HTML]EFEFEF0.19$^{\pm 0.05}$   [HTML]EFEFEF91.07$^{\pm 3.28}$     [HTML]EFEFEF67.72$^{\pm 0.97}$     [HTML]EFEFEF0.85$^{\pm 0.32}$

OOD detection results w/ and w/o ID labels (Cifar100 as ID). Mean and std are estimated on three different runs. Better results are highlighted in bold. “+,-" denotes the labeled and unlabeled case. “LP error" denotes the error of linear probing. $\uparrow$ indicates larger values are better,
and $\downarrow$ indicates smaller values are better. The table shows that (1) the ID labeling information helps OOD detection, especially in the near OOD scenario and when  $\mathbb{P}_{\rm ood}^{\rm test} =\mathbb{P}_{\rm ood}^{\rm LP} $; Moreover, our observations can generalize to the case where the OOD distribution in linear probing is not the same as that in actual testing ($\mathbb{P}_{\rm ood}^{\rm test} \neq \mathbb{P}_{\rm ood}^{\rm LP} $), showcasing the generality of our theory.

Under the same conditions in Theorem <ref>, assume the $k$-th spectral gap of $\tilde{\*A}^{(u)}$ is sufficiently large, i.e., $\tau>k$, then the main error component $ \epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} )  $ in Equation <ref> satisfies

\begin{equation*}
\small
\begin{aligned}
\epsilon(\mathfrak{p}, \mathfrak{q},&\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} )  \geq \\& \left[1+ \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2\left( 2N^2-   \|\tilde{\*A}^{(u)}\|_F^2    \right)  \right] \|\mathfrak{q}\|_F^2.
\end{aligned}
\end{equation*}

Interpretation and key insights. Theorem <ref> shows that the optimal scenarios for achieving the greatest reduction in linear probing error—signifying the most significant benefit by incorporating the ID labels, are when

* The ID data are connected sparsely in the unlabeled case (i.e., $ \|\tilde{\*A}^{(u)}\|_F^2 < 2N^2$), which always holds because $\|\tilde{\*A}^{(u)}\|_{\infty}< N$;

* The OOD data is closely connected to the ID data (near OOD, i.e., $\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2$ is relatively large);

* The semantic connection between each ID data to the labeled ID data from different ID classes is sufficiently large (i.e., $\|\mathfrak{q}\|_F^2$ is large).

Moreover, the simplified bound also enables us to interpret the relationship of each key component with the error reduction $\mathcal{G}$. For example, 1) the bound will monotonically increase when the connection within ID data in the unlabeled case becomes sparser (i.e., $\|\tilde{\*A}^{(u)} \|_F^2$ $\downarrow$); 2) Since $\|\tilde{\*A}^{(u)} \|_F^2$ is smaller than $2N^2$, strengthening the semantic connection from each ID data to the labeled data from different ID classes (i.e., $\|\mathfrak{q}\|_F^2$ $\uparrow$) is always helpful. Intuitively, a larger $\|\mathfrak{q}\|_F^2$ means one ID data point is more likely to be augmented from another ID data;
3) If the ID and OOD data are closer ($\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2$ $\uparrow$), the value of the bound will increase given the same $\mathfrak{q}$ and $\tilde{\*A}^{(u)}$.

Verification of bound on the illustrative example. Our theoretical guarantee aligns well with the empirical results. For example, in Figure <ref> (e) where the OOD data is densely connected to the ID data (near OOD case),  the ID labels can better shape the ID and OOD representations compared to the unlabeled case, rendering them linearly separable. As a result, the linear probing error is reduced from 0.09 in the unlabeled case to 0 in the labeled case.  In contrast, when the OOD data is far from the ID data (Figure <ref> (f)), the representations for ID and OOD are already well separated in the unlabeled case, and thus the benefit of ID labels is relatively marginal. As a verification, the linear probing error remains 0 both with and without ID labels. Therefore, these observations align with our key insight on the effect of OOD-ID connection $\tilde{\*A}_{\rm OI}^{(u)}$ on the error difference for linear probing. Moreover, we provide additional visualization results on changing the Frobenius norm of the ID adjacency matrix $\tilde{\*A}^{(u)}$ and the semantic connection $\mathfrak{q}$ in Appendix <ref>.

§ EXPERIMENTS ON REAL DATASETS

In this section, we verify our theoretical results using real-world OOD detection benchmarks.

Experimental setup. For ID datasets, we use Cifar10 and Cifar100 [Krizhevsky et al., 2009]. We first train the neural network on the ID data for 200 epochs with a ResNet-18 [He et al., 2016], using objective $\mathcal{L}_\text{unlabeled}$ and $\mathcal{L}_\text{labeled}$ for the unlabeled and labeled case, respectively. The penultimate layer embedding dimension $k=512$. We then extract the embeddings for the ID and OOD data and perform linear probing (50 epochs). We explore two different scenarios depending on whether the OOD in linear probing ($\mathbb{P}_{\rm ood}^{\rm LP}$) is the same as the test OOD ($\mathbb{P}_{\rm ood}^{\rm test}$). In the first scenario ($\mathbb{P}_{\rm ood}^{\rm test} =\mathbb{P}_{\rm ood}^{\rm LP} $), we use 75% of the OOD dataset for linear probing and the remaining for testing. Specifically, for far OOD test datasets, we use a suite of natural image datasets including Textures [Cimpoi et al., 2014], Svhn [Netzer et al., 2011], Places365 [Zhou et al., 2017], and Lsun [Yu et al., 2015]. For near OOD, we evaluate on Cifar10 when Cifar100 is ID and vice versa. In the second scenario ($\mathbb{P}_{\rm ood}^{\rm test} \neq \mathbb{P}_{\rm ood}^{\rm LP} $), we use 300K Random Images [Hendrycks et al., 2019] for linear probing and the other OOD datasets for evaluation. More experiment details are in Appendix <ref>.

Evaluation metrics. We report the following metrics: (1) the false positive rate (FPR95$\downarrow$) of OOD samples when the true positive rate of ID samples is 95%, (2) the area under the receiver operating characteristic curve (AUROC$\uparrow$), and (3) the linear probing error (LP error $\downarrow$).

Experiment results. The results are shown in Table <ref>, which demonstrate that: (1) the ID labeling information helps OOD detection, especially in the near OOD scenario and when  $\mathbb{P}_{\rm ood}^{\rm test} =\mathbb{P}_{\rm ood}^{\rm LP} $. For example, the AUROC is improved by 3.08% on Cifar10 compared to 0.02% on Svhn, echoing our theoretical insights; (2) Our observations can generalize to the case where the OOD distribution in linear probing is not the same as that in actual testing ($\mathbb{P}_{\rm ood}^{\rm test} \neq \mathbb{P}_{\rm ood}^{\rm LP} $), where the AUROC increases by 12.3% compared to the unsupervised counterpart on Cifar10, showcasing the flexibility and generality of our theory. Additional results on Cifar10 as the ID dataset and the evaluation using post-hoc OOD detection score are shown in Appendix <ref>.

Verification of bound. We verify the error difference $\mathcal{G}$ and its relationship to the Frobenius norm of the adjacency matrices $\tilde{\*A}^{(u)}$ and $\tilde{\*A}_{\rm OI}^{(u)}$. Firstly, to verify how the value of $\mathcal{G}$ will change given a larger Frobenius norm of $\tilde{\*A}_{\rm OI}^{(u)}$, we compare the linear probing error on Svhn and Cifar10 in Table <ref> with and without ID labels, where the error difference on Cifar10 (near OOD, with larger $\|\tilde{\*A}_{\rm OI}^{(u)}\|_F$) is consistently larger than that on Svhn (far OOD).

OOD dataset     1cSvhn      1cC10

Far OOD    Near OOD

$\| \tilde{\*A}_{\rm OI}^{(u)} \|_F$  $\uparrow$      $2334$    $2739$

$\mathcal{G}$ $\uparrow$     0.00     0.08

Verification with different $\| \tilde{\*A}_{\rm OI}^{(u)} \|_F$ (Cifar100 as ID).

In addition, we verify the relationship of $\|\tilde{\*A}^{(u)}\|_F$ and the error difference (Cifar10 as OOD) in Table <ref>. Specifically, we calculate the norm of the ID adjacency matrix from different training epochs and observe that the difference in linear probing error tends to increase with decreasing $\|\tilde{\*A}^{(u)}\|_F$, which aligns with Theorem <ref>. Additional results and details are included in Appendix <ref>. We further analyze the tightness of our bound in Appendix <ref>.

Epochs      40     80     120      160    200     240

$\| \tilde{\*A}^{(u)} \|_F$ $\downarrow$      20191     19549    18939     16073    15509     14810

$\mathcal{G}$ $\uparrow$     0.01    0.03     0.06     0.06    0.08    0.09

Verification with different $\| \tilde{\*A}^{(u)} \|_F$ (Cifar100 as ID).

§ RELATED WORK

OOD detection has attracted a surge of interest in recent years [Fort et al., 2021, Yang et al., 2021, Fang et al., 2022, Zhu et al., 2022, Ming et al., 2022, Ming et al., 2022, Yang et al., 2022, Wang et al., 2022, Galil et al., 2023, Djurisic et al., 2023, Zheng et al., 2023, Wang et al., 2022, Wang et al., 2023, Narasimhan et al., 2023, Yang et al., 2023, Uppaal et al., 2023, Zhu et al., 2023, Zhu et al., 2023, Ming & Li, 2023, Zhang et al., 2023, Ghosal et al., 2024]. One line of work performs OOD detection by devising scoring functions, including confidence-based methods [Bendale & Boult, 2016, Hendrycks & Gimpel, 2017, Liang et al., 2018], energy-based score [Liu et al., 2020, Wang et al., 2021, Wu et al., 2023], distance-based approaches [Lee et al., 2018, Tack et al., 2020, Ren et al., 2021, Sehwag et al., 2021, Sun et al., 2022, Du et al., 2022, Ming et al., 2023, Ren et al., 2023], gradient-based score [Huang et al., 2021], and Bayesian approaches [Gal & Ghahramani, 2016, Lakshminarayanan et al., 2017, Maddox et al., 2019, Malinin & Gales, 2019, Wen et al., 2020, Kristiadi et al., 2020]. Another  line of work addressed OOD detection by training-time regularization [Bevandić et al., 2018, Malinin & Gales, 2018, Geifman & El-Yaniv, 2019, Hein et al., 2019, Meinke & Hein, 2020, Jeong & Kim, 2020, Liu et al., 2020, van Amersfoort et al., 2020, Yang et al., 2021, Wei et al., 2022, Du et al., 2022, Du et al., 2023, Wang et al., 2023].  For example, the model is
regularized to produce lower confidence [Lee et al., 2018] or higher energy [Liu et al., 2020, Du et al., 2022] on a set of clean OOD data [Hendrycks et al., 2019, Ming et al., 2022], wild data [Zhou et al., 2021, Katz-Samuels et al., 2022, He et al., 2023, Bai et al., 2023, Du et al., 2024] and synthetic outliers [Du et al., 2023, Tao et al., 2023, Park et al., 2023]. Additionally, a similar topic in a different domain, i.e., anomaly detection, often restricts the ID
(normality) to be with a single class and with a different definition of the outliers [Chandola et al., 2009, Han et al., 2022].

Most OOD detection methods rely on the supervision of ID labels, and there have been prior works, such as [Tack et al., 2020, Sehwag et al., 2021, Sun et al., 2022] that empirically verified that training with the ID labels can achieve a much better OOD detection performance compared to the unsupervised version, but a provable analysis of their impact is critical yet missing in the field.

OOD detection theory. Recent studies have begun to focus on the theoretical understanding of OOD detection.  Fang et al., 2022 studied the generalization of
OOD detection by PAC learning and they found a necessary condition for the learnability of OOD
detection. Morteza & Li, 2022 derived a novel OOD score and provided a provable understanding of the OOD detection result using that score. Du et al., 2024 theoretically studied the impact of unlabeled data for OOD detection. In contrast, we formally analyze the impact of ID labels on OOD detection, which has not been studied in the past.

Spectral graph theory is a classical research problem [Von Luxburg, 2007, Chung, 1997, Cheeger, 2015, Kannan et al., 2004, Lee et al., 2014, McSherry, 2001], which aims to partition the graph by studying the eigenspace of the adjacency matrix. Recently, it has been applied in different applications in machine learning [Ng et al., 2001, Shi & Malik, 2000, Blum, 2001, Zhu et al., 2003, Argyriou et al., 2005, Shaham et al., 2018]. HaoChen et al., 2021 derived the spectral contrastive learning from the factorization of the graph's adjacency matrix, and provably understand unsupervised domain adaptation [Shen et al., 2022, HaoChen et al., 2022]. Sun et al., 2023, Sun et al., 2023 expanded the spectral contrastive learning approach to novel class discovery and open-world semi-supervised learning. Our focus is on the OOD detection problem, which differs from prior literature.

§ CONCLUSION

In this paper, we propose a novel analytical framework that studies the impact of ID labels on OOD detection. Our framework takes a graph-theoretic approach by modeling
the ID data via a graph, which allows us to characterize the feature representations by performing
spectral decomposition on the graph that can be expressed
equivalently as a contrastive learning objective on neural
net representation. Leveraging these representations, we establish a provable
error bound that compares the OOD detection
performance with and without
ID labels, which reveals sufficient conditions for
achieving improved OOD detection performance. Empirical observations further support our theoretical conclusions, showcasing the benefits of ID labeling information under proper
conditions. We hope our work will inspire future research on the theoretical understanding of OOD detection. One promising direction is to analyze the setting where there is access to OOD samples, which belongs to an important branch of work in OOD detection literature.

§ ACKNOWLEDGEMENT

We thank Hyeong Kyu (Froilan) Choi and Shawn Im for their valuable suggestions on the draft. The authors would also like to thank
ICML anonymous reviewers for their helpful feedback. Du is supported by the Jane Street Graduate
Research Fellowship. Li gratefully acknowledges the support from the AFOSR
Young Investigator Program under award number FA9550-23-1-0184, National Science Foundation
(NSF) Award No. IIS-2237037 & IIS-2331669, Office of Naval Research under grant number
N00014-23-1-2643, Philanthropic Fund from SFF, and faculty research awards/gifts from Google
and Meta.

§ IMPACT STATEMENT

Our paper aims to improve the reliability and safety of modern machine learning models.  From the theoretical perspective, our analysis can facilitate and deepen the understanding of the effect of in-distribution labels for OOD detection. In Appendix <ref> and Section <ref> of the main paper, we properly verify the necessary conditions and the value of our bound using real-world datasets. Hence, we believe our theoretical framework has a broad utility and significance.

From the practical side,  our study can lead to direct benefits and societal impacts by deploying OOD detection techniques, particularly when practitioners need to determine how to better leverage the in-distribution labels, such as in safety-critical applications
i.e., autonomous driving and healthcare data analysis.  Our study does not involve any human subjects or violation of legal compliance. We do not anticipate any potentially harmful consequences to our work. Through our study and releasing our code, we hope to raise stronger research and societal awareness on the safe handling of out-of-distribution data in real-world settings.

[Ahmed & Courville, 2020]
Ahmed, F. and Courville, A.
Detecting semantic anomalies.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.  3154–3162, 2020.

[Argyriou et al., 2005]
Argyriou, A., Herbster, M., and Pontil, M.
Combining graph laplacians for semi–supervised learning.
Advances in Neural Information Processing Systems, 18, 2005.

[Bai et al., 2023]
Bai, H., Canal, G., Du, X., Kwon, J., Nowak, R. D., and Li, Y.
Feed two birds with one scone: Exploiting wild data for both out-of-distribution generalization and detection.
In International Conference on Machine Learning, 2023.

[Baksalary & Puntanen, 1992]
Baksalary, J. K. and Puntanen, S.
An inequality for the trace of matrix product.
IEEE transactions on automatic control, 370 (2):0 239–240, 1992.

[Belkin & Niyogi, 2003]
Belkin, M. and Niyogi, P.
Laplacian eigenmaps for dimensionality reduction and data representation.
Neural computation, 150 (6):0 1373–1396, 2003.

[Belkin et al., 2006]
Belkin, M., Niyogi, P., and Sindhwani, V.
Manifold regularization: A geometric framework for learning from labeled and unlabeled examples.
Journal of Machine Learning Research, 70 (85):0 2399–2434, 2006.

[Bendale & Boult, 2016]
Bendale, A. and Boult, T. E.
Towards open set deep networks.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.  1563–1572, 2016.

[Bengio et al., 2003]
Bengio, Y., Paiement, J.-f., Vincent, P., Delalleau, O., Roux, N., and Ouimet, M.
Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering.
Advances in neural information processing systems, 16, 2003.

[Bevandić et al., 2018]
Bevandić, P., Krešo, I., Oršić, M., and Šegvić, S.
Discriminative out-of-distribution detection for semantic segmentation.
arXiv preprint arXiv:1808.07703, 2018.

[Blum, 2001]
Blum, A.
Learning form labeled and unlabeled data using graph mincuts.
In Proc. 18th International Conference on Machine Learning, 2001, 2001.

[Chandola et al., 2009]
Chandola, V., Banerjee, A., and Kumar, V.
Anomaly detection: A survey.
ACM computing surveys (CSUR), 410 (3):0 1–58, 2009.

[Cheeger, 2015]
Cheeger, J.
A lower bound for the smallest eigenvalue of the laplacian.
In Problems in analysis, pp.  195–200. Princeton University Press, 2015.

[Chen et al., 2020]
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G.
A simple framework for contrastive learning of visual representations.
In International conference on machine learning, pp.  1597–1607. PMLR, 2020.

[Chen & He, 2021]
Chen, X. and He, K.
Exploring simple siamese representation learning.
In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp.  15750–15758, 2021.

[Chung, 1997]
Chung, F. R.
Spectral graph theory, volume 92.
American Mathematical Soc., 1997.

[Cimpoi et al., 2014]
Cimpoi, M., Maji, S., Kokkinos, I., Mohamed, S., and Vedaldi, A.
Describing textures in the wild.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.  3606–3613, 2014.

[Djurisic et al., 2023]
Djurisic, A., Bozanic, N., Ashok, A., and Liu, R.
Extremely simple activation shaping for out-of-distribution detection.
In International Conference on Learning Representations, 2023.

[Du et al., 2022]
Du, X., Gozum, G., Ming, Y., and Li, Y.
Siren: Shaping representations for detecting out-of-distribution objects.
In Advances in Neural Information Processing Systems, 2022a.

[Du et al., 2022]
Du, X., Wang, X., Gozum, G., and Li, Y.
Unknown-aware object detection: Learning what you don’t know from videos in the wild.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022b.

[Du et al., 2022]
Du, X., Wang, Z., Cai, M., and Li, Y.
Vos: Learning what you don’t know by virtual outlier synthesis.
In Proceedings of the International Conference on Learning Representations, 2022c.

[Du et al., 2023]
Du, X., Sun, Y., Zhu, X., and Li, Y.
Dream the impossible: Outlier imagination with diffusion models.
In Advances in Neural Information Processing Systems, 2023.

[Du et al., 2024]
Du, X., Fang, Z., Diakonikolas, I., and Li, Y.
How does unlabeled data provably help out-of-distribution detection?
In Proceedings of the International Conference on Learning Representations, 2024.

[Eckart & Young, 1936]
Eckart, C. and Young, G.
The approximation of one matrix by another of lower rank.
Psychometrika, 10 (3):0 211–218, 1936.

[Fang et al., 1994]
Fang, Y., Loparo, K., and Feng, X.
Inequalities for the trace of matrix product.
IEEE Transactions on Automatic Control, 390 (12):0 2489–2490, 1994.

[Fang et al., 2022]
Fang, Z., Li, Y., Lu, J., Dong, J., Han, B., and Liu, F.
Is out-of-distribution detection learnable?
In Advances in Neural Information Processing Systems, 2022.

[Fort et al., 2021]
Fort, S., Ren, J., and Lakshminarayanan, B.
Exploring the limits of out-of-distribution detection.
Advances in Neural Information Processing Systems, 34:0 7068–7081, 2021.

[Gal & Ghahramani, 2016]
Gal, Y. and Ghahramani, Z.
Dropout as a bayesian approximation: Representing model uncertainty in deep learning.
In Proceedings of the International Conference on Machine Learning, pp.  1050–1059, 2016.

[Galil et al., 2023]
Galil, I., Dabbah, M., and El-Yaniv, R.
A framework for benchmarking class-out-of-distribution detection and its application to imagenet.
In International Conference on Learning Representations, 2023.

[Geifman & El-Yaniv, 2019]
Geifman, Y. and El-Yaniv, R.
Selectivenet: A deep neural network with an integrated reject option.
In Proceedings of the International Conference on Machine Learning, pp.  2151–2159, 2019.

[Ghosal et al., 2024]
Ghosal, S. S., Sun, Y., and Li, Y.
How to overcome curse-of-dimensionality for ood detection?
In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.

[Greenbaum et al., 2020]
Greenbaum, A., Li, R.-c., and Overton, M. L.
First-order perturbation theory for eigenvalues and eigenvectors.
SIAM review, 620 (2):0 463–482, 2020.

[Han et al., 2022]
Han, S., Hu, X., Huang, H., Jiang, M., and Zhao, Y.
Adbench: Anomaly detection benchmark.
Advances in Neural Information Processing Systems, 35:0 32142–32159, 2022.

[HaoChen et al., 2021]
HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, T.
Provable guarantees for self-supervised deep learning with spectral contrastive loss.
Advances in Neural Information Processing Systems, 34:0 5000–5011, 2021.

[HaoChen et al., 2022]
HaoChen, J. Z., Wei, C., Kumar, A., and Ma, T.
Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations.
Advances in Neural Information Processing Systems, 2022.

[He et al., 2016]
He, K., Zhang, X., Ren, S., and Sun, J.
Deep residual learning for image recognition.
In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.  770–778, 2016.

[He et al., 2023]
He, R., Li, R., Han, Z., Yang, X., and Yin, Y.
Topological structure learning for weakly-supervised out-of-distribution detection.
In Proceedings of the 31st ACM International Conference on Multimedia, pp.  4858–4866, 2023.

[Hein et al., 2019]
Hein, M., Andriushchenko, M., and Bitterwolf, J.
Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.  41–50, 2019.

[Hendrycks & Gimpel, 2017]
Hendrycks, D. and Gimpel, K.
A baseline for detecting misclassified and out-of-distribution examples in neural networks.
Proceedings of the International Conference on Learning Representations, 2017.

[Hendrycks et al., 2019]
Hendrycks, D., Mazeika, M., and Dietterich, T.
Deep anomaly detection with outlier exposure.
In Proceedings of the International Conference on Learning Representations, 2019.

[Huang et al., 2021]
Huang, R., Geng, A., and Li, Y.
On the importance of gradients for detecting distributional shifts in the wild.
In Advances in Neural Information Processing Systems, 2021.

[Jansen et al., 2015]
Jansen, A., Sell, G., and Lyzinski, V.
Scalable out-of-sample extension of graph embeddings using deep neural networks.
arXiv preprint arXiv:1508.04422, 2015.

[Jeong & Kim, 2020]
Jeong, T. and Kim, H.
Ood-maml: Meta-learning for few-shot out-of-distribution detection and classification.
Advances in Neural Information Processing Systems, 33:0 3907–3916, 2020.

[Kannan et al., 2004]
Kannan, R., Vempala, S., and Vetta, A.
On clusterings: Good, bad and spectral.
Journal of the ACM (JACM), 510 (3):0 497–515, 2004.

[Katz-Samuels et al., 2022]
Katz-Samuels, J., Nakhleh, J., Nowak, R., and Li, Y.
Training ood detectors in their natural habitats.
In International Conference on Machine Learning, 2022.

[Kristiadi et al., 2020]
Kristiadi, A., Hein, M., and Hennig, P.
Being bayesian, even just a bit, fixes overconfidence in relu networks.
In International conference on machine learning, pp.  5436–5446, 2020.

[Krizhevsky et al., 2009]
Krizhevsky, A., Hinton, G., et al.
Learning multiple layers of features from tiny images.

[Lakshminarayanan et al., 2017]
Lakshminarayanan, B., Pritzel, A., and Blundell, C.
Simple and scalable predictive uncertainty estimation using deep ensembles.
In Advances in Neural Information Processing Systems, volume 30, pp.  6402–6413, 2017.

[Lee et al., 2014]
Lee, J. R., Gharan, S. O., and Trevisan, L.
Multiway spectral partitioning and higher-order cheeger inequalities.
Journal of the ACM (JACM), 610 (6):0 1–30, 2014.

[Lee et al., 2018]
Lee, K., Lee, H., Lee, K., and Shin, J.
Training confidence-calibrated classifiers for detecting out-of-distribution samples.
In Proceedings of the International Conference on Learning Representations, 2018a.

[Lee et al., 2018]
Lee, K., Lee, K., Lee, H., and Shin, J.
A simple unified framework for detecting out-of-distribution samples and adversarial attacks.
Advances in Neural Information Processing Systems, 31, 2018b.

[Levin et al., 2018]
Levin, K., Roosta, F., Mahoney, M., and Priebe, C.
Out-of-sample extension of graph adjacency spectral embedding.
In International Conference on Machine Learning, pp.  2975–2984. PMLR, 2018.

[Liang et al., 2018]
Liang, S., Li, Y., and Srikant, R.
Enhancing the reliability of out-of-distribution image detection in neural networks.
In Proceedings of the International Conference on Learning Representations, 2018.

[Liu et al., 2020]
Liu, J., Lin, Z., Padhy, S., Tran, D., Bedrax Weiss, T., and Lakshminarayanan, B.
Simple and principled uncertainty estimation with deterministic deep learning via distance awareness.
Advances in Neural Information Processing Systems, 33:0 7498–7512, 2020a.

[Liu et al., 2020]
Liu, W., Wang, X., Owens, J., and Li, Y.
Energy-based out-of-distribution detection.
Advances in Neural Information Processing Systems, 33:0 21464–21475, 2020b.

[Maddox et al., 2019]
Maddox, W. J., Izmailov, P., Garipov, T., Vetrov, D. P., and Wilson, A. G.
A simple baseline for bayesian uncertainty in deep learning.
Advances in Neural Information Processing Systems, 32:0 13153–13164, 2019.

[Malinin & Gales, 2018]
Malinin, A. and Gales, M.
Predictive uncertainty estimation via prior networks.
Advances in Neural Information Processing Systems, 31, 2018.

[Malinin & Gales, 2019]
Malinin, A. and Gales, M.
Reverse kl-divergence training of prior networks: Improved uncertainty and adversarial robustness.
In Advances in Neural Information Processing Systems, 2019.

[McSherry, 2001]
McSherry, F.
Spectral partitioning of random graphs.
In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp.  529–537. IEEE, 2001.

[Meinke & Hein, 2020]
Meinke, A. and Hein, M.
Towards neural networks that provably know when they don't know.
In Proceedings of the International Conference on Learning Representations, 2020.

[Ming & Li, 2023]
Ming, Y. and Li, Y.
How does fine-tuning impact out-of-distribution detection for vision-language models?
International Journal of Computer Vision, 2023.

[Ming et al., 2022]
Ming, Y., Cai, Z., Gu, J., Sun, Y., Li, W., and Li, Y.
Delving into out-of-distribution detection with vision-language representations.
In Advances in Neural Information Processing Systems, 2022a.

[Ming et al., 2022]
Ming, Y., Fan, Y., and Li, Y.
POEM: out-of-distribution detection with posterior sampling.
In Proceedings of the International Conference on Machine Learning, pp.  15650–15665, 2022b.

[Ming et al., 2022]
Ming, Y., Yin, H., and Li, Y.
On the impact of spurious correlation for out-of-distribution detection.
In Proceedings of the AAAI Conference on Artificial Intelligence, 2022c.

[Ming et al., 2023]
Ming, Y., Sun, Y., Dia, O., and Li, Y.
How to exploit hyperspherical embeddings for out-of-distribution detection?
In Proceedings of the International Conference on Learning Representations, 2023.

[Morteza & Li, 2022]
Morteza, P. and Li, Y.
Provable guarantees for understanding out-of-distribution detection.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp.  7831–7840, 2022.

[Narasimhan et al., 2023]
Narasimhan, H., Menon, A. K., Jitkrittum, W., and Kumar, S.
Learning to reject meets ood detection: Are all abstentions created equal?
arXiv preprint arXiv:2301.12386, 2023.

[Netzer et al., 2011]
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y.
Reading digits in natural images with unsupervised feature learning.

[Ng et al., 2001]
Ng, A., Jordan, M., and Weiss, Y.
On spectral clustering: Analysis and an algorithm.
Advances in neural information processing systems, 14, 2001.

[Park et al., 2023]
Park, S., Mok, J., Jung, D., Lee, S., and Yoon, S.
On the powerfulness of textual outlier exposure for visual ood detection.
arXiv preprint arXiv:2310.16492, 2023.

[Quispe et al., 2016]
Quispe, A. M., Petitjean, C., and Heutte, L.
Extreme learning machine for out-of-sample extension in laplacian eigenmaps.
Pattern Recognition Letters, 74:0 68–73, 2016.

[Ren et al., 2021]
Ren, J., Fort, S., Liu, J., Roy, A. G., Padhy, S., and Lakshminarayanan, B.
A simple fix to mahalanobis distance for improving near-ood detection.
CoRR, abs/2106.09022, 2021.

[Ren et al., 2023]
Ren, J., Luo, J., Zhao, Y., Krishna, K., Saleh, M., Lakshminarayanan, B., and Liu, P. J.
Out-of-distribution detection and selective generation for conditional language models.
In International Conference on Learning Representations, 2023.

[Sehwag et al., 2021]
Sehwag, V., Chiang, M., and Mittal, P.
Ssd: A unified framework for self-supervised outlier detection.
In International Conference on Learning Representations, 2021a.

[Sehwag et al., 2021]
Sehwag, V., Chiang, M., and Mittal, P.
Ssd: A unified framework for self-supervised outlier detection.
In Proceedings of the International Conference on Learning Representations, 2021b.

[Shaham et al., 2018]
Shaham, U., Stanton, K., Li, H., Nadler, B., Basri, R., and Kluger, Y.
Spectralnet: Spectral clustering using deep neural networks.
In 6th International Conference on Learning Representations, ICLR 2018, 2018.

[Shen et al., 2022]
Shen, K., Jones, R. M., Kumar, A., Xie, S. M., HaoChen, J. Z., Ma, T., and Liang, P.
Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation.
In International Conference on Machine Learning, pp.  19847–19878, 2022.

[Shi & Malik, 2000]
Shi, J. and Malik, J.
Normalized cuts and image segmentation.
IEEE Transactions on pattern analysis and machine intelligence, 220 (8):0 888–905, 2000.

[Sun et al., 2022]
Sun, Y., Ming, Y., Zhu, X., and Li, Y.
Out-of-distribution detection with deep nearest neighbors.
In Proceedings of the International Conference on Machine Learning, pp.  20827–20840, 2022.

[Sun et al., 2023]
Sun, Y., Shi, Z., and Li, Y.
A graph-theoretic framework for understanding open-world representation learning.
In Advances in Neural Information Processing Systems, 2023a.

[Sun et al., 2023]
Sun, Y., Shi, Z., Liang, Y., and Li, Y.
When and how does known class help discover unknown ones? provable understandings through spectral analysis.
In International Conference on Machine Learning, 2023b.

[Sussman et al., 2012]
Sussman, D. L., Tang, M., Fishkind, D. E., and Priebe, C. E.
A consistent adjacency spectral embedding for stochastic blockmodel graphs.
Journal of the American Statistical Association, 1070 (499):0 1119–1128, 2012.

[Tack et al., 2020]
Tack, J., Mo, S., Jeong, J., and Shin, J.
Csi: Novelty detection via contrastive learning on distributionally shifted instances.
In Advances in Neural Information Processing Systems, 2020.

[Tang et al., 2013]
Tang, M., Sussman, D. L., and Priebe, C. E.
Universally consistent vertex classification for latent positions graphs.
The Annals of Statistics, 410 (3):0 1406–1430, 2013.

[Tao et al., 2023]
Tao, L., Du, X., Zhu, X., and Li, Y.
Non-parametric outlier synthesis.
In Proceedings of the International Conference on Learning Representations, 2023.

[Trosset & Priebe, 2008]
Trosset, M. W. and Priebe, C. E.
The out-of-sample problem for classical multidimensional scaling.
Computational statistics & data analysis, 520 (10):0 4635–4642, 2008.

[Uppaal et al., 2023]
Uppaal, R., Hu, J., and Li, Y.
Is fine-tuning needed? pre-trained language models are near perfect for out-of-domain detection.
In Annual Meeting of the Association for Computational Linguistics, 2023.

[van Amersfoort et al., 2020]
van Amersfoort, J., Smith, L., Teh, Y. W., and Gal, Y.
Uncertainty estimation using a single deep deterministic neural network.
In Proceedings of the International Conference on Machine Learning, pp.  9690–9700, 2020.

[Von Luxburg, 2007]
Von Luxburg, U.
A tutorial on spectral clustering.
Statistics and computing, 170 (4):0 395–416, 2007.

[Wang et al., 2021]
Wang, H., Liu, W., Bocchieri, A., and Li, Y.
Can multi-label classification networks know what they don't know?
Proceedings of the Advances in Neural Information Processing Systems, 2021.

[Wang et al., 2022]
Wang, Q., Liu, F., Zhang, Y., Zhang, J., Gong, C., Liu, T., and Han, B.
Watermarking for out-of-distribution detection.
Advances in Neural Information Processing Systems, 35:0 15545–15557, 2022a.

[Wang et al., 2023]
Wang, Q., Fang, Z., Zhang, Y., Liu, F., Li, Y., and Han, B.
Learning to augment distributions for out-of-distribution detection.
Advances in Neural Information Processing Systems, 2023a.

[Wang et al., 2023]
Wang, Q., Ye, J., Liu, F., Dai, Q., Kalander, M., Liu, T., HAO, J., and Han, B.
Out-of-distribution detection with implicit outlier transformation.
In International Conference on Learning Representations, 2023b.

[Wang et al., 2022]
Wang, Y., Zou, J., Lin, J., Ling, Q., Pan, Y., Yao, T., and Mei, T.
Out-of-distribution detection via conditional kernel independence model.
In Advances in Neural Information Processing Systems, 2022b.

[Wei et al., 2022]
Wei, H., Xie, R., Cheng, H., Feng, L., An, B., and Li, Y.
Mitigating neural network overconfidence with logit normalization.
In Proceedings of the International Conference on Machine Learning, pp.  23631–23644, 2022.

[Wen et al., 2020]
Wen, Y., Tran, D., and Ba, J.
Batchensemble: an alternative approach to efficient ensemble and lifelong learning.
In International Conference on Learning Representations, 2020.

[Wu et al., 2023]
Wu, Q., Chen, Y., Yang, C., and Yan, J.
Energy-based out-of-distribution detection for graph neural networks.
In International Conference on Learning Representations, 2023.

[Yang et al., 2021]
Yang, J., Wang, H., Feng, L., Yan, X., Zheng, H., Zhang, W., and Liu, Z.
Semantically coherent out-of-distribution detection.
In Proceedings of the International Conference on Computer Vision, pp.  8281–8289, 2021a.

[Yang et al., 2021]
Yang, J., Zhou, K., Li, Y., and Liu, Z.
Generalized out-of-distribution detection: A survey.
arXiv preprint arXiv:2110.11334, 2021b.

[Yang et al., 2022]
Yang, J., Wang, P., Zou, D., Zhou, Z., Ding, K., PENG, W., Wang, H., Chen, G., Li, B., Sun, Y., Du, X., Zhou, K., Zhang, W., Hendrycks, D., Li, Y., and Liu, Z.
OpenOOD: Benchmarking generalized out-of-distribution detection.
In Advances on Neural Information Processing Systems, Datasets and Benchmarks Track, 2022.

[Yang et al., 2023]
Yang, P., Liang, J., Cao, J., and He, R.
Auto: Adaptive outlier optimization for online test-time ood detection.
arXiv preprint arXiv:2303.12267, 2023.

[Yu et al., 2015]
Yu, F., Seff, A., Zhang, Y., Song, S., Funkhouser, T., and Xiao, J.
Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop.
arXiv preprint arXiv:1506.03365, 2015.

[Zhang et al., 2023]
Zhang, J., Yang, J., Wang, P., Wang, H., Lin, Y., Zhang, H., Sun, Y., Du, X., Zhou, K., Zhang, W., et al.
Openood v1. 5: Enhanced benchmark for out-of-distribution detection.
arXiv preprint arXiv:2306.09301, 2023.

[Zheng et al., 2023]
Zheng, H., Wang, Q., Fang, Z., Xia, X., Liu, F., Liu, T., and Han, B.
Out-of-distribution detection learning with unreliable out-of-distribution sources.
arXiv preprint arXiv:2311.03236, 2023.

[Zhou et al., 2017]
Zhou, B., Lapedriza, A., Khosla, A., Oliva, A., and Torralba, A.
Places: A 10 million image database for scene recognition.
IEEE transactions on pattern analysis and machine intelligence, 400 (6):0 1452–1464, 2017.

[Zhou et al., 2021]
Zhou, Z., Guo, L.-Z., Cheng, Z., Li, Y.-F., and Pu, S.
STEP: Out-of-distribution detection in the presence of limited in-distribution labeled data.
In Advances in Neural Information Processing Systems, 2021.

[Zhu et al., 2023]
Zhu, J., Li, H., Yao, J., Liu, T., Xu, J., and Han, B.
Unleashing mask: Explore the intrinsic out-of-distribution detection capability.
arXiv preprint arXiv:2306.03715, 2023a.

[Zhu et al., 2023]
Zhu, J., Yu, G., Yao, J., Liu, T., Niu, G., Sugiyama, M., and Han, B.
Diversified outlier exposure for out-of-distribution detection via informative extrapolation.
arXiv preprint arXiv:2310.13923, 2023b.

[Zhu et al., 2003]
Zhu, X., Ghahramani, Z., and Lafferty, J. D.
Semi-supervised learning using gaussian fields and harmonic functions.
In Proceedings of the 20th International conference on Machine learning (ICML-03), pp.  912–919, 2003.

[Zhu et al., 2022]
Zhu, Y., Chen, Y., Xie, C., Li, X., Zhang, R., Xue', H., Tian, X., bolun zheng, and Chen, Y.
Boosting out-of-distribution detection with typical features.
In Advances in Neural Information Processing Systems, 2022.

When and How Does In-Distribution Label Help Out-of-Distribution Detection?

§ NOTATIONS, ASSUMPTIONS AND IMPORTANT CONSTANTS

Here we summarize the important notations and constants in Table <ref>, and restate necessary definitions and assumptions in Section <ref>.

§.§ Notations

Please see Table <ref> for detailed notations.

Main notations and their descriptions.

1cNotation     1cDescription

2cgreyC Spaces

$\mathcal{X}$,  $\mathcal{Z}$, $\mathcal{Y}$         the input, representation space and the label space.

2cgreyC Distributions

$\mathbb{P}_{{\rm id}}$, $\mathbb{P}_{{\rm ood}}$    data distribution for ID data and OOD data

$\mathbb{P}_{\mathcal{X}\mathcal{Y}}$     the joint data distribution for ID data.

2cgreyC Data and Models

$\*x$     input to the neural network

$\tilde{\*A}_{\rm OI}^{(u)}$ and   $\tilde{\*A}_{\rm OI}^{(l)}$      adjacency matrix between OOD and ID data in the labeled and unlabeled case

$\*A^{(u)}$ and  $\*A^{(l)}$     adjacency matrix for ID data in the labeled and unlabeled case

$\tilde{\*A}^{(u)}$ and  $\tilde{\*A}^{(l)}$     normalized adjacency matrix for ID data in the labeled and unlabeled case

$\*D^{(u)}$ and $\*D^{(l)}$    ID diagonal matrix with the diagonal elements being the row sum of $\*A^{(u)}$ and  $\*A^{(l)}$.

$\*D^{(u)}_{\rm ood}$ and $\*D^{(l)}_{\rm ood}$    OOD diagonal matrix with the diagonal elements being the row sum of $\tilde{\*A}_{\rm OI}^{(u)}$ and   $\tilde{\*A}_{\rm OI}^{(l)}$.

$\mathcal{T}$    augmentation graph

$\mathbf{w}$, $\boldsymbol{\theta}$     weight of the ID feature extractor and the linear probing layer

$\mathbf{h}_{\mathbf{w}}$ and $\mathbf{g}_{\boldsymbol{\theta}}$     feature extractor on ID data and linear probing layer for OOD detection

$y$, $\*y$    binary label for linear probing, vectorized one-hot label for $y$

$\*z$      feature for single input $\*x$

$\*{Z}^{(u)}$ and  $\*{Z}^{(l)}$     representation matrix for ID data in the labeled and unlabeled case

$\*{Z}_{\rm ood}^{(u)}$ and  $\*{Z}_{\rm ood}^{(l)}$     representation matrix for OOD data in the labeled and unlabeled case

$\*{Z}_{\rm all}^{(u)}$ and  $\*{Z}_{\rm all}^{(l)}$     representation matrix for both ID and OOD data in the labeled and unlabeled case

$\mathfrak{q}$ and $\mathfrak{p}$     semantic connection from each ID/OOD data to the labeled ID data.

$N$, $M$     size of $\*{Z}$, size of $\*{Z}_{\rm ood}$

$\boldsymbol{\lambda}$     eigenvalue vector of $\tilde{\*A}$

$\*v_j$   the $j$-th eigenvector of $\tilde{\*A}$

$\*V_k, \*V_{\varnothing}$     the first $k$ eigenvectors of $\tilde{\*A}$/the latter $N-k$ eigenvectors of $\tilde{\*A}$ (null space of $\*V_k$)

2cgreyC Distances

$\| \cdot \|_1, \| \cdot \|_2, \| \cdot \|_F$     $\ell_1, \ell_2$ norm and Frobenius norm

2cgreyC Loss and Risk

$\mathcal{L}_{\rm unlabeled}(\cdot), \mathcal{L}_{\rm labeled}(\cdot)$     ID loss function in the unlabeled and labeled case

$R({\*Z_{\rm all}})$     the empirical risk w.r.t. linear probing module over feature set $\*Z_{\rm all}$

$\overline{R}({\*Z_{\rm all}})$     the upper bound of $R(\*Z_{\rm all})$

$\mathcal{G}$     linear probing error difference with and without ID labels

2cgreyC Constants

$\phi_u,\phi_l$      weight coefficients for the unlabeled and labeled case.

$k$     dimension of the feature representation

$\tau$     the parameter that measures the eigengap of $\tilde{\*A}^{(u)}$

$r$     the maximum $\ell_2$ norm of the ID features, i.e.,  $r = \max_{\*z \in \*Z^{(u)}} \|\*z\|_2$

$C$    constants in Theorem <ref>

§.§ Assumptions

[Property of ID adjacency matrix]
We assume the adjacency matrix $\tilde{\*A}^{(u)}$ has the following property: There exists a positive constant $k \leq N$ such that the $k$-th eigengap of  $\tilde{\*A}^{(u)}$ satisfies that $\boldsymbol{\lambda}_{k}^{(u)} \geq \tau \boldsymbol{\lambda}_{k+1}^{(u)}, \tau > k$, where $\boldsymbol{\lambda}_{k}^{(u)}$ is the $k$-th largest eigenvalue of matrix $\tilde{\*A}^{(u)}$.

We have empirically verified our assumption using both simulated and real-world datasets in Section <ref>.

[Property of vectors that depict the semantic connection between each ID/OOD data to the labeled ID data]

Similar to [Sun et al., 2023], we assume each row of the matrix $\mathfrak{q}$ lies in the linear span of $\*V_{k}^{(u)}$ and $\*V_{k}^{(u)}[\*\Sigma_{k}^{(u)}]^{-\frac{1}{2}}$, i.e., $\*V_{\varnothing}^{(u)\top} \mathfrak{q}_i = 0, \*V_{k}^{(u)}\*V_{k}^{(u)\top} \mathfrak{q}_i = \mathfrak{q}_i $ and $\*V_{k}^{(u)}[\*\Sigma_{k}^{(u)}]^{-1}\*V_{k}^{(u)\top} \mathfrak{q}_i = \mathfrak{q}_i$.

Following the assumptions made in the existing literature [Sun et al., 2023], the assumption is used to simplify $\*V_{k}^{(u)} \*V_{k}^{(u) \top}   \mathfrak{q}_i \mathfrak{q}_i^{\top} \*V_{\varnothing}^{(u)} \*V_{\varnothing}^{(u)\top} + \*V_{k}^{(u)}\*V_{k}^{(u)\top} \mathfrak{q}_i \mathfrak{q}_i^\top $ to $ \mathfrak{q}_i \mathfrak{q}_i^\top $ and simplify $\*V_{k}^{(u)}[\*\Sigma_{k}^{(u)}]^{-1}\*V_{k}^{(u)\top} \mathfrak{q}_i$ to $\mathfrak{q}_i$.

§ MAIN THEOREMS

In this section, we provide a detailed and formal version of our main theorems with a complete description of the constant terms and other additional details that are omitted in the main paper.

[Lower bound of the error difference between unlabeled and labeled cases, recap of Theorem <ref> in the main paper]
Suppose we have  adjacency matrices $\tilde{\*A}^{(u)}, \tilde{\*A}^{(l)}\in \mathbb{R}^{N \times N}$ and $\tilde{\*A}_{\rm OI}^{(u)}, \tilde{\*A}_{\rm OI}^{(l)} \in \mathbb{R}^{M \times N}$  for both the labeled and unlabeled cases. If Assumption <ref> holds, given positive constants $\phi_l, C$, the error difference $ \mathcal{G}$  in Equation <ref> is bounded by

\begin{equation}
\begin{aligned}
&  \mathcal{G} \geq      \frac{C \phi_l}{N+M} \epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} ) ,
\end{aligned}
\end{equation}

where $\mathfrak{q} \in \mathbb{R}^{c\times N}$ with each row being defined as $(\mathfrak{q}_i)_\*x = \mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}), \*x \in \mathcal{X}_{\rm id}$. Similarly, we have $\mathfrak{p}\in \mathbb{R}^{c\times M}$ and $(\mathfrak{p}_i)_\*x = \mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}), \*x \in \mathcal{X}_{\rm ood}$. Furthermore,

\begin{equation}
% \small
\begin{aligned}
\epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} )  &=  2 \sum_{i=1}^{c} \operatorname{Tr}\left(\mathfrak{p}_i\mathfrak{q}_i^\top \cdot   \tilde{\*A}_{\rm OI}^{(u)\top}\right)  +  \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2  \right)  \sum_{i=1}^c \|\mathfrak{q}_i\|_F^2 +  \\&
r^2\left( \|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \| \tilde{\*A}^{(u)}\|_F^2  \frac{ 2(\tau- k)}{\tau-1} -2\right)   \cdot \sum_{i=1}^c \|\mathfrak{q}_{i}\|_1,
\end{aligned}
\label{eq14_app}
% \vspace{-1em}
\end{equation}

where $\tau$ is a constant that measures the $k$-th spectral gap of matrix $\tilde{\*A}^{(u)}$, i.e., $\boldsymbol{\lambda}_{k}^{(u)} \geq \tau \boldsymbol{\lambda}_{k+1}^{(u)}$ and $\boldsymbol{\lambda}_{k}^{(u)} $ is the $k$-th largest singular value of $\tilde{\*A}^{(u)}$. $r$ is the maximum $l_2$ norm of the ID representations, i.e.,  $r = \max_{\*z \in \*Z^{(u)}} \|\*z\|_2$.

[Simplified version of Theorem <ref>, recap of Theorem <ref> in the main paper]
Under the same conditions in Theorem <ref>, if the number of ID and OOD samples $N$ and $M$ is sufficiently large, assume the $k$-th spectral gap of $\tilde{\*A}^{(u)}$ satisfies $\tau>k$ (Assumption <ref> holds), then the main error component $ \epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} )  $ in Equation <ref> satisfies

\begin{equation}
\small
\begin{aligned}
\epsilon(\mathfrak{p}, \mathfrak{q},&\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} )  \geq  \left[1+ \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2\left( 2N^2-   \|\tilde{\*A}^{(u)}\|_F^2    \right)  \right]  \sum_{i=1}^c\|\mathfrak{q}_i\|_F^2.
\end{aligned}
\end{equation}

§ PROOFS OF MAIN THEOREMS

§.§ Proof of Theorem <ref>

Before proving Theorem <ref>, we first explain the framework introduced in Section <ref> of the main paper to analyze the difference in the adjacency matrices and the corresponding feature representations between the unlabeled and labeled cases. Specifically, we proposed to analyze the adjacency matrix in the labeled case by perturbation analysis.

Matrix perturbation in the labeled case. Recall that we define in Definition <ref> that the adjacency matrix in the labeled case (l) is the unlabeled one (u) plus connectivity incurred by the ID labels, which can be regarded as the perturbation of the labeling information. Therefore, for the ID adjacency matrix with ID labels, we have the perturbation on $\*A^{(u)}$ as follows:

\begin{equation}
\*A^{(l)} =  \phi_{u} \*A^{(u)} + \phi_l \Delta \*A,
\end{equation}

where $ \Delta \*A \in \mathbb{R}^{N \times N}$ can be calculated based on the augmentation graph $\mathcal{T}$ according to Definition <ref>. Following [Sun et al., 2023], we study the perturbation from two aspects: (1) The direction of the perturbation which is given by $ \Delta \*A$, (2) The perturbation magnitude $\phi_l$. We first consider the perturbation direction $\Delta \*A$ and recall that we defined the concrete form in Definition <ref>:

\begin{equation}
[\Delta \*A]_{\*x\*x^{\prime}}\triangleq \sum_{i \in \mathcal{Y}} \mathbb{E}_{\bar{\*x}_l \sim \mathbb{P}_{l_i}} \mathbb{E}_{\bar{\*x}_l^{\prime} \sim \mathbb{P}_{l_i}} \mathcal{T}\left(\*x \mid \bar{\*x}_l\right) \mathcal{T}\left(\*x^{\prime} \mid \bar{\*x}_l^{\prime}\right), \quad \*x, \*x^\prime \in \mathcal{X}_{\rm id}
\label{eq17_app}
\end{equation}

where $\mathcal{T}$ is the augmentation graph. In our theory, we consider $\|\mathcal{Y}\| = c$, and then we observe that $ \Delta \*A$ is the sum of $c$ rank-1 matrices, which can be written as:

\begin{equation}
\Delta \*A = \sum_{i=1}^c\mathfrak{q}_i  \mathfrak{q}_i^\top,
\end{equation}

where $\mathfrak{q} \in \mathbb{R}^{N \times c}$ with each column defined as $(\mathfrak{q}_i)_\*x=\mathbb{E}_{\bar{\*x}_l \sim \mathbb{P}_{l_i}} \mathcal{T}\left(\*x \mid \bar{\*x}_l\right), \*x  \in \mathcal{X}_{\rm id}$ and $\bar{\*x}_l$ is the labeled ID data with label $i$. And following [Sun et al., 2023], we define the diagonal matrix $\*D^{(l)}$ as follows:

\begin{equation}
\*D^{(l)} = \phi_u \cdot \*D^{(u)} + \sum_{i=1}^c \phi_l \cdot  {\rm diag}(\mathfrak{q}_i).
\end{equation}

Without losing the generality, we let $\phi_u \cdot {\rm diag}(\*1_{N}^\top  \*A^{(u)})=\*I_{N\times N}$, which means the ID nodes have equal degree in the unlabeled case. We then have:

\begin{equation}
\*D^{(l)} \triangleq \operatorname{diag}\left(\mathbf{1}_N^{\top} \*A^{(l)}\right)=\*I_{N\times N}+\phi_l \cdot\sum_{i=1}^c   {\rm diag}(\mathfrak{q}_i).
\end{equation}

The perturbation function of representation. We then consider a more generalized form for the ID adjacency matrix $\*A$:

\begin{equation}
\*A(\phi_l) =  \phi_{u} \*A^{(u)} + \phi_l \cdot \sum_{i=1}^c\mathfrak{q}_i  \mathfrak{q}_i^\top.
\label{eq21_app}
\end{equation}

For the perturbation on the OOD-ID adjacency matrix $\tilde{\*A}_{\rm OI}$, we define $\mathfrak{p} \in \mathbb{R}^{M\times c}$ with each column defined as $(\mathfrak{p}_i)_\*x=\mathbb{E}_{\bar{\*x}_l \sim \mathbb{P}_{l_i}} \mathcal{T}\left(\*x \mid \bar{\*x}_l\right),  \*x  \sim \mathcal{X}_{\rm ood}$ and $\bar{\*x}_l$ is the labeled ID data with label $l_i$. Similar to Equation <ref>, we can define the concrete perturbation formula for $\tilde{\*A}_{\rm OI}$ as follows:

\begin{equation}
[\Delta \tilde{\*A}_{\rm OI}]_{\*x\*x^{\prime}}\triangleq \sum_{i \in \mathcal{Y}} \mathbb{E}_{\bar{\*x}_l \sim \mathbb{P}_{l_i}} \mathbb{E}_{\bar{\*x}_l^{\prime} \sim \mathbb{P}_{l_i}} \mathcal{T}\left(\*x \mid \bar{\*x}_l\right) \mathcal{T}\left(\*x^{\prime} \mid \bar{\*x}_l^{\prime}\right),  \quad\*x^\prime  \sim \mathcal{X}_{\rm id},  \*x \sim \mathcal{X}_{\rm ood}.
\end{equation}

And we have:

\begin{equation}
\tilde{\*A}_{\rm OI}(\phi_l) =  \phi_{u} \tilde{\*A}_{\rm OI}^{(u)} + \phi_l \cdot \sum_{i=1}^c \mathfrak{p}_i  \mathfrak{q}_i^\top.
\label{eq23_app}
\end{equation}

Similarly, for the ID diagonal matrix $\*D$, we have that:

\begin{equation}
\*D(\phi_l) =\*I_{N\times N}+\phi_l \cdot\sum_{i=1}^c   {\rm diag}(\mathfrak{q}_i).
\label{eq24_app}
\end{equation}

In Equations <ref> and <ref>, we treat the adjacency matrix as a function of the “labeling perturbation” magnitude $\phi_l $. It is clear
that $\*A(0) = \phi_u \*A^{(u)}$ and $\tilde{\*A}_{\rm OI}(0) = \phi_u \tilde{\*A}_{\rm OI}^{(u)}$ which are the scaled adjacency matrices in the unlabeled case.  When we let the adjacency matrix be a function of $\phi_l$, the normalized form, and the derived feature representation should also be the function of $\phi_l$. We proceed by defining these terms.

The normalized ID adjacency matrix is given by:

\begin{equation}
\tilde{\*A}(\phi_l) =  \*D(\phi_l)^{-\frac{1}{2}} {\*A}(\phi_l) \*D(\phi_l)^{-\frac{1}{2}},
\end{equation}

In addition, for in-distribution feature representation $\*Z(\phi_l)$,  it is derived from the top-$k$ eigen components of $\tilde{\*A}(\phi_l)$. Specifically, we have:

\begin{equation}
\*Z(\phi_l) \*Z(\phi_l)^\top = \*D(\phi_l)^{-\frac{1}{2}} \tilde{\*A}_k(\phi_l) \*D(\phi_l)^{-\frac{1}{2}} = \*D(\phi_l)^{-\frac{1}{2}} \sum_{j=1}^k \boldsymbol{\lambda}_j(\phi_l) \*\Phi_{j}(\phi_l)  \*D(\phi_l)^{-\frac{1}{2}} ,
\label{eq26_app}
\end{equation}

where $\tilde{\*A}_k(\phi_l)$ is the top-$k$ SVD components of $\tilde{\*A}(\phi_l)$ and can be written as $\tilde{\*A}_k(\phi_l) = \sum_{j=1}^k \boldsymbol{\lambda}_j(\phi_l) \*\Phi_j(\phi_l)$. Here $\boldsymbol{\lambda}_j(\phi_l)$ and $ \*\Phi_{j}(\phi_l) = \*v_j(\phi_l)\*v_{j}^{\top}(\phi_l) $
are the $j$-th eigenvalue and eigen projector of matrix $\tilde{\*A}(\phi_l)$. For simplicity, when $\phi_l=0$, we remove the suffix $(0)$ and give the following definitions:

\begin{equation}
\tilde{\*A}(0) =  \tilde{\*A}^{(u)}, \*Z(0) =  {\*Z}^{(u)}, \*Z_{\rm ood}(0) =  {\*Z}_{\rm ood}^{(u)}, \*Z_{\rm all}(0) =  {\*Z}_{\rm all}^{(u)}, \boldsymbol{\lambda}_j(0) =  \boldsymbol{\lambda}_j^{(u)},  \*v_j(0) =  \*v_j^{(u)}, \*\Phi_{j}(0) =  \*\Phi_j^{(u)}.
\end{equation}

We proceed to provide the five concrete steps to prove Theorem <ref>.

Step 1. Recall that our analysis is based on the upper bound of the linear probing loss, and focuses on the error difference between the labeled and the unlabeled case, which is formulated in Equation <ref>  of the main paper. In the context of perturbation analysis, we can reformulate the error difference $\mathcal{G}$ as a function of $\phi_l$ as follows:

\begin{equation}
\mathcal{G}(\phi_l) = \overline{R}(  {\*Z}_{\rm all}(0)) - \overline{R}(  {\*Z}_{\rm all}(\phi_l)).
\label{eq28_app}
\end{equation}

By the definition of the derivative, we can rewrite Equation <ref>:

\begin{equation}
\mathcal{G}(\phi_l)   = -\left.\frac{\mathrm{d} \overline{R}\left(\*Z_{\rm all}(\phi_l)\right)}{\mathrm{d} \phi_l}\right|_{\phi_l=0} \cdot  \phi_l
\end{equation}

With Lemma <ref>, we can get the lower bound of $\mathcal{G}(\phi_l)$ as follows:

\begin{equation}
\mathcal{G}(\phi_l) \geq \frac{2}{3(N+M)} \phi_l \cdot \max \lambda\left(\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)\right) \cdot \operatorname{Tr}\left(\left(\*Z_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^{\top}\right)^{\prime}\*y\*y^{\top}\right)\bigg|_{\phi_l=0}
% \label{eq21_app}
\end{equation}

According to Lemma <ref>, $\max \lambda\left(\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)\right)\big|_{\phi_l=0} > 0$ is a positive constant. Here $\max \lambda\left(\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)\right)$ means the maximum eigenvalue of the matrix $\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)$. We then proceed to analyze the key component $\operatorname{Tr}\left(\left(\*Z_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^{\top}\right)^{\prime}\*y\*y^{\top}\right)\big|_{\phi_l=0}$.

Next, according to Lemma 3.1 in [HaoChen et al., 2021], which implies that multiplying any invertible matrix by the features of the linear probing module does not change the linear probing performance. Therefore, we simplify the mathematical representation of the ID and OOD features in the Equations <ref> and <ref> in the main paper as follows by removing the terms $\*D(\phi_l)$ and $\*D_{\rm ood}(\phi_l)$:

\begin{equation}
\*Z^{(l)} =  \*V_k^{(l)} [\*\Sigma_k^{(l)}]^{\frac{1}{2}},\quad \*Z_{\rm ood}^{(l)} = \tilde{\*A}_{\rm OI}^{(l)}  \mathbf{V}_k^{(l)}  [\mathbf{\Sigma}_k^{(l)}]^{-\frac{1}{2}},
\end{equation}

which simplifies the notation and will be used in our later analysis.

Step 2. Recall that the input feature for linear probing $\*Z(\phi_l)$ is defined as:

\begin{equation}
\*Z_{\rm all}(\phi_l) = \begin{pmatrix}
\*Z(\phi_l) \\ \*Z_{\rm ood}(\phi_l)
\end{pmatrix} =\begin{pmatrix}
\mathbf{V}_k(\phi_l) \sqrt{\mathbf{\Sigma}_k(\phi_l)}\\
\tilde{\*A}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l) \sqrt{\mathbf{\Sigma}_k(\phi_l)}^{-1} \end{pmatrix}
\label{eq32_app}
\end{equation}

Therefore, it is natural to have that:

\begin{equation}
\tiny
\color{black}
\begin{aligned}
\operatorname{Tr}( (\*Z_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^\top)^\prime \*y\*y^{\top})\bigg|_{\phi_l=0}    &=\operatorname{Tr}\left( \left(\begin{pmatrix}
\mathbf{V}_k(\phi_l) \sqrt{\mathbf{\Sigma}_k(\phi_l)}\\
\tilde{\*A}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l) \sqrt{\mathbf{\Sigma}_k(\phi_l)}^{-1} \end{pmatrix} \cdot  \begin{pmatrix}
\sqrt{\mathbf{\Sigma}_k(\phi_l)} \mathbf{V}_k(\phi_l)^\top &\sqrt{\mathbf{\Sigma}_k(\phi_l)}^{-1} \mathbf{V}_k(\phi_l)^\top \tilde{\*A}^k_{\rm OI}(\phi_l)^\top
\end{pmatrix}\right)^\prime\*y\*y^{\top} \right)\bigg|_{\phi_l=0} \\& \geq { \scriptsize \operatorname{Tr}\left( \begin{pmatrix} \mathbf{V}_k(\phi_l) \mathbf{\Sigma}_k(\phi_l) \mathbf{V}_k(\phi_l)^\top &\mathbf{V}_k(\phi_l)\mathbf{V}_k(\phi_l)^\top \tilde{\*A}_{\rm OI}(\phi_l) \\   \tilde{\*A}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l)\mathbf{V}_k(\phi_l)^\top  & \tilde{\*A}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l)  \mathbf{\Sigma}_k(\phi_l)^{-1} \mathbf{V}_k(\phi_l)^\top\tilde{\*A}_{\rm OI}(\phi_l)^\top  \end{pmatrix}^\prime  \right)\bigg|_{\phi_l=0}} \cdot \operatorname{Tr}(\*y\*y^{\top})\\& = \left(\operatorname{Tr}\left(\left(\mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l) \mathbf{V}_k(\phi_l)^{\top}\right)^{\prime}\right)+\operatorname{Tr}\left(\left(\tilde{\*A}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l)^{-1} \mathbf{V}_k(\phi_l)^{\top} {\tilde{\*A}}_{\rm OI}(\phi_l)^{\top}\right)^{\prime}\right)\bigg|_{\phi_l=0} \right)\cdot \|\*y\|_F^2
\end{aligned}
\end{equation}

In the following steps, we focus on the lower bounds of the two separate terms, i.e., $\operatorname{Tr}\left(\left(\tilde{\*A}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l)^{-1} \mathbf{V}_k(\phi_l)^{\top} \tilde{\*A}_{\rm OI}(\phi_l)^{\top}\right)^{\prime}\right)\big|_{\phi_l=0}$ and $\operatorname{Tr}\left(\left(\mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l) \mathbf{V}_k(\phi_l)^{\top}\right)^{\prime}\right)\big|_{\phi_l=0}$, respectively.

Step 3. As in Lemma <ref>, we provide the lower bound for the first term $\operatorname{Tr}\left(\left(\mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l) \mathbf{V}_k(\phi_l)^{\top}\right)^{\prime}\right)\big|_{\phi_l=0}$ as follows:

\begin{equation}
\operatorname{Tr}\left(\left(\mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l) \mathbf{V}_k(\phi_l)^{\top}\right)^{\prime}\right)\bigg|_{\phi_l=0}\geq \sum_{i=1}^c \|\mathfrak{q}_i\|_F^2-
2r^2  \sum_{i=1}^c\|\mathfrak{q}_{i} \|_1,
\label{eq34_app}
\end{equation}

where $r$ denotes the maximum $\ell_2$ norm of the ID features, i.e.,  $r = \max_{\*z \in \*Z^{(u)}} \|\*z\|_2$, and $\mathfrak{q} \in \mathbb{R}^{N\times c}$ with each column defined as $(\mathfrak{q}_i)_\*x = \mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}), \*x \in \mathcal{X}_{\rm id}$.

Step 4. We provide the lower bound for second term $\operatorname{Tr}\left(\left({\tilde{\*A}}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l)^{-1} \mathbf{V}_k(\phi_l)^{\top} {\tilde{\*A}}_{\rm OI}(\phi_l)^{\top}\right)^{\prime}\right)\big|_{\phi_l=0}$  as in  Lemma <ref> as follows:

\begin{equation}
\begin{aligned}
&\operatorname{Tr}\left(\left(\tilde{\*A}_{\rm OI}(\phi_l) \mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_k(\phi_l)^{-1} \mathbf{V}_k(\phi_l)^{\top} \tilde{\*A}_{\rm OI}(\phi_l)^{\top}\right)^{\prime}\right)\big|_{\phi_l=0}\\ &  \geq 2\sum_{i=1}^{c} \operatorname{Tr}\left(\mathfrak{p}_i\mathfrak{q}_i^\top \cdot   \tilde{\*A}_{\rm OI}^{(u)\top}\right)  -\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2  \|\tilde{\*A}^{(u)}\|_F^2  \cdot(  {\sum_{i=1}^c \|\mathfrak{q}_i\|_F^2 - \frac{ 2r^2(\tau- k)}{\tau-1})}\sum_{i=1}^c\| \mathfrak{q}_{i}\|_1),
\label{eq35_app}
\end{aligned}
\end{equation}

where $\mathfrak{p}\in \mathbb{R}^{M\times c}$ is defined as $(\mathfrak{p}_i)_\*x = \mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}), \*x \in \mathcal{X}_{\rm ood}$.

Step 5. Putting the result in Equations <ref> and <ref> together, if we denote $C = \frac{2}{3}\left\|\mathbf{y}\right\|_F^2  \cdot \max \lambda\left(\*Z_{\rm all}(0)^{\top} \*Z_{\rm all}(0)\right) $, we can get:

\begin{equation}
\scriptsize
\begin{aligned}
&  \mathcal{G}(\phi_l)\geq \frac{C   \phi_l}{N+M}  \cdot \operatorname{Tr}\left(\left(\*Z_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^{\top}\right)^{\prime}\right)\bigg|_{\phi_l=0}
\\& \geq \frac{C   \phi_l}{N+M} \bigg[2 \sum_{i=1}^{c} \operatorname{Tr}\left(\mathfrak{p}_i\mathfrak{q}_i^\top \cdot   \tilde{\*A}_{\rm OI}^{(u)\top}\right)  +   \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \cdot \|\tilde{\*A}^{(u)}\|_F^2  \right) \sum_{i=1}^c \|\mathfrak{q}_i\|_F^2-
r^2 \left( 2-\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \cdot \|\tilde{\*A}^{(u)}\|_F^2  \frac{ 2(\tau-k)}{\tau-1} \right)   \cdot \sum_{i=1}^c\|\mathfrak{q}_{i}\|_1\bigg].
\end{aligned}
\end{equation}

We have completed the proof of Theorem <ref>.

§.§ Proof of Theorem <ref>

As in Assumption <ref>, we can find a $k$ such that $\tau>k$. Based on this condition, we can get the following

\begin{equation}
\begin{aligned}
\tau > k &= 1+ k-1 \\& =1 + \frac{\|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 }{\|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 -1} (k-1) - O( \frac{k-1 }{\|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 -1} ).
\end{aligned}
\end{equation}

When we have a sufficient number of ID or OOD data, $\|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \|\tilde{\*A}^{(u)}\|_F^2$ will be large such that we can omit the term $O( \frac{k-1 }{\|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 -1} )$ because $k \leq N$. Therefore, we will have the inequality of

\begin{equation}
\tau > 1 + \frac{\|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 }{\|\tilde{\*A}_{\rm OI}^{(u)}\|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 -1} (k-1).
\end{equation}

Simply the above inequality, we can get that

\begin{equation}
\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 > \frac{\tau-1}{\tau-k }.
\end{equation}

Therefore we have

\begin{equation}
-r^2 \left(2-\left\|\tilde{\mathbf{A}}_{\rm OI }^{(u)}\right\|_F^2\left\|\tilde{\mathbf{A}}^{(u)}\right\|_F^2 \frac{2\left(\tau-k\right)}{\tau-1}\right) \cdot \sum_{i=1}^c\|\mathfrak{q}_{i}\|_1 > 0,
\end{equation}

Under this condition, the main error term $\epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} )$ in Theorem <ref> can be further bounded by:

\begin{equation}
\epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} ) \geq 2 \sum_{i=1}^{c} \operatorname{Tr}\left(\mathfrak{p}_i\mathfrak{q}_i^\top \cdot   \tilde{\*A}_{\rm OI}^{(u)\top}\right)  +  \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2  \right)  \sum_{i=1}^c \|\mathfrak{q}_i\|_F^2,
\end{equation}

Following the same analysis approach in literature (See Section 4.1 of [HaoChen et al., 2021]), we decompose the vectors $\mathfrak{p}$ and $\mathfrak{q}$ into numbers in each dimension instead of using the vectorized form for calculation. Specifically, we let $\mathcal{T}(\*x|\bar{\*x})=\kappa, \*x, \bar{\*x}\sim\mathcal{X}_{\rm ood}$ and $\mathcal{T}(\*x|\bar{\*x})=\gamma, \*x, \bar{\*x}\sim\mathcal{X}_{\rm id}$
Based on the adjacency matrix and its relationship with the augmentation graph (Equation <ref>), we can prove that the following result holds:

\begin{equation}
\tilde{\*A}_{\rm OI}^{(u)} =\sum_{i=1}^c\phi_u  \frac{\gamma N}{M+N} \cdot [\mathfrak{p}_i, ..., \mathfrak{p}_i] + O(\kappa) = \sum_{i=1}^c\frac{1}{N^3\gamma}  \cdot [\mathfrak{p}_i, ..., \mathfrak{p}_i]+ O(\kappa),
\end{equation}

where  $\phi_u = \frac{M+N}{N^4\gamma^2}$.
Then, we obtain that:

\begin{equation}
\operatorname{Tr}\left(\mathfrak{p}_i\mathfrak{q}_i^\top \cdot   \tilde{\*A}_{\rm OI}^{(u)\top}\right) = \operatorname{Tr}\left(\mathfrak{q}_i^\top \cdot   \tilde{\*A}_{\rm OI}^{(u)\top}\cdot \mathfrak{p}_i\right) =\sum_{i=1}^c \gamma N^2\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\mathfrak{q}_i\|_1 +O(\kappa).
\end{equation}

After that, we can get:

\begin{equation}
\begin{aligned}
&  \epsilon(\mathfrak{p}, \mathfrak{q},\tilde{\*A}^{(u)},\tilde{\*A}_{\rm OI}^{(u)} ) \geq \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2  \right)  \sum_{i=1}^c\|\mathfrak{q}_i\|_F^2  + 2\gamma N^2\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \sum_{i=1}^c\|\mathfrak{q}_i\|_1 +O(\kappa),
\end{aligned}
\end{equation}

Further simplify the right-hand side of the above inequality, we can get:

\begin{equation}
\begin{aligned}
& \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2  \right)  \sum_{i=1}^c\|\mathfrak{q}_i\|_F^2  + 2\gamma N^2\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \sum_{i=1}^c\|\mathfrak{q}_i\|_1 +O(\kappa)\\& = \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2  \right)  \sum_{i=1}^c\|\mathfrak{q}_i\|_F^2 + 2c\gamma N^2\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 N \gamma+O(\kappa)\\& =\left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2  \right)  \sum_{i=1}^c\|\mathfrak{q}_i\|_F^2  + 2N^2 \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \cdot\sum_{i=1}^c \|\mathfrak{q}_i\|_F^2 +O(\kappa)\\ & = \left(1- \|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2 \|\tilde{\*A}^{(u)}\|_F^2 +2N^2\|\tilde{\*A}_{\rm OI}^{(u)} \|_F^2    \right)  \sum_{i=1}^c\|\mathfrak{q}_i\|_F^2 +O(\kappa)
\end{aligned}
\end{equation}

We have completed the proof of Theorem <ref>.

§ NECESSARY LEMMAS

§.§ Details for Spectral Contrastive Learning

(Recap of Lemma <ref> in the main paper)
We define $\*f_\*x = \sqrt{\zeta_\*x}\*h_\*w(\*x)$ for some function $\*h_\*w$. Recall $\phi_{u},\phi_{l}$ are two weight coefficients given in Definition <ref>, then minimizing the loss function $\mathcal{L}(\*F^{(l)}, \*A^{(l)})$ in Equation <ref> is equivalent to minimizing the surrogate loss in Equation <ref>.

\begin{align}
\begin{split}
\mathcal{L}_\text{\rm labeled}(\*h_\*w) &\triangleq - 2\phi_{l} \mathcal{L}_1(\*h_\*w)
- 2\phi_{u}  \mathcal{L}_2(\*h_\*w)  +\\& \phi_{l}^2 \mathcal{L}_3(\*h_\*w) + 2\phi_{l} \phi_{u} \mathcal{L}_4(\*h_\*w) +
\phi_{u}^2 \mathcal{L}_5(\*h_\*w),
\label{eq:def_SORL_app}
\end{split}
\end{align}

\begin{equation}
\begin{aligned}
& \mathcal{L}_1(\*h_\*w) = \sum_{i \in \mathcal{Y}}\underset{\substack{\Bar{\*x}_{l} \sim \mathbb{P}_{{l_i}}, \Bar{\*x}'_{l} \sim \mathbb{P}_{{l_i}},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_{l}), \*x^{+} \sim \mathcal{T}(\cdot|\Bar{\*x}'_l)}}{\mathbb{E}}\left[\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{+}\right)\right] , \\&
\mathcal{L}_2(\*h_\*w) = \underset{\substack{\Bar{\*x}_{u} \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_{u}), \*x^{+} \sim \mathcal{T}(\cdot|\Bar{\*x}_u)}}{\mathbb{E}}
\left[\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{+}\right)\right], \\&
\mathcal{L}_3(\*h_\*w) = \sum_{i, j\in \mathcal{Y}}
\underset{\substack{\Bar{\*x}_l \sim \mathbb{P}_{{l_i}}, \Bar{\*x}'_l \sim \mathbb{P}_{{l_{j}}},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_l), \*x^{-} \sim \mathcal{T}(\cdot|\Bar{\*x}'_l)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{-}\right)\right)^2\right], \\&
\mathcal{L}_4(\*h_\*w) = \sum_{i \in \mathcal{Y}}\underset{\substack{\Bar{\*x}_l \sim \mathbb{P}_{{l_i}}, \Bar{\*x}_u \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_l), \*x^{-} \sim \mathcal{T}(\cdot|\Bar{\*x}_u)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{-}\right)\right)^2\right], \\&
\mathcal{L}_5(\*h_\*w) = \underset{\substack{\Bar{\*x}_u \sim \mathbb{P}_{\rm id}, \Bar{\*x}'_u \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\Bar{\*x}_u), \*x^{-} \sim \mathcal{T}(\cdot|\Bar{\*x}'_u)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {\*h_\*w}\left(\*x^{-}\right)\right)^2\right].
\label{eq:def_SORL_detail_app}
\end{aligned}
\end{equation}

We can expand $\mathcal{L}_{\rm labeled}(\*h_\*w)$ and obtain

\begin{equation}
\small
\begin{aligned}
& \mathcal{L}_{\rm labeled}(\*h_\*w) =\sum_{\*x, \*x^{\prime} \in \mathcal{X}_{\rm id}}\left(\frac{\zeta_{\*x \*x^{\prime}}}{\sqrt{\zeta_\*x \zeta_{\*x^{\prime}}}}-\*f_\*x^{\top} \*f_{\*x^{\prime}}\right)^2 =\\& {\rm const} +
\sum_{\*x, \*x^{\prime} \in \mathcal{X}_{\rm id}}\left(-2 \zeta_{\*x \*x^{\prime}} \*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{\prime}\right)+\zeta_\*x \zeta_{\*x^{\prime}}\left(\*h_\*w(\*x)^{\top}\*h_\*w\left(\*x^{\prime}\right)\right)^2\right),
\end{aligned}
\end{equation}

where $\*f_\*x = \sqrt{\zeta_\*x}\*h_\*w(\*x)$ is a re-scaled version of $\*h_\*w(\*x)$.
At a high level, we follow the proof in  [HaoChen et al., 2021], while the specific form of loss varies with the different definitions of positive/negative pairs. The form of $\mathcal{L}_{\rm labeled}(\*h_\*w)$ is derived from plugging $\zeta_{\*x\*x'}$  and $\zeta_\*x$.

Recall that $\zeta_{\*x\*x'}$ is defined by

\begin{align*}
\zeta_{\*x\*x'} &= \phi_{l} \sum_{i \in \mathcal{Y}}\mathbb{E}_{\bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathbb{E}_{\bar{\*x}'_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \bar{\*x}_{l}) \mathcal{T}\left(\*x' | \bar{\*x}'_{l}\right)+ \phi_{u} \mathbb{E}_{\bar{\*x}_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x| \bar{\*x}_{u}) \mathcal{T}\left(\*x'| \bar{\*x}_{u}\right) ,
\end{align*}

and $\zeta_{\*x}$ is given by

\begin{align*}
\zeta_{\*x } &= \sum_{\*x^{\prime}}\zeta_{\*x\*x'} \\ &=\phi_{l} \sum_{i \in \mathcal{Y}}\mathbb{E}_{\bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathbb{E}_{\bar{\*x}'_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \bar{\*x}_{l}) \sum_{\*x^{\prime}} \mathcal{T}\left(\*x' | \bar{\*x}'_{l}\right)+ \phi_{u} \mathbb{E}_{\bar{\*x}_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x| \bar{\*x}_{u}) \sum_{x^{\prime}} \mathcal{T}\left(\*x' | \bar{\*x}_{u}\right) \\
&= \phi_{l} \sum_{i \in \mathcal{Y}}\mathbb{E}_{\bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \bar{\*x}_{l}) + \phi_{u} \mathbb{E}_{\bar{\*x}_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x| \bar{\*x}_{u}).
\end{align*}

Plugging in $\zeta_{\*x \*x^{\prime}}$ we have,

\begin{align*}
&-2 \sum_{\*x, \*x^{\prime} \in \mathcal{X}_{\rm id}}\zeta_{\*x \*x^{\prime}} \*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{\prime}\right) \\
= & -2 \sum_{\*x, \*x^{+} \in \mathcal{X}_{\rm id}} \zeta_{\*x \*x^{+}} \*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{+}\right)
\\ = & -2\phi_{l}  \sum_{i \in  \mathcal{Y}}\mathbb{E}_{\bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathbb{E}_{\bar{\*x}'_{l} \sim {\mathbb{P}_{l_i}}} \sum_{\*x, \*x^{\prime} \in \mathcal{X}_{\rm id}} \mathcal{T}(\*x | \bar{\*x}_{l}) \mathcal{T}\left(\*x' | \bar{\*x}'_{l}\right) \*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{\prime}\right) \\
& -2 \phi_{u} \mathbb{E}_{\bar{\*x}_{u} \sim {\mathbb{P}_{\rm id}}} \sum_{\*x, \*x^{\prime}} \mathcal{T}(\*x| \bar{\*x}_{u}) \mathcal{T}\left(\*x'| \bar{\*x}_{u}\right) \*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{\prime}\right)
\\ = & -2\phi_{l}  \sum_{i \in  \mathcal{Y}}\underset{\substack{\bar{\*x}_{l} \sim \mathbb{P}_{{l_i}}, \bar{\*x}'_{l} \sim \mathbb{P}_{{l_i}},\\\*x \sim \mathcal{T}(\cdot|\bar{\*x}_{l}), \*x^{+} \sim \mathcal{T}(\cdot|\bar{\*x}'_l)}}{\mathbb{E}}  \left[\*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{+}\right)\right] \\
& - 2\phi_{u}
\underset{\substack{\bar{\*x}_{u} \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\bar{\*x}_{u}), \*x^{+} \sim \mathcal{T}(\cdot|\bar{\*x}_u)}}{\mathbb{E}}
\left[\*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{+}\right)\right] \\ =& - 2\phi_{l}  \mathcal{L}_1(\*h_\*w)
- 2\phi_{u}  \mathcal{L}_2(\*h_\*w).
\end{align*}

Plugging $\zeta_{\*x}$ and $\zeta_{\*x'}$ we have,

\begin{align*}
&\sum_{\*x, \*x^{\prime} \in \mathcal{X}_{\rm id}}\zeta_\*x \zeta_{\*x^{\prime}}\left(\*h_\*w(\*x)^{\top}\*h_\*w\left(\*x^{\prime}\right)\right)^2 \\
= &  \sum_{\*x, \*x^{-} \in \mathcal{X}_{\rm id}}\zeta_\*x \zeta_{\*x^{-}}\left(\*h_\*w(\*x)^{\top}\*h_\*w\left(\*x^{-}\right)\right)^2 \\
= & \sum_{\*x, \*x^{\prime} \in \mathcal{X}_{\rm id}} \left( \phi_{l} \sum_{i \in  \mathcal{Y}}\mathbb{E}_{\bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \bar{\*x}_{l}) + \phi_{u} \mathbb{E}_{\bar{\*x}_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x| \bar{\*x}_{u}) \right)  \\&~~~~~~~~~~~\cdot \left(\phi_{l}  \sum_{j \in  \mathcal{Y}}\mathbb{E}_{\bar{\*x}'_{l} \sim {\mathbb{P}_{l_j}}} \mathcal{T}(\*x^{-} | \bar{\*x}'_{l}) + \phi_{u} \mathbb{E}_{\bar{\*x}'_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x^{-}| \bar{\*x}'_{u}) \right) \left(\*h_\*w(\*x)^{\top}\*h_\*w\left(\*x^{-}\right)\right)^2 \\
= & \phi_{l} ^ 2 \sum_{\*x, \*x^{-} \in \mathcal{X}_{\rm id}}  \sum_{i \in  \mathcal{Y}}\mathbb{E}_{\bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \bar{\*x}_{l}) \sum_{j \in  \mathcal{Y}}\mathbb{E}_{\bar{\*x}'_{l} \sim {\mathbb{P}_{l_j}}} \mathcal{T}(\*x^{-} | \bar{\*x}'_{l})\left(\*h_\*w(\*x)^{\top}\*h_\*w\left(\*x^{-}\right)\right)^2 \\
&+ 2\phi_{u} \phi_{l} \sum_{\*x, \*x^{-} \in \mathcal{X}_{\rm id}} \sum_{i \in  \mathcal{Y}}\mathbb{E}_{\bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \bar{\*x}_{l})  \mathbb{E}_{\bar{\*x}_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x^{-}| \bar{\*x}_{u}) \left(\*h_\*w(\*x)^{\top}\*h_\*w\left(\*x^{-}\right)\right)^2  \\
&+ \phi_{u}^2 \sum_{\*x, \*x^{-} \in \mathcal{X}_{\rm id}}  \mathbb{E}_{\bar{\*x}_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x| \bar{\*x}_{u}) \mathbb{E}_{\bar{\*x}'_{u} \sim {\mathbb{P}_{\rm id}}} \mathcal{T}(\*x^{-}| \bar{\*x}'_{u}) \left(\*h_\*w(\*x)^{\top}\*h_\*w\left(\*x^{-}\right)\right)^2 \\
= & \phi_{l}^2 \sum_{i \in  \mathcal{Y}}\sum_{j \in  \mathcal{Y}}\underset{\substack{\bar{\*x}_l \sim \mathbb{P}_{{l_i}}, \bar{\*x}'_l \sim \mathbb{P}_{{l_j}},\\\*x \sim \mathcal{T}(\cdot|\bar{\*x}_l), \*x^{-} \sim \mathcal{T}(\cdot|\bar{\*x}'_l)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} \*h_\*w\left(\*x^{-}\right)\right)^2\right] \\
&+ 2\phi_{u}\phi_{l}
\sum_{i \in  \mathcal{Y}}\underset{\substack{\bar{\*x}_l \sim \mathbb{P}_{{l_i}}, \bar{\*x}_u \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\bar{\*x}_l), \*x^{-} \sim \mathcal{T}(\cdot|\bar{\*x}_u)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {f}\left(\*x^{-}\right)\right)^2\right] \\ &+ \phi_{u}^2
\underset{\substack{\bar{\*x}_u \sim \mathbb{P}_{\rm id}, \bar{\*x}'_u \sim \mathbb{P}_{\rm id},\\\*x \sim \mathcal{T}(\cdot|\bar{\*x}_u), \*x^{-} \sim \mathcal{T}(\cdot|\bar{\*x}'_u)}}{\mathbb{E}}
\left[\left(\*h_\*w(\*x)^{\top} {f}\left(\*x^{-}\right)\right)^2\right]
\\ = & \phi_{l}^2 \mathcal{L}_3(\*h_\*w) + 2\phi_{u}\phi_{l} \mathcal{L}_4(\*h_\*w) + \phi_{u}^2\mathcal{L}_5(\*h_\*w).
\end{align*}

We complete this proof.

§.§ Derivation of the Data Representations

For the ID representations, we have the following equation.

\begin{equation}
\*Z^{(l)} = [\*D^{(l)}]^{-\frac{1}{2}} \*V_k^{(l)} [\*\Sigma_k^{(l)}]^{\frac{1}{2}}.
\end{equation}

It is easy to see that the following equation holds because of the  Eckart–Young–Mirsky theorem [Eckart & Young, 1936] as we use the top-$k$ SVD components of the matrix $\*A^{(l)}$ to approximate it (low-rank approximation).

For OOD representations, we have the following equation.

\begin{equation}
\*Z_{\rm ood}^{(l)} = [\*D_{\rm ood}^{(l)}]^{-\frac{1}{2}} \tilde{\*A}_{\rm OI}^{(l)}  \mathbf{V}_k^{(l)}  [\mathbf{\Sigma}_k^{(l)}]^{-\frac{1}{2}}.
\end{equation}

The above result can be obtained by the condition that the optimization problem in Equation <ref> is solved perfectly, i.e., $\tilde{\*A}_{\rm OI}^{(l)} = \*F_{\rm ood}^{(l)} \*F^{(l)\top}$. Note that it is easy to check that $ \*F^{(l)} = \*V_k^{(l)} [\*\Sigma_k^{(l)}]^{\frac{1}{2}}$, if we multiply $ \mathbf{V}_k^{(l)}  [\mathbf{\Sigma}_k^{(l)}]^{-\frac{1}{2}}$ to both sides of the equation $\tilde{\*A}_{\rm OI}^{(l)} = \*F_{\rm ood}^{(l)} \*F^{(l)\top}$, we can get:

\begin{equation}
\tilde{\*A}_{\rm OI}^{(l)} \mathbf{V}_k^{(l)}  [\mathbf{\Sigma}_k^{(l)}]^{-\frac{1}{2}} = \*F_{\rm ood}^{(l)} [\*\Sigma_k^{(l)}]^{\frac{1}{2}} \*V_k^{(l)\top}  \mathbf{V}_k^{(l)}  [\mathbf{\Sigma}_k^{(l)}]^{-\frac{1}{2}} = \*F_{\rm ood}^{(l)}.
\end{equation}

Note that $\*F_{\rm ood}^{(l)}  =[\*D_{\rm ood}^{(l)}]^{\frac{1}{2}} \*Z_{\rm ood}^{(l)}$ and thus we can get $\*Z_{\rm ood}^{(l)} = [\*D_{\rm ood}^{(l)}]^{-\frac{1}{2}} \tilde{\*A}_{\rm OI}^{(l)}  \mathbf{V}_k^{(l)}  [\mathbf{\Sigma}_k^{(l)}]^{-\frac{1}{2}}$. Therefore we have completed the proof.

Design Rationale. Here we explain the design rationale of the optimization problem in Equation <ref> to get the OOD representation $\*F_{\rm ood}^{(l)}$ and $\*Z_{\rm ood}^{(l)}$, which is inspired by the literature in out-of-sample extension.

The out-of-sample extension is a statistical approach that computes the embeddings of new vertices in a graph with the existing in-sample embeddings and the similarity measurements [Bengio et al., 2003, Levin et al., 2018]. The goal is to avoid the repeated computational cost of embedding calculations on a large graph when a new vertex emerges. Most of the current works focused on graph Laplacian embedding [Belkin & Niyogi, 2003, Trosset & Priebe, 2008, Belkin et al., 2006, Quispe et al., 2016, Jansen et al., 2015], while a few works relied on the adjacency spectral embedding [Sussman et al., 2012, Tang et al., 2013] for embedding extension. Our framework is similar to the least-squares optimization approach in out-of-sample extension, which derives the out-of-sample embeddings using the adjacency matrix between the in-sample and out-of-sample data (Please refer to Section 3.1 of [Levin et al., 2018] for detailed derivation).

§.§ Upper Bound of the Linear Probing Loss

[Recap of Lemma <ref> in the main paper]
Denote the $\*y \in \mathbb{R}^{(N+M)\times 2}$ as a matrix contains the one-hot labels for ID and OOD features in $\*Z_{\rm all}$. We have:

\begin{equation}
% \small
R(\*Z_{\rm all}) \leq  \frac{2}{N+M}\operatorname{Tr}\left(\left(\mathbf{I}-\*Z_{\rm all}\*Z_{\rm all}^{\dagger}\right) \mathbf{y} \mathbf{y}^\top\right).
\end{equation}

Recall the definition of the linear probing loss is defined as follows:

\begin{equation}
R(\*Z_{\rm all}) \triangleq \min _{\boldsymbol{\theta} \in \mathbb{R}^{k \times 2 }} \mathbb{E}_{\*z \in \*Z_{\rm all}} \mathds{1}[y(\*z) \neq \*g_{\boldsymbol{\theta}}(\*z)].
% \vspace{-1em}
\end{equation}

According to Lemma 5.1 in [Sun et al., 2023], we can get the upper bound of $R(\*Z_{\rm all})$ as follows:

\begin{equation}
R(\*Z_{\rm all}) \leq  \frac{2}{N+M} \min _{\boldsymbol{\theta} \in \mathbb{R}^{k \times 2 }} \|\*y - \*Z_{\rm all}\boldsymbol{\theta} \|_F^2.
\end{equation}

Given the fact that the closed-form solution of the above minimization problem is $\*Z_{\rm all}^{\dagger}\*y$ where $\*Z_{\rm all}^{\dagger}$ denotes the Moore-Penrose inverse of the feature matrix $\*Z_{\rm all}$, we can rewrite the right side of the above inequality as follows:

\begin{equation}
\min _{\boldsymbol{\theta} \in \mathbb{R}^{k \times 2 }} \|\*y - \*Z_{\rm all}\boldsymbol{\theta} \|_F^2 = \|\*y - \*Z_{\rm all}\*Z_{\rm all}^{\dagger}\*y\|_F^2.
\end{equation}

Simplify it further, we have

\begin{equation}
\|\*y - \*Z_{\rm all}\*Z_{\rm all}^{\dagger}\*y\|_F^2 = \|(\mathbf{I}-\*Z_{\rm all}\*Z_{\rm all}^{\dagger}) \mathbf{y} \|_F^2 = \operatorname{Tr}\left(\left(\mathbf{I}-\*Z_{\rm all}\*Z_{\rm all}^{\dagger}\right) \mathbf{y} \mathbf{y}^\top\right).
\end{equation}

Therefore we finished the proof.

§.§ Necessary Lemmas for Theorem <ref>

Following the definitions in Equations <ref> and <ref>, the error difference for linear probing between the unlabeled and labeled case (with a perturbation magnitude $ \phi_l$) is upper bounded by the following term:

\begin{equation}
\mathcal{G}(\phi_l) \geq \frac{2}{3(N+M)} \phi_l \cdot \max \lambda\left(\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)\right) \cdot \operatorname{Tr}\left(\left(\*Z_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^{\top}\right)^{\prime}\*y\*y^{\top}\right)\bigg|_{\phi_l=0},
\end{equation}

where $\max \lambda\left(\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)\right)$ means the maximum eigenvalue of the matrix $\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)$.

From the definition of the derivative, we know that $ \mathcal{G}(\phi_l)=-\left.\frac{\mathrm{d} \overline{R}(\*Z_{\rm all}(\phi_l))}{\mathrm{d} \phi_l}\right|_{\phi_l=0} \cdot  \phi_l$, we then investigate the key component $-\left.\frac{\mathrm{d} \overline{R}(\*Z_{\rm all}(\phi_l))}{\mathrm{d} \phi_l}\right|_{\phi_l=0}$ as follows. Recall that we have

\begin{equation}
\small
\begin{aligned}
&-\left.\frac{\mathrm{d} \overline{R}(\*Z_{\rm all}(\phi_l))}{\mathrm{d} \phi_l}\right|_{\phi_l=0}=   {\rm Tr} \left.\left(  \frac{\rm d\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger}  }{\rm d \phi_l} \*y\*y^{\top}\right)  \right|_{\phi_l=0} \cdot \frac{2\phi_l}{N+M}   \\& = \frac{2\phi_l}{N+M} \cdot    \rm Tr\bigg(\bigg[ \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}     +  \*Z_{\rm all}(\phi_l)\bigg(-\left( \*Z_{\rm all}(\phi_l)^\top  \*Z_{\rm all}(\phi_l)\right)^{-1}\bigg( \*Z_{\rm all}'(\phi_l)^\top \*Z_{\rm all}(\phi_l)\\&  \quad \quad \quad \quad\quad \quad +\*Z_{\rm all}(\phi_l)^\top \*Z_{\rm all}'(\phi_l)\bigg)\left(\*Z_{\rm all}(\phi_l)^\top \*Z_{\rm all}(\phi_l)\right)^{-1} \*Z_{\rm all}(\phi_l)^\top +\left(\*Z_{\rm all}(\phi_l)^\top \*Z_{\rm all}(\phi_l)\right)^{-1} \*Z_{\rm all}'(\phi_l)^\top\bigg) \bigg] \*y\*y^{\top}\bigg)\bigg|_{\phi_l=0} \\&
=   \frac{2\phi_l}{N+M}\rm Tr\bigg( \bigg[ \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}-\left(\*Z_{\rm all}(\phi_l)^{\dagger}\right)^\top \*Z_{\rm all}'(\phi_l)^\top \*Z_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}\\& \quad \quad \quad \quad\quad \quad-\left(\*Z_{\rm all}(\phi_l)^{\dagger}\right)^\top \*Z_{\rm all}(\phi_l)^\top \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}+\left(\*Z_{\rm all}(\phi_l)^{\dagger}\right)^\top \*Z_{\rm all}'(\phi_l)^\top \bigg]\*y\*y^{\top} \bigg)\bigg|_{\phi_l=0}\\&
= \frac{2\phi_l}{N+M}\rm Tr\bigg(
\bigg[\*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}-\left(\*Z_{\rm all}(\phi_l)^{\dagger}\right)^\top\*Z_{\rm all}'(\phi_l)^\top \*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger}\\& \quad \quad \quad \quad\quad \quad-(\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})^\top \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}+\left(\*Z_{\rm all}(\phi_l)^{\dagger}\right)^\top \*Z_{\rm all}'(\phi_l)^\top \bigg] \*y\*y^{\top}
\bigg) \bigg|_{\phi_l=0} \\& = \frac{2\phi_l}{N+M}
\rm Tr\left( \bigg[(\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})^\top \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}+\left(\*Z_{\rm all}(\phi_l)^{\dagger}\right)^\top \*Z_{\rm all}'(\phi_l)^\top(\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})\bigg] \*y\*y^{\top} \right) \bigg|_{\phi_l=0}   \\&
= \frac{2\phi_l}{N+M} \rm Tr\left( \bigg[(\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger}) \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}+\left(\*Z_{\rm all}(\phi_l)^{\dagger}\right)^\top \*Z_{\rm all}'(\phi_l)^\top(\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})^\top \bigg]   \*y\*y^{\top}\right)  \bigg|_{\phi_l=0}  \\&
=  \frac{2\phi_l}{N+M} \rm Tr\left( \bigg[(\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger}) \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}+\left[(\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})  \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger}\right]^\top\bigg] \*y\*y^{\top} \right)  \bigg|_{\phi_l=0}
\\&
= \frac{2\phi_l}{N+M} \rm Tr\left(  (\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger}) \cdot \left( \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger} + (\*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger})^\top \right)  \*y\*y^{\top} \right)  \bigg|_{\phi_l=0}   \\&
\geq\frac{2\phi_l}{N+M} \rm Tr\left(  (\frac{2}{3}\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger}) \cdot \left( \*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger} + (\*Z_{\rm all}'(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger})^\top \right)   \*y\*y^{\top}\right)  \bigg|_{\phi_l=0}
\\ &
\geq \frac{2\phi_l}{N+M}  \left[\nu(\frac{2}{3}\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})+\pi(\frac{2}{3}\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})\right] \cdot \\&  \quad \quad \quad \quad\quad \quad \rm Tr\bigg(\bigg( \*Z_{\rm all}'(\phi_l) (\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l))^{-1}\*Z_{\rm all}(\phi_l)^\top  + \*Z_{\rm all}(\phi_l) (\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l))^{-1}\*Z_{\rm all}'(\phi_l)^\top \bigg)\*y\*y^{\top}\bigg) \bigg|_{\phi_l=0}\\
& =   \frac{2\phi_l}{N+M}  \frac{1}{3} \cdot \rm Tr\bigg( \bigg((\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l))^{-1}\*Z_{\rm all}(\phi_l)^\top  \*Z_{\rm all}'(\phi_l) +  (\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l))^{-1} \*Z_{\rm all}'(\phi_l)^\top\*Z_{\rm all}(\phi_l)\bigg) \*y\*y^{\top}\bigg)\bigg|_{\phi_l=0}
\\&
\geq   \frac{2\phi_l}{N+M}\frac{1}{3}  \min \lambda((\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l))^{-1}) \cdot   \rm Tr\bigg(\bigg(  \*Z_{\rm all}(\phi_l)^\top \*Z_{\rm all}'(\phi_l) + \*Z_{\rm all}'(\phi_l)^\top\*Z_{\rm all}(\phi_l)\bigg)\*y\*y^{\top}\bigg)\bigg|_{\phi_l=0}
\\
&   =  \frac{2\phi_l}{3(N+M)} \max \lambda(
\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l)) \cdot   \rm Tr\bigg(  \bigg((\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^\top)'  \bigg) \*y\*y^{\top}\bigg)\bigg|_{\phi_l=0}\,
\end{aligned}
\end{equation}

where $\nu(\frac{2}{3}\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})$ and $\pi(\frac{2}{3}\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger})$ denote the
smallest negative eigenvalues and the smallest positive eigenvalues[The value of the two terms are $\frac{2}{3}$ and $-\frac{1}{3}$ according to <https://math.stackexchange.com/questions/188129>] of the matrix $\frac{2}{3}\*I-\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^{\dagger}$.

The first seven equations calculate the derivative w.r.t.  the perturbation magnitude $\phi_l$ and use the cyclic property of the trace operator. The first inequality is true because we have

\begin{equation}
\scriptsize
\frac{1}{3}\rm Tr((\*Z'_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger} + (\*Z'_{\rm all}(\phi_l) \*Z_{\rm all}(\phi_l)^{\dagger})^\top )\*y\*y^{\top})\big|_{\phi_l=0} \geq \frac{1}{3}\max \lambda(
\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l)) \max \lambda(\*y\*y^{\top} ) \cdot   \rm Tr(  (\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^\top)'  )\big|_{\phi_l=0}.
\end{equation}

Since we know $\max \lambda(
\*Z_{\rm all}(\phi_l)^\top\*Z_{\rm all}(\phi_l))\big|_{\phi_l=0} > 0$ (Lemma <ref>) and $\max \lambda(\*y\*y^{\top})>0$, and $\rm Tr(  (\*Z_{\rm all}(\phi_l)\*Z_{\rm all}(\phi_l)^\top)'  )\big|_{\phi_l=0}$ is lower bounded and can be large than 0 (Lemmas <ref> and <ref>).  The second inequality holds because of the main theorem in [Baksalary & Puntanen, 1992]. The third inequality holds because the inequality for the trace of matrix product of two square matrices [Fang et al., 1994], i.e., $\rm Tr(\*H \*M) \geq \min \lambda(\*H) \cdot \rm Tr( \*M)$.

Suppose the perturbation magnitude $\phi_l$ is 0, denote the input feature of linear probing as $\*Z_{\rm all}(0)$, then we have that:

\begin{equation}
\max \lambda\left(\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)\right)\bigg|_{\phi_l=0} >  0,
\end{equation}

here $\max \lambda\left(\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)\right)$ means the maximum eigenvalue of the matrix $\*Z_{\rm all}(\phi_l)^{\top} \*Z_{\rm all}(\phi_l)$.

Since we know that the column rank of the ID feature matrix $\*Z(0) \in \mathbb{R}^{N\times k}$ is $k$, then when adding $M$ rows of OOD features  $\*Z_{\rm ood}(0)$ to get $\*Z_{\rm all}(0)$ will not increase the column rank. Therefore, the rank of matrix $\*Z_{\rm all}(0)$ is equal to $k$, which means $\*Z_{\rm all}(0)$ has a full column rank. Thus, the matrix $\*Z_{\rm all}(0)^{\top} \*Z_{\rm all}(0)$  is positive definite [Proof idea is shown here <https://math.stackexchange.com/questions/2202242>], which means the eigenvalues of $\*Z_{\rm all}(0)^{\top} \*Z_{\rm all}(0)$  are all greater than 0 and the lemma is proved.

If Assumption <ref> holds, the lower bound for  $  \operatorname{Tr}\left(\left(\mathbf{V}_{k}(\phi_l) \boldsymbol{\Sigma}_{k}(\phi_l) \mathbf{V}_{k}(\phi_l)^{\top}\right)^{\prime}\right)  \bigg|_{\phi_l=0}$ is given as follows:

\begin{equation}
\operatorname{Tr}\left(\left(\mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_{k}(\phi_l) \mathbf{V}_{k}(\phi_l)^{\top}\right)^{\prime}\right)  \bigg|_{\phi_l=0}\geq \sum_{i=1}^c \|\mathfrak{q}_i\|_F^2-
2r^2  \sum_{i=1}^c\|\mathfrak{q}_{i} \|_1,
\end{equation}

where $\mathfrak{q} \in \mathbb{R}^{N\times c}$ with each column defined as $(\mathfrak{q}_i)_\*x = \mathbb{E}_{\Bar{\*x}_{l} \sim {\mathbb{P}_{l_i}}} \mathcal{T}(\*x | \Bar{\*x}_{l}), \*x \in \mathcal{X}_{\rm id}$, and $r$ is the maximum $l_2$ norm of the ID representations, i.e.,  $r = \max_{\*z \in \*Z^{(u)}} \|\*z\|_2$.

As $\mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_{k}(\phi_l) \mathbf{V}_{k}(\phi_l)^{\top}$ denotes the top-$k$ SVD components of the matrix $\tilde{\*A}(\phi_l)$, according to Equation <ref>, we rewrite it using the eigenvalues and the eigen projectors as follows.

\begin{equation}
\tiny
\begin{aligned}
\operatorname{Tr}\left(\left(\mathbf{V}_k(\phi_l) \boldsymbol{\Sigma}_{k}(\phi_l) \mathbf{V}_{k}(\phi_l)^{\top}\right)^{\prime}\right)  \bigg|_{\phi_l=0} &=  \sum_{j=1}^{k}  { \rm Tr}\bigg(  [  \*D(\phi_l)^{-\frac{1}{2}} \boldsymbol{\lambda}_j(\phi_l) \*\Phi_j(\phi_l) \*D(\phi_l)^{-\frac{1}{2}}]'  \bigg)\bigg|_{\phi_l=0} \\ &=
\sum_{j=1}^k \operatorname{Tr}\left(\left[\*D(\phi_l)^{-\frac{1}{2}}\right]^{\prime} \boldsymbol{\lambda}_j^{ (u)} \*\Phi_j^{ (u)}+\boldsymbol{\lambda}_j^{ (u)} \*\Phi_j^{ (u)}\left[\*D(\phi_l)^{-\frac{1}{2}}\right]^{\prime}+\left[\boldsymbol{\lambda}_j(\phi_l)\right]^{\prime} \*\Phi_j^{ (u)}+\boldsymbol{\lambda}_j^{ (u)}\left[\*\Phi_j(\phi_l)\right]^{\prime}\right)\bigg|_{\phi_l=0},
\end{aligned}
\label{eq68_app}
\end{equation}

where $\boldsymbol{\lambda}_j^{(u)}$ and $\*\Phi_j^{(u)}$ are the $j$-th eigenvalue and eigen projector of matrix $\tilde{\*A}(\phi_l)$ when $\phi_l=0$. Moreover, assume $\tilde{\*A}^{(u)}$ to be the normalized adjacency matrix when $\phi_l=0$, recall $\*D(\phi_l) = \*I_{N \times N} + \phi_l \*D_l$ where $\*D_l = \sum_{i=1}^c   {\rm diag}(\mathfrak{q}_i)$ (Equation <ref>), we have the following calculation for the derivatives:

\begin{equation}
\left[\*D(\phi_l)^{-\frac{1}{2}}\right]^{\prime} = -\frac{1}{2} \*D_l.
\end{equation}

\begin{equation}
\begin{aligned} {\left.[\tilde{\*A}(\phi_l)]^{\prime}\right|_{\phi_l=0} } & =\left.\left[\*D(\phi_l)^{-\frac{1}{2}} \*A(\phi_l) \*D(\phi_l)^{-\frac{1}{2}}\right]^{\prime}\right|_{\phi_l=0} \\ & =\left[\*D(\phi_l)^{-\frac{1}{2}}\right]^{\prime} \tilde{\*A}^{(u)}+[\*A(\phi_l)]^{\prime}+\tilde{\*A}^{(u)}\left[\*D(\phi_l)^{-\frac{1}{2}}\right]^{\prime} \\ & =-\frac{1}{2} \*D_l \tilde{\*A}^{(u)}+\sum_{i=1}^c \mathfrak{q_i q_i}^{\top}-\frac{1}{2} \tilde{\*A}^{(u)} \*D_l\end{aligned}
\label{eq70_pp}
\end{equation}

To get the derivative of the eigenvalues, according to Equation 3 in [Greenbaum et al., 2020],

\begin{equation}
\begin{aligned} {\left.\left[\boldsymbol{\lambda}_j(\phi_l)\right]^{\prime}\right|_{\phi_l=0} } & =\operatorname{Tr}\left(\*\Phi_j^{ (u)}[\tilde{\*A}(\phi_l)]^{\prime}\right) \bigg|_{\phi_l=0}\\ & =\operatorname{Tr}\left(\*\Phi_j^{ (u)}\left(-\frac{1}{2} \*D_l \tilde{\*A}^{(u)}+\sum_{i=1}^c \mathfrak{q_i q_i}^{\top}-\frac{1}{2} \tilde{\*A}^{(u)} \*D_l\right)\right) \\ & =\operatorname{Tr}\left(-\frac{\boldsymbol{\lambda}_j^{ (u)}}{2} \*D_l \*\Phi_j^{ (u)}+\*\Phi_j^{ (u)} \sum_{i=1}^c \mathfrak{q_i q_i}^{\top}-\frac{\boldsymbol{\lambda}_j^{ (u)}}{2} \*\Phi_j^{ (u)} \*D_l\right) \\ & =\operatorname{Tr}\left(\*\Phi_j^{ (u)}\left(\sum_{i=1}^c \mathfrak{q_i q_i}^{\top}-\boldsymbol{\lambda}_j^{ (u)} \*D_l\right)\right) .\end{aligned}
\label{eq71_pp}
\end{equation}

To get the derivative of the eigenvectors, according to Equation 10 in [Greenbaum et al., 2020],

\begin{equation}
\small
\begin{aligned} {\left.\left[\*\Phi_j(\phi_l)\right]^{\prime}\right|_{\phi_l=0} } & =\left(\boldsymbol{\lambda}_j^{ (u)} \*I_N-\tilde{\*A}^{(u)}\right)^{\dagger}[\tilde{\*A}(\phi_l)]^{\prime} \*\Phi_j^{ (u)}+\*\Phi_j^{ (u)}[\tilde{\*A}(\phi_l)]^{\prime}\left(\boldsymbol{\lambda}_j^{ (u)} \*I_N-\tilde{\*A}^{(u)}\right)^{\dagger} \\
& =\sum_{i \neq j}^N \frac{1}{\boldsymbol{\lambda}_j^{ (u)}-\boldsymbol{\lambda}_i^{ (u)}}\left(\*\Phi_i^{ (u)}[\tilde{\*A}(\phi_l)]^{\prime} \*\Phi_j^{ (u)}+\*\Phi_j^{ (u)}[\tilde{\*A}(\phi_l)]^{\prime} \*\Phi_i^{ (u)}\right) \\
& =\sum_{i \neq j}^N \frac{1}{\boldsymbol{\lambda}_j^{ (u)}-\boldsymbol{\lambda}_i^{ (u)}}\left(\*\Phi_i^{ (u)}\left(-\frac{1}{2} \*D_l \tilde{\*A}^{(u)}+\sum_{i=1}^c \mathfrak{q_i q_i}^{\top}-\frac{1}{2} \tilde{\*A}^{(u)} \*D_l\right) \*\Phi_j^{ (u)}+\*\Phi_j^{ (u)}(\ldots) \*\Phi_i^{ (u)}\right) \\