acceptodds
Under review as a conference paper at ICLR 2027

Revisiting Temporal Link Prediction through Structural Proximity

Abstract

Temporal link prediction is an important task for understanding evolving real-world systems, encompassing both recurring interactions and the formation of new relations. Existing studies often characterize datasets by the proportion of previously unseen relations. However, an unseen node pair may still be strongly connected through multi-step paths in the historical graph. This raises a more fundamental question: how much of future-link predictability can be explained by historical structural proximity, even without representation learning? To investigate this question, we revisit Personalized PageRank (PPR), a classical training-free measure of structural proximity, to assess how well historical connectivity predicts future interactions.We incorporate temporal decay into PPR to account for interaction recency, yielding Time-decay PPR. Across 14 datasets spanning diverse domains and interaction patterns, Time-decay PPR ranks first on nine and second on four among the compared methods. Further experiments show that multi-step historical paths help distinguish candidate destinations for new relations, suggesting that current neural models may not fully exploit these structural cues. These findings highlight the predictive value of historical structural proximity and offer insights for reassessing existing methods and designing future models.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
temporal link prediction, dynamic graphs, Personalized PageRank, structural proximity, training-free methods

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_n9QgOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper considers the temporal link prediction (TLP) on continuous-time dynamic graphs (CTDGs). Surprisingly, it shows that a classical structural proximity measure can match or outperform existing TLP methods without training or learned temporal sequence modeling and explores how much predictive information does historical multi-hop structure provide for future link prediction. Concretely, Personalized PageRank (PPR) on historical interaction graphs with simple sliding-window retention or exponential time decay was adopted as an example proximity measure, with its effectiveness validated by a series of empirical evaluations.

Critical strengths

S1. The overall presentation of this paper is easy to read and understand.

S2. This paper shows an interesting and surprising findings that a classical structural proximity measure (i.e., RRP with simple sliding-window retention or exponential time decay) can match or outperform existing TLP methods without training or learned temporal sequence modeling, which was validated by a great amount of empirical experiments.

*S3. This paper anonymously provides its code and data to ensure reproducibility of experiments.

Critical weaknesses

W1. It seems that this paper does not give a comprehensive problem statement regarding the considered TLP problem.

It was not stated that this paper consider what data model of dynamic graphs, e.g., discrete-time dynamic graphs (DTDGs) or continuous-time dynamic graphs (CTDGs), as different data models may have different experiment settings and evaluation protocols.

It was not clearly stated that whether graph attributes are available. It seems that the proposed method does not require graph attributes, while some baselines in experiments (e.g., DyRep, TGAT, DyGFormer, etc.) can leverage node attributes.

It was also not stated this paper considers the conventional transductive or advanced inductive settings of TLP or even the both.


W2. Consistent with W1, it seems that the PPR heuristic in this paper cannot support the advanced inductive TLP, which aims to predict future links for new nodes not observed in previous time steps. In contrast, some baselines in experiments (e.g., DyRep, TGAT, TGN, CAWN, DyGFromer, etc.) can handle this advanced setting.


W3. Some details regarding the proposed method need further clarifications.

In Eq. (4), the definition of II[Δt≤W]II[\Delta t \le W] is not given.

For Eq. (5), the basic logic about why max and sum aggregation can "distinguish the recency or presence of a relation from the accumulated evidence of its recurrence" remains unclear, which need further interpretations.


W4. There seems neither theoretical analysis about the proposed method's complexity nor empirical evaluation about runtime.

This paper introduce a simple yet effective method (with two variants), which can surprisingly achieve inference quality competitive to or even better than SOTA baselines. It indicates that this simple method may also ensure much better inference efficiency or scalability, although it cannot ensure the best quality in all cases. Namely, a significant trade-off between quality and efficiency/scalability may be another superiority of this work. However, there seem no formal complexity analysis and runtime evaluation to highlight this superiority.


W5. Some details of empirical experiment evaluations also need further clarifications.

In Tables 1 and 2, it is unclear why some experiment results are missing (e.g., TGAT on Yelp, Taobao, and WikiLink).

For the definition of random-order reference in Section 5.1, it seems that the aggregated simple graph GMG_M is weighted, as defined in Eq. (5). It is unclear how this reference handles edge weights by just reading Eq. (6). In Eq. (6), the definition of Nk(GM)N_k (G_M) is also missing.

For the analysis in Section 5, it seems that counting triangle, 4-cycle, and 6-cycle is time-consuming. It is unclear how to count these cycles (e.g., using what algorithms) within the limited time to report the results.


W6. This paper does not discuss its potential limitations and possible solutions for future directions at the end, as some other submissions do.

Questions for authors

See W1-W6.

5 comments
AuthorsOpenReview ↗

Response to Reviewer n9Qg (Part 1/2)

We thank the reviewer for the positive evaluation and helpful suggestions. Below, we address W1–W6 in detail and have updated the revised manuscript accordingly.

