acceptodds
Under review as a conference paper at ICLR 2027

The Structural Gain in Temporal Link Prediction Is Mostly Memory and Recency

Abstract

Temporal graph networks increasingly encode neighborhood structure, such as neighbors that co-occur in two nodes' recent histories, shared neighbors inside a sliding window, or temporal walks. The premise is that structure reveals who will interact next. We show that a structural feature computed from an event history also carries two other kinds of information: memory, whether the pair has ever interacted, and recency, when its endpoints were last active. The memory part is provable. Distance is the first depth at which two neighborhoods overlap, and the overlap vector is supported on the three depths around it, so a non-zero overlap at three hops certifies that a pair has never met. We measure the three kinds of information on 14 benchmarks under the random and historical negative protocols of DyGLib. Our test admits a structural feature only after memory, and then only after recency, and checks the result against a shuffled control and a second scorer. Under historical negatives, neighborhood overlap, the classical heuristics and DyGFormer's co-occurrence encoding keep a gain above 0.01 AP after memory on 0, 1 and 9 of the 14 benchmarks, and after recency on 0, 0 and 0. Across four structural signals, a gain remains in 14 of 112 benchmark-protocol cells, with median +0.017. Inside a trained model the picture is the same. Nine numbers about the pair's own history, with no neighbor of either node, replace DyGFormer's co-occurrence channel on 10 of 13 benchmarks, and the two exceptions are the two benchmarks on which the test found structure surviving. Structure survives where memory cannot answer: where no pair repeats (on a repeat-free benchmark overlap adds +0.121 and keeps +0.120 after recency), where every pair repeats (a dense trade network), and in the cold part of ordinary benchmarks. Gating a structural feature to the regime the test identifies keeps a median of 98% of its gain on 66% of queries. We release the test as structaudit, together with measurements of three construction mistakes that silently change its answer.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
temporal graphs, link prediction, evaluation, graph structure, benchmarks

Reviews

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

The paper studies temporal graph link prediction. The authors argue that the structural components in existing TGL models, and their performance gains attributed to them, are largely explained by two simpler signals: memory (whether this edge or event has appeared in the history) and recency (how long ago the endpoints last interacted).

To test this hypothesis, the paper separates memory, recency, and structure and measures how much each component contributes under different settings: logistic regression and gradient-boosted trees as scorers, and evaluation with the TGL models DyGFormer, TGN, and Hawkeye.

Critical strengths
  • The paper identifies construction mistakes (Section 2) and quantifies their impact (Table 1). That contribution should be especially useful to the temporal graph learning community.
Critical weaknesses
  • The evaluation protocol used in this paper, in which each positive edge is scored against a single negative edge with AP reported, is outdated and no longer the literature standard. As highlighted in TGB [3], this strategy tends to produce negatives that are easy to predict given the structure and sparsity of real-world networks [1], leading to inflated performance estimates [2]. This evaluation limitation significantly affects how broadly the paper’s insights apply.

  • Writing issues negtively affect readability:

    • The definitions of Δalone\Delta_{\mathrm{alone}}, Δmemory\Delta_{\mathrm{memory}}, and Δrecency\Delta_{\mathrm{recency}} (lines 120–123) use PP, RR, and SS without clearly defining them.
    • The legend of Figure 1 is confusing and not informative enough. Under the legend, labels such as “added to popularity + pair count” and “added after memory (incl. whether they ever met)” do not state which component or feature is being added. With vertical space available, the figure could be more explicit so readers do not have to guess.
    • At lines 305–306, the authors name four variants: the published co-occurrence channel, the no structural channel, the pair-time channel alone, and both, but Table 3 uses different names, which is confusing (for example, what is the “none” variant?).
    • The paper’s structure feels disconnected and lacks a clear narrative flow. For example, some sections move straight into methodology without stating what the section is for or how it connects to the previous one.
  • The benefit of evaluating with logistic regression and gradient-boosted trees is not clear to me, since these scorers may not reflect whether the results transfer to actual TGL models. TGL models may use different readouts or transform structural features in ways that diverge from logistic regression and gradient-boosted trees.

  • The abstract and title suggest that structural gain in temporal link prediction is mostly memory and recency, but I find this overclaimed. Lines 261–262 and Section 6 describe cases where gains from structural additions after memory and recency remain considerable, especially on repeat-free datasets in TGB-Seq.

  • The introduction lists many TGL baselines, but the empirical results cover only a limited set: DyGFormer, Hawkeye, and TGN. Generalizability of the findings is therefore limited by baseline coverage. Extending the discussion in Section 4 to include additional baselines, such as TPNet, TNCN, or CAWN, besides DyGFormer and TGN, would improve the generalizability of the paper.

  • The main takeaway I draw is that different components matter depending on dataset characteristics (e.g., repeated-edge frequency). The paper calls this out and analyzes it, but the finding feels incremental and somewhat trivial.

  • The only conclusion I can draw is that different components matter depending on dataset characteristics (e.g., repeated-edge frequency). The paper calls this out and analyzes it, but the finding feels incremental and somewhat trivial.


