GOCM: Single-Step Graph Outlier Synthesis via Origin Consistency Model

Abstract

Supervised Graph Outlier Detection has long been constrained by severe class imbalance, and although recent diffusion-based augmentation methods have improved sample quality, their practical utility is hindered by the high computational costs of multi-step iterative sampling and the stochasticity of the generation process. To overcome these bottlenecks, we propose Graph Outlier Synthesis via Origin Consistency Model (GOCM), a single-step graph outlier synthesis framework based on a consistency model. Theoretically, we pioneer the Origin Consistency (OC) mechanism by employing an ``Interval-based Origin Inference'' strategy, which mathematically derives a direct mapping from the noise trajectory to the data origin, achieving robust and efficient single-step sample generation. Architecturally, to address the complexity of heterogeneous graphs containing multiple relations, we design the Multi-input Variational Graph Auto-Encoder (MiVGAE), which decouples intricate structures via relation-level message passing and cross-relation fusion, mapping them into a unified latent space, from which GOCM synthesizes high-quality outlier nodes. Extensive experiments on multiple real-world datasets demonstrate that GOCM achieves superior detection performance with significantly improved generation efficiency. The source code is publicly available at: https://anonymous.4open.science/r/RFS-2026-EB63/.