SpectralGap: Graph-Level Out-of-Distribution Detection via Laplacian Eigenvalue Gaps

1 Introduction

Graph-structured data has become increasingly prevalent in various domains, including social networks, bioinformatics, and recommendation systems [Wu et al., 2020; Hamilton et al., 2017; Huang et al., 2024]. Graph Neural Networks (GNNs) have emerged as powerful tools for learning representations and making predictions on such data, achieving state-of-the-art performance in numerous tasks [Kipf and Welling, 2016; Veliˇckovi´c et al., 2017; Xia et al., 2021; Ju et al., 2024; Qiao et al., 2025]. However, as GNNs are increasingly deployed in real-world applications, ensuring their reliability and robustness becomes paramount. One critical challenge in this context is the detection of out-ofdistribution (OOD) samples at the graph level, which is essential for maintaining the integrity and trustworthiness of GNN-based systems [Liu et al., 2023; Ma et al., 2022; Qiao et al., 2023]. The importance of OOD detection in machine learning has been well-established in domains such as computer vision and natural language processing [Hendrycks and Gimpel, 2016; Liang et al., 2017; Zhang et al., 2022; Mirakhorli et al., 2020]. However, the unique characteristics of graph-structured data pose additional challenges for OOD detection. Unlike images or text, graphs exhibit complex structural properties and relational information that must be considered. Moreover, the potential for subtle distributional shifts in graph data can be more nuanced and difficult to detect using traditional methods [Qiao et al., 2024; Yang et al., 2021; Qiu et al., 2022].

∗Corresponding authors: Ziyue Qiao (ziyuejoe@gmail.com) and Zechao Li (zechao.li@njust.edu.cn).

Recent years have witnessed growing interest in graphlevel OOD detection, with researchers exploring various approaches. Contrastive learning-based methods have shown promise by leveraging the structural information of graphs [Li et al., 2022; Qiu et al., 2022; Liu et al., 2024], while energy-based models have demonstrated effectiveness in capturing the underlying data distribution [Wu et al., 2023; Shen et al., 2024]. Despite these advancements, existing methods often require significant modifications to GNN architectures or extensive additional training, limiting their practical applicability in real-world scenarios where model retraining may be costly or infeasible[Ji et al., 2023; Wang et al., 2024].

In this work, we present a novel perspective on graphlevel OOD detection by focusing on the spectral properties of graphs. Our key observation is a significant difference in the relationship between the largest and second-largest eigenvalues of the Laplacian matrix for in-distribution (ID) and OOD graph samples. As illustrated in Figure 1(a), OOD samples frequently exhibit anomalous spectral gaps - the difference between the largest and second-largest eigenvalues - compared to ID samples. This observation provides a strong intuition for OOD detection: the spectral gap reflects fundamental structural properties of a graph, such as its connectivity and community structure [Chung and Graham, 1997]. ID samples, which share similar structural characteristics, tend to have consistent spectral gaps. In contrast, OOD samples, with potentially different underlying generative processes, often display distinct spectral properties, manifesting as larger or more varied spectral gaps. This phenomenon can be attributed to the fact that the spectral gap is closely related to the mixing time of random walks on the graph and the graph's expansion properties [Hoory et al., 2006], which are likely to differ between ID and OOD samples.

Motivated by this insight, we propose SpecGap, an effective post-hoc approach for OOD detection on graphs. SpecGap leverages the observed spectral gap anomalies by adjusting the high-level features of a graph. Specifically, it subtracts the component associated with the second-largest eigenvalue, scaled by the spectral gap, from the high-level features. This adjustment effectively normalizes the spectral properties of OOD samples, bringing them closer to the distribution of ID samples, as demonstrated in Figure 1(c).

The proposed SpecGap method offers several key advantages:

• Theoretical Grounding: By focusing on fundamental spectral properties, SpecGap provides a theoretically grounded approach to OOD detection, offering insights into the structural differences between ID and OOD graphs.
• Ease of Integration: As a parameter-free post-hoc method, SpecGap can be seamlessly integrated into existing GNN models without requiring additional training or architectural modifications.
• Computational Efficiency: The method relies on efficient eigenvalue computations, making it suitable for large-scale graph datasets.
• State-of-the-Art Performance: Our extensive experiments demonstrate that SpecGap significantly outperforms existing methods, reducing the average false positive rate (FPR95) by 15.40% compared to the previous best approach.

In the following sections, we provide a detailed description of the SpecGap method, present comprehensive theoretical analyses to support our empirical findings, and demonstrate its effectiveness across multiple benchmark datasets. The implementation code will be released upon acceptance.

