# SGOOD: Substructure-enhanced Graph-Level Out-of-Distribution Detection

arXiv: https://arxiv.org/abs/2310.10237 · HTML: https://mlsanity.com/paper/2310.10237/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 59 references that are in the map.
- First posted on arXiv 16 Oct 2023.

## Builds on (most cited first, 30 of 40)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks](https://mlsanity.com/paper/1610.02136/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks](https://mlsanity.com/paper/1807.03888/) (2018)
- [Enhancing The Reliability of Out-of-distribution Image Detection in Neural Networks](https://mlsanity.com/paper/1706.02690/) (2017)
- [Energy-based Out-of-distribution Detection](https://mlsanity.com/paper/2010.03759/) (2020)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images](https://mlsanity.com/paper/1412.1897/) (2014)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Out-of-Distribution Detection with Deep Nearest Neighbors](https://mlsanity.com/paper/2204.06507/) (2022)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [SSD: A Unified Framework for Self-Supervised Outlier Detection](https://mlsanity.com/paper/2103.12051/) (2021)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Contrastive Training for Improved Out-of-Distribution Detection](https://mlsanity.com/paper/2007.05566/) (2020)
- [Motif-based Graph Self-Supervised Learning for Molecular Property Prediction](https://mlsanity.com/paper/2110.00987/) (2021)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [How to Exploit Hyperspherical Embeddings for Out-of-Distribution Detection?](https://mlsanity.com/paper/2203.04450/) (2022)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [User Preference-aware Fake News Detection](https://mlsanity.com/paper/2104.12259/) (2021)
- [OOD-GNN: Out-of-Distribution Generalized Graph Neural Network](https://mlsanity.com/paper/2112.03806/) (2021)
- [Deep Set Prediction Networks](https://mlsanity.com/paper/1906.06565/) (2019)
- [Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network](https://mlsanity.com/paper/1905.11605/) (2019)

## Built on by (most cited first, 7 of 7)

- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptation](https://mlsanity.com/paper/2410.19265/) (2024)
- [GOLD: Graph Out-of-Distribution Detection via Implicit Adversarial Latent Generation](https://mlsanity.com/paper/2502.05780/) (2025)
- [GSINA: Improving Subgraph Extraction for Graph Invariant Learning via Graph Sinkhorn Attention](https://mlsanity.com/paper/2402.07191/) (2024)
- [Harnessing Feature Resonance under Arbitrary Target Alignment for Out-of-Distribution Node Detection](https://mlsanity.com/paper/2502.16076/) (2025)
- [G-OSR: A Comprehensive Benchmark for Graph Open-Set Recognition](https://mlsanity.com/paper/2503.00476/) (2025)
- [Micro-Macro Retrieval: Reducing Long-Form Hallucination in Large Language Models](https://mlsanity.com/paper/2605.28828/) (2026)

## Abstract (arXiv)

Graph-level representation learning is important in a wide range of applications. Existing graph-level models are generally built on i.i.d. assumption for both training and testing graphs. However, in an open world, models can encounter out-of-distribution (OOD) testing graphs that are from different distributions unknown during training. A trustworthy model should be able to detect OOD graphs to avoid unreliable predictions, while producing accurate in-distribution (ID) predictions. To achieve this, we present SGOOD, a novel graph-level OOD detection framework. We find that substructure differences commonly exist between ID and OOD graphs, and design SGOOD with a series of techniques to encode task-agnostic substructures for effective OOD detection. Specifically, we build a super graph of substructures for every graph, and develop a two-level graph encoding pipeline that works on both original graphs and super graphs to obtain substructure-enhanced graph representations. We then devise substructure-preserving graph augmentation techniques to further capture more substructure semantics of ID graphs. Extensive experiments against 11 competitors on numerous graph datasets demonstrate the superiority of SGOOD, often surpassing existing methods by a significant margin. The code is available at https://github.com/TommyDzh/SGOOD.