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

cs.LGFeb 28, 2026

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

Authors: Li Sun, Lanxu Yang, Jiayu Tian, Bowen Fang, Xiaoyan Yu, Junda Ye, Peng Tang, Hao Peng, +1 more

Organizations: North China Electric Power University · Beijing University of Posts and Telecommunications · Tsinghua University · Beijing Institute of Technology · Shandong University · Beihang University · University of Illinois Chicago

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.

Figures & tables

Figure 1: Comparisons between policy-guided and heuristic-based sampling. (a) Policy-guided sampling via a learned agent. (b) Heuristic sampling follows predefined rules.

Figure 2: An overview of our PGOS framework based on pseudo-outlier synthesis.

ID dataset	BZR	PTC-MR	AIDS	ENZYMES	IMDB-M	Tox21	FreeSolv	BBBP	ClinTox	Esol	Avg. Rank
OOD dataset	COX2	MUTAG	DHFR	PROTEIN	IMDB-B	SIDER	ToxCast	BACE	LIPO	MUV	Avg. Rank
PK-SVM	$43.1{\scriptstyle\pm 7.9}$	$50.2{\scriptstyle\pm 6.7}$	$52.1{\scriptstyle\pm 2.6}$	$49.9{\scriptstyle\pm 3.2}$	$49.0{\scriptstyle\pm 3.0}$	$51.0{\scriptstyle\pm 2.0}$	$49.3{\scriptstyle\pm 2.9}$	$53.0{\scriptstyle\pm 2.3}$	$51.9{\scriptstyle\pm 3.0}$	$51.7{\scriptstyle\pm 1.8}$	$14.5$
PK-iF	$52.8{\scriptstyle\pm 2.2}$	$52.0{\scriptstyle\pm 4.0}$	$50.8{\scriptstyle\pm 1.8}$	$52.6{\scriptstyle\pm 2.4}$	$51.9{\scriptstyle\pm 3.0}$	$50.7{\scriptstyle\pm 1.1}$	$51.9{\scriptstyle\pm 1.7}$	$53.1{\scriptstyle\pm 1.8}$	$51.7{\scriptstyle\pm 1.6}$	$51.2{\scriptstyle\pm 4.1}$	$13.7$
WL-SVM	$50.2{\scriptstyle\pm 5.2}$	$52.4{\scriptstyle\pm 7.8}$	$51.4{\scriptstyle\pm 3.3}$	$52.9{\scriptstyle\pm 3.2}$	$52.9{\scriptstyle\pm 2.6}$	$50.7{\scriptstyle\pm 1.9}$	$50.4{\scriptstyle\pm 3.8}$	$52.9{\scriptstyle\pm 2.0}$	$50.8{\scriptstyle\pm 3.7}$	$52.0{\scriptstyle\pm 2.2}$	$13.7$
WL-iF	$50.0{\scriptstyle\pm 3.0}$	$52.8{\scriptstyle\pm 1.9}$	$50.8{\scriptstyle\pm 0.9}$	$51.4{\scriptstyle\pm 3.0}$	$52.6{\scriptstyle\pm 3.5}$	$51.3{\scriptstyle\pm 0.6}$	$53.0{\scriptstyle\pm 3.2}$	$50.6{\scriptstyle\pm 0.7}$	$51.4{\scriptstyle\pm 2.5}$	$51.6{\scriptstyle\pm 1.3}$	$14.0$
IG-iF	$62.7{\scriptstyle\pm 8.6}$	$50.2{\scriptstyle\pm 6.4}$	$91.0{\scriptstyle\pm 1.3}$	$57.3{\scriptstyle\pm 2.4}$	$60.7{\scriptstyle\pm 2.0}$	$57.6{\scriptstyle\pm 0.9}$	$59.6{\scriptstyle\pm 2.1}$	$55.7{\scriptstyle\pm 2.1}$	$46.8{\scriptstyle\pm 2.5}$	$55.8{\scriptstyle\pm 4.2}$	$11.9$

Table 1: OOD detection performance in AUC (%, mean ± std), with the best and second-best results in bold and underlined.

Figure 3: T-SNE visualizations of graph embeddings learned by PGCL on three different datasets. Each point denotes a graph, and colors represent the

K=8

distinct clusters.

