{"id":"c44f36ae-f3da-4315-aec7-e2e583da5800","arxiv_id":"2412.14602","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"RMask uses random walks and a distance-based mask to extract exact-hop graph information, improving the accuracy and speed of model-simplification GNNs.","lead":"The authors propose a plug-in module called RMask that removes 'noise' from each hop of graph propagation, letting simple graph neural networks go deeper without over-smoothing and cutting pre-processing time. They report accuracy gains on six citation and product graphs and end-to-end speedups of up to about five times.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The de-noise matrix M^h in Eq. (2) requires exact shortest-path distances from every node up to depth H, but no algorithm for computing it on 111M-node graphs is given; the claimed scalability of RMask therefore rests on an unspecified and apparently infeasible primitive.","rationale":"I read the paper as trying to make a data-centric contribution: identify redundant low-hop information in each propagation step, mask it via Eq. (2), and use random walks to keep preprocessing sparse and parallel. For the central claim to hold, three things must be true: (1) the de-noise matrix can be computed on graphs with up to 111M nodes, (2) the random walk with masking is well-defined and scalable, and (3) the resulting embeddings consistently improve deeper model-simplification GNNs. The empirical sections give some support for (3): the self-comparisons in Table 2, the depth-stability plots in Figure 4, and the sparsity ablations show consistent accuracy gains over the paper's own baselines. Those results are not dismissed. However, (1) and (2) are the load-bearing foundations, and they are not established. Eq. (2) requires exact shortest-path distances, but no efficient algorithm is given; Eq. (4) involves an N-by-N matrix inverse; and RW(.,.,.) is never formally defined. The complexity analysis in Table 1 conspicuously omits the cost of constructing M^h and S. On ogbn-papers100M, an exact all-nodes BFS to depth H is infeasible, so either the method is not actually scalable or the equations do not describe the implemented procedure. This is not a matter of disagreement with current consensus; it is an internal gap between the formal method and its complexity claims. The reader's weakest assumption identified exactly this issue, and my analysis agrees. Since this gap prevents verification of the central scalability and efficiency claims, the REJECT verdict remains appropriate. A conditional accept could be justified if the authors supplied a concrete approximation algorithm for M^h with error bounds and released code; absent that, UNCHANGED is the honest verdict.","tokens_in":15072,"tokens_out":3502,"duration_ms":28398,"concrete_test":"Implement Algorithm 1 faithfully on ogbn-arxiv (H = 10, T = 5) and instrument the wall-clock time and peak memory needed to construct M^h from Eq. (2) via BFS from every node; then extrapolate the same construction to ogbn-papers100M. If the de-noise-matrix construction dominates the reported preprocessing time, or if it cannot be completed within the claimed O(L(nR+rf)/c + m/(c epsilon)) budget at 111M nodes, the scalability claim fails. Ideally, the authors should release code so the same measurement can be reproduced end-to-end.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that RMask removes redundant lower-hop information via M^h and biased random walks, enabling deeper and faster model-simplification GNNs. That claim requires M^h to be computable on ogbn-papers100M (111M nodes, 1.6B edges) within the stated complexity. Eq. (2) defines m_ij = 1 iff distance(v_i, v_j) = h and 0 iff distance < h; to build M^h for every hop one must know, for each node, the exact shortest-path distance to all nodes within H hops. A direct exact computation needs BFS from every node, i.e., O(N*M) in the worst case, or all-pairs shortest paths, which is impossible at this scale. Algorithm 1 line 1 does 'M = union M^h with Eq. (2)' without specifying any approximation, sampling, or algorithm. The complexity table (Table 1) reports RMask preprocessing as O(L(nR+rf)/c + m/(c epsilon)), which omits the cost of constructing M^h and of computing S = alpha(I - (1-alpha) Ahat)^-1 in Eq. (4), a dense N-by-N inverse (the citation to approximate PPR does not bridge this gap). If M^h is approximated by random walks, then Eq. (2) is not what is computed and the 'pure information' claim must be redefined; if M^h is exact, it is intractable on the claimed datasets. Thus the end-to-end speedups and the scalability thesis are unsupported because the load-bearing primitive is both undefined and, taken literally, infeasible.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes RMask, a plug-and-play module for model-simplification GNNs such as SGC, SIGN, S2GC, GBP, and GAMLP. The central claim is that over-smoothing in deep propagation is caused by 'noise information'—redundant lower-hop information contained in each propagation step—and that this noise can be removed by a de-noise matrix M^h built from shortest-path distances, combined with biased random walks guided by Personalized PageRank. The authors report consistent accuracy improvements over the original baselines on six datasets (Cora, Citeseer, Pubmed, ogbn-arxiv, ogbn-products, ogbn-papers100M) and claim large speedups in pre-processing. The method is presented as a scalable replacement for the Propagation operation, with complexity analysis in Table 1 and ablations in Table 3.","tokens_in":15433,"tokens_out":4419,"duration_ms":33464,"significance":"If the method worked as described, RMask would be a practically useful plug-in: it addresses a real limitation of model-simplification GNNs, is evaluated on standard public benchmarks, and the idea of treating redundant low-hop information as noise is interesting and orthogonal to existing over-smoothing remedies. The consistent gains in Table 2 and the orthogonal combination with DAGNN in Table 3 are credible strengths. However, the central mechanism is underspecified to the point of being unverifiable: the de-noise matrix in Eq. (2), the random walk function in Eq. (3)/(5), and the Personalized PageRank inverse in Eq. (4) are not given feasible algorithmic constructions, and the complexity analysis omits the dominant costs. Because the claimed scalability and the reported results rest on these primitives, the significance cannot be assessed as the paper stands.","major_comments":[{"comment":"The de-noise matrix M^h is defined via exact shortest-path distances: m_ij = 1 when distance(v_i, v_j) = h and 0 when distance(v_i, v_j) < h. For ogbn-papers100M, which has 111,059,956 nodes and 1,615,685,872 edges (Table 4), no feasible algorithm is given for computing these distances. A literal reading requires BFS from every node or all-pairs shortest paths, i.e., O(NM) in the worst case, which is intractable at this scale. Algorithm 1 line 1 simply states 'M = union M^h with Eq. (2)' without specifying any approximation, sampling, or data structure. The complexity in Table 1 omits the cost of constructing M^h entirely, so the scalability thesis is unsupported by the stated method.","section":"Noise Information Identification, Eq. (2)"},{"comment":"Eq. (4) defines S = alpha(I - (1-alpha) Ahat)^-1, which is a dense N x N matrix inverse. On graphs with millions or hundreds of millions of nodes, materializing S as a dense matrix is impossible. The citation to approximate Personalized PageRank does not bridge this gap, because Algorithm 1 line 2 invokes Eq. (4) without specifying how the inverse is approximated, truncated, or stored. Table 1 again omits the preprocessing cost of Eq. (4), so the reported speedups in Figure 5(c) cannot be reconciled with the stated complexity.","section":"Neighbor Nodes Importance Assignment, Eq. (4)"},{"comment":"The random walk function RW is never formally defined. The paper does not specify the transition probabilities, the number of steps, the restart behavior, how the de-noise matrix M^h is combined with the importance matrix S, or how the T walks are aggregated. Algorithm 1's line 'W^h = union_t W_t^h / T' is not a well-defined operation on matrices. This makes the core mechanism of the method irreproducible and prevents verification of the 'de-noise random walk' claim.","section":"RMask Pipeline, Eqs. (3) and (5)"},{"comment":"The causal claim that noise inside P is the cause of over-smoothing is not established. Eq. (2) defines noise operationally as any node within distance strictly less than h, but the evidence in Figure 2(b) is only a correlation between the proportion of redundant information and the Graph Smoothness Level as the hop count grows. There is no controlled experiment isolating whether masking those nodes, rather than changing the effective propagation kernel or the total number of reachable nodes, is responsible for the accuracy improvements. A formal definition of over-smoothing and a derivation of how the hard mask in Eq. (2) reduces it are needed.","section":"Motivation, Figure 2"},{"comment":"The empirical comparison is only against each baseline model's own original version; there is no comparison to other recent scalable GNNs or to state-of-the-art results on the OGB datasets. More importantly, the claimed speedups in Figure 5(c) (2.9x to 4.9x) are not accompanied by end-to-end timings that include the construction of M^h and S. Without a reproducible implementation or a careful accounting of these costs, the trade-off claim in Figure 5(a) is not convincing.","section":"Experiments, Table 2 and Figure 5"}],"minor_comments":[{"comment":"There is a typo in 'Contirbutions' in the Contributions paragraph.","section":"Introduction"},{"comment":"The word 'propagation' is misspelled as 'propogation' in several places, including the abstract and the introduction.","section":"Throughout"},{"comment":"The values for SIGN+RMask on Cora are printed as '84.3 ± 0.684.3 ± 0.684.3 ± 0.6'—a formatting error that also appears in other rows; the table should be regenerated with clean alignment.","section":"Table 2"},{"comment":"The horizontal axis label reads 'Ramdom walk numbers' instead of 'Random walk numbers', and the legend uses 'SSGC' while the text refers to S2GC.","section":"Figure 5(a)"},{"comment":"Line 9 has a bracket mismatch: 'concatenate([Wh1||[Wh2||...])' is missing a closing bracket and the intended concatenation syntax is unclear.","section":"Algorithm 1"},{"comment":"The hyperparameter search ranges are described only for small datasets and large datasets together, but it is not stated which propagation steps and random walk counts were selected for each dataset and each baseline; this is needed for reproducibility.","section":"Appendix, Hyperparameters"}],"recommendation":"reject","confidential_remarks":"The reader's stress-test concern is well-founded and, on reading the paper, I find it decisive: the central primitive in Eq. (2) is both undefined algorithmically and, taken literally, infeasible on the claimed datasets, and Eq. (4) adds a dense inverse that is also unaccounted for. The paper would need a substantially rewritten method section with a concrete approximate algorithm and new complexity analysis, plus rerun experiments, before it could be considered. The consistent accuracy gains in Table 2 suggest there may be a salvageable idea, but the current manuscript does not support the scalability claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this paper. There is a real idea here: each propagation hop in model-simplification GNNs carries information already captured by lower hops, and masking that redundancy before aggregation might let these models go deeper without over-smoothing. But the paper never actually defines the algorithm that is supposed to do this at scale, and taken literally, that algorithm cannot run on the datasets it reports.\n\nWhat is new is the specific combination: a distance-based de-noise matrix plus biased random walks, plugged into S2GC, SIGN, GBP, and GAMLP. The evaluation is more thorough than most—six datasets including ogbn-papers100M, four base models, ablations, and sparsity tests. The accuracy gains are consistent (roughly 1–3 points), which is evidence that the masking concept has value, at least on smaller graphs.\n\nThe soft spots are load-bearing. Equation (2) defines the de-noise matrix using exact shortest-path distances up to H hops. Constructing that matrix on a 111M-node graph requires something like BFS from every node—O(NM)—and the paper gives no alternative. The random-walk function RW is never defined; it appears as a symbol in Equations (3) and (5). The complexity table omits the cost of building M^h and also omits the cost of the PPR matrix S = α(I − (1−α)Â)^−1, which is dense if taken literally. The causal claim that noise causes over-smoothing rests on a correlation plot, not a definition or a controlled experiment. And no code is released.\n\nThese are not minor typos. If M^h is approximated by random walks, the paper needs to say so and then the 'pure information' claim has to be redefined. If M^h is exact, the efficiency story collapses. As written, the central mechanism is unverifiable.\n\nI would not desk-reject this. The idea is plausible and the empirical results are consistent. Send it to review with a clear request to specify the exact computation, provide a scalable approximation with analysis, release code, and compare against two or three external baselines. That is a lot of revision, but the seed is worth examining.","headline":"A genuinely plausible noise-masking idea for scalable GNNs, but the central algorithm is unspecified and, read literally, infeasible at the claimed scale.","tokens_in":15982,"tokens_out":3686,"would_cite":false,"duration_ms":34999,"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":"The paper claims that over-smoothing in simplified graph neural networks is driven not by propagation depth itself but by redundant low-hop information accumulating inside each deeper hop, and that a plug-and-play noise-masking…","keywords":["graph neural networks","over-smoothing","model simplification","noise masking","random walk","Personalized PageRank","node classification","scalability"],"falsifier":"Run RMask on ogbn-papers100M while timing only the construction of the de-noise matrix; if building it requires an all-pairs shortest-path computation whose wall-clock cost matches or exceeds the original serial propagation, the claimed sub-linear pre-processing is not achieved.","tokens_in":14854,"feed_emoji":"🕸️","tokens_out":6756,"duration_ms":72425,"temperature":0.7,"pith_summary":"Model-simplification graph neural networks precompute propagated features once, but their accuracy collapses as the number of propagation hops grows. This paper argues that the collapse is caused by noise: each higher hop re-delivers information already captured by lower hops, and this redundancy accumulates and smooths node representations together. To fix it, the authors propose RMask, a module that identifies noise through shortest-path distances and masks it away, then uses biased random walks to sample only the pure information of each hop. Plugged into existing methods such as SIGN, S2GC, GBP, and GAMLP, RMask keeps accuracy stable well past 20 hops and reports consistent gains on six datasets, while making pre-processing sparse and parallel enough to cut end-to-end time.","feed_headline":"Masking hop noise lets graph networks go 30 hops deep","feed_subtitle":"A plug-in random-walk module strips redundant low-hop information, pushing deeper propagation and cutting pre-processing time.","key_machinery":"The machinery is the de-noise matrix $M^h$, whose entry is 1 when the shortest-path distance from the target node is exactly $h$ and 0 when it is smaller, combined with a random walk $\\mathrm{RW}(G, M^h, T, S)$ that samples only unmasked nodes using Personalized PageRank scores $S = \\alpha (I - (1-\\alpha)\\hat{A})^{-1}$ as edge weights. The matrix identifies which nodes at each hop are redundant, the importance scores steer the walk toward informative neighbors, and the random-walk formulation decouples hops so they can be processed in parallel and sparsely, replacing the dense serial matrix propagation that dominates pre-processing.","core_discovery":"The central claim is that continuous P operations, the repeated propagation steps shared by all model-simplification GNNs, inject noise into every hop, and this noise, not depth per se, is what triggers over-smoothing. RMask replaces the P operation with a de-noise random walk: a de-noise matrix $M^h$ marks a neighbor as noise unless the shortest-path distance from the target is exactly $h$, and a biased random walk guided by Personalized PageRank importance scores samples the remaining nodes. The authors report on Cora, Citeseer, Pubmed, ogbn-arxiv, ogbn-products, and ogbn-papers100M that SIGN, S2GC, GBP, and GAMLP each improve when their propagation stage is swapped for RMask, that accuracy no longer falls as hops increase to 30, and that pre-processing drops to a smaller fraction of end-to-end time, with S2GC+RMask reported 2.9-4.9x faster than S2GC alone.","pith_inferences":["The same distance-based mask could be applied to message passing during training, not just pre-processing; if the noise diagnosis is right, masking inside full GNN layers should also slow over-smoothing. This is an extension the paper does not test.","On graphs where exact shortest-path distances are too expensive, the de-noise matrix could be approximated with random-walk hitting times or landmark distances; whether accuracy survives the approximation is an open question.","The redundancy ratio between consecutive hop neighborhoods could serve as a dataset-level predictor of how much depth a model can tolerate before over-smoothing.","Comparing RMask to a plain exclusive-hop random walk with the same sampling budget would isolate whether the benefit comes from the masking step or from the random-walk reformulation itself."],"forward_implications":["Existing model-simplification GNNs can be extended to 20-30 propagation hops on ogbn-arxiv without the accuracy collapse normally seen beyond a dozen hops.","Pre-processing becomes a smaller share of end-to-end time; the paper reports 2.9-4.9x end-to-end speedups for S2GC+RMask across six datasets.","The benefits are larger on sparse graphs: with heavily dropped features, edges, or labels, RMask-equipped models degrade more slowly than their original versions.","The noise-masking view is orthogonal to other over-smoothing remedies, so RMask can be combined with methods like DAGNN and still improve accuracy.","Because RMask is plug-and-play, any future model-simplification GNN with a different combination rule can adopt the same masked propagation without changing its training model."],"supporting_citations":[{"why":"Defines the model-simplification SGC paradigm and the P operation in Eq. (1) that RMask replaces.","marker":"Wu et al. 2019"},{"why":"SIGN is one of the four model-simplification baselines; RMask is plugged into it in Table 2.","marker":"Rossi et al. 2020"},{"why":"S2GC is a baseline and the model used for the efficiency breakdown and speedup analysis.","marker":"Zhu and Koniusz 2021"},{"why":"GBP is a baseline, and its propagation complexity informs the pre-processing overhead comparison.","marker":"Chen et al. 2020"},{"why":"GAMLP is a baseline; it represents node-wise combination in the RMask evaluation.","marker":"Zhang et al. 2021"},{"why":"Supplies the Node/Graph Smoothness Level measure used to quantify over-smoothing and the DAGNN baseline in the ablation.","marker":"Liu, Gao, and Ji 2020"},{"why":"Provides the approximate Personalized PageRank scores used as neighbor importance in the biased random walk.","marker":"Bojchevski et al. 2020"},{"why":"Provides the three OGB datasets; the 96% pre-processing share on ogbn-papers100M motivates the efficiency contribution.","marker":"Hu et al. 2020"},{"why":"Supplies the three citation datasets (Cora, Citeseer, Pubmed) and the GCN baseline that SGC simplifies.","marker":"Kipf and Welling 2017"}],"fun_headline_variants":["Mask hop noise to deepen GNNs by 30x","Over-smoothing cured by masking propagation noise","RMask strips noise for 30-hop graph networks","Noise masking lets GNNs go deep and stay fast"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the method to work as advertised, identifying which nodes are noise at each hop must be far cheaper than the dense propagation it replaces; the paper assumes this can be done on graphs with over a hundred million nodes without computing all distances between all pairs.","fun_headline_variants_meta":{"raw":{"variants":["Mask hop noise to deepen GNNs by 30x","Over-smoothing cured by masking propagation noise","RMask strips noise for 30-hop graph networks","Noise masking lets GNNs go deep and stay fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1327,"prompt_tokens":1027,"completion_tokens":300,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":246}},"tokens_in":643,"tokens_out":300,"duration_ms":3347,"temperature":1.0,"reasoning_tokens":246,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:04:23.374086+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run RMask on ogbn-papers100M while timing only the construction of the de-noise matrix; if building it requires an all-pairs shortest-path computation whose wall-clock cost matches or exceeds the original serial propagation, the claimed sub-linear pre-processing is not achieved.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"S2GC is a baseline and the model used for the efficiency breakdown and speedup analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GBP is a baseline, and its propagation complexity informs the pre-processing overhead comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Node/Graph Smoothness Level measure used to quantify over-smoothing and the DAGNN baseline in the ablation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the approximate Personalized PageRank scores used as neighbor importance in the biased random walk."},{"cited_title":"N.; and Welling, M","cited_arxiv_id":null,"evidence_quote":"Supplies the three citation datasets (Cora, Citeseer, Pubmed) and the GCN baseline that SGC simplifies."}],"review_version":1}