W1: Problem Statement, Attributes, and Transductive/Inductive Settings

Thank you for asking us to clarify the evaluation setting. We study future link prediction on continuous-time dynamic graphs (CTDGs). PPR uses only historical interactions. In the benchmark baseline settings, node and edge attributes are absent or disabled by default across the evaluated datasets, although baselines such as TGAT, TGN, and DyGFormer can incorporate attributes when available. We retain the released benchmark splits where available and split the remaining datasets chronologically. Across the datasets, these splits include both transductive queries and queries involving nodes absent from training, and we report aggregate test MRR over all queries.


W2: Handling Unseen Nodes

We agree that PPR has no structural evidence for a node before its first observed interaction. Scoring links for completely new nodes in the inductive setting fundamentally relies on external node or edge attributes, whereas PPR is designed to isolate and measure the predictive value of historical interaction topology alone. Because attribute-driven inductive generalization and topology-based link prediction rely on different inputs, they are not directly comparable, and a dedicated evaluation of the inductive setting is outside the scope of our study.


W3: Sliding-Window Indicator in Eq. (4) and Aggregation in Eq. (5)

In Eq. (4), let tt be the query time, τ<t\tau<t the interaction time, and Δt=t−τ\Delta t=t-\tau the age of the interaction. The sliding-window indicator is I[Δt≤W]=1\mathbb{I}[\Delta t \le W] = 1 if 0<Δt≤W0 < \Delta t \le W, and 00 if Δt>W\Delta t > W. Thus, the window retains interactions with t−W≤τ<tt-W \le \tau < t.

In Eq. (5), max and sum aggregate the weights of repeated interactions between the same node pair. With exponential decay, the most recent interaction has the largest weight, so max depends only on its age. Sum also includes the decayed weights of earlier interactions. Two pairs with the same most recent interaction time therefore receive the same max weight, while additional past interactions increase the sum weight. With a sliding window, max indicates whether the pair interacted at least once within the window, and sum counts the interactions within that window. We have added these explanations after Eqs. (4) and (5).


W4: Computational Complexity and Runtime Evaluation

Let BB be the number of queries in a scoring batch and qq the number of candidate destinations per query. For queries that share a historical graph, our implementation propagates one vector per distinct source within each scoring batch. If the batch contains U≤BU\le B distinct sources, scoring with a fixed PPR configuration costs O(K[(n+m)U+Bq])O(K[(n+m)U+Bq]), where KK is the propagation depth, nn is the number of nodes, and mm is the number of distinct undirected edges. At each step, the implementation performs sparse propagation, then gathers the BqBq candidate scores and adds their weighted contributions to the running scores.

With candidate IDs already mapped, the total evaluation cost, including one-time graph indexing, is

O(Nlog⁡N+∑j=1J[bjlog⁡(bj+1)+Dj]+K[(n+m)∑ℓUℓ+q∑ℓBℓ]).O\left( N\log N + \sum_{j=1}^{J} \left[ b_{j}\log(b_{j}+1) + D_{j} \right] + K\left[ (n+m)\sum_{\ell} U_{\ell} + q\sum_{\ell} B_{\ell} \right] \right).

Here, NN is the number of indexed interactions, JJ is the number of graph refreshes, bjb_{j} is the number of events processed at refresh jj, and DjD_{j} counts the stored entries visited when renormalizing the affected rows. For Window-based PPR, bjb_{j} includes both arriving and expiring events. The index ℓ\ell runs over scoring batches.

We measured full-test evaluation time and throughput on five datasets using one GPU per run and the original test candidates. Each entry reports minutes / test queries per second.

MethodGoogleLocalYouTubeFlickrFlightsYelp
Time-decay PPR0.26 / 2,7990.73 / 5,2921.31 / 7,7510.19 / 24,80528.69 / 600
CRAFT / CRAFT-R0.95 / 7685.70 / 68111.34 / 8964.93 / 97320.90 / 823
TGN3.91 / 18521.97 / 17750.35 / 20220.63 / 233106.94 / 161
GraphMixer7.93 / 9240.74 / 95107.23 / 9554.49 / 88195.58 / 88
JODIE9.30 / 7845.96 / 84119.91 / 8513.13 / 36558.24 / 295
DyGFormer13.83 / 52118.25 / 33311.82 / 33145.68 / 33312.01 / 55

DyGFormer timings on GoogleLocal, Flights, and Yelp use optimized co-occurrence counting. The Yelp run uses randomly initialized weights for timing.

We have added the complexity analysis to Appendix B.2. Table 6 reports runtime, throughput, and peak GPU memory, and Table 7 reports validation search times.

(Continued in Part 2/2 below.)

AuthorsOpenReview ↗

Response to Reviewer n9Qg (Part 2/2)

(Continued from Part 1/2 above.)

W5: Missing Baseline Results, Random-Order Reference, and Cycle Counting