[1] A.-L. Barabási. Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1987):20120375, 2013

[2] F. Poursafaei, S. Huang, K. Pelrine, and R. Rabbany. Towards better evaluation for dynamic link prediction. Advances in Neural Information Processing Systems, 35:32928–32941, 2022.

[3] Huang, S., Poursafaei, F., Danovitch, J., Fey, M., Hu, W., Rossi, E., Leskovec, J., Bronstein, M., Rabusseau, G. and Rabbany, R., 2023. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 36, pp.2056-2073.

Questions for authors
  • Line 099 states that a batch sees only events strictly earlier than its first event. Suppose the evaluation set contains multiple batches. For batches after the first batch, does the model also see events from earlier batches?

  • Lines 108–109 state that “structure reads the neighbors of the endpoints, in three blocks.” Can the authors clarify whether structural information is taken from temporal neighbors (e.g., recent interaction history) or only from neighbors within the same timestamp/snapshot?

  • Table 2 reports how many cases structural features help after memory and after recency. To assess more fully whether structural features are mostly memory and recency, could the authors also report how many structural features still help after both memory and recency (i.e., the structural residual)?

1 comment

We thank the reviewer for the detailed comments. We answer the three weaknesses and the three questions together, with results measured since submission.

W1 / Q1. Why separate memory and recency from structure, if their overlap is expected. We agree that some overlap is expected. Our contribution is its size and its consequence. The size: under historical negatives, DyGFormer's co-occurrence encoding keeps a gain above 0.01 AP after memory and recency on 0 of 14 benchmarks. The consequence is practical, because the three sources have very different costs. The memory and recency of a pair are a table lookup, while a structural encoder must read neighborhoods. Inside the trained model, nine numbers about the pair's own history replace the co-occurrence channel on 11 of 14 benchmarks (extended since submission to 14 benchmarks, 3 seeds). The channel makes each batch 3.4 to 6.9 times slower, and the nine numbers at most 12% slower. A designer who reads the usual ablation concludes that neighborhoods are needed. The decomposition shows where they are not, and the test says in advance where they are: repeat-free streams and the cold part of a benchmark. We separate the sources by what a feature reads (the pair's own events, their timestamps, or other nodes' events). This is an operational definition, not a claim that the sources are independent, and we will say so explicitly.

W2 / Q2. Hand-crafted blocks; degree as a structural statistic. The memory block is deliberately minimal. It reads only the events of the pair and of the candidate; the candidate's degree and event count are the popularity statistics used by simple baselines such as EdgeBank, and they read no other node's neighborhood. We accept that the boundary is a choice, so we measured how much the conclusions depend on it. (i) Order-free attribution. Under Shapley values, the structural signals keep 34% to 41% of the gain they show when entering first, so about three fifths of that gain is shared with memory and recency. We will report this next to the sequential numbers and soften our "four fifths" sentence. (ii) Moving the "never met" indicator from memory to structure changes the historical-protocol residual from +0.000 to a median of +0.058 AP. We will report both assignments. (iii) Threshold. At 0.005, 0.01, 0.02 and 0.03 AP, 21, 14, 6 and 3 of 112 cells survive. (iv) A second scorer and a shuffled-feature control are already in the paper. We have not tested richer definitions of memory or recency, such as decayed counts. Richer blocks can only absorb more, so the current blocks give an upper estimate of what structure adds.

