Beyond Pair Statistics: Relational Extrapolation for Temporal Graph Link Prediction

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.