Regarding the missing baseline results in Tables 1 and 2, a dash indicates that a run failed to complete one training epoch within 24 hours or ran out of memory on a 32 GB GPU. We have added this explanation to the captions of Tables 1 and 2.

Regarding the microcanonical randomized reference model, following Gauvin et al. (2022) [1], let G⋆G^{\star} be the observed network and x(G)x(G) the feature to be preserved. The reference model assigns equal probability to every realization GG satisfying x(G)=x(G⋆)x(G)=x(G^{\star}).

We apply this definition to the growth of the unweighted graph. After removing self-loops, each unordered node pair contributes one edge at its first interaction. We fix the final edge set EME_{M} and sample uniformly from its M!M! possible orderings. We compare the observed and reference graphs after the same number mm of distinct edges has been added. In Eq. (6), Nk(GM)N_{k}(G_{M}) is the number of simple kk-cycles in the final unweighted graph, counting each cycle once.

Regarding cycle counting and runtime, we count simple cycles exactly on selected snapshots, each built from the full interaction history up to that point. Let AA be the snapshot's unweighted adjacency matrix. The triangle and four-cycle counts are

N3=tr(A3)6,N4=12∑u<v((A2)uv2).N_{3} = \frac{\mathrm{tr}(A^{3})}{6}, \qquad N_{4} = \frac{1}{2}\sum_{u < v}\binom{(A^{2})_{uv}}{2}.

Here (A2)uv(A^{2})_{uv} counts common neighbors. The factor 1/61/6 accounts for the three starting vertices and two traversal directions of a triangle. The factor 1/21/2 accounts for the two pairs of opposite vertices of a four-cycle.

For six-cycles on general undirected graphs, we compute

N6=112[∑u,v((A3)uv)2−∑HaHnH].N_{6} = \frac{1}{12}\left[\sum_{u,v}\left((A^{3})_{uv}\right)^{2} - \sum_{H} a_{H} n_{H}\right].

The first sum equals tr(A6)\mathrm{tr}(A^{6}) and counts all closed walks of length six. We accumulate it using blockwise adjacency multiplications. The correction sums over the edge patterns HH used by walks that revisit vertices. Here nHn_{H} counts copies of HH as subgraphs, and aHa_{H} counts the six-step closed walks on one copy that use all its edges. Each remaining simple six-cycle has six possible starts and two directions. On bipartite graphs, we count through the common-neighbor projection and use inclusion–exclusion to ensure that the three opposite-side vertices are distinct.

Including snapshot construction, counting all applicable cycle lengths on the final snapshot took about 52 seconds for YouTube (3.29 million distinct edges) and 31 seconds for GoogleLocal (1.91 million distinct edges). We compute the random-order expectation directly from Eq. (6). The revised definition in Section 5.1 specifies that the graph is unweighted and defines Nk(G)N_{k}(G).


W6: Limitations and Future Directions

Thank you for suggesting that we discuss the limitations and directions for future work. Time-decay PPR runs efficiently on the datasets we evaluated, but repeated sparse propagation remains its main computational bottleneck on very large graphs. The time-decay scale and restart probability are selected for each dataset and held fixed during evaluation. In future work, we plan to learn the decay scale and the contribution of each propagation depth, and to investigate whether diffusion scores can be updated incrementally as the graph evolves. We also plan to study whether incorporating node and edge attributes can improve link prediction in both transductive and inductive settings. We discuss these limitations and directions in Appendix H of the revised manuscript.


References

[1] Gauvin et al. (2022). Randomized Reference Models for Temporal Networks. SIAM Review, 64(4), 763–830.

AuthorsOpenReview ↗

Gentle Follow-up on Our Response (Reviewer n9Qg)

Dear Reviewer n9Qg,

Thanks for your time and effort in reviewing our paper. Your comments have been very valuable in improving our work. As the author–reviewer discussion period will end in about 3 days, we kindly ask if you could check our response and let us know whether your concerns have been addressed. Thanks again for your time and help!

Best regards,
The Authors

Reviewer_avBpOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this work, the authors revisit Personalized PageRank (PPR) as a training-free baseline for measuring the predictive value of historical structural proximity and test it in the context of temporal link prediction. The reported results on fourteen datasets show that a time-decay variant of PPR outperforms other methods (best reported test MRR), including recent and learning-based ones, on nine datasets, motivating a reassessment of current temporal link prediction approaches. However, while the approach is “training free” in the usual sense, hyperparameters such as the aggregation function, the restart probability α\alpha, the window size or the exponential-decay half-life hh are all selected using validation MRR, as reported in Appendix B. Furthermore, the authors analyze how historical structural proximity supports temporal link prediction.

The main value of this paper is showing that fairly simple network-science informed measures, such as PPR, can outperform complex neural methods, by leveraging structural (topological) information, despite limitations such as the lack of support for node or edge features.

Critical strengths

While the manuscript does not introduce fundamentally new measures (but rather two variants of PPR), it directly addresses how current neural approaches are evaluated and the insufficient use of simple (but effective) topological baselines. The approach is also simple (which is a strength per se, IMO) and the manuscript has a clear message that is consequential for the evaluation of current and future approaches.

