acceptodds
Under review as a conference paper at ICLR 2027

Frequency Orders and Response Floors of Fixed Filters in Decoupled Graph Models

Abstract

Decoupled graph models classify nodes by filtering node features once with a fixed filter and training only a classifier. The filter comes from a propagation scheme, adjacency powers (SGC) or personalized PageRank (PPR), and only its hyperparameter is tuned. Dataset-level metrics and block-model analyses of specific operators leave open which scheme to use and how much it can lose to no filter. Since a filter rescales each graph frequency separately, we characterize a scheme by its frequency order. PPR orders frequencies by eigenvalue and SGC by magnitude. In a linear feature model, a filter raises the signal-to-noise ratio (SNR) exactly when its squared response covaries positively with the excess of signal over noise across frequencies. Stochastic dominance between signal and noise along a scheme's order decides the whole scheme. Every PPR filter has a response floor bounding its SNR loss, whereas adjacency powers have none. On contextual stochastic block models, the criterion predicts the sign of every significant gain. On 30 real graphs with equal tuning budgets, neither scheme dominates, and PPR significantly beats SGC wherever SGC is significantly below an MLP. The results support searching both frequency orders and keeping the identity in schemes without a floor.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, spectral filters, decoupled GNNs, heterophily, personalized PageRank, node classification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_mbqZOpenReview ↗
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:

  1. Under what conditions can graph propagation improve the signal-to-noise ratio (SNR) relevant to node classification?
  2. Why can SGC and PPR yield substantially different results on the same graph?
  3. 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
  1. 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.

  2. The paper provides a relatively comprehensive set of theoretical proofs rather than relying solely on empirical evidence.

  3. 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.

  4. The experiments cover both synthetic and real-world datasets, and the paper derives simple and practical design principles from its findings.

Critical weaknesses
  1. The gap between the SNR improvements claimed by the paper and the resulting classification performance is not sufficiently discussed.

  2. 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
  1. 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.

  2. 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.

  3. 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.

  4. 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
AuthorsOpenReview ↗

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.

  1. SNR and accuracy on block models. On these models, the feature model holds. We compare the SNR change of the selected filter with the accuracy change of a tuned classifier. The signs agree in all 40 decisive cells and in 207 of 220 single instances (Section 4.1).
  2. Class imbalance. The SNR weights each class by its proportion πc\pi_c, because the class signal is S=YcM\mathbf{S} = \mathbf{Y}_c\mathbf{M} with Yc=Y−1π⊤\mathbf{Y}_c = \mathbf{Y} - \mathbf{1}\boldsymbol{\pi}^\top (Section 3.1). We report ROC-AUC on the binary graphs, several of which are imbalanced. The design rules hold there as they do on the other graphs (Table 1).
  3. Nonlinear learners. Every real-graph head is an MLP with one or two hidden layers, normalization and dropout, tuned over 60 configurations (Appendix C). In the main protocol, SGC is significantly below the MLP in seven pairs. When each selected filter is trained with all 60 heads, SGC remains significantly below the MLP in all seven (Table 7).
  4. What survives a nonlinear learner. The filtered features are a fixed function of X\mathbf{X}. A frequency that a filter sets to zero is lost for every learner. Adjacency powers can remove the class signal entirely (Proposition 2(c)), while every PPR filter keeps at least a fraction α/(2−α)\alpha/(2-\alpha) of each frequency.

The label-aligned ratio of Section 3.4 refines the SNR when a filter mixes classes. On block models with h=0.5h = 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.2h_{\text{adj}} = 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.

GroupPairs (graphs)Mean SGC − MLPMean PPR − MLPSGC above / below MLPPPR above / below MLPPPR betterSGC better
Heterophilous, hadj<0.2h_{\text{adj}} < 0.227 (19)+5.88+5.5021 / 422 / 21210
Homophilous, hadj≥0.2h_{\text{adj}} \ge 0.218 (10)+3.42+4.2015 / 218 / 0141

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.

AuthorsOpenReview ↗

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.

  1. One band-pass filter. A symmetric response that peaks at μ=c\mu = c and decreases away from it ranks frequencies by the score −∣μ−c∣-|\mu - c|. Theorem 2 applies with this score. If the class signal dominates the noise along −∣μ−c∣-|\mu - c|, no such filter loses to the raw features, for any width. For example, (1−μ2)K(1-\mu^2)^K peaks at μ=0\mu = 0 and ranks frequencies by −∣μ∣-|\mu|, the reverse of the SGC order.
  2. 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.
  3. 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.

