acceptodds
Under review as a conference paper at ICLR 2027

A Structural Audit of Missing Propagated Evidence in Temporal Link Prediction

Abstract

Local message-passing graph neural networks are the default tool for temporal link prediction, the task of forecasting which node a source will interact with next. Such a model can use source information in scoring a candidate only if that information reaches the candidate's representation, which raises a question rarely asked before training: how much of a benchmark's evaluation set carries source-to-target propagated evidence at all? Expressiveness results describe what a model class can represent once the right input is present, not whether a given query supplies it, and post-hoc structural analyses correlate graph statistics with accuracy over whole datasets, after the cost of training has been paid. We introduce a training-free audit, computed from the history graph by breadth-first reachability and Weisfeiler–Leman refinement, that flags queries whose target lies outside the source's hop ball and, for anonymous models, queries whose target is indistinguishable from a reachable distractor. We prove what the flag says and what it does not: the target representation of a flagged query carries nothing propagated from the source, yet the flag cannot bound the accuracy of the class, because free node embeddings achieve a perfect ranking on any pairwise-consistent query set however many queries are flagged. The audit therefore measures available evidence rather than capacity, and what the missing evidence costs a trained model is an empirical question. On featured graphs, every architecture we train, from local aggregation and global mixing to source-conditioned path reasoning and temporal memory, collapses toward random on flagged queries while performing well on the complement, and the collapse survives matching on degree, depth and width. On feature-free graphs the same gap is largely degree composition; we state the conditions under which the audit is informative, test them forward on held-out graphs, and isolate the one condition under which a non-message-passing baseline recovers the flagged queries and a change of model class is warranted. A graded hop score turns the flag into a pre-training rule for where source conditioning pays off and where it does not.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
temporal link prediction, graph neural networks, message passing, receptive field, Weisfeiler-Leman, training-free diagnostic, benchmark analysis, evaluation methodology

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_E8T2OpenReview ↗
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
AuthorsOpenReview ↗

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:

modelCollegeMsgBitcoin-OTCWikipediaMathOverflow
CAW−0.337 [−0.357, −0.316]−0.031 [−0.050, −0.013]−0.611 [−0.664, −0.561]−0.066 [−0.092, −0.046]
TNCN−0.046 [−0.058, −0.034]−0.070 [−0.093, −0.049]−0.535 [−0.580, −0.489]−0.052 [−0.066, −0.038]
CTAN+0.002 [−0.013, +0.019]−0.004 [−0.021, +0.016]−0.187 [−0.213, −0.161]+0.016 [−0.003, +0.033]
TGAT−0.001 [−0.007, +0.003]+0.008 [+0.001, +0.016]−0.128 [−0.148, −0.110]+0.004 [−0.003, +0.013]

Read by mechanism, as in Table 30:

  • Pair evidence within two static hops. CAW compares one-step walks from the two endpoints, so the paper's L=2 flag is exactly its flag, as for DyGFormer. It falls on every graph, with every interval below zero. TNCN's common-neighbour features also stay within two hops, and it falls on every graph too. Its memory reaches further, so for TNCN this is consistent with the audit rather than implied by it.
  • Memory along chains of any length. For CTAN, as for TGN, the static flag makes no claim, and after degree matching CTAN is level with its complement except on Wikipedia. The flag that applies is the any-length time-respecting flag of App. X, and it does separate CTAN's flagged rows: rows without a chain score below degree-matched rows with one on all four graphs (−0.109, −0.089, −0.022, −0.055; interval excluding zero on three; new rows in Table 33).
  • No pair evidence. Here we correct our earlier mapping. We had put TGAT under the bounded time-respecting flag, but DyGLib's TGAT encodes each endpoint separately, so with graph-only inputs it carries no pair evidence, like GraphMixer. As for GraphMixer, the flag has nothing to separate: TGAT shows no gap on three graphs, and its complement is weak (0.08–0.22).

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.

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.

AuthorsOpenReview ↗

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.

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

This paper introduces a structural audit for temporal link prediction that is computed before training, applies per query, and requires no training. The starting point is that a depth-L message-passing GNN can propagate information only within L hops. If the true target lies outside the source's L-hop neighborhood, the target representation contains no evidence propagated from the source. The authors also examine WL color collisions under anonymous models. They show that the flag is a diagnostic of available propagated evidence and does not give an MRR upper bound in the class-supremum sense, since free node embeddings can achieve a perfect ranking on any pairwise-consistent query set. Experiments use ten temporal graphs and five encoder classes and report MRR differences between flagged and complement queries. Controls cover target degree, source degree, depth, width, and negative-sampling asymmetry. On the two high-signal graphs, D1 and WIKIPEDIA, all architectures drop sharply on flagged queries. On low-signal graphs, degree composition explains much of the gap. The class-specificity break appears only on the non-redistributable D1 and depends on additional applicability conditions. The authors also give a graded hop score as a pre-training routing signal for the benefit of source conditioning.

