Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited
Authors: Mingguo He
Zhewei Wei
Ji-Rong Wen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Chebyshev Approximation
Chebyshev Interpolation

Abstract: Designing spectral convolutional networks is a challenging problem in graph learning. ChebNet, one of the early attempts, approximates the spectral graph convolutions using Chebyshev polynomials. GCN simplifies ChebNet by utilizing only the first two Chebyshev polynomials while still outperforming it on real-world datasets. GPR-GNN and BernNet demonstrate that the Monomial and Bernstein bases also outperform the Chebyshev basis in terms of learning the spectral graph convolutions. Such conclusions are counter-intuitive in the field of approximation theory, where it is established that the Chebyshev polynomial achieves the optimum convergent rate for approximating a function. 

In this paper, we revisit the problem of approximating the spectral graph convolutions with Chebyshev polynomials. We show that ChebNet's inferior performance is primarily due to illegal coefficients learnt by ChebNet approximating analytic filter functions, which leads to over-fitting. We then propose ChebNetII, a new GNN model based on Chebyshev interpolation, which enhances the original Chebyshev polynomial approximation while reducing the Runge phenomenon. We conducted an extensive experimental study to demonstrate that ChebNetII can learn arbitrary graph convolutions and achieve superior performance in both full- and semi-supervised node classification tasks. Most notably, we scale ChebNetII to a billion graph ogbn-papers100M, showing that spectral-based GNNs have superior performance. Our code is available at https://github.com/ivam-he/ChebNetII.

Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited
Mingguo He Renmin University of China mingguorruc. edu. en
Zhewei Wei" Renmin University of China zheweidruc www.rruu.......oooooooooooo
Ji-Rong Wen Remmin University of China jrwenCruc edu. on
Abstract
Designing spectral convolutional networks is challenging problem in graph learning. ChebNet, one of the early attempts, approximates the spectral graph convolutions using Chebyshev polynomials. GCN simplifies ChebNet by utilizing only the first two Chebyshev polynomials while still outperforming it on real-world datasets. GPR-GNA and BernNet demonstrate that the Monomial and Bernstein bases also outperform the Chebyshev basis in terms of learning the spectral graph convolutions. Such conclusions counter-intuitive in the field of approximation theory, where it is established that the Chebyshev polynomial achieves the optimum convergent rate for approximating function.
In this paper, we revisit the problem of approximating the spectral graph convolu- tions with Chebyshev polynomials. We show that ChebNet's inferior performance is primarily due to illegal coefficients learnt by ChebNet approximating analytic ter functions, which leads to over-fitting. We then propose ChebNetll, new GNN model based on Chebyshev interpolation, which enhances the original Chebyshev polynomial approximation while reducing the Runge phenomenon. We conducted an extensive experimental study to demonstrate that ChebNetlI can learn arbi- trary graph convolutions and achieve superior performance in both full- and semi- supervised node classification tasks. Most notably, we scale ChebNetll to a billion graph ogbn-papers 100M, showing that spectral- based GNNs have superior perfor- mance. Our code is available at httpt::///// thub. com/ ivam- he/ ChebNetiI
Introduction
Graph neural networks (GNNs) have received considerable attention in recent years due to their
remarkable performance variety of graph learning tasks, including social analysis [3] 24 38).
drug discovery [49 19 32 traffic forecasting (26 and recommendation system 44] 46
Spatial-based and spectral- based graph neural networks (GNNs) are the two primary categories of often rely on message propagation and aggregation mechanism between neighboring nodes. Spectral-bar -based methods [8] [2] create spectral graph convolutions or, equivalently, spectral graph filters, the spectral domain of the graph Laplacian matrix. We can further divide spectral-based GNNs into two categories based on whether or not their graph convolutions can be learned.
GNNs. To learn node representations, spatial- GNNs 21 L3
Predetermined graph convolutions: GCN 21 employs simplified first tow Chebyshev polynomials as the graph convolution, which fixed low-pass filter [ APPNP [22 and GDC [12] set the graph convolution with Personalized PageRank (PPR) and also achieve a low-pass filter. [12 54 S²GC [52] derives the graph convolution from the Markov Diffusion Kernel, which is low- and high-pass filter trade-off. GNN-LF/HF 54
41
43
(4).
'Zhewei Wei the corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

designs the graph convolutions from the perspective of graph optimization that can imitate low- and high-pass filters.
Learnable graph convolutions: ChebNet S approximates the graph convolutions using
Chebyshev polynomials and, in theory, could learn arbitrary filters [. CayleyNet [23]
learns the graph convolutions with Cayley polynomials and generates various graph filters. GPR-GNN [6] uses the Monomial basis to approximate graph convolutions, which can derive low- or high-pass filters. ARMA [2] learns the rational graph convolutions through the Auto- nuto-Reeressvve Moving Average filters family (28). BernNet [17] utilizes the Bernstein basis to approximate the graph convolutions, which can also learn arbitrary graph filters.
Despite the recent developments, unsolved. First of all, is well-known that GCN (21] outperforms ChebNet 8 on real-world datasets (e.g., semi-supervised node classification tasks citation datasets (1 )- However, it is
fundamental problems with spectral-based GNNs remain
also established that GCN is a simplified version of ChebNet with only the first two Chebyshev
polynomials and that ChebNet has more expressive capability than GCN in theory M. Consequently,
natural question is: Why is ChebNet's 's performance inferior to GCN's 's despite its better expressiveness?
Secondly, shown in 17. the real-world performance of ChebNet is also inferior to that of GPR- GNN [6] and BernNet 17 which use Monomial polynomial basis and Bernstein polynomial basis to approximate the spectral graph convolutions. Such a conclusion is counter-nttuiive in the field of approximation theory, where it is established that the Chebyshev polynomial achieves near-optimum error when approximating a function [13]. Therefore, the second question is: Why is ChebNet's 's filter inferior to that of GPR-GNN and BernNet, despite the fact that Chebyshev polynomials have a higher approximation ability?
In this paper, we attempt to tackle these problems by revisiting the fundamental problem of approxi- mating the spectral graph convolutions with Chebyshev polynomials. First of all, according to the theory of the Chebyshev approximation, we observe that the coefficients of the Chebyshev expansion for an analytic function need to satisfy inevitable convergence. Consequently, ChebNet's inferior performance is primarily due to illegal coefficients learnt by ChebNet approx- imating analytic filter functions, which leads over-fitting- Furthermore, we propose ChebNetlI, a new GNN model based on Chebyshev interpolation, which enhances the original Chebyshev polynomial approximation while reducing the Runge phenomenon [10]. Our ChebNetll model has robust scalability and can easily cope with various constraints on the learned filters via simple reparameterization, such as the non-negativity constraints proposed in [17]. Finally, we conduct an extensive experimental study to demonstrate that ChebNetlI can achieve superior performance in both full- and semi-supervised node classification tasks and scale to the billion graph ogbn-papers 100M
prove that
2 Revisiting ChebNet
Notations. We consider an undirected graph G (V, with node set V and edge set E. Let ||| denote the number of nodes. We use x E Rn to denote the graph signal, where x(i) denotes the signal at node i. Note that in the general case of GNNs where the input feature is a matrix X. we can treat each column of X as graph signal. Let A denote the adjacency matrix and D denote the diagonal degree matrix, where D. Σ, Aij. For convenience, we use P D-122 AD-1/2 and
L=I- I 1-2 AD- matrix of G, respectively. We use L- = UAU to represent the eigendecomposition of L, where U denotes the matrix of cigenvectors and A = diag (X1, An] is the diagonal matrix of eigenvalues.
- 1/2 to denote the normalized adjacency matrix and the normalized Laplacian
2.1 Speetral-based GNNs and ChebNet
Spectral-based GNNs create the spectral graph convolutions in the domain of Laplacian spectrum. Recent studies suggest that many popular methods use the polynomial spectral filters to achieve graph convolutions g 21 17 We can formulate this polynomial filtering operation as
K
y = Udiag [&(A),, 4(Am)) UXx U
Σ wv L'x,
(I)
k=0
where y denotes the filtering results of x, and (()) is called the spectral filter, which is a function of cigenvalues of the Laplacian matrix L. The Wig denote the polynomial filter weights, and the

---

Table Comparison of ChebNet and GCN.
Table 2: Comparison of different bases.
Method
Cora
Citeseer
Pubmed
Method
Cora
Citeseer
Pubmed
ChebNet (2) 80.54 70.35
70.5
ChebBase 79.29 +0.36 70.76
78.07 +0.32
ChebNet (10) 74.91 =0.52
65.91 67.69
GPR-GNG GRRGGNN 83.95
70.92
78.97
GCN
01.32 71.77+0.11
79. 19.155.am =
BernNet 83.15 02.24-0.25 79.65
polynomial filter can be defined as ((A)= = Ek wx À E [0, 2j. ChebNet g is a remarkable aftempt in this field, which uses Chebyshev polynomial to approximate the filtering operation.
K
(L)xx
(2)
k=0
where L 22/2 denotes the scaled Laplacian matrix. Amar is the largest eigenvalue of L and Wx denote the Chebyshev coefficients. The Chebyshev polynomials can be recursively defined as (z)) 2xTx-1(x) - (x), with To( = and Ti Txx)) ChebNet's structure is:
K
Y
Σ TW(L)XW R=0
(3)
with the trainable weights We. The Chebyshev coefficients wk of the filtering operation (2) are implicitly encoded in the weight matrices Wg. We list more spectral-based GNNs' details in the supplementary materials.
2.2 The motivation of revisiting ChebNet
ChebNet versus GCN. Even though GCN is simplified form of ChebNet, is well known that ChebNet is inferior to GCN for semi-supervised node classification tasks [21] Table [ shows the results of ChebNet and GCN for semi-supervised node classification tasks on Cora, Citeseer and Pubmed datasets (see the Appendix for experimental details). We find that ChebNet is inferior to GCN, especially when we increase the polynomial order from 10 in Equation (3)
On the other hand, existing research [I] has shown that ChebNet is more expressive than GCN in theory. particular, ChebNet can approximate arbitrary spectral filters as K increases, while GCN is fixed low-pas -a-pass filter. If we set K = and wo = wi in the Equation (2) ChebNet corresponds high-pass pass filter; we set K and wh W1. ChebNet becomes low -ww-pass filter which is essentially the same as GCN. Consequently, a natural question is: Why is ChebNer's 's performance inferior to GCN's despite better expressiveness?
Chebyshev basis versus other bases. Chebyshev polynomials are widely used to approximate various functions in the digital signal processing and the graph signal filtering [36 37). The truncated
Chebyshev expansions are demonstrated to produce a minimax polynomial approximation for the analytic functions [3.. Consequently, the spectral filters can be well-approximated by truncated expansion in terms of Chebyshev polynomials Ti (x) up to K-th order [16..
K
M(²)=
we T 1-1,1]
(4)
A==
where Â is the eigenvalue of the scaled Laplacian matrix L. ChebNet g then defined the graph convolutions using the Chebyshev approximated filters, while recent works were inspired by ChebNet and used Monomial (i.e., GPR-GNN (6)) and Bernstein (i.e., BernNet (17) bases to approximate filters. In order evaluate the approximation ability of Chebyshev basis, propose ChebNet with explicit coefficients, ChebBase, which simply replaces the Monomial basis of GPR-GNN and Bernstein basis of BernNet with the Chebyshev basis. The expression of ChebBase is
Y
Σ Wp Te (L)fo (X),
(5)
k=
where fo (X) denotes Multi-Layer Perceptron (MIP). Table 2 reveals the results of ChebBase, GPR-GNN and BernNet for node classification tasks three citation graphs. We can observe that
3

---

10
ChebBase
10-1
1.5
ChebBase/k
10-1
1.0
10
0.5
10-7
10-1
0
10
10
(a) Chebyshev coefficients of exp(().
(b) Chebyshev coefficients learnt on Cora.
Figure Illustrations of the Chebyshev expansion's coefficients of exp(()) and the Chebyshev coefficients learnt by ChebBase and ChebBase/k: on Cora.
ChebBase has the worst performance, which is inconsistent with the fact that the Chebyshev basis approximate minimax polynomial in theory. Therefore, the second question is: Why is ChebNet's filter inferior to that of GPR-GNN and BernNet, despite the fact that Chebyshev polynomials have a higher approximation ability?
2.3 Coefficient Constraints
We now demonstrate that ChebNet's suboptimal performance is due to the illegal coefficients learned, which results in over-fitting. Given an arbitrary continuous function f(r: in the interval [-1, 1], the Chebyshev expansion is defined as f(z) = En=o wxTTx() with the Chebyshev coefficients wk- The following theorem establishes that in order to approximate analytic function, the Chebyshev expansion's ' coefficients must be constrained.
[48] If f(x) is weakly singular at the boundaries and analytic in the interval (-1, 1). then the Chebyshev coefficients wy will asymptotically (as - 20) decrease proportionally to 1/k" for some positive constant q-
Theorem 2.1.
Here, "weakly singular" means that the derivative of could vanish at the boundaries, and "analytic" means f can be locally given by convergent power series in the interval (-1,1). Intuitively, Chebyshev polynomial (xx(r) with larger corresponds to higher frequency oscillation (see the Appendix for more details). Theorem 2.] essentially demonstrates that high frequency polynomials should be constrained in the Chebyshev expansion to approximate an analytic function. Figure [(a) depicts the Chebyshev expansion's coefficients of the analytic function erp()) ()) used as spectral filter in GDC [12 and shows that the coefficients convergent.
The ability to approximate an analytic function crucial in the task of approximating the spectral filters, since non-analytic filters are more difficult to approximate by polynomials and may result in
Table 3: The performance of ChebBase.
Method
Cora
Citeseer
Pubmed
ChebNet GCN
80.54
70.35
75.52
over-fitting In particular, ChebNet and ChebBase learn the coefficients wi by gradient descent with- out any constraints. The coefficients may not satisfy Theorem 2.1 leading their poor performance. To validate this conjuncture, we conducted an empirical analysis of ChebBase with difference coefficient constraints. Inspired by Theorem 2.1
81.32 71.77 79.15 19.1540.18
ChebBase ChebBase/ /k 82.66 72.52 79.25 10.31
70.76 79.2940.36
20.32
use the following propagation process for the ChebBase/ k.
K Wk
Y
(L)) (X), k
k=0
where w denote the Chebyshev coefficients implemented by reparameterizing the learnable param- eters wy. Table the experimental results of the supe-vupe node classification performed on the citation graphs. We can observe that with simple penalty on wi. ChebBase//k outperforms ChebNet, ChebBase, and GCN. Figure ((b) plots the absolute value of the Chebyshev coefficients learnt by ChebBase and ChebBase/k on Cora. We can observe that the coefficients of ChebBase/k could more readily satisfy the convergence constraint. These results validate Theorem 2.1

---

3 ChebNetll model
Although ChebBase/k appears to be promising approach, it still has some drawbacks: Imposing the penalty on the coefficients is not mathematically elegant, as Theorem 2.T only provides necessary condition for the coefficients; spectral filters. For example, it is unclear how we can modify Equation (6) to obtain non-negative filters, a requirement proposed in [7]. this section, we describe ChebNetll, a GNN model based on Chebyshev interpolation that resolves the above two issues. We also discuss the advantages and disadvantages of various polynomial interpolations as well as the Runge phenomenon.
It is hard to impose further constraints on the learned
3.1 Chebyshev interpolation
Consider real filter function l(() that continuous in the interval [-1, 1]. When the values of this filter are known a finite number of points Åk. one can consider the approximation by polynomial Pk with K degree such that h(xx)= = Px (A+). which the general polynomial interpolation. We give explicit expression of the general polynomial interpolation in the supplementary materials.
We generally sample the K + points No < Å1 <... < 'x uniformly from [-1, 1] to construct the interpolating polynomial Px (Å). Intuitively, increasing K should improve the approximation quality. However, this is not always the case due to the Runge Phenomenon [1]] (The details are discussed in section (.3). The popular approach to this problem in the literature 14] is Chebyshev interpolation, having superior approximation ability and faster convergence. Instead of sampling the interpolation points uniformly, Chebyshev interpolation uses Chebyshev nodes as the interpolation points, which are essentially the zeros of the (K + 1)-th Chebyshev polynomial.
Definition 3.1. (Chebyshev Nodes) The Chebyshev polynomial Tg(x)) satisfies the closed form expression Ti (x) cos (k arccos(z)). The Chebyshev Nodes for [z(z) are defined as zz
2j+
j 0, 0.1.... k-- - 1, which lie in the interval (-1,1) and the zeros of T2 (z).
2k
Definition 3.1 suggests that each Chebyshev polynomial Ta (z:) has k zeros, and we can define Chebyshev interpolation by replacing the equispaced points with Chebyshev nodes in the general polynomial interpolation (see the Appendix for details). More eloquently, definition 3.2 efficiently defines the Chebyshev interpolation via their orthogonality properties.
Definition 3.2. (Chebyshev Interpolation) [14] Given continuous filter function h()), let x,- Co8
i+t//2 K+I कτ
.j = 0.. denote the Chebyshev nodes for TK+1 and Mxx)) denotes the function
value node Tj. The Chebyshev interpolation of h()) is defined to be
K
Pk(Å)
& K+L
2
Σ Max))Ta(H))
where the prime indicates the first term is to be halved, that is, do co/2, di cI....,ck CK-
3.2 ChebNetll via Chebyshev Interpolation
Inspired by Chebyshev interpolation, we propose ChebNetll, a graph convolutional network that approximates an arbitrary spectral filter (Å) with an optimal convergence rate. ChebNetll simply reparameterizes the filter value h(x,) in Equation (7) as a learnable parameter Yj. which allows the model to learn an arbitrary spectral filter via gradient descent. More precisely, the ChebNetIl model can be formulated as
2 K
==
Tr (T
where x; cos ((j + 1/2) x /K 1)) are the Chebyshev nodes of TK+1, fx(X) denotes an MLP on the node feature matrix X, and 7; for = 0, 1.... K are learnable parameters. Note that similar to APPNP (22), we decouple feature propagation and transformation.
5

---

Table Dataset statisties.
Chameleon Squirrll
Actor
Texas
Cornell Cora Citeseer Pubmed ogbn-arxiv ogbn-papers 100M
Nodes
2277
5201
7600
183
183
2708
3327
19,717
169,343
111,059,956
Edges
31,371
198,353
26.659
279
277
5278
4552
44,324
1,166,243
1,615,685,872
Features
2325
2089
932
1703
1703
1433
3703
500
128
128
Classes
5
5
5
40
172
H(G)
0.23
0.22
0.22
0.11
0.30
0.81
0.74
0.80
0.66
Consequently, the filtering operation of ChebNetll can be expressed as
K K
Σ
y K+1 k=
is easy to see that compared to the filtering operation of the original ChebNet 2 we only make K one simple change: reparameterizing the coefficient Wk by Wig K+1 Σ/= 7 (x))) However, this simple modification allows us to have more control on shaping the resulting filter, as Chebyshev interpolation suggests that Y directly corresponds to the filter value h(zz) at the Chebyshev node zy. The coefficients Wig K+1 Σソ= (my) are fundamentally guaranteed satisfy the
2
constraints of Theorem 2.1 since we directly approximate the filter Furthermore, Chebyshev interpolation also provides the ChebNetll with several beneficial mathematical properties.
3.3 Analysis of ChebNetll
ChebNetll has several advantages over existing GNN models due to the unique nature of Chebyshev interpolation. From the standpoint of polynomial approximation and computational complexity, we
compare ChebNetll with current related approaches such as GPR-GNN (6) and BernNet [17
Near-minimax approximation. First of all, we examine ChebNetlI's capabilities in terms of filter function approximation. Theorem exhibits that ChebNetll provides an approximation that is close to the best polynomial approximation for a spectral filter
Theorem 3.1.
27 A polynomial approximation Pi (x) for a function f(x is said be near-
best/minimax approximation with a relative distance p if
[z) (=)]l S (1+ p))lf(z) PB(2))l.
(10)
where p is the Lebesgue constant, (z) is best polynomial approximation, and ||- represents the uniform norm (i.e., [6|| max (g(x))). Then, we have p 2 as K oc for the general polynomial interpolation, and p log K) K for the Chebyshev interpolation.
(z)
Convergence. In comparison to BernNet 17), which uses the Bernstein basis, ChebNetll has a faster convergence rate for approximating filter function. Specifically, we have the following Theorem:
Theorem 3.2. [14. 29 Let (x( be the polynomial approximation for function f(x). Then the error is given as [lf(z) (x(x)]l S E(K). If PK(x) is obtained by Bernstein approximation,
then E(K) (1
(2K)-²)w(l (K -1/);; Px(x) obtained by Chebyshev Interpolation, then E(K) ~ CW(( log( K) with constant C, where w is the modulus of continuity.
Runge phenomenon. In comparison GPR-GNN (6), which uses the Monomial basis, ChebNetlI has the advantage of reducing the Runge phenomenon [0.. In particular, when we use the general polynomial interpolation to approximate Runge filter h(Å) with a high degree over set of equis- paced interpolation points, it will cause oscillation along the edges of interval. Consequently, as the degree of the polynomial increases, the interpolation error increases. Following [14], we define the error of polynomial interpolation as
1. 1K-1(() (K + 1)! MK (
Rx (x h(²) (x(()=
(11)
where ग (Å) = -T )x)) denotes the nodal polynomial and ( the value depending on Å. The terrible Runge phenomenon is caused by the values of this nodal polynomial, which have very
(²)

---

Table Dataset statistics large heterophilic graphs.
Penn94
pokec
arXiv-year
genius
twitch-gament
wiki
Nodes
41,354
1,632,803
169,343
421,961
168, 144
1,925,342
Edges
1,362,229
30,622,564
1,166,243
984,979
6,797.557
303,434,860
Features
65
128
12
600
Classes
2
2
5
2
2
5
H(G)
0.47
0.46
0.22
0.62
0.55
0.39
high oscillations around the interval endpoints. In particular. for high-degree polynomial interpolation
at equidistant points in [-1, I], we have limx- [max_ [max_15áş] [R (A)l) oc.
On the other hand, we have the following Theorem 3.3 that explains that Chebyshev nodes can
minimize and quantify this eπror caused by the nodal polynomial, meaning Chebyshev interpolation minimizes the problem of the Runge phenomenon.
Theorem 3.3. 14] Consider the Chebyshev nodes 2j = cos (() + 1/2) x
K. Then the nodal polynomial (x) = II =z)) has the smallest possible uniform norm, i.e.,
[ 2-K
Computational complexity. Compared to BernNet 17. which has time complexity quadratic to the order K in the forward process, ChebNetll can be computed in time linear to K. Specifically, we first compute the ChebNetll's coefficients K41 Σy=0 ?) TTTx((z)) ( in time linear to K as we can precompute (T,)), and then plug the coefficients into Equation (8) for propagation, which also takes
2
the time linear to K, the same that of ChebNet [ and GPR-GNN 6].
4 Experiments
In this section, we conduct experiments to evaluate the performance of ChebNetll against the state-of-the-art graph neural networks on wide variety of open graph datasets.
Dataset and Experimental setup. We evaluate ChebNetll on several real-world graphs for the Semi- and Full-supervised node classification tasks. The datasets include three homophilic citation graphs: Cora, Citeseer, and Pubmed [35] 45), five heterophilic graphs: the Wikipedia graphs Chameleon and Squirrel [34], the Actor co-occurrence graph, and webpage graphs Texas and Cornell from WebKE (30] two large citation graphs: ogbn-arxiv and ogbn-papers I 100M [18], J as well as six large heterophilic graphs: Penn94, pokec, arXiv-year, genius, twitch-gamers and wiki 251 We measure the level of homophily in graph using the edge homophily ratio H(G) = ()
[53)
[
where denotes the label of node v. We summarize the dataset statistics in Tables Jand 5 All the experiments carried out machine with NVIDIA RTX8000 GPU (48GB memory), Intel Xeon CPU (2.20 GHz) with 40 cores, and 512 GB of RAM.
4.1 Semi-supervised node classification with polynomial- methods
Setting and baselines. For the semi-supervised node classification task, compare ChebNetll to 7 polynomial approximation filter methods, including MLP, GCN [I], ARMA (2, APPNP [2]] ChebNet [8], GPR-GNN [6] and BernNet [17]. For dataset splitting, employ both random and fixed splits and report the results on random splits. The results of fixed splits will be discussed in the Appendix.Speccine Specificallly, we apply the standard rraining/validationnessttgg split (45) the three homophilic citation datasets (i.e., Cora, Citeseer, and Pubmed), with 20 nodes per class for training, 500 nodes for validation, and 1,000 nodes for testing. Since this standard split not be used for very small graphs (e.g. Texas), we use the sparse splitting 6 with the training/valle validation/tess sets accounting for 2.5%/2.5%/954 respectively, on the five heterophilic datasets.
For ChebNetll, we use Equation as the propagation process and use the ReLu function to reparametrize ?/j. maintaining the neg-tiity of the filters [7]. We set the hidden units as 64
http:://ww.... edu/ att/csssssssssss//ass cmu, www.eedu/ppee wttp.edduppoojjectteoo----//////

---

Table 6: Mean classification accuracy of semi-supervised node classification with random splits.
Method
Cham.
Squi.
Texas
Corn.
Actor
Cora
Cite.
Pubm.
MLP
26.364285
21.42
32.42
36.5
29.75
57.17
70.52 46.75
GCN
38. 48.15
31.18+031
34.68
32.36+8.55
22.74
79. 19.1
69.71
78. 8 +0.44
ChehNet
37.15
26.5510.6
36.35
28.781485
26.581192
78.08
67.87
73.9611.8
ARMA
37.42+1.72
24.15
39.65+8.00
18.90
27 27.0222211
79. 79.14
69.35+144
78.31
APPNP
32.73+231
24.50
34.79410.11
34.85
29.74=104
82.39
69.794092
49.97
GPR-GNN
33.03
24.36.1.50
13
38, 18.95412236
28 11
82,374091
69.22 69.2221:27
79.28 79,28
BemNet
27.32+4044
22.37
43.01
39.42-49.5
29.87
82. 82.17
69.444m97
79.484147
ChebNetll
43.4213.54
46.58 33.9611.22
42.19 11149
30.18 1881
82.4210.4
69.89 11:11
19.5
Table 7: Mean classification accuracy of full-supervised node classification with random splits.
Method
Cham.
Squi.
Texas
Corn,
Actor
Cora
Cite.
Pubm.
MLP
46.59
31.01
86.81
84.15
40. 40.18 1
76.52 26.892u.97
86.14 14
GCN
6098
45.87
76.97
65.78
33. 33.2611.15
87.1811.12
79.85 0.78
86.7910.31
ChebNet
19.51
40.81
86.28+262
83.91+217
37. 50
87 87.32
79.33-o57
87.82+002
ARMA
60.0
36.27
83.97
85.62.2213
37.67 10.54
87.13
80.04_0.5
86,9310.4
APPNP
52.15
2078
90.64
91.52-2181
39.7620449
88. 18.71
80.47
88.13
GCNII
43.44
41.96=1102
80,46+591
84.26
36.89
88.4 28.46
79.97
89.94
TWIRLS
50.21 12.9
39.63
91.31 13336
89.83 1229
38.13 1:881
88.57 10.91
80.07
0.94
88.8710.43
EGNN
51.55
35.81 1091
21.34
82.09-1116
35. 16
21.47
80.51_a93 =099
80.5
88, 88.74.0..6
PDE-GCN
66.01
48.73=106
93.24
89.73
79.76
88 1..022+1.00
79.98
89.92
GPR-GNN
67.49
50.43
21.32
91.57 96
39.91 20:2
88 20.57
80.13_084
88.4610031
BemNet
68.53
51.39 =092
92.62+1.57
92.13+1.64
41.71+1112
88 51 +0,92
80.08-0.5
88.51 +0,39
ChehNeill +1.37
57.72_a.59
93.28
92.30
11.75
88.71 +0,33
80.53_a.79
88.93
and K 10 for the all datasets the same GPR-GNN [6] and BernNet [17.. We employ the Adam SGD optimizer [20] with an early stopping of 200 and a maximum of 1000 epochs to train
ChebNetll. We use the officially released code for GPR-GNN and BernNet and use the Pytorch Geometric library implementations [1] for other models (i.e., MLP, GCN, APPNP, ARMA, and and baselines' settings are listed in the Appendix.
ChebNet). More details of
Results. We utilize accuracy (the micro-F1 score) with a 95% confidence interval as the evaluation metric. Table reports the relevant results on 10 random splits. Boldface letters indicate the best result for the given confidence interval, and underlinings denote the next best result. We first observe that ChebNet is inferior to GCN even on heterophilic graphs, which concurs with theoretical analysis that the illegal coefficients learned by ChebNet lead to over-fitting, ChebNetll, on the other hand, outperforms other methods on all datasets excluding Pubmed, where it also achieves top-2 classification accuracy. This quality is due to the fact that the learnable parameters 7 of ChebNetll directly correspond to the filter value h(z,) at the Chebyshev node æ., effectively preventing it from learning an illegal filter.
4.2 Full-supervised node classification
Setting and baselines. For full-supervised node classification, we compare ChebNetll to the baselines in the prior superviee node classification. We also include GCNII [5). TWIRLS 44] EGNN (51) and PDE-GCN [9] four competitive baselines for full-supervised node classification. For all datasets, we randomly split the nodes into 60%, 20%, and 20% for training, validation and testing, and all methods share the same 10 random splits for a fair comparison, as suggested in 30 6 17]
For ChebNetlI, we also set the hidden units to be 64 and K 10 for all datasets, and employ the same training manner as in the semi-supervised node classification task. For GCNII TWIRLS, EGNN and PDE-GCN we use the officially released code. More details of pyram-ear and baselines' settings are listed in the Appendix.
Results. Table 7 reports the mean classification accuracy of each model. We first observe that, given more training data, ChebNet starts to outperform GCN on both homophilic and heterophilic datasets, which demonstrates the effectiveness of the Chebyshev approximation. However, we also observe that ChebNetll achieves new state-of-the-art results on 7 out of 8 datasets and competitive results on Pubmed. Notably, ChebNetll outperforms GPR-GNN and BernNet by over 10% on the
8

---

Table Experimental results on large heterophilic graphs. OOM denotes "out of memory".
Method
Penn94
pokec
arXiv-year
genius
twitch-gamers
wiki
MLP
73.61 =0.40
62.37
36.70+u.21
86.68 +0.09
60.92
37.28
LINK
80.79=0.49
80.54
53.97
73.56+0.14
64.85+0.21
47.21
LINKX
84.71 0.52
82.04
56.00
90.77 10.27
66.06
59.80
GCN
82.47
75.45
46,02
87, 87.42-+0.37
62. 12.28
OOM
GCNII
82.92
78, 78.94
47.2 10.28
90.24
63.39
OOM
ChebNet
82.59 =0.39
72.71 20.66
46.7640.24
89.36
62.31
OOM
GPR-GNN
83.54_0.32
80.74
45.97 10.26
90.15
62.59
58.734034
BerNeet
83.26
81.67 10.17
46.34
90.47
64.27 10.31
59.02
ChebNetlI
84.86 0.33
82.33 0..28
48.53
90.85
65.03
60.95 1..39
Squirrel dataset. We attribute this quality to the fact that Chebyshev interpolation achieves near- minimax approximation of any function with respect to the uniform norm, giving ChebNetll greater approximation power than GPR-GNN and BernNet do.
4.3 Scalability of ChebNetII
For ChebNetll we calculate and save Ti (L) for & E o.... KK in the preprocessing, we can scale it to large graphs. Specifically, the below propagation expression.
K y ((()
Y = fo()), Z 2
(12)
K
K=
The pre-computed ' X allow us to train 7j and fa(-) in mini-batch manner. This approach also
works for GPR-GNN 66 and BernNet [17] so we report their results in this manner when ChebNetll
does. We evaluate the scalability of ChebNetll on the large heterophilic graphs (25 and the widely used OGB datasets (18).
On the large heterophilic graphs, we compare Cheb-
Table 9: Mean classification accuracy large graphs. OOM denotes "out of memory" and "L" means failing finish preprocessing in 24h.
NetII to eight competitive baselines, including MLP, LINK [50]. LINKX (25), GCN (21). GCNII [5].
ChebNet M. GPR-GNN 6 and BernNet [17]. For
ChebNetll, we use Equation [22 as the propagation process pokec and wiki and Equation (8) the four remaining datasets. We establish the experi- mental setting following (25) and use the published baselines' results, excluding GPR-GNN. More de- tails are listed in the Appendix. Table g reports the mean results of each method over 5 runs. ChebNetl outperforms all other methods on out of datasets and the polynomial-based methods on ar Xiv-vryear and wiitch-gamers, Notably, LINK and LINKX out- perform ChebNetll on arXiv-yean because they use a directed graph on this dataset. Using the directed graphs to the spectral-based GNNs is future meaningful work because the current spectral graph theory only applies to undirected graphs. For the largest heterophilic graph wiki, ChebNetll obtains a new state-of-the- result. We attribute that ChebNetlI can precompute É x without the graph sampling used in LINK and LINKX and has strong filter approximation ability.
Method
ogbn-arxiv ogbn-papers 100M
GCN
71.74
OOM
ChebNet ARMA
71.12
00M
71.47
00M
GPR-GNN
71.78+0.18
65.89+0.3
Berneet
71.96
SIGN
71.95++0.12
65.68 20.16
GBP
72.21
65. 65.2340.31
NDLS
72.24
65.61 10.29
ChebNeilI
72.32++0.3
67.18
On ogbn-arxic and -papers 100M, we compare ChebNetII to polynomial- based GNNs and state-of- the-art scalable GNNs. SIGN [33. GBP 4 and NDLS* 47). We follow the standard splits (18) and use Equation 122 as the propagation process. More details of settings are listed in Appendix. Table reports the mean accuracy of each model over 10 runs. Note that we do not include the result of BernNet on ogbn-papers 100M as BernNet has a time complexity quadratic to the order K and fails to finish the preprocessing in 24 hours. We can observe that ChebNetll outperforms both datasets,

---

1.0
Chabyshav110)
Chebyshev(29)
1.5
Monomial1
0.5
Monomial(10)
Dernstein(10
1.0
Bernstenn(20)
Chbpsherdd Codaykea221
0.0
0.5
-1.0 -0.5
0.0
0.5
10
-0.5
0.0
0.5
1.0
(a) filter and its approximation results.
(b) The error of approximation results.
Figure 2: (a) A Runge filter h()) 1/(1 + 25 and its approximation results by different polynomial bases. (b) The errors of the different approximation results.
which we attribute to Chebyshev Interpolation's superior approximation quality. These results also show that ChebNetll has lesser complexity and greater scalability than BernNet.
4.4 Comparison of Different Polynomial Bases
We perform numerical studies comparing the Chebyshev basis to the Monomial and Bernstein bases to demonstrate ChebNetll's approximation power. Considering a Runge filter (()) = 1/(1 2552), E [-1,1], Figures ((a) and 2(b) depict the approximation results and errors for several polynomial bases, with the polynomial degree denoted by the numbers in brackets. We find that the Chebyshev basis has faster convergence rate than the Bernstein basis and does not exhibit the Runge phenomenon compared to the Monomial basis. Notably, JacobiConv [40] investigated different polynomial bases the same period and discovered that orthogonal polynomial bases could learn graph filters more effectively. These findings provide empirical motivations for designing GNNs with Chebyshev interpolation.
Conclusion
This paper revisits the problem of approximating spectral graph convolutions with Chebyshev polynomials. We show that ChebNet's inferior performance primarily due illegal coefficients learned by approximating analytic filter functions, which leads to over-fitting. Moreover, we propose ChebNetll, a new GNN model based on Chebyshev interpolation, enhancing the original Chebyshev polynomial approximation while reducing the Runge phenomenon. Experiments show that ChebNetll outperforms SOTA methods in terms of effectiveness on real-world both homophilic and heterophilic datasets. For future work, a promising direction is further to improve the performance of ChebNetll on large graphs and investigate the scalability of spectral-basee GNNs.
Acknowledgments and Disclosure of F Funding
The work was partially done at Gaoling School of Artificial Intelligence, Peng Cheng Laboratory, Beijing Key Laboratory of Big Data Management and Analysis Methods and MOE Key Lab of Data Engineering and Knowledge Engineering. This research was supported in part by the major key project of PCL (PCL202IA12), by National Natural Science Foundation of China (No. 61972401, No. 61932001, No. 61832017, No. U2001212), by Beijing Natural Science Foundation (No. 4222028), by Beijing Outstanding Young Scientist Program No. BJJZYJJH1120 100020098, by Alibaba Group through Alibaba Innovative Research Program, by CCF-Baidu Open Fund (NO.202 APP1 2021PPP5002000 and by Huawei-Renme University joint program on Information Retrieval. We wish to acknowledge the discussion with Professor Zhouchen Lin from Peking University. We also wish to acknowledge the support provided by Engineering Research Center of Next-Generation Intelligent Search and Recommendation, Ministry of Education. Additionally, we acknowledge the support from Intelli- gent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Firs Class" Initiative, Public Policy and Decision maaonnnmaingggg Research Lab, Public Computing Cloud, Renmin University of China.
10

---

References
[1] Muhammet Balcilar, Pierre Héroux, Benoit Gaüizrre Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In ICLR, 2021.
[2] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. TPAMI, 2021.
[3] Toon Bogaerts, Antonio D Masegosa, Juan S Angarita-Zapata, Enrique Onieva, and Peter Hellinekx. A graph cnn-Istm neural network for short and long-term traffic forecasting based on trajectory data. Transportation Research Part C: Emerging l'ccnologiiss 2020.
[4] Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. NeurIPS, 2020.
[5] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICMI, pages 1725-1735. PMLR, 2020.
[6] Eli Chien, Jianhao Peng. Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
[7] Zhiyong Cui, Kristian Henrickson, Ruimin Ke, and Yinhai Wang. Traffic graph convolutional recurrent neural network: A deep learning framework for network-scale traffic learning and forecasting. T-ITS, 41811)4483344844 2019.
[8] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS, pages 3844-3852, 2016.
[9] Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations. In NeurlPS, volume 34, 2021.
[10] James F Epperson. On the runge example. The American Mathematical Monthly, 341,), 1987.
[11] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In ICLR, 2019.
[12] Johannes Gasteiger, Stefan Weiß enberger, and Stephan Günnemann. Diffusion improves graph learning. In NeurlPS, 2019.
[13] Keith O Geddes. mear-minimax polynomial approximation in an elliptical region. SIAM Journal on Numerical Analysis, 15(6))1225-12)) 1233, 1978.
[14] Amparo Gil, Javier Segura, and Nico M Temme. Numerical methods for special functions. SIAM, 2007.
[15] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, pages 1025-1035, 2017.
[16] David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. graph theory. Applied and Computational Harmonic Analysis,
Wavelets on graphs via spectral
2011.
[17] Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In NeurlPS, 2021.
[18] Weihua Hu. Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS, volume 33, 2020.
[19] Dejun Jiang, Zhenxing Wu, Chang Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingiun Hou. Could graph neural networks learn better molecular representation for drug discovery? comparison study descriptor-based and graph-based models. Journal of cheminformatics, 13(1):1-23, 2021.
11

---

[20] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[21] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[22] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
[23] Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. Transactions on Signal Processing, 67(1):97-109, 2018.
[24] Chang Li and Dan Goldwasser. Encoding social information with graph convolutional networks forpolitical perspective detection in news media. In ACL, 2019.
[25] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non non-hononne non-homophilous graphs: New benchmarks and strong simple methods. In NeurlPS, 2021.
[26] Tanwi Mallick, Prasanna Balaprakash, Eric Rask, and Jane Macfarlane. Transfer learning with graph neural networks for short-term highway traffic forecasting. In ICPR, pages 10367-10374. IEEE, 2021.
[27] John Mason and David C Handscomb. Chebyshev polynomials. CRC press, 2002.
[28] Sunil K Narang, Akshay Gadde, and Antonio Ortega. Signal processing techniques for interpo- lation in graph structured data. In ICASSP. IEEE, 2013.
[29] Andrea Pallini. Bernstein-type approximations smooth functions. Statistica, 6592),169-19,, 2005.
[30] Hongbin Pei. Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
[31] Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In KDD, 2018.
[32] Prakash Chandra Rathi, R Frederick Ludlow, and Marcel L Verdonk. Practical high-quality electrostatic potential surfaces for drug discovery using conaolioovolltional deep neural network. Journal of medicinal chemistry, 63(16))8778-8790 2019.
[33] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint 1rXiv:2004.1198, 2020.
[34] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())xenab014, 2021.
[35] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3)993-93, 2008
[36] David Shuman, Pierre Vandergheynst, and Pascal Frossard. Chebyshev polynomial approxi- mation for distributed signal processing. In DCOSS, pages 1-8. IEEE, 2011.
[37] Ljubisa Stankovic, Danilo Mandic, Milos Dakovic, Milos Brajovic, Bruno Scalzo, and An- thony G Constantinides. Graph signal processing-part ii: Processing and analyzing signals on graphs. arXiv preprint arXiv: 10325, 2019.
[38] Peihao Tong, Qifan Zhang, and Junjie Yao. Leveraging domain context for question answering over knowledge graph. Data Science and Engineering, 4(4):323-335, 2019.
[39] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
12

---

[40] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In ICML, 2022.
[41] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
[42] Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. Ression-based recommendation with graph neural networks. In AAAI, 2019.
[43] Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning. In IJCAI, 2019.
[44] Yongyi Yang, Tang Liu, Yangkun Wang. Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang. and David Wipf. Graph neural networks inspired by classical iterative algorithms. ICMI,, 2021.
[45] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, pages 40-48. PMLR, 2016.
[46] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018.
[47] Wentao Zhang, Mingyu Yang. Zeang Sheng, Yang Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Node dependent local smoothing for scalable graph learning. In NeurIPS, volume 34, 2021.
[48] Xiaolong Zhang and John Boyd. Asymptotic coefficients and errors for chebyshev polynomial approximations with weak endpoint singularities: Effects of different bases. Science China Mathematics, 2022.
[49] Tianyi Zhao, Yang Hu, Linda R Valsdottir, Tianyi Zang, and Jiajie Peng. Identifying drug-targe interactions based on graph convolutional network and deep neural network. Briefings in bioinformatics, 22(2):2141-2150) 2021.
[50] Elena Zheleva and Lise Getoor. To join or not to join: the illusion of privacy in social networks with mixed public and private profiles. In Proceedings of the 18th international conference on World wide web, pages 531-540, 2009.
[51] Kaixiong Zhou, Xiao Huang. Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. In NeurIPS, volume 34, 2021.
[52] Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In ICLR, 2021.
[53] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In NeurlPS, 2020.
[54] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In WWW, 2021.
13


Reviews:
[{"review_id": "Qwf4y2vPT35", "reviewer": "Reviewer_jWTu", "summary": "This paper revisited the Chebyshev approximation and showed that the inferior performance of ChebNet is due to illegal learnt coefficients. On the basis of this insight, a new GNN model called ChebNetII is proposed enhancing the Chebyshev polynomial approximation and reducing the Runge phenomenon. ChebNetII can achieve the state-of- art performance on some open graph datasets.", "questions": "1.\tDo you have some suggestions about the choice of $K$? Does it the same as the original ChebNet?\n2.\tWhat does ‘weakly singular’ mean? The vanishing of the derivative of $f$ seems inequivalent to ‘$f$ be locally given by a convergent power series in the interval $(-1,1)$’ at line 132. Could you please give some clear mathematical explanation?\n3.\tWhy one can assert $w_0=w_1$ implies a high-pass filter and $w_0=-w_1$ at line 102 implies a low-pass filter?", "limitations": "CheNetII seems to have broad applications besides the experiments shown in the paper. One can show more future directions in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths: The authors showed a sharp eye for the subtle inferior performance of ChebNet compared with GCN, GPR-GNN and BernNet and proposed two questions to generalize the problem. By citing related theorems, both the questions are explained clearly. The novel model ChebNet resolves the questions without introducing expensive additional computation complexity.\n*Weaknesses: The main theoretical frame is assembled by existing results. It is okay but maybe it makes the paper not very innovative. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IZnDIPI5esi", "reviewer": "Reviewer_ypP8", "summary": "This paper revisits the traditional problem of approximating graph convolutional networks using Chebyshev polynomials. The paper shows that the performance of the network can be greatly improved by using Chebyshev Interpolation to replace the coefficients of ChebNet on both homophilous and heterophilous graphs.", "questions": "The questions have been discussed in detail as above. To sum up, the main questions are:\n\n•\tThe difference between ChebBase and ChebNet should be better explained.\n\n•\tIt would be interesting to showcase some of the filters that ChebNetII has learned. What distinguishes them from the ones learned by BernNet?\n\n•\tThe best results should also be highlighted in Table 3.\n", "limitations": "Yes,  the limitation of this work has been well discussed.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work is mostly well-written with informative content and new ideas that are worth publishing.\n\nStrengths:\n\n•\tThe use of Chebyshev Interpolation is both theoretically and practically justified.\n\n•\tChebNetII's performance improvement is significant, particularly for semi-supervised node classification tasks.\n\n•\tFollowing on from the second point, to the best of my knowledge, this paper presents the first empirical study of semi-supervised node classification with polynomial graph filters.\n\n•\tChebNetII scales to the graph Papers100M, which has more than a billion edges.\n\n•\tThe overall presentation is satisfactory.\n\nWeaknesses:\n\n•\tThere should be a clearer explanation of the distinction between ChebBase and ChebNet.\n\n•\tIt would be interesting to showcase some of the filters that ChebNetII has learned. What distinguishes them from the ones learned by BernNet?\n\nMinor points:\n\n•\tThe best results should also be highlighted in Table 3.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A6KSIIrNXkV", "reviewer": "Reviewer_s9em", "summary": "This paper proposes an extension to ChebNet by introducing Chebyshev Interpolation. The proposed methods is simple, yet provides theoretical support and improved performances for node classification. ", "questions": "Can ChebNetII be extended with any adaptive learning such as in GPRGNN?\n\nCompared to GPRGNN or MixHop, does ChebNetII learn by convolution using higher-order hops from a node?  \n\n\nExperiments are descent, however, dataset are a bit old. There is a new homophily measure and new non-homophilic benchmark datasets introduced by [Lim et al., 2021a, Lim et al., 2021b].\nCan the authors provide few more experiment with the new new non-hohopnilic datasets?\n\nCan the authors include LINK [Zheleva and Getoor, 2009] as a baseline methods?  LINK only uses from the adjacency matrix and gives good indication to learning without node features and convolutions.\n\nReference:\n   \n[Zheleva and Getoor, 2009] Zheleva, E. and Getoor, L. (2009). To join or not to join: The illusion of privacy in  social networks with mixed public and private user profiles. WWW ’09.\n\n[Lim et al., 2021a] Lim, D., Hohne, F. M., Li, X., Huang, S. L., Gupta, V., Bhalerao, O. P., and Lim, S.-N.  (2021a). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In  NeurIPS.\n \n[Lim et al., 2021b] Lim, D., Li, X., Hohne, F., and Lim, S.-N. (2021b). New benchmarks for learning on  non-homophilous graphs. Workshop on Graph Learning Benchmarks, WWW 2021.", "limitations": "Limitations and potential negative societal impact are not well expressed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.) Simple model with theoretical support\n2.) Experimental results are favorable.\n3.) Paper is well written and easy to read.\n\nWeaknesses:\n1.) Theoretical comparisons to adaptive learning of GPRGNN is not clear.\n2.) Incremental work though the contribution is useful.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept