Revisiting Temporal Link Prediction through Structural Proximity

Yuzhang Fei; Yanping Zheng; Lu Yi; Zhewei Wei

cs.SIOct 28, 2026

Revisiting Temporal Link Prediction through Structural Proximity

Authors: Yuzhang Fei, Yanping Zheng, Lu Yi, Zhewei Wei

Organizations: Renmin University of China

Abstract

Existing temporal link prediction methods typically rely on learned temporal representations to capture evolving interaction patterns. In this paper, we show that a classical structural proximity measure can match or outperform these methods without training or learned temporal sequence modeling. We revisit Personalized PageRank (PPR) on historical interaction graphs, using simple sliding-window retention or exponential time decay. Surprisingly, across 14 datasets, Time-decay PPR ranks first on nine and second on four among the compared methods, including datasets with few repeated edges. To understand this result, we examine the historical paths connecting source nodes to previously unseen destinations. We find that such paths contain useful predictive information, and that PPR outperforms a strong neural baseline on queries where historical structure clearly distinguishes the true destination from negative candidates. These results show that strong performance on current benchmarks does not necessarily require complex temporal models. More fundamentally, they raise the question of how much predictive value learned temporal modeling adds beyond historical structural proximity. Our findings motivate reassessing progress in temporal link prediction with strong classical baselines.

Figures & tables

Figure 1: (a) Mean rank over each method’s reported results across 14 datasets; missing results are excluded. Standard deviations are across datasets, and ties share the same rank. (b) Relative test MRR against Time-decay PPR across available results from 14 datasets. Dots represent dataset results, boxes indicate interquartile ranges, whiskers mark the 10th–90th percentiles, and diamonds denote means. Negative values favor Time-decay PPR.

Method	GoogleLocal	Yelp	Taobao	YouTube	Flickr	WikiLink	tgbl-review
JODIE	41.86±1.49	69.88±0.31	48.36±2.18	41.67±2.86	46.21±0.83	57.94±1.33	41.43 ±0.15
DyRep	37.73±1.34	57.69±1.05	40.03±2.40	35.12±4.13	38.04±4.19	42.63±1.33	40.06 ±0.59
TGAT	19.78±0.24	—	—	43.56±2.53	23.53±3.35	—	19.64±0.23
TGN	54.13±1.97	69.79±0.24	60.28±0.54	55.16±5.89	46.03±6.78	62.94±2.16	37.48±0.23
CAWN	18.26±0.02	25.71±0.09	—	47.55±1.08	48.69±6.08	—	19.30±0.10
GraphMixer	21.31±0.14	33.96±0.19	31.54±0.02	58.87±0.12	45.01±0.08	48.57±0.02	36.89±1.50

Table 1: Test MRR

\times 100

(

\uparrow

) on unseen-dominant datasets. Baseline results are from Yi et al. (2025a) .

Method	Wikipedia	Reddit	LastFM	UCI	Flights	tgbl-coin	tgbl-flight
JODIE	76.48±1.72	77.16±1.27	18.49±2.87	51.43±1.74	20.37±4.18	—	—
DyRep	67.42±4.21	72.33±2.14	17.76±6.56	14.00±2.71	15.62±0.47	45.20±4.60	55.60±1.40
TGAT	72.72±1.50	78.03±0.25	24.10±1.26	31.50±0.48	53.90±1.07	60.92±0.57	—
TGN	82.22±0.39	79.25±0.24	25.59±4.43	45.29±6.43	64.24±2.11	58.60±3.70	70.50±2.00
CAWN	86.07±0.08	87.66±0.04	35.10±0.34	66.96±0.48	80.06±2.10	—	—
GraphMixer	73.57±1.48	70.87±0.38	26.76±1.42	59.58±1.00	42.26±0.49	75.57±0.27	—

Table 2: Test MRR

\times 100

(

\uparrow

) on seen-dominant datasets. Baseline results are from Yi et al. (2025a) .

Figure 2: A new edge closes a historical path into a cycle.

Figure 3: Unique node pairs per time interval, grouped by recurrence and closure of historical triangles, four-cycles, or six-cycles. Earlier categories take precedence; definitions are in Appendix C .

Figure 5: Validation sensitivity to half-life and aggregation, with

\alpha

and propagation depth fixed. Half-lives follow an ordered grid;

\infty

denotes no decay. Each panel has its own vertical scale.

Figure 6: Validation sensitivity to

\alpha

and

K

on Wikipedia and YouTube. Other parameters are fixed.

K

