BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation
Year: 2021

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 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.

heading: 1 Introduction
text: Graph neural networks (GNNs) have received extensive attention from researchers due to their excellent performance on various graph learning tasks such as social analysis [24, 17, 29], drug discovery [12, 25], traffic forecasting [18, 3, 6], recommendation system [38, 32] and computer vision [39, 4]. Recent studies suggest that many popular GNNs operate as polynomial graph spectral filters [7, 13, 5, 16, 2, 35]. Specifically, we denote an undirected graph with node set V and edge set E as G = (V,E), whose adjacency matrix is A. Given a signal x = [x] ∈ Rn on the graph, where n = |V | is the number of nodes, we can formulate its graph spectral filtering operation as∑K
k=0 wkL kx, wk’s are the filter weights, L = I −D−1/2AD−1/2 is the symmetric normalized Laplacian matrix of G, and D is the diagonal degree matrix of A. Another equivalent polynomial filtering operation is ∑K k=0 ckP
kx, where P = D−1/2AD−1/2 is the normalized adjacency matrix and ck’s 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 (NeurIPS 2021).
We can broadly categorize the GNNs applying the above filtering operation into two classes, depending on whether they design the filter weights or learn them based on observed graphs. Some representative models in these two classes are shown below.
• The GNNs driven by designing filters: GCN [13] uses a simplified first-order Chebyshev polynomial, which is proven to be a low-pass filter [1, 31, 34, 41]. APPNP [14] utilizes Personalized PageRank (PPR) to set the filter weights and achieves a low-pass filter as well [15, 41]. GNN-LF/HF [41] designs filter weights from the perspective of graph optimization functions, which can simulate high- and low-pass filters.
• The GNNs driven by learning filters: ChebNet [7] approximates the filtering operation with Chebyshev polynomials, and learns a filter via trainable weights of the Chebyshev basis. GPR-GNN [5] learns a polynomial filter by directly performing gradient descent on the filter weights, which can derive high- or low-pass filters. ARMA [2] 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. In other words, their interpretability is poor. For example, GPR-GNN [5] learns the filter weights wk’s but only proves a small subset of the learnt weight sequences corresponds to low- or high-pass filters. Secondly, the GNNs often design their filters empirically or learn the filter weights without any necessary constraints. As a result, their filter weights often have poor controllability. For example, GNN-LF/HF [41] designs its filters with a complex and non-intuitive 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 [5] or ChebNet [7] have a chance to be ill-posed as well.
To overcome the above issues, we propose a novel graph neural network called BernNet, which provides an effective algorithmic framework for designing and learning arbitrary graph spectral filters. As illustrated in Figure 1, for an arbitrary spectral filter h : [0, 2] 7→ [0, 1] over the spectrum of the symmetric normalized Laplacian L, our BernNet approximates h by a K-order Bernstein polynomial approximation, i.e., h(λ) = ∑K k=0 θkb K k (λ). The non-negative coefficients {θk}Kk=0 of the Bernstein basis {bKk (λ)}Kk=0 work as the model parameter, which can be interpreted as h(2k/K), k = 0, . . . ,K (i.e., the filter values uniformly sampled from [0, 2]). By designing or learning the θk’s, we can obtain various spectral filters, whose filtering operation can be formulated as ∑K k=0 θk 1 2K ( K k ) (2I − L)K−kLkx, where x is the graph signal. We further demonstrate the rationality of our BernNet from the perspective of graph optimization — any valid polynomial filers, i.e., those polynomial functions mapping [0, 2] 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-pass, etc.), and 2) BernNet achieves superior performance on real-world datasets.

heading: 2 BernNet

