- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies decoupled graph models, focusing on a comparison between two fixed propagation schemes: Simplified Graph Convolution (SGC) and Personalized PageRank (PPR). It seeks to answer three fundamental questions:
- Under what conditions can graph propagation improve the signal-to-noise ratio (SNR) relevant to node classification?
- Why can SGC and PPR yield substantially different results on the same graph?
- How can the risk of performance degradation caused by graph propagation be mitigated?
The authors develop a theoretical framework centered on frequency order, stochastic dominance between signal and noise, and response floors. They elucidate the differences in frequency ordering between SGC and PPR, as well as the role of response floors, and compare the two propagation schemes under an equal hyperparameter-tuning budget. Finally, they validate their findings through experiments on stochastic block models and 30 real-world graph datasets.
Critical strengths
-
This paper investigates a fundamental question in decoupled graph models: whether graph propagation is beneficial and under what conditions it may degrade the original features. The scope of the study is well-defined, and its theoretical objectives are clearly articulated.
-
The paper provides a relatively comprehensive set of theoretical proofs rather than relying solely on empirical evidence.
-
The paper's findings on the different frequency orderings induced by eigenvalue magnitude and by eigenvalue itself help explain, to some extent, why certain graph convolution methods remain effective on strongly heterophilous graphs. They also demonstrate that homophily alone is insufficient to determine whether propagation is beneficial.
-
The experiments cover both synthetic and real-world datasets, and the paper derives simple and practical design principles from its findings.
Critical weaknesses
-
The gap between the SNR improvements claimed by the paper and the resulting classification performance is not sufficiently discussed.
-
The experimental evaluation is limited to a few classical propagation schemes, and the empirical evidence supporting the discussion of heterophily needs to be strengthened.
Questions for authors
-
The paper's theoretical insights primarily concern the signal-to-noise ratio (SNR). For node classification, where class distributions may be imbalanced, there may be a gap between the linear model assumed in the paper and real-world datasets. Although the authors use accuracy and AUC as evaluation metrics, the direct relationship between SNR and actual classification performance remains unclear. Another question of particular interest is how much of the information beneficial to the final classification outcome can be retained after the filtered features are passed through a subsequent nonlinear learner, even when the SNR is high.
-
The paper mentions that heterophily exposes the low-pass bias of message passing, but this claim does not appear to be sufficiently substantiated on real-world heterophilous graphs. For example, the authors could report heterophily measures for the real-world datasets, analyze the correlation between heterophily and the performance gains of SGC and PPR over MLP, and group datasets by their degree of homophily to compare SGC and PPR and examine whether the proposed frequency-ordering theory explains the performance differences across groups.
-
In addition to SGC and PPR, fixed filter banks with band-pass characteristics are also commonly used. For example, a filter bank that scans the full spectrum from low-pass to high-pass filters could, in principle, cover the entire frequency range if a sufficient number of filters were used. It would be interesting to investigate whether the insights developed in this paper can also explain the behavior of band-pass filters to a comparable extent.
-
Decoupled graph models are computationally efficient. Could the authors provide experiments on large-scale graphs with millions of nodes (ogbn-products, pokec) to further substantiate the paper's claims?
2 comments
Response to Reviewer mbqZ (2/2)
Q3 – Band-pass filter banks – Yes, the theory covers them. Each unimodal band-pass filter has its own order, and Theorem 1 decides every filter in a bank.
- One band-pass filter. A symmetric response that peaks at and decreases away from it ranks frequencies by the score . Theorem 2 applies with this score. If the class signal dominates the noise along , no such filter loses to the raw features, for any width. For example, peaks at and ranks frequencies by , the reverse of the SGC order.
- A bank with different centers. Filters with different centers do not share one order, so no single verdict covers the bank. Theorem 1 still decides each member exactly. Appendix E treats S²GC in the same way, because its members also do not share an order.
- Floors. A band-pass response that vanishes at the ends of the spectrum has no floor. Like adjacency powers, a bank of such filters then needs the identity.
In the revision, we added band-pass filters to Table 9 with their scores and floors (Appendix E).
W2 – Only a few classical schemes – We chose SGC and PPR because they cover both frequency orders and both floor cases. Appendix E maps five more fixed filters onto them.
Heat kernels, DGC and lazy powers share the order of PPR. High-pass powers have the reverse order. The identity is the trivial case. Table 9 lists the score and the floor of each scheme, and the revision adds the band-pass case above. The real-graph protocol trains every scheme with the same 60 heads and splits, so a new fixed scheme can be added as one more arm.
Q4 – Large graphs – Yes. We ran ogbn-products, with 2.4 million nodes. Both schemes gain about 15 points over the MLP, and the joint search matches the better one.
Setup. We use five random 50/25/25 splits with the paper's filter grids, per-split validation and paired split bootstrap. Full-batch training of the width-512 heads does not fit in GPU memory on this graph. Each arm therefore uses the same 16 heads, namely the first 20 configurations without the width-512 ones.
Table R2: Mean test accuracy on ogbn-products over five splits, with the gap to the MLP and its 95% interval. Bold marks the best value in each column.
| Arm | Test accuracy | Gap to MLP |
|---|---|---|
| MLP | 73.27 | — |
| SGC | 88.16 | +14.89 [14.85, 14.94] |
| PPR | 87.62 | +14.35 [14.21, 14.46] |
| Joint search over MLP, SGC and PPR | 88.16 | +14.89 [14.85, 14.94] |
As shown in Table R2, the conclusions of the paper hold at this scale. Both schemes gain significantly over the MLP, as the block models show for homophilous graphs. In these graphs, the class signal lies where the two orders agree (Section 4.1). PPR stays within 0.54 points of SGC. The joint search selects SGC on every split and therefore matches it exactly. Each scheme stores one filtered matrix and trains at the cost of an MLP. We added Table R2 to the revision as Table 16 (Appendix F) and summarize it in Section 4.2.
We hope these answers and the new experiments address your questions. If they do, we would be grateful if you would consider raising the score.
Response to Reviewer mbqZ (1/2)
We thank the reviewer for the precise summary and for noting that the two frequency orders help explain why some graph convolutions stay effective under strong heterophily. Below, we answer each question directly. We added a heterophily analysis on all graphs, a large-graph experiment on ogbn-products, and an analysis of band-pass filters. We uploaded a revised paper, with new text in blue.
W1, Q1 – From SNR to classification– The block models connect the two directly, and every real-graph result already passes through a nonlinear learner.The label-aligned ratio of Section 3.4 refines the SNR when a filter mixes classes. On block models with h=0.5, it predicts the accuracy drop of SGC that the SNR misses (Appendix B).
W2, Q2 – Heterophily on real graphs– We grouped all 46 graph and round pairs by adjusted homophily. Homophily alone does not determine the better scheme. The frequency order explains the clearest case, Facebook100.Setup. We use adjusted homophily [1], which corrects edge homophily for class imbalance and is near zero for a random graph. We split the pairs at hadj=0.2 and use the gaps and significance tests from the paper. Of the 46 pairs, we report the 45 whose data we could download again during the discussion period (Wiki is missing).
Table R1: Gaps to the MLP and between the schemes, grouped by adjusted homophily. Counts are numbers of pairs with a significant difference.
As shown in Table R1, filtering helps on most heterophilous graphs as well, and on average it helps more there. Over all pairs, the rank correlation of adjusted homophily with each gap is close to zero: −0.06 for SGC − MLP, 0.02 for PPR − MLP and 0.03 for PPR − SGC.
What homophily cannot explain is which scheme wins among the heterophilous graphs. PPR is better on roman-empire, Actor, amazon-ratings, minesweeper, questions and tolokers. SGC is better on all five Facebook100 graphs, squirrel-filtered and four Twitch graphs. The frequency order explains the Facebook100 case. On these graphs, the class signal lies partly at negative frequencies, which SGC keeps and PPR damps. Restricting the features to this band reproduces the difference: SGC is significantly above the MLP on all five graphs, and PPR on none (Table 8). This agrees with the reviewer's point that homophily alone is insufficient.
We added Table R1 and the adjusted homophily of every graph to the revision as Tables 15 and 14 (Appendix F), and summarize them in Section 4.2.
[1] Platonov et al., Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond, NeurIPS 2023.