acceptodds
Under review as a conference paper at ICLR 2027

Beyond Pair Statistics: Relational Extrapolation for Temporal Graph Link Prediction

11 views

Abstract

Temporal link prediction aims to infer future interactions from evolving node histories in temporal graphs. Existing methods are broadly query-agnostic or query-aware, with the latter often achieving stronger overall performance. However, separating repeated and first-seen queries reveals that this advantage concentrates on repeated interactions and can weaken or even reverse on first-seen ones. We identify pair statistics, such as edge recurrence and neighbor co-occurrence, as a key source of this behavior. These statistics provide highly predictive shortcuts when supported by historical interactions, but become unavailable or non-discriminative beyond their support. We call this Pair-Statistic Support Bias, under which overall evaluation can conflate pattern exploitation with relational generalization. To address this limitation, we propose StatE, a simple yet effective query-aware approach for link prediction on temporal graphs. We design a stable temporal node memory and provide a tracking-stability analysis; building on it, we propose relational extrapolation encoding for structure learning. Specifically, each source-side historical neighbor serves as a witness and is compared with the targets before aggregation, enabling potential relations to be inferred beyond predefined patterns and generating relational tokens. We then aggregate these relational tokens into node representations. We further provide a unified view: recurrence is directly exposed through witness identity, co-occurrence is indirectly mediated through temporal memories shaped by historical interactions, and unsupported pairs rely on memory-based extrapolation. Across ten temporal graph benchmarks and eleven baselines, StatE achieves up to 17.93% relative MRR improvement over the strongest baseline.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Temporal graphs, link prediction, temporal graph neural networks

Reviews

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

For temporal graph link prediction, diagnostic experiments show that query-aware methods outperform query-agnostic baselines mostly on repeated queries. These methods exhibit weakened or reversed performance on first-seen queries. The authors define this phenomenon as Pair-Statistic Support Bias. This bias describes that shortcuts built upon historical pair statistics only work within historical support ranges. The proposed StatE integrates time-decay smoothed node memory, leverages relational extrapolation encoding to model witness-target dependency and adopts lightweight gMLP aggregation equipped with attention pooling. Experiments across ten datasets and eleven baselines achieve up to 17.93% relative MRR improvement. However, the paper suffers from poor writing, which substantially hinders readability.

Critical strengths

This is a distinctive perspective. The authors partition test queries first into repeated and first-seen categories, and further split them across direct, co-occurrence-only, and none support regimes as shown in Figures 1, 3, and 5. This evaluation clearly demonstrates that aggregate MRR conflates pattern exploitation and relational generalization. The statistic-removal study in Observation II adopts an interventional, rather than observational, design. Removing pair statistics reduces MRR for repeated queries and improves MRR for first-seen queries. This research indicates that statistical shortcuts not only cease to function outside their support range but can also introduce active bias during optimization.

Critical weaknesses
  1. The evaluation relies on non-standard datasets and metrics instead of the official TGB benchmark, limiting the credibility of empirical results. Moreover, the proposed method constitutes largely combinatorial innovation assembled from existing methods. The related work does not discuss a prominent line of static graph link prediction research exemplified by NCN, BUDDY and SEAL, which replaces hand-crafted heuristic statistics with learnable pairwise representations. This omission obscures the close conceptual parallel between this prior paradigm and the authors’ method, substantially weakening the justification for its originality.

  2. Poor writing clarity and insufficient conceptual grounding render the paper difficult to follow. Core concepts including Pair-Statistic Support Bias, relational extrapolation, pattern exploitation, statistic dependence, co-occurrence, repeat frequency, and identity matching are all introduced without explicit definitions prior to their use. Moreover, it remains unclear whether the dichotomy between query-aware and query-agnostic methods has been adopted in prior literature. If this taxonomy is not widely recognized within the field, the paper provides an overly concise discussion on the performance advantages of query-aware methods.

