acceptodds
Under review as a conference paper at ICLR 2027

From Complex Histories to Simple Predictors: Predictive Dimension in Dynamic Graph Learning

Abstract

Existing continuous-time graph learning methods rely heavily on complex neural architectures to encode ever-expanding interaction histories. However, the future conditional distribution induced by complex histories can often be characterized by a low-dimensional predictive state manifold, implying that only a few predictive degrees of freedom are essential for future interactions. We therefore argue that continuous-time graph learning should identify low-dimensional states sufficient for future prediction rather than reconstruct the full history. To make this perspective measurable, we define and independently estimate the intrinsic predictive dimension, which quantifies the effective predictive degrees of freedom required by a given task. Specifically, we remove the history-independent marginal from the history-conditioned future distribution, decompose the resulting predictive residual operator, and estimate the minimum effective rank needed to preserve the predictive power of the full history. Experiments across datasets show that model performance saturation is largely determined by the intrinsic predictive dimension. Based on this finding, we propose PreDyG, a lightweight model whose capacity is matched to the intrinsic predictive dimension. PreDyG achieves superior predictive performance with only 0.07% of the parameters of a representative complex baseline.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Intrinsic Predictive Dimension, Predictive State Representations, Model Capacity, Temporal Link Prediction

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_eqUnOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an independent, data-side method to estimate the 'intrinsic predictive dimension' of a dynamic graph dataset before model design. It demonstrates that this metric acts as a capacity scale, where datasets with higher predictive dimensions require larger parameter budgets to reach near optimum performance, enabling lightweight model selection (PreDyG) guided by task complexity rather than raw graph size.

Critical strengths

S1. Some sections, especially the Introduction and Problem Statement, are very well-written; they motivate the problem effectively and introduce the reader to the literature landscape well.

S2. The paper proposes an ultra-low-parameter, highly efficient model, PreDyG, which achieves state-of-the-art (SOTA) performance with up to 1,300$\times$ fewer parameters than existing baselines. This extreme efficiency makes it particularly standout compared to prior models.

Critical weaknesses

W1. Readability, Structure, and Notational Inconsistencies: The paper becomes noticeably difficult to follow starting in Section 4, as several technical terms are introduced without prior definition or context (e.g., "ambient future-distribution dimension" and "ambient space"). Furthermore, the transition between subsections; such as between the Past–Future Operator and Predictive Dimension Selection; feels abrupt and disconnected, leaving a gap in the narrative flow. Finally, the notation is frequently confusing due to overloaded symbols: for instance, dd denotes both destination nodes and feature dimensions, while mm is later introduced to represent channel dimension/width. Cleaning up the notation, smoothing section transitions, and defining key terms upon their first appearance would significantly improve the paper's clarity. ( Typo in model name PhyDyG in appendix )

W2. No Structural Prior: The work dwells into analysis for dynamic graph event streams and designs an estimator for predictive dimension. It does this by defining the future to predict and historical context, but there are a few unjustified design choices made for the estimator: the complete lack of any structural prior at all or larger historical context, and the use of frequency binning for nodes bs,bdb_s, b_d. The history is limited to the latest observation of the destination node for the query-time source node. This choice—which completely disregards the temporal neighbor/structural information these events build up, as well as the long-range dependencies—does not feel trivial, and not justifying it decreases the credibility of the proposed estimator. Furthermore, the use of frequency binning is yet another design choice that is not elaborated: why is structure left out from this again, and what are the consequences of forming this equivalence class?

W3. Limited Novelty: The proposed work overclaims novelty, with its major contribution limited to the estimator formulation. The architecture PreDyG follows the DyGFormer/DyGMamba architecture, albeit it removes the attention/Mamba aggregation with mean, max, and most recent pooling for the collected events. Moreover, the NIF feature used is simply the neighbor co-occurrence encoder proposed in DyGFormer. Notably, the model's contribution is mostly due to this module (as shown in Table 4). Then again, the lack of structural information in the estimator does not make it a meaningful contribution in graph learning—this estimator is overly generalized and could very well work on streams of arbitrary symbols.

Questions for authors

As mentioned in weakness above.

7 comments

W1. Clarity, organization, and notation

Thank you for identifying these specific reading difficulties. We agree that Section 4 did not sufficiently explain several terms or the connections between its components. We have revised the presentation in four respects.

(1) Clearer methodological progression. We organize the explanation as: prediction task → history–future representations → history-independent baseline → predictive residual → predictive-dimension selection → capacity evaluation. Each transition explains what the preceding step provides and why the next is needed. In particular, we clarify the connection between the Past–Future Operator and Predictive Dimension Selection: the centered operator captures changes in history-conditioned distributions relative to the no-history marginal; its low-rank decomposition supplies candidate predictive directions; and the subsequent Brier-risk criterion determines how many directions are needed to retain predictive gain.

(2) Precise definitions of dimensions. We define “ambient space” and “ambient future-distribution dimension” at their first occurrence. Our fixed representation uses 512 destination bins, so Damb=512D_{\mathrm{amb}}=512 denotes the number of coordinates in the future-probability vector, whose ambient space is R512\mathbb{R}^{512}. These vectors lie in a probability simplex with 511 degrees of freedom. Each row of the centered residual matrix sums to zero, so its rank is at most 511. We also clarify our counting convention: candidate dimension dd includes the baseline component and d−1d-1 residual directions; hence, d=1d=1 is the no-history predictor. This distinguishes ambient dimension, simplex degrees of freedom, residual rank, and selected predictive dimension.

(3) Consistent notation. We use u,vu,v for source and destination nodes, LL for history length, dd for candidate predictive dimension, r=d−1r=d-1 for retained residual directions, mm for channel width, and PP for parameter count, with separate symbols for input feature dimensions. We clarify that data-side predictive dimension and neural channel width are distinct quantities: they need not be numerically equal, and predictive directions do not correspond one-to-one to neural channels. We also provide the shapes of key mathematical objects and check notation throughout the main text and appendix.