Critical weaknesses

My concerns mostly relate to the experimental setup and the analysis and conclusions drawn from it.

  • Although the proposed method is training free, it still requires substantial dataset-specific hyper-parameter tuning, so claims such as “outperforms these methods without training” in the abstract should be clearer
  • Lines 87-97: “New interactions often close existing multi-hop paths into cycles, suggesting that future links are frequently foreshadowed by structural connectivity already present […]”. Since any new edge between two nodes that are already connected by an existing multi-hop path closes a cycle, what is the intended insight in the introduction? Considering that the networks are undirected, the only case where there is no multi-hop path between two (unconnected) nodes is when nodes from two different connected components are involved
  • Furthermore, cycles of length 6 involve paths of length 5, which may already span a significant portion of a small-world network. What are the average shortest path length and the diameters of the network instances? Also, according to the stacked barplot in Figure 3, a significant fraction of the new pairs close 5-hop paths in GoogleLocal, so “structural proximity” appears stretched without contextualizing the typical distances
  • The main results tables (Tables 1 and 2) report that “baseline results are from Yi et al. 2025a”, and some values are unreported without explaining the reason. Such missing values also affect the mean rank shown in Figure 1 as “missing results are excluded”. Moreover, the authors declare that “other candidate sets follow their corresponding ranking protocols.” Which protocols, exactly? Are all methods evaluated on the same splits? Appendix B also states that “For TGB-Seq, we retain the released split assignments. Final event proportions can differ from 70%/15%/15% after preprocessing.” How much do they differ? Then they also claim there that “For the neural baselines evaluated in our experiments, we use the best hyperparameter configurations provided by TGB-Seq and CRAFT (Yi et al., 2025b;a).” Which experiments do the authors rerun, and why do they choose not to rerun the main text baselines with a unified protocol, also filling the gaps?
  • The title “Why do neural models fall short” is too broad, the comparison is only performed against CRAFT (and just on two datasets), the conclusions only correlate the performance gap to path counts. Furthermore, there is no analysis on what temporal or topological structure CRAFT actually captures, or why CRAFT outperforms PPR in some datasets like Yelp.
  • All the PPR experiments are run on symmetrized networks, while it is unclear whether the other baselines are evaluated on symmetrized networks as well. Does PPR retain its predictive performance when edge direction is preserved?
Questions for authors
  • Which baseline results are taken from Yi et al 2025 and which are rerun bu the authors?
  • What are the actual split fractions, and which pre-processing steps alter them exactly?
  • Do the results hold when the edge direction is preserved, and do the baselines against the method is compared to preserve such directionality?
5 comments
AuthorsOpenReview ↗

Response to Reviewer avBp (Part 1/2)

We thank the reviewer for the detailed feedback on our experimental setup and structural analysis. Below, we address each point and have updated the revised manuscript accordingly.

W1: Training-Free Scoring vs. Hyperparameter Selection

We agree that the abstract should make the role of hyperparameter selection clearer. The revised abstract states that PPR has no learnable parameters and requires hyperparameter tuning. Section 4.1 explains that we select the hyperparameters for each dataset using its validation set.


W2 & W3: Cycle Closure Insights and Network Distance Scale

Our point in the introduction concerns how early short cycle motifs accumulate during graph evolution. At the same number of distinct edges, the observed four- and six-cycle counts exceed the expectation under a random ordering of the same edges at every measured intermediate snapshot across the seven datasets examined (Figures 9 and 10). Since each such cycle forms when a new edge closes an existing path, this pattern led us to ask whether those paths help distinguish future interaction targets from negative candidates. On GoogleLocal, for example, three-step simple paths reach 62.6% of positive destinations, compared with 5.4% of negative candidates (Figure 7). We have clarified this distinction in the introduction.

On GoogleLocal, sources and candidate destinations lie in opposite partitions, so only odd-length walks can connect them. Moreover, before testing, GoogleLocal has the highest mean shortest-path length among the datasets studied, at 6.41 hops in its largest connected component (6.34 in the final graph). The diameter of this component is 19 in both snapshots. Nodes in this sparsely connected graph are therefore typically several hops apart. In this setting, five-hop paths can provide useful structural evidence. Figure 3 shows that some new interactions occur between nodes whose shortest-path distance was exactly five before the interaction. For those pairs, five steps are the first opportunity for PPR to propagate a signal from the source to the destination.

The tables report exact mean shortest-path lengths and diameters, in hops, within the largest connected component of each undirected, unweighted interaction graph. The first snapshot includes interactions strictly before the first test timestamp, and the final snapshot includes all interactions. Coverage is the percentage of nodes in each snapshot that belong to its largest connected component. Table 9 in Appendix C reports the distances and diameters before testing.

Unseen-dominant datasets

