CLINIC: Towards High-quality Graph Out-Of-Distribution Detection

This paper studies the problem of graph out-of-distribution (OOD) detection, which aims to identify anomaly graphs out of a graph dataset. Prior efforts usually focus on the utilization of topological structures with unsupervised graph learning to foster typical pattern recognition, which overlooks the semantic structure preserved in contextually affine neighborhoods. Towards this end, we propose a novel approach named Contextual Affinity Exploration with Twin Concordance (CLINIC) for graph OOD detection. The core of CLINIC is to explore and exploit the contextual affinity of the graph data samples for discriminative graph representations. In particular, our CLINIC first builds a contextual affinity graph to depict the semantic structure in the hidden space. More importantly, we introduce high-order affinity to enhance geometric understanding of the structure by utilizing a meta-graph neural network. To enhance representation discriminability with high robustness, we introduce twin concordance learning, which not only minimizes the difference of affinity distributions across different views, but also encourages the consistency between contextually affinitive neighbors. Finally, we introduce a compression strategy to expand the decision boundary for enhanced separation between in-distribution and out-of-distribution graphs. Extensive experimental results demonstrate the superiority of our CLINIC across ten real datasets in comparison to various baselines.

Graphs are a common way to represent complex data, such as molecules, proteins, and citation networks. However, graph-based machine learning models often assume that new examples encountered after deployment will look similar to the data seen during training. In real applications, this assumption may fail, and the model may face out-of-distribution (OOD) graphs that differ from the normal training data and should be detected rather than trusted blindly. This paper proposes CLINIC, a method for identifying such OOD graph examples. CLINIC looks beyond direct graph structures and studies how each graph relates to other graphs in its context. By learning these contextual relationships, the method builds clearer groups of normal graphs and a tighter boundary around them. Graphs that fall outside this boundary are treated as out-of-distribution. This improves the reliability of graph learning systems in scientific and network-based applications.