A Theory of Random Graph Shift in Truncated-Spectrum vRKHS

Zhang Wan; Tingting Mu; Samuel Kaski

cs.LGFeb 27, 2026

A Theory of Random Graph Shift in Truncated-Spectrum vRKHS

Authors: Zhang Wan, Tingting Mu, Samuel Kaski

Organizations: Department of Computer Science, University of Manchester, UK · Department of Computer Science, Aalto University, Finland · ELLIS Institute Finland

Abstract

This paper develops a theory of graph classification under domain shift through a random-graph generative lens, where we consider intra-class graphs sharing the same random graph model (RGM) and the domain shift induced by changes in RGM components. While classic domain adaptation (DA) theories have well-underpinned existing techniques to handle graph distribution shift, the information of graph samples, which are itself structured objects, is less explored. The non-Euclidean nature of graphs and specialized architectures for graph learning further complicate a fine-grained analysis of graph distribution shifts. In this paper, we propose a theory that assumes RGM as the data generative process, exploiting its connection to hypothesis complexity in function space perspective for such fine-grained analysis. Building on a vector-valued reproducing kernel Hilbert space (vRKHS) formulation, we derive a generalization bound whose shift penalty admits a factorization into (i) a domain discrepancy term, (ii) a spectral-geometry term summarized by the accessible truncated spectrum, and (iii) an amplitude term that aggregates convergence and construction-stability effects. We empirically verify the insights on these terms in both real data and simulations.

Figures & tables

Panel of Figure 1 — Figure 1: Estimated latent WD correlates with test losses.

Figure 2: Layerwise perturbation sensitivity. Early-layer sensitivity ( conv0 ) is consistently the largest. Both non-uniform schemes reduce early-layer fragility relative to L2 .

Appendix figures & tables25 assets

Supplementary material from the paper’s appendix.

Appendix

Notation	Description
Graphs and basic objects
$G=(V,E,Z,A)$	A graph with node set $V=(1,\ldots,N)$ , edge set $E\subseteq V\times V$ , node features $Z\in\mathbb{R}^{N\times F}$ (rows $z_{i}\in\mathbb{R}^{F}$ ), and adjacency/weight matrix $A\in\mathbb{R}^{N\times N}$ (entries $a_{ij}$ ).
$N,\ F$	Number of nodes; node feature dimension.
$d_{i}$	Degree of node $i$ (number of incident edges).
$G=(Z,A)$	Simplified notation when node/edge sets are implicit.
Norms, Lipschitzness, and function spaces

Appendix

Table 3

Subgroup	# Graphs	mean nodes	mean edges	min nodes	max nodes	Feat. dim.	Label hist. (0/1)
PTC_FM	349	14.112	28.968	2	64	18	206 / 143
PTC_MM	336	13.973	28.643	2	64	20	207 / 129
PTC_FR	351	14.558	30.006	2	64	19	230 / 121
PTC_MR	344	14.288	29.384	2	64	18	192 / 152

Appendix

Table 4: Summary statistics of the four PTC subgroups.

Panel of Figure 3 — Figure 3: Estimated latent WD correlates with test losses.

dataset	MUTAG	PTC	PROTEINS	NCI1	NCI109	COLLAB	IMDB-B	IMDB-M
size	188	344	1113	4110	4127	5000	1000	1500
classes	2	2	2	2	2	3	2	3
avg node #	17.9	25.5	39.1	29.8	29.6	74.4	19.7	13

Appendix

Table 5: Dataset statistics. [ Maron et al., 2019 ]

Figure 4: Eigenvalues on IMDB-MULTI (1k), NCI1 (2k), PROTEINS (1k).

Figure 5: $d_{\mathrm{eff}}$ on IMDB-MULTI (1k), NCI1 (2k), PROTEINS (1k).

Figure 6: Eigenvalues on IMDB-MULTI (4k), NCI1 (4k), PROTEINS (4k).

Figure 7: $d_{\mathrm{eff}}$ on IMDB-MULTI (4k), NCI1 (4k), PROTEINS (4k).

Panel of Figure 8 — Figure 8: Target-domain test loss under different experimental conditions: (a) Graph size ( $n$ ), (b) Shift level ( $s$ ). Shaded areas indicate variance around the mean loss.

Split	#Graphs	Nodes (mean $\pm$ std)	Edges (mean $\pm$ std)	Density (mean $\pm$ std)	Label 0 ratio	Label 1 ratio
M0	1084	52.6153 $\pm$ 28.1772	104.6328 $\pm$ 34.6927	0.045216 $\pm$ 0.012618	0.4483	0.5517
M1	1084	31.0268 $\pm$ 2.6188	65.3948 $\pm$ 7.6232	0.070414 $\pm$ 0.005084	0.6771	0.3229
M2	1084	23.2094 $\pm$ 2.5559	47.7823 $\pm$ 6.8632	0.093360 $\pm$ 0.009128	0.6236	0.3764
M3	1084	14.4437 $\pm$ 3.3299	28.3967 $\pm$ 7.5115	0.155783 $\pm$ 0.047771	0.4649	0.5351

