A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition
Authors: Nian Liu
Xiaoxin He
Thomas Laurent
Francesco Di Giovanni
Michael M. Bronstein
Xavier Bresson
Venue: ICML 2025 poster (2025)
Keywords: graph wavelet neural network
graph signal processing
Primary area: deep_learning->graph_neural_networks

Abstract: Spectral graph convolution, an important tool of data filtering on graphs, relies on two essential decisions: selecting spectral bases for signal transformation and parameterizing the kernel for frequency analysis. While recent techniques mainly focus on standard Fourier transform and vector-valued spectral functions, they fall short in flexibility to model signal distributions over large spatial ranges, and capacity of spectral function. In this paper, we present a novel wavelet-based graph convolution network, namely WaveGC, which integrates multi-resolution spectral bases and a matrix-valued filter kernel. Theoretically, we establish that WaveGC can effectively capture and decouple short-range and long-range information, providing superior filtering flexibility, surpassing existing graph wavelet neural networks. 
To instantiate WaveGC, we introduce a novel technique for learning general graph wavelets by separately combining odd and even terms of Chebyshev polynomials. This approach strictly satisfies wavelet  admissibility criteria. Our numerical experiments showcase the consistent improvements in both short-range and long-range tasks. This underscores the effectiveness of the proposed model in handling different scenarios.