ArmTest accuracyGap to MLP
MLP73.27—
SGC88.16+14.89 [14.85, 14.94]
PPR87.62+14.35 [14.21, 14.46]
Joint search over MLP, SGC and PPR88.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.

Reviewer_amNaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates when fixed graph filters improve node representations compared with unfiltered features. It characterizes SGC and PPR through their frequency orders, derives conditions for improving spectral signal-to-noise ratio (SNR), and establishes response-floor bounds. The theoretical analysis is supported by experiments on contextual stochastic block models and 30 real-world graphs.

Critical strengths

Theoretical insight: I find the frequency-order characterization interesting. Rather than analyzing individual propagation operators separately, the paper provides a unified perspective on when families of fixed filters improve or degrade spectral SNR. The label-aligned refinement also helps address an important limitation of measuring signal energy alone.

Evaluation: The experimental study is thorough. The evaluation is conducted across 30 real-world graphs, and the negative-frequency intervention on Facebook100. I think These experiments provide useful evidence for the different behaviors of SGC and PPR.

Critical weaknesses

Limited predictive value of the theoretical criterion on real graphs. While the SNR analysis is exact under the assumed linear feature model, I am less convinced that it provides sufficiently useful guidance for choosing propagation schemes in practice. The criterion agrees with 81 of 86 decisive comparisons, compared with 77 for a constant prediction, and correctly orders SGC and PPR in only 15 of 38 significant comparisons. This suggests that spectral SNR alone may not adequately capture downstream classification behavior. Although the label-aligned refinement partially addresses class mixing, its practical effectiveness on real graphs remains unclear. I would like to better understand the conditions under which the criterion provides meaningful guidance beyond simple validation-based model selection.

The novelty and scope of the theoretical contributions could be better clarified. The covariance criterion follows from comparing signal and noise energies after frequency-wise reweighting, while the scheme-wide dominance condition is closely related to first-order stochastic dominance. I agree that applying these principles to propagation schemes is useful, but the paper should more clearly distinguish its new theoretical insights from existing spectral analysis. I would also appreciate a more comprehensive discussion of how the frequency-order characterization relates to adaptive spectral filtering methods [1–4]. While focusing on fixed propagation schemes is reasonable, I wonder whether the proposed characterization provides insights that extend to more flexible, learned frequency responses. In addition, the converse of Theorem 2 applies to the broader class of ordered filters rather than necessarily identifying a failing member of a particular fixed-filter scheme, which somewhat limits its scheme-specific interpretation.

The practical significance of the response-floor guarantee needs further clarification. PPR has a positive response floor, but the strength of this guarantee depends heavily on the teleportation parameter. When alpha approaches one, PPR becomes close to identity, so its empirical stability may partly reflect the ability to avoid meaningful propagation. I am not fully convinced that the response-floor analysis provides substantial practical guidance beyond including a nearly unfiltered representation among the candidates. Similarly, retaining identity propagation is already a common design choice in decoupled and adaptive graph models. It would be useful to clarify what new model-design recommendations follow from the analysis beyond explaining these existing practices.

The practical applicability of the spectral diagnostic remains limited. The real-graph spectral analysis uses class means computed from all labeled nodes, including test nodes, for post-hoc evaluation. Although these labels are not used for model selection, the resulting diagnostic cannot be directly applied in a realistic setting where only training labels are available. I would like to know whether estimating these quantities using training labels alone yields similar conclusions. Furthermore, the combined MLP/SGC/PPR search uses a larger overall configuration budget than each individual scheme. A comparison under a fixed total search budget would better establish the practical benefit of searching multiple frequency orders.

[1] Chien et al., Adaptive Universal Generalized PageRank Graph Neural Network, ICLR 2021.

[2] He et al., BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation, NeurIPS 2021.

[3] Bo et al., Specformer: Spectral Graph Neural Networks Meet Transformers, ICLR 2023.

[4] Zhang et al., HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations, NeurIPS 2025.

Questions for authors

See weakness

3 comments
AuthorsOpenReview ↗

Response to Reviewer amNa (1/3)

