{"id":"587ecc42-c794-4a61-839c-9ba1758f6e25","arxiv_id":"2506.08309","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"L-STEP learns time-evolving positional encodings for graph nodes via a learnable spectral filter and predicts links with MLPs only, matching or beating attention-based baselines on 13 temporal datasets.","lead":"Temporal link prediction models usually rely on expensive attention mechanisms to encode where nodes sit in a graph over time. This paper proposes L-STEP, a lightweight model that learns time-varying positional encodings using Fourier transforms and simple MLPs, and reports improved or matching accuracy on 13 benchmark datasets with lower runtime than recent attention-based models.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 is not established: the Appendix C proof silently assumes future positional encodings p^{L+1}≈p^1 and treats learned Eq. 3 encodings as ground-truth Laplacian eigenvectors, so the advertised 'without future topology' guarantee collapses.","rationale":"I read the paper in good faith. The empirical contribution is substantial: chronological 70/15/15 splits, three negative sampling strategies, five seeds, ablations against attention variants, and runtime comparisons support the claim that a simple MLP model with Fourier-filtered learned positional encodings is competitive on classic temporal link prediction benchmarks. The O(n) complexity argument is reasonable at the batch level. The problem is the theoretical headline. Theorem 4.1 is the only formal basis for the claim that LPE preserves graph properties from the spectral viewpoint and can represent future topology without future information. That theorem is not supported: the proof assumes p^{L+1}≈p^1, an unstated future-stationarity condition; it concerns ground-truth eigenvectors while the algorithm's stored p^t are learned Eq. 3 encodings; it bounds one approximate encoding against another rather than against the true future PE; and Lemma C.1's eigenvalues are off by a factor. The reader's weakest assumption captures part of this, but the Appendix C derivation is internally incomplete even under the stated premise because the future-substitution step is used before any estimate is made. A direct analytical re-derivation would settle this. If the authors withdraw or repair the theorem and align the abstract with Table 2, the empirical contribution is publishable as a method paper; hence the conditional verdict stands and no verdict change is needed.","tokens_in":42608,"tokens_out":11129,"duration_ms":139452,"concrete_test":"Independently re-derive the equality in Eq. 16 symbolically, keeping p^{L+1} as a free vector q instead of replacing it with p^1. The last block of Eq. 16 reduces to [p1...pL] L(R_L) F W_filter F^{-1} α only when q=p^1 (up to the stated slow-changing approximation); with general q, an extra (q−p^1)-dependent term appears. If that term is not controlled by the theorem's stated assumptions, the proof requires an explicit future-stationarity condition. The same re-derivation should also show whether any bound survives when p_j are the stored Eq. 3 encodings rather than Laplacian eigenvectors; if it does not, Theorem 4.1 does not justify the prose claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"L-STEP's central theoretical claim is Theorem 4.1: under a 'slowly changing' graph, the Eq. 2 approximate encoding at time t is within ε of the encoding at a future time t'', so it can represent future positional information without future topology. The Appendix C proof does not deliver this from the stated assumptions. First, the derivation of Eq. 16 replaces p^{L+1} with p^1 in the last coordinate: the term p_L−p_{L+1}+p_L−p_{L−1} becomes p_L−p_1+p_L−p_{L−1}. That substitution is exactly a future-stationarity assumption, p^{L+1}≈p^1, which is not part of the theorem's premise p_0≈...≈p^{t−1} and cannot be checked without peeking at the future. Second, the proof treats p_0,...,p_L as Laplacian eigenvectors of snapshots, but in L-STEP the stored encodings are produced by Eq. 3, an MLP update with tanh; no argument shows these learned vectors remain close to ground-truth eigenvectors, so a bound on eigenvector sequences does not transfer to the implemented sequence. Third, even a correct bound on ||ep^t−ep^{t''}|| would not show approximation to the true positional encoding of the future snapshot. Lemma C.1 also misstates ring-Laplacian eigenvalues as 2−cos(2πk/n) instead of 2−2cos(2πk/n), and the final bound (21) replaces an O(L^2) coefficient sum with 2L−2 without justification. The empirical method can stand on the experiments, but the advertised spectral-preservation guarantee is unsupported as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes L-STEP, a temporal link prediction model built from a Learnable Positional Encoding module (LPE) and a Node-Link-Positional Encoder, both using MLPs rather than attention. LPE applies a learnable Fourier-domain filter to a length-L history of per-node positional encodings, then pools the filtered sequence to form an approximate encoding for the current time; stored encodings are updated after ground-truth links are revealed. The paper claims a spectral-preservation theorem (Theorem 4.1) saying that under a \"slowly changing\" temporal graph the approximate encoding remains close to its future values without using future topology, an O(n) complexity analysis, and strong empirical results on 13 classic datasets under transductive and inductive settings with three negative sampling strategies, plus competitive results on two large TGB datasets.","tokens_in":42956,"tokens_out":4792,"duration_ms":59450,"significance":"If the empirical results are taken at face value, the contribution is practically significant: a lightweight MLP-only model with per-step complexity O(n(Llog L+K+tgap)) that reaches or beats attention-based state-of-the-art on the benchmark suite is a useful data point for the field. The experimental protocol is solid, including chronological 70/15/15 splits, five seeds, validation-based early stopping, three negative sampling strategies, ablation studies, and runtime comparisons. However, the theoretical guarantee advertised in the abstract and Section 4 is not established by the proof in Appendix C, so the paper's significance currently rests on the experiments rather than on the spectral-preservation claim. The theoretical claim needs substantial repair before the paper can be accepted in its advertised form.","major_comments":[{"comment":"The proof's first displayed identity substitutes p^{L+1} with p^1 in the last coordinate, turning p_L - p_{L+1} + p_L - p_{L-1} into p_L - p_1 + p_L - p_{L-1}. This is an additional future-stationarity assumption p^{L+1} ≈ p^1, which is not entailed by the theorem premise p^0 ≈ ... ≈ p^{t-1} and cannot be checked without looking at future topology. Since the advertised no-future-topology guarantee depends on this step, Theorem 4.1 is not established as stated.","section":"Appendix C, Eq. (16)"},{"comment":"The proof assumes p^0, ..., p^L are Laplacian eigenvectors of their respective graph snapshots, but in the implemented model the stored encodings are produced by Eq. (3), an MLP update with tanh, after initializing with Laplacian eigenvectors. No argument shows that these learned vectors remain close to ground-truth eigenvectors over time, so a bound on eigenvector sequences does not transfer to the sequence actually stored and used by L-STEP.","section":"Appendix C, proof of Theorem 4.1"},{"comment":"Even if the inequality ||ep^{L+1} - ep^{L+2}|| were proved correctly, the theorem's advertised conclusion is that the encoding \"can be a good representation of the positional information of future graph snapshots.\" The derived bound compares two approximate encodings, not an approximate encoding with the true positional encoding of the future snapshot. This gap between the theorem's statement and its proof is not addressed in Appendix C.","section":"Section 4, Theorem 4.1 and Appendix C"},{"comment":"Lemma C.1 states the ring-graph Laplacian eigenvalues as 2 - cos(2πk/n); the correct eigenvalues for the unnormalized ring Laplacian are 2 - 2cos(2πk/n). This error propagates into the diagonal matrix Λ used in Eqs. (17)-(18) and into the filter contraction condition. In addition, the derivation of Eq. (21) silently imposes the normalization sum α_j = 1 and the filter condition sum_i |(ΛW_filter)_i| < 1 without listing them as assumptions in Theorem 4.1, and the factor (2L-2) is asserted rather than derived from the preceding O(L^2) coefficient sum.","section":"Appendix C, Lemma C.1 and Eq. (21)"},{"comment":"The theorem's premise p^0 ≈ ... ≈ p^{t-1} asserts approximate constancy of ground-truth positional encodings over time, while the conclusion is about approximate encodings; the proof additionally needs p^{L+1} ≈ p^1. The relation between the premise and the conclusion is therefore close to assuming the desired stability behavior rather than deriving it from graph dynamics. At minimum, the theorem must separate ground-truth eigenvalue stability from approximation-error stability, and the proof must state which of these is actually used at each step.","section":"Section 4, Theorem 4.1"}],"minor_comments":[{"comment":"The notation in Theorem 4.1 uses t and t'', while the proof switches to ep^{L+1} and ep^{L+2}; please align these notations and define how t'' relates to L and the indexing of snapshots.","section":"Section 4 and Appendix C"},{"comment":"The indices for the weights α are inconsistent: the text says α_1, ..., α_{t-1} in one place and α_1, ..., α_L in the following display. Please define α once and use consistent indexing throughout the proof.","section":"Eq. (20) and Eq. (21)"},{"comment":"The subsection title says \"parameter analysis for α_neg\" but the table reports results for α_pe; the title and the accompanying text should be corrected.","section":"Appendix H.5.5"},{"comment":"The abstract says 10 algorithms, while Section 5.1 lists 9 baseline methods plus L-STEP; please state the count consistently so that the comparison is unambiguous.","section":"Abstract and Section 5.1"},{"comment":"The text says LPE \"does not peek\" at current topology, but Algorithm 3 reveals ground-truth links after prediction and updates p^t via Eq. (3). Please clarify that the no-peek property applies only to the forward computation of ep^t, not to the training-time update of stored encodings.","section":"Section 3.1 and Algorithm 3"}],"recommendation":"major_revision","confidential_remarks":"The empirical contribution is substantial and the evaluation is careful, but the theoretical section is the main obstacle. If the authors can either repair Theorem 4.1 under explicit assumptions (including the future-stationarity requirement) or downgrade it to a clearly labeled heuristic, the paper could be acceptable on the strength of the experiments. I see no issue with the novelty disclosure, though the citation for Lemma C.1 should be completed. I would not reject on the empirical merits."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The empirical core of this paper is real and useful. The authors propose L-STEP, an MLP-only temporal link predictor with a learnable positional encoding obtained by filtering the DFT of past positional encodings, and they evaluate it carefully: 13 datasets, chronological 70/15/15 splits, five seeds, three negative sampling strategies, per-dataset hyperparameters, and ablations including the MLP-vs-attention comparison. The results are strong: L-STEP matches or beats attention-based methods on most datasets, often with large margins, and the linear node-complexity argument is plausible. As a method contribution, this is exactly the kind of simple, reproducible baseline the community needs.\n\nWhere the paper falls down is the theory. Theorem 4.1 claims that without peeking at future topology, the approximate encoding stays close to the future encoding under a \"slowly changing\" graph. The Appendix C proof does not establish that. The step in Eq. 16 silently replaces p^{L+1} with p^1, which is a future-stationarity assumption not present in the theorem's premise. The proof also treats the stored p's as Laplacian eigenvectors, but in L-STEP they are outputs of the Eq. 3 MLP update with tanh; no argument shows those learned vectors remain close to true eigenvectors. Lemma C.1 misstates ring-Laplacian eigenvalues as 2−cos(2πk/n) instead of 2−2cos(2πk/n), and the final bound (21) replaces an O(L^2) coefficient sum with 2L−2 without justification. Even if those were fixed, the derived inequality bounds the distance between two approximate encodings, not the distance to the true future positional encoding. The prose conclusion about representing future graph topology does not follow.\n\nThere are smaller overclaims. The abstract says L-STEP obtains \"leading performance\" on TGB, but Table 2 shows rank 2 on tgbl-review and rank 3 on tgbl-coin. The code availability statement in the abstract (public GitHub link) contradicts Appendix I.2 (\"code will be released upon paper's publication\"). Some \"substantial margin\" prose for historical NSS is also looser than the tables, which show mixed results.\n\nDespite the theoretical problems, this paper deserves a serious referee. The empirical method is valuable, the protocol is solid, and the practical finding -- that a Fourier-filtered learnable PE plus MLPs can beat attention models on these benchmarks -- is important. The authors should be asked to restate or withdraw Theorem 4.1, fix Lemma C.1, align the abstract with Table 2, and resolve the code contradiction. I would bring this to a reading group and would cite it for the method.","headline":"L-STEP's empirical contribution is solid and worth engaging with, but its advertised spectral-preservation theorem is not supported by the proof in Appendix C, and the abstract overstates the TGB results.","tokens_in":43615,"tokens_out":1897,"would_cite":true,"duration_ms":25925,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"L-STEP learns node positions from past snapshots with a learnable Fourier filter, proving MLPs can match attention-based transformers on temporal link prediction.","keywords":["temporal link prediction","positional encoding","learnable positional encoding","discrete Fourier transform","spectral graph theory","graph neural networks","temporal graphs"],"falsifier":"Train L-STEP on a temporal graph whose Laplacian positional encodings change abruptly between consecutive snapshots (for example, a graph where central hubs appear and vanish at every timestamp), and record $\\|\\hat{p}_u^t - \\hat{p}_u^{t''}\\|_2$ along with test AP; Theorem 4.1 provides no bound in this regime, and the model's edge over DyGFormer should shrink or disappear. A second check: during training, compute $\\sum_i |(\\Lambda W_{\\text{filter}})_i|$ on validation snapshots; whenever this quantity exceeds 1, the derived bound in Eq. 21 no longer holds even on slowly changing graphs, so the spectral-preservation claim is directly testable.","tokens_in":42244,"feed_emoji":"🔗","tokens_out":7798,"duration_ms":78364,"temperature":0.7,"pith_summary":"The paper claims that a learnable, time-evolving positional encoding can carry enough spatial-temporal information for temporal link prediction that a simple MLP-only model matches or beats transformer-based state of the art. The proposed model, L-STEP, approximates a node's current positional encoding by applying a Discrete Fourier Transform to its recent past encodings, filtering in the frequency domain with a learned complex filter, and pooling the result with learned weights. The paper proves a spectral-preservation bound (Theorem 4.1): on graphs whose Laplacian positional encodings change slowly, the approximate encoding stays close to the encoding of future snapshots, so the model does not need to see the future topology to represent it. Empirically, L-STEP reports the best average rank against ten algorithms on thirteen classic datasets under several sampling strategies, and competitive results on the large-scale TGB benchmark, with complexity linear in the number of nodes rather than edges. The central bet is that learnable spectral filtering of past positions is a cheaper substitute for attention.","feed_headline":"MLPs beat graph transformers on temporal link prediction","feed_subtitle":"L-STEP learns evolving node positions from past snapshots and tops 13 temporal link-prediction benchmarks.","key_machinery":"The Learnable Positional Encoding (LPE) module: it treats a node's past positional encodings as an $L$-length time series, applies the Discrete Fourier Transform, multiplies by a learnable complex-valued filter $W_{\\text{filter}} \\in \\mathbb{C}^{d_P \\times L}$ to suppress noise in the frequency domain, transforms back with the inverse DFT, and sum-pools with learnable weights to produce $\\hat{p}_u^t$. The Node-Link-Positional Encoder then combines these with node and edge features via MLPs only. The spectral argument rests on the fact that the Fourier basis diagonalizes the ring-graph Laplacian (Lemma C.1), which lets the proof rewrite the filtering operation as an application of the ring Laplacian $L(R_L)$ followed by $\\Lambda W_{\\text{filter}}$; the bound then follows from the slow-change assumption plus the imposed filter bound $\\sum_i |(\\Lambda W_{\\text{filter}})_i| < 1$ and normalization $\\sum_j \\alpha_j = 1$.","core_discovery":"L-STEP's central claim is that positional encoding for temporal graphs can be learned rather than fixed: given the sequence of a node's positional encodings over the L most recent timestamps, applying the DFT, multiplying by a learnable complex filter $W_{\\text{filter}}$ in the frequency domain, applying the inverse DFT, and pooling with learnable weights yields an approximate encoding $\\hat{p}_u^t$ that preserves the graph's spectral structure. Theorem 4.1 states that if the ground-truth Laplacian positional encodings are approximately constant across snapshots ($p^0 \\approx \\cdots \\approx p^{t-1}$), then $\\|\\hat{p}_u^t - \\hat{p}_u^{t''}\\|_2 \\le \\varepsilon$ with $\\varepsilon$ depending on $L$, which the paper interprets as showing that the learned encoding represents future positional information without peeking at future topology. The paper also claims that MLPs, not attention, suffice to exploit this encoding, and that L-STEP achieves the best average rank on 13 temporal link prediction datasets in transductive and inductive settings while having $O(n)$ complexity.","pith_inferences":["The proof's slow-change condition is essentially a smoothness assumption on graph spectra; a natural testable extension is to measure, on each dataset, the drift in Laplacian positional encodings across snapshots and check whether L-STEP's margin over baselines correlates with that drift.","If the claim that MLPs fully exploit the encoding is right, the same LPE scheme could replace attention in other temporal graph tasks beyond link prediction, such as node classification or edge regression on continuous-time graphs, at reduced cost.","The bound in Theorem 4.1 concerns the distance between two approximate encodings at different times, not the error with respect to the true current encoding; an honest check would compute $\\|\\hat{p}_u^t - p_u^t\\|_2$ on real data and compare it to the derived $\\varepsilon$ bound.","The learnable filter imposes a hand-chosen spectral radius condition ($\\sum_i |(\\Lambda W_{\\text{filter}})_i| < 1$) that is not enforced during training; monitoring this quantity during training would show whether the theorem's regime is actually entered."],"forward_implications":["If Theorem 4.1 holds, L-STEP can produce useful positional encodings for future snapshots without recomputing a Laplacian eigendecomposition at each timestamp, avoiding $O(|V|^3)$ or $O(|E|^{3/2})$ per-step costs.","The $O(n(L\\log L + K))$ per-step complexity with constants $L$, $K$, and $t_{\\text{gap}}$ independent of $n$ shows that node-based, rather than edge-pair-based, aggregation can suffice for temporal link prediction, contrasting with the co-occurrence design of DyGFormer and FreeDyG.","On the 13 classic datasets, the reported average ranks (e.g., 1.85 for transductive AP) imply that an MLP-only predictor on this encoding is competitive or better than attention-based models, so attention may not be the load-bearing component in temporal link prediction performance.","The robustness test replacing Laplacian PE initialization with Random Walk PE indicates that the LPE scheme is not tied to any specific initial positional encoding.","On TGB, the 2nd and 3rd place ranks on tgbl-review and tgbl-coin suggest the approach transfers to graphs with millions of edges."],"supporting_citations":[{"why":"Supplies the DFT/IDFT formalism that the LPE module applies to past positional encodings.","marker":"(Sundararajan, 2001)"},{"why":"Precursor learnable positional encoding over static structure; also provides the Random Walk PE used in the initialization-robustness test.","marker":"(Dwivedi et al., 2022)"},{"why":"Defines the Laplacian-eigenvector positional encoding that L-STEP uses to initialize its encodings.","marker":"(Ramp´asek et al., 2022)"},{"why":"Provides the cosine time encoder $f_T(t)=\\cos(t\\omega)$ and the TGAT attention baseline.","marker":"(Xu et al., 2020)"},{"why":"Supplies the 13 datasets and the three negative sampling strategies used in evaluation.","marker":"(Poursafaei et al., 2022)"},{"why":"GraphMixer, the MLP-only baseline that supports the claim that attention may be unnecessary.","marker":"(Cong et al., 2023)"},{"why":"DyGFormer, the transformer SOTA whose co-occurrence scheme L-STEP's $O(n)$ complexity is contrasted against, and source of the data splits and training protocol.","marker":"(Yu et al., 2023)"},{"why":"FreeDyG, the Fourier-transform baseline compared in complexity, runtime, and performance.","marker":"(Tian et al., 2024)"},{"why":"Provides the TGB benchmark used for the large-scale leaderboard evaluation.","marker":"(Gastinger et al., 2024)"}],"fun_headline_variants":["L-STEP learns temporal node positions, beats SOTA on 13 link benchmarks","DFT-based encoding: MLPs match transformers for temporal link prediction","Fixed encodings fail: L-STEP learns spatial-temporal positions for links","Learnable positional encoding boosts temporal link prediction accuracy","Spatial-temporal encoding: L-STEP outperforms on 13 datasets with less time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee that the learned encoding carries future positional information holds only when the graph's Laplacian positional encodings stay nearly unchanged across consecutive snapshots (the 'slowly changing' assumption), and the proof additionally requires the trained filter's weighted spectrum to stay below 1 and the pooling weights to sum to 1; the theorem also bounds the gap between two approximate encodings, not the gap between an approximate and the true encoding.","fun_headline_variants_meta":{"raw":{"variants":["L-STEP learns temporal node positions, beats SOTA on 13 link benchmarks","DFT-based encoding: MLPs match transformers for temporal link prediction","Fixed encodings fail: L-STEP learns spatial-temporal positions for links","Learnable positional encoding boosts temporal link prediction accuracy","Spatial-temporal encoding: L-STEP outperforms on 13 datasets with less time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000838,"raw_usage":{"total_tokens":3722,"prompt_tokens":1085,"completion_tokens":2637,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":701,"completion_tokens_details":{"reasoning_tokens":2540}},"tokens_in":701,"tokens_out":2637,"duration_ms":22400,"temperature":1.0,"reasoning_tokens":2540,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:16:24.981176+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train L-STEP on a temporal graph whose Laplacian positional encodings change abruptly between consecutive snapshots (for example, a graph where central hubs appear and vanish at every timestamp), and record $\\|\\hat{p}_u^t - \\hat{p}_u^{t''}\\|_2$ along with test AP; Theorem 4.1 provides no bound in this regime, and the model's edge over DyGFormer should shrink or disappear. A second check: during training, compute $\\sum_i |(\\Lambda W_{\\text{filter}})_i|$ on validation snapshots; whenever this quantity exceeds 1, the derived bound in Eq. 21 no longer holds even on slowly changing graphs, so the spectral-preservation claim is directly testable.","supporting_citations":[{"cited_title":"The discrete Fourier transform: theory, algorithms and applications","cited_arxiv_id":null,"evidence_quote":"Supplies the DFT/IDFT formalism that the LPE module applies to past positional encodings."},{"cited_title":"P., Luu, A","cited_arxiv_id":null,"evidence_quote":"Precursor learnable positional encoding over static structure; also provides the Random Walk PE used in the initialization-robustness test."},{"cited_title":"P., Luu, A","cited_arxiv_id":null,"evidence_quote":"Defines the Laplacian-eigenvector positional encoding that L-STEP uses to initialize its encodings."},{"cited_title":"Towards better evaluation for dynamic link prediction","cited_arxiv_id":null,"evidence_quote":"Supplies the 13 datasets and the three negative sampling strategies used in evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GraphMixer, the MLP-only baseline that supports the claim that attention may be unnecessary."},{"cited_title":"Freedyg: Frequency enhanced continuous-time dynamic graph model for link prediction","cited_arxiv_id":null,"evidence_quote":"FreeDyG, the Fourier-transform baseline compared in complexity, runtime, and performance."}],"review_version":1}