Learning to Explore: Policy-Guided Outlier Synthesis for Graph Out-of-Distribution Detection

Li Sun, Lanxu Yang, Jiayu Tian, Bowen Fang, Xiaoyan Yu, Junda Ye, Peng Tang, Hao Peng, Philip S. Yu

Abstract

Detecting out-of-distribution (OOD) graphs is crucial for ensuring the safety and reliability of Graph Neural Networks. In unsupervised graph-level OOD detection, models are typically trained using only in-distribution (ID) data, resulting in incomplete feature space characterization and weak decision boundaries. Although synthesizing outliers offers a promising solution, existing approaches rely on fixed, non-adaptive sampling heuristics (e.g., distance- or density-based), limiting their ability to explore informative OOD regions. We propose a Policy-Guided Outlier Synthesis (PGOS) framework that replaces static heuristics with a learned exploration strategy. Specifically, PGOS trains a reinforcement learning agent to navigate low-density regions in a structured latent space and sample representations that most effectively refine the OOD decision boundary. These representations are then decoded into high-quality pseudo-OOD graphs to improve detector robustness. Extensive experiments demonstrate that PGOS achieves state-of-the-art performance on multiple graph OOD and anomaly detection benchmarks.

Introduction

Graph Neural Networks (GNNs) have become standard for analyzing complex relational data, from molecular structures to social networks. However, they often suffer from a "closed-world" assumption, where they expect test data to mirror the training distribution. When encountering Out-of-Distribution (OOD) samples, GNNs frequently fail "silently," producing high-confidence but erroneous predictions.

Standard unsupervised OOD detection attempts to model In-Distribution (ID) data, but this approach often fails to define sharp decision boundaries. While synthesizing "pseudo-outliers" can help, traditional methods rely on static heuristics—such as picking points at a fixed distance from the data—which often fail to identify the most informative regions near the decision boundary.

Methodology

The proposed Policy-Guided Outlier Synthesis (PGOS) framework treats outlier synthesis as an adaptive exploration problem. As shown in the framework overview, the system consists of three primary components:

Overview of the PGOS framework
  1. Prototypical Latent Space Construction: PGOS utilizes a graph autoencoder paired with Prototypical Contrastive Learning (PGCL). This forces ID graphs to cluster around specific "prototypes," creating distinct low-density voids that represent potential OOD regions.
  2. Policy-Guided Synthesis (RL Explorer): A Reinforcement Learning (RL) agent, trained via Soft Actor-Critic, navigates the latent space. It is guided by a Repulsion Reward to move into empty spaces and a Spatially-Aware Entropy Regularization to intensify exploration near cluster boundaries.
  3. OOD Detection Training: Latent points identified by the agent are decoded into pseudo-OOD graphs. These synthetic samples are then used alongside ID data to train a robust OOD detector.

Experimental Setup

The framework was evaluated across 25 benchmarks, including:

  • 10 Graph OOD Detection Datasets: (e.g., BZR, AIDS, Tox21, BBBP) covering chemical and molecular domains.
  • 15 Graph Anomaly Detection Datasets: (e.g., PROTEINS, COX2, REDDIT-B) utilizing the Tox21 challenge and TU benchmarks.

Results and Discussion

PGOS demonstrated superior performance, achieving the best average rank (1.9) across OOD benchmarks and significantly outperforming 15 competitive baselines. A key finding is the importance of the adaptive sampling strategy. As illustrated in the latent space comparison, the RL-guided approach effectively identifies the "gaps" between ID clusters, whereas traditional Gaussian sampling produces a more uniform, less informative distribution of outliers.

Comparison of outlier synthesis strategies

Ablation studies further confirmed this, showing that replacing the RL agent with standard Gaussian noise led to a performance drop of up to 17.3% in AUC on specific datasets. This highlights that the quality and location of synthetic outliers are critical for effective boundary refinement.

Conclusion

PGOS introduces a novel paradigm for graph OOD detection by replacing static heuristics with a learned exploration policy. By navigating the latent space to find the most informative pseudo-outliers, PGOS significantly enhances the robustness of GNNs. Future work may involve extending this policy-guided approach to other data modalities and refining reward functions to incorporate detector uncertainty directly.

Summary updated

Abstract

Detecting out-of-distribution (OOD) graphs is crucial for ensuring the safety and reliability of Graph Neural Networks. In unsupervised graph-level OOD detection, models are typically trained using only in-distribution (ID) data, resulting in incomplete feature space characterization and weak decision boundaries. Although synthesizing outliers offers a promising solution, existing approaches rely on fixed, non-adaptive sampling heuristics (e.g., distance- or density-based), limiting their ability to explore informative OOD regions. We propose a Policy-Guided Outlier Synthesis (PGOS) framework that replaces static heuristics with a learned exploration strategy. Specifically, PGOS trains a reinforcement learning agent to navigate low-density regions in a structured latent space and sample representations that most effectively refine the OOD decision boundary. These representations are then decoded into high-quality pseudo-OOD graphs to improve detector robustness. Extensive experiments demonstrate that PGOS achieves state-of-the-art performance on multiple graph OOD and anomaly detection benchmarks.
BibTeX
@inproceedings{sun2026learning,
  author = {Li Sun and Lanxu Yang and Jiayu Tian and Bowen Fang and Xiaoyan Yu and Junda Ye and Peng Tang and Hao Peng and Philip S. Yu},
  title = {{Learning to Explore: Policy-Guided Outlier Synthesis for Graph Out-of-Distribution Detection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2026},
  doi = {10.1609/aaai.v40i30.39768},
}
Figure