We thank the reviewer for finding the frequency-order characterization interesting and the evaluation thorough. Below, we address each point. We added three analyses: the spectral diagnostic with training labels only, a search at a fixed total budget, and the teleport parameters that validation selects. We uploaded a revised paper, with new text in blue.


W1 – Predictive value of the criterion on real graphs – We agree that the criterion does not replace validation. The paper uses it to derive search rules, and these rules hold on every real graph we tested.

  1. Where the criterion is exact. In the linear feature model, Theorem 1 is an equivalence. On block models, where this model holds, the criterion predicts the sign of the gain in all 40 decisive cells (Section 4.1).
  2. What we test on real graphs. A tuned nonlinear head can use structure beyond the linear SNR. We therefore report the criterion on real graphs as a diagnostic and test the design consequences of the theory instead. All of them hold on the 46 graph and round pairs. No fixed scheme is safe everywhere. PPR stays within 1.74 points of no filter, while SGC falls up to 8.25 points below it. Adding the identity removes every significant loss, and the joint search is never significantly below any scheme (Table 1, Appendix D).
  3. Ordering the two schemes. The ordering of two tuned schemes depends on more than the linear SNR. This is why our first rule is to search both orders rather than to pick one by the criterion. Table R3 in our third reply shows that this search pays off even at a fixed budget.
  4. Guidance beyond validation. Validation says which filter wins on one split. The criterion explains why, and it predicts a large effect before any training. On Facebook100, the spectrum and the class means predict that every PPR filter lowers the SNR of the negative band X−\mathbf{X}^-, while SGC with K≤2K \le 2 raises it. Retraining on X−\mathbf{X}^- confirms this. SGC is significantly above the MLP on all five graphs, by 4.34 to 15.48 points, while PPR is not significantly above it on any (Table 8).
  5. The label-aligned ratio. We use this ratio where the SNR counts class mixing as signal. On block models at h=0.5h = 0.5, the SNR of the selected SGC filter predicts almost no effect (log⁡ρ=−0.05\log\rho = -0.05). In contrast, the label-aligned ratio predicts the loss (−0.71-0.71), and SGC loses 6.2 points (Appendix B). The PPR floor of this ratio (Proposition 4) holds on every graph.

W4 – Training labels only – Thank you for this check. With training labels only, the diagnostic gives the same conclusions. It agrees with the significant gaps in exactly as many cells as the version in the paper.

Setup. For each split, we compute the class means and class proportions from the training nodes of that split only. All other nodes carry no class signal. Each arm uses the log SNR ratio of the filter selected on each split, computed from that split's training labels and averaged over the ten splits. The gaps, the selection and the exact traces are the same as in the paper. When run with all labels, the same code reproduces the paper's values. We report the 45 of 46 graph and round pairs whose data we could download again during the discussion period (Wiki is missing).

Table R1: Agreement of the sign of the diagnostic with the significant gaps, on the 45 available pairs. Bold marks the best value in each column.

Class means fromAgrees with the gap to the MLP (84 significant cells)Orders PPR and SGC (37 significant cells)
All labelled nodes (paper)8015
Training nodes of each split (new)8016
Constant prediction "filtering helps"76—

As shown in Table R1, the training-label diagnostic loses nothing. Its sign matches the paper's version in 89 of the 90 (pair, scheme) cases, and the two versions have a correlation of 0.993. The diagnostic can therefore be computed in a realistic setting, before training, from training labels alone. We added Table R1 to the revision as Table 10 (Appendix F), and Section 4.2 now states that the diagnostic needs only training labels.

AuthorsOpenReview ↗

Response to Reviewer amNa (2/3)

W2 – Novelty of the theory – True, the covariance criterion and stochastic dominance are classical tools. Our contributions are the order of each scheme and the floor asymmetry. They give new, testable consequences.

We state this in the paper right after Theorem 2 (L245 - 247): parts (a) and (c) restate first-order stochastic dominance. What is new is what the two tools say about propagation schemes:

  1. The order of each scheme. PPR ranks frequencies by μ\mu, SGC by ∣μ∣|\mu|, and high-pass powers by −μ-\mu (Corollary 1). Appendix E (Table 9) gives the order of heat kernels, DGC, lazy powers and the identity. This turns one comparison per filter into one verdict for all hyperparameters of a scheme.
  2. The floor asymmetry. Every PPR filter passes every frequency with gain at least α/(2−α)\alpha/(2-\alpha), while adjacency powers can lose the whole SNR (Proposition 2). The PPR floor also holds for the label-aligned ratio (Proposition 4).
  3. Opposite verdicts on the same graph and task. Because the orders differ on the negative half of the spectrum, the two schemes can disagree on the same graph. On Facebook100, every PPR filter lowers the SNR of X−\mathbf{X}^-, while SGC with K≤2K \le 2 raises it. Retraining on X−\mathbf{X}^- confirms this: SGC is significantly above the MLP on all five graphs, and PPR on none (Table 8).

In the revision, Section 3 opens with these three points as its contributions, separate from the classical tools they use.


W2 – Relation to adaptive spectral filters [1–4] – Our results apply to any fixed response, so they also describe a learned response after training. They give two requirements for a learned filter.

Theorem 1 holds for every response gg, so it applies to the response learned by GPR-GNN [1], BernNet [2], Specformer [3] or HeroFilter [4]. Our results then give two requirements:

  1. Both orders must be reachable. Suppose the class signal dominates the noise along ∣μ∣|\mu| and is dominated by the noise along μ\mu. Then no μ\mu-ordered response such as PPR raises the SNR, while ∣μ∣|\mu|-ordered responses do not lower it (Theorem 2, as in Corollary 1(iii)). GPR-GNN contains both SGC monomials and PPR as special cases, as we note in Section 2 (L131 - 132).
  2. A floor bounds the loss. Proposition 2(a) applies to any learned response. If ∣g∣|g| stays away from zero over the spectrum, its SNR ratio is at least min⁡kg(μk)2/max⁡kg(μk)2\min_k g(\mu_k)^2 / \max_k g(\mu_k)^2.

This view also agrees with HeroFilter [4], which reports that the frequency response and the heterophily degree do not follow a strict monotonic relation. We added this discussion and reference [4] to Section 2, which already cites [1–3].


W2 – Converse of Theorem 2 – True, part (c) concerns the ordered class. For the two schemes, the paper also gives scheme-specific failing members.

  • PPR: If Bμ(t)≤0B_\mu(t) \le 0 for every tt, no PPR filter raises the SNR above that of the raw features, for any α\alpha (Corollary 1(ii)).
  • SGC: Under white noise and over all signal densities, the infimum of ρ(WK)\rho(\mathbf{W}^K) equals nmin⁡kμk2K/∑kμk2Kn \min_k \mu_k^{2K} / \sum_k \mu_k^{2K} (Proposition 2(c)). The value zero is attained by a concrete graph and its labels. On a complete bipartite graph whose classes split both sides, Wy=0\mathbf{W}\mathbf{y} = 0, so every power loses the whole SNR (L286 - 288).

The revision states these scheme-specific converses directly after Theorem 2.


[1] Chien et al., Adaptive Universal Generalized PageRank Graph Neural Network, ICLR 2021.
[2] He et al., BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation, NeurIPS 2021.
[3] Bo et al., Specformer: Spectral Graph Neural Networks Meet Transformers, ICLR 2023.
[4] Zhang et al., HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations, NeurIPS 2025.

AuthorsOpenReview ↗

Response to Reviewer amNa (3/3)

W3 – Practical value of the response floor – PPR's stability does not come from near-identity filters. Validation selects α≤0.5\alpha \le 0.5 in 87% of all splits, and in 91% of the splits where PPR beats the MLP.

We counted how many splits select each PPR filter over all 46 graph and round pairs (460 selections). This is Table 12 of the revision.

Table R2: Teleport parameter α\alpha of the PPR filter selected on validation, and its response floor α/(2−α)\alpha/(2-\alpha).

α\alpha0.050.10.20.30.50.70.9
Floor α/(2−α)\alpha/(2-\alpha)0.030.050.110.180.330.540.82
All 460 selections535986124784020
410 selections in the 41 pairs where PPR is significantly above the MLP50548511767334

As shown in Table R2, validation selects the near-identity filter α=0.9\alpha = 0.9 in only 4% of all splits, and in 1% of the splits where PPR wins. PPR therefore propagates substantially in most splits and yet never falls far below the MLP. Its worst gap to the MLP is −1.74 points, against −8.25 for SGC. When propagation does hurt, as on the negative band of Facebook100, validation can fall back to α=0.9\alpha = 0.9. The floor also bounds the loss of every member of the grid.

