A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition

We thank the referee for taking the time to review our paper. Please, see below our answer to the raised comments/questions.

Q1: The quality of Figure 1 is still not good enough.

We have improved the image resolution of Figure 1 at https://drive.google.com/file/d/1rfuYedo4FkeLg1zClq45ZOHU6rH-p8L4, and will update the figure in the next version of the paper.

Q2: Practical advantage of being admissible.

The wavelet admissibility criterion is not just a theoretical preference—it is a fundamental requirement for a function to be considered a valid wavelet. Without satisfying this condition (i.e., g(0)=0), a function labeled as a "wavelet" loses its essential localization property. As discussed in our response to Reviewer 4MPc (Q1), this localization enables node-specific filtering, where each node can capture local deviations from the global signal structure. In contrast, non-admissible constructions (e.g., DEFT [Bastos et al., 2022]) lack this guarantee, leading to less precise node-level modeling.

The practical advantage of admissibility becomes evident in tasks that require strong node-wise representation learning. For instance:

$\bullet$ In short-range node-level tasks (e.g., CS, Photo, Computer, CoraFull, ogbn-arxiv), WaveGC consistently outperforms baselines.

$\bullet$ In long-range node-level tasks (e.g., VOC and COCO), WaveGC also demonstrates superior performance.

$\bullet$ To further validate the node-level expressiveness, we conducted additional experiments on heterophilous datasets (e.g., Actor and Tolokers), where accurate node-level modeling is particularly challenging. Results, shown in Table 1, confirm that WaveGC outperforms DEFT.

Together, these results across homophily, heterophily, short-range, and long-range settings support the claim that admissibility leads to more effective and localized node-wise signal processing, providing WaveGC with a substantial practical advantage over prior non-admissible designs.

We thank the reviewer for the careful reading and comments regarding our work. Please, see below our answer to the raised comments/questions. The link for the table is available at https://drive.google.com/file/d/146c3rsB_eJLJmk3I21aWg9fzGPpCvd7S.

Q1: Compare with SOTA methods based on Fourier bases with further discussion theoretically and experimentally.

Below we address both experimental and theoretical aspects:

1. Experimental Comparison

We have conducted additional experiments comparing WaveGC with four representative Fourier basis-based methods—GPR-GNN, BernNet, UniFilter, and S²GCN—on three long-range and three short-range datasets. As shown in the newly added Figure 1, WaveGC consistently outperforms these baselines, with particularly strong gains on long-range tasks. This empirically supports the practical advantages of our wavelet-based design, especially in modeling multi-scale information.

2. Theoretical Perspective

a) The core distinction between WaveGC and Fourier-based spectral methods lies in their design focus:

$\bullet$ Fourier-based methods typically fix the basis (Laplacian eigenvectors) and focus on designing flexible filters.

$\bullet$ WaveGC, by contrast, introduces a novel learnable basis construction via graph wavelets and Chebyshev decomposition, while using a matrix-valued kernel as the filter.

These two directions—basis design and filter design—are complementary rather than mutually exclusive. In fact, a hybrid method (e.g., applying Bernstein polynomials as filters on our wavelet bases, akin to a "BernWave" model) could be a promising future direction.

b) Localization and Adaptivity

Graph wavelets offer node-level localization due to the property g(0)=0 and the small values of g(λ) at low frequencies. This enables each node to respond to local deviations from global structure, creating node-dependent filters. In contrast, Fourier bases are inherently global, with eigenvectors representing community-level structures—leading to community-dependent filters.

WaveGC benefits from this localized adaptivity, further enhanced by the scaling parameter s, which enables multi-resolution control. This is critical for tasks requiring both short- and long-range information modeling.

c) Scope of Fourier Methods

While many recent Fourier-based methods are effective in scenarios such as homophily/heterophily adaptation (e.g., GPR-GNN), they do not explicitly model spatial scale or receptive field. Even methods like S²GCN, which improve long-range capture via kernel design, may be limited by the fixed Fourier basis. Combining such techniques with our wavelet-based approach could potentially lead to stronger long-range generalization.

We will include the new experimental results and expand our discussion in the paper to address these points.

Q2: Scaling to large graphs.