(4) A worked example. Using UCI, we illustrate how the history–future conditional-probability table QQ and no-history marginal π\pi yield

Chf=ph(Qhf−πf),C_{hf}=\sqrt{p_h}(Q_{hf}-\pi_f),

and how retaining d−1d-1 residual directions, adding back the marginal, clipping, and normalization reconstruct predictive probabilities. Following the original protocol, the first 40% of events fit the operator and the next 20% select the dimension. We evaluate the full candidate grid {1,2,4,8,16,32,64,128,256,512}\{1,2,4,8,16,32,64,128,256,512\}. The retained gain is

G(d)=R(1)−R(d)R(1)−min⁡j∈DR(j),G(d)=\frac{R(1)-R(d)}{R(1)-\min_{j\in\mathcal D}R(j)},

where R(d)R(d) is selection-split Brier risk and D\mathcal D is the full candidate grid. This example illustrates selecting the smallest candidate dimension retaining at least 95% of the best attainable predictive gain, with minimality checked against the full grid. It makes the connection between operator construction, residual directions, and dimension selection concrete.

Finally, we have corrected “PhyDyG” to “PreDyG” in the appendix tables and checked the model name throughout the manuscript.

W2: History, structure, and frequency grouping.

(1) Historical and structural context. The general definition permits a history map Hk=ϕ(Hk,qk)H_k=\phi(\mathcal H_k,q_k) constructed from the pre-query event stream. The reported implementation uses the source category and its previous destination category. This compact context controls sparsity in the finite-sample conditional table; it does not assume that longer-range or structural dependencies are absent. PreDyG can retrieve up to LL interactions per endpoint, with configurable LL, and uses elapsed-time and neighborhood-interaction-frequency features. We have clarified the distinct roles of the estimator’s context and the model’s history encoder.

We evaluated three history settings, applying each consistently to the corresponding estimator and PreDyG capacity evaluation. The future target, chronological protocol, and original link-prediction test task were kept fixed.

DatasetHistory settingHeld-out Brier gain (10−2)(10^{-2})d^pred\hat d_{\rm pred}Capacity regret
SocialEvoReported context5.6320.7
SocialEvoL=16L=16 + time4.4320.5
SocialEvoFull history + structure5.7320.4
RedditReported context4.92560.8
RedditL=16L=16 + time5.22560.6
RedditFull history + structure5.02560.5
Controlled structural streamReported / full history + structure0.3 / 1.81 / 324.8 / 0.6

Capacity regret is the test-AP gap from the best configuration within the same history setting; test AP is not used to select a configuration. On SocialEvo and Reddit, richer histories increase held-out predictive gain while the selected dimension remains 32 and 256, respectively. The reported compact setting has a capacity regret below one AP point on both datasets; incorporating more history and structure reduces that gap by 0.3 points. The stable dimension indicates that these additions do not change the estimated capacity scale on these datasets, although they improve the performance of the corresponding history settings. The controlled stream identifies a boundary: when future interactions depend on structure absent from the compact context, the estimated dimension changes from 1 to 32 and regret falls from 4.8 to 0.6 points. We have made this scope explicit in the revision.

(2) Frequency grouping. A category budget KK retains the K−1K-1 most frequently observed identities separately and pools the remainder. Frequency determines which identities have enough observations for separate estimation; it is not a predictive feature or a claim that nodes with similar frequencies behave alike. A structural grouping additionally requires a graph-construction window and a definition of structural similarity. We compared the reproducible frequency rule with a structural alternative at the same category budget.

Reddit destination partitionRare-identity event shared^pred\hat d_{\rm pred}/categoriesCapacity regret
K=256K=256, one tail category11%128/2560.9
K=512K=512, one tail category5%256/5120.8
K=512K=512, structural tail groups5%256/5120.6

A shared tail category is a computational grouping, not predictive equivalence: it may mix distinct source preferences or future destinations. Increasing KK changes Reddit’s absolute estimated dimension, so the partition must accompany any reported dimension. At the matched K=512K=512 budget, structural tail grouping retains the 256-dimensional estimate and reduces capacity regret by 0.2 AP points in its corresponding capacity evaluation. Thus, the frequency rule provides a compact baseline at this resolution, while structural refinement yields a measurable improvement in the evaluated setting. We have stated both the information lost through grouping and the dependence of the estimate on the partition.

W3. Limited Novelty

We thank the reviewer for this comment. Our contribution concerns the predictive information retained during feature extraction and the capacity needed to represent it. We clarify three aspects below.

(1) Performance attribution beyond NIF. Table 4 establishes the importance of NIF to PreDyG. Attribution of gains over existing methods requires a complementary comparison in which NIF is shared.

We therefore evaluate two factors: whether NIF is included and whether capacity is selected using the proposed estimator. Estimator guidance selects capacity within each backbone. Data splits, history sampling, other inputs, and training/evaluation protocols are held fixed, with the capacity-selection rule and search budget specified before test evaluation.

UCI AP (%).

BackboneCapacityWithout NIFWith NIF
DyGFormerOriginal91.8095.76
DyGFormerGuided92.1596.15
DyG-MambaOriginal92.1096.14
DyG-MambaGuided92.4096.50

With NIF retained, estimator guidance improves AP by 0.39* and 0.36* percentage points on DyGFormer and DyG-Mamba, respectively. Without NIF, the corresponding gains are 0.35* and 0.30* points. We further evaluate the same guidance across datasets:

MethodWikipedia APLastFM APUCI AP
DyGFormer98.8293.0095.76
+ guidance98.9593.2596.15
DyG-Mamba99.0893.5796.14
+ guidance99.1593.7596.50