MetricGoogleLocalYelpTaobaoYouTubeFlickrWikiLinktgbl-review
Mean distance before testing6.414.925.043.464.303.194.74
Diameter before testing1912141222812
Coverage before testing (%)99.923899.996799.984099.755793.104699.999699.9597
Final mean distance6.344.854.923.424.233.144.66
Final diameter1912141222810
Final coverage (%)99.923899.997999.989699.776493.4916100.000099.9997

Seen-dominant datasets

MetricWikipediaRedditLastFMUCIFlightstgbl-cointgbl-flight
Mean distance before testing4.403.652.433.063.203.332.73
Diameter before testing1286781110
Coverage before testing (%)98.977399.9635100.000099.884699.642999.950499.8317
Final mean distance4.303.612.423.063.163.282.71
Final diameter1186881110
Final coverage (%)99.284799.9636100.000099.684099.711499.952799.8402

(Continued in Part 2/2 below.)

(Continued from Part 1/2 above.)

W4, W5, Q1 & Q2: Missing Results, Evaluation Protocols, and Dataset Splits

Regarding baseline sources and protocols, the neural baseline scores in Tables 1 and 2 come from Yi et al. (2025a) [2]. A dash indicates that a run exceeded 24 hours per training epoch or 32 GB of GPU memory. We ran both PPR variants in the main comparison, along with the heuristic baselines (Table 14), negative-sampling evaluations (Tables 15 and 16), and efficiency measurements (Appendix B.2). In the main comparison, both PPR variants follow the exact same splits, test candidate sets, and MRR metric as the reported baselines: we use the official test candidates for TGB [1] and TGB-Seq [3], and 100 randomly sampled negative destinations per test query for the five classic datasets [2].

Regarding dataset splits, the five classic and three TGB datasets follow the standard 70%/15%/15% chronological splits (within 0.6% on Flights and 0.05% on TGB due to timestamp-aligned cutoffs). For TGB-Seq, we retain the released splits [3], which apply 70%/15%/15% chronological cutoffs first and then remove validation and test events involving nodes absent from the filtered training graph:

MetricGoogleLocalYelpTaobaoYouTubeFlickrWikiLink
Train (%)94.1986.1674.1683.0479.4480.89
Validation (%)3.538.6213.089.8812.1210.11
Test (%)2.285.2212.767.088.449.00

Regarding Figure 1, each method's rank is averaged over the datasets where it has a reported score. Recomputing mean ranks on the nine datasets with complete results for all methods preserves the top-three order: Time-decay PPR (1.56), CRAFT(-R) (2.67), and Window-based PPR (3.22).


W6: Scope of the Neural Baseline Comparison

In Section 5.2, we focus on CRAFT because it is the strongest neural baseline on most datasets in Tables 1 and 2. We chose GoogleLocal and YouTube as case studies because three-hop paths distinguish positive from negative candidates on GoogleLocal, while two-hop paths do so on YouTube (Figure 7). We then compare CRAFT and PPR across query groups with strong, medium, weak, or no three-hop support (Figure 4 and Table 11). Although PPR trails learned models on some datasets, our goal is not to propose a universal replacement, but to use a simple classical baseline to assess how well current models exploit historical topology. In future work, we will explore learning the time-decay scale and propagation-depth weights across datasets.


W7 & Q3: Edge Directionality and Fair Comparison

The baselines in Tables 1 and 2 can use historical interactions at both endpoints when updating node memories or retrieving recent neighbors. PPR likewise traverses historical edges bidirectionally while retaining the query's source and destination roles. This is essential on bipartite graphs, where walks restricted to directed user-to-item edges stop after one hop.

We also examine asymmetric direction weights via Aβ=βA+(1−β)A⊤A_\beta=\beta A+(1-\beta)A^\top before row normalization, where AA is the weighted directed adjacency matrix. On bipartite datasets, all recorded edges point from the source partition to the destination partition, so each row of AβA_\beta receives entries from only AA or only A⊤A^\top. For any 0<β<10<\beta<1, the factor cancels during row normalization, yielding the exact same transition matrix as β=0.5\beta=0.5.

On the seven non-bipartite datasets, we evaluate Time-decay PPR with the main-table configurations and test candidates fixed. While following only outgoing edges (β=1\beta=1) discards reverse-edge connectivity, retaining both directions with asymmetric weights (β∈{0.1,0.2,…,0.9}\beta\in\{0.1,0.2,\ldots,0.9\}) preserves directional information and consistently improves over the undirected graph across all seven datasets (test MRR ×100\times 100):

DatasetUndirectedDirected (β=1\beta=1)Directional mix AβA_\beta
UCI78.8067.5379.24 (β=0.1\beta=0.1)
Flights86.1585.8486.32 (β=0.8\beta=0.8)
YouTube70.5646.5471.03 (β=0.7\beta=0.7)
Flickr71.9366.6872.05 (β=0.7\beta=0.7)
WikiLink86.1672.2986.23 (β=0.6\beta=0.6)
tgbl-coin81.2980.2581.59 (β=0.9\beta=0.9)
tgbl-flight89.4589.4289.61 (β=0.8\beta=0.8)