1. Different Designs for Different Scenarios: While Fourier-based methods scale well to massive graphs, they often sacrifice expressiveness—particularly in long-range modeling, where WaveGC consistently outperforms them (Table 1 in the link). We believe model design should align with task demands rather than aim for universal scalability.
2. Applicability to Current Datasets: The eigendecomposition required for WaveGC has O($N^3$) complexity in the worst case and O($N^2$) in training. This is practical for the small-to-medium graphs used in long-range benchmarks, where detailed spectral modeling is critical.
3. Our focus is on constructing learnable, admissible wavelet bases—a core challenge in spectral graph learning. Scaling spectral methods efficiently is an important but orthogonal problem that we identify as promising future work.

Q3: Can WaveGC approximate functions meet the requirements?

We agree that using odd and even Chebyshev polynomials to construct h(λ) and g(λ) provides a sufficient but not necessary condition for wavelet admissibility. While our method does not guarantee representation of all admissible function pairs (g,h), it introduces a strong inductive bias through the separation of odd and even Chebyshev terms, enabling a principled and controllable wavelet construction.

Despite this restriction, our approach offers strong practical approximation capacity due to several factors:

$\bullet$ Chebyshev polynomials form a complete basis over [0,2], allowing approximation of any continuous function on this interval.

$\bullet$ The separation into odd and even terms allows independent control over h and g while preserving admissibility.

$\bullet$ Learnable coefficients enhance flexibility in shaping the filter functions.

$\bullet$ The scaling parameter s further adapts the spectral response.

Together, these elements form a flexible and expressive class of wavelet filters suitable for practical graph learning. We will clarify this approximation perspective in the revised manuscript.

We appreciate the review provided. Please, find below our clarifications on the points raised, and the link to the figures & tables: https://drive.google.com/file/d/1DALF7e1t6O4SSMUkvfi2euMufIpNJARv.

Q1: Analysis of learned scales and experimental impacts.

1. Learned Scales and Receptive Fields

Figure 1 visualizes the largest learned scales and corresponding receptive fields for Ps and VOC, using the heuristic: Given a wavelet Ψ(sλ), node j lies in the receptive field of node i if |Ψ(sλ)[i, j]| > 0.1 × max(|Ψ(sλ)|).

Under this criterion, Ps exhibits a significantly larger receptive field (scale = 9.48), aligning with its inherently longer average shortest-path distances. Table 1 further confirms this through average and max receptive field sizes across all nodes.

2. Behavior at Extremely Large Scales (s → ∞)

We increased the predefined scale vector $\bar{s}$ in Eq. (7) for Pf to be (10, 100, 1000). This vector determines the upper bound of the learnable scale range. As shown in Figure 2, the receptive field expands from local (s = 9.17) to global (s = 988.24), empirically supporting our theoretical claim that WaveGC captures long-range dependencies as 𝑠→∞.

Q2: Verify the necessity of MPNN for low-frequency information.

As shown in Table 2 (w/o MPNN), WaveGC remains competitive without the MPNN branch, though with some performance drop—demonstrating its adaptability while also showing the benefit of MPNN.

Wavelet bases are inherently localized and suppress low-frequency signals, enabling node-specific filtering for local structure modeling. However, global community-level information—captured by low-frequency components—is still important. A single scaling function h(λ) appears insufficient to model this alone, as reflected by the performance drop without MPNN. Therefore, we argue that including an MPNN branch complements the wavelet by restoring low-frequency (community-level) signals.

Notably, removing the wavelet branch (w/o wavelet) leads to a larger performance drop, confirming that wavelets are the primary contributor, with MPNN as a helpful supplement.

Q3: Description on kernel parameters.

Our goal is to balance expressiveness and efficiency. While matrix-valued kernels offer greater capacity than vector-valued ones, assigning separate matrices per frequency (as in FNO) leads to excessive parameters and risk of overfitting. To mitigate this, we use a shared MLP across frequencies, which retains modeling power while keeping parameter count low. As shown in Tables 3 and 4, this strategy improves performance with manageable complexity. We will revise the text to clarify this trade-off.

Q4: Usage of tight frames and parameter sharing.