W3 / Q3. Generalization beyond DyGFormer. Since submission we ran the trained-model experiment on four backbones, 14 benchmarks and 3 seeds. The pair-time channel improves TGN, GraphMixer and TCL on 13, 12 and 13 of 14 benchmarks (median +0.011, +0.030 and +0.044 AP, up to +0.199). We have not run CAWN, TPNet or TNCN, and the revision will state that the model-level claim covers DyGFormer's co-occurrence channel and these three backbones only. At the feature level, the test already covers four structural signals, including a published cohesion channel. We also agree that the conclusion depends on data and protocol, and that is the claim we intend. We will scope the title and abstract to standard benchmarks. The paper names the regimes where structure survives, for example GoogleLocal, where overlap keeps +0.120 AP after recency over 5 seeds (standard deviation 0.0004).

We hope the added backbones, the order-free attribution and the narrower claim address the soundness concerns, and we would be grateful if the reviewer would reconsider the rating in their light.

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

This paper investigates whether the performance improvements attributed to structural encoding in temporal link prediction primarily arise from structural information or from historical interaction memory and recency. The authors propose structaudit, an evaluation framework that progressively controls for memory and recency features to measure the independent predictive contribution of structural information. The framework is evaluated on 14 temporal graph benchmarks under random and historical negative sampling protocols, covering four types of structural signals. The experimental results suggest that most apparent structural gains diminish substantially after accounting for memory and recency.

Critical strengths
  1. The paper investigates the actual contribution of structural information in temporal link prediction. By distinguishing structural information from historical interaction memory and recency, the study provides a perspective for reassessing the effectiveness of structural encoding mechanisms in existing temporal graph learning models.
  2. The experimental evaluation is relatively comprehensive, covering 14 temporal graph benchmarks, multiple structural encoding mechanisms, and different negative sampling protocols. The authors also incorporate shuffled-feature controls and alternative scoring models to examine the robustness of their findings, and further validate their observations through experiments with trained temporal graph models.
  3. The paper investigates the specific scenarios in which structural information remains beneficial, including repeat-free interactions, memory-saturated networks, and cold-pair prediction. These analyses provide insights into when structural modeling may be necessary.
Critical weaknesses
  1. Insufficient justification of the core research motivation. The paper aims to demonstrate that the predictive gains attributed to structural encodings in temporal link prediction largely arise from memory and recency. However, the investigated structural encodings inherently incorporate historical interaction and temporal information by design. Specifically, DyGFormer's neighbor co-occurrence encoding explicitly operates on historical interaction sequences, while Hawkeye's cohesion features are computed within temporal windows. Therefore, the overlap between structural information and memory/recency is not necessarily surprising. The paper does not sufficiently justify why these information sources should be treated as conceptually separate.
  2. Heuristic decomposition of information sources. The proposed framework defines memory and recency through a limited set of handcrafted statistics. The choice of feature set is not properly justified, and the distinction between memory, recency and structure is not always clear, as some memory features, such as node degree, are themselves structural statistics. The incremental predictive gains measured after controlling these features therefore do not necessarily establish a rigorous attribution of structural modeling contributions.
  3. Limited generalizability of the empirical findings. Although the paper evaluates multiple structural signals across 14 benchmarks, the scope of trained-model validation is primarily limited to DyGFormer. Other representative temporal graph models with more sophisticated structural modeling mechanisms, such as CAWN and TPNet, are not evaluated. Moreover, the authors' own analysis suggests that the contribution of structural information is highly dependent on the characteristics of datasets and evaluation protocols. Therefore, the current experimental evidence does not sufficiently support the broad conclusion that structural gains in temporal link prediction are mostly attributable to memory and recency.
Questions for authors
  1. Could authors further clarify why memory and recency should be considered conceptually separate from temporal structural information, and what additional insights the proposed decomposition provides beyond the expected overlap among these information sources?
  2. Could authors clarify whether the handcrafted features used for analysis sufficiently characterize memory and recency in temporal graph learning? How sensitive are the findings to alternative feature definitions?
  3. Given that the trained-model validation primarily focuses on DyGFormer, could the authors clarify to what extent the conclusions generalize to other temporal graph models with different structural encoding mechanisms?
1 comment

We thank the reviewer for the detailed comments. We answer the three weaknesses and the three questions together, with results measured since submission.

