  Graph Neural Networks (GNNs) have shown remarkable performance on
graph-structured data. However, recent empirical studies suggest that GNNs are
very susceptible to distribution shift. There is still significant ambiguity
about why graph-based models seem more vulnerable to these shifts. In this work
we provide a thorough theoretical analysis on it by quantifying the magnitude
of conditional shift between the input features and the output label. Our
findings show that both graph heterophily and model architecture exacerbate
conditional shifts, leading to performance degradation. To address this, we
propose an approach that involves estimating and minimizing the conditional
shift for unsupervised domain adaptation on graphs. In our controlled synthetic
experiments, our algorithm demonstrates robustness towards distribution shift,
resulting in up to 10% absolute ROC AUC improvement versus the second-best
algorithm. Furthermore, comprehensive experiments on both node classification
and graph classification show its robust performance under various distribution
shifts.