Critical strengths
  1. The process is performed before training, applies to each query, and has a clear mechanism. It can be computed from the history graph without training. It directly turns whether the target representation receives evidence propagated from the source into something that can be inspected, and it gives the source-invariance conclusion of Proposition 1. This is more useful for diagnosis than dataset-level correlations or structural attribution performed after training, and it helps assess the query composition of benchmarks.
  2. Theoretical boundaries and empirical honesty. Proposition 2 states explicitly that the hard fraction cannot serve as a class-supremum upper bound. This prevents the flag from being read as an accuracy ceiling. The experiments account for target degree, source degree, depth, width, negative-sampling asymmetry, and degree composition on low-signal graphs. The authors also report limitations directly: D1 is not redistributable, and the class-specific break is not reproduced on public graphs. These points count in favor of the paper in review.
Critical weaknesses
  1. The core class-specificity conclusion relies too heavily on D1, and the baseline comparison is not fully feature-matched. The paper's most important result, that a non-message-passing baseline wins in a concentrated way on flagged queries, holds only on D1. The eight public graphs do not show an equivalent break. On D1, XGBoost uses 46 features, including 4 transductive cross-query features computed from the evaluation candidate batch, while the GNNs use 26 core features. The authors acknowledge in the appendix that the comparison is not feature-matched and that the break depends on these dataset features. This affects how one should interpret the difference between model class and feature interface, and it is the main obstacle to accepting the paper's core claim.
  2. The practical scope and external validity of the audit remain narrow, and the collision clause rarely applies. This clause contributes less than 0.4% of queries on nine of ten graphs. Deployed models usually carry free embedding tables, so the clause has almost no effect on actual architectures. The conclusions rest on the reachability clause. On low-signal graphs, the raw gap is mainly degree composition, and the graded score even reverses on these graphs. The audit is also topological and uses a fixed depth, so it does not model temporal reachability. TGN falls outside the theorem, and sequence models are not trained. The paper is therefore closer to an evaluation-set diagnostic tool with an analysis of applicability conditions than to a general method that can directly guide model selection. The authors acknowledge this limitation, but it reduces the broader impact of the work.
Questions for authors
  1. On D1, if the 4 transductive cross-query features are removed and XGBoost is restricted to the same 26 core features as the GNNs, how much of the concentration ratio and class-specific break on flagged queries remains?
  2. Can the authors perform a truly feature-matched comparison on public graphs, for example by feeding the same covariates through the GNN's readout, or by restricting the non-message-passing baseline to the same information interface as the GNNs?
  3. For time-respecting models such as TGN and DyGFormer, can the authors provide a temporal-reachability version of the audit and report the flag fraction? Would fixed-L topological reachability systematically overestimate the proportion of missing propagated evidence for these models?
  4. On low-signal graphs, the graded score inverts. Can the authors give a pre-training-checkable condition for side-feature availability, rather than relying on post-hoc judgment of whether the graph is suitable for graded routing?
1 comment
AuthorsOpenReview ↗

Response to Reviewer Vsb5 (3/2)

A short correction to our reply on Q3. We listed TGAT among the models that relay along time-respecting chains of bounded length. DyGLib's TGAT encodes each endpoint separately, so with graph-only inputs it carries no pair evidence; in new runs it behaves like GraphMixer, with no gap on three of four graphs. The bounded time-respecting flag applies to TGRank, which propagates a source label. Table 30 is corrected.

The same runs add CAW, TNCN and CTAN (App. Y, Table 35). CAW, whose evidence reaches exactly two static hops, falls on every graph, as does TNCN. The memory model CTAN is level with its complement on three graphs, but on its flagged rows those without a time-respecting chain score below degree-matched rows with one on all four graphs (Table 33), which bears on your question about memory models.

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

The paper proposes a query level diagnostic / audit of the kind of evidence (scoped to structural) available for predicting temporal links. The authors diagnostic tool is to essentially "flag" queries whose target nodes are outside the message passing radius of the chosen source node. The authors then perform diagnostic experiments on 10 graphs and compare GNN based encoders on flagged queries and their complement. They show flagged queries perform substantially worse than their complements. They also show with feature-controlled ablations that performance of link prediction on such flagged queries scales when new features are introduced instead of GNN model architecture tweaks.

Critical strengths

The structural audit proposed is simple to implement and reason about. The diagnostic tool gives an experimenter a way to deep dive into the results and interpret them for e.g. Rather than reporting one aggregate prediction accuracy, distinguish performance where propagated evidence is available from performance where it is absent for the queries in hand,

