  Graph Neural Networks (GNNs) are state-of-the-art models for performing
prediction tasks on graphs. While existing GNNs have shown great performance on
various tasks related to graphs, little attention has been paid to the scenario
where out-of-distribution (OOD) nodes exist in the graph during training and
inference. Borrowing the concept from CV and NLP, we define OOD nodes as nodes
with labels unseen from the training set. Since a lot of networks are
automatically constructed by programs, real-world graphs are often noisy and
may contain nodes from unknown distributions. In this work, we define the
problem of graph learning with out-of-distribution nodes. Specifically, we aim
to accomplish two tasks: 1) detect nodes which do not belong to the known
distribution and 2) classify the remaining nodes to be one of the known
classes. We demonstrate that the connection patterns in graphs are informative
for outlier detection, and propose Out-of-Distribution Graph Attention Network
(OODGAT), a novel GNN model which explicitly models the interaction between
different kinds of nodes and separate inliers from outliers during feature
propagation. Extensive experiments show that OODGAT outperforms existing
outlier detection methods by a large margin, while being better or comparable
in terms of in-distribution classification.