References

[1] Huang et al. (2023). Temporal Graph Benchmark for Machine Learning on Temporal Graphs. NeurIPS.

[2] Yi et al. (2025a). Future Link Prediction Without Memory or Aggregation. NeurIPS.

[3] Yi et al. (2025b). TGB-Seq Benchmark: Challenging Temporal GNNs with Complex Sequential Dynamics. ICLR.

Reviewer_avBpOpenReview ↗

Thanks for the clarifications, a few remaining points

I thank the authors for their response, which addresses most of my concerns and questions. I therefore confirm my score. Some remaining points:

  • I see in the updated abstract (please mark the changes there as well) you specify "modest hyperparameter tuning". Considering that the search covers more than 2,000 configurations (and that evaluation is not exactly cheap), which, for instance, translates in more than 44h on Yelp as reported in the other response, I do not think that the term "modest" is supported
  • It is not clear to me how β\beta is selected for each dataset
  • The authors report network-distance statistics and large network diameters, which directly address my question about structural proximity. Yet, I think my point still stands, as the 5-hop paths are not substantially shorter than the reported average shortest path length in GoogleLocal. Interpreting them as “structural proximity” still seems stretched
  • Section 5.2 "WHY DO NEURAL MODELS FALL SHORT?" is left unchanged, and while a deeper investigation would add value to the article, it is still a brief comparison of PPR and CRAFT based on broad query groups, conducted on just two datasets. IMO, it is still not enough to justify the section title and the conclusions in lines 422-424 “These results suggest that modeling historical interaction sequences does not necessarily ensure effective use of higher-order structural information for link prediction”
Reviewer_WzWkOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper revisits the role of historical graph structure in temporal link prediction. The authors investigate whether classical Personalized PageRank (PPR), combined with sliding-window retention or exponential time decay, can compete with modern temporal graph neural networks without learned temporal representations. Experiments on 14 datasets show that Time-decay PPR ranks first on nine datasets and second on four. The paper further analyzes historical paths, cycle closure, and structural discriminability to explain how multi-hop connectivity can support future link prediction even for previously unseen node pairs.

Critical strengths
  1. The paper addresses a meaningful research problem: how much of the performance achieved by modern temporal link prediction models comes from learned temporal representations, and how much can already be explained by historical graph structure? This question is important for reassessing the contributions of existing methods and establishing stronger classical baselines for future research.

  2. The paper conducts extensive evaluation across 14 datasets, covering both seen-dominant and unseen-dominant interaction scenarios. The authors compare PPR with multiple temporal graph neural networks and classical baselines. The paper further provides additional results for temporal decay, propagation depth, restart probability, historical paths, and alternative negative sampling strategies.

Critical weaknesses
  1. The methodological novelty of the paper is relatively limited. The proposed approach mainly combines existing PPR with conventional temporal decay and sliding-window mechanisms, without introducing a fundamentally new propagation algorithm or theoretical framework. The main contribution lies more in the empirical analysis of existing techniques than in methodological innovation.

  2. The proposed time-decay PPR is quite sensitive to negative candidate set construction.

  • Appendix G.2 evaluates the robustness of PPR by retaining the original positive destinations while changing the negative sampling strategy. As shown in Tables 10 and 11, PPR achieves an MRR of 70.56 on YouTube with the original negative candidate set, but only 14.04 under activity-weighted negative sampling. This performance drop suggests that PPR is highly sensitive to the negative candidate set construction.
  • A further concern is that PPR's performance may get even worse under another negative sampling strategy, where positive and negative candidates have similar historical structural characteristics. The authors should consider evaluating PPR under such settings.
  1. Despite the high computational overhead of the proposed method, the paper lacks measurement results on runtime, inference throughput, and memory consumption.
  • Although PPR requires no training, it still requires maintaining an evolving historical graph and performing multiple sparse matrix propagation steps, which may introduce substantial computational overhead on large graphs. In particular, Algorithm 1 rebuilds the sparse graph topology when new node pairs appear.
  • For hyperparameter selection, PPR considers 12 values of KK, 11 values of α\alpha, 8 values of hh, and 2 aggregation methods, resulting in 2,112 possible configurations per dataset. Evaluating such a large number of configurations on the validation set may require substantial time.
  • The authors should report the computational costs of graph updates, PPR propagation, and hyperparameter selection, and compare them with representative baselines.
  1. There is no comparison between finite-step PPR and converged PPR. The paper selects the best finite-step PPR configuration from a search space of up to 2,112 configurations for each dataset based on validation performance. It remains unclear how much of the reported performance comes from the tuned hyperparameter, rather than the underlying PPR mechanism. The authors should consider comparing finite-step PPR with converged PPR under the same experimental settings.

  2. There is inconsistency in the window-based ablation results. In Table 3, on YouTube, the window-based configuration achieves a validation MRR of 71.21, whereas the full-history configuration achieves 72.11. According to Appendix B.1, the window-based search space includes W=∞W = \infty, which means the full-history configuration is included in the window search space. Since the other parameters are fixed in this ablation, the best window-based configuration should not perform worse than the full-history configuration.

