{"id":"9237c42f-7ef6-43a1-8f41-f9116352c999","arxiv_id":"2502.01122","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"PEARL generates expressive, stable, and scalable graph positional encodings by passing random or basis node features through message-passing GNNs and pooling the outputs.","lead":"This paper introduces PEARL, a way to generate graph positional encodings using graph neural networks with random or basis-vector node inputs, avoiding expensive eigenvector computations. It claims these encodings are as expressive and stable as eigenvector-based methods while running in linear or quadratic time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"R-PEARL's linear-scalability theorem (Thm 4.3) rests on unverified β=1/F filter-norm bound; with batch norm/skip connections and K≤18, βF can exceed 1, making required M grow with depth and undermining the central claim.","rationale":"The reader's weakest-assumption pick is the same point that I find most load-bearing: Theorem 4.3 is the only result that converts R-PEARL's per-sample linear cost into an overall linear-complexity guarantee. The proof's variance bound (Eq. 73) collapses to a constant only under β=1/F and Cσ=1; the implemented network uses batch norm, skip connections, and K up to 18, none of which is covered by the theorem or checked in the paper. A missing premise in a theorem does not by itself falsify the empirical method; the experiments are extensive and the stability argument inheriting GNN bounds is reasonable, and the CSL/cycle-counting results give independent evidence of expressiveness. But because the headline claim is explicitly that PEARL is simultaneously expressive, stable, and scalable, and the scalability half rests on an unverified normalization condition, a conditional verdict is appropriate. The concrete test I propose—measuring β_l F_l and empirical variance on a released checkpoint—would settle whether the concern lands; if it does, the scalability claim should be restated as conditional on weight normalization, not as a proven property of the architecture as trained.","tokens_in":29532,"tokens_out":13975,"duration_ms":170978,"concrete_test":"Take a trained R-PEARL checkpoint (e.g., ZINC or RelBench config). For each GNN layer, measure β_l = max over output features of the operator norm of Σ_k H_k^{(l)} S^k, using power iteration on the filter with the actual GSO S and learned weights, and also measure the effective Lipschitz constant of the full layer including batch norm/skip connections. Check whether β_l F_l ≤ 1 for all l. Separately estimate Var[Φ(G,q)] with M'=1000 fresh q samples on a small and a large graph from the same dataset. If any β_l F_l > 1, or if the empirical variance grows with L or N, Theorem 4.3's premise fails and the constant-M scalability claim is not justified for the released model; if β_l F_l ≤1 and variance is flat, the concern is resolved and the conditional can be lifted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central scalability claim—that R-PEARL approximates E[Φ(G,q)] with a constant number of samples independent of graph size—rests entirely on Theorem 4.3. Its proof (Appendix F) derives Var[Φ(G,q)] ≤ (Cσ β F)^{2L} (Eq. 73) and sets Cσ=1, β=1/F to make this constant. But the theorem's architecture is the idealized layer in Eq. (3), whereas the implemented Φ is a 9-layer GNN with batch normalization, skip connections, K up to 18, and widths F=40/128. Nothing in the paper verifies or enforces β≤1/F for the learned filters; skip connections alone add an identity path with operator norm 1, and batch norm changes the effective per-layer Lipschitz constants. If βF>1, the variance bound grows as (βF)^{2L} and Chebyshev (Eq. F.1) requires M ≥ Var/(δ ε²), so the sample count needed for a fixed ε,δ can grow exponentially in depth—exactly the regime the linear-complexity claim excludes. The theorem as stated also has the inequality direction reversed: Chebyshev yields M ≥ 1/(δ ε²), not M ≤. This does not refute the empirical comparisons, but it means the theoretical basis for constant-M scalability is currently unsupported for the released architecture.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PEARL, a framework for constructing graph positional encodings from message-passing GNNs. In R-PEARL, each node is initialized with M i.i.d. random signals, the graph is processed M times, and the outputs are averaged; in B-PEARL, standard basis vectors are used and the outputs are summed. The authors argue that message-passing GNNs are nonlinear functions of the graph shift operator's eigenvectors (Prop. 3.1), that PEARL can universally approximate basis-invariant functions (Thm. 3.1), that the sample complexity of the empirical average is independent of graph size (Thm. 4.3), that the encodings count cycles and exceed 1-FWL expressiveness (Cors. 4.4, 4.5), and that they inherit GNN stability guarantees (Cor. 4.6). Experiments on REDDIT, ZINC, DrugOOD, RelBench, CSL, and Peptides-struct show competitive or better performance relative to eigenvector-based baselines, often at lower claimed complexity.","tokens_in":29832,"tokens_out":7674,"duration_ms":89623,"significance":"If the theoretical claims held as stated, PEARL would be a substantial practical contribution: it would offer a scalable, stable, and expressive alternative to full spectral positional encodings. The paper includes useful open-source code, a broad experimental evaluation, and careful connections to existing spectral PE methods. The empirical results are genuinely promising, especially B-PEARL on ZINC and the low-sample behavior of R-PEARL on REDDIT. However, several load-bearing theoretical statements are not currently justified for the architectures actually evaluated, and one central theorem contains a reversed inequality. The paper's conceptual contribution is solid, but the formal backing needs correction before the scalability guarantee can be accepted.","major_comments":[{"comment":"The inequality in Theorem 4.3/Eq. (10) is reversed. From Chebyshev's inequality as written in Eq. (49), P(|1/M Σ P(m) - E[Φ]| ≥ ε) ≤ Var/(M ε²). To make this probability at most δ, one needs M ≥ Var/(δ ε²), which with Var ≤ 1 gives M ≥ 1/(δ ε²), not M ≤ 1/(δ ε²). The proof therefore supports a lower bound on the number of samples, not the upper bound printed in the theorem. Since this theorem is the basis for the claimed graph-size-independent sample complexity, the statement must be corrected.","section":"Section 4.1, Theorem 4.3 and Appendix F"},{"comment":"Theorem 4.3 depends critically on Assumption 4.2 with β = 1/F and Cσ = 1, but the architecture described in Section 6.1 uses a 9-layer GNN with batch normalization, skip connections, K up to 18, and widths 40/128. Nothing in the paper enforces ∥H(S)∥ ≤ 1/F for the learned filters. Skip connections add an identity path with operator norm 1, and batch normalization changes the effective per-layer Lipschitz constants. If βF > 1, the bound in Eq. (73) grows as (βF)^{2L}, so the sample count needed for a fixed error can grow exponentially in depth. The constant-M scalability claim is therefore not established for the implemented PEARL architecture.","section":"Section 4.1, Assumption 4.2; Section 6.1"},{"comment":"The basis-universality proof uses polynomial filters of order K equal to the number q of distinct eigenvalues (Lemma C.1) and an unrestricted equivariant pooling function ρ, e.g., a high-order tensor IGN. For large graphs q can be as large as N, making the filter order and pooling cost incompatible with the paper's linear-complexity claim and with the fixed, small K values used in experiments (K ≤ 18). The universal-approximation and linear-complexity claims cannot both be supported by the current proof as written.","section":"Section 3.2, Theorem 3.1 and Appendix C"},{"comment":"The claimed equivalence between B-PEARL and SPE is established by expanding the spectral functions α_i as Taylor series and truncating them to polynomials. An MLP, the actual choice in the SPE implementation cited by the authors, is not generally a polynomial. Exact equivalence holds only for polynomial α_i; for general analytic α_i the argument gives an approximation without an error bound. The remark overstates the relationship between the two architectures.","section":"Section 5.1, Remark 5.2 and Appendix I"},{"comment":"The statement of Corollary 4.6 defines Lipschitz filters with constant C but the displayed bound is independent of C. In the stability framework of Gama et al. that the paper cites, the Lipschitz constant typically enters the bound, often through a factor such as C^L. Either C is implicitly set to 1, in which case that should be stated explicitly, or the bound must include C. As written, the displayed inequality does not follow from the stated assumptions.","section":"Section 4.3, Corollary 4.6 and Appendix H.2"}],"minor_comments":[{"comment":"The word 'requqired' appears in the proof of Theorem F.1; it should be 'required'.","section":"Appendix F"},{"comment":"The rows for R-PEARL with K=1 and K=12 report the identical Test MAE of 0.0699; please clarify whether this is a duplicate row or an actual coincidence of results.","section":"Table 9"},{"comment":"Typography: 'RREDDIT-M' in the Table 1 caption and 'ouperforms' in the Table 2 caption should be corrected.","section":"Tables 1 and 2"},{"comment":"The phrase 'to captural structural information' should read 'to capture structural information'.","section":"Appendix A"},{"comment":"The notation Φ(G, ·)[:, f] is used without a definition; please define it when the stability bound is first stated.","section":"Section 4.3, Eq. (11)"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid methods paper that deserves a serious referee, but the headline theory needs repair. What is actually new is the specific recipe — message-passing GNNs over random or basis node identifiers plus statistical pooling as a PE generator — and the argument that this gives equivariant, eigenvector-style PEs at O(MN) or O(N^2) cost. That combination is not in the prior literature, even though the ingredients are. The experiments back the empirical claim: R-PEARL and B-PEARL match or beat full eigenvector PEs on ZINC, REDDIT-M, DrugOOD, and RelBench at much lower cost, and the CSL zero-training classification is a nice sanity check. The paper also does the right thing by reporting architecture details and parameter-budget comparisons in the appendix.\n\nSoft spots, in order of importance. First, Theorem 4.3 as written has the Chebyshev inequality direction reversed. The proof gives Var/(M epsilon^2) <= delta, which forces M >= 1/(delta epsilon^2), not M <=. This is a simple fix but it matters, because the theorem currently asserts the opposite of what the proof implies. Second, the constant-M sample complexity rests on the assumptions C_sigma = 1 and beta = 1/F. The implemented Phi is a 9-layer GNN with batch normalization, skip connections, K up to 18, and widths 40/128; nothing in the paper verifies or enforces beta <= 1/F. Skip connections alone put an identity path with operator norm 1 into each layer, so beta F can exceed 1 and the variance bound (C_sigma beta F)^{2L} can grow with depth. That does not refute the experiments, but it means the scalability theorem is currently unsupported for the released architecture. Third, the basis-universality theorem uses an unrestricted pooling function rho and polynomial filters of order equal to the number of distinct eigenvalues, so it does not directly justify the implemented mean/sum pooling with small K. This is a gap between theory and practice rather than a fatal flaw. Minor: the code links in the abstract and appendix point to two different repositories. The reliance on prior cycle-counting and GNN-stability results from the same group is fine; those are published building blocks, not circular conclusions.\n\nBottom line: I would send this to review. A referee should ask for the inequality fix, a clear statement of which pooling functions Theorem 3.1 covers, and either verification of beta F <= 1 or a revised sample-complexity claim that admits depth dependence. The experimental contribution alone is worth a serious look.","headline":"A genuinely useful PE method with strong experiments; the headline sample-complexity theorem has an inverted inequality and an unverified norm assumption, but the empirical core holds up and deserves refereeing.","tokens_in":30376,"tokens_out":1883,"would_cite":true,"duration_ms":21612,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that graph positional encodings can be learned by message-passing GNNs with random or basis node initializations, achieving linear complexity, stability, and high expressiveness without computing eigenvectors.","keywords":["positional encodings","graph neural networks","eigenvectors","permutation equivariance","sample complexity","graph expressivity","stability","message passing"],"falsifier":"Train R-PEARL on graphs of increasing size with filter norms larger than 1/F, then measure the empirical variance of the pooled outputs as M grows; if the variance grows with depth or graph size rather than staying bounded, Theorem 4.3's premise fails. A second test is to apply random node permutations to a graph and measure whether the finite-M PEARL output changes by more than the predicted equivariance error, which would show that exact equivariance requires more samples than the theorem assumes.","tokens_in":29316,"feed_emoji":"🕸️","tokens_out":6245,"duration_ms":62744,"temperature":0.7,"pith_summary":"The paper introduces PEARL, a way to build graph positional encodings entirely from message-passing GNNs instead of from eigenvector decompositions. It argues that a GNN is a nonlinear function of the graph shift operator's eigenvectors, so feeding the GNN a batch of random or standard-basis node attributes and averaging the outputs recovers eigenvector-style positional information. The paper claims this construction is permutation equivariant in expectation, stable under graph perturbations independently of eigenvalue gaps, and expressive enough to count cycles up to length seven and to beat the 1-WL test. If true, this would give graph transformers and GNNs a scalable substitute for spectral encodings: linear or quadratic complexity instead of cubic, with comparable accuracy.","feed_headline":"GNNs can generate positional encodings at linear cost","feed_subtitle":"Random or basis seeds let message-passing GNNs match full eigenvector encodings with far less compute.","key_machinery":"The load-bearing object is the observation that message-passing GNN layers of the form $X^{{(l)}}$ = σ(Σ_{k=0}^{K-1} S^k $X^{{(l-1)}}$ H_k) act as nonlinear mappings applied to the eigenvectors V of the graph shift operator S, with first-layer weights constrained by eigenvalues and node features. PEARL exploits this by breaking node symmetries with M unique random or basis identifiers, processing each independently, and restoring permutation equivariance through statistical pooling (empirical mean for R-PEARL, sum for B-PEARL). The sample complexity theorem and the stability bound both flow from viewing the GNN as a bank of bounded filters H(S) applied to unit-variance inputs.","core_discovery":"The central claim is that learnable positional encodings can be generated by message-passing GNNs with statistical pooling, and that these encodings approximate equivariant functions of the graph's eigenvectors. For large graphs, R-PEARL initializes each node with M random scalar samples, runs the same GNN on each sample, and averages the outputs; the paper proves the required number of samples is bounded by 1/(δ $ε^{2}$), independent of graph size, and that the encoding inherits GNN stability while counting node-level 3-7 node cycles. For smaller graphs, B-PEARL initializes with the N standard basis vectors and sums the GNN outputs, which the paper shows is equivalent to the SPE architecture when the spectral filters are analytic, at quadratic rather than cubic cost.","pith_inferences":["Editorial extension: If the graph-size-independent sample bound transfers to trained models, PEARL-style encodings could make spectral information practical for graph transformers on graphs with billions of edges, where eigendecomposition is impossible.","Editorial extension: Finite-sample R-PEARL is only approximately equivariant, so there is a concrete trade-off between sample count and permutation invariance; the paper's own experiments show one random sample degrades performance sharply, but the exact error as a function of M is not characterized.","Editorial extension: Because B-PEARL coincides with SPE for analytic spectral filters, any future improvement to SPE's stability or expressivity should carry over to B-PEARL at reduced cost; this gives a cheaper testbed for spectral PE research.","Editorial extension: The cycle-counting result suggests a direct probe: measure whether PEARL-derived encodings recover known cycle counts on graphs where closed-form counts are available, and whether structurally aware sampling extends counting to longer motifs, which the paper leaves outside its scope."],"forward_implications":["R-PEARL scales to large graphs: its feed-forward cost is Θ(M N F² + M |E| F), so with 10–100 samples it is roughly linear and avoids the O(N³) eigendecomposition.","B-PEARL matches or beats full eigenvector PEs on molecular and social benchmarks while reducing cost from cubic to quadratic, and it improves out-of-distribution size generalization on DrugOOD.","PEARL-augmented GNNs are strictly more expressive than the 1-WL test and can count node-level cycles of length 3 through 7, without pre-specified motif biases.","Because the stability bound does not depend on eigenvalue gaps, PEARL avoids the eigengap fragility of truncated eigenvector encodings such as SignNet and BasisNet."],"supporting_citations":[{"why":"Supplies the concentration inequality used to turn the variance bound into the M ≤ 1/(δε²) sample complexity.","marker":"(Boucheron et al., 2003)"},{"why":"Provides the GNN stability bounds that PEARL inherits and adapts for perturbations to the graph shift operator.","marker":"(Gama et al., 2020)"},{"why":"Establishes the substructure-counting results that Corollary 4.4 uses to prove PEARL counts cycles up to length seven.","marker":"(Kanatsoulis & Ribeiro)"},{"why":"Gives the GIN expressiveness hierarchy used to prove PEARL-augmented GNNs are strictly more powerful than 1-WL.","marker":"(Xu et al., 2019)"},{"why":"Defines the SPE spectral encodings that B-PEARL is shown equivalent to when the spectral functions are analytic.","marker":"(Huang et al.)"},{"why":"Defines the sign and basis invariant networks whose universal approximation of basis-invariant functions PEARL recovers.","marker":"(Lim et al.)"},{"why":"Introduces Laplacian eigenvector positional encodings, the baseline class PEARL aims to replace.","marker":"(Dwivedi & Bresson, 2021)"}],"fun_headline_variants":["Linear-cost positional encodings via GNNs","GNN-generated PEs match eigenvector methods cheaply","Random seeds unlock GNN positional encodings","PEARL: GNNs produce PEs with linear complexity","Match eigenvector PEs at a fraction of the cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's guarantee that a small number of random samples suffices assumes the learned message-passing filters have norm at most 1/F and the nonlinearities do not amplify variance; if trained filters are stronger than that, the sample bound can degrade with network depth and graph size.","fun_headline_variants_meta":{"raw":{"variants":["Linear-cost positional encodings via GNNs","GNN-generated PEs match eigenvector methods cheaply","Random seeds unlock GNN positional encodings","PEARL: GNNs produce PEs with linear complexity","Match eigenvector PEs at a fraction of the cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000915,"raw_usage":{"total_tokens":3951,"prompt_tokens":993,"completion_tokens":2958,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":609,"completion_tokens_details":{"reasoning_tokens":2878}},"tokens_in":609,"tokens_out":2958,"duration_ms":21394,"temperature":1.0,"reasoning_tokens":2878,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T16:30:42.646764+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train R-PEARL on graphs of increasing size with filter norms larger than 1/F, then measure the empirical variance of the pooled outputs as M grows; if the variance grows with depth or graph size rather than staying bounded, Theorem 4.3's premise fails. A second test is to apply random node permutations to a graph and measure whether the finite-M PEARL output changes by more than the predicted equivariance error, which would show that exact equivariance requires more samples than the theorem assumes.","supporting_citations":[{"cited_title":"Concentration inequalities","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration inequality used to turn the variance bound into the M ≤ 1/(δε²) sample complexity."},{"cited_title":"Stability properties of graph neural networks","cited_arxiv_id":null,"evidence_quote":"Provides the GNN stability bounds that PEARL inherits and adapts for perturbations to the graph shift operator."},{"cited_title":"A generalization of transformer networks to graphs","cited_arxiv_id":null,"evidence_quote":"Introduces Laplacian eigenvector positional encodings, the baseline class PEARL aims to replace."}],"review_version":1}