REVIEW 5 major objections 6 minor 33 references
Towards Scalable and Deep Graph Neural Networks via Noise Masking
T0 review · 5 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict A genuinely plausible noise-masking idea for scalable GNNs, but the central algorithm is unspecified and, read literally, infeasible at the claimed scale. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (5)
- [Noise Information Identification, Eq. (2)] 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.
- [Neighbor Nodes Importance Assignment, Eq. (4)] 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.
- [RMask Pipeline, Eqs. (3) and (5)] 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.
- [Motivation, Figure 2] 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.
- [Experiments, Table 2 and Figure 5] 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.
minor comments (6)
- [Introduction] There is a typo in 'Contirbutions' in the Contributions paragraph.
- [Throughout] The word 'propagation' is misspelled as 'propogation' in several places, including the abstract and the introduction.
- [Table 2] 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.
- [Figure 5(a)] The horizontal axis label reads 'Ramdom walk numbers' instead of 'Random walk numbers', and the legend uses 'SSGC' while the text refers to S2GC.
- [Algorithm 1] Line 9 has a bracket mismatch: 'concatenate([Wh1||[Wh2||...])' is missing a closing bracket and the intended concatenation syntax is unclear.
- [Appendix, Hyperparameters] 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.
Circularity Check
No significant circularity: RMask is evaluated against external benchmarks and its de-noise matrix is defined independently of the prediction target.
full rationale
RMask's derivation does not reduce to its own inputs. The de-noise matrix M^h (Eq. 2) is defined by shortest-path distances, and the random-walk matrices W^h are built from it before any accuracy measurement; the accuracy comparison is then run on held-out splits of six external datasets against external model-simplification baselines (SIGN, S2GC, GBP, GAMLP). Hyperparameters and propagation depths are selected by grid search on validation performance, not fitted to the reported test outcomes, so no prediction is forced by construction. The only same-author citations (GAMLP and NAFS) are used as a baseline and for the standard stationary-state fact about normalized adjacency powers, respectively; the central claim does not depend on either being true. The scalability objection raised by a literal reading of M^h on ogbn-papers100M is a feasibility/correctness concern about an omitted algorithm and omitted complexity terms, not a circularity: if the primitive is intractable the method is unsupported, but the method would not thereby be equivalent to its inputs. No equation in the paper is both premise and conclusion, and no fitted parameter is renamed as a prediction.
Assumptions & free parameters
free parameters (3)
- number of random walks T =
grid search over {5, 10, 15, 20, 25, 30}
- restart probability alpha =
not stated in the paper
- propagation hops H =
grid search over {6-15}; depth experiments up to 30
assumptions (3)
- domain assumption Adjacency-matrix powers overlap lower-hop supports, and these lower-distance entries are 'noise' that should be removed.
- ad hoc to paper Random walks with T samples and the de-noise matrix approximate the exact masked propagation well enough to preserve accuracy.
- standard math Personalized PageRank S can be computed approximately at scale (citing Bojchevski et al. 2020) and can guide random walks effectively.
invented entities (2)
-
noise information
-
de-noise matrix M^h
Cite this review
Pith. "Pith review of Towards Scalable and Deep Graph Neural Networks via Noise Masking." pith.science (2026). https://pith.science/paper/MU47T4XC
@misc{pith2026241214602,
author = {Pith},
title = {Pith review of: Towards Scalable and Deep Graph Neural Networks via Noise Masking},
year = {2026},
howpublished = {\url{https://pith.science/paper/MU47T4XC}},
note = {Machine review of arXiv:2412.14602}
}
read the original abstract
In recent years, Graph Neural Networks (GNNs) have achieved remarkable success in many graph mining tasks. However, scaling them to large graphs is challenging due to the high computational and storage costs of repeated feature propagation and non-linear transformation during training. One commonly employed approach to address this challenge is model-simplification, which only executes the Propagation (P) once in the pre-processing, and Combine (C) these receptive fields in different ways and then feed them into a simple model for better performance. Despite their high predictive performance and scalability, these methods still face two limitations. First, existing approaches mainly focus on exploring different C methods from the model perspective, neglecting the crucial problem of performance degradation with increasing P depth from the data-centric perspective, known as the over-smoothing problem. Second, pre-processing overhead takes up most of the end-to-end processing time, especially for large-scale graphs. To address these limitations, we present random walk with noise masking (RMask), a plug-and-play module compatible with the existing model-simplification works. This module enables the exploration of deeper GNNs while preserving their scalability. Unlike the previous model-simplification works, we focus on continuous P and found that the noise existing inside each P is the cause of the over-smoothing issue, and use the efficient masking mechanism to eliminate them. Experimental results on six real-world datasets demonstrate that model-simplification works equipped with RMask yield superior performance compared to their original version and can make a good trade-off between accuracy and efficiency.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Bojchevski, A.; Klicpera, J.; Perozzi, B.; Kapoor, A.; Blais, M.; R \' o zemberczki, B.; Lukasik, M.; and G \" u nnemann, S. 2020. Scaling Graph Neural Networks with Approximate PageRank. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020 , 2464--2473
work page 2020
-
[4]
Chen, J.; Ma, T.; and Xiao, C. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In 6th International Conference on Learning Representations, ICLR
work page 2018
-
[5]
Chen, J.; Zhu, J.; and Song, L. 2018. Stochastic Training of Graph Convolutional Networks with Variance Reduction. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 , volume 80, 941--949
work page 2018
-
[6]
Chen, M.; Wei, Z.; Ding, B.; Li, Y.; Yuan, Y.; Du, X.; and Wen, J. 2020. Scalable Graph Neural Networks via Bidirectional Propagation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020
work page 2020
-
[7]
Chen, Z.; Feng, B.; Yuan, L.; Lin, X.; and Wang, L. 2023. Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks. Data Science and Engineering, 8(3): 263--278
work page 2023
-
[8]
Chiang, W.; Liu, X.; Si, S.; Li, Y.; Bengio, S.; and Hsieh, C. 2019 a . Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference on nowledge Discovery & Data Mining, KDD 2019 , 257--266
work page 2019
Show all 33 references
-
[9]
Chiang, W.; Liu, X.; Si, S.; Li, Y.; Bengio, S.; and Hsieh, C. 2019 b . Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , 257--266
2019
-
[10]
Chien, E.; Peng, J.; Li, P.; and Milenkovic, O. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021
2021
-
[11]
Cui, Y.; Zheng, K.; Cui, D.; Xie, J.; Deng, L.; Huang, F.; and Zhou, X. 2021. METRO: A Generic Graph Neural Network Framework for Multivariate Time Series Forecasting. Proc. VLDB Endow. , 15(2): 224--236
2021
-
[12]
L.; Ying, Z.; and Leskovec, J
Hamilton, W. L.; Ying, Z.; and Leskovec, J. 2017. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 1024--1034
2017
-
[13]
Hao, P.-Y.; Liu, S.-H.; and Bai, C. 2024. Intent-Aware Graph-Level Embedding Learning Based Recommendation. Journal of Computer Science and Technology, 39(5): 1138--1152
2024
-
[14]
He, H.; Chen, G.; and Chen, C. Y.-C. 2024. Integrating sequence and graph information for enhanced drug-target affinity prediction. Science China Information Sciences, 67(2): 129101
2024
-
[15]
Helali, M.; Mansour, E.; Abdelaziz, I.; Dolby, J.; and Srinivas, K. 2022. A Scalable AutoML Approach Based on Graph Neural Networks. Proc. VLDB Endow. , 15(11): 2428--2436
2022
-
[16]
Hu, W.; Fey, M.; Zitnik, M.; Dong, Y.; Ren, H.; Liu, B.; Catasta, M.; and Leskovec, J. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS
2020
-
[17]
Huang, W.; Zhang, T.; Rong, Y.; and Huang, J. 2018. Adaptive Sampling Towards Fast Graph Representation Learning. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS, 4563--4572
2018
-
[18]
P.; and Ba, J
Kingma, D. P.; and Ba, J. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015
2015
-
[19]
N.; and Welling, M
Kipf, T. N.; and Welling, M. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017
2017
-
[20]
Li, Y.; Shen, Y.; Chen, L.; and Yuan, M. 2023. Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank. Proc. VLDB Endow. , 16(6): 1332--1345
2023
-
[21]
Liu, M.; Gao, H.; and Ji, S. 2020. Towards Deeper Graph Neural Networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , 338--348
2020
-
[22]
Piao, C.; Xu, T.; Sun, X.; Rong, Y.; Zhao, K.; and Cheng, H. 2023. Computing Graph Edit Distance via Neural Graph Matching. Proc. VLDB Endow. , 16(8): 1817--1829
2023
-
[23]
Rong, Y.; Huang, W.; Xu, T.; and Huang, J. 2020. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In 8th International Conference on Learning Representations, ICLR
2020
-
[24]
M.; and Monti, F
Rossi, E.; Frasca, F.; Chamberlain, B.; Eynard, D.; Bronstein, M. M.; and Monti, F. 2020. SIGN: Scalable Inception Graph Neural Networks. CoRR, abs/2004.11198
2020 arXiv
-
[25]
Velickovic, P.; Cucurull, G.; Casanova, A.; Romero, A.; Li \` o , P.; and Bengio, Y. 2018. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018
2018
-
[26]
Wu, F.; Jr., A. H. S.; Zhang, T.; Fifty, C.; Yu, T.; and Weinberger, K. Q. 2019. Simplifying Graph Convolutional Networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , volume 97, 6861--6871
2019
-
[27]
Wu, J.; Sun, C.; and Yang, C. 2024. On the size generalizibility of graph neural networks for learning resource allocation. Science China Information Sciences, 67(4): 142301
2024
-
[28]
Zeng, H.; Zhou, H.; Srivastava, A.; Kannan, R.; and Prasanna, V. K. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method. In 8th International Conference on Learning Representations, ICLR
2020
-
[29]
Zhang, S.; Ni, W.-W.; and Fu, N. 2023. Community-Preserving Social Graph Release with Node Differential Privacy. Journal of Computer Science and Technology, 38(6): 1369--1386
2023
-
[30]
Zhang, W.; Sheng, Z.; Yang, M.; Li, Y.; Shen, Y.; Yang, Z.; and Cui, B. 2022. NAFS: A Simple yet Tough-to-beat Baseline for Graph Representation Learning. In International Conference on Machine Learning, ICML , volume 162, 26467--26483
2022
-
[31]
Zhang, W.; Yin, Z.; Sheng, Z.; Ouyang, W.; Li, X.; Tao, Y.; Yang, Z.; and Cui, B. 2021. Graph Attention MLP with Reliable Label Utilization. arXiv preprint arXiv:2108.10097
2021 arXiv
-
[32]
Zhong, S.; Wang, J.; Yue, K.; Duan, L.; Sun, Z.; and Fang, Y. 2023. Few-shot relation prediction of knowledge graph via convolutional neural network with self-attention. Data Science and Engineering, 8(4): 385--395
2023
-
[33]
Zhu, H.; and Koniusz, P. 2021. Simple Spectral Graph Convolution. In 9th International Conference on Learning Representations, ICLR 2021
2021
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.