{"id":"a86d72a6-5a26-4afa-8e91-71b5251d8a49","arxiv_id":"2501.00743","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"AttriReBoost augments feature propagation with a partial reset of known nodes and a global-mean (virtual edge) term, achieving consistent but modest accuracy gains over FP and PCFI on eight benchmarks.","lead":"AttriReBoost is a new propagation method for filling in missing node features in graphs; it adds a moving reset for known nodes and virtual edges that connect all nodes, then proves the iterative update converges. The authors report better attribute reconstruction and node classification than prior feature propagation methods, with a claimed average accuracy gain that the paper's own tables do not fully support.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Banach fixed-point convergence proof is invalid: Eq. (12) asserts ρ(K)<1 implies ∥K∥2<1, which is false for the nonsymmetric iteration matrix K, so the claim that convergence is 'rigorously established' is unsupported.","rationale":"The reader identified the confusing convergence passage in the rationale but selected the ad hoc loss in Eq. (5) as the weakest assumption. I agree that the loss is heuristic, but the more load-bearing problem is that the paper's central theoretical claim—'convergence rigorously established'—rests on an invalid contraction-mapping argument. The iteration matrix K is nonsymmetric, and the proof's use of ρ(K)<1 to conclude ∥K∥2<1 is false; a concrete counterexample settles this immediately. The algorithm itself may still converge because the nonnegative matrix K is bounded above by an irreducible matrix B with ρ(B)≤1, so a corrected proof using Perron-Frobenius and the spectral-radius bound is likely available. Thus the flaw is repairable and does not by itself invalidate the empirical results, but the paper must fix the proof before the theoretical claim can be accepted. In addition, the abstract's 5.11% accuracy improvement is contradicted by the paper's own Table IV, which yields 2.49% over the second-best method; this reporting inconsistency should be corrected. These concerns reinforce the reader's CONDITIONAL verdict rather than changing it.","tokens_in":22005,"tokens_out":24065,"duration_ms":226082,"concrete_test":"Build the 2-node ARB iteration matrix for eA=[[0,1],[1,0]], α=0.9, β=0.1, or equivalently use the matrix K=[[0,10],[0.01,0]], and compute both ρ(K) and ∥K∥2. This will show ρ(K)<1 while ∥K∥2>1, directly disproving the inference in Eq. (12). As a second check, compute the spectral norm of the full ARB matrix K on Cora using the reported optimal α and β; if ∥K∥2≥1, the contraction argument as written fails, even though the iteration may still converge linearly to a unique fixed point.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV-D attempts to prove convergence by showing the iteration in Eq. (10) is a contraction in the spectral norm. The proof defines K = [[βBkk, βBku], [Buk, Buu]], which is the nonsymmetric matrix D B with D diagonal (β<1 on known nodes, 1 on unknown nodes). The argument then says 'From ρ(K)<1, we know ρ(K^T K)<1' and concludes ∥∆f(X)∥2 < ∥∆X∥2. This inference is false in general: a nonnegative irreducible matrix such as K = [[0,10],[0.01,0]] has ρ(K)≈0.316 but ∥K∥2=10, since ρ(K)<1 does not bound the spectral norm of a nonsymmetric matrix. Thus Eq. (12) does not establish that f is a contraction, and the Banach fixed-point theorem is not legitimately invoked. The linear iteration may still converge because ρ(K)<1 can likely be proven via Perron-Frobenius (B is positive and K≤B, K≠B), but the paper's stated proof is mathematically incorrect. Since the abstract and introduction explicitly advertise that convergence is rigorously proven, this gap is load-bearing for the paper's theoretical claim. The empirical headline is also internally inconsistent: the abstract says 5.11% average accuracy improvement, while Section V-C reports 2.49% over the second-best method, which is the value actually supported by Table IV.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AttriReBoost (ARB), an iterative, gradient-free method for reconstructing missing node attributes in graphs. ARB augments classic feature propagation with two modifications: a soft \"moving reset\" of known nodes (weighted by beta) and a virtual complete-graph edge term implementing a global mean (weighted by alpha), derived from a regularized Dirichlet-energy objective. The authors give an iterative update rule, claim convergence via the Banach fixed-point theorem, and present experiments on eight datasets covering reconstruction metrics, downstream node classification, ablations, missing-rate robustness, and runtime. The headline claims are a 5.11% average accuracy improvement over state-of-the-art methods and processing a 2.49M-node graph in about 16 seconds on a single GPU.","tokens_in":22366,"tokens_out":12555,"duration_ms":115180,"significance":"If correct, ARB is an appealing drop-in preprocessing method: it is gradient-free, adds only two hyperparameters relative to feature propagation, scales to millions of nodes, and appears to help precisely in the cold-start regimes (isolated and low-degree nodes) where feature propagation struggles. The paper makes its code public and reports a wide range of benchmarks, which are strengths. However, the convergence proof as written is invalid, the method definition has an ambiguity between Eqs. (9) and (10), and the headline accuracy improvement in the abstract does not match the value reported in Section V-C. These issues affect the paper's central theoretical and empirical claims, though they appear fixable within the manuscript's scope.","major_comments":[{"comment":"The contraction argument is mathematically incorrect. The iteration matrix K defined in Eq. (10) is not symmetric, so rho(K) < 1 does not imply rho(K^T K) < 1; a simple counterexample is K = [[0,10],[0.01,0]], for which rho(K) = 0.316 but rho(K^T K) = 100. Consequently Eq. (12) does not establish that f is a contraction in the spectral norm, and the Banach Fixed Point Theorem is not legitimately invoked. The same paragraph also writes rho(K) = max_X X^T K X / X^T X, a Rayleigh-quotient identity valid only for symmetric matrices, and the equality ||K Delta X||_2 = Delta X^T K^T K Delta X omits a square on the left-hand side. The 'Additionally' paragraph proposing a block decomposition of B is unexplained and does not apply to the full matrix B. Since the abstract states that convergence is 'rigorously established,' this is a load-bearing gap. A Perron-Frobenius argument on the positive matrix B, with K <= B elementwise and K != B, can likely yield rho(K) < 1 directly, and then convergence of the linear iteration follows from standard spectral-radius theory; the authors should replace the invalid argument with such a proof.","section":"Section IV-D, Eqs. (11)-(12)"},{"comment":"The iterative scheme is not defined unambiguously. Eq. (9) writes X_k^{(l+1)} = beta X_k^{(l)} + (1-beta) Z_k, but the fixed-point relation in Eq. (8) and the block iteration in Eq. (10) require X_k^{(l+1)} = beta [alpha \\tilde{A} X^{(l)} + (1-alpha) \\bar{X}^{(l)}]_k + (1-beta) Z_k. The latter includes the beta B_{ku} X_u term appearing in Eq. (10); the former does not. Algorithm 1 line 4 ('Xk <- beta Xk + (1-beta) Zk') is ambiguous about whether the right-hand side uses the value after line 3. If it does, the algorithm agrees with Eq. (8); if it does not, it defines a different method whose convergence matrix is not the K analyzed in the proof. Please state the order of updates unambiguously and align Eq. (9) with Eq. (10), also correcting the notation so that the global-propagation line uses \\bar{X}^{(l)} rather than X^{(l)}.","section":"Section IV-C/D, Eq. (9)-(10), Algorithm 1"},{"comment":"The headline accuracy claim is inconsistent. The abstract and the contributions list say 'average accuracy improvement of 5.11%' over state-of-the-art methods, but Section V-C reports 'an average improvement of 2.49% over the second-best method.' Table IV gives ARB average 79.79% versus PCFI 77.85%, which is a 1.94-percentage-point or 2.49% relative improvement; the 5.11% figure does not follow from any reported table. Please reconcile the numbers and state explicitly whether improvements are reported as relative or absolute percentage points.","section":"Abstract, Section V-C, Table IV"}],"minor_comments":[{"comment":"Table II uses 'MEGAE' while the text and Table III use 'MAGAE'; please standardize the method name.","section":"Tables II-III"},{"comment":"Table III uses 'CSAT' for the method called 'CAST' in Section II-A and Table II; please standardize the name.","section":"Table III"},{"comment":"The supplementary appendix refers to 'Section III D' twice in the convergence proofs; the correct reference is Section IV-D.","section":"Appendix A/B"},{"comment":"The step from X_k = beta (\\tilde{A}X)_k + (1-beta) Z_k and X_u = (\\tilde{A}X)_u to the displayed 'So: X = \\tilde{A}X, X_k = beta X_k + (1-beta) Z_k' is algebraically unclear; please expand or correct the derivation.","section":"Appendix A, Eq. (18)"},{"comment":"The hyperparameter search reports a range for alpha but not the chosen alpha, beta, and l for each dataset; listing the selected values in a table would improve reproducibility.","section":"Section V-E"},{"comment":"The positive-definiteness argument for L + eta I0_k + theta L1 should explicitly state the assumption that the known set V_k is nonempty or that theta > 0, and that the Rayleigh quotient is taken with the Euclidean norm.","section":"Section IV-D, Eq. (14)"}],"recommendation":"major_revision","confidential_remarks":"The theoretical proof defects are serious but appear fixable: a correct spectral-radius argument likely exists, and the empirical study is reasonably extensive. The abstract's 5.11% claim should be corrected or substantiated before publication. I see no citation or novelty concerns that would warrant rejection, but the manuscript should not be accepted with the convergence proof and method definition in their current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: ARB is a simple, useful drop-in replacement for feature propagation on missing-attribute graphs, with consistent gains across eight datasets and a genuinely nice large-scale runtime. But the convergence proof as written is wrong, and the abstract's 5.11% improvement figure doesn't match the 2.49% reported in the results section.\n\nWhat's new: the update in Eq. (9) combines a moving reset of known nodes with a global-mean teleport term. Both ideas resemble existing techniques—partial reinitialization and Personalized PageRank—but the specific combination, and the derivation from a regularized Dirichlet energy, are original. The derivation itself is sound: the stationary equations follow from the loss, and the Perron-Frobenius argument that ρ(K)<1 is valid (B is positive and K is a proper substochastic-like substructure). The experiments are fairly thorough: eight datasets, binary and continuous features, ablations, missing-rate sensitivity, and isolated/low-degree node analysis. The code is available.\n\nSoft spots: the proof of convergence in Section IV-D is mathematically incorrect. The paper defines a nonsymmetric matrix K, correctly shows ρ(K)<1, but then claims ρ(K^TK)<1 and concludes f is a contraction in the spectral norm. That inference is false for nonsymmetric matrices—a simple counterexample is [[0,10],[0.01,0]], with spectral radius ~0.32 but spectral norm 10. So the Banach fixed-point theorem is not legitimately invoked. The convergence result is almost certainly true—ρ(K)<1 already implies K^l→0 and the iteration converges to the unique fixed point—but the stated proof needs replacing. This is a real flaw in a paper that advertises rigor, and a referee should demand the fix.\n\nThe other soft spots are minor: no error bars, the ad hoc loss is justified only empirically, and the abstract's 5.11% average improvement is not what Table IV supports—there it's 2.49% over PCFI, which is still decent. Hyperparameter tuning on validation is standard and not circular.\n\nOverall: this is a modest but solid empirical contribution. The paper is for practitioners who want a fast, simple, gradient-free imputer for missing attributes, and for researchers benchmarking propagation methods. The proof issue is fixable without changing the method or the empirical story.\n\nRecommendation: send it to peer review. Require the authors to correct the convergence proof and reconcile the reported improvements before acceptance.","headline":"Useful, simple feature-propagation variant with a real but fixable convergence-proof gap and an overstated headline number.","tokens_in":22891,"tokens_out":3918,"would_cite":true,"duration_ms":37559,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"AttriReBoost claims to fix the cold start problem in attribute-missing graphs by redefining boundary conditions and adding virtual edges to feature propagation, with reported gains of 5.11% average accuracy and 16-second processing for a…","keywords":["attribute-missing graphs","cold start problem","feature propagation","missing attribute reconstruction","virtual edges","graph neural networks","large-scale graph learning","Banach fixed point theorem"],"falsifier":"Run ARB against feature propagation on a synthetic graph with two well-separated communities whose known attributes are far apart, concentrating missing nodes at isolates and degree-one nodes; if ARB's reconstruction error for those nodes is larger than feature propagation's because the global-mean term pulls them toward the wrong average, then the virtual-edge mechanism is the cause.","tokens_in":21828,"feed_emoji":"⚡","tokens_out":7378,"duration_ms":70984,"temperature":0.7,"pith_summary":"This paper tries to establish that the cold start problem in attribute-missing graphs can be eliminated within the simple, gradient-free feature propagation paradigm. The proposed method, AttriReBoost (ARB), replaces the hard reset of known nodes after each propagation step with a moving reset that remembers their original features only gradually, and it overlays the graph with a virtual complete-graph term so that every node, including isolated and low-degree ones, receives global mean information. On eight benchmark graphs the authors report better reconstruction and downstream classification than strong prior methods, with the largest gains on isolated and low-degree nodes, and running time nearly equal to feature propagation: the 2.49 million-node Ogbn-Products graph is processed in about 16 seconds. If these results hold, ARB is a drop-in preprocessing step for any GNN needing complete attributes, adding only two hyperparameters over feature propagation and no backpropagation.","feed_headline":"Cold-start fix lifts graph attribute recovery by 5.11%","feed_subtitle":"A propagation-only method with virtual edges fills missing node features on large graphs in seconds.","key_machinery":"The load-bearing object is the augmented Dirichlet-energy objective $\\mathcal{L}(X) = \\mathrm{tr}(X^\\top L X) + \\eta(X_k - Z_k)^\\top(X_k - Z_k) + \\theta X^\\top L_1 X$, where $L$ is the normalized Laplacian and $L_1$ is the Laplacian of the complete graph, so the last term acts as a global-mean penalty. The algorithm is the fixed-point iteration this objective induces: global propagation $X \\leftarrow \\alpha \\tilde{A}X + (1-\\alpha)\\bar{X}$, followed by moving reset $X_k \\leftarrow \\beta X_k + (1-\\beta)Z_k$. Convergence rests on the iteration matrix $K$ being elementwise dominated by a strongly connected matrix of spectral radius at most 1, which forces $\\rho(K) < 1$ and makes the update a Banach contraction.","core_discovery":"On the paper's own terms, the central claim is that missing attributes in a graph are better reconstructed by minimizing a modified Dirichlet energy that contains three terms: the usual edge smoothness, a soft penalty pulling known nodes back toward their original values, and a complete-graph penalty that connects every pair of nodes through virtual edges. The stationarity condition of this objective yields the iteration $X^{(l+1)} = \\alpha \\tilde{A}X^{(l)} + (1-\\alpha)\\bar{X}^{(l)}$ for all nodes and $X_k^{(l+1)} = \\beta X_k^{(l)} + (1-\\beta)Z_k$ for known nodes, where $\\alpha$ and $\\beta$ are functions of the penalty weights $\\theta$ and $\\eta$. The paper proves that the iteration matrix has spectral radius strictly below 1, so the update map is a contraction and, by the Banach fixed point theorem, converges to a unique fixed point. Experiments then show faster and more accurate reconstruction than feature propagation and PCFI, especially for isolated and low-degree nodes.","pith_inferences":["A testable extension is to replace the single global mean with per-community means computed from known nodes; the paper's virtual-edge term assumes one global average, so a clustered-corruption benchmark would reveal whether the mean term blurs community-specific attributes.","The moving reset coefficient $\\beta$ interpolates between hard reset and pure averaging, so an untested corollary is that annealing $\\beta$ from 1 to a lower value over iterations could combine early local fidelity with later global smoothing.","ARB's update is a form of diffusion toward a global sink, and the heuristic hyperparameter search over $\\alpha$ suggests a direct connection between $\\alpha$ and graph conductance; one could predict good $\\alpha$ values from the spectral gap instead of searching per dataset.","Because the paper's 5.11% average gain is measured under its chosen missing-rate protocol and baseline set, the claim should not be extrapolated to non-random missingness without a dedicated experiment."],"forward_implications":["If ARB works as claimed, feature propagation becomes a stronger preprocessing step: any downstream GNN can consume fully imputed attributes without changing the model or adding training cost.","Reconstruction quality stops depending so sharply on node degree, so isolated and low-degree nodes, the long tail of real networks, get usable features rather than zero or stale values.","Because ARB costs almost the same as feature propagation and avoids backpropagation, graphs with tens of millions of edges can be imputed on a single GPU in seconds, sidestepping memory-heavy batch training.","Deeper propagation remains stable up to $l = 10$ in the reported experiments, so users do not need to tune depth carefully to avoid oversmoothing while using ARB.","The Banach fixed-point argument means the iteration is guaranteed to reach the same unique steady state from zero initialization, making early stopping a safe speedup rather than a heuristic."],"supporting_citations":[{"why":"Defines feature propagation with hard reset, the method ARB modifies and the primary baseline.","marker":"[16]"},{"why":"PCFI, the confidence-weighted propagation baseline ARB compares against in accuracy and speed.","marker":"[17]"},{"why":"SVGA is a leading deep generative baseline; its experimental protocol for missing-rate splits is followed.","marker":"[13]"},{"why":"SAT is a state-of-the-art attribute-missing graph baseline used in reconstruction and classification comparisons.","marker":"[12]"},{"why":"Supplies the bound on the normalized adjacency matrix spectral radius used in the convergence proof.","marker":"[46]"},{"why":"Banach fixed point theorem, invoked to conclude the ARB iteration converges to a unique fixed point.","marker":"[47]"},{"why":"Provides the Ogbn-Arxiv and Ogbn-Products datasets that ground the large-scale runtime and accuracy claims.","marker":"[52]"}],"fun_headline_variants":["Gradient-free graph method lifts attribute recovery by 5.11%","Virtual edges fix cold start in missing-attribute graphs","Graph attribute fix: no backprop, 2.49M nodes in 16s","Cold start tamed: propagation with virtual edges boosts accuracy 5.11%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's load-bearing premise is that the three-term loss in its optimization objective, smoothness over real edges, a soft pull toward known attributes, and a complete-graph mean penalty, is the right objective for reconstructing missing attributes; this premise is validated by tuning $\\alpha$ and $\\beta$ per dataset rather than derived from a generative model of why attributes are missing.","fun_headline_variants_meta":{"raw":{"variants":["Gradient-free graph method lifts attribute recovery by 5.11%","Virtual edges fix cold start in missing-attribute graphs","Graph attribute fix: no backprop, 2.49M nodes in 16s","Cold start tamed: propagation with virtual edges boosts accuracy 5.11%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000364,"raw_usage":{"total_tokens":1969,"prompt_tokens":962,"completion_tokens":1007,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":578,"completion_tokens_details":{"reasoning_tokens":926}},"tokens_in":578,"tokens_out":1007,"duration_ms":9795,"temperature":1.0,"reasoning_tokens":926,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:44:05.864854+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run ARB against feature propagation on a synthetic graph with two well-separated communities whose known attributes are far apart, concentrating missing nodes at isolates and degree-one nodes; if ARB's reconstruction error for those nodes is larger than feature propagation's because the global-mean term pulls them toward the wrong average, then the virtual-edge mechanism is the cause.","supporting_citations":[{"cited_title":"Learning on attribute-missing graphs,","cited_arxiv_id":null,"evidence_quote":"SAT is a state-of-the-art attribute-missing graph baseline used in reconstruction and classification comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the bound on the normalized adjacency matrix spectral radius used in the convergence proof."},{"cited_title":"Sur les op ´erations dans les ensembles abstraits et leur application aux ´equations int ´egrales,","cited_arxiv_id":null,"evidence_quote":"Banach fixed point theorem, invoked to conclude the ARB iteration converges to a unique fixed point."},{"cited_title":"Open graph benchmark: Datasets for machine learning on graphs,","cited_arxiv_id":null,"evidence_quote":"Provides the Ogbn-Arxiv and Ogbn-Products datasets that ground the large-scale runtime and accuracy claims."}],"review_version":1}