- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper introduces BernNetII, which aims to improve BernNet for heterophilic graph learning. Three modifications are applied: coefficient decomposition, learnable spectral warp, and residual bypass. The filter coefficients are decomposed into smooth and step components with separate regularization. The spectral warp rescales the evaluation domain of the Bernstein basis, while the residual bypass retains self representation alongside the propagated representations. The authors provide theoretical analyses of the properties of the decomposition, spectral warp, convergence and generalization bound. They then evaluate BernNetII on eight node-classification benchmarks under fully supervised and semi-supervised settings.
Critical strengths
The proposed modifications are simple and effective, although I have concerns about their justification and empirical contribution (see Critical Weaknesses).
Critical weaknesses
Here are my concerns for each of the proposed modifications.
-
The motivation for the sharp step component is insufficiently supported. The learned spectral responses visualized in the original BernNet (Figure 4 of [1]) and ChebNetII (Figure 6 of [2]) exhibit, even for heterophilic datasets, smooth curves rather than step-like patterns. The authors should provide evidence supporting the need for step-like spectral responses in real-world classification tasks, for example by citing relevant prior work or providing convincing explanations or analysis. It would be also great if the authors show whether BernNetII actually learns such responses, e.g., providing visualizations of the learned spectral responses of BernNetII.
-
The theoretical result does not establish the claimed benefits of spectral warping. Section 3.2 states that Proposition 4 shows that the warp reduces approximation error by focusing polynomial degrees on the effective frequency band. However, the proposition only establishes that the filter’s total variation remains bounded by the coefficients’ discrete total variation, which does not demonstrate improved approximation accuracy or more efficient allocation of filter domains. The claimed benefit requires further theoretical analysis or empirical evidence.
-
The improvements beyond the residual modification of BernNet are unclear. The residual bypass is straightforward to add to the original BernNet, making BernNet with the same learnable bypass an essential baseline. Without the bypass, the most substantial improvement over BernNet is concentrated only on Chameleon, while the gains on Squirrel and Texas are small, and performance decreases on Cornell, Cora, and Pubmed. Although the component-removal ablations suggest that warp and decomposition contribute within the full model, they do not establish their value over BernNet with a bypass. A matched comparison is needed to determine whether the two main proposed modifications provide benefits beyond the baseline.
[1] BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. NeurIPS 2021.
[2] Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited. NeurIPS 2022.
Questions for authors
Could the authors address the concerns raised in Critical Weaknesses?
5 comments
I generally accept the authors' explanations for spectral warping and the residual bypass. However, in my view, both are closer to practical tricks than substantial contributions. Spectral warping is mainly supported by empirical results, while its theoretical motivation remains largely intuitive. As for the residual bypass, I see it as a fairly standard technique rather than a novel contribution. Therefore, I do not consider either of them a main contribution of this paper.
In my view, the most interesting and potentially significant contribution is the proposed decomposition of spectral filter coefficients into smooth and step components. After reading the authors' additional explanations, I find this idea plausible and potentially useful. However, I am still not fully convinced about how broadly applicable the assumption of step-like spectral structures is in real-world tasks, or whether the proposed decomposition actually learns the intended step-like components.
For instance, the model mainly tries to achieve this separation through different regularization terms. However, the two components are still jointly learned and further coupled through the curvature-alignment penalty, so it is unclear whether they can truly separate global smooth trends from localized sharp variations. For example, on Squirrel (Figure 2), the label spectrum is relatively smooth except for a narrow notch near , whereas the learned filter exhibits a much broader suppression region and substantial variations across other frequencies. Although the label spectrum and learned filter need not have the same shape, this result raises questions about whether the proposed decomposition works as intended.
I will keep my score unchanged, but I would encourage the authors to reconsider the priorities and emphasis of the paper. In particular, I suggest placing less emphasis on spectral warping and the residual bypass, and investigating the proposed decomposition more thoroughly, as I believe this is a genuinely interesting research question. For example, the following questions may be worth exploring:
- Why do sharp spectral variations occur at different frequencies across datasets? Are there any underlying patterns, and how are they related to graph homophily and heterophily?
- How can we design a better decomposition that effectively separates global smooth trends from localized sharp variations?
P.S. I think the paper may confuse two different things: heterophily is often associated with stronger high-frequency graph signals, but this does not necessarily mean that the spectral filter itself needs sharp variations. For example, a smooth high-pass filter can also emphasize high-frequency signals.
Thank you for the careful reading and for identifying the decomposition as the most interesting part of the work. We agree that it is the central idea. Proposition 3, Theorem 5 and Proposition 6 all concern it, and the final version will state this priority in the introduction.
Separation under joint learning. The two components do separate, and the split is fixed by the regularisers, as in morphological component analysis (Starck et al., 2005). Because the forward pass depends on and only through , the loss cannot distinguish two splits of the same . For and given weights of , exactly one split of each minimises the regularisers (Section 3.1), so any stationary point reached by training has this split. The weights of are computed with stop-gradient, so only weights the penalty on and does not mix the components. This split places each kind of structure in the intended component. By Proposition 3, a sufficiently large jump in cannot stay entirely in , and by the optimality condition of the fused lasso, whenever every second difference of is at most in absolute value. Accordingly, the learned on Cora and Citeseer is a single jump between and (Appendix G).
Width of the stopband on Squirrel. The wide stopband on Squirrel is a limit of the polynomial degree, not a failure of the decomposition. The notch is one bin, in , wide, whereas a single jump in the Bernstein coefficients already gives a transition about wide for and , from 10% to 90% of its height (Appendix G). A filter of this degree therefore cannot follow the notch, and the stopband formed by the zero coefficients , and has a width set by this resolution. Within this resolution, the response follows the label spectrum. The label energy is near or below the random-label band only in the first bin and around , and these are exactly the places where the response is lowest.
Smooth or sharp filters (P.S.). The sharp variations in BernNetII are steps at the edges of narrow bands that carry the class information, not the high-frequency emphasis of a smooth high-pass filter, and these steps are needed. The key point is the width of the informative band, not its frequency. The stochastic block model analysis in Section 2.4 shows that the response that separates the classes is one on a few bands and zero elsewhere, and Appendix G finds such narrow bands in five of the eight label spectra. Because a narrow band must be passed while its neighbours are suppressed, the filter has to change within a short interval of at the edges of the band, which a smooth filter cannot do, whether the band lies at low or high frequency. This is why steps also appear on the homophilic Cora and Citeseer, and why the band-stop target of Chameleon and Squirrel, with class information on both sides of , cannot be met by a high-pass filter. When the informative band is wide, a smooth filter suffices, and BernNetII represents it without the step component. The high-pass filter , for example, has the coefficients with zero second differences and is represented with at no regularisation cost.
We hope this resolves your remaining questions, and we would be grateful if you would take it into account in your final assessment.
References
Starck, J. L., Elad, M., & Donoho, D. L. (2005). Image decomposition via the combination of sparse representations and a variational approach. IEEE transactions on image processing, 14(10), 1570-1582.
W1. The label spectra of real datasets contain sharp transitions, and the coefficients learned by BernNetII contain the corresponding jumps. As a model-independent check, we projected the node labels onto the Laplacian eigenvectors and compared the result with randomly permuted labels (Appendix G). On Cora the label energy drops by more than an order of magnitude within λ≤0.2, and on Chameleon and Squirrel the label spectrum has a narrow notch near λ≈1. This agrees with the stochastic block model, where the classes are recovered from a few eigenvectors, so the ideal response is one on a few bands and zero elsewhere (Rohe et al., 2011). The curves in Fig. 4 of [1] and Fig. 6 of [2] look smooth because the slope of a polynomial of degree 10 is bounded by Markov's inequality (DeVore and Lorentz, 1993), whether or not the target has a step. In the Bernstein basis a sharp transition appears as a jump in the coefficients, and a jump in β gives a single transition without overshoot whose oscillation is at most ∥β∥DTV (Theorem 1). BernNetII learns a steep low-pass filter on Cora and a band-stop filter on Chameleon and Squirrel whose stopband lies on the notch (Figure 2), with the forward-pass coefficients θ4+=θ5+=θ6+=0 in all ten runs on Chameleon and in seven of ten on Squirrel. In Table 6, removing the decomposition lowers accuracy on seven of the eight datasets, by 3.09 points on Squirrel.
W2. Proposition 4 guarantees that the regulariser remains effective under the warp, and the benefit of the warp is supported by the ablation in Table 6. Theorem 1 bounds the oscillation of the filter by the DTV of its coefficients for the original Bernstein basis. The warp replaces the argument λ/2 by sλ/2 and therefore changes the basis functions, and Proposition 4 proves that the same bound holds for every s. The warped basis spans the same polynomials for every s, so the benefit of the warp is established empirically. In Table 6, removing the warp lowers accuracy on seven of the eight datasets, by 3.01 points on Squirrel. The sentence after Proposition 4 has been revised accordingly.
W3. Appendix F now includes BernNet with the same bypass, initialisation, seeds and splits as BernNetII. BernNetII exceeds this baseline on seven of the eight datasets, by 3.82 points on Squirrel and by 1.3 to 1.9 points on Chameleon, Texas, Cornell and Actor. The same table removes the warp and the decomposition separately, and each removal lowers accuracy on seven of the eight datasets. The warp and the decomposition therefore add value beyond the bypass.
References
DeVore, R. A., & Lorentz, G. G. (1993). Constructive approximation (Vol. 303). Springer. Rohe, K., Chatterjee, S., & Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4), 1878-1915.