Method	WL-SVM	IG-iF	GCL-iF	OCGIN	OCGTL	SIGNET	CVTGAD	GLocalKD	GOOD-D	GOODAT	PGOS
PROTEINS	$52.9{\scriptstyle\pm 3.8}$	$55.8{\scriptstyle\pm 2.0}$	$59.1{\scriptstyle\pm 2.5}$	$76.3{\scriptstyle\pm 0.0}$	$74.2{\scriptstyle\pm 0.0}$	$72.6{\scriptstyle\pm 0.1}$	$74.4{\scriptstyle\pm 0.0}$	$71.4{\scriptstyle\pm 0.5}$	$72.4{\scriptstyle\pm 0.0}$	$\underline{77.9{\scriptstyle\pm 2.4}}$	$\mathbf{81.3}{\mathbf{\scriptstyle\pm 0.3}}$
ENZYMES	$57.2{\scriptstyle\pm 2.6}$	$52.4{\scriptstyle\pm 4.5}$	$52.1{\scriptstyle\pm 4.0}$	$63.6{\scriptstyle\pm 2.2}$	$66.0{\scriptstyle\pm 0.1}$	$63.2{\scriptstyle\pm 0.3}$	$\mathbf{69.4{\scriptstyle\pm 0.7}}$	$66.0{\scriptstyle\pm 0.4}$	$61.5{\scriptstyle\pm 0.7}$	$59.1{\scriptstyle\pm 2.5}$	$\underline{67.1{\scriptstyle\pm 0.1}}$
AIDS	$49.2{\scriptstyle\pm 3.4}$	$72.8{\scriptstyle\pm 2.4}$	$78.0{\scriptstyle\pm 2.7}$	$\mathbf{99.8}{\mathbf{\scriptstyle\pm 0.0}}$	$\underline{99.6{\scriptstyle\pm 0.0}}$	$92.2{\scriptstyle\pm 0.3}$	$98.6{\scriptstyle\pm 0.0}$	$97.3{\scriptstyle\pm 0.0}$	$95.9{\scriptstyle\pm 0.1}$	$96.0{\scriptstyle\pm 1.0}$	$96.9{\scriptstyle\pm 0.1}$
DHFR	$52.9{\scriptstyle\pm 3.0}$	$51.4{\scriptstyle\pm 3.0}$	$50.3{\scriptstyle\pm 2.8}$	$59.8{\scriptstyle\pm 0.2}$	$59.4{\scriptstyle\pm 0.1}$	$\underline{72.7{\scriptstyle\pm 0.6}}$	$64.2{\scriptstyle\pm 0.1}$	$59.6{\scriptstyle\pm 0.1}$	$64.5{\scriptstyle\pm 0.0}$	$62.2{\scriptstyle\pm 2.5}$	$\mathbf{73.2}{\mathbf{\scriptstyle\pm 0.2}}$
BZR	$52.3{\scriptstyle\pm 6.2}$	$61.2{\scriptstyle\pm 2.5}$	$61.2{\scriptstyle\pm 2.8}$	$68.9{\scriptstyle\pm 0.4}$	$63.5{\scriptstyle\pm 0.6}$	$\underline{79.3{\scriptstyle\pm 1.3}}$	$\mathbf{80.0}{\mathbf{\scriptstyle\pm 0.5}}$	$63.9{\scriptstyle\pm 1.3}$	$65.7{\scriptstyle\pm 0.6}$	$59.0{\scriptstyle\pm 5.3}$	$77.1{\scriptstyle\pm 2.4}$
COX2	$49.2{\scriptstyle\pm 2.9}$	$55.7{\scriptstyle\pm 2.9}$	$51.0{\scriptstyle\pm 1.7}$	$57.4{\scriptstyle\pm 0.5}$	$56.6{\scriptstyle\pm 0.3}$	$\underline{70.6{\scriptstyle\pm 0.2}}$	$67.6{\scriptstyle\pm 0.4}$	$49.2{\scriptstyle\pm 0.6}$	$61.6{\scriptstyle\pm 0.7}$	$59.3{\scriptstyle\pm 7.6}$	$\mathbf{74.6}{\mathbf{\scriptstyle\pm 2.3}}$

Table 2: Anomaly detection performance in AUC (%, mean ± std), with the best and second-best results in bold and underlined.

