Test-time Graph OOD Detection via Dynamic Dictionary Expansion and OOD Score Calibration

Out-of-distribution (OOD) detection for graph-structured data remains a challenging problem, particularly when test-time OOD samples deviate significantly from the training outliers. Existing methods are typically optimized to capture the features within the in-distribution (ID) training data, but often fail to model the transitional region near the boundary between ID and OOD samples. Moreover, since data distributions are usually governed by multiple latent factors, pre-trained models constrained by the scope and diversity of training data struggle to represent the full spectrum of sample characteristics and distributional boundaries. To address this dilemma, we propose a novel test-time graph OOD detection method, termed D2GO, that constructs and dynamically updates ID and OOD graphon dictionaries for OOD score calibration, without requiring fine-tuning. Specifically, D2GO estimates graphons from test graphs and employs a mix-up strategy to generate boundary samples, eliminating the need for exposing auxiliary datasets or training graphs. Priority queues are utilized to expand the ID and OOD dictionaries by incorporating diverse graphons based on pseudo-labels at test-time, and the OOD scores are calibrated by computing the similarity between test samples and both graphon dictionaries. Extensive experiments on real-world datasets show that D2GO significantly outperforms existing state-of-the-art methods in OOD detection.