KEGOD: Kernel-enhanced Latent Substructure Learning for Graph Out-Of-Distribution Detection
Open Access
- 12 April 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1160-1170
Abstract
Out-of-Distribution (OOD) detection, which seeks to identify samples deviating from the In-Distribution (ID) training distribution at test time, is crucial for building robust machine learning systems. While extensive efforts have been made for Euclidean data, OOD detection on graph-structured data remains relatively underexplored. On the one hand, the specific properties of a graph may be attributed to its substructures. On the other hand, acquiring labeled data for graph learning is typically time-consuming and labor-intensive. Toward this end, in this paper, we propose a novel kernel-enhanced graph substructure learning framework termed KEGOD for unsupervised graph OOD detection. Specifically, we introduce a learnable graph generator to construct the augmented graph view that preserves distinguishable structure information. Then, for both the input graph and augmented view, a graph neural network (GNN) branch and a graph kernel (GK) branch are incorporated to explore graph latent patterns. By performing multi-branch concordance learning on the extracted graph patterns, our KEGOD captures complementary ID structural semantics in both implicit and explicit manners, enabling reliable detection of OOD graphs through semantic inconsistency. Finally, we build a self-adaptive training mechanism to automatically control diverse sensitivities of the graph patterns. Experimental results on several public graph datasets reveal the superiority of our KEGOD. Our code is available at~ https://github.com/jamesyifan/KEGOD.Keywords
Funding Information
- National Key Research and Development Program of China (2023YFC3341203)
- Fundamental Research Funds for the Central Universities in UIBE (23QN02)
- Humanities and Social Sciences Research Fund of the Ministry of Education of China (25YJCZH275)
- National Natural Science Foundation of China (62276002)
- National Natural Science Foundation of China (62306014)
- National Natural Science Foundation of China (12501344)
- Postdoctoral Fellowship Program (Grade A) of CPSF (BX20250376)
- Postdoctoral Fellowship Program (Grade A) of CPSF (BX20240239)
- Sichuan Science and Technology Program (2025ZNSFSC1506)
- Sichuan Science and Technology Program (2025ZNSFSC0808)
- Fundamental Research Funds for the Central Universities (1082204112K97)
- Sichuan University Interdisciplinary Innovation Fund (-)
This publication has 22 references indexed in Scilit:
- When Heterophily Meets Heterogeneous Graphs: Latent Graphs Guided Unsupervised Representation LearningIEEE Transactions on Neural Networks and Learning Systems, 2025
- A Comprehensive Survey on Deep Graph Representation LearningNeural Networks, 2024
- On Using Classification Datasets to Evaluate Graph Outlier Detection: Peculiar Observations and New InsightsBig Data, 2023
- Deep graph level anomaly detection with contrastive learningScientific Reports, 2022
- DisenHAN: Disentangled Heterogeneous Graph Attention Network for Recommendation2020
- Robust Physical-World Attacks on Deep Learning Visual Classification2018
- Intelligible Models for HealthCare2015
- Isolation Forest2008
- Shortest-Path Kernels on Graphs2005
- Protein function prediction via graph kernelsBioinformatics, 2005