2 SpecGap: Spectral Gap-based OOD Detection

2.1 Preliminaries

Let G = (V, E) be an undirected graph with n vertices. The Laplacian matrix L of G is defined as:

where D is the degree matrix and A is the adjacency matrix of G. The degree matrix D is diagonal with Dii being the degree of vertex i, and the adjacency matrix A is defined as:

The Laplacian matrix L is symmetric and positive semidefinite, with n non-negative real eigenvalues 0 = λ1 ≤ λ2 ≤ ... ≤ λn. These eigenvalues provide crucial information about the graph's structure and connectivity.

The spectral gap, defined as ∆λ = λn - λn-1, plays a significant role in graph theory. Intuitively, the spectral gap represents the connectivity and expansion properties of the graph. A larger spectral gap indicates better connectivity and faster information diffusion within the graph. In the context of OOD detection, we hypothesize that in-distribution (ID) and out-of-distribution (OOD) samples may exhibit different spectral gap characteristics, reflecting fundamental differences in their underlying graph structures.

2.2 SpecGap Algorithm

Feature Adjustment

Given a high-level feature map X ∈ RC×HW from a Graph Neural Network (GNN), where C is the number of channels and H ×W is the spatial dimension, our SpecGap algorithm adjusts this feature based on the spectral properties of the graph it represents.

First, we compute the Laplacian matrix L of the original input graph. Then, we calculate its two largest eigenvalues λn and λn-1, along with the eigenvector un-1 corresponding to λn-1.

The spectral gap is computed as:

Next, we project the feature map X onto the subspace spanned by un-1:

Now, we adjust the feature map by subtracting the component associated with λn-1, scaled by the spectral gap:

This adjustment effectively removes the influence of the second-largest eigenvalue, which we hypothesize is more prominent in OOD samples. The scaling by ∆λ ensures that the adjustment is proportional to the spectral gap, which differs between ID and OOD samples.

Intuitively, this adjustment can be seen as "normalizing" the spectral properties of the graph. For OOD samples, which may have anomalous spectral gaps, this normalization brings their feature representations closer to those of ID samples, potentially making them easier to detect.

Integration into GNN Models

The adjusted feature map X′ is seamlessly integrated back into the GNN model. Specifically, X′ replaces the original feature map X in the subsequent layers of the network. The process can be formalized as:

where hl+1 is the output of the (l +1)-th layer, fl is the layer function, and A is the adjacency matrix.

This integration allows the SpecGap adjustment to influence the entire downstream processing of the GNN. The effect of this adjustment on the model's output can be significant: 1) Enhanced Discriminability: By normalizing the spectral properties, the adjusted features may become more discriminative between ID and OOD samples. 2) Improved Generalization: The spectral gap-based adjustment may help the model focus on more robust, graph-structural features, potentially improving generalization. 3) Calibrated Confidence: For OOD samples, the adjustment may lead to less overconfident predictions, as their anomalous spectral properties are mitigated.

Mathematically, we can express the impact on the model's output y as:

where g is the final classification layer and L is the total number of layers.

The SpecGap adjustment essentially modifies the feature space in which the GNN operates, potentially creating a more suitable space for distinguishing between ID and OOD samples. This modification is based on fundamental graph properties, making it a theoretically grounded approach to improving OOD detection in GNNs.

2.3 Efficient Computation of Spectral Gap

Lanczos Algorithm

To efficiently compute the two largest eigenvalues λn and λn-1 of the Laplacian matrix L, we employ the Lanczos algorithm. This iterative algorithm is particularly effective for large, sparse matrices, making it well-suited for graph Laplacians. The Lanczos algorithm builds an orthonormal basis for the Krylov subspace:

where v is an initial vector, typically chosen randomly. The algorithm proceeds by iteratively constructing a sequence of orthonormal vectors {qj}kj=1 and scalars {αj}kj=1 and {βj }k-1 j=1 . At each iteration, the algorithm computes:

This process generates a tridiagonal matrix Tk ∈ Rk×k :

The eigenvalues of Tk approximate the extreme eigenvalues of L. Specifically, the largest eigenvalue of Tk converges to λn, and the second largest to λn-1. Regarding convergence, the error in the j-th Ritz value θj (an approximation to an eigenvalue) is bounded by:

where C is a constant. This bound demonstrates that the convergence is faster when the eigenvalues are well-separated.

The computational complexity of the Lanczos algorithm is O(k·nnz(L)), where k is the number of iterations and nnz(L) is the number of non-zero elements in L. For sparse graphs, this is significantly more efficient than full eigendecomposition.

Implementation Details