Questions for authors
  1. What distinguishes the pairwise target-dependent representation from the line of static graph link prediction methods that replace hand-crafted heuristic statistics with learnable pairwise representations, such as NCN, BUDDY, and SEAL?

  2. Is the taxonomy of query-aware and query-agnostic methods adopted in prior literature?

  3. The ablation study presents an inconsistency with the core claim of the paper. Table 3 shows that StatE+Co-occ outperforms vanilla StatE across all three datasets (UCI: 79.92 > 79.89, MOOC: 68.44 > 66.06, YouTube: 68.38 > 65.37). StatE+Stats also achieves better performance on UCI and MOOC. In other words, the best-performing proposed variant still incorporates explicit pairwise statistics. This directly contradicts the "beyond pair statistics" claim in the title and abstract. The authors rationalize this observation by stating that co-occurrence retains complementary information. However, if StatE+Stats is indeed the optimal model, the narrative of going beyond pair statistics becomes questionable. We suggest the authors either acknowledge this inconsistency and revise their claim to "learning relations as the primary component with explicit statistics as an optional supplement", or explain why the combined variant is not adopted as the main model.

Reviewer_pajROpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The authors of this work study temporal link prediction on dynamic graphs and expose a limitation that they call Pair-Statistic Support Bias. This refers to the fact that some existing methods achieve strong overall performance simply by exploiting recurring historical patterns (edge recurrence and neighbor co-occurrence), which weakens their performence for data with unseen relations. To address this issue, the authors propose STATE, a method that replaces explicit pair-wise lookups with a learned relational encoding. STATE maintains stable temporal node memories with theoretical tracking-stability guarantees. It further compares each historical example with candidate targets via a learned MLP-based relation before aggregation, generating target-dependent relational tokens. With this approach, the authors unify recurrence, co-occurrence, and extrapolation to new relations in a single framework. The proposed approach is shown to exhibit improved performance compared to 11 baseline methods across 10 temporal graph data sets.

Critical strengths
  • [S1] The Pair-Statistic Support Bias is clearly formulated and the authors give good empirical evidence for its relevance. Moreover, the decomposition of the bias into repeated/first-seen and direct/co-occurrence regimes provides insights that go beyond simple aggregate metrics.

  • [S2] The proposed method STATE achieves best or second-best performence in 8 out of 10 data sets and it achieves favorable accuracy–efficiency trade-offs compared to other query-aware methods. However, an open question is why the proposed method shows a degradation for two datasets Reddit and Flights, which are highly recurrent (see Questions).

  • [S3] The paper contains both a theoretical analysis as well as an experimental evaluation in ten data sets with 11 baselines. The authors further perform an ablation study to test the impact of several components of their architecture.

Critical weaknesses
  • [W1] The problem as such is not new and the issue of inductive link prediction in temporal graphs has been addressed by several works that are not mentioned. In particular, the paper "Towards Better Evaluation for Dynamic Link Prediction" by F Poursafei et al. specifically discussed challenges in the evaluation of temporal link prediction that are due to simple reoccurrence patterns, introduced aggregate statistics to capture such patterns, discussed suitable negative sampling strategies (similar to those used by the authors of the present work) and provide a simple memorization baseline method EdgeBank that provides strong performance on several data sets. The fact that the authors do not discuss the relation of their proposed approach to this closely related prior work is an obvious omission.

  • [W2] Considering the focus of the work, it is surprising that the authors do not compare their approach against other methods that are specifically designed for inductive temporal link prediction, e.g. CAW proposed by Wang et al. at ICLR 2021. Similarly, there are several related methods from static link prediction that should be discussed, e.g. inductive relational GNNs.

  • [W3] In terms of reproducibility, there are some details of the method that require further elaboration, e.g. how exactly the authors perform "collision checking in negative sampling to avoid information leakage" (page 18), how some hyperparameters have been chosen or how memory is updated at training and test time (see questions below).

[W4] The specific choice of the hyperparameter that controls the decay rate of memory seems strange, given the very different timescales of the data sets. A single fixed value was used, but it seems that this parameter should strongly depend on the characteristics of the data sets, and that the performance of the model should be sensitive to this choice.

Questions for authors