The analysis gives three design recommendations beyond keeping the identity:

  1. Which schemes need the identity. PPR, heat kernels and DGC with T<K/2T < K/2 have floors. Adjacency powers, lazy powers ((1+μ)/2)K((1+\mu)/2)^K and high-pass powers have none (Appendix E, Table 9). Like PPR, lazy powers rank frequencies by μ\mu, yet have no floor. So the order alone does not make a scheme safe, and the identity is needed exactly for the floorless schemes.
  2. Adding the identity costs little. Adding the MLP grid to a scheme removes all 9 significant losses to the MLP, and the only significant cost is 0.29 points (Table 4).
  3. Search both orders, even at a fixed budget. See the next point.

W4 – Fixed total search budget – We ran this comparison. At the budget of a single scheme, searching both orders and the identity is significantly above the MLP in 42 of 46 pairs on average. It falls below a full scheme far less often than either scheme falls below the other.

Setup. The joint search draws 20 of the 60 configurations from each arm, giving the same total of 60 candidates as one scheme. We repeat the draw 200 times and compare each draw with each full arm (60 candidates). Each comparison uses the paper's per-split selection and paired split bootstrap on all 46 graph and round pairs.

Table R3: Number of graph and round pairs (of 46) in which a search is significantly above or below a full arm. Joint search at 60 candidates: mean over 200 draws. Bold marks the best value in each column.

SearchCandidatesAbove MLPBelow MLPBelow full SGCBelow full PPR
SGC alone60367—27
PPR alone6041211—
MLP + SGC + PPR, 20 each (new)6041.91.05.48.5

As shown in Table R3, at an equal budget, the joint search keeps almost all of the gain over the MLP. It also falls below a full single scheme far less often than either scheme falls below the other. Committing to SGC loses to PPR in 27 pairs, and committing to PPR loses to SGC in 11 pairs. The joint search at the same budget loses to SGC and PPR in 5.4 and 8.5 pairs on average. With all 180 candidates (Table 1), it is never significantly below any arm. We added Table R3 to the revision as Table 11 (Appendix F) and state the budget of each search in Section 4.2.


We hope these answers and the new results address your concerns. Thank you!

Reviewer_JcL4OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This work studies decoupled models where the graph is used to precompute features and the learned architecture is graph-agnostic, particularly comparing SGC and PPR. They analyze how much linear signal-to-noise ratio these precomputations can preserve compared to the original features through a spectral analysis. Then they compare node classification settings, where there is no clear winner across datasets.

Critical strengths

None

Critical weaknesses

The whole paper is extremely dense in all parts. The theory is particularly cumbersome and unreadable. The insights are not clearly stated, and the conclusions look like checklists. Everything is obscured and overwhelming in exposition.

Moreover, I think that most of the insights do not mean much in practice. First of all, based on a recent paper on decoupled models with MLPs and concatenations can be competitive with GNNs (Rubio-Madrigal et al., ICML 2026), I would expect that many useful patterns of these aggregation processes are nonlinear. It's not clear how much their definition of signal can describe this. I would also expect that concatenating the intermediate aggregated representations is also quite important, and that some of the studied losses can be easily avoided by it. The end results seem to be that the important signal is task dependent, which is almost tautological, and leads to requiring learning aggregation.

Questions for authors

What is the incentive to study decoupled models' single aggregation representation?

If you don't know whether to filter or not, why not concatenate the features and let the model learn it?

How strongly is the dependence to the task with respect to the results of this paper?

Can the task depend on nonlinear patterns and how does this interplay with the analysis?

3 comments
AuthorsOpenReview ↗

Response to Reviewer JcL4 (1/2)

We thank the reviewer for the careful reading and for the pointer to fixed aggregation features [1]. Below, we answer each question directly. Following the reviewer's suggestion, we ran the paper's protocol with concatenated features on all available graph and round pairs. We uploaded a revised paper, with new text in blue.


W1 – Density of the presentation – Fair point. We restructured Section 3 around three plain statements and moved technical details to the appendix.

