STAMP: Symmetric Temporal Averaging Message Passing for Domain Adaptation in Chronologically Split Graphs

Joo Young Park; Sejun Park; Hyunwoo Park

cs.LGNov 17, 2024

STAMP: Symmetric Temporal Averaging Message Passing for Domain Adaptation in Chronologically Split Graphs

Authors: Joo Young Park, Sejun Park, Hyunwoo Park

Organizations: College of Medicine, Seoul National University, Gwanak-gu, Seoul 08826, Korea · Electrical and Computer Engineering, Seoul National University, Gwanak-gu, Seoul 08826, Korea · Graduate School of Data Science, Seoul National University, Gwanak-gu, Seoul 08826, Korea

Abstract

This paper addresses domain adaptation in graph-structured data under chronological splits. We consider transductive semi-supervised node classification (SSNC), in which labels of historical nodes are used to predict labels of more recent nodes. Temporal dependencies in graph connectivity induce distribution shifts across time, often degrading the performance of models trained on past nodes. Despite its practical relevance, domain adaptation under chronological graph splits remains relatively underexplored. We propose Symmetric Temporal Averaging Message Passing (STAMP), a timestamp-balanced operator that replaces standard neighborhood aggregation with temporally aligned propagation. We call its specialized variant for the heterogeneous ogbn-mag dataset STAMP-mag, reserving STAMP for the general formulation. By balancing messages across timestamps, STAMP enforces first-moment invariance across temporal domains while remaining scalable and easy to implement. Unlike many existing domain adaptation methods, whose assumptions are difficult to verify on graphs, STAMP relies on transparent, practically checkable conditions and is supported by theoretical analysis. Empirically, STAMP and STAMP-mag improve accuracy across all evaluated temporal graph benchmarks. STAMP achieves state-of-the-art performance on ogbn-arxiv, while STAMP-mag does so on ogbn-mag. For temporal-split Pokec, where no established benchmark exists, applying STAMP to the state-of-the-art model for the original dataset consistently improves performance under our chronological split. These results demonstrate that timestamp-balanced propagation is an effective and practical approach to mitigating temporal distribution shift in graph learning.

Figures & tables

Figure 1: Illustrative explanation of a chronological split dataset. Nodes are organized by their timestamps along the horizontal axis. The training set consists of nodes from earlier time periods, while the test set contains the most recent nodes. Edges may connect nodes across different timestamps, and the neighborhood composition of a node can change over time, leading to distribution shift between the training and test domains.

Figure 2: Overview of STAMP. Conventional message passing assigns greater weight to timestamps with more neighbors, whereas STAMP balances contributions across timestamps before passing the aggregated features to the GNN.

M_{v}^{(1)}=\sum_{u\in\mathcal{N}_{v}}\alpha_{u\to v}X_{u}^{(0)}.

Algorithm 1 Symmetric Temporal Averaging Message Passing ( STAMP )

Figure 3: Graphical representation of functions $f$ and $g$ , which jointly govern the distribution of neighboring node label–timestamp pairs under Assumption 3. The shaded bars denote relative connectivity for a target node with label $y$ ; only neighboring nodes with label $\tilde{y}$ are shown. The function $g(y,\tilde{y},|\tilde{t}-t|)$ captures how relative connectivity decays with temporal distance, while the normalization factor $f(y,t)$ adjusts the overall scale so that ${P}_{yt}(\tilde{y},\tilde{t})$ forms a valid probability distribution.

Figure 4: Graphical illustration of STAMP-mag. For a target node at timestamp $t=2018$ , neighbors at timestamps $2017$ and $2019$ form a symmetric pair ( $\Delta=1$ ), contributing equally during aggregation. Neighbors at timestamps outside this symmetric range (e.g., $2016$ , $2015$ , …) are single nodes whose weights are doubled under STAMP-mag to restore balance.

Property	STAMP	STAMP-mag
Corrected imbalance	Unequal numbers of neighbors across source timestamps.	Unequal multiplicity between paired temporal offsets and one-sided offsets near chronological boundaries.
Aggregation	Averages neighbors within each source-timestamp bucket and assigns equal total mass to every timestamp.	Assigns weight $2$ to same-time and one-sided neighbors and weight $1$ to paired neighbors, followed by normalization.
Feature assumption	$\mathbb{E}[X_{u}^{(0)}]=m_{1}(time(u)).$ The feature mean depends only on the source timestamp.	$\mathbb{E}[X_{u}^{(0)}]=\mu_{1}(y_{u}).$ The feature mean depends only on the source label and is time-invariant.
Graph assumption	Every target node has at least one neighbor at each timestamp: $\|\mathcal{N}_{v}(\tilde{t})\|>0,\quad\forall v,\tilde{t}.$	Neighbor connectivity depends symmetrically on temporal distance: $P_{yt}(\tilde{y},\tilde{t})=f(y,t)g(y,\tilde{y},\|\tilde{t}-t\|).$
Guarantee	Exact first-moment invariance with respect to the target label and timestamp under the assumptions.	Approximate first-moment invariance with respect to the target timestamp under the assumptions.
Recommended setting	Chronological graphs with broad cross-time connectivity and substantial imbalance among timestamp buckets.	Citation-like graphs with approximately symmetric temporal connectivity truncated near chronological boundaries.