Estimator guidance improves both backbones across the three datasets while retaining their existing NIF inputs. Together, these results demonstrate an additional contribution from estimator-guided capacity selection beyond NIF, with benefits extending to architectures other than PreDyG. The substantial NIF ablation drop in Table 4 therefore reflects the importance of the input feature, while the controlled comparisons establish the complementary value of our method.

(2) Predictive dimension of node interactions. The probe conditions on the source-node frequency bin and the frequency bin of its most recent interaction partner, and predicts the next partner's bin. Histories therefore follow the same source node's interaction trajectory, capturing source-conditioned preferences and recent relational context. Its scope is event-ordered interaction dependence; multi-hop topology and elapsed-time intervals are not explicitly encoded.

Predictive state representations [4] and spectral HMM learning [5] establish precedents for representing states through future predictions and learning predictive representations using spectral methods. We develop this perspective into a reproducible estimator for node-interaction events: fix the history–future representation, subtract the history-independent marginal, decompose the weighted predictive residual, and select the minimum dimension preserving historical predictive gain under held-out Brier risk. We then test its relationship with dynamic graph model capacity saturation.

The manuscript's interventions provide relevant evidence: on SocialEvo, perturbing source or destination identity reduces the estimated dimension from 32 to 1, while temporal shuffling leaves it at 32. Thus, the estimate responds to particular interaction dependencies even when event count is preserved. Its relevance to graph learning rests on measuring these dependencies and connecting them to useful model capacity; the statistical framework can also transfer to other event streams.

(3) Feature integration versus feature extraction. PreDyG separates these two stages. The manuscript treats node attributes, edge attributes, time encodings, and neighborhood interaction statistics as established inputs in this line of work. Neighbor co-occurrence and related frequency features are used or developed in DyGFormer, FreeDyG, and DyG-Mamba [1–3].

Our focus is the subsequent feature-extraction stage: how many predictive degrees of freedom must be retained? Across the evaluated probes and tasks, predictive variation concentrates in relatively few effective directions, and estimated dimension is associated with capacity saturation. This motivates the compact PreDyG instantiation, which combines MLP-based learnable components with mean, max, and most-recent pooling. The contribution connects data-side predictive complexity, effective capacity, and a minimal feature extractor evaluated for accuracy and cost. Shared input features make comparisons of this extraction stage more informative.

[1] Yu et al. Towards Better Dynamic Graph Learning. NeurIPS 2023.
[2] Tian et al. FreeDyG. ICLR 2024.
[3] Li et al. DyG-Mamba. NeurIPS 2025.
[4] Littman et al. Predictive Representations of State. NeurIPS 2001.
[5] Hsu et al. A Spectral Algorithm for Learning Hidden Markov Models. COLT 2009.

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

This paper explores the intrinsic predictive dimension in continuous-time graph learning, hypothesizing that future interaction distributions lie on a low-dimensional manifold and therefore do not require encoding the full history. The authors introduce a model-agnostic estimator of this dimension, empirically demonstrate that predictive performance plateaus once model capacity matches the dimension across datasets, and propose a lightweight model designed around this dimension. It achieves state-of-the-art results while using orders of magnitude fewer parameters than complex baselines.

Critical strengths
  1. The work introduces the intrinsic predictive dimension as a data-centric, model-agnostic metric that quantifies the effective predictive degrees of freedom in temporal interaction processes.
  2. The empirical validation is thorough and systematic: intervention experiments that disrupt temporal order, node identities, and event pairs confirm that the predictive dimension captures genuine history–future dependencies rather than confounding factors such as dataset size, event count, or marginal statistics.
Critical weaknesses
  1. The predictive dimension estimator relies on fixed frequency-based binning and a simplified history representation (current source plus most recent destination). This discrete, handcrafted representation may underestimate the true predictive dimension of complex interaction patterns, limiting the estimator’s expressiveness.
  2. Dependency intervention experiments are conducted on only a small subset of datasets with limited perturbation types. The nature of the dependencies captured by the predictive dimension is not deeply interpreted, and there is a lack of finer-grained analysis of what predictive directions actually encode.
  3. The relationship between predictive dimension and sufficient parameter budget is established only empirically within the PreDyG family. No theoretical bound is provided, and it is uncertain whether this correspondence holds across different architecture families, limiting its prescriptive power.
  4. Ablation results show that neighborhood interaction frequency (NIF), an explicit statistical feature, drives the largest performance gains. This means part of PreDyG’s advantage comes from feature engineering rather than low-dimensional state modeling, somewhat weakening the core argument centered on predictive dimension.
Questions for authors

Please refer the the weaknesses.

6 comments

W1: Sensitivity to identity binning and history representation.

Thank you for raising this question. We examine whether finer identity resolution or richer histories reveal predictive structure missed by the original probe. The comparisons below show stable selected dimensions and 96.4%–98.6% retention of the richer histories' predictive gain.

The fixed probe provides a reproducible, architecture-independent measurement while controlling conditional-table sparsity. Frequent node identities remain separate; only tail identities are pooled. Its history summary combines the current source and that source's previous destination. We test both choices on the original intervention-study streams: 80,000-event prefixes of Reddit and SocialEvo, and the complete UCI stream.

(1) Identity resolution. We increase source and destination category budgets together and extend the candidate-dimension grid, keeping the history summary and chronological splits fixed.

Category budgetReddit: d / KUCI: d / K
512256 / 512256 / 512
1,024256 / 1,024256 / 1,024
2,048256 / 2,048256 / 1,899

Here d is the selected dimension, including the marginal component, and K is the occupied destination-category count.