W1 / Q1. Why separate memory and recency from structure, if their overlap is expected. We agree that some overlap is expected. Our contribution is its size and its consequence. The size: under historical negatives, DyGFormer's co-occurrence encoding keeps a gain above 0.01 AP after memory and recency on 0 of 14 benchmarks. The consequence is practical, because the three sources have very different costs. The memory and recency of a pair are a table lookup, while a structural encoder must read neighborhoods. Inside the trained model, nine numbers about the pair's own history replace the co-occurrence channel on 11 of 14 benchmarks (extended since submission to 14 benchmarks, 3 seeds). The channel makes each batch 3.4 to 6.9 times slower, and the nine numbers at most 12% slower. A designer who reads the usual ablation concludes that neighborhoods are needed. The decomposition shows where they are not, and the test says in advance where they are: repeat-free streams and the cold part of a benchmark. We separate the sources by what a feature reads (the pair's own events, their timestamps, or other nodes' events). This is an operational definition, not a claim that the sources are independent, and we will say so explicitly.

W2 / Q2. Hand-crafted blocks; degree as a structural statistic. The memory block is deliberately minimal. It reads only the events of the pair and of the candidate; the candidate's degree and event count are the popularity statistics used by simple baselines such as EdgeBank, and they read no other node's neighborhood. We accept that the boundary is a choice, so we measured how much the conclusions depend on it. (i) Order-free attribution. Under Shapley values, the structural signals keep 34% to 41% of the gain they show when entering first, so about three fifths of that gain is shared with memory and recency. We will report this next to the sequential numbers and soften our "four fifths" sentence. (ii) Moving the "never met" indicator from memory to structure changes the historical-protocol residual from +0.000 to a median of +0.058 AP. We will report both assignments. (iii) Threshold. At 0.005, 0.01, 0.02 and 0.03 AP, 21, 14, 6 and 3 of 112 cells survive. (iv) A second scorer and a shuffled-feature control are already in the paper. We have not tested richer definitions of memory or recency, such as decayed counts. Richer blocks can only absorb more, so the current blocks give an upper estimate of what structure adds.

W3 / Q3. Generalization beyond DyGFormer. Since submission we ran the trained-model experiment on four backbones, 14 benchmarks and 3 seeds. The pair-time channel improves TGN, GraphMixer and TCL on 13, 12 and 13 of 14 benchmarks (median +0.011, +0.030 and +0.044 AP, up to +0.199). We have not run CAWN, TPNet or TNCN, and the revision will state that the model-level claim covers DyGFormer's co-occurrence channel and these three backbones only. At the feature level, the test already covers four structural signals, including a published cohesion channel. We also agree that the conclusion depends on data and protocol, and that is the claim we intend. We will scope the title and abstract to standard benchmarks. The paper names the regimes where structure survives, for example GoogleLocal, where overlap keeps +0.120 AP after recency over 5 seeds (standard deviation 0.0004).

We hope the added backbones, the order-free attribution and the narrower claim address the soundness concerns, and we would be grateful if the reviewer would reconsider the rating in their light.

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

This paper examines whether structural features in temporal link prediction provide predictive value beyond interaction memory and recency. Across 14 benchmarks, an audit using incremental feature inclusion, shuffled controls, and two scorers finds that most measured structural gains disappear after accounting for these factors. Model-level experiments further show that simple pair-history features can often replace DyGFormer’s co-occurrence channel. Structural information remains valuable for previously unseen pairs, repeat-free datasets, and certain dense networks. The paper introduces structaudit to identify these regimes and detect evaluation pitfalls.

Critical strengths
  1. The paper challenges the interpretation of structural-channel ablations rather than merely proposing another predictor. Distinguishing structural information from interaction repetition and timing could improve both benchmark design and the interpretation of architectural gains.

  2. The analysis explicitly examines simultaneous-event leakage, invalid negative sampling on bipartite graphs, and fitting scorers within the test period. The shuffled-feature control and second scorer provide additional checks beyond a single probing model.

  3. The study covers multiple structural signals, benchmarks, and negative-sampling protocols, supplemented by model-level interventions. Its identification of regimes where structure remains useful is particularly valuable and makes the findings more informative than a blanket claim that structure is unnecessary.

Critical weaknesses
  1. The audit establishes conditional predictive redundancy, not a definitive attribution of structural gains. A small improvement from adding structure after memory and recency does not establish that the structural representation primarily encodes those quantities. Correlated signals and interactions can produce the same result, and the sequential ordering assigns shared predictive information to the features introduced first.

  2. The trained-model experiments do not remove all neighborhood information. Replacing DyGFormer’s explicit co-occurrence channel leaves its neighborhood-sequence backbone intact. More importantly, Section 4 describes TGN as reading no neighborhood structure, whereas the standard DyGLib implementation uses a graph-attention embedding module that accesses temporal neighbors. Unless the authors modified this component, TGN is not a structure-free control.

  3. The interpretation of Corollary 1 exceeds what it proves. The implication that nonzero overlap at depth three certifies a previously unseen pair is valid under the stated undirected-history construction. However, it is only a sufficient condition: zero overlap does not establish that the pair has interacted. Indeed, the measured vector ((ov_1,ov_2,ov_3)) can equal ((1,0,0)) both for adjacent vertices in a triangle and for the nonadjacent endpoints of a three-node path. Thus, this truncated overlap vector does not generally determine whether a pair has met. The propositions support partial memory information, but not the stronger identification suggested by the surrounding text.

Questions for authors
  1. Which neighborhood-derived inputs remain in each “no structural channel” variant?

  2. How sensitive are the conclusions to the ordering of feature blocks, the 0.01 AP threshold, and retaining richer sequence-level structural representations rather than aggregate summaries?

2 comments

We thank the reviewer for a careful and constructive review. All three weaknesses are fair. We answer each with results measured since submission, and we will revise the paper accordingly.

W1. Conditional redundancy, not attribution; dependence on ordering. We agree, and we will state the claim as the conditional one: what structure adds once a model already has memory and recency. To measure how much the order matters, we computed Shapley values over the feature blocks on all 84 feature matrices (14 benchmarks, 2 protocols, 3 seeds). Entering last, the four structural signals add a median of +0.000 to +0.008 AP. Under Shapley values, which split shared information symmetrically, they keep 34% to 41% of what they add when entering first (34% to 43% with gradient-boosted trees). The order-free statement is therefore that about three fifths of the apparent structural gain is shared with memory and recency, not the four fifths our text suggests. We will report both rules side by side and correct that sentence.

W2. Neighborhood information remaining in the trained models. The reviewer is right on both points. (a) Removing DyGFormer's co-occurrence channel leaves the neighbor sequences intact, with their node, edge and time encodings. (b) DyGLib's TGN uses a graph-attention embedding over temporal neighbors, and we did not modify it. "Reads no neighborhood structure" is wrong; the accurate statement is "has no pairwise structural channel", and we will correct it. To have a control that truly reads no neighbor, we trained a model on the nine pair-history numbers alone: a two-layer MLP with the same training protocol, no backbone, and no neighbor of either node. Under random negatives it is within 0.01 AP of the best of four backbones on 8 of 14 benchmarks, and within 0.03 on 10. Under historical negatives it is within 0.01 on only 1 of 14, so backbones do earn their keep under that protocol, and we will say so.

W3. Corollary 1. We agree. The corollary is one-sided: non-zero overlap at depth three certifies a never-met pair, and the converse fails. The reviewer's example is correct. What separates the triangle from the path is depth zero (whether u is itself a neighbor of v), which our measured vector over depths 1 to 3 omits. We will restate the surrounding text as "the overlap vector carries partial information about whether the pair has met" and remove the wording that suggests identification.

Q1. Neighborhood-derived inputs in each "no structural channel" variant. DyGFormer: the first-hop neighbor sequences of both nodes with node, edge and time encodings; only the co-occurrence encoding is removed. TGN: node memory plus graph attention over temporal neighbors. The nine-number model above: none. We will add a table that lists this for every variant.

Q2. Sensitivity. Ordering: see W1. Threshold: at 0.005, 0.01, 0.02 and 0.03 AP, the surviving cells are 21, 14, 6 and 3 of 112, so the conclusion does not hinge on 0.01. Assignment of the "never met" indicator: it matters under historical negatives, where counting it as structure gives a median of +0.058 AP, and we will report both assignments. Richer sequence-level representations: the trained-model experiment is this check, because the co-occurrence channel is a per-slot sequence representation inside the Transformer. We have extended it to 14 benchmarks with 3 seeds each. The nine numbers match or exceed the channel on 11 of 14, and the exceptions are Flights, Can. Parl. and UN Vote. Our text says "two exceptions"; three is correct, and we will fix it. The same nine numbers also improve TGN, GraphMixer and TCL on 13, 12 and 13 of 14 benchmarks (median +0.011, +0.030 and +0.044 AP).

In short, the revision will make the claim conditional, report the order-free attribution next to the sequential one, add a neighbor-free control, and restate Corollary 1 as a one-sided result. We hope these changes address the concerns, and we would be grateful if the reviewer would reconsider the rating in their light.

I thank the authors for their detailed rebuttal. But the paper is not ready for publication in its current form.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.