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:
- 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.
- 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).
- 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.
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.
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