As additional destination identities become distinguishable, d remains 256 while d/K decreases from 50.0% to 12.5% on Reddit and 13.5% on UCI. This supports saturation below the expanded representation ceilings on these streams.

(2) Historical information. We fix the future partition at 512 and enrich the context with the previous two/four destinations and a cumulative summary of recency-weighted interactions, elapsed time, and local structure. All features use only pre-query events. We fit on the first 40%, select dimensions and variant settings on the next 20%, refit on the first 70%, and evaluate on the same final 30%.

History summaryRedditSocialEvoUCI
Source + previous destination0.9331 / 2560.8997 / 320.9204 / 256
Source + previous 2 destinations0.9328 / 2560.8994 / 320.9198 / 256
Source + previous 4 destinations0.9324 / 2560.8991 / 320.9191 / 256
Cumulative summary + time + structure0.9320 / 2560.8989 / 320.9184 / 256
Original gain / richer-reference gain (%)97.898.696.4

Entries are test Brier risk / selected d. The final row is 100(R0-R_original)/(R0-R_reference), with R0=0.9820/0.9560/0.9740. The reference variant is selected on validation data before test evaluation.

Richer histories improve Brier risk by 0.0008–0.0020, while the original summary already gains 0.0489–0.0563 over the marginal baseline. The common-reference comparison shows that the compact summary preserves over 95% of the predictive gain available to the tested richer histories, alongside stable dimension choices. This directly tests information retention beyond each probe's own saturation curve.

We will add these sensitivity results and describe the measurement explicitly as effective predictive rank for a specified history summary and future partition. The supported claim is that the compact probe captures the dominant predictive structure accessible to the tested refinements on these streams.

W2: Limited intervention coverage and unclear semantics of the predictive directions.

We have expanded the dependency interventions and added a content-level analysis of the predictive directions.

Intervention coverage. We extended the same intervention protocol from four datasets to all eight conventional benchmarks, adding Wikipedia, LastFM, Enron, and Flights with the same history/future representation, chronological splits, dimension-selection rule, and three independent randomizations per intervention. We additionally introduce two targeted perturbations that isolate one component of the history instead of removing a whole dependency: a within-source shuffle of the previous destination LL, which preserves p(F∣S)p(F\mid S) while removing the additional dependence on recent interaction, and a recency-position shuffle that permutes the position of the most recent interaction while preserving its multiset.

The expanded results retain the same dependency sensitivity. Shuffling destination or source identity collapses the estimate to the no-history floor on every one of the eight streams, whereas time/order shuffling and intact source–destination pair shuffling leave a dataset-specific fraction of the predictive structure: predictive dimension tracks the dependency that is actually disrupted, not a generic sensitivity to perturbation. For example, LastFM falls from d^pred/dhold=64/64\widehat d_{\mathrm{pred}}/d_{\mathrm{hold}}=64/64 to 8/88/8 (13% retained) under time/order shuffling yet stays at 64/6464/64 (100%) under pair shuffling, while Wikipedia shows the complementary pattern, 128/128128/128 under time/order shuffling but 32/3232/32 (25%) under pair shuffling. Together with the original four datasets, the eight streams span two orders of magnitude in node and event scale and give five distinct response profiles.

DatasetOriginalTime/orderDestinationSourceSource–destination pair
SocialEvo32/32 (100%)32/16 (100%)1/1 (3%)1/1 (3%)16/16 (50%)
UCI256/256 (100%)1/1 (<1%)1/1 (<1%)1/1 (<1%)1/1 (<1%)
LastFM64/64 (100%)8/8 (13%)1/1 (2%)1/1 (2%)64/64 (100%)
Enron32/32 (100%)1/1 (3%)1/1 (3%)1/1 (3%)4/1 (13%)
Reddit256/256 (100%)256/256 (100%)1/1 (<1%)1/1 (<1%)256/256 (100%)
Contacts512/512 (100%)512/512 (100%)1/1 (<1%)4/1 (1%)512/512 (100%)
Wikipedia128/128 (100%)128/128 (100%)1/1 (<1%)1/1 (<1%)32/32 (25%)
Flights256/256 (100%)256/128 (100%)1/1 (<1%)1/1 (<1%)256/256 (100%)

What a predictive direction encodes. Each direction is a pattern of destination-probability changes activated by the interaction context: who initiates the current interaction, and whom that source contacted most recently, jointly determine which destinations become more likely next. Formally, let SS be the source category, LL its previous-destination category, and FF the next-destination category; then

p(F∣S,L)−p(F)=p(F∣S)−p(F)+p(F∣S,L)−p(F∣S)⏟additional recent-interaction information.p(F\mid S,L)-p(F)=p(F\mid S)-p(F)+\underbrace{p(F\mid S,L)-p(F\mid S)}_{\text{additional recent-interaction information}}.

where p(F∣S)−p(F)p(F\mid S)-p(F) is source-conditioned preference. We project both components onto the leading predictive subspace (the first d^pred−1\widehat d_{\mathrm{pred}}-1 right singular vectors of the weighted residual matrix CC, Appendix A.1) and inspect their destination loadings and activating contexts. Direction A expresses differing interaction-partner preferences across sources, whereas Direction B expresses how the same source's destination preference changes with its most recent interaction; the two are cleanly separated by a within-source shuffle. Concretely, on Enron the leading direction (38% of subspace energy) has a positive group of 12 high-frequency partners of the source (loadings +0.18+0.18 to +0.31+0.31) and a negative group of 9 cross-group partners plus the tail bin (−0.22-0.22 to −0.14-0.14); it is activated by S∈{3,17,42}S\in\{3,17,42\} with history-side coefficients +0.41±0.06+0.41\pm0.06, and its source loading stays at 0.61→0.600.61\to0.60 under the shuffle. The second direction (21% of energy) shows the complementary behaviour: its positive and negative destination groups swap sign with LL (coefficient–LL correlation r=0.83r=0.83), and its energy falls from 0.210.21 to 0.030.03 after the same shuffle.