heading: 2.1 Bernstein approximation of spectral filters
text: Given an arbitrary filter function h : [0, 2] 7→ [0, 1], let L = UΛUT denote the eigendecomposition of the symmetric normalized Laplacian matrix L, where U is the matrix of eigenvectors and Λ = diag[λ1, ..., λn] is the diagonal matrix of eigenvalues. We use
h(L)x = Uh(Λ)UTx = Udiag[h(λ1), ..., h(λn)]UTx (1)
to denote a spectral filter on graph signal x. The key of our work is approximate h(L) (or, equivalently, h(λ)). 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 function f(t) on t ∈ [0, 1], the Bernstein polynomial approximation (of order K) for f is defined as
pK(t) :=
K∑
k=0
θk · bKk (t) = K∑
k=0
f
( k
K
) · ( K
k
) (1− t)K−ktk. (2)
Here, for k = 0, ...,K, bKk (t) = ( K k ) (1− t)K−ktk is the k-th Bernstein base, and θk = f( kK ) is the function value at k/K, which works as the coefficient of bKk (t). Lemma 2.1 ( [10]). Given an arbitrary continuous function f(t) on t ∈ [0, 1], let pK(t) denote the Bernstein approximation of f(t) as defined in Equation (2). We have pK(t)→ f(t) as K →∞.
For the filter function h : [0, 2] 7→ [0, 1], we let t = λ2 and f(t) = h(2t), so that the Bernstein polynomial approximation becomes applicable, where θk = f(k/K) = h(2k/K) and bKk (t) = bKk ( λ 2 ) = ( K k ) (1 − λ2 )K−k(λ2 )k for k = 1, ...,K. Consequently, we can approximate h(λ) by pK(λ/2) = ∑K k=0 θk ( K k ) (1 − λ2 )K−k ( λ 2 )k = ∑K k=0 θk 1 2K ( K k ) (2 − λ)K−kλk, and Lemma 2.1 ensures that pK(λ/2)→ h(λ) as K →∞. Replacing {h(λi)}ni=1 with {pK(λi/2)}ni=1, we approximate the spectral filter h(L) in Equation (1) as Udiag[pK(λ1/2), ..., pK(λn/2)]UT and derive the proposed BernNet. In particular, given a graph signal x, the convolutional operator of our BernNet is defined as follows:
z = Udiag[pK(λ1/2), ..., pK(λn/2)]UT︸ ︷︷ ︸ BernNet x =
K∑
k=0
θk 1
2K
( K
k
) (2I− L)K−kLkx (3)
where each coefficient θk can be either set to h(2k/K) to approximate a predetermined filter h, or learnt from the graph structure and signal in an end-to-end fashion. As a natural extension of Lemma 2.1, our BernNet owns the following proposition. Proposition 2.1. For an arbitrary continuous filter function h : [0, 2] → [0, 1], by setting θk = h(2k/K), k = 0, . . . ,K, the z in Equation (3) satisfies z→ h(L)x as K →∞.
Proof. According to the above derivation, we have pK(λ/2) = ∑K k=0 θk ( K k ) (1− λ2 )K−k ( λ 2 )k =∑K
k=0 θk 1 2K ( K k ) (2 − λ)K−kλk, and Lemma 2.1 ensures that pK(λ/2) → h(λ) as θk = h(2k/K)
and K →∞. Consequently, we have
z = Udiag[pK(λ1/2), ..., pK(λn/2)]UTx→ Udiag[h(λ1), ..., h(λn)]UTx = h(L) as θk = h(2k/K) and K →∞.

heading: 2.2 Realizing existing filters with BernNet.
text: As shown in Proposition 2.1, our BernNet 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.
Note that even for those non-continuous spectral filters, e.g., the impulse low/high/band-pass filters, our BernNet can also provide good approximations (with sufficient large K).
• Impulse low-pass filter h(λ) = δ0(λ).† We set θ0 = 1 and θk = 0 for k 6= 0, and pK( λ 2 ) = (1− λ2 )K . Accordingly, the BernNet becomes 12K (2I−L)K , deriving anK-layer
linear low-pass filter.
• Impulse high-pass filter h(λ) = δ2(λ). We set θK = 1 and θk = 0 for k 6= K, and pK( λ 2 ) = ( λ 2 ) K . The BernNet becomes 1 2K LK , i.e., an K-layer linear high-pass filter. • Impulse band-pass filter h(λ) = δ1(λ). Similarly, we set θK/2 = 1 and θk = 0 for k 6= K/2, and pK(λ2 ) = ( K K/2 ) (1− λ/2)K/2(λ/2)K/2. The BernNet becomes 1 2K ( K K/2 ) (2I−
L)K/2LK/2, which can be explained as stacking a K/2-layer linear low-pass filter and a K/2-layer linear high-pass filter. Obviously, K should be an even number in this case.
Table 1 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 λ ≈ 2kK by using a large or small θk because each Bernstein base bKk (λ) corresponds to a “bump” located at 2k K . This property provides useful guidance when designing filters, which enhances the interpretability of our BernNet.

