Handling Distribution Shifts on Graphs: An Invariance Perspective
It addresses a critical problem for graph machine learning practitioners by enabling graph neural networks to generalize better under distribution shifts, which is incremental as it adapts existing invariance principles to the graph domain.
The paper tackles out-of-distribution generalization for graph-structured data by developing Explore-to-Extrapolate Risk Minimization (EERM), a method that uses adversarially trained context explorers to leverage invariance principles, achieving strong performance on real-world datasets with distribution shifts from spurious features, cross-domain transfers, and dynamic evolution.
There is increasing evidence suggesting neural networks' sensitivity to distribution shifts, so that research on out-of-distribution (OOD) generalization comes into the spotlight. Nonetheless, current endeavors mostly focus on Euclidean data, and its formulation for graph-structured data is not clear and remains under-explored, given two-fold fundamental challenges: 1) the inter-connection among nodes in one graph, which induces non-IID generation of data points even under the same environment, and 2) the structural information in the input graph, which is also informative for prediction. In this paper, we formulate the OOD problem on graphs and develop a new invariant learning approach, Explore-to-Extrapolate Risk Minimization (EERM), that facilitates graph neural networks to leverage invariance principles for prediction. EERM resorts to multiple context explorers (specified as graph structure editers in our case) that are adversarially trained to maximize the variance of risks from multiple virtual environments. Such a design enables the model to extrapolate from a single observed environment which is the common case for node-level prediction. We prove the validity of our method by theoretically showing its guarantee of a valid OOD solution and further demonstrate its power on various real-world datasets for handling distribution shifts from artificial spurious features, cross-domain transfers and dynamic graph evolution.