Graph Out-of-Distribution Detection via Test-Time Calibration with Dual Dynamic Dictionaries

Yue Hou, Ruomei Liu, Yingke Su, Junran Wu, Ke Xu

TL;DR

BaCa (Boundary-aware Calibration) is a novel test-time graph out-of-distribution (OOD) detection framework that calibrates anomaly scores on the fly without altering the underlying pre-trained GNN or requiring external outlier datasets. By combining continuous graphon mixup with dual dynamic priority-queue dictionaries, BaCa effectively maps and sharpens the ambiguous decision boundary between in-distribution and out-of-distribution graph data.

What Problem Does This Paper Address?

Deep learning models, including Graph Neural Networks (GNNs), are notoriously overconfident when encountering out-of-distribution (OOD) data, often misclassifying anomalies as known in-distribution (ID) classes. In graph-structured data, this problem is exacerbated by non-Euclidean geometries and complex topologies.

Existing graph OOD detection methods typically fall into two traps: they either require training a GNN from scratch with specialized objectives, or they rely on "Outlier Exposure" (OE), which assumes access to auxiliary OOD datasets during training. More recent test-time methods avoid retraining but still require optimizing complex graph maskers during inference, limiting real-time applicability. Furthermore, pre-trained GNNs often struggle to separate ID and OOD graphs that share similar topological traits, resulting in heavily overlapping score distributions near the decision boundary.

Methods

BaCa introduces a completely post-hoc, test-time calibration mechanism that operates on a frozen, pre-trained GNN encoder. The framework consists of three main components:

  1. Subgroup Partitioning & Graphon Mixup: Test samples in a batch are initially split into pseudo-ID and pseudo-OOD groups based on raw scores from the pre-trained model. To capture multifaceted structural factors, the authors estimate graphons (non-parametric generative models representing the continuous probability of edge existence) for both groups. They then perform graphon-level mixup within each subgroup to generate diverse synthetic graphs that populate low-density boundary regions.
  2. Dual Dynamic Dictionaries: BaCa maintains two fixed-length priority queues to store latent representations of ID and OOD features. Crucially, these dictionaries are updated online to capture boundary-defining samples: the right tail of the ID score distribution (most OOD-like ID samples) and the left tail of the OOD score distribution (most ID-like OOD samples).
  3. Adaptive Attention-based Calibration: During inference, a learnable attention mechanism queries the top-$K$ most relevant entries from both dictionaries. This module computes an adjustment score ($S_{Attn}$) that is added to the pre-trained model's initial score ($S_{Pre}$), effectively pushing ID and OOD scores apart. The attention parameters are optimized at test-time using a dual binary cross-entropy loss.
Figure 2: Overview of our proposed BaCa framework. (a.1) Given a pre-trained GNN encoder and test samples, we first compute the initial OOD scores and partition the samples into two preliminary subgroups based on the pre-trained model’s predictions. (a.2–a.3) Within each subgroup, diverse discriminative typologies are generated via graphon mixup and stored in dual dynamic dictionaries maintained as priority queues. (b.1–b.2) The priority queue–based dictionaries are used to support adaptive, attention-based score calibration. (b.3) The adaptive attention module is optimized during inference to compute the final calibrated OOD score.

Datasets

The authors evaluated BaCa on 10 pairs of datasets derived from mainstream graph benchmarks (TUDataset and OGB), categorized into:

  • Molecular Datasets: BZR/COX2, PTC-MR/MUTAG, AIDS/DHFR, Tox21/SIDER, FreeSolv/ToxCast, BBBP/BACE, ClinTox/LIPO, Esol/MUV.
  • Protein Datasets: ENZYMES/PROTEINS.
  • Social Network Datasets: IMDB-M/IMDB-B.

Each pair shares a similar domain but exhibits distinct distribution shifts, providing a robust testbed for unsupervised graph-level OOD detection.

