Graph Domain Adaptation via Theory-Grounded Spectral Regularization

Yuning You, Tianlong Chen, Zhangyang Wang, Yang ShenICLR 2023 · OpenReview

Transferring knowledge between different graph datasets—such as moving a model trained on human protein networks to yeast protein networks—is a notoriously difficult task. While Graph Neural Networks (GNNs) are powerful, they often struggle when the "source" and "target" domains exhibit different distributions. This paper provides a rigorous theoretical bridge to solve this challenge, introducing spectral regularizers that dictate exactly which parts of a GNN to tune for better transferability.

The Challenge of Graph Domain Adaptation

Graph Domain Adaptation (GDA) is the challenge of taking a GNN trained on one graph (the source) and applying it to another (the target) where the underlying distributions of nodes and edges differ.

Most existing methods either rely on heuristics or use generic Domain Adaptation (DA) theories that treat graphs like any other data type. These generic theories ignore the unique structural properties of graphs, such as how edges connect nodes or how signals propagate through the graph's spectrum. The authors identify a major gap: the field lacks a theoretical understanding of how the internal design of a GNN—specifically its Lipschitz constant in the non-Euclidean graph space—affects its ability to generalize across domains.

Theory-Grounded Methods

To address this, the researchers combined Optimal Transport (OT) theory with Graph Filter Theory to derive a novel, model-based GDA bound. They proved that the performance gap between source and target domains is controlled by the GNN's Lipschitz constant.

By breaking this constant down via spectral decomposition, they identified two measurable spectral properties:

  • Spectral Smoothness (SS): How sensitive the GNN is to changes in the graph's edges.
  • Maximum Frequency Response (MFR): How sensitive the GNN is to changes in node features.
Spectral Regularization Framework

Based on this theory, they proposed two new regularization terms, SSReg and MFRReg, which are added to the training loss. These terms explicitly constrain the GNN's spectral behavior during training to keep the transferability bound tight. These regularizers are integrated into a standard adversarial training setup (using Wasserstein distance) to learn domain-invariant representations.

Datasets and Evaluation

The authors evaluated their approach on diverse, real-world transfer scenarios:

  • Cross-Species Protein-Protein Interaction (PPI): Training on Human PPI data and transferring to Mouse, Zebrafish, Fruit fly, and Yeast. They evaluated both "co-expression" (link-heavy) and "physical interaction" (node-feature-heavy) tasks.
  • Temporally Shifted Citation Networks: Using ArnetMiner data to classify paper topics across different time periods.
  • Large-Scale Benchmarks: Evaluation on the ogbn-arxiv dataset under varying label rates to test semi-supervised performance.

Key Insights and Results

The core realization of the paper is that transferability is essentially a form of stability. If a GNN is stable against perturbations in edges and node features, it is more likely to transfer well.

Crucially, the authors found that different tasks require different spectral constraints:

  • Node Transfer: When node features are the primary source of information (and edges are noisy), SSReg is more effective.
  • Link Transfer: When the graph topology (edges) is the primary invariant information, MFRReg provides more benefits.
Performance Comparison of SSReg and MFRReg

Overall, the proposed methods consistently outperformed state-of-the-art GDA methods like UDAGCN and self-supervised approaches like GraphCL. For instance, in cross-species PPI co-expression tasks, MFRReg achieved the top rank across almost all species, often improving AUROC by several percentage points over vanilla adversarial training. In citation networks, the spectral regularizers helped the model overcome the performance degradation often seen when using standard domain adaptation techniques.

Furthermore, while calculating eigenvalues can be computationally heavy ($O(N^3)$), the authors demonstrated that using mini-batching makes the overhead negligible (around 3 seconds per epoch on a standard GPU).

Limitations and Future Work

While groundbreaking, the current theory is primarily developed for GNNs that can be modeled as graph filters (like GCN or GIN). Extending this to more complex, non-linear architectures like Graph Transformers remains an open challenge. Additionally, although mini-batching mitigates computational complexity, the reliance on eigendecomposition might still be a hurdle for extremely large, dense graphs where batching is difficult. Finally, while the paper touches on "conditional shift," future work is needed to handle cases where the fundamental relationship between graphs and labels changes between domains.

Summary updated

Abstract

Transfer learning on graphs drawn from varied distributions (domains) is in great demand across many applications. Emerging methods attempt to learn domain-invariant representations using graph neural networks (GNNs), yet the empirical performances vary and the theoretical foundation is limited. This paper aims at designing theory-grounded algorithms for graph domain adaptation (GDA). (i) As the first attempt, we derive a model-based GDA bound closely related to two GNN spectral properties: spectral smoothness (SS) and maximum frequency response (MFR). This is achieved by cross-pollinating between the OT-based (optimal transport) DA and graph filter theories. (ii) Inspired by the theoretical results, we propose algorithms regularizing spectral properties of SS and MFR to improve GNN transferability. We further extend the GDA theory into the more challenging scenario of conditional shift, where spectral regularization still applies. (iii) More importantly, our analyses of the theory reveal which regularization would improve performance of what transfer learning scenario, (iv) with numerical agreement with extensive real-world experiments: SS and MFR regularizations bring more benefits to the scenarios of node transfer and link transfer, respectively. In a nutshell, our study paves the way toward explicitly constructing and training GNNs that can capture more transferable representations across graph domains. Codes are released at https://github.com/Shen-Lab/GDA-SpecReg.
BibTeX
@inproceedings{you2023graph,
  author = {Yuning You and Tianlong Chen and Zhangyang Wang and Yang Shen},
  title = {{Graph Domain Adaptation via Theory-Grounded Spectral Regularization}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=OysfLgrk8mk},
}
Figure