Appendix

Table 9: Mutagenicity M0–M3 split statistics.

Methods	M0 $\to$ M1	M0 $\to$ M2	M0 $\to$ M3	M1 $\to$ M2	M1 $\to$ M3	M2 $\to$ M3
GCN	$\underline{74.50\pm 0.37}$	$\mathbf{69.30\pm 0.88}$	$53.28\pm 1.34$	$69.35\pm 1.72$	$49.91\pm 2.85$	$53.82\pm 1.26$
+ L2	$74.24\pm 0.40$	$\underline{69.21\pm 0.52}$	$\underline{53.62\pm 1.01}$	$69.39\pm 1.48$	$49.83\pm 2.70$	$\underline{54.70\pm 2.49}$
+ Front	$74.48\pm 0.30$	$68.51\pm 0.94$	$\mathbf{53.67\pm 0.94}$	$\underline{69.80\pm 1.88}$	$\underline{51.25\pm 3.67}$	$\mathbf{54.96\pm 2.50}$
+ Back	$\mathbf{74.56\pm 0.42}$	$68.63\pm 1.22$	$53.14\pm 1.59$	$\mathbf{69.94\pm 2.13}$	$\mathbf{51.59\pm 4.57}$	$54.15\pm 2.68$
Methods	M3 $\to$ M2	M3 $\to$ M1	M3 $\to$ M0	M2 $\to$ M1	M2 $\to$ M0	M1 $\to$ M0
GCN	$56.22\pm 1.78$	$44.26\pm 0.66$	$\underline{57.18\pm 0.36}$	$75.63\pm 0.26$	$\underline{68.56\pm 0.40}$	$60.57\pm 5.38$

Appendix

Table 10: Accuracy (in %) on Mutagenicity (source

\to

target).

Methods	M0 $\to$ M1	M0 $\to$ M2	M0 $\to$ M3	M1 $\to$ M2	M1 $\to$ M3	M2 $\to$ M3
+ L2	$\underline{74.30\pm 0.51}$	$\mathbf{69.17\pm 0.54}$	$\mathbf{53.56\pm 1.02}$	$69.39\pm 1.65$	$49.83\pm 3.02$	$\mathbf{54.70\pm 2.78}$
+ Front	$\mathbf{74.54\pm 0.29}$	$\underline{68.15\pm 0.93}$	$52.68\pm 1.09$	$\mathbf{69.82\pm 2.19}$	$\underline{51.03\pm 3.59}$	$\underline{54.21\pm 2.71}$
+ Back	$74.08\pm 0.44$	$67.99\pm 1.03$	$\underline{52.95\pm 1.04}$	$\underline{69.69\pm 2.12}$	$\mathbf{51.68\pm 4.27}$	$54.00\pm 2.77$
Methods	M3 $\to$ M2	M3 $\to$ M1	M3 $\to$ M0	M2 $\to$ M1	M2 $\to$ M0	M1 $\to$ M0
+ L2	$\underline{56.55\pm 2.24}$	$\mathbf{44.37\pm 0.95}$	$\underline{57.14\pm 0.32}$	$\mathbf{75.77\pm 0.58}$	$\mathbf{68.56\pm 0.20}$	$\mathbf{61.55\pm 4.99}$
+ Front	$56.33\pm 2.68$	$44.06\pm 1.04$	$\mathbf{57.23\pm 0.25}$	$\underline{75.50\pm 0.50}$	$\underline{68.49\pm 0.46}$	$61.40\pm 5.45$

Appendix

Table 11: Accuracy (in %) on Mutagenicity (source

\to

target) under Regularization Strength

L=3

Figure 9: Setting A: layerwise downstream-product proxy by method. For each layer

l

, we plot the mean of

P_{l}=\prod_{j\geq l}\|W_{j}\|_{F}

over all runs. Both non-uniform methods show smaller downstream products than gcn_l2 , especially at earlier layers.

Figure 10: Setting A: paired-change analysis against gcn_l2 . Left: distributions of paired shifts in product proxy (

\Delta P_{1}

) and target accuracy (

\Delta\mathrm{Acc}

). Right: relation between

\Delta P_{1}

and

\Delta\mathrm{Acc}

(Spearman

\rho=0.604

for front vs l2 ,

\rho=0.651

for back vs l2 ; each computed from 60 paired comparisons = 12 transfer directions

\times

5 seeds).

Figure 11: Setting B: combined absolute sensitivity curves. Mean

\lvert\Delta\ell\rvert

versus perturbation magnitude

\epsilon

for all methods in one panel. Early-layer sensitivity ( conv0 ) is consistently dominant. Compared with gcn_l2 , both gcn_front and gcn_back reduce early-layer sensitivity, most clearly at larger

\epsilon