Critical weaknesses
  1. The paper is not clear on the recommendations for the end practitioner of temporal link prediction from using the diagnostic tool. The paper claim of model class switching is not well supported. As even NBFNet with matched features attains the high score, Sufficient experimental results are not presented to make a stronger and useful claim that this diagnostic tool can be used as an architecture selector. (Also, the paper misses comparisons to other model classes aimed at temporal link prediction like CAW[1], TGRank [2] and other such methods in literature.).

  2. The audit tool makes relies on the reachability flag component, which means the model class assumption is: The target representation is computed through a fixed number of local message-passing rounds on the audited graphs. Like the authors point out this locality assumption is not shared by many SoTA models hence weakens the use of the tool itself. Also relates to point 1) what's the motivation of the intended use for the audit tool ?

Refs [1] Wang, Yanbang, et al. "Inductive representation learning in temporal networks via causal anonymous walks." arXiv preprint arXiv:2101.05974 (2021). [2] Suresh, Susheel, et al. "Expressive and efficient representation learning for ranking links in temporal graphs." Proceedings of the ACM Web Conference 2023. 2023.

Questions for authors
  1. With Table 3’s matched-interface result, what remaining evidence warrants recommending a model-class switch on D1 rather than adding the same features to NBFNet?

  2. What are the scores of deeper models on the fixed set originally flagged at depth two, separating queries that become reachable from those that remain outside the radius? This would materially clarify whether depth fails to recover useful evidence or instead recovers part of the original set while leaving a harder remainder.

4 comments
AuthorsOpenReview ↗

Response to Reviewer nRJk (3/2)

Additional results on W1 and W2: CAW, TGAT and two memory models

We had not trained CAW when we replied. We have now trained CAW and TGAT (DyGLib) and the memory models TNCN and CTAN (official code) on our query sets, under the same protocol as DyGFormer and TPNet (three seeds, graph-only inputs, tie-aware MRR). Flagged and seen vs complement, with the degree-matched gap in brackets:

modelCollegeMsgBitcoin-OTCWikipediaMathOverflow
CAW0.072 vs 0.434 (−0.337)0.149 vs 0.290 (−0.031)0.047 vs 0.820 (−0.611)0.102 vs 0.394 (−0.066)
TNCN0.128 vs 0.214 (−0.046)0.198 vs 0.422 (−0.070)0.047 vs 0.711 (−0.535)0.082 vs 0.301 (−0.052)
CTAN0.213 vs 0.270 (+0.002)0.242 vs 0.416 (−0.004)0.054 vs 0.344 (−0.187)0.177 vs 0.448 (+0.016)
TGAT0.069 vs 0.079 (−0.001)0.096 vs 0.119 (+0.008)0.043 vs 0.219 (−0.128)0.077 vs 0.132 (+0.004)

At the DyGLib default walk length of one, CAW compares one-step walks from both endpoints, so its pair evidence reaches two static hops and the paper's flag is exactly its flag. It falls on every graph, with every interval below zero. After DyGFormer, this is the second predicted case.

On W2, the memory models are where locality fails, and the results show it. After degree matching CTAN is level with its complement on three graphs; the static flag makes no claim about it, as for TGN. What does separate its flagged rows is the any-length time-respecting flag: rows without a chain score below degree-matched rows with one on all four graphs, with the interval excluding zero on three (new rows in Table 33). TNCN falls on all four graphs.

We also need to correct one line of our reply. TGAT does not belong with the bounded-chain models. DyGLib's TGAT encodes each endpoint separately, so with graph-only inputs it has no pair evidence, and it behaves like GraphMixer: no gap on three graphs and a weak complement. The bounded time-respecting flag applies to TGRank, which propagates a source label. Table 30 is corrected, and App. Y (Table 35) has the full numbers with intervals.

AuthorsOpenReview ↗

Response to Reviewer nRJk (4/2)

You asked what the audit is for once the model-class claim is withdrawn. The use we can support with our own runs is that it changes which model a practitioner would pick on some graphs, and not on others.

We took the ten models trained under one protocol (GCN, NBFNet, TGN, DyGFormer, TPNet, GraphMixer, CAW, TGAT, TNCN, CTAN; three seeds; the Table 1 query sets of the four public graphs) and compared the leaderboard by aggregate MRR with the leaderboard on each part of the audit split (new Tables 35a and 35b, App. Y). A rank flip counts only when a paired query bootstrap puts both differences away from zero.

Where nothing changes. On CollegeMsg and Wikipedia the aggregate ranking, the complement ranking and the ranking without novel-target rows are identical (Kendall tau 1.00). TPNet is first by aggregate on all four graphs and stays first once novel targets are removed.

Novel targets reorder the leaderboard where they are frequent. On Bitcoin-OTC (33% of queries have a target with no history) and MathOverflow (29%), removing those rows gives 6 and 9 confirmed flips. GraphMixer is second by aggregate on both graphs and fifth without them, with 57% and 52% of its aggregate MRR coming from novel rows. TGN is third on MathOverflow and ninth without them (63%). No negative candidate is ever a new node, so ranking unseen candidates first scores well on these rows without using the source.