uses an ordered grid; markers show measured values. Each panel has its own vertical scale.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Unseen-dominant
Dataset	Interaction	Nodes	Events	Timestamps	Repeat (%)
GoogleLocal	Business review	206,244/267,336	1,913,967	1,771,060	0.00
Yelp	Business review	1,338,688/405,081	19,760,293	14,646,734	25.18
Taobao	Product interaction	760,617/863,016	18,853,792	139,171	16.58
YouTube	Follow	402,422	3,288,028	203	0.00
Flickr	Follow	233,836	7,223,559	134	0.00

Appendix

Table 4: Dataset statistics reported by Yi et al. (2025a) .

Dataset	Aggr.	$W$	$\alpha$	$K$	Aggr.	$h$	$\alpha$	$K$
	Window-based PPR				Time-decay PPR
Wikipedia	count	$7\,\mathrm{d}$	0.6	7	last	$7\,\mathrm{d}$	0.9	5
Reddit	count	$\infty$	0.6	3	sum	$7\,\mathrm{d}$	0.6	3
LastFM	count	$30\,\mathrm{d}$	0.8	4	sum	$7\,\mathrm{d}$	0.4	4
UCI	count	$7\,\mathrm{d}$	0	3	last	$1\,\mathrm{d}$	0	3
Flights	count	$90\,\mathrm{d}$	0.9	3	sum	$30\,\mathrm{d}$	0.8	3

Appendix

Table 5: Configurations used for the main-table PPR results.

Figure 7: Positive and negative candidate coverage by one-, two-, and three-step simple paths on seven complete test sets.

Bipartite graphs
	2-hop		3-hop
Dataset	AUC	MRR	AUC	MRR
Wikipedia	—	—	58.75	18.05
Reddit	—	—	70.59	28.04
LastFM	—	—	53.54	8.66
GoogleLocal	—	—	80.14	48.61

Appendix

Table 6: Query-averaged ROC-AUC and MRR (

\times 100

) of two- and three-step simple-path counts on the test set.

Figure 8: Recurrence and historical cycle closure on the remaining ten datasets, using the categories and counting protocol of Figure 3 .

Figure 9: Three- through six-cycle accumulation versus the exact random-order expectation, indexed by distinct-edge coverage.

Figure 10: Observed minus expected cycle fractions across datasets. Positive values indicate earlier cycle accumulation than under random edge ordering.

Dataset	Interactions	Distinct edges $M$	3-cycles	4-cycles	5-cycles	6-cycles
GoogleLocal	1,913,967	1,913,967	$0\phantom{.00\times 10^{00}}$	$2.03\times 10^{7\phantom{0}}$	$0\phantom{.00\times 10^{00}}$	$3.26\times 10^{10}$
YouTube	3,288,028	3,288,028	$6.57\times 10^{6\phantom{0}}$	$5.96\times 10^{9\phantom{0}}$	$3.90\times 10^{11}$	$3.83\times 10^{14}$
Wikipedia	157,474	18,257	$0\phantom{.00\times 10^{00}}$	$1.22\times 10^{5\phantom{0}}$	$0\phantom{.00\times 10^{00}}$	$3.38\times 10^{7\phantom{0}}$
Reddit	672,447	78,516	$0\phantom{.00\times 10^{00}}$	$1.25\times 10^{7\phantom{0}}$	$0\phantom{.00\times 10^{00}}$	$4.15\times 10^{10}$
LastFM	1,293,103	154,993	$0\phantom{.00\times 10^{00}}$	$5.98\times 10^{8\phantom{0}}$	$0\phantom{.00\times 10^{00}}$	$1.85\times 10^{13}$
Flights	1,927,145	295,795	$3.94\times 10^{6\phantom{0}}$	$5.08\times 10^{8\phantom{0}}$	$8.15\times 10^{10}$	$1.47\times 10^{13}$

Appendix

Table 7: Interactions, distinct edges, and simple cycles in the final aggregated graph.

Dataset	Group	Share (%)	PPR	CRAFT	$\Delta$	Contribution
GoogleLocal	Strong	38.85	94.63	86.61	+8.02	+3.12
GoogleLocal	Medium	22.37	59.09	57.43	+1.65	+0.37
GoogleLocal	Weak	1.34	23.11	32.42	-9.31	-0.12
GoogleLocal	No 3-step	37.44	41.65	42.24	-0.60	-0.22
GoogleLocal	All	100.00	65.89	62.75	+3.14	+3.14
YouTube	Strong	49.13	96.99	85.48	+11.51	+5.66

Appendix

Table 8: Test MRR

\times 100

by structural group.

\Delta

is PPR minus CRAFT; contribution is query share times

\Delta

Dataset	Window	Excluded events
Wikipedia	7d	68.47%
Reddit	90d	0.00%
LastFM	30d	96.93%
UCI	7d	90.92%
Flights	90d	13.53%
YouTube	90d	31.95%

Appendix

Table 9: Selected windows and mean fractions of excluded historical events.