1. Parameter sharing. In Appendix D.7, “parameter sharing” refers to sharing parameters across stacked WaveGC+MPNN blocks (Fig. 2 in the paper). Most datasets use independent parameters per layer, which performed better empirically. This is unrelated to the matrix kernel’s weight-sharing, which is always applied. We will revise the wording to clarify this.

2. Tight frames. The tight frame condition simplifies Eq. (9), but requires normalizing the scaling and wavelet bases, which may restrict model expressiveness. For ogbn-arxiv and Peptides-struct, we relaxed this constraint (i.e., omitted normalization) to prioritize performance. Importantly, all datasets still used Eq. (9), so the computational efficiency remained unaffected.

Q5: Does MLP(F(X)) facilitate interaction between node features?

It is correct that the matrix-valued kernel (via MLP) operates within the feature dimension of each spectral component, not directly across frequency modes. Each row in $F(X)\in \mathbb{R}^{N(J+1) \times d}$ is transformed independently by the shared MLP.

However, since all spectral modes share the same MLP, the model learns a unified transformation that generalizes across modes. This shared design indirectly couples the modes, as the MLP must accommodate diverse spectral inputs. We will revise the text to clarify this mechanism.

Q6: Rationality of only keeping the first 30% graph spectrum.

Following your suggestion, we tested three types of spectral filters: 1) Low-frequency (diffusion) kernel: g1(λ)=exp⁡(−β⋅λ), 2) High-frequency kernel: g2(λ)=exp⁡(−β⋅(2−λ)) and 3) Combined kernel: g3(λ)=g1(λ)+g2(λ). Applied using R=Ug(λ)U⊤, the results (Table 6) show that g1 consistently outperformed the others across four short-range datasets. In contrast, g2 performed poorly, and g3 showed mixed results. On ogbn-arxiv, the diffusion kernel caused OOM.

These findings support our choice to retain only the first 30% of the spectrum: it captures the most relevant low-frequency signals while reducing computational cost and noise from high-frequency parts.

Q7: Use the same datasets across experiments.

We have supplemented experiments as in Tab. 3, 4 and 5 in the link. New results did not overturn the conclusions in the paper.

We thank the reviewer for reviewing our work. Please, see below our answer to the raised comments/questions.

Q1: Eq. (1) is inappropriate.

Eq. (1) describes requirements for general wavelets as introduced in Mallat’s book in 1999, not only graph wavelets, where g(λ = 0) = 0 is important for any data format. Thanks for your feedback, and we will change Eq. (1) to discrete version.

Q2: Why using a full matrix-valued kernel when a diagonal kernel is sufficient for 1D orthogonal transforms like the graph Fourier or wavelet transform?

It is true that, in the context of classical 1D discrete orthogonal transforms (such as the Fourier or wavelet transform), convolution in the spectral domain can be represented using a diagonal matrix where each diagonal entry scales the corresponding frequency component. This is the foundation for many spectral GNNs that use vector-valued kernels (e.g., diag(θλ)).

However, our design departs from this classical formulation by introducing a matrix-valued kernel, which enables richer transformations. Specifically:

1. Diagonal kernels perform independent scaling across feature channels for each frequency mode, limiting the ability to model interactions between features.
2. Matrix-valued kernels, in contrast, allow interaction within the feature dimension at each frequency mode. This is particularly useful in deep learning settings where features are multi-dimensional, and learning correlations between them is beneficial.
3. Furthermore, in our implementation, the same transformation (via a shared MLP) is applied across all spectral modes. This enforces a consistent filtering mechanism while keeping the parameter count manageable.

Thus, while a diagonal kernel is mathematically sufficient for linear spectral filtering, we adopt a matrix-valued kernel to increase expressiveness and enable learnable feature-channel interactions, which empirically improves performance (as shown in Section 6.2). This design is inspired by similar motivations behind matrix-valued kernels in Fourier Neural Operators and Transformer models. We will revise the manuscript to more clearly explain this motivation and distinguish our approach from classical spectral filtering.

Q3: What are S and W in Eq. 9?

S and W are the same as M in line 191 in the left column, representing different matrix-valued kernels. We will clarify this point.