The implementation of the Lanczos algorithm requires careful consideration of numerical stability and efficiency. We initialize q1 as a random unit vector, computed by normalizing a vector of random numbers drawn from a standard normal distribution:

The matrix-vector product Lqj is computed efficiently by leveraging the sparsity of the Laplacian matrix:

where D and A are the degree and adjacency matrices, respectively. To maintain numerical stability, we perform full reorthogonalization after each iteration:

where Qj = [q1, ..., qj]. The eigenvalues of the tridiagonal matrix Tk are computed using a stable method such as the QR algorithm. The two largest eigenvalues of Tk serve as our approximations for λn and λn-1.

The iteration process continues until the change in the estimated eigenvalues falls below a predetermined threshold ϵ:

where λ(k) n and λ(k) n-1 are the estimates at the k-th iteration.

By implementing these details, we can efficiently and stably compute the spectral gap ∆λ = λn -λn-1 for use in our SpecGap algorithm, even for large graphs.

3 Experiments

To comprehensively evaluate the effectiveness of the SpecGap method, we have designed a series of experiments. This section will detail the experimental setup, main results analysis, and in-depth ablation studies.

3.1 Experimental Setup

Datasets

Our experiments utilize five pairs of datasets, representing indistribution (ID) and out-of-distribution (OOD) data respectively. These pairs are selected from the TU datasets[Morris et al., 2020] and Open Graph Benchmark (OGB)[Hu et al., 2020], covering molecular, social network, and bioinformatics domains. Each pair belongs to the same field but exhibits a mild domain shift, providing an ideal testbed for OOD detection. We follow the dataset split strategy from previous works[Liu et al., 2023]: 80% of ID graphs for training, and the remaining 20% split equally between validation and test sets. These latter sets are augmented with an equal number of OOD graphs, creating a realistic and challenging evaluation scenario.

Baselines and Our Method

Our experiments include several baseline methods, categorized into unsupervised and supervised approaches. The unsupervised baselines are GCL[You et al., 2020] and JOAO[You et al., 2021], while the supervised ones are GIN[Xu et al., 2018] and PPGN[Maron et al., 2019]. We also compare our method with state-of-the-art OOD detection methods, including AAGOD[Guo et al., 2023], GOODD[Liu et al., 2023], OCGIN[Zhao and Akoglu, 2023], and GLocalKD[Ma et al., 2022]. Our proposed method, SpecGap, is applied to all these baseline methods as well as AAGOD to demonstrate its versatility and effectiveness as a post-processing technique.

Evaluation Metrics

To ensure a comprehensive evaluation, we employ three widely-used metrics in OOD detection tasks: Area Under the Receiver Operating Characteristic Curve (AUC), Area Under the Precision-Recall Curve (AUPR), and False Positive Rate at 95% True Positive Rate (FPR95). These metrics provide a holistic view of the method's performance across different operating points.

Implementation Details

In our implementation, SpecGap is applied to the final layer's feature map of the GNN models. This choice allows us to leverage the most abstract and task-relevant features learned by the network. For Graph Transformer architectures, we apply SpecGap after the self-attention layer, enabling it to refine the attention-weighted features. This consistent application across different architectures demonstrates the flexibility and generality of our approach.

3.2 Main Results

To evaluate the effectiveness of SpecGap, we conduct experiments on various well-trained GNNs, including unsupervised methods (GCL, JOAO) and supervised methods (GIN, PPGN). We used the SSD/LOF scoring function from [Guo et al., 2023] to enable these baseline methods to have OOD detection capabilities.Tables 1 and 2 present the results on unsupervised and supervised GNNs, respectively.The results in Tables 1 and 2 demonstrate the superior performance of SpecGap across various GNN architectures and datasets.

The substantial and consistent performance improvements achieved by SpecGap across a diverse range of graph neural network architectures and datasets. SpecGap's effectiveness is particularly evident in its ability to significantly enhance OOD detection capabilities, as reflected by the marked increases in AUC and AUPR scores, coupled with notable reductions in FPR95 values. For instance, when applied to the GCL S model on the BZR/COX2 dataset pair, SpecGap elevates the AUC from 75.00% to an impressive 98.56%, while simultaneously reducing the FPR95 from 47.50% to a mere 12.69%. This dramatic improvement underscores SpecGap's prowess in refining the feature space to accentuate the distinctions between in-distribution and out-of-distribution samples. The method's efficacy is further corroborated by its performance on challenging cases, such as improving the AUC of GIN S on the IMDBM/IMDBB pair from 42.05% to 60.77%, demonstrating its ability to extract meaningful signals even in scenarios where baseline methods struggle.

