  We tackle the problem of graph out-of-distribution (OOD) generalization.
Existing graph OOD algorithms either rely on restricted assumptions or fail to
exploit environment information in training data. In this work, we propose to
simultaneously incorporate label and environment causal independence (LECI) to
fully make use of label and environment information, thereby addressing the
challenges faced by prior methods on identifying causal and invariant
subgraphs. We further develop an adversarial training strategy to jointly
optimize these two properties for causal subgraph discovery with theoretical
guarantees. Extensive experiments and analysis show that LECI significantly
outperforms prior methods on both synthetic and real-world datasets,
establishing LECI as a practical and effective solution for graph OOD
generalization.
  Our code is available at https://github.com/divelab/LECI.