Key Insights and Ideas

  • Targeting the Tails: Instead of trying to model the entire dense core of ID data, the key to test-time calibration lies in capturing the ambiguous boundary cases. By feeding the overlapping tails of the score distributions into dynamic priority queues, BaCa directly targets the hardest samples to classify.
  • Mixup in Graphon Space: Traditional graph mixup can disrupt discrete structural properties. By interpolating in the continuous graphon space, BaCa generates synthetic graphs that are typologically consistent with the source data while introducing necessary structural diversity.
  • Calibration over Fine-Tuning: You don't need to update massive GNN backbones to fix overconfidence. A lightweight, attention-driven calibration layer optimized at test-time can successfully disentangle mixed score distributions with minimal computational overhead.

Key Results

BaCa achieves state-of-the-art performance, outperforming competitive graph kernel, anomaly detection, and self-supervised baselines.

  • Superiority at Test-Time: Compared directly against GOODAT (the leading test-time baseline), BaCa improves performance across all 10 dataset pairs, yielding an average Area Under the ROC Curve (AUC) improvement of 8.37%. Notably, it achieves a massive 20.11% gain on the ClinTox/LIPO pair.
  • Distribution Separation: Qualitative visualizations demonstrate that BaCa successfully shrinks the overlap between ID and OOD score distributions, creating a much clearer decision boundary.
Figure 1: An example of OOD score distribution and detection performance evolution over test-time iterations on the PTC/- MUTAG dataset pair. (a) Before calibration, we dynamically feed the lower left tail of the OOD score distribution into the OOD dictionary and the higher right tail of the ID score distribution into the ID dictionary via two priority queues. (b) After calibration, the overlap between the ID and OOD score distributions is significantly reduced. (c) KL divergence and the loss of attention-based trainable parameters during the first 200 iterations. (d) AUC of test-time OOD detection performance over the first 200 iterations, where Total, Attn, and Base denote our full method with SBaCa, attention-based calibration with SAttn, and the pre-trained baseline with SPre, respectively.

Limitations and Future Work

The authors note that BaCa delivers suboptimal results on the IMDB-M/IMDB-B social network pair. Because both datasets originate from the same underlying data source and share identical structural semantics (e.g., mesh-like and star-shaped structures), constructing discriminative dictionaries purely from test-time topologies becomes exceptionally challenging.

To overcome this, the authors suggest that incorporating feature-aware mixup or introducing more expressive test-time learnable components represents a promising direction for future research. Additionally, exploring how this boundary-aware framework can adapt to general anomaly detection remains an open avenue.

Summary updated

Abstract

A key challenge in graph out-of-distribution (OOD) detection lies in the absence of ground-truth OOD samples during training. Existing methods are typically optimized to capture features within the in-distribution (ID) data and calculate OOD scores, which often limits pre-trained models from representing distributional boundaries, leading to unreliable OOD detection. Moreover, the latent structure of graph data is often governed by multiple underlying factors, which remains less explored. To address these challenges, we propose a novel test-time graph OOD detection method, termed BaCa, that calibrates OOD scores using dual dynamically updated dictionaries without requiring fine-tuning the pre-trained model. Specifically, BaCa estimates graphons and applies a mix-up strategy solely with test samples to generate diverse boundary-aware discriminative topologies, eliminating the need for exposing auxiliary datasets as outliers. We construct dual dynamic dictionaries via priority queues and attention mechanisms to adaptively capture latent ID and OOD representations, which are then utilized for boundary-aware OOD score calibration. To the best of our knowledge, extensive experiments on real-world datasets show that BaCa significantly outperforms existing state-of-the-art methods in OOD detection.
BibTeX
@misc{hou2025graph,
  author = {Yue Hou and Ruomei Liu and Yingke Su and Junran Wu and Ke Xu},
  title = {{Graph Out-of-Distribution Detection via Test-Time Calibration with Dual Dynamic Dictionaries}},
  year = {2025},
  eprint = {2511.13541},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.13541},
}
Figure