Across all eight datasets, keeping each source's interaction counts and the marginal of LL fixed while shuffling the LL–FF pairing within each source leaves the source-conditioned component 96%–99% intact (a change of only 1%–4%), reduces the recent-interaction component by 91%–97% (median 94%), and lowers the corresponding held-out predictive gain by 35% (31%–42%), in line with the 29%–46% share that component carries in the leading subspace. These results tie the content of each predictive direction to stable source-conditioned preference and recent-interaction-dependent transition information.

W3. Predictive dimension and sufficient parameter budgets.

Predictive dimension characterizes the task-relevant state complexity for a specified prediction target, representation family, and tolerance. Our estimator measures this quantity through the effective rank of a centered past–future conditional-distribution operator, selected using held-out Brier risk. Our theoretical characterization concerns predictive-state dimension; the connection to sufficient parameter budgets is established empirically through architecture-specific calibration. We therefore extend the evidence beyond PreDyG through cross-architecture capacity analysis and budget selection on unseen datasets, connecting independently estimated predictive dimension to architecture-specific parameter budgets and actionable capacity recommendations.

1. Cross-architecture validation. We extend the capacity analysis from PreDyG to DyGFormer, DyG-Mamba, and TGAT, retaining the same eight datasets, chronological splits, prediction task, and independently estimated predictive dimension. For each architecture–dataset pair, we scan configurations from under-capacity to an observed performance plateau. We define P0.05P_{0.05} as the smallest scanned parameter budget reaching at least 95% of that architecture’s best validation AP on the dataset.

Architectureρ(d^pred,P0.05)\rho(\widehat d_{\mathrm{pred}},P_{0.05}) ↑ρ(Nnodes,P0.05)\rho(N_{\mathrm{nodes}},P_{0.05})ρ(Nevents,P0.05)\rho(N_{\mathrm{events}},P_{0.05})Best-scan test AP (%) ↑Dimension-guided test AP (%) ↑Target met ↑Recommended budget / P0.05P_{0.05} ↓
PreDyG0.900.240.3196.896.48/81.20×
DyGFormer0.860.290.3696.295.67/81.30×
DyG-Mamba0.880.210.3396.396.08/81.25×
TGAT0.830.330.3889.889.17/81.35×

Correlations are calculated across datasets within each architecture. AP values are equally weighted means over eight datasets. Best-scan test AP uses the configuration selected by validation AP from the full scan; dimension-guided results use the leave-one-dataset-out procedure described below. Target attainment refers to the prespecified validation threshold, and budget ratios are medians across datasets.

Predictive dimension consistently tracks sufficient parameter budgets across all four architectures: its correlations range from 0.83 to 0.90, compared with 0.21–0.33 for node count and 0.31–0.38 for event count. Dimension-guided configurations achieve mean test AP within 0.3–0.7 percentage points of the full-scan selections, with median budget ratios of 1.20×–1.35× relative to P0.05P_{0.05}. These results connect independently measured predictive complexity to useful capacity across different temporal-graph architectures.

2. Budget selection on unseen datasets. For each architecture, we calibrate a dimension-to-budget mapping on seven datasets and use the held-out dataset’s predictive dimension to recommend a configuration. We repeat this procedure for all eight datasets, yielding 32 architecture–dataset evaluations. Capacity is selected through the source-calibrated mapping; the target capacity scan serves only as an evaluation reference. Node-count and event-count mappings follow the same procedure.

Budget-selection signalTarget met ↑Median recommended budget / P0.05P_{0.05} ↓Median test AP gap to best scan ↓Total compute saved vs. full scan ↑
Node count20/321.80×2.8 pp49%
Event count22/321.65×2.4 pp52%
Predictive dimension30/321.27×0.5 pp68%

Target attainment is assessed against the prespecified validation threshold. Test AP evaluates the configurations selected through the stated procedures. Total compute includes dimension estimation, calibration, and training under the stated reuse setting.

Dimension-guided selection meets the target in 30 of 32 cases, with a median test-AP gap of 0.5 percentage points and 68% less compute than a full scan. Compared with node-count and event-count guidance, it combines higher target attainment, lower budget overhead, and closer performance to the full-scan reference.

Together, these results connect data-side predictive complexity, architecture-specific parameter budgets, and capacity selection on unseen datasets. Predictive dimension provides a transferable capacity-selection signal, while architecture-specific calibration translates that signal into economical model configurations.

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

This paper posits that dynamic-graph prediction may require only a low-dimensional state, even when interaction histories are long. The authors estimate a predictive dimension by constructing a binned past–future probability table, removing the no-history marginal, truncating the residual via SVD, and selecting a rank that retains 95% of the observed predictive gain. They then introduce PreDyG, a compact predictor relying on recent interactions and neighborhood-interaction-frequency features. PreDyG achieves strong link-prediction performance on eight standard streams and four TGB datasets, using significantly fewer trainable parameters than several baselines.

Critical strengths
  1. PreDyG serves as a compelling lightweight baseline. It performs well in Tables 2–3, and the appendix further validates it under harder negative sampling. Ablation studies show that removing NIF substantially reduces AP, particularly on Enron, confirming that the model’s design has an identifiable source of value.
  2. The evaluation goes beyond simple comparisons of model width. The authors estimate a data-side quantity over chronological intervals and perturb dependencies within the event stream. These represent worthwhile attempts to empirically test the proposed theoretical explanation.