Questions for authors

Please address the weaknesses listed above. In particular, please answer the following questions:

  1. In Table 3, why does the validation-selected window perform worse than the full-history configuration on YouTube, given that the search space includes W=∞W = \infty?
  2. How does finite-step PPR perform compared with converged PPR under the same experimental settings?
  3. Have the authors considered evaluating PPR with negative candidates that have similar historical structural characteristics to the positive candidates?
  4. Could the authors provide runtime, inference throughput, memory consumption, and hyperparameter search costs of the proposed method?
5 comments
AuthorsOpenReview ↗

Response to Reviewer WzWk (Part 1/2)

We thank the reviewer for the thoughtful feedback and constructive questions. Below, we address each point and have updated the revised manuscript accordingly.

W1: Empirical Contribution and Key Insights

We agree that our main contribution lies in empirical analysis rather than proposing a new propagation algorithm. We intentionally keep the PPR formulation simple so that it serves as a clean, controlled probe of how much predictive value already exists in the higher-order structure of historical interactions. This simplicity reveals three concrete insights: (1) even on benchmarks designed to remove repeated-edge shortcuts, Time-decay PPR ranks first on nine of 14 datasets and second on four; (2) incoming interactions close historical multi-hop paths into cycles earlier than under random edge ordering, and these historical paths help distinguish positive from negative candidates; and (3) PPR consistently outperforms strong neural baselines on queries with strong multi-hop support, and simply fusing unweighted 3-hop path counts into fixed neural predictions further improves their test MRR. Together, these findings not only establish a strong baseline for evaluating future methods, but also provide concrete guidance for future model design, motivating architectures that explicitly integrate multi-hop structural priors with learned temporal representations and adaptive decay scales.


W5 & Q1: Window Ablation and Search Space (Table 3)

In the submitted Table 3, the ablation is designed to explicitly contrast a finite sliding-window cutoff (Column 2) with full-history retention without decay (W=∞W=\infty, Column 3) under the fixed aggregation rule, restart probability, and propagation depth of Time-decay PPR. Therefore, Column 2 reports the best configuration among the finite windows evaluated, with a maximum window length of 90 days. Table 12 in Appendix F of the revised manuscript lists the selected windows. On YouTube, the selected 90-day window achieves a validation MRR of 71.21 (×100\times 100), while the separately evaluated full-history setting achieves 72.11 with the same fixed parameters. Appendix B.1 describes the separate hyperparameter search for Window-based PPR in the main results, where full history (W=∞W=\infty) is eligible for selection.

We have clarified this distinction by relabeling the Table 3 columns as “Finite window, no decay” and “Full history, no decay” and listing the finite windows evaluated in the ablation in Appendix F.


W4 & Q2: Finite-Step vs. Converged PPR

We compared finite-step and converged Time-decay PPR across the 12 datasets whose validation-selected configurations use a positive restart probability (α>0\alpha>0). On UCI and tgbl-review, the selected α=0\alpha=0 reduces Eq. (3) to a KK-step walk without restart. Using the same historical graphs, refresh schedules, restart probabilities, and test candidates, we kept the validation-selected depth KK for finite-step PPR and approximated the stationary solution by summing through hop HH, with an ℓ1\ell_1 truncation error bound of (1−α)H+1≤10−8(1-\alpha)^{H+1}\le 10^{-8}. The tables below report test MRR ×100\times 100 and correspond to Table 13 in Appendix F.1 of the revised manuscript.

Unseen-dominant datasets

MethodGoogleLocalYelpTaobaoYouTubeFlickrWikiLink
Finite-step PPR65.8972.2871.8170.5671.9386.16
Converged PPR65.3769.6768.6967.1270.0285.51

Seen-dominant datasets

MethodWikipediaRedditLastFMFlightstgbl-cointgbl-flight
Finite-step PPR89.1789.6146.6686.1581.2989.45
Converged PPR89.1789.6046.4986.1481.2986.22

These results suggest that much of the predictive performance comes from the underlying time-decayed PPR mechanism. Finite-step and converged PPR differ by less than 0.7 MRR points on seven of the twelve datasets, and converged PPR outperforms the strongest reported neural baseline on seven datasets. On the five datasets with larger gaps, selecting a finite depth KK improves test MRR by 1.91–3.44 points while requiring fewer propagation steps. Figures 6 and 12 show a similar pattern on validation for YouTube and Flickr, where increasing the depth beyond the best shallow setting reduces MRR.


AuthorsOpenReview ↗

Response to Reviewer WzWk (Part 2/2)

(Continued from Part 1/2 above.)

W2 & Q3: Sensitivity to Negative Candidate Construction

