BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation
Authors: Mingguo He
Zhewei Wei
Zengfeng Huang
Hongteng Xu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Networks
Bernstein Polynomial Approximation
Arbitrary Spectral Filters

Abstract: Many representative graph neural networks, $e.g.$, GPR-GNN and ChebNet, approximate graph convolutions with graph spectral filters. However, existing work either applies predefined filter weights or learns them without necessary constraints, which may lead to oversimplified or ill-posed filters. To overcome these issues, we propose $\textit{BernNet}$, a novel graph neural network with theoretical support that provides a simple but effective scheme for designing and learning arbitrary graph spectral filters. In particular, for any filter over the normalized Laplacian spectrum of a graph, our BernNet estimates it by an order-$K$ Bernstein polynomial approximation and designs its spectral property by setting the coefficients of the Bernstein basis. Moreover, we can learn the coefficients (and the corresponding filter weights) based on observed graphs and their associated signals and thus achieve the BernNet specialized for the data. Our experiments demonstrate that BernNet can learn arbitrary spectral filters, including complicated band-rejection and comb filters, and it achieves superior performance in real-world graph modeling tasks. Code is available at https://github.com/ivam-he/BernNet.

BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation
Mingguo He Renmin University of China mingguo&ruc.. edu..eedueee. en
Zhewei Wei" Renmin University of China zhewei eruc. edu. cn
Zengfeng Huang Fudan University huangzfffudan. edu. cn
Hongteng Xu Renmin University of China hongtengxu&ruc. edu. cn
Abstract
Many representative graph neural networks, e.g., GPR-GNN and ChebNet, ap- proximate graph convolutions with graph spectral filters. However, existing work either applies predefined filter weights or learns them without necessary constraints, which may lead to oversimplified or ill-posed filters. To overcome these issues, we propose BernNet, novel graph neural network with theoretical support that provides simple but effective scheme for designing and learning arbitrary graph spectral filters. In particular, for any filter of a graph, our BernNet estimates it by an order- K Bernstein polynomial approxi- mation and designs its spectral property by setting the coefficients of the Bernstein basis. Moreover, we can learn the coefficients (and the corresponding filter weights) based observed graphs and their associated signals and thus achieve the BernNet specialized for the data. Our experiments demonstrate that BernNet can learn arbitrary spectral filters, including complicated cajd-rejection and comb filters, and it achieves superior performance in real-world graph modeling tasks. Code is available hattps://gi thgtbbbb.b..b......m com/ com/ivam ivvm- he/ /eeernnett
the normalized Laplacian spectrum
Introduction
Graph neural networks (GNNs) have received extensive attention from researchers due to their excellent performance various graph learning tasks such social analysis [4
17 29) drug traffic forecasting [8. 3 (), recommendation system 38 and computer Recent studies suggest that many popular GNNs operate as polynomial graph spectral
discovery 12
25),
vision 39 4
filters 7 13
5
16
2 35). Specifically, we denote an undirected graph with node set V and edge
(V, E),, whose adjacency matrix is A. Given signal x [x] E H²M on the graph, where n V| is the number of nodes, we can formulate its graph spectral filtering operation as
E' as
EK wv L wy 's the filter weights, L I D 1/2 --1 A/ 11/2 is the symmetric normalized Laplacian matrix of G, and D the diagonal degree matrix of A. Another equivalent polynomial filtering operation is Ek Pkxx x, where P = P= 1/2 1-12 AD 11/2 is the normalized adjacency matrix and C are the filter weights.
Zhewei Wei and Hongteng Xu are the corresponding authors. Work partially done at Gaoling School of Artificial Intelligence, Beijing Key Laboratory of Big Data Management and Analysis Methods, MOE Key Lab of Data Engineering and Knowledge Engineering, Renmin University of China, and Pazhou Lab, Guangzhou. 510330, China.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