Figure 12: Setting B: combined absolute sensitivity curves. Left: integrated

\lvert\Delta\ell\rvert

over

\epsilon

(aggregate sensitivity), confirming strongest fragility at conv0 . Right: combined signed

\Delta\ell

curves; signed averages can be small due to cancellation across perturbation directions, so absolute response is used as the primary metric in Fig. 11 .

Figure 13: Setting C: pair-level best-

\alpha

distribution under budget fixing. For each transfer pair, we mark the

\alpha

that gives the best mean target accuracy. Best points are spread across multiple

\alpha\neq 1

values, indicating that non-uniform allocations are systematically useful.

Panel of Figure 14 — Figure 14: Bound changes along with the varying weight changes of the MLP classifier and of the MPNN feature extractor.

Panel of Figure 15 — Figure 15: Bound changes along with varying quantities regarding to the RGM kernel function $W$ .

Panel of Figure 16 — Figure 16: Bound changes along with complexity of feature mapping $f$ (joint implication).

Figure 17: Bound change against

D_{\mathcal{X}}

Panel of Figure 18 — Figure 18: Bound changes along with: (a) MPNN Lipschitz $L_{\Phi},L_{\Psi}$ , (b) MPNN number of layers $T$ .

Figure 19: MPNN number of layers

T

affect bound change rates over

\frac{\left\|\Delta\Theta_{\Box^{(l)}}\right\|_{F}}{\left\|\Theta_{\Box^{(l)}}\right\|_{F}}

Panel of Figure 20 — Figure 20: Bound changes along with: (a) latent Gaussian shifts $s$ , (b) number of classes $Cisn$ .

Figure 21: Number of nodes

N

affects

\Delta_{N}

change in polynomial.

Graph Domain Adaptation

See all 9 papers

Cross-Resolution Semantic Learning for Graph Domain Adaptation
Jul 31, 2026Yingxu Wang, Haoze Huang, Zhongkai Zheng +1Unsupervised Domain Adaptation Graph Representation Learning
Mohamed bin Zayed University of Artificial Intelligence · Fuzhou University · Sun Yat-sen University +1
Efficient Memory Crystallization for Graph Learning under Non-Stationary Distribution Shifts
Oct 2, 2026Yue Hou, Ruomei Liu, Yingke Su +2Continual Test-Time Adaptation Domain-Incremental Learning
State Key Laboratory of Complex & Critical Software Environment, Beihang University · Shen Yuan Honors College, Beihang University
Graph Domain Adaptation Does Not End with Representation Learning
Sep 22, 2026Ziqian Liu, Yongxue Xu, Enze Zhang +3Unsupervised Domain Adaptation Graph Representation Learning
Sun Yat-sen University, China · University of Wisconsin–Madison, USA · Jiangsu University, China +2

Jul 31, 2026J/K move · Enter open · S save

Cross-Resolution Semantic Learning for Graph Domain Adaptation

Yingxu Wang, Haoze Huang, Zhongkai Zheng, Shangsong Liang

Mohamed bin Zayed University of Artificial Intelligence · Fuzhou University · Sun Yat-sen University+1

Unsupervised Domain Adaptation Graph Representation Learning Domain Adaptation Graph Domain Adaptation

Open paper AskPDF arXiv

Graph Domain Adaptation (GDA) transfers predictive knowledge from labeled source graphs to unlabeled target graphs under distribution shift. Existing methods align representations or regularize graph structures, but do not explicitly model how class-discriminative knowledge learned at different source neighborhood ranges should be routed across target ranges. We call the neighborhood range encoded by a graph representation its propagation resolution and define semantic resolution shift as a cross-domain change in the propagation resolutions at which class-discriminative evidence is strongest. Such shifts can make fixed same-resolution pairing suboptimal and increase the risk of negative transfer. To address this issue, we propose Cross-Resolution Semantic Learning (CReSL), a GDA method that learns soft sourceto-target resolution correspondence from cross-domain class structure. First, CReSL constructs a multi-resolution representation bank using a shared Graph Neural Network and learnable resolution embeddings, with a resolution-indexed expert for each source resolution. Second, CReSL introduces Cross-Resolution Prototype Transport, which constructs class-resolution prototypes from source labels and soft target posteriors and converts cross-domain prototype discrepancies into expert-specific routing over target resolutions. Third, CReSL introduces Cross-Resolution Target Grafting, which constructs posterior-weighted target-to-source prototype displacements and enforces correspondence-weighted prediction consistency for instance-level adaptation under class uncertainty. Extensive experiments on graph benchmarks under diverse domain shifts show that CReSL outperforms strong representative baselines across most settings.

Abstract

Graph Domain Adaptation

Explore similar work

Cross-Resolution Semantic Learning for Graph Domain Adaptation

Efficient Memory Crystallization for Graph Learning under Non-Stationary Distribution Shifts

Graph Domain Adaptation Does Not End with Representation Learning