- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The setting is temporal link prediction. The paper proposes a training-free audit that marks individual queries where message-passing models may lack propagated evidence from the source.
The audit covers 2 regimes:
-
Reachability flags queries whose true target is farther than L hops from the source, where L is the number of message-passing layers.
-
Collision flags queries where the target is within L hops but some wrong candidate in the set share the same local topology as the target after L rounds of Weisfeiler–Leman refinement, so they ends up with the same embedding after message passing stage.
The authors back this with formal claims about what structure implies for representations, and with experiments showing a large gap between flagged queries and the rest on four static GNN baselines (GCN, APPNP, GraphSAGE, NBFNet) and on TGN.
Critical strengths
-
Flagged queries constructed using the proposed methodology can effectively identify instances of link-prediction failure in static GNNs.
-
The paper demonstrates that the relationship between flagged queries and link-prediction failure holds irrespective of node popularity, as measured by node degree.
-
The comparison between the message-passing baseline and the non-message-passing baseline (XGBoost) is particularly interesting. The paper narrows down the set of queries for which the non-message-passing baseline outperforms the message-passing baseline.
Critical weaknesses
-
Although the paper’s title concerns temporal link prediction, the applicability of its findings to temporal graph learning remains limited.
-
The paper primarily evaluates static GNNs and includes only one TGNN baseline, TGN, as an empirical stress test. It remains unexplored whether flagged queries can explain link-prediction failures in state-of-the-art TGNNs such as TPNet [1], DyGFormer [2], , CTAN [3], and TNCN [4].
-
The baselines used in the empirical experiments appear outdated. More recent and stronger alternatives to NBFNet include A*Net. For temporal models, the baselines should also include the TGNNs listed above.
[1] Lu, Xiaodong, et al. "Improving temporal link prediction via temporal walk matrix projection." Advances in Neural Information Processing Systems 37 (2024): 141153-141182.
[2] Yu, Le, et al. "Towards better dynamic graph learning: New architecture and unified library." Advances in Neural Information Processing Systems 36 (2023): 67686-67700.
[3] Gravina, Alessio, et al. "Long range propagation on continuous-time dynamic graphs." arXiv preprint arXiv:2406.02740 (2024).
[4] Zhang, Xiaohui, et al. "Efficient neural common neighbor for temporal graph link prediction." arXiv preprint arXiv:2406.07926 (2024).
Questions for authors
-
What is the performance of models such as TPNet and DyGFormer on flagged queries vs. complement?
-
How applicable is this work to discrete temporal graphs (snapshot-based), where the dynamic graph is the graph within a timestamp window rather than the whole historical graph up to the cutoff?
3 comments
I thank the author for their comprehensive rebuttal and additional results on TGNN baselines, which improve the coverage of the paper significantly and strengthen the findings of the paper. In my opinion, the results provided by the authors during the rebuttal should be presented as part of the main paper rather than near the end of the appendix. Thus, I would suggest the author revise the paper to move these results to the camera-ready version. In light of the rebuttal, I updated my score toward acceptance.
Response to Reviewer E8T2 (4/2)
Thank you for reading the additional results and for raising your score. The temporal-model experiments came directly from your question, and we agree with you: they now carry a large part of the paper's argument, so a reader should not have to find them at the end of the appendix.
If the paper is accepted, the camera-ready version will move them into the main text as follows.
- Sec. 5 gets a new subsection on current temporal models. It will hold a compact version of Table 35: the degree-matched gap on flagged queries whose target has a history, with 95% intervals, for DyGFormer, TPNet, CAW, TNCN, CTAN, TGAT and GraphMixer on the four graphs. The full columns (complement, seen and novel MRR, per-seed values) stay in App. Y.
- The mapping from model mechanism to the flag that applies (Table 30) moves into Sec. 4, next to Def. 1. It tells a reader which flag to compute for their own model, so it belongs with the definition.
- The time-respecting flag of App. X and the chain split for memory models (TGN, CTAN and TNCN, Table 33) will be summarized in Sec. 5 in one paragraph, with the full tables kept in the appendix.
- The introduction and conclusion will state the temporal results directly instead of pointing to the appendix.
To make room, we will move part of the static-encoder controls in Sec. 5 to the appendix. No result is dropped, and every moved table keeps a pointer from the main text.
Thank you again for the detailed review and for the follow-up.
Response to Reviewer E8T2 (3/2)
Additional results: CAW, TNCN, CTAN and TGAT on the flagged set
We trained four more temporal models under the protocol of our first reply (Table 1 query sets, graph-only inputs, three seeds, at most 12 epochs with early stopping on the history tail, tie-aware MRR). CAW (walk length 1, the default) and TGAT come from DyGLib. TNCN and CTAN come from their official code, TNCN with its repository defaults and CTAN with one fixed configuration from its authors' grid, without a search. Degree-matched gap on flagged queries whose target has a history, with 95% CI:
Read by mechanism, as in Table 30:
Seeds agree except CTAN on Wikipedia (complement 0.408, 0.430, 0.195) and TNCN on MathOverflow (0.236–0.389); App. Y notes both.
Change in the paper: Table 35 (App. Y) adds the four models, Table 33 adds the chain split for CTAN and TNCN, and Table 30 now lists TGAT with GraphMixer and adds CAW.