SpecGap's consistent performance across both unsupervised (GCL, JOAO) and supervised (GIN, PPGN) architectures, as well as its compatibility with different scoring functions (SSD and LOF), highlights its versatility and robustness as a post-processing technique. The method's success can be attributed to its novel approach of leveraging spectral properties, particularly the spectral gap, to capture and amplify structural differences between ID and OOD graphs. This spectral-based feature adjustment effectively normalizes the feature representations, bringing OOD samples closer to the ID distribution in the feature space, thereby facilitating more accurate detection. The observed improvements across various graph types, including molecular (e.g., TOX21/SIDER with AUC increase from 68.04% to 73.41% for GCL S), social network (IMDBM/IMDBB), and bioinformatics (ENZYMES/PROTEIN) datasets, underscore SpecGap's generalizability and its potential for wide-ranging applications in graph-based machine learning tasks.

Comparison with Other OOD Detection Methods

The experimental results demonstrate that SpecGap consistently outperforms existing state-of-the-art graph OOD detection methods across various datasets, showcasing its effectiveness as a post-processing technique. To rigorously evaluate SpecGap's performance, we conducted a comparative analysis against several prominent graph OOD detection methods: AAGOD, OCGIN, GLocalKD, and GOOD-D. For this comparison, AAGOD was implemented using the JOAO architecture with the SSD scoring function, establishing a robust baseline. SpecGap, being a post-processing method, was applied to each of these methods to assess its universal applicability and potential for performance enhancement.

Figure 2 presents the AUC scores of these methods across five dataset pairs, both before and after the application of SpecGap. The results reveal a consistent pattern of improvement, with SpecGap enhancing the performance of all methods across all datasets. This uniform uplift in AUC scores underscores SpecGap's ability to extract and utilize complementary information from the graph structure. The magnitude of improvement varies across methods and datasets, reflecting the complex interplay between SpecGap, the base methods, and the underlying data distributions. Notably, SpecGap's enhancements are not limited to underperforming methods; even high-performing algorithms like GOOD-D see non-trivial improvements in certain datasets. This observation suggests that SpecGap captures fundamental graph properties that are not fully exploited by existing techniques.

3.3 Ablation Studies

Component Analysis

To thoroughly investigate the effectiveness of our proposed SpecGap method, we conducted comprehensive ablation studies on its key components. These studies focus on three critical aspects: comparison of different spectral gap adjustment techniques, the impact of feature adjustment methods, and the influence of using varying numbers of largest eigenvalues. Our experiments were performed on the ENZYMESPROTEIN dataset using the GCL model with the SSD scoring function (GCLS) as the base architecture.

The choice of spectral gap adjustment technique proves to be crucial for the performance of SpecGap, with our proposed method outperforming alternative approaches. Table 3 presents the comparison of different spectral gap adjustment techniques. We evaluated four approaches: no adjustment (original GCLS), simple subtraction (λn-λn-1), relative difference ((λn - λn-1)/λn), and our proposed method (scaled subtraction). Our proposed scaled subtraction method outperforms the alternatives across all evaluation metrics. The improvement is particularly notable in the AUC and AUPR

scores, with increases of 19.5% and 23.3% respectively compared to the original model. This significant enhancement can be attributed to the method's ability to effectively capture and emphasize the structural differences between indistribution and out-of-distribution graphs. The simple subtraction method, while showing some improvement over the original model, falls short of our proposed approach.

The method of incorporating the spectral gap information into the graph features significantly influences the performance of SpecGap. We compared three feature adjustment methods: concatenation, multiplication, and our proposed subtraction method. Table 4 presents the results of this comparison. Our proposed subtraction method consistently outperforms both alternative techniques across all evaluation metrics. The concatenation method, while providing additional information, fails to effectively emphasize the structural differences captured by the spectral gap. This results in only modest improvements over the original model. The multiplication method shows better performance, likely due to its ability to scale features based on the spectral gap. However, it may overly amplify or diminish certain features, leading to suboptimal results.

The number of largest eigenvalues used in SpecGap significantly impacts its performance, with an optimal range identified for best results. Figure 3 illustrates the impact of using different numbers of largest eigenvalues on the OOD detection performance. We varied the number of eigenvalues from 1 to 10 and measured the resulting AUC scores. The results reveal a clear trend: performance initially improves as more eigenvalues are incorporated, reaches a peak at 2 eigenvalues (which corresponds to our proposed method using the spectral gap), and then gradually declines. This pattern suggests that while the largest eigenvalues contain crucial structural information for OOD detection, incorporating too many may introduce noise or redundant information that dilutes the discriminative power of the spectral features. The sharp increase in performance from using just one eigenvalue to using two (i.e., considering the spectral gap) underscores the importance of capturing this specific aspect of the graph's spectral properties. The subsequent decline in performance when using more eigenvalues indicates that the most relevant structural information for OOD detection is concentrated in the spectral gap.