BernNet
G(V, E)
Graph Spectral Filtering
M(A)
Bernstein Approximation
Model Parameter {0x H
Eigenvalue
Filter
(AT
(A)
(A)
Laplacian
Matrix
L
K
8k
(2I
Bernstein Basis
Signal X
2
km0
Figure An illustration of the proposed BernNet.
We can broadly categorize the GNNs applying the above filtering operation into two classes, de- pending whether they design the filter weights or learn them based on observed graphs. Some representative models these two classes are shown below.
The GNNs driven by designing filters: GCN 13 uses simplified first-order Chebyshev polynomial, which is proven to be a low-pass filter [ 31 34 41]. APPNP [14) utilizes Personalized PageRank (PPR) to set the filter weights and achieves a low-pass filter as well [5] 41. GNN-LF/HF 40 designs filter weights from the perspective of graph optimization functions, which simulate high- and low-pass filters.
The GNNs driven by learning filters: ChebNet 7 approximates the filtering operation with Chebyshev polynomials. and learns filter via trainable weights of the Chebyshev basis. OPR-GNN [5] learns polynomial filter by directly performing gradient descent on the filter weights, which can derive high- or low-pass filters. ARMA learns a rational filter via the family of Auto-Regressive Moving Average filters 21
Although the above GNNs achieve some encouraging results in various graph modeling tasks, they still suffer from two major drawbacks. Firstly, most existing methods focus on designing or learning simple filters (e.g., low- and/or high-pass filters), while real-world applications often require much more complex filters such as band-rejection and comb filters. To the best of our knowledge, none of the existing work supports designing arbitrary interpretable spectral filters. The GNNs driven by learning filters can learn arbitrary filters in theory, but they cannot intuitively show what filters they have learned. other words, their interpretability the filter weights 's but only proves small subset of the learnt weight sequences corresponds to low- or high-pass filters. Secondly, the GNNs often design their filters empirically or learn filter weights without any necessary constraints. As result, their filter weights often have poor controllability, For example, GNN-LF/HF [4] designs its filters with a complex and non-intuitio polynomial with difficult-to-tune hyperparameters. The multi-layer GCN/SGC [13 31 leads to "ill-posed" filters (i.e., those deriving negative spectral responses). Additionally, the filters learned by GPR-GNN [ ChebNet 7 have chance to be ill-posed well.
poor. For example, GPR-GNN [5] learns
To overcome the above issues, we propose a novel graph neural network called BernNet, which provides effective algorithmic framework for designing and learning arbitrary graph spectral filters. illustrated in Figure 1, for an arbitrary spectral filter h [0, 2) + [0, 1] over the spectrum of the symmetric normalized Caplacian L, our BernNet approximates h by a K-order Bernstein polynomial approximation, i.e., h(A)= Ex O&bk K (A). The non-negative coefficients {0x ( of the Bernstein basis [bK (X)) work the model parameter, which can be interpreted as h(2/KK) h: = O...., K (i.e., the filter values uniformly sampled from [0, 2). )- By designing or learning the 02 's,
be formulated as Σk_ b (K) (2I K>-IXx where is the graph signal. We further demonstrate the
obtain various spectral filters, whose filtering operation
rationality of our BernNet from the perspective of graph optimization any valid polynomial filers, i.e., those polynomial functions mapping [0, to [0, 1), can always be expressed by our BernNet, and accordingly, the filters learned by our BernNet are always valid. Finally, we conduct experiments to demonstrate that 1) BernNet can learn arbitrary graph spectral filters (e-g., band-rejection, comb, low-band- www-band-aas,, pass, etc.), and 2) BernNet achieves superior performance real-world datasets.

---

2 BernNet
2.1 Bernstein approximation of spectral filters
Given an arbitrary filter function h [0. 2] + [0, 1), let = UAU denote the eigendecomposittin of the symmetrie normalized Laplacian matrix L, where U is the matrix of eigenvectors and A diag (A.... >n] is the diagonal matrix of eigenvalues. We use
h(L)x= = Uh(A)UXx Udiagli(AA))..... UX"n)
(1)
to denote spectral filter on graph signal x. The key our work is approximate (LL) (or, equivalently, (A)). For this purpose, we leverage the Bernstein basis and Bernstein polynomial approximation defined below.
Definition 2.1 ( (10). (Bernstein polynomial approximation) Given an arbitrary continuous func- tion ft) on E [0, 11, the Bernstein polynomial approximation (of order K) for f is defined as
K
K ( (
pk (1) Σ
O2 PE
(1)
Σ
-1)K 11)K--k-- k)
K
is the k-th Bernstein base, and 02 f(()) is the function value at k//K, K, which works as the coefficient of by (t).
Here, for .,,, K, 6% (t)
Lemma 2.1 ( (10). Given arbitrary continuous function f(t) on t E 10, 11. let (t) denote the Bernstein approximation of f()) as defined in Equation 2 We have pr (1) - s(t) as K + co.
For the filter function h [0, + [0, 1]. let l 2/2 and f(1) h(26). so that the Bernstein polynomial approximation becomes applicable, where 0₂ f(k/ K) h(2k/ K) and by (t) o% (3) = (1) - (2)* for k = 1..... K. Consequently, we can approximate h(A) by Oz
pk (A/2) = Ox=00x(E) (x) - 3)) )k== (2) = Ek O (x) - 2) ~>* and Lemma 2.1
ensures that PK (A/2) h(2) as K + oc.
Replacing (h(A,) with {pk (A./2)) we approximate the spectral filter hL) in Equation
as Udiag pK (A1/2), PM PIC (An/ /)" and derive the proposed BernNet. In particular, given a graph signal x, the convolutional operator of our BernNet defined as follows:
K
K k
z = Udiaglex (A)
PK.
x
Σ
ON
2K
(21 - (2
K
L
(3)
BernNet
where each coefficient 0₂ can be either set to h(2k/ K) to approximate a predetermined filter or learnt from the graph structure and signal in end-to-end fashion. As natural extension of Lemma 2.1 our BernNet owns the following proposition.
Proposition 2.1. For arbitrary continuous filter function h 10, 2] - [0, 1). by setting 0% (22k/K), k = O...., K, the z in Equation B
satisfies z + h(L)xx as + oc.
K (2) Ek On य. (2) =) and Lemma 2.1 ensures that px(222) h(A) 02 h(2k:/ K) and K xc.
Proof. According to the above derivation, we have pk (A/2) 0
O& (*)
Consequently, we have
z= ==UdiaglpK (2) (x(nn/))'>>>>>>>>>> (di.gl h(L)
as 0g h(22k/ K) and K + oc.
2.2 Realizing existing filters with BernNet.
As shown in Proposition 2.1 our BerNeet can approximate arbitrary continuous spectral filters with sufficient precision. Below we give some representative examples of how our BernNet exactly realizes existing filters that are commonly used in GNNs.
3

---

Table 1: Realizing commonly used filters with BernNet.
Hilter types
Hilter R(A)
0g for U....,K K
Bersstein approximation px($)
BernNet
All- pass
6g k/K
Lineur low-pass
2/2
A/2
Lineur high-pass
1/2
0, k/KK
X/2
L
Impulse low-pass
(A
6n and other 82 =
(1 A/2)
(2I
L)
Impulse high-pass
(2(A)
8K and other 0
(A/2)
L
Impulse bund-pass
6((A)
0K/² 1 and other O2
(2/2)
(A/2222
(2r
LA2
All-pass filter h(A) = 1. We set 02 = for h = 0,..., K, and the approximation px (x))) = 1 is exactly the same with h(A). Accordingly, our BernNet becomes an identity matrix, which realizes the all-pass filter perfectly.
Linear low-pass filter h(A) 1-2 We set 8g = 1- -t-k/K for k: = O..... K and obtain
.....
(k($) = 1 2/2. The BernNet becomes En=0 K 2
(K-k) 1 (x) (21 K))->I
I- L
which achieves the linear low-pass filter exactly. Note that I - - 2 (I+ P) is also the
same as the graph convolutional network (GCN) before renormalization [3
Linear high-pass filter h(A)= = X/2. Similarly, we can set 0g k/ K for k 0, 0.... Koo
get perfect approximation p ( -.2 and the BernNet becomes L
Note that even for those non-continuous spectral filters, e.g., the impulse low/high/band-pan filters, our BernNet can also provide good approximations (with sufficient large K).
Impulse low-pass filter ((A) = (A) We set 0g 1 and 0g = 0 for k * 0, and px(2) = (1 2)K Accordingly, the BerNNet becomes linear low-pass filter.
(0)-1)); L)K deriving an K K-llayer 2 (2I -
1
Impulse high-pass filter h(A) = 62()). We set 0K and 0g 0 for * K, and px = (5)* "
The BernNet becomes 2 L i.e., an K K-layer linear high passspassssa filter.
Impulse band-pass filter (A) = 61 (A). Similarly, we set 0x/2 = 1 and 0g = 0 for kt +f K/2, and px (5) (1))) 2/2)* The BernNet becomes z Kk/2 (2I
K
L) /)///1122 K/2 which can be explained as stacking K/ K/2-layer linear low-pass filter and a K/2-layer linear high-pass filter. Obviously, K should be an even number this case.
Table I summarizes the design of the BernNet for the filters above. We can find that an appealing advantage of our BernNet is that its coefficients are highly correlated with the spectral property of the target filter. In particular, we can determine to pass or reject the spectral signal with À R 2 This
2k
K by using
a large or small 0g because each Bernstein base i,K (A) corresponds to a "bump" located at K- property provides useful guidance when designing filters, which enhances the interpretability of our BernNet.
2.3 Learning complex filters with BernNet
Besides designing the above typical filters, our BernNet can express more complex filters, such as band-pass, band-rejection, comb, low-band-pian -pass filters, etc. Moreover, given the graph signals before and after applying such filters (i.e., the x's and the corresponding z z's), our BernNet can learn their approximations in an end end-to-end manner. Specifically, given the pairs {x, z). we learn the coefficients (0x K of the BernNet by gradient descent. More implementation details can be found at the experimental section below. Figure 2jillssrrtess the four complex filters and the approximations we learned (The low-band pass filter is h())) = Iio.o.5 (A) + exp (-10((A 0.5) (o..,)) exp (-50(A- - M. (A), where (A) = 1 when À E Ω2 otherwise (A( = 0). In general, our BernNet can learn a smoothed approximation of these complex filters, and the approximation precision improves with the increase of the order K. Note that although the BernNet cannot pinpoint the exact peaks of the comb filter or drop to 0 for the valleys of comb or low-band-pass filters due to the limitation of K, it still significantly outperforms other GNNs for learning such complex filters.
+
The impulse function (A) = 1 if À æ, otherwise (A)

---

1000-100-111
100A -17)
[sin(xA]]
Low-band
1.0
1.0
H(A
DCA)
0.3
0.5
Real
Phel
A
(a) Band-pass
(b) Band-rejection
(c)
Comb
(d)
Low- band-aandddaa pands
Figure 2: Illustrations of four complex filters and their approximations learnt by BernNet.
BernNet in the Lens of Graph Optimization
In this section, we motivate BernNet from the perspective of graph optimization. In particular, we show that any polynomial filter that attempts to approximate a valid filter has to take the form of BernNet.
3.1 A generalized graph optimization problem
Given n-dimensional graph signal x, we consider a generalized graph optimization problem
min f(z) a)1" (L)z allz -
(4)
where a E [0, 1) trade-off parameter, 12 denotes the propagated representation of the input
graph signal x, and (L) denotes an energy function of L, determining the rate of propagation (28). Generally, 7-) operates on the spectral of L, and we have (L) Udiagly(A1)... ..., ?(An)
We can model the polynomial filtering operation of existing GNNs with the optimal solution of Equation 44) For example, if
r(L) L, then the optimization function 44) becomes
f(z) = (1 ax) Lz + al|z - x|2. a well-known convex graph optimization function proposed by
Zhou et al. [40]. fzz) takes the minimum when the derivative 0f(x) which solves to
2(1 (11-aa) aa)aaazz 2a (z x) 0.
aI (I- (1
Σ a(1 - a)* (I- (- Σ a(1-a)'p'x
By taking suffix sum > kk a(1 - <x*x, obtain the polynomial filtering operation for
APPNP [14. Zhu et al. [41 further show that GCN 13), DAGNN [9), and JKNet (36 can be interpreted by the optimization function (4) with (L) = L.
The generalized form of Equation 4 allows us to simulate more complex polynomial filtering
operation. For example, let 0.5 and <LL) = e I, heat kernel with the temperature
parameter. Then fzz takes the minimum when the derivative 0f(z) which solves to
I) z +
ix
2
-I =e ((I-P)
Σ k=0
Pxx.
M
By taking a suffix sum Exn -t pkx,, we obtain the polynomial filtering operation for the heat kernal based GNN such as GDC [15] and GraphHeat [34
3.2 Non-negative constraint on polynomial filters
natural question is that, does an arbitrary energy function (LL correspond to a valid or ill- ill-posed spectral filter? Conversely, does any polynomial filtering operation Σ L correspond to the optimal solution of the optimization function (4) for some energy function >(L)
As it turss out, there is a "minimum requirement" for the energy function >L); (L) has to be positive semidefinite. In particular, if 7(L) is not positive semidefinite, then the optimization
5

---

function fz) is not convex, and the solution to a = 0 may corresponds to a saddle point.
oz
Furthermore, without the positive semidefinite constraint on (L), (z) may goes to -o as we set to be multiple of the eigenvector corresponding to the negative eigenvalue.
Non-negative polynomial filters. Given a positive semidefinite energy function (L), we now consider how the corresponding polynomial filtering operation Σx=o L2L should look like. Recall that we assume (L)) Udiagly(A1)) ?(nn) By the positive semidefinite constraint, we have (() 2 0 for À E [0, 2]. Since the objective function f(z) is convex, it takes the minimum when (f 2(1 - (ar((L))n)))))) (L)z + 2a (z x) = 0. Accordingly, the optinum 2" can be derived as
02
a (al = (1- a1-)) x Udiag
a (1 ()) a+ (1-a))(An)
U
(5)
Let h(A) = (+(1-a))(2) denote the exact spectral filter, and = wx denote a polyno-
mial approximation of (A) (e.g. the suffix sum of (A)'ss taylor expansion). Since 7()) 2 0 when
À E [0, 2). we have S h(A) 5 a+(1-a)- = for X [0, 2]. Consequently, it is natural to assume
the polynomial filter ((A = Ek wx also satisfies 0 S g(A) < 1.
Constraint 3.1. Assuming the energy function y(L) is positive semidefinite, polynomial filter g(A) -k w approximating the optimal solution to Equation has to satisfy
K
x((A)=
k=0 way 1. AA [0,2].
(6)
While Constraint 3.1 seems to be simple and intuitive, some the existing GNN may not satisfies this constraint. For example, GCN uses Px (I L) x, which corresponds to polynomial filter
g(A) = 1- À that takes negative value when À > 1, violating Constraint 3.1 As shown [31, the
renormalization trick P D) 1/2 (I + A) (I D) 1/22 shrinks the spectral and thus reliefs the problem. However, g()) may still take negative value the maximum eigenvalue of L I P is still larger than 1.
3.3 Non-negative polynomials and Bernstein basis
such that S g() S 1 when À E [0, 2]. The g{)) S 1 part is trivial, we can always rescale each wn: by a factor of K
Constraint 3.1 motivates us to design polynomial filters g(A)
Ek= A* -K
Lk=o |ws]] 12* The (A) 2 0 part, however, requires more elaboration. Note that we can not simply set wy 2 0 for each A = 0 K, since it is shown in [5) that such polynomials only correspond to low-pass filters.
As turns out, the Bernstein basis has the following nice property: a polynomial that is non- non-negative on certain interval can always be expressed non-negative linear combination of Bemstein basis. Specifically, we have the following lemma.
Lemma 3.1 (23). Assume polynomial p(x) = Ek Og* satisfies p(x) 2 0 for x E [o, 1]. Then there exists sequence of non-negative coefficients Os. k: O,...,
.,. K, such that
K
K5 (1 k
p(z) Σ (x)
Σe 0x
Lemma 3.1 suggests that approximate a valid filter, the polynomial filter (()) has be a non- negative linear combination of Bernstein basis. Specifically, by setting x = A/2, the filter g(A) that satisfies g()) for À [0, 2] can be expressed as
K
((A) =
Σ A=
0k
(2 1
2k
Consequently, any valid polynomial filter that approximate the optimal solution of (4) with positive
semidefinite energy function 7()) has to take the following form: z Σk 0x अ (21 ~ This observation motivates our BernNet from the perspective of graph optimization any valid polynomial filers, i.e., the g [0, 2] r> [0, 1), can always expressed by BernNet, and accordingly, the filters learned by BernNet are always valid.

---

(a) Original
(h) Low-pass
(c) High-pass
(d) Band-pass (c) Band-rejection
(f) Comb
Figure 3: A imput image and the filtering results.
Table 2: Average sum of squared error and R score in parentheses.
Low-pass
High-pass
Band-pass
Band-rejection
Comb
10x(=10XF)
exeeppp-100 10A²)
exp(-10(A 1)2)
1xxp(11044 1)²)
|sin(=A)]
GCN
3.4799(
67.6635(2366)
25.8755(1148)
21.0747(,9438
50.5120(,2977)
GAT
2.3574(.9905)
21.9618(7529)
14,43261,4823
12.6384(.9622)
23.1813(,6957)
GPR-GNN
0.4169(, 9984)
0.0943( (9986))
3.5121(8851)
3.7917(.905)
4.6549(.331)
ARMA
188478(9932
(.863((9793)
7.6922(,708)
8.2732(9982)
15.1214(7775)
ChebNet
0.8220 (973)
0.7867 (.9003)
2.2722(9904)
2.5296 2.5296(9933)
4.0735(.944
Bernerr
0.0314(.999)
0.0113(9999)
0.0411(9984)
0.9313(9973)
0.9982(.988)
4 Related Work
Graph neural networks (GNNs) can be broadly divided into spectral-based GNNs and spatial-based
GNNs 333.
Spectral-based -batrall-aaeddde GNNs design spectral graph filters in the spectral domain. ChebNet 7 uses Chebyshev polynomial to approximate a filter. GCN 13 simplifies the Chebyshev filter with the first-order approximation. GraphHeat 34 uses heat kernel to design graph filter. APPNP 14 utilizes Personalized PageRank (PPR) to set the filter weights. GPR-GNN [5] learns the polynomial filters via gradient descent on the polynomial coefficients. ARMA 2
learns a rational filter via the family learns simple filters across multiple layers with a single parameter for each feature channel at each layer. As aforementioned, these methods mainly focus designing low- or high-pass filters or learning filters without any constraints, which may lead to misspecified even ill oll-posed filters.
of Auto- Reggeeeveeeev Moving Average filters [21]. AdaGNN 99
On the other hand, spatial-based GNNs directly propagate and aggregate graph information in the spatial domain. From this perspective, GCN [3] neighbor information on the graph. GAT 30
can explained as the aggregation of the one-hop uses the attention mechanism to learn aggregation weights. Recently, Balcilar et I bridge the gap between spectral-based and spatial-based GNNs and unify GNNs in the same framework. Their work shows that the GNNs can be interpreted as sophisticated data-driven filters. This motivates the design the proposed BernNet, which can learn arbitrary non-negative spectral filters from real-world graph signals.
Experiments
In this section, we conduct experiments to evaluate BernNet's capability to learn arbitrary filters as well as the performance of BernNet real datasets. All the experiments are conducted machine with an NVIDIA TTTAN GPU (12GB memory), Intel Xeon CPU (2.20 GHz), and 512GB of RAM.
5.1 Learning filters from the signal
We conduct an empirical analysis on 50 real images with the resolution of 100x100 from the Image Processing Toolbox in Matlab. We conduct independent experiments on these 50 images and report the average of the evaluation index. Following the experimental setting in [. we regard each image as a 2D regular 4-neighborhood grid graph. The graph structure translates an 10, 000 x 10, 000 adjacency matrix while the pixel intensity translates to a 10, 000-dimensional signal vector.
7

---

Table 3: Dataset statistics.
Cora
CiteSeer
PubMed
Computers
Photo
Chameleon
Squirrel
Actor
Texas
Cornell
Nodes
2708
3327
19717
13752
7650
2277
5201
7600
183
183
Edges
5278
4552
44324
245861
119081
31371
198353
26659
279
277
Features
1433
3703
500
767
745
2325
2089
932
1703
1703
Classes 7
6
5
10
8
5
5
5
5
For each of the 50 images, we apply different filters (low-pass, high-pass, band-pass, band-rejection and comb) to the spectral domain of its signal. The formula of each filter is shown in Table 2 Recall
that applying a low-pass filter exp(-10X²) to the spectral domain L = Udiag [ An] U means applying Udiag [exp(-10A7). one of the input image and the corresponding filtering results.
-=p(-) UT to the graph signal. Figure shows the
In this task, we use the original graph signal as the input and the filtering signal to supervise the training process. The goal is to minimize the square error between output and the filtering signal by learning the correct filter. We evaluate BernNet against five popular GNN models: GCN [ GAT [30]. GPR-GNN [3, ARMA (2] and ChebNet 17]. To ensure fairesss, we use two convolutional units and a linear output layer for all models. We train all models with approximately 2k trainable parameters and tune the hidden units ensure they have similar parameters. Following M. we discard any regularization or dropout and simply force the GNN to learn the input-output relation. For all models, not drop for 100 consecutive times and use Adam optimization with a 0.01 learning rate without mask to cover
set the maximum number of epochs to 2000 and stop the training if the loss does
decay. Models do not the position information of the picture pixels. We the edge nodes of the picture, so the problem can be regarded as a simple regression problem. For BernNet,
a two-layer model, with each layer sharing the same set of G2 for k ..... .. K and set K = 10. For GPR-GNN, we use the officially released code (see the supplementary materials for URL and commit numbers) and set the order of polynomial filter K 10. Other baseline models are based on Pytorch Geometric implementation [ The more detailed experiments setting can be found in the Appendix.
Table shows the average of the sum of squared error (lower the better) and the R² scores (higher the better). We first observe that GCN and GAT can only handle low-pass filters, which concurs with the theoretical analysis in M GPR-GNN: ARMA and ChebNet can learn different filters from the signals. However, BernNet consistently outperformed these models by large margin on all tasks in terms of both metrics. We attribute this quality to BernNet's ability to tune the coefficients 0g 's which directly correspond to the uniformly sampled filter values.
5.2 Node classification on real-world datasets
We now evaluate the performance of BernNet against the competitors on real-world datasets. Fol- lowing [5], we include three citation graph Cora, CiteSeer and PubMed [27] 37), and the Amazon co-purchase graph Computers and Photo (20). As shown in (5) these 5 datasets are homophilic graphs on which the connected nodes tend to share the same label. We also include the Wikipedia graph
Chameleon and Squirrel [26), the Actor co-occurrence graph, and wehpage graphs Texas and Cornell from WebKB [22]. These 5 datasets are heterophilic datasets which connected nodes tend to have different labels. We summarize the statistics of these datasets in T
Following (5). we perform full-supervised node classification task with each model, where we randomly split the node set into vrain/valiationnnest set with ratio 60%/20%/20%. For fairness, we generate 10 random splits by random seeds and evaluate all models on the same splits, and report the average metric for each model.
We compare BernNet with baseline models: MLP, GCN 13, GAT 30 APPNP 14], ChebNet (7). and GPR-GNN 5. For GPR-GNN, materials for URL and commit numbers) and set the order of polynomial filter K = 10. For other models, we use the corresponding Pytorch Geometric library implementations
the officially released code (see the supplementary
[I]] For BernNet, we
http:://ww.cc. cs. cmu. www.eedda/fasfeee ww.. wttppeee//ooojee//tooooo////////

---

188
0.4
1.0
((A)
((A)
0.2
0.5
0.5
2.0
0.0
1.5
1.0
0,0
0.
(a) Chameleon
(b) Actor
(c) Squirel
(d) Texas
Figure 4: Filters learnt from real-world datasets by BernNet.
Table 4: Results on real world benchmark datasets: Mean accuracy (%) 95% confidence interval.
GCN
GAT
APPNP
MLP
ChebNet
GPR-Gi
BernNet
Cora
87.14
88.03 #0.79
40.7
76.96=u9s
86,67 +ox2
88.57 +0.69
88.52.t0.55
CiteSeer
79.861007
80.52
80.47
76.58
79. 11:75
80.121083
80.09
PubMed
86.74.007
87.04=004
88. 18.12
85.94.0022
87.95
88 88.4610033
88.48
Computers
83.32
83.32
85.32
82.85
87.54
86.85 +::25
87.64
Photo
88. 88.261107
90.94
88, 10.31
84.72.0..4
93.77.10.2
93.85+00.2
93.63
Chameleon
59.61 1:2.1
63.13
51.84
16.85
59.28
67.28
68.29
Actor
33.23
33.93
39.66
40.19
37.61
39.924.067
41.79
Squirrel
46878
44.49 20.88
34.71 +0.57
31.03
40.55
50.15
51.35
Texas
77.38 4:328
80.82
90.98 1.64
91.45
86.22 86.22442.5
92.95
93.12 :..6..0.66
Cornell
65.90
78.21 #:29
91.81 1.9
90.82
83.934213
91.37++.81
92.13
use the following propagation process:
K
K k:
=
00
2K
21
(0- L) L
k=U
where f(X) is a 2-layer MLP with 64 hidden units on the feature matrix X. Note that this propagation process is almost identical to that of APPNP GPR-GNN. The only difference is that substitute the Generalized PageRank polynomial with Bernstein polynomial. We set the K 10 and use different learning rate and dropout for the linear layer and the propagation layer. For all models, optimal leaning rate over {0.001, 0.002, 0.01, 0.05] } and weight decay (0.0, 0.0005]. More detailed experimental settings discussed in Appendix.
use the micro-F1 score with a 95% confidence interval as the evaluation metric. The relevant results are summarized in Table Boldface letters indicate the best result for the given confidence interval. We observe that BernNet provides best results on seven out of the ten datasets. On other three datasets, BernNet also achieves competitive results against SOTA methods.
More interestingly, this experiment also shows BernNet can learn complex filters from real-world datasets with only the supervision of node labels. Figure plots some of the filters BernNet learnt in the training process. On Actor, BernNet learns an all-pass-alike filter, which concurs with the fact that MLP outperforms all other baselines on this dataset. On Chameleon and Squirrel, BernNet learns two comb-alike filters. Given that BernNet outperforms all competitors by least 1% on these two datasets, it may suggest that comb-alike filters are necessary for Chameleon and Squirrel. Figure shows the Coefficients 0g learnt from real-world datasets by BernNet. When comparing Figures and 5 we observe that the curves of filters and curves of coefficients are almost the same. This is because BernNet's coefficients are highly correlated with the spectral property of the target filter, which indicates BernNet Bernnet has strong interpretability.
Finally, we present the train time for each method in Table BernNet is slower than other methods due to its quadratic dependence on the degree K. However, compared to the SOTA method GPR- GNN, the margin is generally less than 2, which often acceptable practice. In theory, both ChebNet (7] and GPR-GNN S are linear time complexity related to propagation step K, but BernNet quadratic time complexity related K. Delgado et al. g show that Bernstein approximation can be evaluated in linear time related to K using the corner cutting algorithm. However, BernNet can not use this algorithm directly, because we need to multiply signal x. How to convert BernNet to linear complexity will be problem worth studying in the future.

---

25
2.0
20
0.6
1.0
15
10
0.5
05
08
5.0
0.0
0.0
(a) Chameleon
(b) Actor
(c) Squirel
(d) Texas
Figure 5: Coefficients 0g learnt from real-world datasets by BernNet.
Table 5: Average running time per epoch (ms)/average total running time (s).
GCN
GAT
APPNP
MLP
ChebNet
GPR-GNN
BemNet
Cora
4.59/1.62
9,56/2.03
7.16/2.32
3.06/0.93
6.25/1.76
9.94/2.21
19.71/5.47
CiteSeer
4.63/1.95
9.93/2.21
7.79/2.77
2.95/1.09
8.28/2.56
11.16/2.37
22.36/6.32
PubMed
5.12/1.87
16.16/3.41
8.21/2.63
2.91/1.61
18.04/3.03
10.45/2.81
22.02/8.19
Computers
5.72/2.52
30.91/7.85
9.19/3.48
3,47/1.31
20.64/9.64
16.05/4.38
28.83/8.69
Photo
5.08/2.63
19.97/5.41
8.69/4.18
3.67/1.66
13.25/7.02
13.96/3.94
24.69/7.37
Chameleon
4.93/0.99
13.11/2.66
7.93/1.62
3.14/0.63
10.92/2.25
10.93/2.41
22.54/4.75
Actor
5.43/1.09
11.94/2.45
8.46/1.71
3.82/0.77
7.99/1.62
11.57/2.35
23.34/5.81
Squirrel
5.61/1.13
22.76/4.91
8,01/1.61
3.41/0.69
38.12/7.78
9.87/5.56
25,58/9.23
Texas
4.58/0.92
9.65/1996
7.83/1.63
3.19/0.65
6.51/1.34
10.45/2.16
23.35/4.81
Cornell
4.83/0.97
9.79/1.99
8.23/1.68
3.25/0.66
5.85/1.22
9.86/2.05
22.23/5.26
Conclusion
This paper proposes BernNet, graph neural network that provides simple and intuitive mechanism for designing and learning an arbitrary spectral filter via Bernstein polynomial approximation. Compared previous methods, BernNet approximate complex filters such band-rejection and comb filters, and can provide better interpretability. Furthermore, the polynomial filters designed and learned by BernNet are always valid. Experiments show that BernNet outperforms SOTA methods in terms of effectiveness on both synthetic and real-world datasets. For future work, an interesting direction is to improve the efficiency of BernNet.
Broader Impact
The proposed BernNet algorithm addresses the challenge of designing and learning arbitrary spectral filters on graphs. We consider this algorithm a general technical and theoretical contribution, without any foresecable specific impacts. For applications in bioinformatics. computer vision, and natural language processing, applying the BernNet algorithm may improve the performance of existing GNN models. We leave the exploration of other potential impacts to future work.
Acknowledgments and Disclosure of Funding
Zhewei Wei was supported in part by National Natural Science Foundation of China (No. 61972401,
No. 61932001 and No. 61832017), by Beijing Outstanding Young Scientist Program NO. by Alibaba Group through Alibaba Innovative Research Program, and by CCF-Baidu Open the Fund (NO.2021PH) (021PP15002000) Zengfeng Huang was supported by National Natural Science Foundation of China Grant No. 61802069, and by Shanghai Science and Technology Commission Grant No. 17JC1420200. Hongteng Xu was supported by Tencent AI Lab Rhino-Bird Joint Research Program. This work is supported by China Unicom Innovation Ecological Cooperation Plan and by Intelligent Social Governance Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Firs" Class" Initiative, Renmin University of China. We also wish acknowledge the support provided and contribution made by Public Policy and Decision- maccing Research Lab of Renmin University of China.
BJJWZYJHO1 RAA00101111000000000
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 Hellinckx. A graph cnn-Istm neural network for short and long-term traffic forecasting based on trajectory data. Transportation Research Part C: Emerging Technologies, 2020.
[4] Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Yanwen Guo. Multi-label image recognition with graph convolutional networks. In CVPR, 2019.
[5] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
[6] 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-TTS, 21(11):48883
2019.
[7] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS, pages 3844-3852, 2016.
[8] Jorge Delgado and Juan Manuel Pena. A linear complexity algorithm for the bernstein basis. In GMP, pages 162-167, 2003.
[9] Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang and Jundong Li. Graph neural networks with adaptive frequency response filter. In CIKM, 2021.
[10] Rida T Farouki. The bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design, 29(6):379-4199 2012.
[11] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In ICLR, 2019.
[12] Dejun Jiang, Zhenxing Wu, Chang Yu Hsich, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingjun Hou. Could graph neural networks learn better molecular representation for drug discovery? a comparison study of seeerittorbbscee and graph-based models. Journal of cheminformatics, 13(1):1-23, 2021.
[13] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[14] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
[15] Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In NeuriPS, 2019.
[16] Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. Transactions Signal Processing, 67(1)977-09, 2018.
[17] Chang Li and Dan Goldwasser. Encoding social information with graph convolutional networks forpolitical perspective detection news media. In ACL, 2019.
[18] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In ICLR, 2018.
[19] Meng Liu, Hongyang Gao, and Shuiwang Towards deeper graph neural networks, In KDD, 2020.

---

[20] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-basee recommendations on styles and substitutes. SIGIR, 2015.
[21] Sunil K Narang, Akshay Gadde, and Antonio Ortega. Signal processing techniques for interpo- lation in graph structured data. In ICASSP. IEEE, 2013.
[22] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
[23] Victoria Powers and Bruce Reznick. Polynomials that are positive on an interval. Transactions of the American Mathematical Sociery, 352(10):4677-45) 4692, 2000.
[24] Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong. Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In KDD, 2018.
[25] Prakash Chandra Rathi, R Frederick Ludlow, and Marcel L Verdonk. Practical high-quality electrostatic potential surfaces for drug discovery using graph-convolutional deep neural network. Journal of medicinal chemistry, 63(16))8778-8790, 2019.
[26] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9()xcnab014, 2021.
[27] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. magazine, 29(3):93 93, 2008.
[28] Daniel Spielman. Spectral and algebraic graph theory. Yale lecture notes, draft of December, 4, 2019.
[29] 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.
[30] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018
[31] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
[32] Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. Session-based recommendation with graph neural networks. In AAAI, 2019.
[33] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
[34] Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning. In IJCAI, 2019.
[35] Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. In ICLR, 2018
[36] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML., 2018.
[37] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICMI., pages 40-48. PMLR, 2016.
[38] 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.
[39] Long Zhao, Xi Peng, Yu Tian, Mubbasir Kapadia, and Dimitris Metaxas. Semantic graph convolutional networks for 3d human pose regression. In CVPR, 2019.
12

---

[40] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In NeurIPS, 2004.
[41] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In WWW, 2021.
13


Reviews:
[{"review_id": "sUG1fHq0hn", "reviewer": "Reviewer_VEJH", "summary": "The authors propose BernNet, which uses Bernstein polynomial basis to learn graph filters. From extensive experiments and theoretical reasoning, the authors demonstrate that BernNet is favored over baselines with a similar idea such as GPR-GNN and ChebyNet.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "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": "Strengths:\n\n(+) The theoretical motivation of using the Bernstein basis is neat and inspiring.\n\n(+) The synthetic experiments on the ability of BernNet to learn arbitrary graph filters well support its validity.\n\n(+) The paper is well written.\n\n(+) The higher computational complexity of BernNet over simpler models such as GPR-GNN is clearly stated. So, the performance-complexity trade-off is clear to the readers.\n\nMinor Weakness:\n\n(-) Do not compare with the other popular polynomial basis such as Chebyshev (different from ChebyNet), Legendre. I understand that they might not have the same good properties as Bernstein, but some synthetic experiments would be appreciated.\n\nDetail comments:\n\nOverall, I like the main idea of this paper. The motivation of why we should use Bernstein basis is clear and neat. The synthetic experiments on learning filters for images are interesting and convincing. Although the model itself just changes monomial basis in GPR-GNN to Bernstein basis, the idea and theoretical reasoning behind it is profound.\n\nStill, I think some minor things can further improve the current manuscript. The authors clearly show that it is reasonable to consider the non-negative constraint and thus Bernstein basis becomes a great choice. However, when it comes to polynomial approximation the other popular polynomial basis should also be considered, such as Chebyshev and Legendre. Note that using Chebyshev basis in GPR-GNN is not the same as ChebyNet. I think the current manuscript can be even more solid if such an experiment can be done.\n\nOriginality: Great. Although the model itself does not differ a lot, the idea and motivation behind it are inspiring.\n\nQuality: Both theoretical reasoning and experiments are convincing.\n\nClarity: The paper is well written. Maybe the importance of the non-negative graph filters section can be further emphasized.\n\nSignificance: This work has moderate significance.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations on computational complexity are addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "eeRokv89vI", "reviewer": "Reviewer_UYuG", "summary": "This paper proposes BernNet, a novel graph neural network with theoretical support that provides a simple but effective scheme for designing and learning arbitrary graph spectral filters. The key property of BernNet is that 1) any valid polynomial filers that maps [0,2] to [0,1] can always be expressed by a BernNet, and 2) the filters learned by our BernNet are always non-negative. The experiments demonstrate that BernNet can learn complex spectral filters, such as band-rejection and comb filters, and it achieves superior performance in real-world graph modeling tasks. Overall, the motivation is clear and the idea is interesting. Technical contributions are clearly shown with both theoretical and empirical evidence. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "", "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": "This work is mostly well-written with informative content and new ideas that are worth publishing.  \n\nStrengths:\n\n1. The use of the Bernstein basis to approximate an arbitrary graph filter is an exciting idea. \n\n2. The Bernstein basis has higher interpretability and controllability than the Chebyshev basis since its coefficients directly match the filter values. \n\n3. The authors demonstrate that any non-negative polynomial filter can be expressed using a non-negative linear combination of the Bernstein basis, distinguishing Bernstein from other learnable GNNs (e.g. ChebNet, GPR). \n\n4. The experiments reveal some intriguing findings. BernNet, for example, learns an MLP from the Actor dataset, which seems to outperform other advanced GNN models.\n\nWeakness:\n\n1. The technical section of the paper is relatively dense, which may be difficult for non-experts in GNN to understand. \n\n2. From the standpoint of graph optimization, the authors justify the non-negative feature of polynomial filters. While this motivation makes perfect sense, it appears that a valid filter has to be non-negative by definition.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors addressed all these aspects.\n\nDescribe the limitations of your work? [Yes] BernNet is quadratic dependent on K.\n\nAny potential negative societal impacts of this work? [Yes] see Section 7 [Broader Impact]", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "HD-F6o6Vyz", "reviewer": "Reviewer_ZSJK", "summary": "This paper proposes a new graph neural network (GNN) architecture whose convolutional layer is capable of learning spectral graph filters of arbitrary characteristics via Bernstein approximation. Under the constraint of positive filter response, the authors show that the polynomial which approximates the solution to a generalised graph-based optimisation necessarily has the form of a non-negative linear combination of Bernstein basis, which justifies the proposed GNN convolutional layer. Experimental results demonstrate that the proposed scheme can learn complex filters and achieve competitive results on a number of benchmark datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "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": "This paper proposes a new GNN architecture following the so-called spectral designs. Compared to spatial designs (e.g. message-pass neural networks), spectral designs have been arguably less extensively studied, and in this sense the paper adds value to the GNN literature. The proposed graph convolutional layer involves a filter based on Bernstein polynomial approximation and has several advantages: 1) it guarantees a non-negative filter response; 2) it can adapt to complex filter characteristics; 3) it is theoretically justified via a graph-based optimisation problem. Despite the rich literature, these are interesting aspects that enrich the design of GNN architectures.\n\nThe paper is generally technically sound and ideas are presented in a clear and coherent manner. The illustrations of the filter response of various types are helpful for understanding the advantage of the proposed approach.\n\nMy main concern is that the advantages of the proposed approach over existing methods that can learn flexible spectral filters (e.g. ChebNet) should be better justified. Theoretically, the authors should explain in more depth why the Bernstein polynomial approximation is potentially better than the one by Chebyshev polynomials. Empirically, in addition to performance metrics, it would be good to compare the learned filters from BertNet and ChebNet (among others) so that their differences can be made more clear.\n\nAnother major issue is that, to increase the expressivity of the proposed filter we need to increase the order of the polynomial K, which increases the computational complexity quadratically. This can in certain scenarios be a significant shortcoming compared to approaches such as ChebNet whose complexity is linear with respect to K.\n\nOverall, I am slightly inclined to recommend acceptance due to the positive aspects of the paper mentioned above, but I would recommend the authors address some of the issues raised in the review during rebuttal.\n\nBelow are additional comments that may help further improve the quality of the paper:\n\nThe statement “none of the existing work supports designing arbitrary spectral filters” is not precise as architectures such as ChebNet can do that in theory.\n\nI am not sure it is the negative spectral response that leads to the over-smoothing of GNNs as claimed by the authors. To me these seem to be separate issues (unless a definitive link can be made which would be welcome).\n\nThe claim that some existing GNNs may not satisfy Constraint 3.1 is in my view not precise as it depends on the range of spectrum. For example, the GCN filter would guarantee non-negative filter response if the eigenvalues are upper bounded by 1, which is the case for scaled or shifted normalised graph Laplacian (which are commonly used in the literature, e.g. in ChebNet). This corresponds to one of the main novelties of the paper and needs to be explained in more depth. Related to a comment above, it would be good to compare the learned filters using BernNet and baselines to demonstrate this point.\n\nThe statement “these methods mainly focus on designing low- or high-pass filters…” is not entirely precise. In theory, as long as the architecture can adapt to data characteristics (e.g. non-smoothness) they can learn flexible filters beyond low- or high-pass ones.\n\nIn 5.1, the formulation of the problem as a regression problem should be explained more clearly (e.g. what do the authors means by using “a mask to cover the edge nodes”?).\n\nSome recent work on learning filters of various spectral characteristics should be discussed in Related Work, for example:\n- https://arxiv.org/abs/2011.10988\n- https://arxiv.org/abs/2104.12840\n\n------post-rebuttal------\n\nI thank the authors for their response and clarifications. I would suggest that the authors further improve their paper based on these discussions. One thing I am not sure about is the authors' claim that it would not be easy to check the filter response from ChebNet. In my view this should be possible to do (see for example a recent work https://arxiv.org/abs/2003.11702) and can further strengthen the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are mainly discussed from the perspective of computational complexity for which running time results have been reported and discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new algorithmic approach for GNNs, and is backed up with both theory and empirical validation. The reviewers are all generally positive and in agreement of its important contributions.
Decision: Accept (Poster)