{"id":"6bf2c4b9-3834-41d9-adea-8d145d2460bb","arxiv_id":"2505.20992","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Random feature aggregation (RFA) derives identity and position graph embeddings from random noise via one parameter-free spectral propagation, matching or beating trained baselines at much lower cost.","lead":"The paper introduces RFA, a graph embedding method that feeds random noise through a fixed spectral filter and needs no training, yet produces embeddings that separate nodes by structural role or by community. A generalist reader should care because it suggests that much of what trained graph neural networks do may be achievable with a single propagation step, at a fraction of the cost.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Test-set hyperparameter selection for RFA (Tables 8/9) may inflate the reported quality-efficiency trade-off; no validation split is described.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: per-dataset hyperparameters in Tables 8 and 9 were selected without a described held-out validation split. I agree with that assessment. The paper's central claim is empirical and comparative, so the fairness of the evaluation protocol is decisive. Other potential weaknesses, such as the heuristic derivation of Remark 3.5 linking high-frequency information to node identities, are real but less load-bearing because the empirical results could stand even if the theoretical interpretation is incomplete; the paper itself defers rigorous guarantees to future work. The efficiency comparison is also less concerning because RFA's time advantage is large and its complexity analysis is sound, though the trade-off metric NToS is normalized per dataset and therefore sensitive to quality changes. The proposed concrete test—a validation-based selection protocol—would settle whether the reported quality advantage generalizes. If RFA remains top-3 under that protocol, the central claim holds; if not, the paper would need to soften the 'better trade-off' claim or restrict it to default settings. Since the reader already arrived at CONDITIONAL with the same concern, my read does not change the verdict.","tokens_in":26384,"tokens_out":5221,"duration_ms":60893,"concrete_test":"Reproduce Tables 3, 4, and 6 with a nested validation protocol: split labeled nodes into train/val/test (e.g., 20/20/60), select (d, tau, K, activation, normalization) for RFA and for each baseline on the validation split, then evaluate on the test split and average over 10 random splits. If RFA no longer achieves best or top-3 quality in a majority of datasets, the reported trade-off advantage is not established. A complementary check is to fix one default setting (e.g., d=128, tau=20, K=10, tanh, z-norm) across all datasets and compare—if quality drops materially, the per-dataset tuning is doing substantial work.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that RFA derives informative identity/position embeddings with no training and achieves a better quality-efficiency trade-off than baselines—is empirical. The per-dataset settings in Tables 8 and 9 (embedding dimension d, degree correction tau, layer count K, activation, normalization) appear to be selected after observing test performance. Section 4.1 states that for baselines, several normalization strategies were tried and 'the best quality metrics reported,' but no held-out validation split is described for RFA's own hyperparameters. The irregular settings across datasets (e.g., RFA(H) uses exp with z-norm on Europe but exp without normalization on USA, and K ranges from 2 to 12) are consistent with per-dataset optimization on the test labels. If so, the quality advantage in Tables 3/4 and the NToS scores in Table 6 are inflated, and the 'without any training' claim is weakened because test labels are used for model selection. This is the most load-bearing weakness because it affects every quantitative comparison supporting the headline claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes random feature aggregation (RFA), an unsupervised graph embedding method that uses a parameter-free spectral GNN backbone with random Gaussian input, a degree-corrected graph convolution, nonlinear activation, and normalization. Two variants—RFA(H) with a high-pass filter (δ=0.1, α=−1) and RFA(L) with a low-pass filter (δ=0.1, α=1)—are designed to produce identity and position embeddings, respectively, through a single K-layer forward propagation with no training. The paper motivates the design with a graph-signal-processing observation on small examples that high- and low-frequency eigenvectors encode node identities and positions, and reports experiments on 10 datasets against 18 baselines, claiming better or competitive quality with orders of magnitude lower inference time, summarized by a normalized trade-off score (NToS). Theoretical remarks connect low-frequency eigenvectors to relaxed normalized cut and high-frequency eigenvectors to degree variation and the Weisfeiler-Lehman test, but these are heuristic. The code is publicly available.","tokens_in":26636,"tokens_out":8011,"duration_ms":80000,"significance":"If the reported results hold under a proper validation protocol, the paper makes a valuable empirical contribution: it shows that a training-free, random-input spectral aggregation can match or beat trained GNNs and dedicated structural embedding methods on unsupervised identity and position tasks, with a dramatic efficiency advantage. The connection between filter type and embedding property is interesting and potentially useful for practitioners. Strengths include the breadth of the evaluation (10 datasets, 18 baselines), the explicit efficiency and scalability analysis, and a public code release. The main caveat is that the quantitative claim currently rests on an evaluation protocol in which hyperparameters appear to be selected after observing test labels, and no uncertainty estimates are provided; until this is addressed, the significance of the empirical claim is not fully established.","major_comments":[{"comment":"The hyperparameters of RFA (d, τ, K, activation, normalization) appear to be selected per dataset on the test portion, since no held-out validation split or selection procedure is described and the settings vary widely across datasets (e.g., K ranges from 2 to 14; exp with z-norm is used on Europe but exp without normalization on USA). Because all three quantitative claims—quality, efficiency trade-off, and NToS—are computed from these settings, the comparison is potentially inflated. Please report a validation-based selection protocol (e.g., choose hyperparameters on the 20% labeled training split or a separate validation split) and give the resulting test scores, or provide results for a fixed default hyperparameter setting.","section":"§4.1, Tables 8-9"},{"comment":"No standard deviations or significance tests are reported for quality metrics, although differences between RFA and the best baseline are small on several datasets (e.g., Reality-Call micro-F1 85.88 vs. 85.72 for GMAE; Film micro-F1 60.03 vs. 59.51 for GMAE; PPI micro-F1 20.38 vs. 20.88 for SketchNE). Without repeated-measures variance or error bars, the claimed 'better quality' and the derived NToS improvements are not statistically substantiated. Please report means with standard deviations over the 10 random splits and, where relevant, paired significance tests.","section":"§4.1, Tables 3-4"},{"comment":"The proof of Remark 3.5 does not establish the claim that high-frequency information captures node identities. Equation (8) only rewrites the eigenvector equation to express λ_r as a sum of degree-normalized neighbor terms; the subsequent step that high-frequency eigenvectors 'encode degree information' and that RFA 'may play a role similar to the WL test' relies on an unverified injectivity condition and the phrase 'if a high-frequency base is powerful enough.' Since the paper presents this as a theoretical interpretation and labels it a proof, please either develop the argument into a precise statement with explicit conditions or clearly label the remarks as intuition.","section":"§3.4, Remark 3.5"}],"minor_comments":[{"comment":"The phrase 'low- and high-pass information may respectively characterize node identities and positions' reverses the paper's own finding; it should read 'high- and low-pass information.'","section":"§4.2"},{"comment":"The legend entries in Figure 4 use 'LFA' instead of 'RFA' (e.g., 'LFA(L) w/ CPU') and should be corrected to 'RFA.'","section":"Figure 4"},{"comment":"The USA dataset URL is identical to the Europe URL (europe-airports.edgelist); the USA link appears to be wrong and should be fixed.","section":"Appendix B"},{"comment":"There is a typo in the sentence about Figure 1: 'v1 ad v8' should be 'v1 and v8.'","section":"§2"},{"comment":"The NToS computation should state explicitly how out-of-time and out-of-memory methods are treated in the min-max normalization, since their inclusion or exclusion affects the reported scores.","section":"§4.3"},{"comment":"The statement that for baselines 'the best quality metrics reported' were used is too vague for reproducibility; please specify the searched parameter grids and normalization choices for each baseline.","section":"§4.1"}],"recommendation":"major_revision","confidential_remarks":"The central idea is interesting and the empirical evidence is broad, but the missing validation protocol and lack of uncertainty estimates are load-bearing for the headline quality-efficiency claim. I would be willing to accept after the authors provide a fair hyperparameter-selection procedure and error bars. The fit with KDD is good, and the public code is a plus."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the empirical core is real and the paper is worth a serious referee, but the central quality-efficiency claim is softer than the abstract suggests because the per-dataset hyperparameters in Tables 8/9 look like they were chosen after seeing test labels, and there are no error bars.\n\nWhat's new: RFA combines random noise inputs, a parameter-free spectral filter, and a degree-corrected convolution to produce identity and position embeddings in one feed-forward pass. The observation that high-pass filters give identity-like embeddings and low-pass filters give position-like embeddings is a genuinely fresh result, and the experiments are broad: ten datasets, eighteen baselines, plus ablation and scalability studies. The method is also very fast in practice, and the code is public.\n\nThe soft spots. First, the test-set tuning issue is real and load-bearing. The paper describes splitting labeled nodes for the downstream classifier, but never describes a validation split for choosing d, tau, K, activation, and normalization. Tables 8 and 9 show irregular settings across datasets (e.g., RFA(H) uses exp with z-norm on Europe but exp without normalization on USA, with K from 2 to 12), which is exactly the pattern you get when you pick settings per dataset to maximize reported F1. This doesn't undermine the claim that RFA is cheap or that the filter-frequency correlation exists, but it does undermine \"a better trade-off between quality and efficiency,\" because a fair comparison requires the same model-selection protocol for RFA and the baselines. The stress-test note is on target.\n\nSecond, the paper reports means over 10 runs but no standard deviations, so we can't tell whether the quality gaps are meaningful.\n\nThird, the theoretical support for the high-frequency/identity link is a heuristic argument (Remark 3.5), not a proof, and the paper itself admits that rigorous guarantees are future work. That's fine for a KDD paper, but the abstract's \"we find\" should be read as \"we observe empirically.\"\n\nNone of these are fatal. The method is simple, reproducible, and a useful baseline for anyone doing unsupervised identity/position embedding. For a graph-ML reading group, it's a good paper to discuss. I'd send it to peer review, but I'd ask for a validation-based hyperparameter selection procedure, error bars, and a softened abstract. The paper deserves serious referee time.","headline":"Useful empirical paper with a real but overstated quality-efficiency claim; test-set hyperparameter tuning and missing error bars are the main issues.","tokens_in":27089,"tokens_out":2617,"would_cite":true,"duration_ms":27565,"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":"Random noise, propagated through a parameter-free spectral graph filter in a single forward pass, yields embeddings that match or beat trained GNNs and dedicated baselines on both identity and position tasks—provided the filter sign…","keywords":["Efficient graph embedding","Node identity embedding","Node position embedding","Spectral graph neural networks","Random feature aggregation","Graph signal processing","Degree correction","Unsupervised graph embedding"],"falsifier":"On a fresh graph with known structural roles and known communities, freeze a single RFA(H) and RFA(L) configuration chosen only on validation data, then run both variants; if the high-pass variant cannot separate nodes with identical ego-nets, or the low-pass variant cannot separate communities at above-chance F1, the paper's spectral identity/position claim would be falsified.","tokens_in":26204,"feed_emoji":"🕸️","tokens_out":15687,"duration_ms":141534,"temperature":0.7,"pith_summary":"This paper tries to establish that identity and position graph embeddings—the two standard kinds of topology-only node embeddings—can be produced without any training, feature extraction, or eigen-decomposition. The method, random feature aggregation (RFA), feeds Gaussian random noise into a parameter-free spectral graph filter and reads off the output after a single forward propagation through $K$ layers. The paper argues that the filter's sign is a task selector: a low-pass filter amplifies community structure and yields position embeddings, while a high-pass filter amplifies degree variation and yields identity embeddings. On ten datasets, the two RFA variants stay within the top three on F1 quality and achieve the best or near-best quality-versus-time trade-off, while several trained GNN baselines time out or run out of memory on the largest graphs. If this holds, topology-only graph embedding becomes a near-instant, parameter-free inference routine.","feed_headline":"One training-free pass turns random noise into graph embeddings","feed_subtitle":"Filter sign picks node identity or community position, so million-node graphs embed in seconds.","key_machinery":"The load-bearing mechanism is random feature aggregation (RFA): a parameter-free spectral GNN backbone. Each layer applies the graph convolution $g(\\tilde{\\Lambda}) = (\\delta+\\alpha)I_N - \\alpha\\tilde{\\Lambda}$ to the current node-feature matrix, where $\\tilde{\\Lambda}$ is the eigenvalue matrix of the degree-corrected normalized Laplacian $L_\\tau = I_N - D_\\tau^{-1/2}AD_\\tau^{-1/2}$ with $D_\\tau = D + \\tau I_N$; the sign of $\\alpha$ chooses low-pass (positions) or high-pass (identities), and the degree-correction term $\\tau$ squeezes the spectrum toward 1, an effect the Gershgorin circle theorem explains. Stacking $K$ layers with a nonlinear activation and row or column normalization turns the initial noise into informative embeddings while keeping the whole procedure one forward pass. The argument works because low-frequency eigenvectors are the relaxed solution of normalized cut, while high-frequency eigenvectors concentrate degree variation so that nodes with identical ego-nets receive identical coordinates.","core_discovery":"The central claim is that node identities and node positions are carried by opposite ends of the graph spectrum. Low-frequency eigenvectors of the normalized Laplacian, which solve the relaxed normalized-cut objective, encode community structure and therefore positions; high-frequency eigenvectors encode local degree variation that distinguishes rooted subgraphs and therefore identities. RFA operationalizes this by replacing learned GNN weights with the fixed spectral kernel $g(\\tilde{\\Lambda}) = (\\delta+\\alpha)I_N - \\alpha\\tilde{\\Lambda}$, feeding Gaussian noise $\\Theta \\sim \\mathcal{N}(0,1/d)$ through $K$ such layers with nonlinear activation and normalization, and using the output as the embedding. The RFA(H) variant takes $\\alpha<0$ (high-pass) and produces identity embeddings; RFA(L) takes $\\alpha>0$ (low-pass) and produces position embeddings. The paper's experiments report top-three F1 quality on all ten datasets and the best or near-best normalized trade-off score between quality and inference time, with RFA completing in seconds to minutes where several trained GNN baselines time out or run out of memory.","pith_inferences":["Inference: Because the filter sign separates the two embedding tasks, the same backbone could be reused across different graphs without retraining; a testable prediction is that a rule based only on the downstream task (role classification versus community detection) will select the correct variant.","Inference: The degree-correction term acts as spectrum shaping—it pulls the eigenvalues of the Laplacian together—so it could be adopted by any spectral GNN as a cheap regularizer, not just by this parameter-free backbone.","Inference: Because RFA needs no labels, it can serve as a feature generator for semi-supervised or few-shot settings: run the random propagation once, then train only the downstream classifier on a small labeled set.","Inference: Since RFA's input is isotropic Gaussian noise, its output is a deterministic function of the random seed; ensembling or concatenating a few seeds is a natural, architecture-free way to reduce variance and possibly raise quality further."],"forward_implications":["Identity and position embeddings become a simple inference routine: draw Gaussian noise, apply the chosen filter for $K$ layers, and return the output—no optimizer, no eigen-decomposition, no feature extraction.","The filter sign is a task selector: choose $\\alpha>0$ when the downstream task rewards community membership, and $\\alpha<0$ when it rewards structural role; this gives a principled way to decide which topology property a spectral method will capture.","Inference cost is roughly linear in the number of edges and nodes, allowing graphs with more than a million nodes and a hundred million edges to be embedded in seconds on a GPU and in minutes on a CPU.","A small degree-correction parameter $\\tau$ improves quality for both filter types, while a $\\tau$ that is too large degrades it, giving a cheap tuning knob with a clear spectral interpretation.","For topology-only inputs, trained GNNs fed one-hot degree features need not be the default choice: the paper's results indicate that an untrained spectral backbone can match or exceed their embedding quality at a fraction of the cost."],"supporting_citations":[{"why":"Supplies struc2vec, the standard identity-embedding baseline, and the barbell-graph setting used to show that high-frequency eigenvectors assign identical values to nodes with the same structural role.","marker":"[40]"},{"why":"Defines DeepWalk and the neighbor-overlap notion of position that the paper adopts for node positions.","marker":"[27]"},{"why":"Supplies node2vec, the key position-embedding baseline, and several position-evaluation datasets (PPI, BlogCatalog).","marker":"[14]"},{"why":"Grounds the low-frequency/position claim by showing that the relaxed normalized-cut objective is solved by the smallest-eigenvalue eigenvectors of the normalized Laplacian.","marker":"[46]"},{"why":"Together with [36], provides degree-corrected spectral clustering, the basis for RFA's degree-correction mechanism.","marker":"[18]"},{"why":"Introduces regularized spectral clustering under the degree-corrected stochastic blockmodel, motivating the tau term in the convolution.","marker":"[36]"},{"why":"Provides the random-projection theory that supports feeding random Gaussian noises to the backbone instead of learned inputs.","marker":"[1]"},{"why":"Connects node identities to degree refinement through the Weisfeiler-Lehman test, the mechanism used to argue that high-frequency bases distinguish ego-nets.","marker":"[22]"},{"why":"Supplies the spectral-GNN expressiveness analysis used to argue that high-frequency bases can encode 1-hop degree information in an injective way.","marker":"[47]"}],"fun_headline_variants":["No training, just noise: spectral filter yields identity or position embeddings","Random noise in, graph embeddings out—choose frequency for identity or position","One pass, no weights: spectral graph embeddings from random features","High or low frequency tells identity from position in graphs","Spectral shortcut: random noise becomes useful embeddings without any training"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the per-dataset choices of dimension, degree-correction strength, layer count, activation, and normalization were not effectively tuned to the test sets; if those choices were made after seeing test performance, the reported quality advantage may not transfer to new graphs.","fun_headline_variants_meta":{"raw":{"variants":["No training, just noise: spectral filter yields identity or position embeddings","Random noise in, graph embeddings out—choose frequency for identity or position","One pass, no weights: spectral graph embeddings from random features","High or low frequency tells identity from position in graphs","Spectral shortcut: random noise becomes useful embeddings without any training"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000212,"raw_usage":{"total_tokens":1468,"prompt_tokens":1043,"completion_tokens":425,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":348}},"tokens_in":659,"tokens_out":425,"duration_ms":5184,"temperature":1.0,"reasoning_tokens":348,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:42:09.238052+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a fresh graph with known structural roles and known communities, freeze a single RFA(H) and RFA(L) configuration chosen only on validation data, then run both variants; if the high-pass variant cannot separate nodes with identical ego-nets, or the low-pass variant cannot separate communities at above-chance F1, the paper's spectral identity/position claim would be falsified.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies struc2vec, the standard identity-embedding baseline, and the barbell-graph setting used to show that high-frequency eigenvectors assign identical values to nodes with the same structural role."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines DeepWalk and the neighbor-overlap notion of position that the paper adopts for node positions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies node2vec, the key position-embedding baseline, and several position-evaluation datasets (PPI, BlogCatalog)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Grounds the low-frequency/position claim by showing that the relaxed normalized-cut objective is solved by the smallest-eigenvalue eigenvectors of the normalized Laplacian."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Together with [36], provides degree-corrected spectral clustering, the basis for RFA's degree-correction mechanism."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces regularized spectral clustering under the degree-corrected stochastic blockmodel, motivating the tau term in the convolution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the random-projection theory that supports feeding random Gaussian noises to the backbone instead of learned inputs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Connects node identities to degree refinement through the Weisfeiler-Lehman test, the mechanism used to argue that high-frequency bases distinguish ego-nets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the spectral-GNN expressiveness analysis used to argue that high-frequency bases can encode 1-hop degree information in an injective way."}],"review_version":1}