  Despite recent success in using the invariance principle for
out-of-distribution (OOD) generalization on Euclidean data (e.g., images),
studies on graph data are still limited. Different from images, the complex
nature of graphs poses unique challenges to adopting the invariance principle.
In particular, distribution shifts on graphs can appear in a variety of forms
such as attributes and structures, making it difficult to identify the
invariance. Moreover, domain or environment partitions, which are often
required by OOD methods on Euclidean data, could be highly expensive to obtain
for graphs. To bridge this gap, we propose a new framework, called Causality
Inspired Invariant Graph LeArning (CIGA), to capture the invariance of graphs
for guaranteed OOD generalization under various distribution shifts.
Specifically, we characterize potential distribution shifts on graphs with
causal models, concluding that OOD generalization on graphs is achievable when
models focus only on subgraphs containing the most information about the causes
of labels. Accordingly, we propose an information-theoretic objective to
extract the desired subgraphs that maximally preserve the invariant intra-class
information. Learning with these subgraphs is immune to distribution shifts.
Extensive experiments on 16 synthetic or real-world datasets, including a
challenging setting -- DrugOOD, from AI-aided drug discovery, validate the
superior OOD performance of CIGA.