The three insights of the paper, in one sentence each:

  1. A fixed filter helps exactly when it amplifies the frequencies where the class signal exceeds the noise (Theorem 1).
  2. PPR and SGC amplify frequencies in different orders, so on the same graph one can help while the other hurts (Theorem 2, Corollary 1). Facebook100 is such a graph (Table 8).
  3. PPR can never lose much, while adjacency powers can lose everything (Proposition 2). Hence a search should cover both orders and keep the identity in schemes without a floor.

In the revision, we:

  • opened Section 3 with these three statements and Figure 1, before any formal definition.
  • preceded each theorem with one plain sentence that says what it means for a practitioner.
  • moved the strictness clauses, Theorem 2(c) and the details of Propositions 3 and 4 to Appendices A and B.
  • rewrote the conclusion as a short paragraph of findings.

Q1 – Why study a single precomputed filter – Because it is the design of SGC and precomputed PPR, and because every concatenation method is built from such filters.

  1. Use and cost. SGC and precomputed PPR store one filtered feature matrix and train an MLP at the cost of a plain MLP. Concatenating KK hops stores K+1K+1 matrices of size n×dn \times d, which matters on large graphs.
  2. Building block. Each block of a concatenation is a fixed filter g(W)Xg(\mathbf{W})\mathbf{X}. Our results say which blocks a concatenation needs: blocks from both frequency orders, and the identity block when the other blocks have no floor.

Q2 – Why not concatenate and let the model learn it – Concatenation is a good design, and our rules explain when it helps. We added this experiment.

A concatenation [X∣g1(W)X∣… ][\mathbf{X} \mid g_1(\mathbf{W})\mathbf{X} \mid \dots] contains the identity block. A linear head on it can realize any combination ∑jcjgj(W)X\sum_j c_j g_j(\mathbf{W})\mathbf{X}, including X\mathbf{X} alone. So, in the population, the best linear classifier on the concatenation is never worse than on X\mathbf{X}. This is exactly the floor that our second rule asks for. The fixed aggregation features of [1] follow this pattern. They keep the hop-0 features, and their mean aggregations are SGC-type powers of a normalized adjacency.

Setup. We trained an MLP on [X∣WX∣W2X][\mathbf{X} \mid \mathbf{W}\mathbf{X} \mid \mathbf{W}^2\mathbf{X}] with the paper's protocol: the same 60 heads and seeds, the same splits, per-split validation and the paired split bootstrap. Each head used the operator that the SGC arm drew for it.

Table R1: Concatenation compared with each scheme in the paper, on the 45 available graph and round pairs (Wiki is missing). Counts are pairs where concatenation is significantly above or below.

Concatenation compared withSignificantly aboveSignificantly belowMean gap
MLP on X\mathbf{X}401+5.65
SGC2314+0.75
PPR1311+0.67
Joint search over MLP, SGC and PPR (our rule)821−0.70

As shown in Table R1, the result supports both of our rules.

  • The identity block acts as a floor. Concatenation is significantly above the MLP in 40 of 45 pairs and below it in only one (Actor, by 1.81 points). This is the floor that our second rule asks for.
  • Concatenation does not replace the search over both orders. The joint search over MLP, SGC and PPR is significantly above concatenation in 21 pairs and below it in 8. The largest gaps are on Facebook100, where the validation-selected SGC filter is above concatenation by 3.07 to 14.12 points. On this graph family, the paper traces the advantage of SGC to its frequency order (Table 8).

On the two graphs we checked, rerunning the MLP arm on our current machines moves its accuracy by at most 0.61 points. This is far less than these gaps.

We added this experiment to the revision as Table 13 (Appendix F) and summarize it in Section 4.2.


[1] Rubio-Madrigal and Burkholz, Fixed Aggregation Features Can Rival GNNs, ICML 2026.

AuthorsOpenReview ↗

Response to Reviewer JcL4 (2/2)

W2, Q4 – Nonlinear patterns – Our real-graph experiments already use nonlinear learners, and the design rules hold with them.

  1. Every real-graph head is nonlinear. Each head is an MLP with one or two hidden layers, normalization, ReLU and dropout, tuned over 60 configurations (Appendix C). All real-graph results use these heads. No fixed scheme is safe on every graph, PPR stays close to no filter, and the joint search is never significantly below any scheme (Table 1, Appendix D).
  2. The full head budget does not change this. When each selected filter is trained with all 60 heads, SGC remains significantly below the MLP in all seven pairs, and no significant comparison between SGC and PPR changes sign (Table 7).
  3. A filter limits every learner, linear or not. The filtered features are a fixed function of X\mathbf{X}. If a filter sets the frequencies that carry the class signal to zero, no downstream learner can recover them. Adjacency powers can do this (Proposition 2(c)). A PPR filter cannot, because its response is at least α/(2−α)\alpha/(2-\alpha) at every frequency.

