Generalization Error Bounds for Graph Neural Networks in Unseen Domains

The shift in data distribution between training and testing presents challenges for Graph Neural Networks (GNNs), especially in out-of-distribution (OOD) scenarios. Most analyses focus on graph domain adaptation, where the target domain is known during training. However, real-world applications often require GNNs to generalize to unseen domains, a problem that lacks sufficient theoretical analysis, particularly regarding interpretable error bounds. In this work, we bridge this gap by using the linear combination of source domains as a reference object for unseen domains.We derive generalization error bounds for GNNs based on the mixture distribution of the source domains, emphasizing the importance of domain diversity and domain-invariant feature learning for strong generalization. Furthermore, we explore a special case where the mixed distribution degenerates to the distribution of the source domains, introducing the maximum Wasserstein distance as a measure of the difference between the source domain and the unseen domains, and derive tighter error bounds. Our analysis highlights the importance of balancing domain diversity and invariance, demonstrating how these factors affect the generalization performance of GNNs in unseen domains.