Figure 11: Half-life and aggregation sensitivity on all seven datasets. Validation MRR

\times 100

; panel-specific vertical scales.

Figure 12: Sensitivity to

\alpha

and

K

on seven datasets, with other parameters fixed. Validation MRR

\times 100

	Unseen-dominant
Method	GoogleLocal	Yelp	Taobao	YouTube	Flickr	WikiLink	tgbl-review
EdgeBank ∞	1.96	9.77	20.28	1.95	1.96	1.96	1.89
EdgeBank tw	1.96	5.89	14.62	1.96	1.96	1.96	2.05
Pair-recency	1.96	9.79	20.29	1.95	1.96	1.96	1.97
Pair-frequency	1.96	9.78	20.29	1.95	1.96	1.96	1.89
Destination-recency	13.41	24.78	20.72	34.57	20.78	30.55	33.01

Appendix

Table 10: Test MRR

\times 100

of heuristic baselines on the original candidate sets. Time-decay PPR results follow the main tables.

Method	Wikipedia	Flights	GoogleLocal	YouTube	Flickr
JODIE	66.39±0.51	11.06±2.00	25.63±0.12	5.88±0.78	17.60±1.47
DyRep	62.39±1.66	5.54±0.24	22.29±0.28	5.03±0.21	14.34±0.34
TGN	77.47±0.92	30.57±1.46	37.35 ±0.18	11.04 ±1.34	19.20±1.03
GraphMixer	60.93±0.17	11.95±0.28	7.01±0.05	4.84±0.15	4.82±0.18
DyGFormer	85.16 ±0.08	60.89 ±0.21	4.77±0.20	5.73±0.50	22.46 ±3.11
CRAFT / CRAFT-R	83.40 ±0.12	56.65 ±0.58	49.54 ±0.50	10.83 ±0.56	29.12 ±0.32

Appendix

Table 11: Test MRR

\times 100

(

\uparrow

) under activity-weighted negative sampling (mean

\pm

standard deviation over three seeds).

Temporal Link Prediction

Temporal link prediction forecasts which relationships will form or recur as networks and knowledge graphs change over time.

See all 62 papers

Do Temporal Link Predictors Need Learned Memory? A Smoothed-Count Baseline with a Handful of Parameters
Sep 28, 2026Lisi Qarkaxhija, Ingo ScholtesLink Prediction Temporal Link Prediction
Chair of Machine Learning for Complex Networks Center for Artificial Intelligence and Data Science (CAIDAS) Julius-Maximilians-Universität Würzburg, DE
EdgeReMIND: A Scalable, Top-Ranked Memorization Baseline for Temporal Multi-Relational Link Prediction
Sep 15, 2026Bryant PollardLink Prediction Temporal Link Prediction
Clemson University
Your Temporal Link Predictor Is Blind to Who Is Active: A Missing Factor That Transfers Across Models
Oct 4, 2026Ji Zhang, Zixin Liu, Yiran Ding +3Temporal Link Prediction Dynamic Graph Learning
Tsinghua University

Sep 28, 2026J/K move · Enter open · S save

Do Temporal Link Predictors Need Learned Memory? A Smoothed-Count Baseline with a Handful of Parameters

Lisi Qarkaxhija, Ingo Scholtes

Chair of Machine Learning for Complex Networks Center for Artificial Intelligence and Data Science (CAIDAS) Julius-Maximilians-Universität Würzburg, DE

Link Prediction Temporal Link Prediction

Open paper AskPDF arXiv

Many temporal link predictors summarize past interactions through learned node representations. We examine whether simple counts of recurring interaction patterns can provide competitive predictions without learning these representations. We propose a temporal link predictor based on statistical language modelling. It pools transition and co-occurrence counts across sources to predict links that a source has never formed. We smooth sparse estimates using destination frequencies or Kneser-Ney continuation counts. A shared log-linear rule combines these estimates with popularity, source history, and recency, without node embeddings. In our main evaluation, the model achieves the highest MRR among the compared methods on 7 out of 16 datasets from TGB and TGB-Seq. It also outperforms EdgeBank and Base3 on all 16 datasets and the heuristic family on 14. These gains extend to datasets designed to limit repeated edges. With only 9--13 learned parameters, our model provides a simple and competitive baseline for evaluating future neural temporal link predictors.

Abstract

Temporal Link Prediction

Explore similar work

Do Temporal Link Predictors Need Learned Memory? A Smoothed-Count Baseline with a Handful of Parameters

EdgeReMIND: A Scalable, Top-Ranked Memorization Baseline for Temporal Multi-Relational Link Prediction

Your Temporal Link Predictor Is Blind to Who Is Active: A Missing Factor That Transfers Across Models