A unified pairwise distribution matching framework for graph domain adaptation under structure shift

Graph domain adaptation (GDA) has emerged as an important problem in graph machine learning when the distribution of the source graph used for training differs from that of the target graph used for testing. While much of the prior work on GDA has focused on aligning node representations across source and target domains, recent studies show that such approaches can be suboptimal in the presence of graph structure shift, where the underlying connection patterns between nodes change across domains. In this work, we develop a unified pairwise distribution matching framework for mitigating conditional structure shift (CSS), a specific form of graph structure shift in which conditional edge distributions vary across domains. The framework recovers existing GDA methods as instances of moment matching and motivates PLSA, a new likelihood-based method that uses calibrated probabilistic predictors on connected target node pairs. Theoretically, we establish finite-sample guarantees for both the likelihood-based and moment-matching estimators under the contextual stochastic block model. Our analysis uses Bernstein-type concentration bounds for edge-weighted U-statistics, leading to error bounds that reflect both the effective number of observed edges and the conditioning of the corresponding likelihood or moment-matching problem. We complement our theoretical results with empirical studies that demonstrate the effectiveness of the proposed framework.