Critical weaknesses
  1. The measured rank is much narrower than the claimed intrinsic dimension. As written, Equation 2 takes an infimum over state maps and readouts without restricting their precision or complexity. Since a one-dimensional real state can encode a finite or countable history given arbitrary maps, the formal minimum requires a specified function class to be meaningful. Furthermore, the estimator uses at most 512 destination bins and represents history solely by the source bin and that source's previous destination bin. While this may be a useful task-specific statistic, it does not directly estimate the dimension required to predict from the full interaction history.
  2. Experiments do not yet disentangle low predictive dimension from easily reusable interaction patterns. Because PreDyG's NIF explicitly counts recent and shared neighbors, strong results on conventional streams and TGB datasets could reflect effective recency or repetition-based heuristics rather than a genuinely low-dimensional future state. Yi et al. (ICLR 2025 TGB-Seq) have noted excessive repeated edges and weak sequential demands in many earlier temporal-graph datasets, introducing TGB-Seq to test lower-repetition, more complex sequences. Although Appendix D.4 tests historical and inductive negative sampling, changing negatives does not alter the underlying event sequences. Without results on a benchmark like TGB-Seq or at least a breakdown of performance and estimated dimension for repeated versus genuinely new edges—the generality of the dimension principle remains unclear.
Questions for authors
  1. What restrictions on the state map and readout are necessary to make the formal dimension nontrivial? Would "predictive rank under the specified binning and history summary" more accurately describe the measured quantity?
  2. Can the authors evaluate PreDyG and the predictive-dimension estimate on TGB-Seq (or another low-repetition benchmark requiring sequential generalization) using its official MRR protocol? Please report results separately for repeated and previously unseen edges, and include recency/frequency or memory baselines. Does the low-dimensional saturation pattern persist when recent-neighbor reuse is less informative?
  3. Can a mapping from estimated rank to PreDyG size be learned on source datasets and transferred to new ones without a target-dataset capacity sweep? How does this approach compare to using a fixed small model or scale-based heuristics?
7 comments

W1/Q1: Formal definition and estimator scope.

(1) Definition. We agree that unrestricted maps and readouts allow one real number to encode history. We now fix the history summary HH and future partition FF and restrict predictions to a fixed marginal plus a linear residual readout: Qh,:=π⊤+z(h)⊤W,z(h)∈Rr,Q_{h,:}=\pi^\top+z(h)^\top W,\quad z(h)\in\mathbb R^r, where Qhf=P(F=f∣H=h)Q_{hf}=P(F=f\mid H=h) and π=P(F)\pi=P(F). For positive-probability contexts, the minimum dimension for exact reconstruction is rank⁡(C),C=diag⁡(ph)(Q−1π⊤).\operatorname{rank}(C),\quad C=\operatorname{diag}(\sqrt{p_h})(Q-\mathbf1\pi^\top). An rr-dimensional representation has rank at most rr; rank factorization attains this bound. Linear readout excludes arbitrary decoding in your counterexample.

"Effective predictive rank under the specified binning and history summary" therefore better describes our measurement. In practice, held-out Brier risk selects truncation after probability clipping and normalization. We retain d=r+1d=r+1: a fixed baseline plus rr residual directions. The baseline adds no history-dependent coordinate. The rank statement concerns exact linear reconstruction; empirical selection concerns the finite-sample procedure.

(2) Binning. We increase source/destination category budgets and candidate dimensions, keeping history and chronological splits fixed. Frequent identities remain separate; tail identities are pooled.

BudgetNon-empty destination bins (R/S/U/C)Allocated coordinatesRedditSocialEvoUCIContacts
512512/59/512/274512256 (50.0%)32 (6.3%)256 (50.0%)512
1,0241,024/59/1,024/2741,024256 (25.0%)32256 (25.0%)512
2,0482,048/59/1,899/2742,048256 (12.5%)32256 (12.5%)512

Entries show selected dd. Allocated coordinates include empty bins, which do not increase attainable rank. SocialEvo's 6.3% uses allocated coordinates, not non-empty bins. Destination category counts remain unchanged for SocialEvo and Contacts. Contacts' 512 is a grid label, not 511 effective directions; actual truncation is recorded in the run log.

Reddit and UCI retain d=256d=256 as resolution increases, with reported proportions falling from 50.0% to 25.0%, then 12.5% and 12.5%, respectively. This supports stability under the tested refinements.

(3) Richer history. With the future partition fixed, we use the previous two/four destinations and a cumulative summary of all pre-query events containing recency-weighted counts, time and local structure. This summary does not preserve the entire sequence.

History / metricRedditSocialEvoUCIContacts
Source + previous destination0.9331 / 2560.8997 / 320.9204 / 2560.9240 / 512
Source + previous 2 destinations0.9328 / 2560.8994 / 320.9198 / 2560.9233 / 512
Source + previous 4 destinations0.9324 / 2560.8991 / 320.9191 / 2560.9226 / 512
Cumulative + time + structure0.9320 / 2560.8989 / 320.9184 / 2560.9220 / 512
Original gain retained (%)97.898.696.497.1

Rows 1-4 report held-out Brier risk / selected dd. Gain retention is (R(1)−Rorig)/(R(1)−Rbest)(R(1)-R_{\mathrm{orig}})/(R(1)-R_{\mathrm{best}}), with no-history risks 0.9820/0.9560/0.9740/0.9910 (R/S/U/C). Predictors are selected on the middle 20%; gains share a baseline and are evaluated on the disjoint final 30% (Appendix A.1).

The original summary retains 96.4%-98.6% of the richer reference's gain. Richer histories improve risk by at most 0.0020, versus the original history's gain of 0.0489-0.0670. Thus, stable dimensions accompany limited information loss relative to tested alternatives. Table 1 additionally reports 1/1 under destination/source shuffling (4/1 for Contacts under source shuffling), and 32/16 and 16/16 for SocialEvo under temporal and pair perturbations, supporting estimator sensitivity.

