{"id":"a6dcbd53-9e4a-42f9-8d93-4d44c2d20994","arxiv_id":"2504.20430","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"LLPE applies learnable Chebyshev weights to the full Laplacian spectrum so graph positional encodings capture heterophilous as well as homophilous structure, improving node classification accuracy.","lead":"This paper proposes a new graph positional encoding, LLPE, that learns weights over all Laplacian eigenvectors and eigenvalues to capture structure in both homophilous and heterophilous graphs. The authors show that standard Laplacian encodings can miss heterophilous structure and that LLPE improves node classification accuracy on 12 benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3 proves expressivity only for d=n, while the deployed LLPE fixes d=128; the central approximation guarantee does not cover the method actually evaluated.","rationale":"The reader's weakest assumption is exactly the gap between the d=n proof of Theorem 4.3 and the d=128 setting used in experiments. My stress-test confirms this is the most load-bearing concern: Theorem 4.3 is the only formal link between LLPE's design and its claimed expressive advantage, and the empirical section uses d=128 throughout, so without a fixed-dimension transfer result the core claim is supported only by experiments. The additional r(lambda) versus r(lambda)^2 mismatch in the proof of Theorem B.6 is a concrete internal inconsistency that reinforces the need for a careful re-derivation, though it is likely repairable by approximating sqrt(r). The paper does have real supporting evidence: a broad evaluation across 12 benchmarks, multiple base models, code availability, and sensitivity analyses; these should not be discounted. However, they do not close the expressivity gap between theory and the deployed method. Conditioning acceptance on a corrected theorem for fixed d, or on an explicit approximation bound that covers d=128, is the appropriate outcome. This does not change the reader's conditional verdict, so no move to ACCEPT or REJECT is warranted.","tokens_in":30217,"tokens_out":6638,"duration_ms":75422,"concrete_test":"On a small graph with known eigendecomposition, e.g., Cora or a controlled SBM, compute an exact target distance matrix f_r(i,j) for a nontrivial spectral function, such as r(lambda)=1/lambda on nonzero eigenvalues. Fit LLPE with d=128 and M in {64,128} by directly minimizing the sum of squared errors between ||P[i]-P[j]||_2 and f_r(i,j) over all node pairs, and repeat with d=n under otherwise identical training. If the d=128 approximation error is substantially above the d=n error, then the fixed-dimension expressivity gap is real and Theorem 4.3 does not transfer to the evaluated configuration. In parallel, re-derive Eqs. (44)-(46): if the proof is only consistent when h approximates sqrt(r(lambda_j)) rather than r(lambda_j), the theorem statement and proof need correction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central expressivity result does not cover the method actually evaluated. Theorem 4.3 / Theorem B.6 sets output dimension d=n; each of the n columns of W_LLPE is a Chebyshev approximation to a narrow Gaussian bump isolating one eigenvalue lambda_j, so P=U W can realize the diagonal spectral weighting needed for f_r. In the deployed LLPE, d=128 (Appendix D.2). For n>128, W is n x 128, so the Gram matrix W W^T has rank at most 128, while representing f_r^2 for arbitrary r requires a rank-n diagonal Gram matrix diag(r(lambda)). The theorem therefore gives no approximation guarantee for the d=128 configuration used in all experiments, and no replacement theorem is supplied. There is also an internal proof mismatch: the proof approximates h(lambda) ~ r(lambda_j) exp(-(lambda-lambda_j)^2 C_max), which makes P ~ U diag(r(lambda)) and the squared encoding distance contain r(lambda)^2, not r(lambda) as in Definition 4.2; the displayed bound in Eqs. (44)-(46) drops this square. This is fixable by approximating sqrt(r) instead, but as written Theorem 4.3 is not established. The headline empirical gains, up to 35% on synthetic and 14% on real-world graphs, therefore rest on an unproven expressivity premise for fixed d.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Laplacian positional encodings (LPEs) for node classification on heterophilous graphs. It first shows (Section 3) that on heterophilous SBMs the last eigenvectors of the graph Laplacian, not the first k, recover the communities, so standard LPEs fail. It then proposes LLPE, which forms P = U W_LLPE where W_LLPE is an n×d matrix whose entries are learnable Chebyshev polynomials evaluated at the eigenvalues, thus weighting all eigenvectors. The main theoretical claims are: (i) an expressivity theorem (Theorem 4.3) stating that LLPE can approximate any spectral distance f_r of the form f_r(i,j)^2 = Σ_k r(λ_k)(u_k[i]-u_k[j])^2; (ii) a Rademacher-complexity bound (Theorem 4.4) for the Chebyshev function class; and (iii) an approximate large-graph variant using the first and last k eigenpairs. Empirically, LLPE is evaluated on 12 benchmarks with MLP, GraphSAGE, and a full graph transformer, reporting up to 35% and 14% accuracy improvements over baselines on synthetic and real graphs, respectively.","tokens_in":30575,"tokens_out":9692,"duration_ms":97909,"significance":"The paper addresses a real and under-studied problem: positional encodings for heterophilous graphs. The SBM analysis connecting heterophily to the high end of the Laplacian spectrum is clear and useful, and the proposed LLPE is simple, scalable, and empirically strong: it obtains the best average rank on almost every benchmark and shows consistent gains over LPE-FK, including on large graphs. The theoretical framework linking full-spectrum PEs to spectral distances (Definition 4.2) is a valuable step. However, the central expressivity theorem is not established as stated (r vs r^2 mismatch) and, more importantly, the theorem that is proved (d=n) does not cover the deployed configuration (d=128), so the theoretical justification for the headline empirical results is currently missing. The generalization analysis is also limited to a univariate polynomial class rather than the end-to-end classifier. These are correctable in revision but are load-bearing.","major_comments":[{"comment":"The proof of Theorem 4.3 is not internally consistent. The construction sets h(λ;θ_j) to approximate f_j(λ)=r(λ_j)exp(-C_max(λ-λ_j)^2), so the j-th column of W_LLPE is approximately r(λ_j) times a bump that is 1 at λ_j and 0 elsewhere. Consequently P=UW_LLPE ≈ U diag(r(λ_1),...,r(λ_n)), and the squared distance between rows i and j is approximately Σ_k r(λ_k)^2(u_k[i]-u_k[j])^2, which is not f_r(i,j)^2 = Σ_k r(λ_k)(u_k[i]-u_k[j])^2 as claimed. The displayed chain (44)-(46) replaces the approximation by r(λ_k) plus an ε term, thereby dropping the square; that step does not follow from the stated construction. The theorem is repairable by choosing the bump amplitude to be sqrt(r(λ_j)) rather than r(λ_j), but as written the proof does not establish the statement. The proof also does not control the overlap of the Gaussian bumps when eigenvalues are close, since C_max and M are not chosen relative to the minimal spectral gap of G; this is another gap in the same argument.","section":"4.2 / Appendix B.2, Theorem 4.3 and Eqs. (43)-(46)"},{"comment":"The expressivity guarantee does not cover the configuration used in all experiments. Theorem B.6 (main text Theorem 4.3) sets d=n, with one Chebyshev column per eigenvalue. In the experiments, Appendix D.2 fixes d=128. For n>128, P=UW_LLPE has W_LLPE∈R^{n×128}, so the Gram matrix W_LLPE W_LLPE^T has rank at most 128, whereas representing f_r^2 for arbitrary r from Definition 4.2 requires a diagonal Gram matrix diag(r(λ)) of rank up to n. Thus no statement in the paper guarantees that the fixed-dimensional LLPE evaluated in Section 5 can approximate the class of distances in Theorem 4.3. This is load-bearing because the abstract and Section 5 attribute the empirical gains (up to 35% and 14%) to LLPE's expressivity, but the proved expressivity is for a different, larger model.","section":"4.2 / Appendix D.2"},{"comment":"The Rademacher-complexity result is for the univariate function class H_LLPE = {λ→Σ_m θ_m \\tilde T_m(λ)}, not for the hypothesis class of the node classifier that consumes the LLPE encodings. The theorem therefore does not establish the paper's claim that 'LLPE exhibits the best statistical generalization among other designs' (Section 4, opening paragraph) or that LLPE as a positional encoding generalizes better than LPE-FK, SAN-PE, or RWSE. To support that claim, one would need a bound on the empirical Rademacher complexity of the composed GNN/classifier with LLPE input, or at least an end-to-end bound that incorporates the l1/l2 regularization on the columns of W_LLPE that is actually used in training (Appendix D.2). As stated, Theorem 4.4 is a bound on a component function class and should be presented as such.","section":"4.3 / Theorem 4.4"}],"minor_comments":[{"comment":"The statement of Theorem 3.2 says the 'first nontrivial k eigenvectors' do not recover the communities, but the proof shows that any k−1 eigenvectors from the eigenvalue-1 eigenspace cannot do so; the statement should be adjusted to 'first k−1 nontrivial eigenvectors' or 'first k nontrivial eigenvectors' with a matching proof.","section":"3.2 / Appendix A.2"},{"comment":"The caption says 'while LPE-FK does not' but the experiment is a comparison with LPE-FLK (first and last k eigenvectors), as stated in the text; the caption should use the same name as the text.","section":"Appendix C.1, Figure 5 caption"},{"comment":"The approximation order in Theorem B.4 is denoted n while the number of nodes is also n in the rest of the paper, and the number of derivatives is d while d is the output dimension of LLPE; this notation clash should be removed (e.g., use M for the series order and s for the number of derivatives).","section":"Appendix B.1, Theorem B.4"},{"comment":"No sensitivity analysis over the output dimension d is reported, although d is the only architectural parameter for which the theoretical expressivity theorem is silent; reporting accuracy for a few values of d (e.g., 32, 128, 256) would help the reader assess the practical dependence on this parameter.","section":"Appendix D.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be of interest to the AISTATS/ICLR-style audience for which it is formatted. The empirical study is careful and the proposed method is practical. The main obstacle is the mismatch between the proven representational statement and the evaluated model; I believe this is fixable and recommend a major revision rather than rejection. I also note that the authors list a code repository in the paper, but the checklist indicates that the code/data needed to reproduce the main results is not fully provided; the editors may want to ask for the complete experimental artifacts."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThis one is worth a serious look. The crispest new piece is Theorem 3.2: in a heterophilous SBM the last k−1 Laplacian eigenvectors recover the communities while the first k do not. It gives a principled reason to stop treating PEs as low-frequency objects. The LLPE design itself is simple—Chebyshev weights over the full spectrum—and the evaluation is broad: twelve datasets, three base models, multiple PE baselines, with believable gains on heterophilous and mixed benchmarks (Amazon-ratings, Tolokers, Questions), plus a nice quintile analysis showing the gains come from heterophilous neighborhoods inside Cora.\n\nThe soft spots are theoretical, not empirical. Theorem 4.3's proof has a concrete mismatch: the Gaussian bump h(λ)≈r(λ_j) gives P≈U diag(r(λ)), so the squared encoding distance is ∑ r(λ_k)^2(...), not ∑ r(λ_k)(...) as Definition 4.2 requires. The displayed bound silently drops the square. This is fixable—approximate sqrt(r) instead—but the theorem as written is not established.\n\nThe bigger gap is that the expressivity proof sets d=n, while every experiment uses d=128. For n>128 the encoding Gram matrix has rank at most 128, while f_r^2 for arbitrary r needs rank n. So the central approximation guarantee does not cover the deployed configuration. That does not kill the paper; the empirical results stand on their own. But the authors should either prove a finite-rank version with an explicit error depending on the spectral tail or the class of r, or run d=n on small graphs and see whether the theory is what drives the gains. The Rademacher bound also has a small scaling error in the lower bound (factor n^{1/2}), though the upper bound is the one that matters.\n\nTwo administrative points: the checklist says no code/data while the text gives a GitHub link, and the medium-scale experiments claim full eigendecomposition at n≈25k without saying how that was done. Both should be fixed.\n\nWho should read it: anyone working on positional encodings or heterophily. I'd send it to reviewers with instructions to ask for the d=n gap and the proof mismatch to be handled; the empirical contribution deserves referee time.","headline":"The expressivity proof covers d=n while the deployed LLPE uses d=128, but the heterophily result and the broad empirical evaluation are solid enough to deserve a proper review.","tokens_in":31056,"tokens_out":6657,"would_cite":true,"duration_ms":70614,"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":"Learnable Laplacian encodings that weight the full spectrum recover a general class of spectral graph distances and improve node classification on heterophilous graphs by up to 35% on synthetic and 14% on real-world benchmarks.","keywords":["graph neural networks","positional encodings","heterophily","graph Laplacian","Chebyshev polynomials","spectral graph theory","node classification","graph transformers"],"falsifier":"Train LLPE with $d=128$ on a heterophilous graph where the class structure is known to live in a specific high-frequency eigenspace, then compare its node classification accuracy to that of a PE built directly from the exact label-correlated eigenvectors. A systematically large gap would falsify the practical expressivity claim, since the theory does not guarantee that the fixed-dimensional Chebyshev encoding can recover that subspace.","tokens_in":30056,"feed_emoji":"📈","tokens_out":7636,"duration_ms":65854,"temperature":0.7,"pith_summary":"This paper claims that standard graph positional encodings, especially Laplacian encodings built from the first few eigenvectors, miss the structure that matters on heterophilous graphs, where connected nodes tend to have different labels. To fix this, it introduces Learnable Laplacian Positional Encodings (LLPE), which weight all eigenvectors of the graph Laplacian through a learned function of the eigenvalues. The paper proves that LLPE can approximate a broad class of spectral graph distances, encompassing commute time, diffusion distance, and biharmonic distance, and that its generalization error is controlled by the norm of the learned coefficients. Across twelve benchmarks and several GNN backbones, LLPE improves node classification accuracy by up to 35% on synthetic graphs and up to 14% on real-world graphs, with the largest gains on heterophilous benchmarks and on nodes in locally heterophilous regions of globally homophilous graphs.","feed_headline":"Full-spectrum Laplacian encodings lift heterophilous node accuracy","feed_subtitle":"Learned weights over every Laplacian eigenvector let GNNs handle both same-label and opposite-label neighborhoods.","key_machinery":"The load-bearing object is the learned spectral weighting function $h(\\lambda; \\theta) = \\sum_{m=0}^{M} \\theta_m T_m(\\tilde{\\lambda})$, a truncated Chebyshev series evaluated at normalized Laplacian eigenvalues. Applied as $W_{\\mathrm{LLPE}}$ with entries $h(\\lambda_i; \\theta_j)$, it converts the full eigenvector matrix $U$ into a positional encoding whose per-node Euclidean distances approximate a target spectral distance. The mechanism carries the argument because the Chebyshev weights are smooth universal approximators on the spectrum, so the same encoding can act as a low-pass filter on homophilous graphs and a high-pass filter on heterophilous ones; the smoothness of the weights also keeps the hypothesis class low-dimensional, which the paper shows yields favorable Rademacher complexity.","core_discovery":"The central claim is that the eigenvectors of the graph Laplacian that carry the label-relevant structure shift with the homophily of the graph: in homophilous stochastic block models the first nontrivial eigenvectors encode communities, while in heterophilous block models it is the last eigenvectors that do so, and the first ones provably fail. Consequently, any positional encoding fixed to the low end of the spectrum cannot serve both regimes. LLPE removes this restriction by forming $P_{\\mathrm{LLPE}} = U W_{\\mathrm{LLPE}}$, where the columns of $W_{\\mathrm{LLPE}}$ are truncated Chebyshev series evaluated at the eigenvalues, so the network learns which spectral directions matter for the task. The paper proves (Theorem 4.3) that, with output dimension equal to $n$, LLPE can recover any distance of the form $f_r(i,j)^2 = \\sum_k r(\\lambda_k)(u_k[i] - u_k[j])^2$ for a nonnegative weight function $r$, thereby subsuming several known graph distances and capturing both low- and high-frequency structure. It also proves Rademacher-complexity bounds showing that the Chebyshev-coefficient norm, not the series order, controls generalization.","pith_inferences":["The expressivity theorem is proven with output dimension $d = n$ using narrow Gaussian bumps approximated by Chebyshev series; the practical LLPE fixes $d = 128$, so whether the fixed-dimensional encoding retains the full approximation power on real graphs is an empirical premise rather than a proven guarantee.","LLPE's learned weight curve $h(\\lambda)$ could be inspected post-hoc to identify which spectral bands actually mediate the label structure of a dataset, offering a diagnostic for heterophily that is not currently part of the paper.","The method's ability to capture both same-label and opposite-label proximity suggests it could transfer to link prediction or graph-level tasks in heterophilous settings, though the paper only evaluates node classification.","One could test LLPE against a directly supervised selection of eigenvectors (e.g., chosen by label correlation) on heterophilous benchmarks; a large gap would indicate that the Chebyshev parametrization, rather than spectral content, is the bottleneck."],"forward_implications":["LLPE can be added to any GNN or graph transformer without changing the model, improving accuracy on heterophilous benchmarks and on locally heterophilous regions of homophilous graphs.","Because LLPE provably approximates commute time, diffusion distance, and biharmonic distance, a single learned encoding can replace several purpose-built positional encodings.","The generalization bound implies that increasing the Chebyshev order $M$ improves expressivity without degrading generalization, as long as the learned coefficient norm stays small.","For large graphs, the approximate LLPE using only the first and last $k$ eigenvectors obtained by Arnoldi iteration preserves most of the benefit while keeping computation feasible.","Existing learnable PEs that process the full eigenvector matrix with MLPs or transformers scale poorly in the node count; LLPE's parameter count depends on $M$, not $n$, so it scales more gracefully."],"supporting_citations":[{"why":"Supplies the homophilous SBM theorem that the first k eigenvectors recover communities, which the paper extends to the heterophilous case.","marker":"(Abbe, 2018)"},{"why":"Provides the Laplacian concentration bound that lets the proofs transfer spectral statements from expected to observed graphs.","marker":"(Oliveira, 2009)"},{"why":"Supplies the Davis–Kahan sin Θ theorem used to bound eigenvector misclassification in the SBM proofs.","marker":"(Yu et al., 2015)"},{"why":"Establishes the minimax property of Chebyshev polynomials that yields the generalization bound.","marker":"(Rivlin, 2020)"},{"why":"Gives the exponential convergence rate for Chebyshev partial sums exploited in the distance-approximation theorem.","marker":"(Mason and Handscomb, 2002)"},{"why":"Defines the diffusion distance that serves as one of the distance notions subsumed by Theorem 4.3.","marker":"(Coifman and Lafon, 2006)"},{"why":"Defines the LPE-FK baseline and the graph transformer base model used in all experiments.","marker":"(Dwivedi and Bresson, 2021)"},{"why":"Provides the large non-homophilous benchmark datasets used to evaluate the scalable version of LLPE.","marker":"(Lim et al., 2021)"}],"fun_headline_variants":["Full-spectrum Laplacian encodings learn which eigenvectors matter for heterophily","Heterophilous GNNs? Learn the full Laplacian spectrum","Full-spectrum Laplacian encodings beat fixed low-frequency PEs on heterophily","Up to 35% accuracy gain on heterophilous graphs with full-spectrum Laplacian PE"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that LLPE can approximate any spectral distance assumes the output dimension equals the number of nodes, while the deployed version fixes a much smaller output dimension, and the paper gives no theorem that the reduced encoding still achieves the same approximation.","fun_headline_variants_meta":{"raw":{"variants":["Full-spectrum Laplacian encodings learn which eigenvectors matter for heterophily","Heterophilous GNNs? Learn the full Laplacian spectrum","Full-spectrum Laplacian encodings beat fixed low-frequency PEs on heterophily","Up to 35% accuracy gain on heterophilous graphs with full-spectrum Laplacian PE"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001209,"raw_usage":{"total_tokens":5007,"prompt_tokens":1001,"completion_tokens":4006,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":617,"completion_tokens_details":{"reasoning_tokens":3912}},"tokens_in":617,"tokens_out":4006,"duration_ms":25657,"temperature":1.0,"reasoning_tokens":3912,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:29:32.486595+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train LLPE with $d=128$ on a heterophilous graph where the class structure is known to live in a specific high-frequency eigenspace, then compare its node classification accuracy to that of a PE built directly from the exact label-correlated eigenvectors. A systematically large gap would falsify the practical expressivity claim, since the theory does not guarantee that the fixed-dimensional Chebyshev encoding can recover that subspace.","supporting_citations":[],"review_version":1}