SGOOD: Substructure-enhanced Graph-Level Out-of-Distribution Detection
Zhihao Ding Jieming Shi
Graph-level representation learning is important in a wide range of
applications. However, existing graph-level models are generally built on
i.i.d. assumption for both training and testing graphs, which is not realistic
in an open world, where models can encounter out-of-distribution (OOD) testing
graphs that are from different distributions unknown during training. A
trustworthy model should not only produce accurate predictions for
in-distribution (ID) data, but also detect OOD graphs to avoid unreliable
prediction. In this paper, we present SGOOD, a novel graph-level OOD detection
framework. We find that substructure differences commonly exist between ID and
OOD graphs. Hence, SGOOD explicitly utilizes substructures to learn powerful
representations to achieve superior performance. Specifically, we build a super
graph of substructures for every graph, and design a two-level graph encoding
pipeline that works on both original graphs and super graphs to obtain
substructure-enhanced graph representations. To further distinguish ID and OOD
graphs, we develop three graph augmentation techniques that preserve
substructures and increase expressiveness. Extensive experiments against 10
competitors on numerous graph datasets demonstrate the superiority of SGOOD,
often surpassing existing methods by a significant margin. The code is
available at https://anonymous.4open.science/r/SGOOD-0958.