- 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 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 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 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
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 be the observed network and the feature to be preserved. The reference model assigns equal probability to every realization satisfying .
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 and sample uniformly from its possible orderings. We compare the observed and reference graphs after the same number of distinct edges has been added. In Eq. (6), is the number of simple -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 be the snapshot's unweighted adjacency matrix. The triangle and four-cycle counts are
Here counts common neighbors. The factor accounts for the three starting vertices and two traversal directions of a triangle. The factor accounts for the two pairs of opposite vertices of a four-cycle.
For six-cycles on general undirected graphs, we compute
The first sum equals and counts all closed walks of length six. We accumulate it using blockwise adjacency multiplications. The correction sums over the edge patterns used by walks that revisit vertices. Here counts copies of as subgraphs, and 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 .
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.
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
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 t be the query time, τ<t the interaction time, and Δt=t−τ the age of the interaction. The sliding-window indicator is I[Δt≤W]=1 if 0<Δt≤W, and 0 if Δt>W. Thus, the window retains interactions with t−W≤τ<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 B be the number of queries in a scoring batch and q 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≤B distinct sources, scoring with a fixed PPR configuration costs O(K[(n+m)U+Bq]), where K is the propagation depth, n is the number of nodes, and m is the number of distinct undirected edges. At each step, the implementation performs sparse propagation, then gathers the Bq 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(NlogN+∑j=1J[bjlog(bj+1)+Dj]+K[(n+m)∑ℓUℓ+q∑ℓBℓ]).
Here, N is the number of indexed interactions, J is the number of graph refreshes, bj is the number of events processed at refresh j, and Dj counts the stored entries visited when renormalizing the affected rows. For Window-based PPR, bj includes both arriving and expiring events. The index ℓ 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.
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.)