The theory measures this effect with the linear SNR, which is exact in the feature model (Theorem 1). On block models, the sign of the SNR change agrees with the sign of the accuracy change of a trained classifier in all 40 decisive cells (Section 4.1).


Q3 – Dependence on the task – The task enters only through where its class signal lies in the spectrum. The PPR floor does not depend on the task at all.

  • Explicit dependence. For a given graph, a scheme's verdict depends on the task only through the class signal aka_k at each frequency. This signal is compared with the noise along the scheme's frequency order (Theorem 2).
  • Task-free guarantee. The PPR floor holds for every class signal and every noise covariance (Propositions 2 and 4).
  • Stable across the 30 tasks we tested. Across all 46 graph and round pairs, the joint search over MLP, SGC and PPR is never significantly below any of them (Appendix D).

W2 – Practical meaning of the insights – Respectfully, the result is more specific than task dependence. It names the deciding quantity and predicts which scheme fails.

The result does not stop at "the useful signal depends on the task". It names the deciding quantity: the class signal compared with the noise along each scheme's frequency order. It then predicts which scheme fails on a given graph. On Facebook100, from the spectrum and the class means, it predicts that every PPR filter lowers the SNR of the negative band X−\mathbf{X}^-, while SGC with K≤2K \le 2 raises it. Retraining confirms this. On X−\mathbf{X}^-, SGC is significantly above the MLP on all five graphs, by 4.34 to 15.48 points, while PPR is significantly above it on none (Table 8). The practical consequences are simple rules: search both orders, and keep the identity when a scheme has no floor. The concatenation experiment above also supports these rules.

We hope these answers and the new concatenation experiment address your concerns. If they do, we would be grateful if you would consider raising the score.

Thank you to the authors for their response and the additional experiments. The timing of the rebuttal left me little time to assess all the new content, and particularly I would have liked to assess how the other reviewers' concerns were answered. I also feel that some of my questions were misunderstood and would have appreciated more time to discuss the actual ones. My main concerns remain unresolved, so I am keeping my original score.

Q1. I understand the argument about cost, although feature selection can reduce the additional cost of concatenation in practice. My concern with the second reason is that determining which blocks a nonlinear model needs requires an argument about how it uses those blocks jointly. The paper analyzes what each block preserves in isolation.

Q2. The finding that concatenating intermediate aggregations can improve performance is consistent with the paper I cited and supports my original review. In the new experiment, concatenation significantly improves over the raw-feature MLP in 40 of 45 graph–round pairs. The cases where a single filter still performs better raise a different question that is not addressed in the current paper.

I also have a concern about the last row of Table R1. The reported 21–8 result in favor of the joint search compares 180 candidates across the MLP, SGC, and PPR grids with 60 candidates for concatenation. A fair comparison at the same tuning budget would put the 60-candidate joint search directly.

Q3. I understand where task dependence enters the theory. My question was how much changing the target can change the interpretation of the results. Even on the same graph with the same features, a different target can make different frequencies useful and reverse which filter is preferable. Since validation can select a different filter for each target, the joint search could perform well across all 30 datasets even if the preferred filter changed every time.

Q4. My question concerned nonlinear relationships between signals from different aggregation steps. For example, a label might depend on whether a node’s own feature and its neighbors’ average have the same sign. An MLP given both quantities can learn that relationship. If either quantity alone is insufficient, a nonlinear classifier receiving only that quantity still lacks the information it needs. The gains from concatenation are consistent with this possibility. What I wanted to understand is how much the paper's definition of signal captures in such cases. I find the conclusion that different filters can lose different kinds of signal depending on the task of limited practical value unless the analysis helps identify when a single aggregation loses a relationship that matters for prediction.

Comments on the paper

1 comment
AuthorsOpenReview ↗

To the Area Chair and all Reviewers: summary of the discussion and the revised paper. Thank you!