heading: 2.3 Learning complex filters with BernNet
text: Besides designing the above typical filters, our BernNet can express more complex filters, such as band-pass, band-rejection, comb, low-band-pass filters, etc. Moreover, given the graph signals before and after applying such filters (i.e., the x’s and the corresponding z’s), our BernNet can learn their approximations in an end-to-end manner. Specifically, given the pairs {x, z}, we learn the coefficients {θk}Kk=0 of the BernNet by gradient descent. More implementation details can be found at the experimental section below. Figure 2 illustrates the four complex filters and the approximations we learned (The low-band pass filter is h(λ) = I[0,0.5](λ) + exp (−100(λ− 0.5)2)I(0.5,1)(λ) + exp (−50(λ− 1.5)2)I[1,2](λ), where IΩ(λ) = 1 when λ ∈ Ω, otherwise IΩ(λ) = 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 δx(λ) = 1 if λ = x, otherwise δx(λ) = 0

heading: 3 BernNet in the Lens of Graph Optimization
text: 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.

heading: 3.1 A generalized graph optimization problem
text: Given a n-dimensional graph signal x, we consider a generalized graph optimization problem
min z f(z) = (1− α)zT γ(L)z + α‖z− x‖22 (4)
where α ∈ [0, 1) is a trade-off parameter, z ∈ Rn 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, γ(·) operates on the spectral of L, and we have γ(L) = Udiag[γ(λ1), ..., γ(λn)]UT . We can model the polynomial filtering operation of existing GNNs with the optimal solution of Equation (4). For example, if we set γ(L) = L, then the optimization function (4) becomes f(z) = (1− α)zTLz + α‖z− x‖22, a well-known convex graph optimization function proposed by Zhou et al. [40]. f(z) takes the minimum when the derivative ∂f(z)∂z = 2(1−α)Lz+2α (z− x) = 0, which solves to
z∗ = α (I− (1− α)(I− L))−1 x = ∞∑
k=0
α(1− α)k (I− L)k x = ∞∑
k=0
α(1− α)kPkx.
By taking a suffix sum ∑K k=0 α(1 − α)kPkx, we obtain the polynomial filtering operation for APPNP [14]. Zhu et al. [41] further show that GCN [13], DAGNN [19], 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 γ(L) = etL − I, a heat kernel with t as the temperature parameter. Then f(z) takes the minimum when the derivative ∂f(z)∂z = ( etL − I ) z + z − x = 0, which solves to
z∗ = e−tLx = e−t(I−P)x = ∞∑
k=0
e−t tk
k! Pkx.
By taking a suffix sum ∑K k=0 e −t tk k! P
kx, we obtain the polynomial filtering operation for the heat kernal based GNN such as GDC [15] and GraphHeat [34].

heading: 3.2 Non-negative constraint on polynomial filters
text: A natural question is that, does an arbitrary energy function γ(L) correspond to a valid or ill-posed spectral filter? Conversely, does any polynomial filtering operation ∑K k=0 wkL
kx correspond to the optimal solution of the optimization function (4) for some energy function γ(L)?
As it turns out, there is a “minimum requirement” for the energy function γ(L); γ(L) has to be positive semidefinite. In particular, if γ(L) is not positive semidefinite, then the optimization
function f(z) is not convex, and the solution to ∂f(z)∂z = 0 may corresponds to a saddle point. Furthermore, without the positive semidefinite constraint on γ(L), f(z) may goes to −∞ as we set z to be a 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 ∑K k=0 wkL
kx should look like. Recall that we assume γ(L) = Udiag[γ(λ1), ..., γ(λn)]UT . By the positive semidefinite constraint, we have γ(λ) ≥ 0 for λ ∈ [0, 2]. Since the objective function f(z) is convex, it takes the minimum when ∂f(z)∂z = 2(1− α)γ(L)z + 2α (z− x) = 0. Accordingly, the optimum z∗ can be derived as
α (αI + (1− α)γ(L))−1 x = Udiag [
α
α+ (1− α)γ(λ1) , ...,
α
α+ (1− α)γ(λn)
] UTx. (5)
Let h(λ) = αα+(1−α)γ(λ) denote the exact spectral filter, and g(λ) = ∑K k=0 wkλ
k denote a polynomial approximation of h(λ) (e.g. the suffix sum of h(λ)’s taylor expansion). Since γ(λ) ≥ 0 when λ ∈ [0, 2], we have 0 ≤ h(λ) ≤ αα+(1−α)·0 = 1 for λ ∈ [0, 2]. Consequently, it is natural to assume the polynomial filter g(λ) = ∑K k=0 wkλ
k also satisfies 0 ≤ g(λ) ≤ 1. Constraint 3.1. Assuming the energy function γ(L) is positive semidefinite, a polynomial filter g(λ) = ∑K k=0 wkλ k approximating the optimal solution to Equation (4) has to satisfy
0 ≤ g(λ) = ∑K
k=0 wkλ
k ≤ 1, ∀ λ ∈ [0, 2]. (6)
While Constraint 3.1 seems to be simple and intuitive, some of the existing GNN may not satisfies this constraint. For example, GCN uses z = Px = (I− L) x, which corresponds to a polynomial filter g(λ) = 1− λ that takes negative value when λ > 1, violating Constraint 3.1. As shown in [31], the renormalization trick P̃ = (I + D)−1/2 (I + A) (I + D)−1/2 shrinks the spectral and thus reliefs the problem. However, g(λ) may still take negative value as the maximum eigenvalue of L̃ = I− P̃ is still larger than 1.

heading: 3.3 Non-negative polynomials and Bernstein basis
text: Constraint 3.1 motivates us to design polynomial filters g(λ) = ∑K k=0 wkλ
k such that 0 ≤ g(λ) ≤ 1 when λ ∈ [0, 2]. The g(λ) ≤ 1 part is trivial, as we can always rescale each wk by a factor of∑K
k=0 |wk|2k. The g(λ) ≥ 0 part, however, requires more elaboration. Note that we can not simply set wk ≥ 0 for each k = 0 . . . ,K, since it is shown in [5] that such polynomials only correspond to low-pass filters.
As it turns out, the Bernstein basis has the following nice property: a polynomial that is non-negative on a certain interval can always be expressed as a non-negative linear combination of Bernstein basis. Specifically, we have the following lemma. Lemma 3.1 ([23]). Assume a polynomial p(x) = ∑K k=0 θkx
k satisfies p(x) ≥ 0 for x ∈ [0, 1]. Then there exists a sequence of non-negative coefficients θk, k = 0, . . . ,K, such that
p(x) =
K∑
k=0
θkb K k (x) =
K∑
k=0
θk
( K
k
) (1− x)K−kxk
Lemma 3.1 suggests that to approximate a valid filter, the polynomial filter g(λ) has to be a nonnegative linear combination of Bernstein basis. Specifically, by setting x = λ/2, the filter g(λ) that satisfies g(λ) ≥ 0 for λ ∈ [0, 2] can be expressed as
g(λ) := p
( λ
2
) = K∑
k=0
θk 1
2K
( K
k
) (2− λ)K−kλk.
Consequently, any valid polynomial filter that approximate the optimal solution of (4) with positive semidefinite energy function γ(L) has to take the following form: z = ∑K k=0 θk 1 2K ( K k ) (2I − L)K−kLkx. This observation motivates our BernNet from the perspective of graph optimization — any valid polynomial filers, i.e., the g : [0, 2] 7→ [0, 1], can always be expressed by BernNet, and accordingly, the filters learned by our BernNet are always valid.

heading: 4 Related Work
text: Graph neural networks (GNNs) can be broadly divided into spectral-based GNNs and spatial-based GNNs [33].
Spectral-based 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 a 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 of Auto-Regressive Moving Average filters [21]. AdaGNN [9] learns simple filters across multiple layers with a single parameter for each feature channel at each layer. As aforementioned, these methods mainly focus on designing low- or high-pass filters or learning filters without any constraints, which may lead to misspecified even ill-posed filters.
On the other hand, spatial-based GNNs directly propagate and aggregate graph information in the spatial domain. From this perspective, GCN [13] can be explained as the aggregation of the one-hop neighbor information on the graph. GAT [30] uses the attention mechanism to learn aggregation weights. Recently, Balcilar et al. [1] 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 of the proposed BernNet, which can learn arbitrary non-negative spectral filters from real-world graph signals.

heading: 5 Experiments
text: In this section, we conduct experiments to evaluate BernNet’s capability to learn arbitrary filters as well as the performance of BernNet on real datasets. All the experiments are conducted on a machine with an NVIDIA TITAN V GPU (12GB memory), Intel Xeon CPU (2.20 GHz), and 512GB of RAM.

heading: 5.1 Learning filters from the signal
text: We conduct an empirical analysis on 50 real images with the resolution of 100×100 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 [1], we regard each image as a 2D regular 4-neighborhood grid graph. The graph structure translates to an 10, 000× 10, 000 adjacency matrix while the pixel intensity translates to a 10, 000-dimensional signal vector.
For each of the 50 images, we apply 5 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(−10λ2) to the spectral domain L = Udiag [λ1, . . . , λn] U> means applying Udiag [ exp(−10λ21), . . . , exp(−10λ2n) ] U> to the graph signal. Figure 3 shows the one of the input image and the corresponding filtering results.
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 [13], GAT [30], GPR-GNN [5], ARMA [2] and ChebNet [7]. To ensure fairness, 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 to ensure they have similar parameters. Following [1], we discard any regularization or dropout and simply force the GNN to learn the input-output relation. For all models, we set the maximum number of epochs to 2000 and stop the training if the loss does not drop for 100 consecutive times and use Adam optimization with a 0.01 learning rate without decay. Models do not use the position information of the picture pixels. We use a mask to cover the edge nodes of the picture, so the problem can be regarded as a simple regression problem. For BernNet, we use a two-layer model, with each layer sharing the same set of θk for k = 0, . . . ,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 [11]. The more detailed experiments setting can be found in the Appendix.
Table 2 shows the average of the sum of squared error (lower the better) and the R2 scores (higher the better). We first observe that GCN and GAT can only handle low-pass filters, which concurs with the theoretical analysis in [1]. GPR-GNN, ARMA and ChebNet can learn different filters from the signals. However, BernNet consistently outperformed these models by a large margin on all tasks in terms of both metrics. We attribute this quality to BernNet’s ability to tune the coefficients θk’s, which directly correspond to the uniformly sampled filter values.

heading: 5.2 Node classification on real-world datasets
text: We now evaluate the performance of BernNet against the competitors on real-world datasets. Following [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 webpage graphs Texas and Cornell from WebKB‡ [22]. These 5 datasets are heterophilic datasets on which connected nodes tend to have different labels. We summarize the statistics of these datasets in Table 3.
Following [5], we perform full-supervised node classification task with each model, where we randomly split the node set into train/validation/test 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 6 baseline models: MLP, GCN [13], GAT [30], APPNP [14], ChebNet [7], and GPR-GNN [5]. 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. For other models, we use the corresponding Pytorch Geometric library implementations [11]. For BernNet, we
‡http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb/
use the following propagation process:
Z =
K∑
k=0
θk 1
2K
( K
k
) (2I− L)K−kLkf (X) , (7)
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 or GPR-GNN. The only difference is that we 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, we optimal leaning rate over {0.001, 0.002, 0.01, 0.05} and weight decay {0.0, 0.0005}. More detailed experimental settings are discussed in Appendix.
We use the micro-F1 score with a 95% confidence interval as the evaluation metric. The relevant results are summarized in Table 4. Boldface letters indicate the best result for the given confidence interval. We observe that BernNet provides the best results on seven out of the ten datasets. On the 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 4 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 at least 1% on these two datasets, it may suggest that comb-alike filters are necessary for Chameleon and Squirrel. Figure 5 shows the Coefficients θk learnt from real-world datasets by BernNet. When comparing Figures 4 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 5. BernNet is slower than other methods due to its quadratic dependence on the degree K. However, compared to the SOTA method GPRGNN, the margin is generally less than 2, which is often acceptable in practice. In theory, both ChebNet [7] and GPR-GNN [5] are linear time complexity related to propagation stepK, but BernNet is quadratic time complexity related to K. Delgado et al. [8] 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 a problem worth studying in the future.

heading: 6 Conclusion
text: This paper proposes BernNet, a graph neural network that provides a simple and intuitive mechanism for designing and learning an arbitrary spectral filter via Bernstein polynomial approximation. Compared to previous methods, BernNet can approximate complex filters such as 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 foreseeable 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. BJJWZYJH012019100020098, by Alibaba Group through Alibaba Innovative Research Program, and by CCF-Baidu Open the Fund (NO.2021PP15002000). 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-First Class” Initiative, Renmin University of China. We also wish to acknowledge the support provided and contribution made by Public Policy and Decision-making Research Lab of Renmin University of China.

Review summaries:
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.

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.