The estimate concerns the specified history-future representation. These results support robustness on the evaluated streams, without assuming recovery of unrestricted full-history predictive dimension.

W2/Q2: Repeated interactions and generalization to low-repetition streams.

We thank the reviewer for suggesting this test. We evaluate both PreDyG and the predictive-dimension probe on TGB-Seq, combining official-protocol MRR, repeated/unseen-edge breakdowns, reuse baselines, and capacity sweeps.

(1) Prediction beyond edge reuse. We use ML-20M, Taobao, and Yelp with the official splits, candidate sets, and MRR protocol. All methods access only permitted pre-query history; configurations are selected on validation data. Recent-edge ranks candidates by their latest interaction with the source. Edge-frequency uses cumulative or windowed counts selected on validation data. Both use fixed tie handling. NIF-only applies a small readout to NIF features. The table reports MRR (%). Rows marked † reproduce published results from TGB-Seq Table 3; OOT denotes failure to finish one training epoch within 24 hours in that study.

MethodML-20MTaobaoYelp
Recent-edge2.0 ± 0.0016.3 ± 0.0024.2 ± 0.00
Edge-frequency2.0 ± 0.0016.9 ± 0.0024.7 ± 0.00
NIF-only16.8 ± 0.3148.0 ± 0.2950.0 ± 0.33
TGN†23.99 ± 0.2060.28 ± 0.5469.79 ± 0.24
DyGFormer†OOTOOT21.68 ± 0.20
PreDyG w/o NIF20.5 ± 0.3555.0 ± 0.2858.0 ± 0.32
PreDyG24.6 ± 0.2261.3 ± 0.2570.5 ± 0.24

PreDyG achieves higher mean MRR than the evaluated reuse baselines, NIF-only, and published TGN results, including on ML-20M, where edges do not repeat.

(2) Repeated versus unseen edges. A query is repeated only if its endpoint pair occurred strictly before the query time. We retain the official candidate sets and aggregate reciprocal ranks by query group. ML-20M contains only unseen edges. For Taobao and Yelp, R/U denote repeated/unseen queries. NR indicates that corresponding subgroup results are not reported in the cited table.

Method / test shareTaobao RTaobao UYelp RYelp U
Test share (%)16.683.425.274.8
Recent-edge88.0 ± 0.002.0 ± 0.0090.0 ± 0.002.0 ± 0.00
Edge-frequency92.0 ± 0.002.0 ± 0.0092.0 ± 0.002.0 ± 0.00
NIF-only64.0 ± 0.4644.8 ± 0.3465.0 ± 0.4845.0 ± 0.38
DyGFormer†NRNRNRNR
PreDyG w/o NIF71.0 ± 0.5051.8 ± 0.3373.0 ± 0.4653.0 ± 0.36
PreDyG94.0 ± 0.3254.8 ± 0.2993.0 ± 0.3462.9 ± 0.27

PreDyG retains gains over the reuse baselines and NIF-only on unseen pairs. NIF can still convey shared-neighborhood information for these pairs; its value and the capacity needed to exploit it are examined separately below. The improvements on unseen pairs demonstrate that PreDyG’s gains extend beyond recurring interactions to the prediction of new links.

(3) Predictive information and capacity saturation. We compare the reported probe with a richer summary of the latest 16 interactions, time gaps, and local structure, using the same 512 future categories. We follow the paper's chronological fitting and selection procedure. Here d includes the marginal component: d-1 residual directions are retained. G is the independent held-out Brier gain of the validation-selected reference predictor, multiplied by 100; retention is the gain retained at the selected d relative to that reference. O/E denote original/enriched summaries.

Datasetd (O/E)G (O/E)Retention % (O/E)
ML-20M32/641.8/2.495.4/95.7
Taobao32/642.5/3.295.6/96.0
Yelp32/642.1/2.895.3/95.8

Enriching history reveals additional predictive information and increases the selected dimension, while most measured gain remains concentrated in relatively few directions. These estimates describe the specified history/future representation.

We then vary PreDyG's state width m while fixing NIF, history length, other inputs, and aggregation, with the same training and validation-selection procedure for each width.

mML-20M MRRTaobao MRRYelp MRR
1621.557.866.9
3223.460.269.4
6424.661.370.5
12824.761.470.6
25624.861.470.9

The model comparisons above use m=64. Increasing width to 256 adds at most 0.4 MRR percentage points. This establishes saturation within the evaluated PreDyG family. The narrow margin over published TGN results, together with the saturation below, bounds the benefit of additional capacity within this representation. The data-side estimates support compact structure within the specified probe, while the capacity curves characterize this model family's attainable performance. We incorporate this scope into the revised claim: required complexity depends on the task and history representation, and the observed saturation is specific to the evaluated representation and architecture.

Q3: Can estimated rank guide PreDyG size on new datasets without a target capacity sweep?

Thank you for suggesting this direct test of practical capacity guidance. We evaluate whether a mapping calibrated on source datasets can select a compact PreDyG configuration for a held-out dataset.

(1) Source calibration and target selection. We use leave-one-dataset-out evaluation across the eight conventional benchmarks. Following the capacity analysis in the manuscript, the input is relative predictive dimension, x = d_hat/D_amb, under a fixed history-summary and partition protocol. Following §4.1 / Eq. (6), d_hat counts the no-history marginal as one coordinate. We estimate it using chronological subdivisions of each dataset's training events.

On source datasets, we define P_0.05 as the smallest tested parameter budget reaching 95% of the best validation AP in the capacity scan. This model-performance threshold is separate from the estimator's predictive-gain criterion. We fit log(P_0.05) = a + b log(x), with b >= 0, and select the smallest available configuration meeting the predicted budget, clipping to the candidate range. The configuration family, mapping and rounding rule are fixed using source data.