Table 1: Comparison between STAMP and STAMP-mag.

	Temporal Aggregation Skew			Boundary Asymmetry
Model	Baseline	STAMP	Gain	Baseline	STAMP-mag	Gain
SGC	$0.2036\pm 0.0220$	$0.7573\pm 0.0022$	$+0.5538$	$0.4089\pm 0.0377$	$0.9356\pm 0.0318$	$+0.5267$
GCN	$0.1951\pm 0.0072$	$0.8471\pm 0.0025$	$+0.6520$	$0.6689\pm 0.0113$	$0.9189\pm 0.1147$	$+0.2500$
GraphSAGE	$0.3569\pm 0.0242$	$0.8924\pm 0.0077$	$+0.5356$	$0.7789\pm 0.0068$	$0.9889\pm 0.0042$	$+0.2100$
RevGAT †	$0.2453\pm 0.0214$	$0.9062\pm 0.0064$	$+0.6609$	$0.7300\pm 0.0191$	$0.9911\pm 0.0103$	$+0.2611$

Table 2: Test accuracy on the two synthetic benchmarks. The TSBM evaluates STAMP under temporal bucket imbalance, while the boundary-asymmetric graph evaluates STAMP-mag when label-informative edges occur on only one temporal side. Results are averaged over seeds

{0,1,2}

	Nodes				Edges
Dataset	Type	#Train	#Valid	#Test	Src	Edge type	Dst	#Edges
ogbn-arxiv	Paper	90,941	29,799	48,603	Paper	cites*	Paper	1,166,243
t.s. Pokec	User	1,218,296	297,038	117,306	User	connects to*	User	30,622,117
ogbn-mag	Paper	59,965	64,879	41,939	Author	affil. with	Inst.	1,043,998
	Author	1,134,649	0	0	Author	writes	Paper	7,145,660
	Inst.	8,740	0	0	Paper	cites*	Paper	5,416,271

Table 3: Type and number of nodes and edges in experimental datasets.

Dataset	Model	Test Acc. $\pm$ Std.	Valid Acc. $\pm$ Std.
ogbn-arxiv	SimTEG+TAPE+RevGAT † +STAMP	0.7820 $\pm$ 0.0007	0.7867 $\pm$ 0.0009
	SimTEG+TAPE+RevGAT (previous SOTA)	0.7803 $\pm$ 0.0007	0.7846 $\pm$ 0.0004
	SimTEG+TAPE+RevGAT (our environment)	0.7795 $\pm$ 0.0015	0.7831 $\pm$ 0.0005
temporal-split Pokec	GCN+STAMP	0.7676 $\pm$ 0.0016	0.7886 $\pm$ 0.0011
	GCN (previous SOTA*)	0.7668 $\pm$ 0.0017	0.7887 $\pm$ 0.0012
ogbn-mag	HGAMLP-HOPE+STAMP-mag	0.5806 $\pm$ 0.0013	0.6002 $\pm$ 0.0007

Table 4: Experimental results on real-world datasets. Best results are shown in bold. Results were averaged from seeds 0 to 9.

Method	Weight construction	First propagation	Additional time	Additional memory
STAMP	$\mathcal{O}(E)$	$\mathcal{O}(Ef)$	$\mathcal{O}(E)$	$\mathcal{O}(B+E)$
STAMP-mag	$\mathcal{O}(E)$	$\mathcal{O}(Ef)$	$\mathcal{O}(E)$	$\mathcal{O}(N+E)$

Table 5: Additional computational cost of adapting a pre-existing graph learning method with STAMP or STAMP-mag. Both methods replace the ordinary first feature-propagation operation rather than adding propagation layers.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Timestamp-conditioned feature means on ogbn-arxiv using the exact TAPE RoBERTa representation employed as $X^{(0)}$ . Panel a reports pairwise Euclidean distances between empirical timestamp means. Panel b reports the distance of each timestamp mean from the global mean, together with the relative number of nodes at that timestamp. The results reveal a measurable temporal first-moment shift.