On YouTube, every evaluated method scores lower under activity-weighted negative sampling than under the original candidate construction. For example, CRAFT drops from 58.92 to 10.83 and TGN from 55.16 to 11.04. Time-decay PPR still ranks first among the evaluated methods, with a score of 14.04 in Table 15 of the revised manuscript (Table 11 in the submission).

To further evaluate PPR against negatives with stronger historical connections to the source, we sample up to 100 distinct destinations per query uniformly from eligible nodes at shortest-path distance one to three in the historical graph. We exclude all positive destinations for the same source and timestamp and fill any remaining slots uniformly from other eligible historical destinations. All methods use the same 100 negatives per query, and the neural baselines retain their original checkpoints. The table reports test MRR ×100\times 100 and corresponds to Table 16 in Appendix G.3.

MethodWikipediaFlightsGoogleLocalYouTubeFlickr
Time-decay PPR88.1784.7919.1768.6263.59
CRAFT / CRAFT-R87.4581.4919.6757.1954.35
TGN80.9460.4618.0462.4639.87
GraphMixer73.5141.368.5355.6234.94
JODIE76.2427.9415.1739.1934.90
DyRep67.8312.7013.6728.0234.79
DyGFormer88.0584.645.5646.7337.09

Time-decay PPR remains competitive with the evaluated neural baselines under three-hop neighborhood negative sampling.


W3 & Q4: Computational Cost, Runtime, and Memory

We measured full-test evaluation time and throughput on five datasets of varying graph sizes, using a single GPU per run and the original test candidates. Time-decay PPR was comparable in efficiency to the fastest baselines we evaluated. Its evaluation time includes one-time indexing and initialization, incremental graph updates, and candidate scoring. Each entry below reports minutes / test queries per second. The runtime and memory results appear in Table 6 in Appendix B.2.

MethodGoogleLocalYouTubeFlickrFlightsYelp
Time-decay PPR0.26 / 2,7990.73 / 5,2921.31 / 7,7510.19 / 24,80528.69 / 600
CRAFT / CRAFT-R0.95 / 7685.70 / 68111.34 / 8964.93 / 97320.90 / 823
TGN3.91 / 18521.97 / 17750.35 / 20220.63 / 233106.94 / 161
GraphMixer7.93 / 9240.74 / 95107.23 / 9554.49 / 88195.58 / 88
JODIE9.30 / 7845.96 / 84119.91 / 8513.13 / 36558.24 / 295
DyGFormer13.83 / 52118.25 / 33311.82 / 33145.68 / 33312.01 / 55
Peak GPU memory (MiB)GoogleLocalYouTubeFlickrFlightsYelp
Time-decay PPR224232201121,001

In our implementation, the one-time indexing allocates the sparse structure upfront, with each pair holding zero weight until its first observed interaction enters the history. Consequently, each refresh only updates the active pair weights and renormalizes the affected rows u∈Ru \in R in place. We have revised Algorithm 1 to describe these incremental updates.

For each combination of a half-life or window length and an aggregation rule, we compute per-hop scores up to the maximum depth and reuse them across restart probabilities and propagation depths. The full grid for each variant covers 2,112 configurations across 16 historical graph settings, with 132 combinations of α\alpha and KK sharing the propagation results for each setting. The table below reports the validation search time for each variant under its respective search grid (Table 7 in Appendix B.2).

Hyperparameter selection timeGoogleLocalYouTubeFlickrFlightsYelp
Time-decay PPR3 h 49 min46 min1 h 13 min11 min44 h 11 min
Window-based PPR19 min32 min1 h 32 min11 min25 h 39 min

We sincerely appreciate your thorough review, which has helped us substantially strengthen the empirical rigor and completeness of our paper. As we have tried our best to conduct all the requested experiments, we hope these new results and clarifications satisfactorily resolve your concerns. If so, we would be grateful if you would consider raising your score, and we remain happy to provide any further clarifications during the discussion period.

AuthorsOpenReview ↗

Gentle Follow-up on Our Response (Reviewer WzWk)

Dear Reviewer WzWk,

Thanks for your time and effort in reviewing our paper. Your comments have been very valuable in improving our work. As the author–reviewer discussion period will end in about 3 days, we kindly ask if you could check our response and let us know whether your concerns have been addressed. Thanks again for your time and help!

Best regards,
The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Closing Summary and Sincere Thanks

Dear Area Chair and Reviewers,

As the discussion period draws to a close, we would like to express our sincere gratitude to all reviewers and the Area Chair for your time, thoughtful feedback, and constructive engagement throughout the review process.

Your insightful comments and follow-up discussions have helped us substantially strengthen both the empirical depth and clarity of our work. We have incorporated our rebuttal clarifications, additional experiments, and textual refinements into the revised manuscript, and we will also make sure to include the newly suggested discussions and comparisons with recent works in the final version, if accepted.

Thank you once again for your valuable guidance and support!

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.