Energy-based Out-of-Distribution Detection for Graph Neural Networks

Qitian Wu, Yiting Chen, Chenxiao Yang, Junchi Yan

Abstract

Learning on graphs, where instance nodes are inter-connected, has become one of the central problems for deep learning, as relational structures are pervasive and induce data inter-dependence which hinders trivial adaptation of existing approaches that assume inputs to be i.i.d. sampled. However, current models mostly focus on improving testing performance of in-distribution data and largely ignore the potential risk w.r.t. out-of-distribution (OOD) testing samples that may cause negative outcome if the prediction is overconfident on them. In this paper, we investigate the under-explored problem, OOD detection on graph-structured data, and identify a provably effective OOD discriminator based on an energy function directly extracted from graph neural networks trained with standard classification loss. This paves a way for a simple, powerful and efficient OOD detection model for GNN-based learning on graphs, which we call GNNSafe. It also has nice theoretical properties that guarantee an overall distinguishable margin between the detection scores for in-distribution and OOD samples, which, more critically, can be further strengthened by a learning-free energy belief propagation scheme. For comprehensive evaluation, we introduce new benchmark settings that evaluate the model for detecting OOD data from both synthetic and real distribution shifts (cross-domain graph shifts and temporal graph shifts). The results show that GNNSafe achieves up to 17.0% AUROC improvement over state-of-the-arts and it could serve as simple yet strong baselines in such an under-developed area.

Introduction

Deep learning models are notoriously overconfident; they frequently assign high-probability scores to inputs they have never encountered during training. In safety-critical domains such as medical diagnosis or autonomous driving, this lack of self-awareness can be disastrous. While Out-of-Distribution (OOD) detection is a well-established field for independent data (like images), it remains significantly under-explored for graph-structured data.

In a graph, nodes are not isolated islands; they are inter-connected. If a node is OOD, its neighbors are likely to be influenced by similar distribution shifts. Most existing OOD methods fail because they treat every node as an independent sample, ignoring the rich relational information inherent in the graph's topology. This paper introduces GNNSafe, a framework designed to bridge this gap by leveraging energy-based models and the graph's structural consensus to identify "alien" nodes.

Methodology

The authors propose two variants of their framework: GNNSafe (the base version) and GNNSafe++ (an enhanced version utilizing outlier exposure). The approach is built on three pillars:

1. Energy-Based Discriminator

Standard GNNs typically use softmax probabilities for classification, which are prone to overconfidence. Instead, GNNSafe calculates an "energy score" derived directly from the GNN's raw output (logits). In-distribution (ID) data naturally tends to reside in low-energy regions of the logit space, while OOD data tends to exhibit higher energy. This provides a more robust signal for discrimination than simple probability thresholds.

2. Energy Belief Propagation (EBP)

The core innovation of this work is Energy Belief Propagation. Inspired by how labels are smoothed across graphs in semi-supervised learning, EBP propagates energy scores among neighboring nodes. If a node exhibits high energy and its neighbors do as well, the model’s confidence that the entire neighborhood is OOD increases. This mechanism uses the graph's topology to widen the margin between ID and OOD scores, effectively filtering out local noise through neighborhood consensus.

3. Energy-Regularized Learning (GNNSafe++)

When a small amount of auxiliary OOD data is available during training—a technique known as "outlier exposure"—the authors introduce a regularization term. This term explicitly pushes ID energy down and OOD energy up. Crucially, the authors provide a theoretical proof (Proposition 3) demonstrating that this regularization does not degrade the model's primary classification accuracy, ensuring that robustness does not come at the cost of performance.

Experimental Setup

To rigorously test the framework, the authors established new benchmarks covering various distribution shifts:

  • Real-World Shifts:
    • Twitch-Explicit: A multi-graph dataset where subgraphs represent different geographic regions (cross-domain shift).
  • ogbn-Arxiv: A citation network where papers published after a specific year are treated as OOD (temporal shift).
  • Synthetic Shifts: Using datasets like Cora, Amazon-Photo, and Coauthor-CS, the authors simulated OOD scenarios via structure manipulation (randomized edges), feature interpolation (noisy features), and label leave-out (unseen classes).

Key Insights and Results

Superior Detection Performance

GNNSafe++ demonstrated significant gains over existing state-of-the-art methods. It achieved a 17.0% AUROC improvement on the Cora-Structure benchmark and a 12.8% improvement on the Twitch dataset. The "Belief Propagation" step alone consistently boosted performance across all tested datasets, confirming that graph topology is a vital, previously missing link in OOD detection.

Efficiency and Versatility

Unlike complex Bayesian methods or generative models (such as GPN or GKDE) that require expensive density estimation, GNNSafe is "learning-free" at inference time. It is often an order of magnitude faster than specialized graph OOD models and can be integrated with almost any standard GNN architecture, including GCNs and GATs.

Theoretical Consistency

A major contribution of this work is the proof that energy-based OOD detection is consistent with the standard classification objective. This means practitioners can optimize for safety without worrying about a trade-off in predictive power on in-distribution data.

Conclusion and Future Work

GNNSafe establishes a simple yet powerful baseline for OOD detection in graph-structured data. By treating energy scores as signals that can be propagated through the graph, it turns the challenge of data inter-dependence into a strength.

While the framework is highly effective, it currently relies on hyper-parameter tuning for propagation depth ($K$) and self-loop strength ($\alpha$) to avoid "over-smoothing." Future research may explore extending these energy-based principles to Graph Transformers and further automating the selection of representative OOD data for the outlier exposure phase.

Summary updated

Abstract

Learning on graphs, where instance nodes are inter-connected, has become one of the central problems for deep learning, as relational structures are pervasive and induce data inter-dependence which hinders trivial adaptation of existing approaches that assume inputs to be i.i.d.~sampled. However, current models mostly focus on improving testing performance of in-distribution data and largely ignore the potential risk w.r.t. out-of-distribution (OOD) testing samples that may cause negative outcome if the prediction is overconfident on them. In this paper, we investigate the under-explored problem, OOD detection on graph-structured data, and identify a provably effective OOD discriminator based on an energy function directly extracted from graph neural networks trained with standard classification loss. This paves a way for a simple, powerful and efficient OOD detection model for GNN-based learning on graphs, which we call GNNSafe. It also has nice theoretical properties that guarantee an overall distinguishable margin between the detection scores for in-distribution and OOD samples, which, more critically, can be further strengthened by a learning-free energy belief propagation scheme. For comprehensive evaluation, we introduce new benchmark settings that evaluate the model for detecting OOD data from both synthetic and real distribution shifts (cross-domain graph shifts and temporal graph shifts). The results show that GNNSafe achieves up to $17.0\%$ AUROC improvement over state-of-the-arts and it could serve as simple yet strong baselines in such an under-developed area.
BibTeX
@inproceedings{wu2023energy,
  author = {Qitian Wu and Yiting Chen and Chenxiao Yang and Junchi Yan},
  title = {{Energy-based Out-of-Distribution Detection for Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=zoz7Ze4STUL},
}
Figure