Model Variants	BZR	PTC-MR	IMDB-M	Tox21
Model Variants	COX2	MUTAG	IMDB-B	SIDER
PGOS- $\mathcal{L}_{\text{IPS}}$	$93.3{\scriptstyle\pm 1.1}$	$82.2{\scriptstyle\pm 2.2}$	$83.7{\scriptstyle\pm 1.4}$	$72.9{\scriptstyle\pm 1.7}$
PGOS-PGCL	$93.4{\scriptstyle\pm 2.7}$	$80.9{\scriptstyle\pm 3.7}$	$81.6{\scriptstyle\pm 1.3}$	$71.7{\scriptstyle\pm 2.4}$
PGOS- $\mathcal{H}_{\text{target}}(s_{t})$	$93.1{\scriptstyle\pm 1.3}$	$82.8{\scriptstyle\pm 2.1}$	$82.0{\scriptstyle\pm 1.3}$	$70.6{\scriptstyle\pm 1.4}$
PGOS-RL	$77.5{\scriptstyle\pm 1.6}$	$74.5{\scriptstyle\pm 1.3}$	$76.8{\scriptstyle\pm 2.6}$	$64.9{\scriptstyle\pm 2.3}$
PGOS-Full	$\mathbf{94.8}\mathbf{{\scriptstyle\pm 1.1}}$	$\mathbf{84.1}\mathbf{{\scriptstyle\pm 1.7}}$	$\mathbf{85.4}\mathbf{{\scriptstyle\pm 1.4}}$	$\mathbf{74.2}\mathbf{{\scriptstyle\pm 1.1}}$

Table 3: Performance comparison of PGOS and its ablated variants, reported as AUC scores (%, mean ± std).

Figure 4: T-SNE visualization of sampled points generated by the RL-based and Gaussian sampling strategies on the BBBP+BACE OOD dataset.

Figure 5: Sensitivity analysis of the number of prototypes

K

on OOD detection performance across different datasets.

Explore similar work

From Subtle to Significant: Prompt-Driven Self-Improving Optimization in Test-Time Graph OOD Detection
Feb 19, 2026Luzhi Wang, Xuanshuo Fu, He Zhang +3OOD Detection Test-Time Adaptation
College of Artificial Intelligence, Dalian Maritime University · Computer Vision Center, Universitat Aut`onoma de Barcelona · School of Computing Technologies, RMIT University +1
Disentangled Graph Prompting for Out-Of-Distribution Detection
Mar 31, 2026Cheng Yang, Yu Hao, Qi Zhang +1OOD Detection Graph Neural Networks
the Beijing Key Lab of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, China · China Mobile Group Shaanxi Co., Ltd.
What Information Matters? Graph Out-of-Distribution Detection via Tri-Component Information Decomposition
May 13, 2026Danny Wang, Ruihong Qiu, Zi HuangGraph Neural Networks OOD Detection
The University of Queensland, Australia.

Feb 19, 2026J/K move · Enter open · S save

From Subtle to Significant: Prompt-Driven Self-Improving Optimization in Test-Time Graph OOD Detection

Luzhi Wang, Xuanshuo Fu, He Zhang, Chuang Liu+2

College of Artificial Intelligence, Dalian Maritime University · Computer Vision Center, Universitat Aut`onoma de Barcelona · School of Computing Technologies, RMIT University+1

OOD Detection Test-Time Adaptation Prompt Learning

Open paper AskPDF arXiv

Graph Out-of-Distribution (OOD) detection aims to identify whether a test graph deviates from the distribution of graphs observed during training, which is critical for ensuring the reliability of Graph Neural Networks (GNNs) when deployed in open-world scenarios. Recent advances in graph OOD detection have focused on test-time training techniques that facilitate OOD detection without accessing potential supervisory information (e.g., training data). However, most of these methods employ a one-pass inference paradigm, which prevents them from progressively correcting erroneous predictions to amplify OOD signals. To this end, we propose a Self-Improving Graph Out-of-Distribution detector (SIGOOD), which is an unsupervised framework that integrates continuous self-learning with test-time training for effective graph OOD detection. Specifically, SIGOOD generates a prompt to construct a prompt-enhanced graph that amplifies potential OOD signals. To optimize prompts, SIGOOD introduces an Energy Preference Optimization (EPO) loss, which leverages energy variations between the original test graph and the prompt-enhanced graph. By iteratively optimizing the prompt by involving it into the detection model in a self-improving loop, the resulting optimal prompt-enhanced graph is ultimately used for OOD detection. Comprehensive evaluations on 21 real-world datasets confirm the effectiveness and outperformance of our SIGOOD method. The code is at https://github.com/Ee1s/SIGOOD.

Abstract

Explore similar work

From Subtle to Significant: Prompt-Driven Self-Improving Optimization in Test-Time Graph OOD Detection

Disentangled Graph Prompting for Out-Of-Distribution Detection

What Information Matters? Graph Out-of-Distribution Detection via Tri-Component Information Decomposition