A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition
Nian Liu' Xiaoxin He!
Thomas Laurent? Francesco Di Giovanni Michael M. Bronstein 34 Xavier Bresson
Abstract
of the convolution operation to graphs, as convolution for grid-structured data, i.c. sequences and images, has demon- strated remarkable success (LeCun et al., 1998; Hinton et al., 2012; Krizhevsky et al., 2012). Significant research interests in graph convolution revolve around two key factors: (1) de- signing diverse bases for spectral transform, and (2) param- eterizing powerful graph kernel. For (1), the commonly used graph Fourier basis, consisting of the eigenvectors of the graph Laplacian (Shuman al., 2013), stands as prevalent choice. However, graph wavelets (Hammond et al., 201 offer enhanced flexibility by constructing adaptable bases. For (2), classic approaches involve diagonalizing the kernel with fully free parameters (Bruna et al., 2013) or employing various polynomial approximations such as Chebyshev (Def- ferrard et al., 2016) and Cayley (Levie et al., 2018) polyno- mials. Additionally, convolution with tensor-valued kernel serves the spectral function of Transformer (Vaswani et al., 2017) under the shift- thift-invariant condition (Li et al., 2021; Guibas et al., 2021).
Spectral graph convolution, an important tool of data filtering on graphs, relies on two essen- tial decisions: selecting spectral bases for sig- nal transformation and parameterizing the ker- nel for frequency analysis. While recent tech- niques mainly focus on standard Fourier trans- form and vector-valued spectral functions, they fall short in flexibility to model signal distribu- tions over large spatial ranges, and capacity of spectral function. In this paper, we present novel wavelet-based graph convolution network, namely WaveGC, which integrates multi-resolution spec- tral bases and matrix-valued filter kernel. The- oretically, we establish that WaveGC can effec- tively capture and decouple short-range and long- range information, providing superior filtering flexibility, surpassing existing graph wavelet neu- ral networks. To instantiate WaveGC, we in- troduce novel technique for learning general graph wavelets by separately combining odd and even terms of Chebyshev polynomials. This ap- proach strictly satisfics wavelet admissibility cri- teria. Our numerical experiments showcase the consistent improvements in both short-range and long-range tasks. This underscores the effective- ness of the proposed model in handling differ- ent scenarios. Our code is available at https: / //github.. com/ -iun-on ine WaveGG.
Despite the existence of techniques in each aspect, the inte- gration of these two lines into a unified framework remains challenging, impeding the full potential of graph convolu- tion. In an effort to unravel this challenge, we introduce novel operation
Wavelet-based Graph Convolution (WaveGC), which seamlessly incorporates both spectral ba- sis and kernel considerations. In terms of spectral basis design, WaveGC is built upon graph wavelets, allowing it to capture information across the entire graph through a multi- resolution approach from highly adaptive construction of multiple graph wavelet bases. For filter parameterization, we opt for a matrix-valued spectral kernel with weight-sharing The matrix- -vauued kernel offers greater flexibility to filter wavelet signals, thanks to its larger parameter space.
1. Introduction
Spectral graph theory (SGT) (Chung, 1997), which enables analysis and learning on graph data, has firmly established itself as pivotal methodology in graph machine learn- ing. A significant milestone in SGT is the generalization
To comprehensively explore WaveGC, we theoretically anal- yse and assess its information-capturing capabilities. In contrast to the K-hop basic message-passing framework, WaveGG is demonstrated to exhibit both significantly larger and smaller receptive fields concurrently, achieved through the manipulation of scales. Previous graph wavelet the- ory (Hammond et al., 201 only verifies the localization in small scale limit. Instead, our proof is complete as it covers both extremely small and large scales from the perspective
National University of Singapore LLoyola Marymount Univer- sity University of Oxford AITHYRA, Austria. Correspondence to: Nian Liu <nianliu www.p..us.cduuss..
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
of information mixing (Di Giovanni et al., 2023). Moreover, our proof also implies that WaveGC is capable of simultane- ously capturing both short-range and long-range information for each node, which facilitate global node interaction.
graph Laplacian. With eigen-decomposition, L UAUT, where A diag(A1, ...... Ax) R X, E [0.2] and U = [ u,] E RN*N are the eigenvalues and cigenveetors of Ł, respectively. Given a signal f f R on G, the graph Fourier transform (Shuman et al., 2013) is de- fined as f U f E IR-,, and its inverse is = f E RRN,
To implement WaveGC, a critical step lies in constructing graph wavelet bases that satisfy two fundamental criteria: (1) meeting the wavelet admissibility criteria (Mallat, 1999) and (2) showing adaptability to different graphs. Exist- ing designs of graph wavelets face limitations, with some falling short in ensuring the criteria (Xu et al., 2019a; 2022), while others having fixed wavelet forms, lacking adapt- ability (Zheng et al., 2021; Cho et al., 2023). To address these limitations, we propose an innovative and general implementation of graph wavelets. Our solution involves approximating scaling function basis and multiple wavelet bases using odd and even terms of Chebyshev polynomials, respectively. This approach is inspired by our observation that, after a certain transformation, even terms of Cheby- shev polynomials strictly satisfy the admissibility criteria, while odd terms supplement direct current signals. Through the combination of these terms via learnable coefficients, we aim to theoretically approximate scaling function and multiple wavelets with arbitrary complexity and flexibility. Our contributions are:
Spectral graph wavelet transform (SGWT). Hammond et al. (2011) redefine the wavelet basis (Mallat, 1999) on ver- tices in the spectral graph domain. Specifically, the SGWT is composed of three components: (1) Unit wavelet basis, denoted as V/ such that V/ +(( = Ug(A)U", where g acts as band-pass filter g : R - IR+ meeting the following wavelet admissibility criteria (Mallat, 1999):
C C== x
la(A)]2 [I]
dA <<<00 00.
(1)
To meet this requirement, g(A = 0) 0 and limi g() 0 are two essential prerequisites. (2) Spa- tial scales, series of positive real values { where dis- tinct values of 8j with V, Ug(ssA)UU* can control different size of neighbors. (3) Scaling function busis, de- noted as & such that o- = Uh(A)UT, Here, the function of h : IR + Rt is to supplement direct current (DC) signals at X = 0, which is omitted by all wavelets g(s;A) since g(0) = O. Next, given a signal f E TR-,,, the formal SGWT (Hammond al., 2011) is:
We derive a new wavelet-based graph convolution (WaveGC), which integrates restiiresolltionn bases and matrix-valued kernel, enhancing spectral convolution on large spatial ranges.
Wy Wy(s;) v UU( JERN,
(2)
where (s;)) is the wavelet coefficients of f under scale 8j. Similarly, scaling function coefficients are given by
We theoretically prove that WaveGC can capture and distinguish the information from short and long ranges, surpassing conventional graph wavelet techniques.
S = 0f Uh(A)U E RV. Let G(A) = h())² + Σ, {5,(3))) then if G(A) = 1, AA E A, the constructed graph wavelets are known as tight frames, which guarantee energy conservation of the given signal between the original and the transformed domains (Shuman et al., 2015). More spectral graph wavelets are introduced in Appendix E.
We pioneer an implementation of learnable graph wavelets, employing odd terms and even terms of Chebyshev polynomials individually. This implementa- tion strictly satisfies the wavelet admissibility criteria. Our approach consistently outperforms baseline meth- ods on both short-range and long-range tasks, achiev- ing up to 15.7% improvement on VOC dataset.
3. From Graph Convolution to Graph Wavelets
2. Preliminaries
Spectral graph convolution is fundamental operation in the field of graph signal processing (Shuman et al., 2013). Specifically, given a signal matrix (or node features) X E R- xd on graph G, the spectral filtering of this signal is defined with a kernel & E IR NxN by the convolution theo- rem (Arfken, 1985):
An undirected graph can be presented as G = (V. where V is the set of N nodes and E C V V is the set of edges. The adjacency matrix of this graph is A E (0, 1JNN, where Aij E 10 denotes the rela- tion between nodes i and j in V. The degree matrix is D= = diag(d),....dd .dn) E IR NNN, where d, = Ejev Aij is the degree of node E V. The node feature matrix is E Nxo, where v, is a dg dimen- sional feature vector of node E V. Let -= = D AD- - be the symmetric normalized adjacency matrix, then L - -p- & is the symmetric normalized
K*g x F (F(N) F(X)) E ER
(3)
X = (21,
where is the matrix multiplication operator, F(.) and (-) are the spectral transform (e.g., graph Fourier trans- form (Bruna et al., 2013)) and corresponding inverse trans- form, respectively. To implement a spectral convolution,
IN- À D t (D- (D-A)D A)D-5
2

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
two critical choices must be considered in Eq. (3): 1) the selection of the transform F and 2) the parameterization of the kernel K.
tra of first six Chebyshev polynomials before and after the transform in Fig. 1 (b), where the set of odd and even terms after the transform are denoted as { and {T² J. respec- tively. From the figure, g(> = 0) = 0 for all {TT) and h(A = 0) = 1 for all (7P)- Consequentially. (T²) } and {TT) strictly meet the criteria and naturally serve as the ba- sis of unit wavelet and scaling function. Moreover, not only can we easily get each Chebyshev term via iteration, but the constructed wavelet owns arbitrarily complex waveform because of the combination of as many terms needed. Given ) and {T?), all we need to do is just to learn the coefficients to form the corresponding g(A) and h(A):
3.1. General spectral wavelet via Chebyshev decomposition
For the selection of the spectral transform FF and its in- verse FF1, it can be tailored to the specific nature of data. For set data, the Dirac Delta function (Oppenheim et al., 1997) is employed, while the fast Fourier Transform (FFT) proves efficient for both sequences (Li et al., 2021) and grids (Guibas et al., 2021). In the context of graphs, the Fourier transform (F + U emerges as one classical can- didate. However, some inherent flaws limit the capacity of Fourier bases. (1) Standard graph Fourier bases, represented by one fixed matrix UT, maintain a constant resolution and fixed frequency modes. (2) Fourier bases lack the adaptabil- ity to be further optimized according to different datasets and tasks. Therefore, multiple resolution and adaptability two prerequisites for the design of advanced base.
2(A) = Σ (A) ERNNN
(5)
M(A = Σ (TT RNNN
where P = K/2 (K is the total number of truncated Chebyshev terms), ā = (a) Oo.,,......4 ap) E R x and
b = (b), be. bp) E R represent two learnable co- efficient vectors as follows:
Notably, wavelet base is able to conform the above two demands, and hence offers enhanced filtering compared to Fourier base. For the resolution, the use of different scales 8y allows wavelet to analyze detailed components of a sig- nal at different granularities. More importantly, due to its strong spatial localization (Hammond et al., 201 1), each wavelet corresponds to signal diffused away from a central node (Xu et al., 2019a). Therefore, these scales also control varying receptive fields in spatial space, which enables the si- multaneous fusion of short- and long-range information. For the adaptability, graph wavelets offer the flexibility to adjust the shapes of wavelets and scaling function. These com- ponents can be collaboratively optimized for the alignment of basis characteristics with different datasets, potentially enhancing generalization performance.
â = Mean W, W + ba).
b = Mean W, 2 + bb). (6)
where (Wa, Wo) E RR and (ba, b,} E RII are learn- able parameters, and 2 is the eigenvalue embedding com- posed by the module in (Bo et al., 2023). Further details can be found in Appendix B. Also, we can learn the scales á = ($1, $2, ................................ ,8) in the same way:
8 = σ (Mean( W. E + ba)) B B
(7)
where a is sigmoid function, W, E RdxJ and b2 E RXXX are learnable parameters, and g = (3., 22, 3J) is a pre- defined vector to control the size of
Based on our construction, gA) is strict band-pass filter in [0, 2], while can scale its shape in g gs Specifically, < "stretches" the shape of gA)), and 8 >> 1 "squeezes" its shape (Please refer to Fig. 9). To maintain the same spectral interval [0, 2]. we truncate (s>) within the intersection of X E [0. 2] and X E [o. 2/s).
Next, we need to determine the form of the scaling func- tion basis +- = Ul(AUUT, the unit wavelet basis V = U UAAAU and the scales 8j. The forms of h and g are expected to be powerful enough and easily available. Con- currently, 9 should strictly satisfy the wavelet admissibility criteria, i.e., Eq. (1), and h should complementally provide DC signals. To achieve this target, we separately intro- duce odd terms and even terms from Chebyshev polynomi- als (Hammond et al., 201 1) into the approximation of h and g. Please recall that the Chebyshev polynomial Tę (y) of order k may be computed by the stable recurrence relation (y)) 2v)) 2x) with To 1 and Ti- = y. After the following transform, we surprisingly observe that these transformed terms match all above expectations:
3.2. Matrix-valued kernel via weight sharing
Next, we consider the parametrization of the convolutional kernel F(x). In the spectral domain, each Fourier mode typically corresponds to a global frequency pattern, either low- or high-frequency. Consequently, in Fourier-based approaches, it is common to apply a veluer kernel over the diagonalized graph Laplacian spectrum, denoted as diag(0x, (Bruna et al., 2013; Defferrard et al., 2016; Levie et al., 2018), which effectively scales these global frequency components. However, this strategy becomes un- suitable after applying a wavelet transform. Unlike Fourier
(x) + 1/2- (-Ti - 1) + 1).
(4)
To give a more intuitive illustration, we present the spec-
3

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
(a) WaveGC Block
(b) Spectral Transform
Scaling Function
MLP & Pooling
#$ + dHf
Eigernaluue Encoding
(q.. br)
Odd
Odd
-1
1
MLP Pooling
Chebyshey Polymomials
f +II-11--11
Figenvalue
Even
MMIP
1
(s))
MIP& Pooling
Even
0.5
Sm By
W.W . 4,H
Multiple Waveletss
Original
After transform
Figure 1. (a) Overview of our proposed WaveGC technique. (b) Illustration of Chebyshev polynomials before and after the given transform. from [-1, 1] to J0, 2]. In this representation, we distinguish odd and even terms, presenting only the first three terms for cach.
bases, wavelet coefficients encode localized, node-specific patterns that may capture short- or long-range interactions, but not global frequency modes. As a result, a different parametrization scheme, tailored to the localized nature of wavelet representations, is required.
3.3. WAVELET-BASED GRAPH CONVOLUTION
Until now, we have elaborated the proposed advancements on kernel and bases, and now discuss how to integrate these two aspects. Provided that we have J wavelet ",,,)=1 and one scaling function o constructed via the above Chebyshev decomposition, F R stack of transforms from each component:
Along another line of research, Fourier Neural Operator (FNO) (Li et al., 2021) models the convolution kernel as a fully Iearnable tensor M E RN xdxx, where is the num- ber of frequency modes, and is the feature dimension. This tensor-valued kernel offers two notable advantages. First, although FNO was originally introduced in the context of the Fourier transform, the kernel M is inherently indepen- dent of graph spectrum, and is thus amenable to generaliza- tion across other transforms (Tripura & Chakraborty, 2023). Second, in contrast to vector-valued kernels, the matrix- valued formulation provides a significantly larger number of learnable parameters, thereby increasing its expressivity and capacity adapt to complex patterns. Experimental results presented in Section 6.2 empirically demonstrate that the matrix-valued kernel outperforms its vector-valued counterpart in the context of filtering wrvelee-transformedd signals.
xd + [J+(() in Eq. (3) is the
F(H TH ((+H))
(v H
()) 11.. ,. H TT N(++1)
(8)
where T ( | IT is the overall trans- form and means concatenation, H is the node bedding matrix at layer 1. Next, we check if the in- verse F-1 exists. Considering T is not square ma- trix, F-1 should be its pseudo-inverse as (T (P"T)""'' where TT TΦ + E/= V V.,
Uīh(A)² + ((=))(B)))PUTT.. Ideally, if T is imposed as tight frames, then h(A)² + E/=1((s,)) {(s Van De Ville, 2013), and T T T UIUT I. In this case, F-1 (T) T T and Eq. (3) becomes:
I (Leonardi &
In this paper, we adopt the tensor M for the convolution kernel. The standard parameter count for M is N x d. This can lead to substantial number of parameters, es- pecially for large-scale graphs with high N, increasing the risk of overfitting. To mitigate this while preserving model expressivity, we introduce a parameter-sharing strat- egy across all frequency modes by employing a single MLP. This approach reduces the number of learnable parame- ters from N x (tensor) to d x d (matrix). Accord- ingly, the convolution operation in Eq. (3) simplifies to MI #g X F 'M F(X) F (MLP(F(X)) where o is the composition between two functions. An alternative method is presented in AFNO (Guibas et al., 2021), intro- ducing a similar technique that offers improved efficiency but with more intricate design.
H = T M TH
= 4$ H (0)
Σ 1=1
We, W, W
Ve, H
E Nxd
where we separate MI into S and (W) as scaling kernel and different wavelet kernels.
How to guarantee tight frames? From above derivations, tight frames is key for the simplification of inverse F-1 in Eq. (9). This can be guaranteed by l2 norm on the above constructed wavelets and scaling function. For each eigen- value X; E A, we have of = h((,)²² + E/=1 g(syA:)². T(AA,) h(Ae)/,, (((s):)) g(s)Aa/v.. Then, G(A) h(A) + E, A(, = II forms tight frames (Section 2). Thus, while the pseudo-invers must theoretically exist, we

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Table 1. Comparison between spectral graph convolution and WaveGC.
Spectral Graph Convolution
WaveGC
Kernel
diag (xx): Diagonal matrix
8 / W: Full matrix
Bases
U Fourier basis
4 / v Scaling/ Wavelet basis
Convolution
Udiag(Ox)UU X
@ ΦX W.W o V.X
can circumvent the necessity of explicitly calculating the pseudo-inverse.
comprising the primary model and a readout function (e.g.. mean, max) applied over the last layer. or and 3 represent two entries of the d-dimensional features a. and æb.
Resembling the multi-head attention (Vaswami al., 2017), we treat each wavelet transform as a "wavelet head", and concatenate them rather than sum them to get H(+1) E RR NgNxo
Next, we employ the concept of 'maximal mixing' on the WaveGC. For simplicity, we only take one wavelet basis V, for analysis. The capacity of v, on mixing information depends on two factors, i.e. K K-order Chebyshev term and scale s. For fair discussion on the effect of on mes- sage passing, we compare a HW)) and K-order message passing with the form of a (C)- A2 T E [0. 1]:
H =a ((0S $ ( W1 Vss I|
(10)
... ...I//a,, W V., H (1) w).
where an outermost MLP increases the flexibility. Fig. (a) presents the whole framework of our wavelet-based graph convolution, or WaveGC. For better understand- ing, we compare spectral graph convolution and WaveGC in Table. 1, where WaveGC contains only one wavelet for simplicity. Based on the differences shown in the table, WaveGC endows spectral graph convolution with the bene- ficial inductive bias of long-range dependency.
Theorem 4.2 (Short-range and long-range receptive fields). Given large even number K >> O and two random nodes and b. if the depths my and mA are necessary for o VV,, (HW and o(Ln k amount of mixing mixyo (b, a). then the lower bounds of my and m. iee Tm and Tum approximately satisfy the following relation when scale + 0:
T2 HW) to induce the same
4. Theoretical Properties of WaveGC
P Ling s3 K TLma +
2 mix ya (b,a)
1
K dadd
7
(a (a2g2Kymus
Traditionally, wavelet is notable for its diverse receptive fields because of varying scales (Mallat, 1999). For graph wavelet, Hammond et al. (2011) were the first to prove the localization when scale s -> 0, but did not discuss the long-range case when + oo. We further augment this dis- cussion and demonstrate the effectiveness of the proposed WaveGC in capturing both short- and long-range informa- tion. Intuitively, a model's s ability to integrate global infor- mation enables the reception and mixing of messages from distant nodes. Conversely, a model with a limited recep- tive field can only effectively mix local messages. Hence, assessing the degree of information 'mixing' becomes a key property. For this reason, focus on the concept of maximal mixing:
(12)
Or, if - oo, the relation becomes:
P
E
mixyo (b, a)
Tmmg " Iima K(K + 1 dd
(13)
where P < K and (TPAP)ma = max ((T At Yho m==
da and da are degrees of two nodes, and a C.2% (KK"(K+) (K+1)
K!
= / dmuse where dmaz/dmin is the maximum / mmnnmum degree the graph.
The proof is provided in Appendix A.3. In Eq. (12), since the second term on the right-hand side is large (s + 0). it required V, to propagate more layers to mix the nodes. Conversely, if s > oo (Eq, (13)), V. will achieve the same degree of node mixing as K K-hop message passing but with less propagation. Morcover, the greater the "mixing" mixyo (b, a) is required between nodes, the fewer number of layers T.my is needed compared to L.m,, To conclude, v presents the short- and long-range characteristics of WaveGC on message passing, while these characteristics do not derive from the order K of Chebyshev polynomials but from the scale s exclusively.
Definition 4.1. (Maximal mixing) (Di Giovanni et al., 2023). For twice differentiable graph-function yG of node features EG the maximal mixing induced by ya among the features Pa and ar, with nodes a, b
82 yG XX)
mixyo (a, max max Isa.
(II)
dx dxy
This definition is established in the context of graph-level task, and yG is the final output of an end-to-end framework,
5

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Table Qualified results on short-range tasks compared to baselines. Bold: Best, Underline: Runner-up, OOM: Out-of-memory. All
results are reproduced based on source codes.
Photo
Computer
CoraFull
oghn arxiv
Model
Accuracy f
Accuracy
Accuracy f
Accuracy
Accuracy t
GCN
92.92=0.12
92.70=0:20
89 99,65500.52
61,76+0.
71.74#0.29
GAT
93.61=0.14
93.8740.11
90.78460.
64.4740.18
71.8240.23
APPNP
94,49+0.07
94.32+0.11 14
90.18+0.1
65. 1640.28
71,90+0.25
Scattering
94.77a0.33
92.10g0.61
85.6880.71
57.6540.84
66.2340.19
Scattering GCN
95.18+0.30
93.07=0.42
88 38.8340.44
11.
71.1840.76
SGWT
94.81=0.23
92.45=0.62
85.19 59
1.
69,0840.30
GWNN
90.7520.59
94.45=0.45
90.75a0.59
19,0.99.79
11.13:0.47
UFGCome
95.33=0.27
33.98
88. 69..6.80..39
61.25a0..9
70.0440.22
LFGComr
95.46=0.33
94.34+0.34
89. 39.29:40.46
62.43:0..0
71.97+0.12
WaveShrinl-ChsbNot
94.90=0.30
93.5420.90
38.200+0.65
58. $8.9840.69
O0M
DEFT
95.0M20.32
94.35a0.44
91.63a0.52
68.01
72.01a0.20
WaveNet
94.91=0.29
94.09s0.63
92.0640.33
57.65&1.05
71.3740.14
SEA GWNN
95.11=0.37
94.35+0.500 50
89 19.88400.64
66. 744
72.64+0.21
WaveGC (ours)
95,8920.34
95.37=0.44
92,26210.18
69.1420.78
73.01:0.18
5. Why do we need decomposition?
following datasets: (1) Datasets for short-range tasks: CS, Photo, Computer and CoraFull 1 from the PyTorch Geometric (PyG) (Fey & Lenssen, 2019), and one large-size graph, i.e. ogbn-arxiv from Open Graph Benchmark (OGB) (Hu et al., 2020) (2) Datasets for long-range tasks: Pasca VOC-SP (VOC), PCQM-Contact. (PCQM), COCO-SP SP (COCO), Peptides funddes-func (Pf) and Peptides-struct (Fs) from LRGB (Dwivedi et al., 2022). Please refer to Appendix C.1 for implementation details and Appendix C.2 for details of datasets.
As shown in Fig. (b), odd and even terms of Chebyshev polynomials meet the requirements on constructing wavelet after decomposition and transform. Additionally, each term is apt to be obtained according to the iteration formula, while infinite number of terms guarantee the expressive- ness of the final composed wavelet. Next, we compare our decomposition solution with other related techniques:
Constructing wavelet via Chebyshev polynomials. Previ- ous wavelet-based GNNs leverage Chebyshev polynomials with two purposes. (I) Approximate wavelets of pre-defined forms. SGWT (Hammond et al., 2011). GWNN (Xu al., 2019a) and UFGConvS/R (Zheng et al., 2021) follow this line. They firstly fix the shape of wavelets as cubic spline, exponential or high-pass/low-pass filters, followed by the approximation via Chebyshev polynomials. In this pipeline, wavelet fails to learn further and suit the dataset and task at hand. (2) Compose new wavelet. DEFT (Bastos al., 2023) employs MLP or GNN network to freely learn the coefficients before each Chebyshev basis. These coefficients are optimized according to the training loss, but loose the constraint on wavelet admissibility criteria.
6.1. Benchmarking WaveGC
For short-range (S) datasets, we follow the settings from (Chen et al., 2022). For ogbn-arxiv, we use the public splits in OGB (Hu et al., 2020). For long- range datasets, we adhere to the experimental configura- tions outlined in (Dwivedi et al., 2022). The selected baselines belong to four categories, i.c., classical GNNs {GCN (Kipf & Welling, 2017), GAT (Velickovic al., 2017), APPNP (Gasteiger et al., 2018), 1), GINE (Xu et al., 2019b) and GatedGCN (Bresson & Laurent, 2017)), graph scattering network (Scattering (Gama et al., 2018) and Scat- tering GCN (Min et al., 2020)}, spectral graph wavelet network (SGWT (Hammond et al., 2011), 1), GWNN (Xu et al., 2019a), UFGConvS (Zheng et al., 2021), UFG- ConvR (Zheng al., 2021), WaveShrink (Wan et al., 2023), DEFT (Bastos et al., 2023) and WaveNet (Yang et al., 2024)} and wavelet lifting transform (SEA-GWNN (Deb et al., 2024) 1. The results of the comparison with SOTA models are shown in Table 2 and 3, where our WaveGC demonstrates the best results on all datasets. Remarkably, the improvement on VOC achieves up to 11.83%, implying the superior long-range information perception.
No decomposition. If we uniformly learn the coefficients for all Chebyshev terms without decomposition, WaveGC degrades to a variant similar to ChebNet (Defferrard al., 2016). However, mixture rather than decomposition blends the signals from different ranges, and the final spatial ranges cannot be precisely predicted and controlled.
We provide numerical comparison and spectral visualization in section 6.3 for WaveGC against these related studies.
6. Numerical Experiments
In the experiments conducted on the five short-range
In this section, we evaluate the performance of WaveGC on both saort-range and long-range benchmarks using the
For SGWT and Scattering, we concatenate the filtered signals from all bases and apply an MLP to get the final embeddings.
6

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Table Qualified results on long-range tasks compared to baselines. Bold: Best, Underline: Runner-up, OOM: Out-of-memory, All
results are reproduced based on source codes.
VOC
PCQM
COCO
Model
F1 score 1
MRR 1
F1 score
AP T
MAB J
GCN
12.68:0060
32.34+0.06
08.41#0. 10
59,30+0.23
34, 34,96#0.13
GINE
12.65:0.76
31.80+0.27
13.39:0.44
54,98&0.79
35.47=0.45
GatedGCN
28.7142.19
32. 18+0. 11
26.41+0.45
18.64+0.77
34.20=0.11 13
Scattering
16.5820.49
33.9020.27
16.44a0.79
56.80s0.38
26.77a0.11
Seattering GCN
30.45#0.36
33.73+0.45
30.2740060
62.87+0.64
26.43e0 20
SGWT
31,22:0.56
34. $4.0420.05
32.97+0.53
60.23+0.27
25.39
GWNN
35.60200.56
32.72+0.08
13.39220.44
65.47200488
27.34
UFGConvS
31.27.00.99
33.94m0.24
23.15a00.55
65. 65.83300.75
27.082 58
UFGComeR
31.08=0.33
34.08+0.20
26.07:40.48
65, 65.29:0.82
27.50+0.21
WaveShrink-ChebNe
18.80:0.85
32.5640.11
11.12+0.46
61.12:0.53
27.45=0.06
DEFT
35,9840,20
34.2520.06
30.1420.49
66.9520..3
25.062 13
WaveNel
28. 15.6040..15
33.19+0.20
23.0640..1 18
64.63+0.27
25.88&0.01
SEA BENNGWNN
31.97=0.55
29.89+0.26 26
24.3340.23
68. 28.75+0.20
25.64
WaveGC (ours)
41.63=20.19
34.50:0.02
35,9620022
69,7320.43
24.8320.11
datasets, the model is required to prioritize local information, while the five long-range datasets necessitate the handling of distant interactions. The results clearly demonstrate that the proposed WaveGC consistently outperforms traditional graph convolutions and graph wavelets in effectively aggre- gating both local and long-range information.
an approximate increase about 876K parameters.
Table 5. Compare sharing and non-sharing kernel weights.
Result (Parameters) Computer (Accuracy 1)
Ps (MAF 4)
Non-sharing
90.51 (535k)
26.22 (1,410k))
Sharing
92.26 (167k)
24.83 (534k)
6.2. Effectiveness of matrix-valued kernel
6.3. Effectiveness of learnable wavelet bases
The proposed matrix-valued kernel and weight-sharing strat- egy mark an advancement over conventional graph convolu- tion, particularly in the context of processing wavelet-based signals. In this section, we conduct a comprehensive anal- ysis of the effectiveness of these two architectural innova- tions.
In this section, we compare the learnt wavelet bases from WaveGG with other baselines, including five graph wavelets (i.e. SGWT (Hammond et al., 2011). UFGConvS/R (Zheng et al., 2021), DEFT (Bastos et al., 2023), GWNN (Xu et al., 2019a) and WaveNet (Yang et al., 2024)). We addition- ally evaluate ChebNet', variant of our WaveGC where the only change is to combine odd and even terms without decomposition. Therefore, the improvement of WaveGC over ChebNet reflects the effectiveness of decoupling op- eration. The numerical comparison on Computer and PascalVOC- SP has been shown in Table. and 3, which demonstrates obvious gains from WaveGC especially on long-range Pascal The ChebNet" gets 89.85 and 36.45 separately on Computer and PascalvOC-S5 SP, still inferior to WaveGC. 2
As shown in Table 4, the matrix-valued kernel consistently outperforms its vector-valued counterpart. This improve- ment suggests that increasing the expressiveness of the ker- nel-through a higher parameter capacity-enhance the model's ' ability on feature learning.
Table 4. Compare Matrix-valued and veluor kernels.
Kernel Vector-valued
Computer (Accuracy 1)
(MAE І)
89.96
25.30
Matrix-valued
92.26
24.83
To address the performance gap observed on the VOC dataset, we provide insights through the spectral visualiza- tion of various bases in Fig. 2. Upon examination of various wavelets, those from SGWT and UFGConvS/R meet ad- missibility criteria with multiple resolutions, but these lines are not adaptive. DEFT outputs multiple bases with unpre- dictable shapes, so it is hard to strictly restrain these outputs as wavelets. GWNN adopts one exponential wavelet base, omitting information from different ranges as well as not meeting criteria. WaveNet and ChebNet* blend local and distant information in spatial space, hampering the deci-
In addition, Table 5 examines the impact of weight sharing across spectral frequencies. Assigning distinct kernels to individual frequencies does not improve performance and, even results in degradation. This decline likely due to over- fitting caused by the large number of parameters introduced in the non-sharing setup. Specifically, non-sharing kernels require mapping from each eigenvalue embedding to unique transformation matrix, defined as f : IRd + 1ddxd which is implemented using a multi-layer perceptron (MLP) with a weight dimension of pdxdxd is the embedding dimension. For instance, when d=96 in P.s, this results in
We explore more differences between ChebNet (Defferrard et al., 2016) and our WaveGC in Appendix C.4.
7

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
ChebNet*
SGWT
UFGCon/S/R
DEFT
GWNN
WaveNet
0.5
0.5
0.5
0
-3
Scaling Unit wovelar
SIAI
ND0 60tAl
gis.a
givu)
n0t alspi
WaveGC
0.5
0.5
5, ---0 0.12
52 0.21
82 0.72
Frequency
Frequancy mode
Figure 2. The spectral and spatial visualization of different bases on Pa PascalvOC-SP.
sion on the best range. For our WaveGC, Fig. 2 intuitively demonstrates that the unit wavelet got by decoupling of Chebyshev polynomials strictly meets the admissibility criteria, as Eq. (1), while the corresponding base scaling function supplements the direct current signals at À = 0. After integration of learnable scales, the final wavelets also meet criteria and adapt to the demand on multiresolution. The plot of G(A) h(A)² + Σi=1 dashed line (located at 1) confirms the construction of tight frames via normalization technique. 2 also depicts the signal distribution over the topology centered on the target node (the red-filled circle). As the scale 8y increases, the receptive field the central node expands. Once again, this visualization intuitively confirms the capability WaveGC to aggregate both short- and long-range information simul- taneously but distinguishingly. More analyses are given in Appendix C.3.I.
continue to exclude scaling term (i.e., 'w/o h(A)), wavelet terms (i.e., 'w/o g(sA)") and tight frame constrains (i.e., 'w/o tight frame'). Then, both the scaling function basis h(A) and wavelet bases g(s)) are essential components of our WaveGC. In particular, neglecting l(A) results in a larger drop in performance on both short-range and long- range cases, emphasizing the crucial role of oo-frrquency information.
(e=1g(s,,)) ,(2 a black
6.5. Complexity analysis
The main complexity of WaveGC is the eigen- decomposition process, involving O(N²). This is practical for the small-to-medium graphs used in all long-range and some short-range benehmarks, where detailed spectral modeling is critical. To accelerate the decomposition on large-scale graph (e.g., ogbn-arxiv), we may adopt randomized SVD (Halko et al., 2009) with complexity ONN2 log K), where we only pick the top K eigenvectors.
6.4. Ablation study
Table 6. Results of the ablation study. Bold: Best.
Table 7. Training and EVD time on short- and long-range datasets.
Variants
Computer
Ps
Short-range
CS
Photo
Computer
CoraFull
oghn-arxiv
Accuracy f
MAE +
Training (min)
5.70
0.95
4.87
22.00
36.67
WaveGC
92.26
24.83
EVD (min)
2.82
0.32
1.44
3.49
21.69
w/o wavelet
89.65
34.20
Long-range
VOC
PCQM
COCO
Pf
Ps
w/o MPNN
90.89
25.04
Training (h)
4.02
12.33
45.40
1.88
1.32
w/o h(2)
90.57
25.12
w/o g(>A)
90.87
25.09
EVD (h)
0,05
0.21
0.58
0.02
0.02
Fig. 7 presents a direct comparison of the training time and EVD time across both short-range and long-range datasets. As shown, the time required for EVD is consistently lower than that of training across all datasets, with the difference being particularly significant in the long-range cases. Fur- thermore, the EVD operation is performed only once before training, and it is prerequisite for most graph wavelet base- lines. To further reduce complexity, we propose fully polynomial based approximation that removes the need for EVD, achieving total complexity of ONN). More details are given in Appendix D.
In this section, we conduct an ablation study of our WaveGC to assess the effectiveness of each component, and the cor- responding results are presented Table The evalu- ation is conducted on Peptides-ste and Computer (short-range).
(long-range)
Given the hybrid network (Fig. 3), we firstly remove the MPNN part (i.e., 'w/o MPNN') and wavelet part (i.c., 'w/o wavelet'), ) respectively. Both ablations degrade model per- formances, where 'w/o wavelet' decline more. To avoid in- terference from MPNN part, we base on "w/o MPNN', and
8

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Other experiments In Appendix C.5, analyze the complexity and report the running time for WaveGC and other spectral graph wavelets. Our model shows shorter running times than competitive spectral models while being significantly more accurate. Appendix C.6, we test the sensitivity of two important hyper-parameters.
tral networks and locally connected networks on graphs. arXiv preprint arXiv:13/2.6203: 2013.
Chen, J., Gao, K., Li, G., and He, K. Nagphormer: tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference Learning Representations, 2022.
7. Conclusion
Chien, E., Peng. J., Li, P., and Milenkovic, O. Adaptive uni- versal generalized pagerank graph neural network. arXiv preprint wwXiv:2006.07988 2020.
In this study, proposed novel graph convolution opera- tion based on wavelets (WaveGC), establishing its theoreti- cal capability to capture information at both short and long ranges through a
Cho, H., Jeong, M., Jeon, S., Ahn, S., and Kim, Multi- resolution spectral coherence for graph generation with score-based diffusion. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
approach.
Acknowledgements
Chung, F. R. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
XB is supported by NUS Grant 2-222-000-B97-118 and MOE AcRF TI Grant 25 2SIES24233 MB is partially sup- ported by the EPSRC Turing AI World-Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub No. EP/Y028872/1. The authors would like to express their gratitude to the reviewers for their feedback, which has improved the clarity and contribution of the paper.
Coifman, R. R. and Maggioni. M. Diffusion wavelets. Ap- plied and computational harmonic analysis, 21(1):53-94, 2006.
Deb, S., Rahman, S., and Rahman, S. Sea-gwnn: Simple and effective adaptive graph wavelet neural network. In Proceedings of the AAAI Conference on Artificial Intelli- gence, pp. 11740-11748, 2024.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must specifically highlighted here.
Defferarrd, M., Bresson, X., and Vandergheynst, P. Con- volutional neural networks on graphs with fast localized spectral filtering. Advances in neural information pro- cessing systems, 29, 2016.
References
Di Giovanni, F., Rusch, T. K., Bronstein, M. M., Deac, A., Lackenby, M., Mishra, S., and Veličković, P. How does over-squashing affect the power of gnns? arXiv preprint urXiv:2306.03589. 2023.
Arfken, G. Convolution theorem. In Mathematical Methods for Physicists). Academic Press, 1985.
Bastos, A., Nadgeri, A., Singh, K., Suzumura, T., and Singh, M. Learnable spectral wavelets on dynamic graphs to cap- ture global interactions. In Proceedings of the AAAI Con- ference Artificial Intelligence, pp. 6779-6787, 2023.
Dwivedi, V. P. and Bresson, of transformer networks graphs. arXiv preprint arXiv:2012.09699, 2020.
generalization
Dwivedi, P., Rampášck, L., Galkin, M., Parviz, A., Wolf, G., Luu, T., and Beaini, D. Long range graph bench- mark. Advances in Neural Information Processing Sys- lems, 35:22326-2253 22340, 2022.
Bo, D., Wang, X., Shi, C., and Shen, H. Beyond low- frequency information in graph convolutional networks. In Proceedings of the AAAI conference artificial intel- ligence, pp. 3950 3950-3957000000 2021.
Fey, M. and Lenssen, J. E. Fast graph representation learning with PyTorch Geometric, In ICLR Workshop on Repre- sentation Learning on Graphs and Manifolds, 2019.
Bo, D., Shi, C., Wang. L., and Liao, R. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, 2023.
Gama, F., Ribeiro, A., and Bruna, J. Diffusson scattering transforms on graphs. arXiv preprint 1rXiv:1806.0899 2018.
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint
2017.
Gama, F., Ribeiro, A., and Bruna, Stability of graph scattering transforms. Advances in Neural Information Processing Systems, 32, 2019.
Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. Spec-
9

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Gao, F., Wolf, G., and Hirn, M. Geometric seattering for graph data analysis. In International Conference on Ma- chine Learning, pp. 2122-2131. PMLR, 2019.
Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Koke, and Kutyniok, G. Graph scattering beyond wavelet shackles. Advances in Neural Information Processing Systems, 35:30219-30233 2022.
Gasteiger, J., Bojchevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: (8X0.0///100559990 2018.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Advances neural information processing systems, 25, 2012.
Guibas, J., Mardani, M., Li, Z., Tao, A., Anandkumar, A., and Catanzaro, Adaptive fourier neural operators: Efficient token mixers for transformers. arXiv preprint (rXiv:2111.33587 2021.
LeCun, Y., Bottou, I.., Bengio, Y., and Haffner, Gradient- based learning applied document recognition. Proceed- ings of the IEEE, 86(1 I1 1):2278-2324, 1998.
Halko, N., Martinsson, P.-G., and Tropp, J. A. Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions. arXiv preprint arXiv:0909, (9060000009990 909, 2009.
Leonardi, N. and Van De Ville, D. Tight wavelet frames on multislice graphs. IEEE Transactions on Signal Process- ing. 61(13):3357-3367, 2013.
Hammond, D. K., Vandergheynst, P., and Gribonval, R. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 3092):129-150, 2011.
Levie, R., Monti, F., Bresson, X., and Bronstein, M. M. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1)977-109 2018
He, M., Wei, Z., Xu, H., et al. Bernnet: Learning arbi- trary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, pp. 14239-14251, 2021.
Li, Q., Han, Z., and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelli- gence, 2018
Hinton, G., Deng, L., Yu, D., Dahl, G. E., Mohamed, A.-r,, Jaitly, N., Senior, A., Vanhoucke, V., Nguyen, P., Sainath, T. N., et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal processing magazine, (9())22-997 2012.
Li, Z., Kovachki, N. B., Azizzadeneshhli, K., Liu, B., Bhat- tacharya, K., Stuart, A. M., and Anandkumar, Fourier neural operator for parametric partial differential equa- tions. In 9th International Conference Learning Rep- resentations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 2020.
Lovász, L. Random walks on graphs. Combinatorics, Paul erdos is eighty. 2(1-46):4, 1993.
Mallat, S. A Wavelet Tour of Signal Processing, 2nd Edition. Academic Press, 1999.
Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., and Leskovec, J. Ogb-Ise: A large-scale challenge for machine learning graphs. arXiv preprint arXiv:2103.09430, 2021.
Mallat, S. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10)1331-13395 2012.
Min, Y.. Wenkel, F., and Wolf, G. Scattering gen: Over- coming oversmoothness in graph convolutional networks. Advances neural information processing systems, 33: 14498-14508. 2020.
Huang, K. Wang, Y. G., Li, M., et al. How universal polynomial bases enhance spectral graph neural networks: Heterophily, over-smoothing, and over-squashing. arXiv preprint arXiv:2405.1247: 2024.
Opolka, F., Zhi, Y.CC., Lio, P., and Dong, X. Adaptive gaussian processes on graphs via spectral graph wavelets. International Conference on Artificial Intelligence and Statistics, pp. 4818 4834. PMLR. 2022.
Joannidis, V. N., Chen, S., and Giannakis, G. Pruned graph scattering transforms. In International Conference on Learning Representations, 2020.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representationss ICLR 2017,
Oppenheim, A. V., Willsky, A. S., Nawab, S. H., and Ding, J.JJ. Signals and systems, volume 2. Prentice hall Upper Saddle River, NJ, 1997.
10

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Pan, C., Chen, S., and Ortega, A. Spatio-temporal graph scattering transform. arXiv preprint arX1v:20/22.3333, 2020.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In 7th International Con- ference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019b.
Rampásek, L.,, Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scal- able graph transformer. In Advances in Neural Infor- mation Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Xu, M.. Dai, W., Li, C.,, Zou, J., Xiong, H., and Frossard, P. Graph neural networks with lifting-basse based adaptive graph wavelets. IEEE Transactions on Signal and Information Processing over Nenworks, 5:63-77, 2022.
Yang, Z., Hu, Y., Ouyang, S., Liu, J., Wang. S., Ma, X..
Wang, W., Su, H., and Liu, Y. Wavenet: Tackling non- stationary graph signals via graph spectral wavelets. In Proceedings of the AAAI Conference on Artificial Intelli- gence, pp. 9287-9295, 2024.
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and Vandergheynst, P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83-99) 2013.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
Shuman, D. I., Wiesmeyr, C.. Holighaus, N., and Van- dergheynst, P. Spectrum-adapter tight graph wavelet and vertex-frequency frames. IEEE Transactions on Signal Processing, 63(16))4223-4233 2015.
Zhang, K., Pu, X., Li, Wu, J., Shu, H., and Kong, Hierarchical diffusion scattering graph neural network. In IJCAI, pp. 3737-3743, 2022.
Tripura, T. and Chakraborty, S. Wavelet neural operator for solving parametric partial differential equations in com- putational mechanics problems. Computer Methods in Applied Mechanics and Engineering, pp. 115783, 2023,
Zheng, X., Zhou, B., Gao, J., Wang. Y., Lió, P., Li, M., and Montúfar, G. How framelets enhance graph neu- ral networks. In Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139, pp. 12761-12771, 2021.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Zou, D. and Lerman, G. Graph convolutional neural net- works via scattering. Applied and Computational Har- monic Analysis, 49(3):1046-109) 2020.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y., al. Graph attention networks. stat, 1050 1045:00,4 2017.
Wan, L., Li, X., Han, H., Yan, X., Sun, L., Ning, Z., and Xia, F. Unifying and improving graph convolutional neural networks with wavelet denoising filters. In Proceedings of the ACM Web Conference 2023, pp. 177-187, 2023.
Wu, Q. Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., and Yan, Simplifying and empowering trans- formers for large-graph representations. arXiv preprint arXiv:2306.100 10759 2023.
Xing, Y., Wang. X., Li, Y., Huang, H., and Shi, C. Less is more: on the wer-globalizing problem in graph trans- formers. arXiv preprint 2rX5v:2405.01 102, 2024.
Xu, B., Shen, H., Cao, Q. Qiu, Y., and Cheng, X. Graph wavelet neural network. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019a.

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
A. Theoretical Proof
Firstly, we give two auxiliary but indispensable lemma and theorem. Let starts from the formula o oV,HHW). In this equation, we bound the first derivate of non-linear function as |o'| < Ca. and set |[ S w, where || is the operator norm. First, we give an upper bound for each entry in V.
Lemma A.1 (Upper bound for graph wavelet). Let L = UU(AAUT. Given large even mumber K > 0, then for ji,j E Vx x V, we have:
is a C.2
(Vo)s < (a(A)552²))
(14)
K!
The proof is given in Appendix A. In this lemma, we assume y is smooth enough at À = 0. For fair comparison with traditional K-hop message passing framework "Ejz T HW), we just test the flexibility with the similar form HW). In this case, we derive the depth my necessary for this wavelet basis U, to induce the amount of mixing mix (a. b) between two nodes a and b.
Theorem A.2 (The least depth for mixing). Given commute time T r(a,b) (Lovász, 1993) and number of edges |E| Vf
generates mixing mix yo (b, a), then the number of layers my satisfies
T(a.b)
2|
mixyo (b. a)
1 (7+ + 11- X
my 2
+
(15)
2K
K /dded (222 ymp
X
where da and do are degrees of two nodes, 7 / Amane and | X = maxocnsN- Anl < 1.
The proof is given in Appendix A.2. In the following subsections, we firstly prove these lemma and theorem, and finally give the complete proof of Theorem 4.2.
A.1. Proof of Lemma A.1 (Upper bound for graph wavelet)
Proof. We aim to investigate the properties of filters Va, = UUSSsAAUUT to capture both global and local information, corresponding to the cases 8y + and 8j + oo, respectively. In the former case, as s approaches zero, g(s,A) tends towards (0). For the latter case, the spectral information becomes densely distributed and concentrated near zero. Hence, the meaningful analysis of (A) primarily revolves around À O. Expanding g using Taylor's series around À 0, we get:
K Ck Ck g ((*)
AK+1
K
A
9(A)
Ck
(16)
(K 1)!
k!
k=
k=0
where we neglect the high-order remainder term. Next, we have
C*
(v), = (Ug(A)UT))
Σ
Ck
A
k=
Σ A!
K
Ch
(I-
T-Ai -A)*
K
C
(
A)p
h!
p=0
Σ
K
C
k
( (A))
K
h!
p}!p! (A)
hd
(k
4=
p=0
2j
k=
p=0
ij
(A)
(17a)
(k: p)lp!
p=0
(EN=) Cv E p=
(A)P
We introduce a new parameter μ
so the above relation becomes:
(Cx x
(A)2
K
(A)P
K
(A)r P
(W)a < (x+1)Cxx
Σ
(18)
(K-
p)lp!
(K-
p)!p!
p=
ij
p=0
ij
12

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
(4), where we C' ( + 1)Ck. Then, let us explore the expression eg - [X (Pppp! First, will address the denominator (K - ppppl. As p increases, this denominator experiences sharp decrease followed by rapid increase. The minimum value occurs at (K (K/)) when = K/2, assuming K is even. Second, let's 's analyze the numerator (A) which involves repeated multiplication of A. According to Theorem in (Li et al., 2018), this repeated multiplication causes (A)p to converge the eigenspaces spanned by the eigenvector D 1/2 1 of O, where
R Then, let us assume there exists value p" beyond which the change in (A)² becomes negligible. Given that K a large even number, we can infer that K/2 >> p². Thus, when (K - p)!p! sharply decreases, (A)p has already approached a stationary state. (A) Consequently, max eg (K/2) where the denominator reaches its minimum. Thus, have
(1, .,...,,..1........... 1)
.......,,
K
(A)
VV <
C p=0
C
-p)pp! (K
ij
K/)
C(K+1)
(K/2)((/22)
C.2k 2k (K + +1)
(A) K/2
(19a)
K!
i5
We have (K/2)([/22)
kt given that
K
K-2
4
K
K -
2
(K/))((K/2\ =
2
2
2
2
2
2
2
2
K
K - 2
4
K-1
3
2
2
2
2
2
2
2
2
(20)
K
K
1
K
K
3
4
2
KT
2 2 2
2. 2. 2.2
2K
terms
With C-2 C-2*(K(1) (K+1) KT and scale 8, Eq. (19a) can be finally written as
(Veks < (a(A)<125*)
(21)
A.2. Proof of Theorem A.2 (The least depth for mixing)
For this section, we mainly refer the proof from (Di Giovanni et al., 2023).
Preliminary. For simplicity, we follow (Di Giovanni et al., 2023) to denote some operations utilized in this section. As stated, we consider the message passing formula HW)... First, we denote h (1).a as the a-th entry of the embedding (1) for node a at the 1-th layer. Then, we rewrite the formula as:
h (0)a (k 1sasd.
(22)
where Ti (1-1).a HV, is the entry a of the pre-activated embedding of node layer 1. Given nodes and b, denote the following differentiaaion operations:
Th
22 dx Oxb
Vah
(1)
V Vash
(1)
(23)
dx
Next, we firstly derive upper bounds on V h (1)
V2 ab h (1)
and then on
'Simple proof. (Á)" = U(I - A = Ei (1- X, uT Provided only 1 As = and X E (-1,1) for other
eigenvalues, with p - co, only (1 - >a) = but 2,)a Thus, we have (Á)" - urur where un = D 1/2
13

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Lemma A.3. Given the message passing formula oV,, TVV.HV ,HW), let assume |o'| S Co and ||W]| S w, where ||. the operator norm. For nodes o and b after I layers of message passing, the following holds:
Vo 0 - (Co
(24)
where Bba = (aa(A)/333))
bo
Proof. If = 1 and we fix entries 1 a, S d, then have:
(V (v.hg
(1) Da. = (diag(o (h (W
(W)) (N bb Mas-
(25)
With Cauchy-Schwarz inequality, we bound the left hand side by
[a 11 < ||diag(o (mg MI|
(0)
W (1) Pool
S Co w Bia.
Next, we turn to a general case where 1 >> 1:
(Vah, (1) Jgz (diag( (a'a (hi (hl--1)
(W Σ Vos Voll 11) )aB
(27)
Then, we can use the induction step to bound the above equation:
f 11 < (4
ΣΣ
W bojo w jus
V adt
4 Vii-pal 20
30 51
3t
(28)
S () Da.
In Eq. (28), we implicitly use /V'l < (a(A))/23k) following proof:
B ba. Similar to proof given in Appendix A.I, we can give the
IK Ci LIK
V laa Ug(SA\UT
hb =
KPd
ba
ik C³
Cd
I -A)iK
ik
UK
A)
Kll
KR
ba
C
iK
C
IK
(IK)
8 JK
(1))
(A)P
JKK
(Á)P
KR
(IK p)lp!
p=0
ba
p=0
ba
(29)
uk C² (LK))
UK
(A)P
CH(IK)
(A)18/2
IK
(IK +1)
KP
(IK-
p)!p!
KIl
(IK/2)((K/2))
ba
ba
Jkk C (UK))
2
LIK Ct. (IK + 1) (A)
(IK + (IK)) (A)KK12
KM
KI
ba (a(A))/235))
ba
IK Cl 2
(K + 1)²
(A)iK/2)
K
where in the last line, we utilize the relation IK + 1 < (K +1'
Lemma A... Given the message passing formula a OO,,HHWW HWW,, let assume lo'), lo'| S co and [[]]| $ w, where || operator norm. For nodes a and after layers of message passing, the following holds:
is
1-1 >X (cow)2 21 k-1 w 1 ))0( (B'
12 111 S
(30)
where Bin = (a(A)Ki2gk)
ba
14

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Proof. Considering Vagh h E [ddx(dx)), we refer to (Di Giovanni et al., 2023) to use the following ordering for indexing the columns:
h 0
)o, ((-(()-))
(31)
0rg 0r²
Similar to the proof of Lemma A.3, we firstly focus on m
=:
(Vath (1)
Ja (add0-1))) = (diag(o' "(h
x (W(2) Das-
(32)
We bound the left-hand side as:
I 1o ( (c Byb Bral)-
(33)
Then, for m >
(Vas (1)
diag(o" (h: )W E Ue
Un., Vohl x (W Σ Uis VinVonh
(34)
R
Mis Vashh + diag(o (1(1-11),0) (w(m)) ( Σ
2
We denote 1|, 11 as (D)( and |/ h || as (11))- To bound R, we deduce as follows:
R
Bij V h (1 11) x (w Σ Big BB, BigllVah, (1 11 I co(w Σ
cowlw
(BDh (1-1) jin
S cc B" )ml ( (B(co B² Dea
(35a)
= (c) (w B 1bb B im),
where we utilize the conclusion from Theorem A.3 in (35a). For term Z, we have:
Z I cg w (t-)),
1-2
< C w
B is
2c-
2-1--22-11pp0 w( 111--)) ) (BB'-N)
(36a)
k=
1-2
(c 21 2- ( (B'-1-k) (B++1) (B (B----11))
(BB
Σ
(( (Bo (By(B'
(Cg (C
k=
where in (36a), recursively the Eq. (34). Finally, we finish the proof as:
(
R
Z1l
1-1
(37)
Σ
( (B'-*) (BB (B)))) (B' "a.
With Lemma A.3 and A.4, now we give the following theorem.
15

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Theorem A.5. Consider the message passing formula a HW) with my layers, the induced mixing mixyo (b, a) over the features of nodes o, and b satisfies:
mixyo (b,
(B diag (1 (1 Bmo-!)
(38)
ab"
1=0
where Bin = (a(()///38k) and 1 E R is the vector of ones.
ha
Proof. Here, we define the prediction function yo N x d on G as yi to gather all nodes embeddings get the final graph embedding, H m)) is the node embedding matrix after my layers and 0 is the learnable weight for graph-level task. If we set Readout sum, derive:
(ma) Readout (H())) 00, where Readout
Pyg (m))) (X)
mix (b,a) = max max 1sB
dx?
8 h ca
(ma
Oxa Oz?
NV
(mmw)) 011
EV
h (mp)
(39a)
me
(c
(w (Bmo-t)² T diag (1T Bb) Bmo-k)
(39b)
ab
where in (39a), assume the norm ||0|| < 1. In (39b), we use the results from Lemma A.4. This upper bound still holds if Readout is chosen as MEAN or MAX (Di Giovanni et al., 2023).
In theorem A.5, we can assume that 6, to be smaller or equal than one, which is satisfied by the majority of current active functions. Furthermore, considering the normalization (c.g., Le norm) on W, we assume w < 1. With these two assumptions, the conclusion of theorem A.5 is rewritten as:
mixya (b,a)
S
m.g.
Σ 1=0
(BBT--)) T diag (1 B') Bmo--))
(40)
With this new conclusion, we now turn to the proof of Theorem A.2:
Proof. Firstly, diag (1 (ITB')- ((as*) ((a))(((((())))))) S ((ssk) by using (((A))/2)(1), S (Di Giovanni et al., 2023). Then, we find
me
m 11
(Bmo-1)² diag (1TB') B
B2 1) (ast)))
Sy
ab
ab
(a((A) K/2 f / -1) (asskig)
ab
(41)
ma Ak(mo-1
ab
ma
= < yamo
Σ
AKI
16

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
The following proof depends on commute time 7(a, b) (Lovász, 1993), whose the definition is follows using the spectral representation of the graph Laplacian (Di Giovanni al., 2023):
N-1 1
(a)
Un (b)
<(a,)) b) 2
(42)
An
dda
v db
1=0
Then, we have:
map
Kme
Σ Aki
A'
ab
1=1
1=0
Kme
Xn) (a)un())
=
1=0 no0
ds
(1
Km
(Kmo 1)
+
Σ
Un un(a)un())
(43a)
F
An
2²0
v dddd
A) Kmm++
= -Kmp + 1)
Σ
(a)u,)
Un
un (a)
2|E]
An
n>0
m20
In Eq. (43a), use uo(a)=
du 2
Then, from the definition of commute time, we can get:
V
N
un (b) = -T(a,b) b)
1
de de
V dadh +
+
(u (1))
u
To
4/F)
Am
==1
(44)
-T(a,
1
do
do
ddd
E
do +
2X1
V
dg
+
dn
E
where in the last inequation, we utilize the fact that Besides, we use An \1 Vn > Next, we derive
En>o U (a) = 1 - ug (a) because {un} } is set of orthonormal basis.
(1
km
x Kmo+1
Σ A20
Un (b) 5
In (un(a)un (b)l
An
An
X Kmo+1
Σ (1) + +,²(())
(45)
2
1 Km]Km
de + do
2
2A1
2 2
where [1 X maxoens Amd < 1. Insert derivations (44) and (45) into (43), then gather all above derivations:
(Kmv + 1) da T(a,b)
mixyo (b, S ((sss Ky3mo
Vd
F
4/Fl
1
di
de
vdada
1 - x kmo++
2 du + db
2
V
dp
+
V
E
+
2x1
2) Ei
(46)
Kmm
T(a, b) E
Hask jamo
du
dp
(as* yyam
S <aaa K jamo
v dodb
V dl
+ V do
+
11 X Kmo+1
211
In last inequation, we discard
ddd 2
1 X (1+
|| Kmo--
(V + v ( ))
0 because d < 1. Then,
2
Plaskyamm Vdald
mixyo (b,a)
Kmp
2 F.
T(a,b) b)
4 F
+
2\1 vdaao
1
(Via+va
to
+1
d
db
+ 2 X-IKmmtt1
(47)
17

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
From (47), we can finally give the lower bound of my as:
E
T(a, b)
mix (b,a)
(V&
do (Vd, ds +V du
db
+ 2 X kkmot1)
N
+
K
E
Mas jamo (aams))mmn vdodo
2 2dI
T(a, b)
mixyo (b)
1
(27 + 2/1 ^ Am|Kmotl) +1
K
E
ddgdb Mask )2mo
2
(48)
T(a,
b)
mixyo (b,a)
1
(> + 1 1- 11=
K
dadh
(a2g2k)mm yime
A1
T(a,b) b)
F|
mix (1,
1
(7 + | XY|Kmott))
+
2K
K Kv d db
d1
A.3. Proof of Theorem 4.2 (Short-range and long-range receptive fields)
Proof. From theorem A.2, we denote Lin
r(a.b) 2K
2| mixyc (b,0) + Kva,d, b(a222k) yom X (7 + X x1]Kmett)]] For
K-order message passing TJ Tj E {(TAA")aa .... (TKAK)aa )ar). According to theorem A.5, we can get the similar conclusion, replacing B with C (K + 1)TPAP, Then, we have the following proof:
[0, 1], we assume that (TPA Dh is the maximum among
Proof.
Again, diag (ITC'). ((K (A S 7((K 1)Tp). Then, we have
mA
mA-1 -1
((mma-l)) diag (1
Σ
((K + 1)Tp}
1=0
1=0
ma-1
Σ
((K A)pAAP)2mma-) ((K + 1)Tp)
<9
1=0
ab
ma
< <>((K + 1)Tp) ams
A 22P(ma-1)
(49)
=>((K + JMA
Σ
A 2P
1=1
2ma
< <7(V (K 1)TP) mma
Σ
API
ab
Following the rest proof of Lmn- replace {as* mm, K} with {v(K 1)TP, 2m PJ. and get the expression of Lmn
IAnA
b(a
2|E1
mixyo (b, a)
1
(7 + 11 xmpepmat)
(50)
2P
2) + T)p An
Therefore, we have
P
F| mix ycr (b,a)
Liw
Lia +
(51)
K
K ddd
7
((K + T)"
where ignore |1 Km and |1 X 2m +1 Since - X+1 < 1 shown in theorem A.2, therefore |1
x Kmo+1 | X+ 2Pma+1 will be very small, especially when me and m, are large. From Eq. (51), when 8 co, the relation becomes:
P K(K 1)2ma T 2m 2m dddeo
E
mix (b. a)
Liw 2 K Lmm-
(52)
7
18

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Or, when 8 + O, the relation becomes:
P K
2|
mixya (b,a) 7
Lim
Lmn + K dd,db
(53)
(a2gak)m
B. Details of Encoding Eigenvalues
In this paper, we adopt Eigenvalue Encoding (EE) Module (Bo al., 2023) to encode eigenvalues. EE functions set-to-set spectral filter, enabling interactions between eigenvalues. EE, both magnitudes and relative differences of all eigenvalues are leveraged. Specifically, the authors use eigenvalue encoding function to transform each À from scalar R to vector Rd:
pl>, 2i) = sin (+2/100002//1) p(>, 2i + = cos (eA/1000024/0)
(54)
where is the dimension of the representations and hyper parameter. By encoding in this way, relative frequency shifts between eigenvalues are captured. Then, the raw representations of eigenvalues are the concatenation between eigenvalues and corresponding representation vectors:
AN x = (NNI(A))...,,,-IIlllll
E R.
(55)
To capture the dependencies between eigenvalues, a standard Transformer is used followed by skip-connection and feed forward network (FFN):
2 Transformer(L(((2)) + E R- Z FFN((N + 2A E RR
(56)
where LN is the layer normalization. Then, Z is the embedding matrix for eigenvalues, which is injected into the learning of combination coefficients à and and scales 8.
C. Experimental Details
C.1. Implementation Details
Inspired by (Rampásek al., 2022), adopt the hybrid network architecture shown in Fig. 3, where the "WaveGC" block is the pro- cess shown in Fig. 1 (a). This architecture explicitly involves a parallel massage passing neural network (MPNN) (e.g., GCN (Kipf & Welling, 2017), GatedGCN (Bresson & Laurent, 2017)) to augment the low- frequency modeling. Then, these two branches separately go through skip-connection normalization, and then sum together followed by a two-layers MLP, eventually skip-connection and normalization.
Predict head
x L
Add & Norm
Feed Forward Network
Add Norm
Add Norm
We explore the number of truncated terms p from to 10 and adjust the number of scales J from 1 to 5. Additionally, for the pre-defined vector & controlling the amplitudes of scales, we test each element in 8 from 0.1 to 10. The usage of the tight frames constraint is also parameter subject to tuning, contingent on the given dataset. Typically, models iterate through several layers to produce single result, thus the parameters of WaveGC may or may not be shared between different layers. For sanrt-range datasets, only retain the first 30% of eigenvalues and their corresponding eigenvectors for efficient eigendecomppssiiion and set threshold N and filter out entries in & and V,, whose absolute value is lower than K.
MPNN
WaveGC
Positional
Raw feature
U.A
Figure 3, Combing MPNN with WaveGC.
For fair comparisons, we randomly run times on long-range datasets (Dwivedi et al., 2022), and 10 times on short-range datasets (Chen et al., 2022), and report the average results with their standard deviation for all methods. For the sake of reproducibility, we also report the related parameters Appendix C.7.
19

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
Table The statisties of the short-range datasets.
Dataset
# Graphs
Nodes
# Edges
Features
# Classes
CS
18,333
163,788
6,805
15
Photo
1
7,650
238,163
745
8
Computer
1
13,752
491,722
767
10
CoraFull
1
19,793
126,842
8,710
70
ogbn-arxiv 1
169,343
1,116,243
128
40
C.2. Datasets Description
For short-range datasets, we choose five commonly used CS, Photo, Computer, CoraFull (Fey & Lenssen, 2019) and ogbn-arxiv (Hu et al., 2020). CS is network based on co-authorship. with nodes representing authors and edges symbolizing collaboration between them. In the Photo and Computer networks, nodes stand for items, and edges suggest that the connected items are often purchased together, forming co-purchase networks. CoraFull is network focused on citations, where nodes are papers and edges indicate citation connections between them. ogbn-arxi v is a citation network among all Computer Science (CS) Arxiv papers, where each node corresponds to an Arxiv paper, and the edges indicate the citations between papers. The details of these five datasets are summarized Table 8.
Table The statistics of the long rangrange datasets.
Dataset
# Graphs
Avg. # nodes
Avg. # edges
Prediction level
Task
Metric
PascalVOC-SP
11,355
479.4
2,710.5
inductive node inductive link
21 2clclsss classif.
Fl score
PCQM-Contact
529,434
30.1
61.0
link ranking 81-class classif.
MRR
COCO-SP
123,286
476.9
2,693.7
inductive node
FI score
Peptides-fumd
15,535
150.9
307.3
graph graph
10-task classif.
Avg. Precision
Peptides-struct 15,535
150.9
307.3
1 11-task regression
Mean Abs. Error
For long-range tasks, we choose five long-range datasets (Dwivedi et al., 2022), including PascalVOC- (VOC), PCgM-Contact (PCQM), COCO-SP (COCO), Pepti pootides-foet func. (PF) and Pept ssptides-sttuce five datasets are usually used test the performance on long-range modeling. VOC and COCO datasets are created through SLIC superpixelization of the Pascal VOC and MS COCO image collections. They are both utilized for node classification, where each super-pixel node is categorized into specific object class. PCQM is developed from PCQM4Mv2 (Hu et al., 2021) and its related 3D molecular structures, focusing on binary link prediction. This involves identifying node pairs that are in 3D contact but distant in the 2D graph. Both Pf and Ps datasets consist of atomic graphs of peptides sourced from SATPdb. In the Pepti seeeeiies-fee func dataset, the task involves multi-label graph classification into 10 distinct peptide functional classes. Conversely, the Pept i des- -t suct dataset is centered on graph regression to predict 11 different 3D structural properties of peptides. The details of these five datasets summarized in Table 9.
(Ps). These
C.3. More analyses for section 6.3
In this section, we firstly give a further visualization on short-range dataset and then analyze the impact of the learned scales.
C.3.1. VISUALIZATION ON CORAFULL
To give one more example, we provide additional visualization results the CoraFull dataset. These results presented in Fig. 4, where the learned scaling functions h(A) and g(A) meet the specified requirements. The four subfigures in Fig. 4(c) illustrate that as the scale sy increases, the receptive field of the center node expands. This highlights WaveGC's capability to capture both short- and long-range information by adjusting different values of 8j. However, one of our strategies for CoraFull involves considering only 30% of eigenvalues as input. Consequently, the full spectrum is truncated, leaving only the remaining 30% parts, as depicted in Fig. 5. We give a deeper insight the behavior of this truncation from both spectral and spatial perspectives:
Spectral perspective. As shown in Fig. 5, the wavelet function g(s retains non-trivins amplitudes within the first 30% domain. While g(A) 0, the retained spectral range is sufficiently broad to allow the wavelets operate
20

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
[8]
Rovdd
Aag Nooadd
21-143821
22-082915
sI-143023
33146467
Scdl
53-1 46467
Scsting hurctinn
Figure 4. Illustration of the spectral and spatial signals of the learned function basis and multiple wavelet bases with full spee- trum.
Figure 5. Illustration of the spectral and spatial signals of the learned function basis and multiple wavelet bases with partial spectrum.
effectively. Therefore, even in the truncated setting, both the scaling function ((A) and wavelet function g(A) contribute meaningfully to low-frequency modeling.
Spatial perspective. In Fig. 5(b), we observe that truncating the spectrum mimics the effect of using a larger wavelet scale & > 1, which reduces the effective spectral range and increases the spatial receptive field. This effect visually confirmed in Fig. 4(c) and 5(c), where the receptive fields become noticeably larger after truncation. Thus, even on short-range datasets, the wavelet branch captures valuable higher-order information that complements local aggregation from MPNN. This complementary role is further validated by the performance drop observed in Table when wavelets removed.
Overall, spectral truncation does not impair wavelet behavior; instead, supports effective low-frequency modeling while also enhancing spatial coverage.
C.3.2. IMPACT OF THE LEARNED SCALES
Table 10. Comparison of average and max receptive fields of Ps and VOC.
Peptides-struct
Pascal-VOC
Avg. Receptive Field
3.02
0.74
98
0+0.2
Max Receptive Field
9
3
Peptides-stract
Pascal-VOG
Avg. Shortest Path
20.89
10.74
Figure Visualizations receptive fields Peptides-struct (Ps) and Pascal-Vol VOC (VOC) at their largest scale
We empirically analyze the learned scale values and their impact on receptive fields Fig. 6. Specifically, we illustrate the largest learned scales for the Ps and VOC datasets, along with their corresponding receptive field visualizations. The receptive field is heuristically defined as follows:
Definition (Receptive field.) Given a wavelet (sA), node j lies in the receptive field node (s))((i > 0.1 (sXI)
Under this criterion, we observe that Ps exhibits larger receptive fields, corresponding to larger learned scale of 9.48. We further report the average and maximum receptive field sizes across all nodes in Table 10. The larger receptive fields in Ps align with its inherently longer average shortest-path distances, thus validating the model's 's ability to adaptively adjust to long-range dependencies. To examine the extreme case of large-scale values, we increase the predefined scale vector in Eq. (7) for Peptides-fum (Pf) to (10, 100, 1000). This vector determines the upper bound of the learnable scale range. The
21

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
130
s= 9.17
66.59
988.24
Figure 7. Visualizations of receptive fields for Peptides-fune (Pf) al extreme scales.
resulting learned scales and receptive fields are depicted in Figure 3. When s 9.17, the red node primarily aggregates local information; in contrast, at s 988.24, the same node gathers information from a much broader range. This confirms our theoretical assertion that WaveGC exhibits long-range behavior as s approaches infinity.
C.4. More comparisons between WaveGC and ChebNet
Table II. More ablations for differences between WaveGC and ChebNet.
Free ã
Free 3
Fix s=1
Free ø
Original
Computer
91.28+0.15 25.08+0.01
91.19+0.09
91.73+0002
91.51+0.02 25.15
92.26+0.18
Ps
25.09
25.28+0.00
24.83+0.11
Obviously, both WaveGC and ChebNet attempt weighted combination of Chebyshev polynomials in different ways. On one hand, ChebNet learns term coefficients independently, while WaveGC map eigenvectors into coefficients and B3. On the other hand, WaveGC further involve multiple and learnable scales Finally, we test importance of these differences on the Computer and Ps. The results summarized in Table 11, showeasing different variants such free learning coefficients (i.e.. ã. B), adopting single scale s=1, and free learning & to avoid joint parameterization. Each of these modifications resulted in degraded performance compared to the original model, demonstrating the improvements our new model offers over ChebNet.
C.5. Complexity and Running time
Table 12. Comparison rumning time per epoch (s).
SGWT
GWNN
WaveShrink
WaveNet
DEFT
UFGConvS
UFGConvR
WaveGC
Computer
3,6
0.8
2.7
2.0
1.1
3.1
3.2
1.5
Ps
21.0
30.5
52.0
27.3
23.6
47.3
43.5
23.9
The main contribution of WaveGC to address long-range interactions in graph convolution, so it inevitably establishes spatial connections between distant nodes. This results the same O(N2) complexity as Transformer (Vaswani et al., 2017). This is the same for all spectral graph wavelets, including SGWT, GWNN, WaveShrink, WaveNet and UFGConvS/R. possible solution is to decrease the number of considered frequency modes from N to v. In this way, the complexity is reduced to O(v N). We report the running time consumption of WaveGC and other spectral graph wavelets (that is, SGWT, GWNN, WaveShrink, WaveNet, DEFT, UFGConvS and UFGConvR). The time consumptions for Computer and Ps are presented in Table 12. According to the table, the running time of WaveGC is in the first level among spectral graph wavelets.
C.6. Hyper-Parameee Sensitivity Analysis
In WaveGC, two key hyper-parameters, namely p and J, play important roles. The parameter p governs the number of truncated terms for both TV and T while J determines the number scales in Eq. (7). In this section, we explore the sensitivity of and J on the Peptides-struct (Ps) and Computer datasets. The results are visually presented in Fig.8, where the color depth of each point reflects the corresponding performance (the lighter the color, the better the performance), and
22

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
the best points identified with red Observing the results, we that the optimal value for p is 2 for Ps and 7 for Computer. This discrepancy be attributed the substantial difference in the graph sizes between the two datasets, with Computer exhibiting significantly larger graph size (refer to Appendix C.2). Consequenty,, more intricate filter design is necessary for the larger dataset. Concerning J, the optimal value is determined to be 3 for both Ps and Computer. A too small J leads to inadequate coverage of ranges, while an excessively large J results in redundant scales with overlapping ranges.
25.35
92.55
25.26
92.50
8026
Test Accuracy
Test Accuracy
Test MAE
03.83
01.02
Test MAE
25.15
92.03
91.89
2307
50.03
2429
2487
24.94
2007
2433
24.80
89.90
24.80
90.60
The value of
The value
The value of)
The value off
(a) Ps: p-analysis
(b) Computer: p-analysis
(c) Ps: J-analysis
(d) Computer: J-analysis
Figure 8. Analysis of the sensitivities of and J.
C.7. Hlype--aaaaeete Settings
We implement our WaveGC in PyTorch, and list some important parameter values in our model in Table 13. Please note that for the five long-range datasets, we follow the parameter budget ~500k (Dwivedi et al., 2022).
Table 13. The values parameters used in WaveGG (T: True; F: False).
Dataset
parameters
J
8
Tight frames
N
CS
495k
3
{0.5, 0.5, 0.5]
T
0.1
Photo
136k
3
{1.0, 1.0, 1.0]
0.1
Computer
167k
3
{10.0, 10.0, 10.0)
0.1
CoraFull
621k
3
2.00,
0.1
ogbn-arxiv
2,354k
3
5..0,
F
PascalVOC-SP
506k
3
(0.5, 1.0, 10.0)
PCQM-Contact
508k
3
100,
T
COCO-SP
546k
3
{0.5, 10.0)
T
Peptides-func
496k
3
{10.0, 10.0, 10.0)
T
Peptides-struct
534k
3
{10.0, 10.0)
C.8. Operating Environment
The environment where our code runs is shown as follows:
Operating system: Linux version 5. 11..-43-geeerrie
CPU information: Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz
GPU information: NVIDIA RTX A5000
D. Approximation Strategy for O(N) Complexity
To further reduce complexity, we propose a fully polynomial-based approximation that removes the need for eigendecompo- approximation the wavelet transform using Chebyshev polynomials:
sition, achieving total complexity of O(N), on par with graph Fourier-basis basi-bbadd methods. This achieved via polynomial
23

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
2
2
2/x
(1) Base g(A)
(2) 1, "stretched" (3) 1, "squeezed"
true (s
complete g(
"window" w(2)
Figure The scale can "stretch" or "squeeze" the shape of g(A) as g(sA).
Figure I0. The illustration of applying "window" over ((s)).
Scaling function (()). Since h(A) (.T, where Tς are odd-degree Chebyshev polynomials, we can compute
Φ UU-UUA f EbDTTCD (L)(())
(57)
This is equivalent polynomial operation over the graph Laplacian L, which has O(N) complexity.
Wavelet Function (A). Similarly, g(A) = Ea,T, where T even-degree Chebyshev polynomials, gives
f = UU(A)U f == (L),,
(58)
which also polynomial in L with O(N) cost.
Incorporating scale The domain À [0, for ((A) transforms to À E 2/s] g(>)). This raises two scenarios:
If < 1: The full spectrum [0.2] is covered, and g(A) remains valid a polynomial (Fig. 9 (2)).
If s > 1: Only the interval [0,2/s] valid. The rest of the spectrum [2/s,2] should be suppressed (Fig. 9 (3)). To handle this, we apply window function w(A), where:
w(A) -(o
A [0,
Xe [2/s, 2]
The true scaled wavelet becomes g(s)) = g(>)) (A)). Both g(sA) and w(A) can be approximated using Chebyshev polynomials, so the entire operation remains within (NV) complexity.
Using this approach, plus without eigenvalue encoding (EE) and tight frame constraint, we no longer require EVD with the maximum simplification. The resulting model maintains the theoretical structure of WaveGC while gaining substantial computational benefits.
Table 15. Qualified results three short-range datasets.
Table 14. Running time (s) per epoch.
Accuracy 1
CS
Photo
Computer
CS
Photo
Computer
GPRGNN
95.13
94,49
90.82
GPRGNN
1.1
0.2
0.4
BernNet
95.42
94.67
90.98
BernNet
1.5
0.5
1.3
UniFilter
95.68
94.34
90.07
UniFilter
5.7
0.8
1.5
WivpliCsimllifted
95.63
94.90
91.22
WaveGC simplified
1.4
0.6
1.8
WaveGC 95.89
95.37
92.26
To validate this simplified version, we compared its runtime and accuracy with GPRGNN (Chien et al., 2020), BernNet (He et al., 2021), and UniFilter (Huang et al., 2024) on three short-range datasets. As shown Table 14, the WaveGC simpliiied achieves comparable training time to Fourier-basee methods. According to Table 2, it incurs only a small drop in performance compared with WaveGC, confirming that polynomial approximation remains effective even without EVD.
24

---

A General Graph Spectral Wavelet Convolution via Chebyshey Order Decomposition
E. Related Work
Graph Wavelet Transform. Graph wavelet transform is a generalization of classical wavelet transform (Mallat, 1999) into graph domain. SGWT (Hammond et al., 2011) defines the computing paradigm on weighted graph via spectral graph theory. Specifically, it defines scaling operation in time field as the scaling on cigenvalues. The authors also prove the localization properties of SGWT in the spatial domain in the limit of fine scales. To accelerate the computation additionally present fast Chebyshev polynomial approximation algorithm. GWNN (Xu et al., 2019a) chooses heat kernel as the filter to construct the bases. The graph wavelet bases learnt from these methods are not guaranteed as band-pass filters in À E [0, 2] and thus violate admissibility condition (Mallat, 1999). UFGCONV (Zheng et al., 2021) defines a framelet-bassee graph convolution with Haar-type filters. WaveNet (Yang et al., 2024) relies on Haar wavelets as bases, and uses the highest-order scaling function to approximate all the other wavelets and scaling functions. WGGP (Opolka et al., 2022) integrates Gaussian processes with Mexican Hat represent varying levels of smoothness on the graph. The above four methods fix the form of the constructed wavelets, extremely limiting the adaptivity different datasets. In this paper, our WaveGC constructs band-pass filter and low-pass filter purely depending on the even terms and odd terms of Chebyshev polynomials. In this case, the admissibility condition is strictly guaranteed, and the constructed graph wavelets can be arbitrarily complex and flexible with the number of truncated terms increasing. In addition, SEA-GWNN (Deb et al., 2024) focuses on the second generation of wavelets, or lifting schemes, which is a different topic from ours.
transform, they
Graph Scattering Transform. The Scattering Transform constructs hierarchical, tree-like structure by combining a cascading filter bank (or wavelets), point-wise non-linearity, and low-pass operator. As introduced by Mallat (Mailat, 2012), this approach guarantees translation invariance and stability to deformations. On one hand, researchers have explored the application of this technique to graph data. Early efforts, such as those by (Zou & Lerman, 2020), (Gama et al., 2019), and GS-SVM (Gao et al., 2019), extended the scattering transform into the graph spectral domain. ST-GST (Pan et al., 2020) defined filtering and wavelets for spatio-temporal graphs, deriving the corresponding scattering process. Meanwhile,(Game et al., 2018) employed lazy diffusion(Coifmanl & Maggioni, 2006) as wavelets to construct graph diffusion scattering, demonstrating its stability against deformations based on diffusion distance. HDS-GNN (Zhang et al., 2022) enhanced GNNs by integrating scattering features from a diffusion scattering network layer by layer. while GGSN (Koke & Kutyniok, 2022) introduced further flexibility to each operation. On the other hand, the computational efficiency of this transform, which involves total of Σ J' filtering operations, poses significant challenge. To address this, PGST (Ioannidis et al., 2020) proposed pruning strategy, retaining only the higher-energy child signals for each parent node. Scattering GCN (Min et al., 2020) further optimized the process by selectively using more beneficial wavelets, simplifying the scattering computation.
Spectral graph convolution. Traditional studies on spectral graph convolution mainly concentrate on the design of filter with fixed Fourier bases. One way to design low-pass filters that smooth signals within neighboring regions. GCN (Kipf & Welling, 2017) keeps the first two ChebNet (Defferrard al., 2016) terms with extra tricks, and averages signals between neighbors. PPNP (Gasteiger et al., 2018) smooths signals in broader range following PageRank based diffusion. Another way is to design adaptive filters so work in both homophily and heterophily scenarios. ChebNet (Defferrard et al., 2016) approximates universe filter functions with Icarnable coefficients before each Chebyshev term. FAGCN (Bo et al., 2021) proposes self-gating mechanism to adaptively learn more information beyond low-frequency information in GNNs.
Graph Transformer. Graph Transformer (GT) has attracted considerable attentions on long-range interaction. GT (Dwivedi & Bresson, 2020) proposes to employ Laplacian eigenvectors as PE with randomly flipping their signs. Graphormer (Ying et al., 2021) takes the distance of the shortest path between two nodes as spatial encoding, which is involved in attention calculation as a bias. GraphGPS (Rampásek et al., 2022) provides different choices for PE, consisting of LapPE, RWSE, SignNet and SquivStablellapPh SGFormer (Wu et al., 2023) is empowered by simple attention model that can efficiently propagate information among arbitrary nodes. Recently, Xing et al. (2024) are the first to reveal the over-globalizing problem in graph transformer, and propose CoBFormer to improve the GT capacity on local modeling with a theoretical guarantee.
25


Reviews:
[{"review_id": "NGzZ61uyHW", "reviewer": "Reviewer_JRdk", "summary": "This paper introduces WaveGC, a wavelet-based graph convolution network that integrates multi-resolution spectral bases with a matrix-valued filter kernel. It proposes graph wavelets by decomposing Chebyshev polynomials into odd and even terms and combining them with learnable coefficients, ensuring strict admissibility criteria and enhanced flexibility. The authors demonstrate that WaveGC effectively captures both extremely small and large scales, extending beyond previous graph wavelet theory. Experimental results show state-of-the-art performance in both short-range and long-range tasks.\n\n## Update after rebuttal\nI think this is a nice work but not quite up to my expectation. I will keep my original rating for now.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> Q1: Analysis of learned scales and experimental impacts.\n\n1) Learned Scales and Receptive Fields\n\nFigure 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λ)|).\n\nUnder 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.\n\n2) Behavior at Extremely Large Scales (s → ∞)\n\nWe 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 𝑠→∞.\n\n> Q2: Verify the necessity of MPNN for low-frequency information.\n\nAs 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.\n\nWavelet 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. \n\nNotably, 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.\n\n> Q3: Description on kernel parameters.\n\nOur 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.\n\n> Q4: Usage of tight frames and parameter sharing.\n\n1) **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.\n\n2) **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.\n\n> Q5: Does MLP(F(X)) facilitate interaction between node features?\n\nIt 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.\n\nHowever, 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.\n\n> Q6: Rationality of only keeping the first 30% graph spectrum.\n\nFollowing 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.\n\nThese 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. \n\n> Q7: Use the same datasets across experiments.\n\nWe have supplemented experiments as in Tab. 3, 4 and 5 in the link. New results did not overturn the conclusions in the paper.", "claims_and_evidence": "The paper provides theoretical and empirical support for WaveGC’s ability to capture both short-range and long-range information, as well as its superior performance over existing models. However, several claims require further validation.\n\n1. The assertion that WaveGC covers extremely large scales ($s \\rightarrow \\infty$) is supported by theoretical proof but lacks empirical verification as there is no analysis of the actual learned scale values or their impact.\n\n2. Since only a single scaling term is used for low-frequency information while multiple wavelet bases are employed, the authors justify the addition of an MPNN in parallel to augment low-frequency modeling. However, the scaling function already takes a value of 1 at $\\lambda = 0$, and other wavelet bases can also learn low-frequency components near the origin. Fig.3 shows that $g(s_3 \\lambda)$ retains a significant amount of low-frequency information, raising the question of whether the additional MPNN is truly necessary for enhancing low-frequency modeling. I think if WaveGC can achieve strong performance without MPNN, it would better demonstrate its adaptability.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are generally well-aligned with the problem of spectral graph learning, as WaveGC is tested on both short-range and long-range benchmark datasets, demonstrating its adaptability. The use of various baselines is also appropriate. However, the rationale behind certain methodological choices is not so clear to me as,\n1. The argument “powerful kernel with more parameters provide enough flexibility to adjust itself”  seems contradicting the later claim that parameter sharing is necessary due to excessive parameters.\n2. The paper claims that the matrix-valued kernel allows various frequency modes to interact. However, since $F(X)$ has a dimension of $N \\times d$ and the kernel M is $d \\times d$, the operation MLP($F(X)$) appears to facilitate interaction between node features rather than frequency modes. Is this understanding correct?", "theoretical_claims": "I have not verified the validity of Theorem 4.2 as it is in the appendix.", "experimental_designs_or_analyses": "1. The ablation studies are presented on different datasets across Tab.4, Tab.5, and Tab.6, rather than consistently using the same set of datasets. This raises concerns whether each component consistently contributes to performance improvement. Additionally, in Appendix D.7, tight frames were not applied to ogbn-arxiv and Peptides-struct, and parameter sharing was not used for most long-range datasets. The paper claims these techniques as contributions for efficient computation and performance improvement. However, since strong performance is achieved without them on certain datasets, I am not so sure how to interpret this. \n2. The paper states that, due to memory constraints, only the first 30% of eigenvalues and their corresponding eigenvectors were retained for short-range datasets. This approach likely results in a significant loss of high-frequency information, which is particularly important for short-range datasets. Given this, I have concerns on whether this strategy is appropriate unless kernels such as diffusion kernels are being tested.", "relation_to_broader_scientific_literature": "This paper advances spectral graph convolution and graph wavelet transforms in SGWT (Hammond et al., 2011). It introduces a Chebyshev polynomial decomposition into odd and even terms, ensuring strict wavelet admissibility while enabling learnable wavelet construction. Additionally, it incorporates matrix-valued kernels, inspired by Fourier Neural Operators (Li et al., 2021), to enhance spectral filtering flexibility. The paper also expands on previous graph wavelet theory by providing a theoretical proof that WaveGC effectively captures both short-and-long range information from the perspective of information mixing (Di Giovanni et al., 2023), addressing a limitation in prior work (Hammond et al., 2011) that focused only on small-scale localization.", "essential_references_not_discussed": "The paper is referencing proper and essential papers.", "other_strengths_and_weaknesses": "Strength:\n- The paper introduces a novel wavelet construction by decomposing Chebyshev polynomials into odd and even terms, ensuring wavelet admissibility. \n- These wavelets are learnable and, together with the matrix-valued kernel, provide greater flexibility. It also includes a theoretical proof for long-range information capture and demonstrates strong performance through extensive experiments across various datasets and models, achieving state-of-the-art results. \n\nWeakness: \n- However, including the concerns raised above, I see the overall lack of clarity in the writing and the complex notations as weaknesses.", "other_comments_or_suggestions": "Some minor comments would be: \n1. In Eq. (3), shouldn't the dimension be Nxd instead of NxN?\n2. The paper should states that the eigenvalues are restricted within [0,2] for normalized Laplacian to define $g(\\lambda)$ is a strict band-pass filter in the range [0,2]. \n3. There is no explanation of what $H$ represents in Eq. (8).\n4. There is a large blank space above \"Other experiments\" on page 8 and conclusion should be expanded. \n5. In Table 3, the WaveGC result for Pf is reported as 69.10, but in Table 6, it appears as 69.01.", "questions_for_authors": "- The notation in Eq. (6) seems unclear. Does $d$ here refer to the node feature dimension? According to Appendix C, the dimension of $\\hat{Z}$ is given as $N \\times (d+1)$, which does not align with the matrix operations.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "SWvvqWcDjn", "reviewer": "Reviewer_YKSE", "summary": "In this work, the authors introduce WaveGC, an innovative wavelet-based graph convolution approach featuring multi-resolution bases and a dense matrix kernel. They construct the necessary wavelet bases by leveraging Chebyshev polynomials of the first kind. For kernel implementation, they draw inspiration from AFNO, employing MLPs to create an effective kernel structure. The operation of WaveGC closely resembles FFT-based convolution. Theoretical analysis demonstrates that WaveGC effectively captures both short-range and long-range feature information. Comprehensive experimental results convincingly showcase the superior performance and effectiveness of WaveGC across various tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reviewing our work. Please, see below our answer to the raised comments/questions.\n\n> Q1: Eq. (1) is inappropriate.\n\nEq. (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.\n\n> 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?\n\nIt 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(θλ)).\n\nHowever, our design departs from this classical formulation by introducing a **matrix-valued kernel**, which enables richer transformations. Specifically:\n1. **Diagonal kernels perform independent scaling across feature channels** for each frequency mode, limiting the ability to model interactions between features.\n2. **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.\n3. 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.\n\nThus, 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.\nWe will revise the manuscript to more clearly explain this motivation and distinguish our approach from classical spectral filtering.\n\n> Q3: What are S and W in Eq. 9?\n\nS and W are the same as M in line 191 in the left column, representing different matrix-valued kernels. We will clarify this point.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n1. The authors prove that WaveGC can effectively captures both short-range and long-range feature information.\n\nWeaknesses:\n1. Eq. 1 is inappropriate. This is because in this formula, $\\lambda$ represents the eigenvalue of the graph Laplacian. Eigenvalues are clearly discrete quantities and cannot be integrated.\n2. Whether it's the graph Fourier transform or the graph wavelet transform, both are 1D discrete orthogonal transforms. For a 1D discrete orthogonal transform, a diagonal matrix rather than a full-size dense square matrix is sufficient as the kernel.", "other_comments_or_suggestions": "Although [1] was accepted by ICLR 2019, GWNN is not actually a GNN based on graph wavelet transform. First, graph wavelet transform requires the filter to be a band-pass filter, while GWNN uses the Heat Kernel, which is a low-pass filter. Second, graph wavelet transform is a discrete orthogonal transform, while $e^{-tL}$ is not a orthogonal matrix.\n\n[1] Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, & Xueqi Cheng (2019). Graph Wavelet Neural Network. In International Conference on Learning Representations.", "questions_for_authors": "1. In Eq. 9, what are the specific representation of $\\mathbb{S}$ and $\\mathbb{W}$? The explanation of different wavelet kernels is vague.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tLOOeuOmnD", "reviewer": "Reviewer_4MPc", "summary": "This paper proposes a wavelet-based graph convolution method, WaveGC, which integrates spectral bases and matrix-valued kernels. The authors use the odd and even terms of Chebyshev polynomials to learn graph wavelets that satisfy the necessary conditions. Experimental results demonstrate that the proposed method achieves promising improvements on both short-range and long-range tasks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> Q1: Compare with SOTA methods based on Fourier bases with further discussion theoretically and experimentally.\n\nBelow we address both experimental and theoretical aspects:\n1. Experimental Comparison\n\nWe 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.\n\n2. Theoretical Perspective\n\na) The core distinction between WaveGC and Fourier-based spectral methods lies in their **design focus**:\n\n$\\bullet$ Fourier-based methods typically fix the basis (Laplacian eigenvectors) and focus on designing flexible **filters**.\n\n$\\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.\n\nThese 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.\n\nb) Localization and Adaptivity\n\nGraph 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**. \n\nWaveGC 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.\n\nc) Scope of Fourier Methods\n\nWhile 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.\n\nWe will include the new experimental results and expand our discussion in the paper to address these points.\n\n> Q2: Scaling to large graphs.\n\n1) 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.\n2) 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. \n3) 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.\n\n> Q3: Can WaveGC approximate functions meet the requirements?\n\nWe 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.\n\nDespite this restriction, our approach offers **strong practical approximation capacity** due to several factors:\n\n$\\bullet$ Chebyshev polynomials form a complete basis over [0,2], allowing approximation of any continuous function on this interval.\n\n$\\bullet$ The separation into odd and even terms allows independent control over h and g while preserving admissibility.\n\n$\\bullet$ Learnable coefficients enhance flexibility in shaping the filter functions.\n\n$\\bullet$ The scaling parameter s further adapts the spectral response.\n\nTogether, 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.", "claims_and_evidence": "The authors discuss the limitations of Fourier bases in Section 3.1, arguing that they lack multi-resolution and adaptability. This serves as the main motivation for exploring graph wavelets in this paper. However, to my knowledge, FFT bases are also fixed, much like graph Fourier bases. Additionally, while graph wavelets are theoretically more flexible than graph Fourier bases, they do not seem to offer significant practical advantages. Notably, the authors' experiments do not provide a comparison with graph Fourier base-based methods, which could have helped to highlight the benefits of wavelet-based methods.", "methods_and_evaluation_criteria": "This paper introduces novel wavelet-based graph convolution methods and proposes using odd and even Chebyshev polynomials to learn graph wavelets. This approach offers a new method for graph convolution techniques and holds some implications for the graph learning community.", "theoretical_claims": "The main theoretical contribution of this paper is Theorem 4.2. I reviewed the corresponding proof and found no issues with it.", "experimental_designs_or_analyses": "The main issue in the experimental section is the absence of baselines based on Fourier bases, including polynomial approximation methods such as GPR-GNN(https://arxiv.org/abs/2006.07988), BernNet(https://arxiv.org/abs/2106.10994), UniFilter(https://arxiv.org/abs/2405.12474), S²GCN(https://arxiv.org/abs/2405.19121), and others.", "relation_to_broader_scientific_literature": "The discussion in this paper is somewhat limited to the narrow scope of graph wavelets. If the authors intend to explore spectral-based graph convolution methods, they should focus on comparing them with existing state-of-the-art methods based on Fourier bases, as this could lead to meaningful advancements in the field of graph learning.", "essential_references_not_discussed": "There is no lack of essential references, and the authors have considered the key works in the field of graph wavelets.", "other_strengths_and_weaknesses": "The significant computational complexity of eigenvalue decomposition remains a key drawback, although it is present in most graph wavelet methods. The proposed method in this paper faces challenges in scaling to large graphs. In contrast, graph Fourier-basis-based methods can be easily scaled to graphs with hundreds of millions of nodes.", "other_comments_or_suggestions": "Minor comments:\nThe $\\mathbf{I}_n$ on the left of line 108 should be written as $\\mathbf{I}_N$.\nThe K on the left in line 285 should be in math font.", "questions_for_authors": "1. Further discussion is needed on how the graph Fourier-basis-based methods compare with the method proposed in this paper, both theoretically and experimentally. This comparison should especially contain some of the latest approaches in the field.\n\n2. The functions $g$ and $h$ approximated by odd and even Chebyshev polynomials are sufficient but not necessary conditions for any function $g$ and $h$ that satisfy the graph wavelet condition. Does this imply that using odd and even Chebyshev polynomials to approximate $g$ and $h$ does not guarantee that any function meeting the requirements will be learned?\n\n\n## update after rebuttal\n\nI keep my score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tiipvteOBx", "reviewer": "Reviewer_5Zza", "summary": "The authors propose a novel spectral graph network, WaveGC, inspired by SWGT. WaveGC filters input features with matrix-valued kernels in the spectral domain and utilizes transformer architectures for wavelet transforms. The wavelet functions are learnable and are parameterized by Chebyshev polynomials with learnable spatial scales and polynomial coefficients. The authors provide theoretical results on the short-range and long-range performance of WaveGC and demonstrate its effectiveness on both node-level and graph-level tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for taking the time to review our paper. Please, see below our answer to the raised comments/questions.\n\n> Q1: The quality of Figure 1 is still not good enough.\n\nWe 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.\n\n> Q2: Practical advantage of being admissible.\n\n|        |     Actor      |    Tolokers    |\n| :---: | :------------: | :------------: |\n|  DEFT  |   35.04±1.89   |   84.32±0.45   |\n| WaveGC | **37.40±1.04** | **85.38±0.52** |\nTable 1. Comparing WaveGC and DEFT on heterophily datasets.\n\nThe 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**.\n\nThe **practical advantage** of admissibility becomes evident in tasks that require strong node-wise representation learning. For instance:\n\n$\\bullet$ In **short-range node-level tasks** (e.g., CS, Photo, Computer, CoraFull, ogbn-arxiv), WaveGC consistently outperforms baselines.\n\n$\\bullet$  In **long-range node-level tasks** (e.g., VOC and COCO), WaveGC also demonstrates superior performance.\n\n$\\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.\n\nTogether, 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.", "claims_and_evidence": "The authors supported their claims with evidence.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense to me.", "theoretical_claims": "The theoretical results make sense to me.", "experimental_designs_or_analyses": "The experimental design and analyses make sense to me.", "relation_to_broader_scientific_literature": "The authors proposed a new spectral GNN architecture based on graph wavelets. Good enough for an ICML submission.", "essential_references_not_discussed": "While there were concerns about WaveGC missing the prior work (Bastos et al., 2022) that learns spectral wavelets, I see that the authors have included it as a baseline and shown competitive performance against it. I agree the novelty is somewhat limited along this line, but I think it is fine as long as the authors do not overclaim.", "other_strengths_and_weaknesses": "Strengths: The authors analyze WaveGC theoretically. The method is evaluated on large datasets. The authors also provide details that rationalize WaveGC in Section 5.\nWeaknesses: The quality of Figure 1 is still not good enough.", "other_comments_or_suggestions": "Interestingly I am assigned the same paper that I reviewed a year ago. Most of my concerns, e.g. missing evaluation on large datasets and using eigenvalue embeddings, were addressed during the rebuttal period last year and in this new submission. Thus I maintain the same score as last year.", "questions_for_authors": "The authors now advertise WaveGC satisfying admissibility criteria as the main advantage against (Bastos et al., 2022). I understand this is theoretically more appealing, but what is the practical advantage of being admissible?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a wavelet-based graph convolution architecture (WaveGC) designed to integrate learnable spectral wavelet bases with matrix-valued kernels, resulting in more expressive and localized graph representation learning. The method introduces a novel decomposition of Chebyshev polynomials into odd and even components, ensuring admissibility and multi-scale expressiveness. The model is shown to outperform existing spectral methods, particularly in long-range and heterophilous settings. The work is supported by both theoretical insights and empirical validations across a broad range of benchmarks.

There is a range of reviewer sentiment across the four reviews, though the discussion and rebuttal process was constructive. The authors responded to all concerns in satisfactory ways, and demonstrated a willingness to clarify design decisions and revise the manuscript accordingly.

**Weak Accepts:**

Reviewers 5Zza, and YKSE find the contribution meaningful and well-supported. Reviewer 5Zza highlights that many concerns raised in a prior review round have been addressed and praises the theoretical rigor and empirical validation. Reviewer YKSE raised some technical questions on formulation and implementation details (e.g., kernel choice and matrix structure), which were answered to their satisfaction in the rebuttal.

**Weak Rejects:**

Reviewers 4MPc and JRdk express concerns around either comparative analysis or interpretability of results. In particular, 4MPc critiques the absence of Fourier-basis baselines and the scalability of WaveGC. In response, the authors ran new experiments comparing against GPR-GNN, BernNet, UniFilter, and S²GCN, showing that WaveGC consistently outperforms them, particularly in long-range settings. The authors also proposed a polynomial-based approximation to reduce complexity to O(N), directly addressing scaling concerns. Reviewer JRdk initially questioned the necessity of MPNN for low-frequency recovery and the truncation of eigenvalues; these were answered through both visualization and analytical explanations. While JRdk remained skeptical about the spectral range truncation, the authors presented both spectral and spatial perspectives to support their design.

Reviewer 4MPc remained concerned about scalability and still found the improvements over Fourier-based methods to be insufficiently compelling. Yet, to my understanding, the new experiments provided by the authors in the rebuttal do address these concerns. 

**Summary** 

The authors’ rebuttal was comprehensive and collegial throughout: In addition to running new comparisons, they clarified theoretical justifications (e.g., admissibility, receptive field behavior, and MPNN integration) and responded to formatting and clarity suggestions. WaveGC is an interesting contribution to spectral graph learning with a new, well-motivated architecture and empirical strength across diverse tasks. The addition of a computationally efficient variant further improves the paper’s relevance. Assuming the authors follow through with their promised revisions, this work would be a good addition to ICML.
Decision: Accept (poster)