For each target, we estimate x from training events and train only the recommended configuration. Target validation data support early stopping; they do not select capacity or adjust the mapping. A separate target sweep provides a retrospective reference: its configuration is selected by validation AP and evaluated on the test set.

(2) Comparison with fixed and scale-based choices. We compare against a fixed small configuration selected on source datasets and mappings based on node count or event count. All mappings use the same functional form and source data. NIF, history sampling, other inputs and training protocols are shared. The table reports test AP (%) for four targets; all entries belong to the new evaluation protocol.

Selection ruleWikipediaRedditEnronUCI
Fixed small99.1299.0891.7596.20
Node count99.1699.1592.1096.38
Event count99.1899.1992.3296.50
Predictive dimension99.2799.3093.0596.91
Target-sweep reference99.3299.3693.2697.08

Dimension-guided selection stays within 0.05-0.21 AP percentage points of the sweep reference. Its gains over the fixed small configuration are 1.30 points on Enron and 0.71 on UCI. The comparison with scale-based rules shows that predictive structure provides useful information for capacity allocation.

(3) Performance-budget trade-off. We also include a fixed larger configuration selected on source data. The following summary covers the same four targets. Budget ratios use the source-calibrated predicted budget \hat P; values below one must be interpreted together with performance.

Selection ruleMean test-AP gap (pp)Median budget/P_0.05
Fixed small0.720.80
Fixed larger0.103.20
Node count0.561.85
Event count0.461.65
Predictive dimension0.121.20
Target-sweep reference0.001.60

The fixed larger model obtains a similar AP gap with a higher budget ratio. Dimension guidance adapts capacity across datasets, combining a 0.12 point mean gap with a 1.20 median budget ratio. The sweep reference can exceed P_0.05 because it selects maximum validation AP, whereas P_0.05 identifies the smallest configuration meeting the 95% threshold. Each transfer rule trains one target configuration, with repeated seeds; estimator overhead and one-time source calibration are recorded separately.

These results show that the source-calibrated mapping selects effective capacities for new datasets without a target capacity sweep, achieving a better accuracy–budget trade-off than the tested fixed-capacity and scale-based rules. The capacity sweeps in the original manuscript locate performance saturation, providing a reference for quantifying the recommended configurations’ accuracy gaps and parameter overhead, thereby validating the reliability of capacity recommendations.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Responses and Revisions

We sincerely thank all three reviewers (EKQQ, R59S, and eqUn) for their careful evaluations and constructive feedback. To facilitate the ongoing discussion, we summarize the main clarifications, revisions, and supporting evidence reported in our responses.

Formal Definition and Scope

  • Mathematical definition (EKQQ, R59S). We fix the history representation and future partition and restrict predictions to a fixed marginal plus a linear residual readout. Under these conditions, the minimum exact residual dimension equals the centered conditional-probability operator’s rank.
  • Estimator scope (EKQQ, R59S, eqUn). The estimator measures effective predictive rank under the specified representation, selecting the smallest candidate truncation retaining at least 95% of the best held-out predictive gain.

Historical Representation and Structural Dependencies

  • Sensitivity analysis (EKQQ, R59S). We evaluate category budgets up to 2,048 and richer historical summaries. Selected dimensions remain stable under the tested refinements on the evaluated conventional streams, while the original summary retains 96.4%–98.6% of the richer reference’s predictive gain.
  • Structural information (eqUn). We clarify that structure enters the framework through the chosen historical representation; the original compact probe does not explicitly encode multi-hop topology. On a controlled structural stream, enriching the context increases the estimated dimension from 1 to 32 and reduces capacity regret.
  • Interventions and interpretation (R59S). We extend dependency interventions to all eight conventional benchmarks and add targeted recent-context shuffles. Predictive-direction analysis distinguishes source-conditioned partner preferences from recent-interaction-dependent transitions.

Low-Repetition Evaluation and Capacity Saturation

  • TGB-Seq evaluation (EKQQ). Under official evaluation protocols, PreDyG achieves MRRs of 24.6%, 61.3%, and 70.5% on ML-20M, Taobao, and Yelp, respectively. Comparisons with recent-edge, edge-frequency, and NIF-only baselines, together with repeated/unseen-edge breakdowns, show gains beyond recurring interactions.
  • History enrichment and saturation (EKQQ). Richer histories increase the selected dimension from 32 to 64 on these three datasets. With inputs and aggregation fixed, increasing PreDyG’s width from 64 to 256 adds at most 0.4 MRR percentage points.

Capacity Guidance and Performance Attribution

  • Cross-architecture validation (R59S). We extend capacity analysis to DyGFormer, DyG-Mamba, and TGAT. Predictive dimension is positively associated with empirically sufficient budgets across the tested architectures, supporting architecture-specific capacity calibration.
  • Transfer to unseen datasets (EKQQ, R59S). Leave-one-dataset-out calibration recommends configurations without target capacity sweeps. Across four architectures and eight datasets, dimension-guided selection meets the prescribed validation target in 30 of 32 cases.
  • NIF and capacity effects (R59S, eqUn). Shared-NIF comparisons confirm the substantial contribution of neighborhood statistics. Complementary experiments show benefits from capacity guidance within DyGFormer and DyG-Mamba.

Contribution Positioning and Presentation

  • Contribution clarification (eqUn). We acknowledge established predictive-state and neighborhood-feature precedents and clarify our focus: estimating predictive complexity, examining capacity saturation, and evaluating a compact predictor.
  • Clarity and notation (eqUn). We reorganize Section 4, distinguish ambient dimension, residual rank, predictive dimension, and neural width, and provide a worked UCI example.

We hope this summary provides a useful overview of our responses and supporting evidence. We appreciate the reviewers’ time and welcome further discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.