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

TL;DR

This paper introduces Policy-Guided Outlier Synthesis (PGOS), a novel framework that uses a reinforcement learning agent to intelligently generate synthetic Out-of-Distribution (OOD) graph data. By learning an adaptive exploration policy, PGOS overcomes the limitations of traditional methods that rely on fixed heuristics, leading to more robust graph neural networks capable of better distinguishing between in-distribution and OOD graphs.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful tools for analyzing graph-structured data, but their reliability is challenged when they encounter data from distributions different from what they were trained on (Out-of-Distribution or OOD data). Standard GNNs, trained only on "in-distribution" (ID) data, often fail silently and with high confidence when faced with OOD samples. This is because their decision boundaries are not robust enough to handle these unseen data types. A promising approach to improve robustness is "Outlier Exposure" (OE), which involves training with synthetic OOD samples. However, existing OE methods for graphs rely on fixed, non-adaptive sampling strategies (like distance or density) to generate these synthetic outliers. These strategies are inflexible and cannot systematically explore the most informative regions of the feature space to refine decision boundaries effectively. The core problem this paper addresses is how to adaptively discover the most informative outlier locations in the latent space to improve OOD detection.

Methods

The proposed PGOS framework tackles this problem in two main stages:

  1. Prototypical Representation Learning for Graphs (PGCL): To enable adaptive exploration, PGOS first structures the latent space. It uses a prototypical contrastive learning approach to create well-separated clusters of ID graphs, each represented by a learnable "prototype." This creates a navigable latent space with clear low-density regions between clusters. This stage involves a graph encoder-decoder architecture trained with a combination of:
  2. Debiased Contrastive Loss: Standard contrastive learning enhanced with prototype information to avoid false negatives.
  3. Prototypical Consistency Loss: Ensures that different augmented views of the same graph are mapped to the same prototype.
  4. Inter-Prototype Separation Loss: Pushes prototypes further apart to create distinct clusters.
  5. Generative Reconstruction Loss: Trains the decoder to reconstruct graph structures and features from latent representations.
  6. Policy-Guided Outlier Synthesis: With a structured latent space, PGOS employs a reinforcement learning (RL) agent to explore and generate informative pseudo-OOD samples.
  7. MDP Formulation: The latent space is treated as an environment where the agent's state is its current position.
  8. Reward Function: A novel repulsion reward encourages the agent to move into low-density regions between clusters while penalizing it for entering dense ID regions.
  9. Boundary Constraint: A hard boundary constraint projects the agent back onto a global hypersphere if it ventures too far from the ID data manifold, ensuring relevance.
  10. Spatially-Aware Entropy Regularization: An adaptive entropy tuning mechanism, inspired by Soft Actor-Critic (SAC), dynamically adjusts the exploration target based on the agent's distance to cluster boundaries, focusing exploration on informative areas.
  11. Learning Policy: The agent learns an exploration policy using the SAC algorithm, aiming to maximize both reward and policy entropy for effective exploration.

Once the policy converges, the agent generates latent representations of pseudo-OOD samples, which are then decoded into high-quality pseudo-OOD graphs. These synthetic graphs are used alongside ID graphs to train a robust OOD detection model.

Datasets

The paper evaluates PGOS on a wide range of benchmarks:

  • OOD Detection: 10 representative benchmarks are used, including PTC-MR, MUTAG, DHFR, ENZYMES, IMDB-M, IMDB-B, Tox21, SIDER, BZR, and COX2.
  • Anomaly Detection: 15 graph-level anomaly detection benchmark datasets are used, including those from the Tox21 challenge and the TU benchmark.

The paper does not introduce new datasets but uses established benchmarks to ensure fair comparison.

Key Insights and Ideas

  • Adaptive Exploration is Key: The most significant insight is that fixed heuristics for generating synthetic outliers are suboptimal. An adaptive policy, guided by learned rewards and constraints, can systematically discover more informative regions for OOD detection.
  • Structuring the Latent Space is Crucial: Before adaptive exploration can be effective, the latent space needs structure. Prototypical contrastive learning provides this structure by creating distinct, well-defined clusters, making the low-density regions between them navigable.
  • RL for Outlier Generation: Applying reinforcement learning to navigate the latent space and generate outliers is a novel approach. The carefully designed reward function and boundary constraints are critical for guiding the RL agent to produce meaningful pseudo-OOD samples.
  • Balancing Exploration and Relevance: The PGOS framework elegantly balances exploring novel regions (via entropy maximization) with staying relevant to the data distribution (via boundary constraints and repulsion rewards).

Key Results

  • State-of-the-Art Performance: PGOS achieves state-of-the-art results on multiple graph OOD and anomaly detection benchmarks.
  • It achieved the best average rank of 1.9 across 10 OOD detection benchmarks.
  • It established new state-of-the-art performance on 7 out of 15 anomaly detection datasets.
  • Notable improvements include a 2.2% AUC gain on PTC-MR/MUTAG and significant gains on other challenging datasets.
  • Ablation Studies: Removing the policy-guided sampling module (PGOS-RL) led to a significant performance drop (average 11.2% AUC), highlighting the critical role of the adaptive exploration policy. Other components like inter-prototype separation and entropy regularization also proved important.
  • Visualization: T-SNE visualizations confirmed that PGCL creates well-separated clusters, and the policy-guided sampler generates pseudo-OOD samples clearly distinct from ID clusters, unlike random Gaussian sampling.

Limitations and Future Work

  • Sensitivity to Prototype Count: The performance is sensitive to the number of prototypes ($K$). While the paper shows that an adequate $K$ improves performance, finding the optimal $K$ might require careful tuning.
  • Future Directions: The authors suggest exploring more advanced reward mechanisms for the RL agent and extending the PGOS paradigm to other data modalities (beyond graphs) and security-related tasks. They also hint at the potential for further advancements by combining their approach with other techniques like cross-aggregation.

Summary updated

Abstract

Detecting Out-of-Distribution (OOD) graphs—those are drawn from a different distribution from the training data-is a critical task for ensuring the safety and reliability of Graph Neural Networks. The main challenge in unsupervised graph-level Out-of-Distribution detection lies in its common reliance on purely in-distribution (ID) data. This ID-only training paradigm leads to an incomplete characterization of the feature space, resulting in decision boundaries that lack the robustness needed to effectively separate ID from OOD samples. While incorporating synthesized outliers into the training process is a promising direction, existing generation methods are limited by their dependence on pre-defined, non-adaptive sampling heuristics (e.g., distance- or density-based). Such fixed strategies lack the flexibility to systematically explore the most informative OOD regions for refining decision boundaries. To overcome this limitation, we propose a novel Policy-Guided Outlier Synthesis (PGOS) framework that replaces static heuristics with a learned, adaptive exploration policy. PGOS trains a reinforcement learning agent to autonomously navigate low-density regions within a structured latent space, sampling representations that are maximally effective for regularizing the OOD decision boundary. These sampled points are then decoded into high-quality pseudo-OOD graphs to enhance the detector's robustness. Extensive experiments demonstrate the strong performance of our method, state-of-the-art results 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