- 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, denotes both destination nodes and feature dimensions, while 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 . 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
Part 2/3
W2: History, structure, and frequency grouping.
(1) Historical and structural context. The general definition permits a history map 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 interactions per endpoint, with configurable , 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.
| Dataset | History setting | Held-out Brier gain | Capacity regret | |
|---|---|---|---|---|
| SocialEvo | Reported context | 5.6 | 32 | 0.7 |
| SocialEvo | + time | 4.4 | 32 | 0.5 |
| SocialEvo | Full history + structure | 5.7 | 32 | 0.4 |
| Reported context | 4.9 | 256 | 0.8 | |
| + time | 5.2 | 256 | 0.6 | |
| Full history + structure | 5.0 | 256 | 0.5 | |
| Controlled structural stream | Reported / full history + structure | 0.3 / 1.8 | 1 / 32 | 4.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 retains the 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 partition | Rare-identity event share | /categories | Capacity regret |
|---|---|---|---|
| , one tail category | 11% | 128/256 | 0.9 |
| , one tail category | 5% | 256/512 | 0.8 |
| , structural tail groups | 5% | 256/512 | 0.6 |
A shared tail category is a computational grouping, not predictive equivalence: it may mix distinct source preferences or future destinations. Increasing changes Reddit’s absolute estimated dimension, so the partition must accompany any reported dimension. At the matched 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.
Part 3/3
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 (%).
| Backbone | Capacity | Without NIF | With NIF |
|---|---|---|---|
| DyGFormer | Original | 91.80 | 95.76 |
| DyGFormer | Guided | 92.15 | 96.15 |
| DyG-Mamba | Original | 92.10 | 96.14 |
| DyG-Mamba | Guided | 92.40 | 96.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:
| Method | Wikipedia AP | LastFM AP | UCI AP |
|---|---|---|---|
| DyGFormer | 98.82 | 93.00 | 95.76 |
| + guidance | 98.95 | 93.25 | 96.15 |
| DyG-Mamba | 99.08 | 93.57 | 96.14 |
| + guidance | 99.15 | 93.75 | 96.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.
Part 1/3
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=512 denotes the number of coordinates in the future-probability vector, whose ambient space is R512. 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 d includes the baseline component and d−1 residual directions; hence, d=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,v for source and destination nodes, L for history length, d for candidate predictive dimension, r=d−1 for retained residual directions, m for channel width, and P 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 Q and no-history marginal π yield
Chf=ph(Qhf−πf),
and how retaining d−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}. The retained gain is
G(d)=R(1)−minj∈DR(j)R(1)−R(d),
where R(d) is selection-split Brier risk and 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.