Feature Adjustment Position

The position of SpecGap application within the GNN architecture significantly impacts its effectiveness, with earlier layers generally yielding better performance. Table 5 presents the OOD detection performance of SpecGap when applied at different positions in a 3-layer GCL model on the Table 6: Performance comparison of SpecGap using different Laplacian matrix variants on the BZR-COX2 dataset with the GCLS model.

ENZYMES-PROTEIN dataset. The results demonstrate that applying SpecGap after the first layer consistently outperforms applications at later layers or the output layer. The superior performance of early-layer application can be attributed to the enhancement of global structural information captured by the spectral gap. By applying SpecGap in the early layers, we allow the subsequent layers to learn more discriminative representations based on the adjusted spectral properties of the graph.

Laplacian Matrix Variants

The choice of Laplacian matrix variant in SpecGap significantly influences OOD detection performance, with the normalized Laplacian generally yielding the best results. Table 6 compares the performance of SpecGap using different Laplacian matrix variants on the BZR-COX2 dataset with the GCLS model. The variants considered are the unnormalized Laplacian, normalized Laplacian, and signless Laplacian. The normalized Laplacian consistently outperforms other variants across all metrics. This superior performance can be attributed to its invariance to graph scale and its ability to capture both local and global graph properties effectively. The normalized Laplacian's spectral gap provides a more informative measure of graph connectivity and community structure, which is crucial for distinguishing between in-distribution and out-of-distribution samples.The unnormalized Laplacian, while still effective, shows slightly lower performance compared to its normalized counterpart. This may be due to its sensitivity to graph size, which can introduce unwanted variability in the spectral gap calculation for graphs of different scales.

Feature Projection Methods

The choice of feature projection method in SpecGap plays a crucial role in its effectiveness, with eigenvector-based projection demonstrating superior performance. Figure 4 illustrates the performance of different feature projection methods in SpecGap on the IMDBM-IMDBB dataset using the JOAOS model. We compare three projection methods: eigenvector-based, random projection, and no projection (direct feature adjustment). The eigenvector-based projection method consistently outperforms the alternatives across all evaluation metrics. This superior performance can be attributed to its ability to align the feature adjustment with the principal directions of variation in the graph structure, as captured by the eigenvectors of the Laplacian matrix. Random projection, while showing some improvement over no projection, falls short of the eigenvector-based method. This suggests that while dimensionality reduction can be beneficial, the specific structure preserved by eigenvector projection is particularly valuable for OOD detection.The no projection method, which directly adjusts features without any projection, shows the lowest performance.

4 Conclusion

This paper introduces SpecGap, a novel theoretical and empirical framework for graph-level out-of-distribution (OOD) detection using spectral properties. Our key contributions include: (1) A parameter-free post-processing technique that leverages spectral gaps to enhance OOD detection, showing consistent improvements across multiple benchmark datasets and model architectures; (2) A rigorous theoretical foundation demonstrating how spectral gaps reflect fundamental structural differences between ID and OOD graphs; and (3) Comprehensive empirical analyses through extensive experiments and ablation studies that validate our theoretical findings. Our theoretical analysis reveals that the spectral gap serves as a robust structural signature, supported by formal proofs of distribution-level separation gains and connections to classical graph theory. The experimental results demonstrate significant performance improvements, with SpecGap reducing the average false positive rate (FPR95) by 15.40% compared to previous methods.

While SpecGap shows promising results, several important directions remain for future research. First, scalability to very large graphs could be further improved through more efficient eigenvalue computation techniques or approximation methods. Second, investigating the method's robustness under adversarial perturbations and developing theoretical guarantees for such scenarios would strengthen its reliability for applications. Finally, exploring the integration of SpecGap with other graph learning tasks beyond OOD detection.

Acknowledgments

The work is partially supported by the National Natural Science Foundation of China (Grant No. 62406056, 62425603), the Guangdong Basic and Applied Basic Research Foundation (Grant No.2024A1515140114), the Basic Research Program of Jiangsu Province (Grant No. BK20240011), and Guangdong Research Team for Communication and Sensing Integrated with Intelligent Computing (Project No. 2024KCXTD047). The computational resources are supported by SongShan Lake HPC Center (SSL-HPC) in Great Bay University.