Related to the weaknesses discussed below, I kindly ask the authors to clarify the following questions:

  • [Q1] For the data sets Reddit and Flights, which both have a high repeat ratio, I found surprising that the proposed method performs worse than the baselines. Considering the explicit modelling of reoccurrence I found this surprising. Do the authors have an explanation for this?

  • [Q2] Considering the memory updates explained in section 4, how exactly are node memories updated? Are ground-truth edges from the training set used or model predictions? If ground-truth edges are used, does this create a train-test discrepancy since memory updates at test time must probably rely on predicted edges?

  • [Q3] The negative sampling protocol seemingly does not cover the case that both endpoints of an edge have previously been not observed. How would the proposed method perform in the transductive case of completely unobserved nodes?

  • [Q4] Could the authors explain how the specific values of hyperparameters have been chosen, e.g. λ=0.31\lambda=0.31, β=0.3\beta=0.3 or the dimensionality of the embeddings. Have these parameters been found by hyperparameter optimization? Moreover, λ=0.31\lambda=0.31 leads to a very rapid decay on the timescale of less than an hour. It is thus surprising that this choice does not depend on the temporal granularity of the data sets, which are very different. How sensitive is the performance to the choice of this value?

  • [Q5] Why are the ablations only reported for four of the data sets?

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

The paper studies future interaction prediction in changing graphs and argues that overall scores can hide weaker performance on first-time interactions because models may rely heavily on repeated interactions and shared neighbors. Its proposed method, StatE, maintains a summary of each node’s history and uses a small neural network to compare a candidate node’s history with those of the other node’s previous neighbors. These comparisons are combined with link and time information to predict interactions. Experiments are conducted to compare the performance of StatE with eleven existing methods on ten datasets.

Critical strengths
  1. The problem studied is relevant and clearly motivated. Separating repeated links from first-seen links makes aggregation scores more interpretable.

  2. The paper examines performance in challenging settings. Figure 3 reports improvements for the group classified as having neither previous interactions nor shared-neighbor support on both Stack Exchange datasets. It also tests the same trained models against harder sets of alternative destinations on four datasets. Additional analyses suggest that the learned comparison features remain useful when the examined hand designed statistics provide little information.

  3. The method appears practical to train. Its main comparison function and history update rule are relatively simple. On sx-askubuntu, the reported training efficiency is comparable to lightweight methods, and peak GPU memory use is 2.38 GB, though efficiency is evaluated on only one dataset.

Critical weaknesses
  1. It is unclear what the proposed comparison function adds beyond existing approaches. StatE uses a small neural network to compare the historical summaries of a previous neighbor and a candidate destination. CRAFT already compares a candidate destination with a node’s previous neighbors using an attention mechanism. StatE makes this comparison differently, but the experiments do not clearly show why its particular design is better.

  2. The history-update procedure may need a clearer explanation. Each node has one stored history summary, but the node features calculated during prediction depend on the candidate destination. The paper does not clearly explain which candidate’s features are used to update that summary. It should also explain how multiple appearances of the same node within a batch are combined and which observed interactions trigger updates.

  3. It is unclear how events with identical timestamps are handled. This matters because Flights and YouTube contain millions of interactions but only 122 and 203 distinct timestamps, respectively.

  4. The results do not fully support that reliance on past statistics causes weaker prediction of first-time interactions. The motivating analysis covers only two datasets, and removing statistics does not affect all methods in the same way. For example, Appendix A reports a 51.35% relative drop in SALoM’s performance on first-time interactions after statistics are removed. In addition, adding explicit statistics to StatE also improves performance on all three datasets in Table 3. It suggests that the usefulness of these statistics depends on the model and setting. The main claim is thus less convincing.

  5. The mathematical analysis does not establish better prediction of previously unseen links. Theorem 1 explains how the history-update rule can track changing node features under assumptions that limit feature changes and representation errors. It also requires old information to lose influence sufficiently quickly. The paper does not show that the features learned by StatE satisfy these assumptions.

Questions for authors
  1. In Line 246, what is the function \kappa(w, d; t)?

  2. In Line 291, what does it mean by two branches?

  3. Can we have average precision (AP) comparison in addition to MRR scores, as the AP values are commonly used in the literature?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.