Figure 6: Timestamp-conditioned feature means on temporal-split Pokec using the exact normalized representation employed as $X^{(0)}$ . Panel a reports pairwise Euclidean distances between empirical timestamp means. Panel b reports the distance of each timestamp mean from the global mean, together with the relative number of nodes at that timestamp. The timestamp effect is accompanied by comparatively small residual label dependence.

Figure 7: Estimated relative connectivity. [Left] when $y=1$ and $\tilde{y}=1$ , [Right] when $y=311$ and $\tilde{y}=1$ .

Figure 8: Weighted average relative connectivity. [Left] when $y=\tilde{y}$ , [Right] when $y\neq\tilde{y}$ .

Figure 9: 2D projection of each community’s mean feature by t-SNE. Points corresponding to communities with the same label are represented in the same color. [Left] Plot for all 349 labels, [Right] Plot for 15 labels with the most nodes.

Temporal Domain Adaptation

See all 10 papers

Selectivity Matters: Source Node Influence Pruning for Unsupervised Graph Domain Adaptation
Jul 20, 2026Ridong Han, Yawen Shen, Zhongnian Li +3Unsupervised Domain Adaptation Domain Adaptation
School of Computer Science and Technology / School of Artificial Intelligence, China University of Mining and Technology, Xuzhou 221116, China · Mine Digitization Engineering Research Center of the Ministry of Education, Xuzhou 221116, China · Jiangsu Provincial Industrial Technology Engineering Center for Intelligent Sensing and Emergency IoT in Underground Space, Xuzhou 221116, China +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
Never Skip a Batch: Dense Learning of Temporal GNNs via Adaptive Pseudo-Supervision
May 18, 2025Alexander Panyshev, Dmitry Vinichenko, Oleg Travkin +2Temporal GNNs Temporal Link Prediction
Risk AI Research Lab Moscow Independent Research Institute of Artificial Intelligence Moscow, Russia · Risk AI Research Lab Moscow, Russia · Risk AI Research Lab Applied AI Institute Moscow, Russia

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

Selectivity Matters: Source Node Influence Pruning for Unsupervised Graph Domain Adaptation

Ridong Han, Yawen Shen, Zhongnian Li, Tongfeng Sun+2

School of Computer Science and Technology / School of Artificial Intelligence, China University of Mining and Technology, Xuzhou 221116, China · Mine Digitization Engineering Research Center of the Ministry of Education, Xuzhou 221116, China · Jiangsu Provincial Industrial Technology Engineering Center for Intelligent Sensing and Emergency IoT in Underground Space, Xuzhou 221116, China+1

Unsupervised Domain Adaptation Domain Adaptation Data Selection Graph Domain Adaptation

Open paper AskPDF arXiv

Unsupervised Graph Domain Adaptation (UGDA) aims to facilitate knowledge transfer from a labeled source graph to an unlabeled target graph by mitigating cross-domain distribution shifts. Existing methods primarily focus on node-level feature alignment in latent spaces, relying on the implicit assumption that all source nodes contribute positively to the alignment. However, this assumption often fails because a node's semantic information is intrinsically coupled with its topological graph structure. Due to structural shifts, source nodes with severe structural deviations (e.g., structural outliers) lack semantic counterparts in the target graph, and forcing alignment on them introduces severe noise and causes negative transfer. To bridge this gap, we argue that selective source node utilization is superior to full-graph training, thereby shifting the research paradigm from feature-level alignment to data-level refinement. To this end, we propose Source Node Influence Pruning (SNIP), a novel model-agnostic, data-centric refinement framework. Specifically, SNIP quantifies the structural discrepancy between individual source nodes and the target domain by integrating multiple centrality measures, assigning each source node an influence score. A rank-based normalization mechanism is further employed to eliminate scale variations across different measures, allowing SNIP to effectively identify and filter out structurally incompatible nodes with low influence scores. As a plug-and-play method, SNIP constructs a refined "sub-source" graph that is inherently more beneficial for subsequent alignment. Comprehensive experiments across eight transfer scenarios on five real-world datasets demonstrate that SNIP consistently outperforms competitive baselines and significantly enhances adaptation performance, validating the superiority of selective node utilization over full-graph training.

Abstract

Temporal Domain Adaptation

Explore similar work

Selectivity Matters: Source Node Influence Pruning for Unsupervised Graph Domain Adaptation

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

Never Skip a Batch: Dense Learning of Temporal GNNs via Adaptive Pseudo-Supervision