Flagged queries whose target has a history have their own leaderboard. Kendall tau with the aggregate order is 0.07, 0.64, 0.11 and 0.56 (CollegeMsg, Bitcoin-OTC, Wikipedia, MathOverflow). CTAN is first on this part on CollegeMsg, Bitcoin-OTC and MathOverflow, and sixth, third and fourth by aggregate. On CollegeMsg TPNet leads CTAN by 0.178 [0.167, 0.189] in aggregate and trails it by 0.083 [0.068, 0.097] on flagged-seen queries, which fits Table 30: CTAN's memory relays along time-respecting chains of any length, so the static flag does not remove its evidence.

In practice: before training, compute for the queries you care about the flag at each candidate model's reach and whether the target has a history; this needs one search per query and no model. Then report complement, flagged-seen and flagged-novel MRR instead of the aggregate alone. If many of your queries have novel targets, the aggregate rewards novelty detection. If many are flagged with a known target, choose on that column, where the order can differ from the aggregate one. If both parts are small, as on Wikipedia (3% and 6%), the aggregate leaderboard is a fair guide.

A correction on TGRank (W1). We wrote that TGRank propagates a source label along time-respecting edges, so that the bounded time-respecting flag applies to it. Its official code does something else. It samples a subgraph around both endpoints with the query time as the cut-off at every hop, and its three propagation layers pass messages only along edge direction, with event time as an edge feature. Its flag is therefore static and directed: no directed path of length at most three from the source inside that subgraph. With the official sampler it flags 0.323, 0.436, 0.237 and 0.521 of the queries, against 0.356, 0.548, 0.089 and 0.364 for the paper's flag. On the bipartite Wikipedia it reaches only pages the source has already edited. Table 30 and App. V are corrected; this also replaces the same sentence in our replies to E8T2 and Vsb5. We have since trained TGRank with its official code under the same protocol (three seeds, graph-only inputs, Table 1 query sets, official defaults; its dropout stays on at evaluation, as in its code). Read at its own reach, the flag separates TGRank's queries on all four graphs: on flagged queries whose target has a history it falls below the queries it reaches, after degree matching, by −0.054 [−0.059, −0.048], −0.013 [−0.023, −0.001], −0.049 [−0.051, −0.047] and −0.019 [−0.022, −0.016] (CollegeMsg, Bitcoin-OTC, Wikipedia, MathOverflow). These gaps are larger than on the paper's flag (−0.039, −0.007, −0.044, +0.000), which is why the flag should be computed at each model's own reach. Two caveats, both in App. Y: within the paper's flagged set, the rows TGRank reaches score higher only on CollegeMsg, and TGRank is weak in this setting (complement MRR 0.07–0.15, still improving at the 12-epoch cap on MathOverflow), so the margins are small.

Really appreciate all the additional experiments performed by the authors in the rebuttal period. And thanks for the rebuttal for some of the points raised in the reviews. Given the significant changes needed to address all the weaknesses, especially some of the motivational recommendations of the paper, and further experiments to support the revision, IMHO I wish to retain the score I originally proposed. I feel the paper can better integrate the commentary during the rebuttal in the next version of the work to be more cohesive and easy to understand for the end practitioner.

Thanks again for the discussion during the rebuttal period.

AuthorsOpenReview ↗

Response to Reviewer nRJk (5/2)

Thank you for reading all of the additional results and for the frank assessment. We agree that the rebuttal material has to be part of the paper's argument rather than an appendix a reader must assemble. Concretely, the next version is organized around the question you asked: what a practitioner does with the audit.

  • Introduction and abstract. The paper opens with the practical use. Computed before any training, the audit tells a reader when the aggregate leaderboard of temporal link prediction can be trusted, and which column to choose a model on when it cannot. The earlier model-class recommendation is gone. In its place is the narrower statement that Table 3 supports: a flagged query lacks propagated evidence, so it needs non-propagation features or source conditioning.
  • Sec. 4. The flag definition sits next to the mechanism-to-flag mapping (Table 30, with the corrected TGRank row), so a reader can compute the right flag for their own model.
  • Sec. 5. A compact version of the leaderboard comparison (Tables 35a and 35b) and of the temporal-model results (Table 35) moves into the main text, followed by the three-step procedure from our last reply: compute the flag at the model's reach, check whether the target has a history, and report complement, flagged-seen and flagged-novel MRR.
  • Appendix. The static-encoder controls move there to make room. Every moved table keeps a pointer from the main text.

The same plan is stated in our reply to E8T2, so the three threads lead to one version of the paper. Thank you again for the careful review and the discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.