We thank the Area Chair and all reviewers for their time and constructive feedback. Below, we summarize the strengths the reviewers noted, how we addressed each concern, and what the revised paper contains. We uploaded a revised paper, with new text in blue.


Strengths noted by the reviewers

  • A unified view of fixed filters. amNa finds the frequency-order characterization interesting, because it gives "a unified perspective on when families of fixed filters improve or degrade spectral SNR".
  • Explaining heterophily. mbqZ notes that the two frequency orders "help explain, to some extent, why certain graph convolution methods remain effective on strongly heterophilous graphs".
  • Rigorous theory and thorough evidence. mbqZ values the "relatively comprehensive set of theoretical proofs" and the "simple and practical design principles". amNa finds the study on 30 real graphs and the Facebook100 intervention "thorough".

Main concerns and how we addressed them

  • JcL4 finds the presentation dense. We restructured Section 3.
    • Section 3 now opens with three plain statements, and each theorem is preceded by one sentence for practitioners. We moved technical clauses to Appendices A and B.
  • JcL4 asks why we do not concatenate the features. We added this experiment.
    • Concatenation is significantly above the MLP in 40 of 45 pairs. Its identity block acts as the floor that our second rule asks for. The search over both orders is still significantly above concatenation in 21 pairs and below it in 8 (Table 13).
  • JcL4 and mbqZ ask about nonlinear learners and the link from SNR to accuracy. Our evidence already uses tuned nonlinear heads.
    • Every real-graph result uses MLP heads tuned over 60 configurations. On block models, the sign of the SNR change agrees with the sign of the accuracy change in all 40 decisive cells.
  • amNa asks whether the diagnostic works with training labels only. It does.
    • With training labels only, it agrees with the significant gaps in the same 80 of 84 cells as the version in the paper (Table 10).
  • amNa asks for a fixed total budget. Searching both orders pays off at equal budget.
    • At the budget of one scheme, the joint search falls below a full SGC or PPR grid in 5.4 and 8.5 pairs on average. Committing to SGC loses to PPR in 27 pairs, and committing to PPR loses to SGC in 11 (Table 11).
  • amNa asks whether PPR is stable only because it stays near the identity. It is not.
    • Validation selects α≤0.5\alpha \le 0.5 in 87% of all splits and the near-identity α=0.9\alpha = 0.9 in only 4% (Table 12).
  • amNa asks for clearer novelty, a link to adaptive filters and scheme-specific converses. All three are now in the paper.
    • Section 3 separates our contributions from the classical tools. Section 2 explains what our results require of a learned response. The converses for PPR and SGC follow Theorem 2.
  • mbqZ asks for heterophily measures on real graphs. We added them.
    • The rank correlation of adjusted homophily with each gap lies between −0.06 and 0.03. Homophily alone does not decide the better scheme, and the frequency order explains the clearest case, Facebook100 (Tables 14 and 15).
  • mbqZ asks about band-pass filters and large graphs. We added both.
    • Table 9 now gives the score and floor of band-pass filters. On ogbn-products, with 2.4 million nodes, SGC and PPR gain 14.89 and 14.35 points over the MLP, and the joint search matches the better scheme (Table 16).

What the revised paper contains

Section 3 opens with the three main statements and our contributions. Section 2 discusses fixed aggregation features and adaptive spectral filters. Section 4.2 summarizes the new analyses, Table 9 adds band-pass filters, and Appendix F reports the new results in Tables 10 to 16. All original table, theorem and section numbers are unchanged.


Contributions to the community

  • A spectral lens for whole propagation schemes. One covariance decides whether a fixed filter beats no filter, and one frequency order gives a verdict for every hyperparameter of a scheme.
  • A floor asymmetry with practical consequences. PPR can never lose much, while adjacency powers can lose everything. This tells practitioners which schemes need the identity.
  • Two simple design rules, tested at equal budget. Search both frequency orders, and keep the identity in schemes without a floor. The rules hold on block models, on 30 real graphs, at a fixed total budget, against concatenation and on a graph with millions of nodes.
  • A reproducible equal-budget evaluation of fixed filters, with code for every experiment.

We sincerely thank the Area Chair and the reviewers. Their questions led to new experiments and a clearer paper, and we hope the revision shows the value of this work to the community.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.