Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective
Authors: Muhammet Balcilar
Guillaume Renton
Pierre Héroux
Benoit Gaüzère
Sébastien Adam
Paul Honeine
Venue: ICLR 2021 Poster (2021)
Keywords: Graph Neural Networks
Spectral Graph Filter
Spectral Analysis

Abstract: In the recent literature of Graph Neural Networks (GNN), the expressive power of models has been studied through their capability to distinguish if two given graphs are isomorphic or not. Since the graph isomorphism problem is NP-intermediate, and Weisfeiler-Lehman (WL) test can give sufficient but not enough evidence in polynomial time, the theoretical power of GNNs is usually evaluated by the equivalence of WL-test order, followed by an empirical analysis of the models on some reference inductive and transductive datasets. However, such analysis does not account the signal processing pipeline, whose capability is generally evaluated in the spectral domain. In this paper, we argue that a spectral analysis of GNNs behavior can provide a complementary point of view to go one step further in the understanding of GNNs. By bridging the gap between the spectral and spatial design of graph convolutions, we theoretically demonstrate some equivalence of the graph convolution process regardless it is designed in the spatial or the spectral domain. Using this connection, we managed to re-formulate most of the state-of-the-art graph neural networks into one common framework. This general framework allows to lead a spectral analysis of the most popular GNNs, explaining their performance and showing their limits according to spectral point of view. Our theoretical spectral analysis is confirmed by experiments on various graph databases. Furthermore, we demonstrate the necessity of high and/or band-pass filters on a graph dataset, while the majority of GNN is limited to only low-pass and inevitably it fails.

Published as a conference paper at ICLR 2021
ANALYZING THE EXPRESSIVE POWER OF GRAPH NEURAL NETWORKS IN A SPECTRAL PERSPECTIVE
Muhammet Balcilar; Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, Paul Honeine Normandy University, LITIS Lab, University of Rouen Normandy, INSA Rouen Normandie Rouen, 76000, France
ABSTRACT
In the recent literature of Graph Neural Networks (GNN), the expressive power of models has been studied through their capability distinguish if two given graphs are isomorphic or not. Since the graph isomorphism problem is NP-intermediate, and Weisfeiler-Lehmaal (WL.) test can give sufficient but not enough evidence polynomial time, the theoretical power of GNNs is usually evaluated by the equiv- alence of WL-test order, followed by an empirical analysis of the models on some reference inductive and transductive datasets. However, such analysis does not account the signal processing pipeline, whose capability is generally evaluated in the spectral domain. In this paper, we argue that a spectral analysis of GNNs behavior can provide a complementary point of view to go one step further in the understanding of GNNs. By bridging the gap between the spectral and spa- tial design of graph convolutions, we theoretically demonstrate some equivalence of the graph convolution process regardless it is designed in the spatial or the spectral domain. Using this connection, we managed to re-formulate most of the late-of-the--e art graph neural networks into one common framework. This general framework allows to lead spectral analysis of the most popular GNNs, explain- ing their performance and showing their limits according to spectral point of view. Our theoretical spectral analysis is confirmed by experiments on various graph databases. Furthermore, we demonstrate the necessity of high and/or band-pass filters on graph dataset, while the majority of GNN is limited to only low-pass and inevitably it fails.
Code available at http://thhcccoomlduuugoggggeepep
INTRODUCTION
Over the last five years, many Graph Neural Networks (GNNs) have been proposed in the literature of geometric deep learning (Veličković et al.) 2018 Gilmer al., 2017; Bronstein al., 2017 Battaglia et al. 22018), in order to generalize the very efficient deep learning paradigm into the world of graphs. This large number of contributions explains a new challenge recently tackled by the community, which consists in assessing the expressive power of GNNs.
In this area of research, there is consensus evaluate the theoretic expressive power of GNNs according to equivalence of Weisfeiler-Lehman (WL) test order (Morris et al. 2019 Xu et al. 2019 Maron et al. 2019b]a) a). Hence, GNNs models are frequently classified as "as powerful as 1-WL" as "as powerful as k-WL". However, this perspective cannot make differences
powerful as 2-WL", between two methods if they are as powerful as the same WL test order. Moreover, it does not always explain success or failure of any GNN on common benchmark datasets.
In this paper, we claim that analyzing theoretically and experimentally GNNs with a spectral point of view can bring new perspective on their expressive power.
So far, GNNs have been generally studied separately as spectral based or as spatial based (Wul et al. 20019] Chami et al. 2020). To the best of our knowledge, Message Passing Neural Networks (MPNNs) (Gilmer et al. 2017) 77 and GraphNets (Battaglia et al. 2018) are the only attempts to merge
mmuhammtthaliiar@@@ee ammillllliiaaammmmoommcmm.

---

Published as a conference paper at ICLR 2021
both approaches in the same framework. However, these models are not able to generalize custom designed spectral filters, as well as the effect of each convolution support in a multi convolution case. The spatial-spectrec connection is also mentioned indirectly in several comerstone studies by Defferrard et al. (2016); Kipf & Welling (0117); Levie et al. (2019). Since the spectral-spatial inter- changeability is missing, they did not propose show spectral behavior of any graph convolution. Recent studies have also attempted to show, for limited number of spatial GNNs, that they act as low-pass filters (NT & Machara 2019 Wu al., 2019a). NT & Machara (2019) concluded that using adjacency induces low-pte pa--ssss effects, while Wu et al. 2019a) studied single spatial GNN's s spectral behavior by assuming adding self-connection changes the given topology of the graph.
In this paper, we bridge the gap between spectral and spatial domains for GNNs. Our first con- tribution consists in demonstrating the equivalence of convolution processes regardless if they are defined as spatial or spectral GNN. Using this connection, we propose new general framework and taxonomy for GNNs as the second contribution. Taking advantage of this equivalence, our third contribution is to provide a spectral analysis of any GNN model. This spectral analysis is another perspective for the analysis of expressive power of GNNs. Our theoretical spectral analysis is con- firmed by experiments on various well-known graph datasets. Furthermore, show the necessity of high and/or band-pass filters in our experiments, while the majority of GNNs are limited to only low-pass filters and thus inevitably fail when dealing with these problems. The code used in this paper is available at
The remainder of this paper is organized as follows. Section 2 introduces convolutional GNNs and presents existing approaches. In Section 3 and Section 4, we describe the main contributions men- tioned above. Section 5 presents series of experiments and results which validate our propositions. Finally, Section 6 concludes this paper.
2 PROBLEM STATEMENT AND STATE OF THE ART
Let G be a graph with n nodes and an arbitrary number of edges. Connectivity is given by the adjacency matrix A (0, |xxx and features defined on nodes by X R with fo the length of feature vectors. For any matrix X, we used X,, X,, and X,, to refer its i-th column vector, j-th row vector and scalar value on (i.j) location, respectively. A graph Laplacian L = D A (or L = I - 1-112 1D/1/22 where D E R is the diagonal degree matrix and I is the identity. Through eigendecomposition, L can be written by L = U diag(A)U where each column of U E R=x= an eigenvector of L, À E RR" gathers the eigenvalues of L and diag(.) function creates a diagonal matrix whose diagonal elements are from given vector. We use superscript to refer same kind variable as base. For instance, (1)) E RR refers node representation on layer I whose feature dimension is fi. A Graph Convolution layer takes the node representation of the previous layer (!- as input and produces a new representation H(), with H0)) X.
2.1 SPECTRAL APPROACHES
Spectral GNNs rely on the spectral graph theory (Chung 1997). In this framework, signals on graphs are filtered using the eigendecomposition of graph Laplacian (Shuman al.) (013). By transposing the convolution theorem to graphs, the spectral filtering in the frequency domain can be defined by Iifit diaag & (A))U' x,, where (b.) is the desired filter function. As consequence, a graph convolution layer in spectral domain can be written by sum of filtered signals followed by an activation function as in (Bruna et al. 2013), namely
ft Udiag( F. DU H!!)) ),(0): Σ
H
for j E S(1))
Here, a is the activation function, p(.) E Bu is the corresponding weight vector to be tuned as used in (Henaff al. 2015) for the single-graph problem known as non-parametrie spectral GNN.
A first drawback is the necessity of Fourier and inverse Fourier transform by matrix multiplication of U and UT, Another drawback occurs when generalizing the approach to multi-graph learning prob- lems. Indeed, the k-th element of the vector F((.)) weights the contribution of the k-th eigenvector to the output. Those weights are not shareable between graphs of different sizes, which means
2

---

Published as a conference paper at ICLR 2021
different length of F2! is needed. Moreover, even though the graphs have the same number of nodes, their eigenvalues will be different their structures differ.
To overcome these issues, few spatially-localizeed filters have been defined such cubic B-spline (Bruna et al., 2013), polynomial and Chebyshev polynomial (Defferrard et al. 2016) and Cayley polynomial parameterization (Levie al. 2019). With such approaches, trainable parameters are
defined by F: F:(1.)) B [W:]]] ..... W
where each column in B IR** is designed as function of eigenvalues, namely Bk.. 4, (A+), where k= = 1,..... denotes eigenvalue index,
1, Ae denotes index of filters and 8e is the number of desired filters. Here, W((,s) E /R////411 is the trainable matrix for the I-th layer's s-th filter's.
2.2 SPATIAL APPROACHES
Spatial GNNs consider an agg operator, which aggregates the neighborhood nodes, and an upd operator, which updates the concerned node as follows:
(1 upd (o (H agg (I :uE)))
where ((v) is the set of neighborhood nodes and go, 91 RaxSi - Raxf4+ trainable models. The choice of agg, upd, 90- 91. and even (w)), determines the capability of model.
The vanilla GNN (known by GIN-O in (Xu et al. 2019) uses the same weights in go and g1. (v)) is the set of connected nodes to v, agg is the sum of all connected node values and upd(x, y) := a + y) where a is elementwise nonlinearity. GCN has the same selection but normalizes features as in (Kipf & Welling 2017). Hamilton et al. (2017) used separated weights in go and 91. which means that two sets of trainable weights are applied self feature and neighbor nodes. Other approaches defined multi neighborhood and used different gi for different kind of neighborhood. For instance, Duvenaud et al. (2015) defined the neighborhood according to node label and/or degree, NNepent et al. (2016) reordered the neighbor nodes and used the same model to neighbors according to their order.
These spatial GNNs use sum or normalized sum over gi in equation 2 Other methods weighted this summation by another trainable parameter, where the weights can be written by the function of node and/or edge features in order to make the convolutions more productive. such as graph attention networks (Veličković al., 2018), MoNet (Monti et al. 2017). GatedGCN (Bresson & Laurent 2018) and SplineCNN (Fey et al. 2018).
BRIDGING SPATIAL AND SPECTRAL GNNS
In this section, we define a general framework which includes most of the well-know GNN mod- els. including euclidean convolution and models which use anisotropic update schema such as in Veličković et al. (2018); Bresson & Laurent 2018).
When upd(æ,) y) = a(r y). agg is sum (or weighted sum) of the defined neighborhood nodes contributions and 9i applies linear transformation, one can trivially show that mentioned spatial GNNs can be generalized as propagation of the node features to the neighboring nodes followed by feature transformation and activation function of the form
0++) o Σ glo) 1
where (()) E RaXR is the s-th convolution support that defines how the node features are prop- agated to the neighboring nodes. Within this generalization, GNNs differ from each other by the choice of convolution supports C(s). This formulation generalizes many different kinds of Graph Convolutions, as well as Euclidean domain convolutions, which can be seen in Appendix with the detailed schema.
Definition 1. A Trainable-support is Graph Convolution Support (+s) with least trainable parameter that can be tuned during training. If C(s) has no trainable parameters, i.e. when the supports are pre-designed, is called fixed-support graph convolution.
3

---

Published as a conference paper at ICLR 2021
In the trainable support supports can be different in each layer, which can be shown by C(!.s) for the s-th support in layer Formally, we can define a trainable support by:
(CU.s) -hs,t ( H E 0,00 A)
where Era shows edge features on layer from node to node if it is available and h(.) is any trainable model parametrized by (s,
Theorem 1. Spectral GNN parameterized with B of entries Bag 2 defined
H
U diag (B [WW ..... w (UTH""
(5)
is a particular case of framework in equation
3 with the convolution kernel set to
(++) = U diag (,(A)UTT.
(6)
The proof can be found in Appendix This theorem is general and covers many well-known
spectral GNNs, such as non-parametric spectral graph convolution (Henaff' et al. 2015), polynomial
parameterization (Defferrard et al. (016)) cubic B-spline parameterization (Bruna et al. 2013). Cay-
leyNet (Levie et al., 2019) and also any custom designed graph convolution. From Theorem one can see that the spatial and spectral GNNs work all the same way. Therefore, Fourier calculations parameterized by B. As consequence of Theorem one can see that the separation of spectral and spatial GNNs is just an interpretation. The only difference the way convolution supports are designed: either in the spectral domain in the spatial one.
not necessary when convolutions
Definition 2. A Spectral-designed graph convolution refers a convolution where supports are written as a function of eigenvalues ( (A) and eigenvectors (U) ofe corresponding graph Lapla- cian (equation 6y. Thus, each convolution support ((a) has the same frequency response 4, (A) over different graphs. Graph convolution out of this definition is called spatial-designed graph convolu- tion.
Corollary 1.1. The frequency profile of any given graph convolution support (()) can be defined in spectral domain by
Φ. (>) = diag (UTT(()))))))))))))
where (.) returns the vector made of the diagonal elements from the given matrix.
The proof of this corollary is given in Appendix This corollary leads to the spectral analysis of
any given graph convolution support, including spatial-designed convolutions. Since the spatial- designed convolutions do not fit into equation 6 U ((*) not diagonal matrix. Therefore, also compute the full frequency profile by Φ. UT UTTTCCC) C(s)U, which includes all eigenvectors pairwise contributions for spatial-designes convolutions.
4 THEORETICAL FREQUENCY RESPONSE OF GRAPH CONVOLUTIONS
This section aims at providing a theoretical understanding of the graph convolution process through an analysis in the spectral domain of existing GNNs. To the best of our knowledge, one has led such an analysis concerning graph convolutions in the literature. This analysis is based on a reformulation of existing graph convolutions in our general framework (equation B}. and based on deriving analytical expressions of 4, (A) (equation 7 in Corollary [.1) for each convolution support of concerned graph convolution process. All proofs are provided Appendices.
The theoretical frequency response of ChebNet (Defferrard et al. 2016) convolutions is given by the following theorem.
Theorem 2. The theoretical frequency response of each support of ChebNet can be defined
2A 1,
21(A) = 1, (2(A)
- - 2x-2(A),
(8)
Amax
where 1 is the vector of ones and Amax is the maximum eigenvalue.
4

---

Published as a conference paper at ICLR 2021
The proof of Theorem 2 is given in Appendix D Since it has no trainable parameter in the sup- ports and all support frequency responses do not depend on the graph, we can classify ChebNet as opectral-desighee fixed
fixed-support support graph convolution.
The theoretical frequency response of CayleyNet (Levie et al. 2019) convolution is given in the following theorem, and its proof is given in Appendix
can be defined as Theorem 3. The theoretical frequecc response of each support of CayleyNer can
1
if==1
2r where h is a trainable scalar and ((x) (atan2(-1,,5) atan2(1,
(A)
cOs( ()(()))) sin( - (
ifs E (2, (2.,,...,2r) if {3,5, ...,,..................... 2r 1}
Since it has trainable parameter h in the supports and all support frequency responses do not depend on the graph, we can classify CayleyNet as
trainable-suppor graph convolution.
GCN Kiip & Welling 2017) uses single convolution support and its theoretical frequency re- sponse is defined approximately in the following theorem, and its proof is given in Appendix Theorem 4. The theoretical frequency response of GCN support can be approximated as (()) 2 1 - Ap/ + 1),
(10)
where p is the average node degree in the graph.
Since its support has trainable parameter but the frequency response is not independent of the graph, we can classify GCN as spatial-designed fixed-support graph convolution.
Graph Isomorphism Network (GIN) defined in Xu et al. (2019) has attracted lot of interests from the community, mostly because of its simple convolution mechanism. has a single convolution support and its theoretical frequency response is given in the following theorem:
Theorem 5, The theoretical frequency response of GIN support can be approximated as
((A) = =
+ +1-A
(11)
P
where is a trainable scalar.
The proof of this theorem is in Appendix G Since its support has trainable parameters but the frequency response depends on the graph structure, we classify GIN as spatial-designed trainable- support graph convolution.
Graph attention networks (GATs) in /Veličković et al. 2018) proposes an application for graph world of the attention mechanism from Vaswani et (2017). Due to the fact that graphs are invariant to the node order, GAT cannot use positional encoding. In addition, instead of considering that all nodes are connected to each other, GAT just assigns attention weights to the node itself and the connected ones according to adjacency (sparse attention). Thus, we can see its convolution support weighted, self loop added adjacency. GAT can be represented in our framework in equation by defining trainable convolution supports as follows:
(Cll.))
E0,u
(12)
"EEN(O)) Cr.k
where 6n = exp (a(())))) w(.)) H.! w((l))))) ( and (l.s) is another trainable weight. Con- volution support will be calculated from node v to each element of (u)), which shows the self- connection added neighborhood. Thus, we classify GAT as spatial-designed trainable-supee support graph neural network in our framework. Since convolution supports are function of connected node features, a theoretical frequency response is not possible to formulate.All studied models are sum- marised in [
5 EXPERIMENTAL RESULTS
This section is dedicated to empirical spectral analysis of existing GNNs on some certain graphs to validate the theoretical results and also performance analysis of these GNNs on benchmark graph
5

---

Published as a conference paper at ICLR 2021
Table 1: Summary of the studied GNN models.
Design
Support Type
Convolution Matrix
Frequency Resporse
МL.P
Spectral
Fixed
4(2) =
Spatial
D A.-
4(A) = A7/(7+11
GIN
Spatial
Triiable
C = +
4(A) = + +1
GAT
Spatial
Traiable
Cn, cs.u/ Exc((()) Cv.k
NA
(0) =1
(1 =1
CayleyNer
Spectral
Trainalle
((ar) Re(a(h()))
92-(A) cos(r
C(2r+1) Re((p((())))
42 sin(r((hA))
CO)
(1(A)
ChebNet
Spectral
( Daux
(2 =2A/Amux
( c(1-1) ((l-2)
(A) 202(A)0.-1(A) 2x-2(A)
p(z) (a 1///22
dataset to demonstrate the necessity of having various frequency responses convolution supports. The implementation and the introduced datasets publicly available
5.1 SPECTRAL ANALYSIS RESULTS
All empirical analyses are based on obtaining convolution supports matrix for certain GNN model, followed by equation 7 to obtain the frequency response. In our analysis, we used three graphs independently: the first is ID signal encoded regular circular line graph with 1001 nodes; the others are the well-known Cora and CiteSeer graphs with 2708 and 3327 nodes respectively (Yang al. 2016). Besides, used 2 different collections of graph datasets, ENZYMES and PROTEIN, which have 600 and 1113 graph respectively (Kersting et al. 2016). The details of the graphs can be found in Appendix
Magnitude
Magnitude
E Sigervalttes
Elgenvalua
2nd hernel
lot hernel
4-th lorrel
3-rd kornel
2-nd korne!
1-st hernel
3rd bezuel
G-th harnal
5-th kernel
4thh leruel
7-th kornel
5th lornel
(a) First ChebNet supports
(b) First 7 CayleyNet supports
Figure Frequency profiles (+.(
Since ChebNet and CayleyNet are spectral-designet their frequency responses do change for different graphs. They are presented in Figure for first 5 and 7 supports respectively. The results in the theoretical analyses in Theorem [ and Theorem 3 The full frequency profiles not illustrated because they consist of zeros outside the diagonal. Analyzing the frequency profile of ChebNet. one can argue that the convolutions mostly cover the spectrum. However, none of the kernels focuses some certain parts of the spectrum. As example, the second kernel is mostly low-pass and high-pass filter and stops the middle band, while the third one passes very high, very low and middle bands, but stops almost first and third quarter of the spectrum. Therefore, if the relation between input-output pairs can be figured out by just a low-pass, high-pass or some specific

---

Published as a conference paper at ICLR 2021
band-pass filter, high number of convolution kernels is needed. However, in the literature, only or kernels are generally used in experiments (Defferrard et al., 2016 Kipf & Welling 2017).
The scale parameter h in CayleyNet affects the x-axis scaling, but does not change the global shape. When h = 1, frequency profiles can be defined within the range [0, 2] (because Amax three test graphs). If h 1.5, the frequency profile be defined till 1.5Xmax and rescale axis label from [0,3] to [0, in original range. Learning the scaling of eigenvalues may seem advantageous. However, induces extra computational cost in order to calculate the new convolution supports in every learning epoch. In addition, similarly to ChebNet, CayleyNet does have any band specific convolutions, even when considering different scaling factors.
in all 3 in Figure
Magubaiis
Magustule
Magalbale
1D graph
Eigenraliuer
Cora
Eigenvales
Eigntraoow
Citeseer
(a) GCN frequency profiles
(b) GIN ID
(c) GIN CiteSeer
Figure 2: Frequency profiles of GCN ID, Cora, CiteSeer graph and GIN on ID and CiteSeer graph with e 1,0,-1, -1,-2
When the given graph is regular graph where each node degree is the same (2 for 1D graph case), theoretical frequency responses become certain as seen in Figure [ in blue for GCN and Figure (2p for GIN. When
2, ID graph's 's (p 2) frequency responses of GCN and GIN are the same except scaling factor as seen in blue Figure 2h yellow in Figure 2p. However in realistic graphs, both GIN and GCN are not spectral -essinel their frequency responses differ for different graphs. As Theorem 4 and Theorem S demonstrate, GCN's and GIN's frequency responses depend on the average node degree. GCN's cut-off frequency decrease by increasing the p while p acts as scaling factor GIN's frequency response. This analysis leads us understand that GCN works as low- pass filter and does not cover the whole spectrum. This approach not able to learn relations that can be represented by high-pass band- -adds filtering. Hence, even though gives very good results on a single graph node classification problem Kipf & Welling (2017). it may fail for problems where discriminant information lies in particular frequency bands. Therefore, such an approach can be considered as problem specific.
In order create GIN's convolution support seems advantageous. But, since it is not spectral-designed, there is no guarantee that it has exactly the same spectral profiles for different graphs. Besides, its low-pass shape (where is high) is a linearly decreasing function, thus it is not strong low-pass that gen- erally natural graph problems need. Using more stacked layer may be solution. In addition, this convolution cannot focus on some certain bands if the problem needs.
variations between low-pass high-past pash, having trainable parameter in
Since the GAT's convolution supports are function of connected nodes feature, frequency profiles cannot be directly computed similarly to previous ones. Thus, we proposed to obtain frequency response by two ways, one is the expected frequency responses among simulations, the other the frequency responses of trained model for any specific graph learning problem.
We calculated the expected frequency responses of GAT convolution supports on Cora graph by simulation of randomly created 240 possible attention weights. The expected value of simulated support's frequency response and its standard deviation are shown in Figure 3h. This result gives an idea about the capability of the model spectral domain, without being the true learned convolution support. In addition, the simulation is just for the first layer, because the first layer's 's input is known without learning. Besides, attention head's 's in all layers for all the graphs of ENZYMES and PROTEINS datasets respectively (in our model, there
also provide in FigureBb-c the frequency responses of all learned GAT
GNN layer consisting of 25 attention head). Since there is significant

---

Published as a conference paper at ICLR 2021
Sreadard Bavtakko
Magnitudo
Moquitule
Maputook
Bigenvalnes
Eigruvaloe
Bigenvaluc
(a) Expected frequency response (b) Heat density map of learned fre- (c) Heat density map of learned fre- quency response on ENZYMES
from Simulation on Cora
quency response on PROTEINS
Figure 3: Frequency profiles of GAT
differences between frequency responses in different layer or different attention head, we stacked all together in the same heat map.
As one can see, the mean standard frequency profile has a similar shape than those of GCN and GIN- O which are methods that use self-looped added (normalized or not) adjacency matrix as convolution support. Variations on the frequency profile induce more variations output signal when compared to GCN and GIN-O. However, the variation on frequency profile might not be sufficient in problems that need some specific band-pass filters.
5.2 PERFORMANCE ANALYSIS OF GNNS
First, our goal was to assess empirically the ability of GNN models to produce the desired frequency effects given graph signals. With the conducted experiments detailed in Appendix [ we can out- line the empirical results as follows. GCN and GAT can produce low-pass effects but not band-pass or high-pass, while GAT has better variation frequency profile; these empirical results corrobo- rate the theoretical analysis of this paper, namely Theorem 4and and Section 5.] Thanks to its trainable parameter e, GIN can do better on producing low-pass and high-pass effects, but not band-pass, as demonstrated by Theorem 5 However, the opectral-designn ChebNet always outperformed the rest with huge margin, which not surprising.
Secondly, we measured the generalization capability of the GNN model for graph classification task as a toy example where the graph classes depend on the frequency of the signal on the graph. The conducted experiments are described in Appendix[] [ Again, we seen that GCN and GAT performed worse than GIN, because of their inability to catch necessary frequency components. Besides, thanks to the spectral-designed convolutions, ChebNet can catch the underlying patterns on the graphs and finally achieves better results.
Some graph problems naturally just need low-pass filtering, as argued in Appendix K Having spectral ability may increase the complexity of the model, which may result in a negative effect. However, some other problems might need various kind of filters, like image understanding prob- lems. In our last experiment, we use the superpixel version of MNIST dataset (MNIST-75) show an example of graph problems that need various filtering. In MNIST-75, images segmented into around 75 regions by the SLIC superpixel segmentation algorithm (Achanta et al. 2012). Regions constitute the nodes of the graph and edges correspond to connection between regions in the image. The average pixel value of this region was assign to node, giving one continuous value. The dataset also includes the center position of each region, but we excluded that information to make the prob- lem more realistic and harder in terms of graph research. The dataset consists of 55K graphs for training, 5K graphs for validation and 10K for testing. Details and some illustrations the dataset can be found in Appendix L
We use hidden graph convolution layers that have 64, 128, and 128 features respectively. followed by global mean operator as graph readout layer, and ended by fully connected layer with 10 outputs corresponding to the number classes. To understand the effect of graph convolution, we apply the tests on 3 different inputs: the first one uses node degree feature, the second one uses
8

---

Published as a conference paper at ICLR 2021
Table 2: Test set accuracies on MNIST superpixel dataset
Node feature
MLP
GCN
GIN
GAT
CayleyNet
ChebNet
Node degree
01.29:
1..81
32.45+1.2
31.72+
45.61+1.7
46.23+1.8
Pixel value
12.11=0.5
11.35#1.1
64.96+399
62.61+2.9
88.41#2.1
91.10+1199
Both
25.10
52.9843.1
75.23+4.1
82.7342.1
90.31+2.3
92.08
pixel values and the last one uses both information. Implementation details and hyperparameter tuning can be found in Appendix
Table 2 gives the mean and standard deviation of the accuracy obtained over 10 runs on the test set, with different seed numbers. well known that the image version of the MNIST dataset can be processed by any ordinary CNN architecture. which is able to apply various filtering operations. Hence, we argue that superpixel graph of MNIST is a good candidate to show the graph data needs various kind of filtering. As seen in Table MLP and GCN cannot do significantly better than a random classifier when using only node degree or pixel value as input. That means that the distribution of node degrees or pixel values has no significant meaning for classification. When both node degree and pixel values are given, the accuracy of GCN is increased, but remains behind the best results. GIN and GAT outperform GCN in each case, but their performances remain behind those of ChebNet and CayleyNet, which are spectral-designed with supports that cover the spectrum.
FINAL REMARKS
In this paper, we have shown that most influential graph convolutions such as (Kipf & Welling 2017 Veličković et al. 2018) operate low-pass filters and some have very limited ability on producing high-pass in addition to low-pass filtering effect such as (Xu et al. (019).
Interestingly, while being restricted to low-pass filters, they obtain state-of-the-art performance reference node classification problems such as Cora, CiteSeer and Pubmed (Yang et al. 2016).. These good results on these particular problems induced by the nature of the graphs processed. Indeed, citation network problems, which are heavily assortative, are inherently low-pass filtering problems.
It is worth noting that, if we use enough convolution kernels, the frequency response of ChebNet kernels (Defferrard al., 2016 Levie et al., 2019) covers nearly all frequency profiles. However, these frequency responses are not specific to special bands of frequency. It means that they can act as high-pass filters, but not as Gabor-like special band-pass filters,if a low number of convolution supports are used (e.g. 3). Getting any arbitrary band-pass effect requires large number of convo- lution kernels, which makes the convolution not spatially-localized and increases the computational complexity.
As a conclusion, we claim that graph convolutions are problem specific and not problem agnostic. To have problem agnostic solutions, graph convolutions need to be able to produce necessary at least plenty of different frequencies in output signal profile. The frequency profile of graph convolutions not the single issue to be taken into account. But it is definitely one of the important perspectives that we need to pay attention. We point out that using only low-pass GNNs may not be a good choice for many graph problems. Finally, the convolution design can be considered the tuning of hyperparameters or it can be automatically designed by another secondary unsupervised task with respect the problem domain. Our future work will investigate this track. Experiments conducted in Section provviee empirical results to validate the theoretical analysis conducted in this paper.
ACKNOWLEDGMENTS
This work was partially supported by the French Agence National de Recherche (ANR), grant APi (ANR-18-CE23-0014 and the PAUSE Program (Collège de France).

---

Published as a conference paper at ICLR 2021
REFERENCES
Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süisstrunk. Slic superpixels compared to state-of-the-ar superpixel methods. IEEE transactions on pattern analysis and machine intelligence, (4(111)2274-22882 2012.
Peter W Battaglia, Jessica B Hamrick. Victor Bapst, Alvaro Sanzaez- Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:
2018.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets, 2018. URL https:// openreview net htte//oooumndd-HxxxXXXe0
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geo- metric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4): 18-42, July 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv: 2013.
Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning graphs: A model and comprehensive taxonomy. arXiv preprint arXiv:205..03675, 2020.
F.R.K. Chung. Spectral graph theory. American Mathematical Society, 1997.
Michaäl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pp. 3844-3852, 2016.
David K. Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Thimothy Hirzel, Alan Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molec- ular fingerprints. In Advances in Neural Information Processing Systems, pp. 2224-2232. 2015.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geomet- ric deep learning with continuous b-spline kernels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 869 1799-877441 2018
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyal, and George E. Dahl. Neural message passing from quantum chemistry. In Proceedings of the International Conference on Machine Learning, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks graph-structured data. arXiv preprint arXiv:1506.0516 2015.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Muizel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. http:://grapikeeeel.sss cs. tu do rww.orrtmuudd.mmm de
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
R. Levie, E. Monti, X. Bresson, and M. M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1): 97-109, Jan 2019. ISSN 1941-0476. doi: 10. 10.110997SP2201888899663
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks, 2020.
10

---

Published as a conference paper at ICLR 2021
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph
networks. In International Conference on Learning Representations, 2019b. URL https: 7/openreview. Sttp://ormmnndxyxymydem
Fernand Meyer. Topographic distance and watershed lines. Signal processing. (8(1):113-12) 1994.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115-
5124, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In Proceedings of the International Conference on Machine Learning, pp. 2014-2023, 2016.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: (90::09955051 2019.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending nigh-dimensional data analysis to net- works and other irregular domains. IEFE signal processing magazine, 30(3):83-98, 2013.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-50088 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning (ICML), 2019a.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.005: 2019b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference on Machine Learning, ICML' 16, 2016.

---

Published as a conference paper at ICLR 2021
A
GENERALISATION OF FRAMEWORK
1-th layer
Graph Convolution Layer
(1 11-th layer
H (+1)
H (1)
CR
Teni
Figure 4: a) Schematic of the graph convolution layer defined in equation
3 The graph has 12 nodes
and 12 edges. In the (-th layer, each node has a 2- feature vector H and H. represented
by colors. The / 1-th layer, has a 3-length feature vector, denoted H (((1) H (1+1) and (+(()))) Two convolution supports C() and ((2) are used. This architecture has trainable parameters, omitting biases if the convolution supports ( and C12) fixed. b) Graph convolution supports for 2D Euclidean domain signal to perform convolution process by 3 x mask.
Our selection of GNN generalization in equation 3 can be shown in Figure 4a with a detailed schematic of graph convolution layer on sample graph signal. This framework alize the Euclidean domain convolution layer. For 2D signal convolution by W7(1) R3x3 mask, we can define different convolution supports denoted by C()) ...C(9) f0, 13 16x16 in Figure for sample signal (c.g. image) shown by H() E R2x4, When we stack all node values (c.g. pixels) into column vector ( R 16x1 and ((.s), shows s-th scalar weight in stacked W1(1) we can write equivalence of Euclidean convolution by:
also gener-
H
Σ c(0) H(w(..))
(13)
One can see that in Euclidean domain, the supports can be designed by relative position of the nodes which is not the in graph world.
B PROOF OF THEOREM
Proof. First, let expand the B matrix by introducing its columns denoted 4 (A), (A)..... $s(A)
R":
H (+1))
Σ Udiag (2)) UJ H,!0)
(14)
Now, we distribute U and T over the inner summation:
n -1-1 =a
Udiag 1 (2)) n!!))
(15)
Then, we take out the scalars (ll.s) of the diag operator:
W
5 ft
(11)) =
W 1.
Udiag(# H.D))
(16)
12

---

Published as a conference paper at ICLR 2021
Let us define convolution operator C(s) I
C = Udiag p. (A))UT.
(17)
Using equation 16 and equation 17 we have thus:
$ Σ
H3
(1+1)
W
(1) Cl+)
H
(18)
Then, each term of the sum corresponds to matrix H Rux with
H(++1) (cO) Hw)))))))))) C(S) ((l..)))).
(19)
with _1 = [ 1 We get by grouping the terms:
H Σ c(s) cls) ((
(20)
which corresponds to equation 3 Therefore, equation corresponds to equation with ((+) defined as equation
C PROOF OF COROLLARY 1.1
Proof. By using equation 6 from Theorem we can obtain a spatial convolution kernel (()) whose frequency profile &, (A). Since the eigenvector matrix is orthonormal (i.e., U-1 U,,, we can extract 4b (A), which yields equation] 7
D PROOF OF THEOREM
ChebNet relies on the approximation of spectral graph analysis proposed in (Hammond et al. 2011), based on the Chebyshev polynomial expansion of the scaled graph Laplacian. Even though its multi supports frequency responses are known, to the sake of simplicity, it was represented in form of equation in (Defferrard et al. 2016) follows;
((1) =I, ((2) 2L/2max I, c(k) - ((K-2),
(21)
Proof. When the identity matrix is used as convolution kemne,, it just directly transmits the inputs to the outputs without any modification. This process is called all-pass filter. Mathematically, we can calculate the full frequency profile for kernel 7 by using Corollary I.1 namely
Φ = -
(22)
since the eigenvectors are orthonormal. Therefore, we can parametrize the diagonal of the full frequency profile by and reach the standard frequency profile for the first ChebNet support as follows:
(A) diag(1 (I) =
(23)
We can compute the (2)) kernel full frequency profile using Corollary 1.1
$ = U ( X L --I) U.
(
(24)
Since IT I0
equation 24 can be rearranged
T Amax
U U LU I
(25)
13

---

Published as a conference paper at ICLR 2021
Since À i An] are the eigenvalues of the graph Laplacian L, those must conform to the following condition:
LU = Udi:
(26)
U LU = diag(A).
(27)
Replacing equation 27 into equation
25 we get
2 Aax
2
diag () I.
(28)
This full frequency profie consists of two parts, a diagonal matrix and the negative identity matrix. Therefore, we can parametrize the full frequency matrix diagonal show the standard frequency profile as follows:
2A
Φ (A) = diag (2)
(29)
Amax
Given the third and following ChebNet supports, when we use Corollary T.1 frequency profile is
the corresponding
2x UT (20(0) - -cu--2) (2C(0C(-1-CH--)UU U.
(30)
By expanding equation 30
get.
Φ = 20 ((:) - T(C(K-2))
(31)
Since UUT_ = 1, we can insert the product UUT into equation 31
Thus, we have
& 20 CU -UT
(32)
2 (UT (1T) ((TC()) - (((h-22))
(33)
Since &F UT ((K)U for any k', it yields:
22 = 2422 2k-2;
(34)
Hence @1 and D2 are diagonal matrices, and the rest of the kernels frequency profiles become write the corresponding standard frequency profiles of third and following ChebNet convolution supports as follows:
diagonal matrices in equation 34 Therefore,
T (A) = 20 (-) (2) 2
(35)
E PROOF OF THEOREM 3
Proof. CayleyNet was originally defined as it uses the weight vector parametrization of (ماا) where the function ((: is defined in (Levie et al.
Igs.ja (i), 4)] in equation 1
2019 by
hd
K hd +i
g(A,h)= = co 2Re
Ck
(36)
where 12 - 1, Re(-) the function that returns the real part of given complex number, co trainable real coefficient, and CI,..., are complex trainable coefficients. We can write hd i
in Fuler form by v + 1. (otan and for ly + i by vI2X² 1.d By this substitution, equation 36 becomes
Σ c -aan-aoo0(---s----a22(aAaaa
g(A, h) = co +2e
(37)
14

---

Published as a conference paper at ICLR 2021
where atam2(y, 2) is the inverse tangent function, which finds the angle (in range of |- m)) of a point given its and æ coordinates. For further simplification, let us introduce the 8(-) function defined by
((x) atan2(-1,x)) a1,
(38)
Since the C&S are complex numbers, we can write them as a sum real and imaginary parts, Cj 4g/2 + iby/2 (the scale factor 2 is added for convenience). Thus, equation 37 can be rewritten as follows:
9(2.h) + Re E(ax ibs (uo(ns)
(39)
We can replace (ho(hA)) with its polar coordinate equivalence form cos(k((h)) + ssin(k((AA)). When we remove the imaginary components because of Re(-) function, equation 39 becomes
9(,, h)
+ cos(ke(hA)) - by sin(k
(40)
Jrmn
In this definition, there is complex coefficient, but only real coefficients (Co, dg and by for k 1,...,r) r) to be tuned by training. By using the form in equation 40 we can parametrize CayleyNet by the parametrization matrix B E 1gax2r+1 by
Lg( ...... ,... h)] = B Bico, 41 bi...., 6.]".
(41)
The s-th column vector of matrix B, denotes B., must fulfill the following conditions:
{ ((
1
if if E (2,4..... 2r. sin - (hhA) if E (3.5....,25
B, = 22)
(42)
2r +r++1 +1
We can see CayleyNet as a spectral graph convolution that uses 2r convolution kernels. The first kernel an all-pass filter, and the frequency profiles of remaining 2r kernels (A)) are created using sine and cosine functions, with a parameter h used to scale the eigenvalues in equation 42 Considering equation in Theorem domain. CayleyNet includes the tuning of this scaling parameter in the training pipeline. Note that because of the function definition in equation 38 (hh) is not linear in A. Therefore, $ cannot be a perfect sinusoidal As.
we can write CayleyNet's convolutions (C(+)) in spatial
F PROOF OF THEOREM 4
One major simplification of the ChebNet is Graph Convolution Network (GCN) (Kipf & Welling 2017). which has single convolution support and already presented in our framework in equation The first proposal of this paper uses the subtraction of the second ChebNet support from the first one under the assumption of >unax = 2 and L. is the normalized graph Laplacian, as it is defined by CGEN = C(1) - (2) = L.
Proposition 1. CGCN- = 21 - is a spectral-designell support and its frequency response is &CCN- (A) = X.
Proof. If the assumption is true, it should meet:
21 Udiag (2- XAUT
(43)
this can be written in the following way as well
21 L TT diaa T
(44)
since T 7 and (oddiag()UU" L., the proposition is true.
n
15

---

Published as a conference paper at ICLR 2021
One can see that the first proposal of GCN is spectral-designed and it is low- pass filter. That is why GCN is misclassified as a spectral approach in the literature (Wu et al. 2019b Chami et al. 2020).
However, instead of using this version, GCN used re- ne-oommalizatinn trick and defined its final single convolution support as:
CGON (D (D+1) (D+1)~11(A+ I)D 1)
(45)
where is diagonal degree matrix and A is the adjacency matrix.
Proposition 2. CCCN = (D 1/2 + T)(D + -)- frequency response is VGCN (X)
p+1 X for regular graphs whose node degrees are p.
p
Proof. When all node degrees are p. we can write diagonal degree matrix by = pl. It yields, L = I A/p A pl pL. When we substitute new equations of A and D into GCN support,
we get
pl - pL =
PL. L.
P
CGCN
(46)
p+1
p+
It should meet the following condition if the given frequency response is true:
p = Udiag(1
P A)UT
(47)
p+
p+1
Since Udiag(1)UT = I, and U dii = L, the condition in equation 47 is satisfied.
This proposition shows that the GCN frequency profile acts as a low-pass filter. When the given graph is regular graph, all node degrees are equal for the case of p = 2, is leading to a frequency profile defined by 1-22/3. Since the normalized graph Laplacian eigenvalues are in the range [0, 2]. the filter magnitude linearly decreases until the third quarter of the spectrum (cut-off frequency) where reaches zero. Then linearly increases until the end of the spectrum. This explains the shape of the frequency profile of GCN convolutions for ID regular graph observed in Figure 2 in blue one.
However, this conclusion cannot explain the perturbations the GCN frequency profile. To analyse this point, we relax the assumption = pl and rewrite equation 45 as follows and start to proof.
CGCN = (D + 7) + (D + 1) + 1/21/2
(48)
Proof. We can see that the GCN kernel consists of two parts, CGCN = C1 + C2. where first part is given by 61 (D + r)-1 and the second one is C2 = (D+ 1) A(D T)-1/2
For the second part (c2), we can write it using the element-wise multiplication operator @ (Hadamard multiplication)
C = II(d+1)) VI/(d+1)
(49)
where d the column degree vector d diag(D) and the division and square root also element- wise (Hadamard) operations. With the same notation, we can rewrite the Chebyshev second kernel, assuming that Amax 2.
C -
V1fd".
(50)
The two expressions equation 49 and equation 50 show that negative 02 is an approximation of the second Chebyshev kernel if vector consists of same values, as was assumed in Proposi- tion When the vector d composed of different values, the two matrices /I/d./I/d and (I/d+)).///(L
are not proportional for each coordinate (i.e., entry). To obtain 02 from ((2), we need to use different coefficients for each coordinate of the kernel. If the difference be- tween node degrees is important, these coefficients have the strong influence, and 02 may be very different from (2) Conversely, if the node degrees quite uniform, these coefficients may be neglected. This phenomenon is the first cause of perturbation on GCN frequency profile.
The first part (c1) of the GCN kernel in equation 48 is more interesting. Actually, it is diagonal matrix that shows the contribution of each node in the convolution process. Instead of looking for some approximations of known frequency profiles such those of Chebyshev kemels, we can write
16

---

Published as a conference paper at ICLR 2021
its frequency profile directly. Using Corollary matrix form by
1.1
express the frequency profile of c1 in
2. = -U"
(51)
where U is the eigenvectors matrix. By taking advantage of having diagonal kernel e1 we can express each component of full frequency profile as
Σ k=1 I+ (1+tauunau UinUss))))
( (Da)
(52)
where n is the number of nodes in the graph, ds is degree of the k-th node, ULA: is the k-th element of i-th eigenvector. As eigenvectors U, and U, are orthogonal for i j. their scalar product null. However, in equation 52 the weighting coefficient I+dæ is not constant over all the dimensions of the eigenvectors. Therefore, there is no guarantee that de,, (f. is null. This is another reason that explains that the GCN frequency profile has many non-zero elements outside of the diagonal.
In addition, it is also clear that the standard frequency profile of c1 (diagonal of De,, ie., (Le,), ),, in weighted sum
equation (52) is not smooth. Indeed, the diagonal elements of &c., can be written of squared eigenvalues elements, which again is weighted by 1/(1 + dg). ). If the latter constant for all k the sum of squared eigenvectors elements has be since the eigenvectors have unit 1.2- norm. But in the general case where 1/(1+ + dy) are not necessarily constant over all the dimensions of cigenvectors, the diagonal of the matrix may have some perturbations. This point constitutes another explanation on the fact that the GCN standard frequency profile is not smooth.
On the other hand, under the assumption that the node degrees distribution is uniform, we can derive the following approximation:
D p
ds-
(53)
We can then write an approximation of the GCN frequency profile function of the average node degree by replacing with p and obtain the final approximation:
C (A) == P
D+1 A.
(54)
Therefore, we can theoretically show the cut-off frequency, namely where GCN kernel frequency profile reaches 0, by
p+1
Aeut 23
(55)
G PROOF OF THEOREM
Graph Isomorphism Network (GIN) defined in (uu et al. 2019) has a single convolution support defined as follows:
CGIN A + (1 (1+6) +)1,,
(56)
where e a trainable parameter that makes the support trainable (GIN-c) and classified as spatial- designed trainable-support graph convolution. Another version named GIN-O also defined in the same paper where e = 0, which makes CCIN = A /: thus, the convolution becomes fixed-support
and identical with Vanilla GNN defined Section 2.2
The proof of B on the following proposition.
Proposition 3. For CGIN = 11+++)),, the frequency response is PGIN(A) = 1ts + +1-1)
for regular graphs, where p is the node degrees.
Proof. When all node degrees are it yields D = pl, L 1 A/p or A pl pL. When we substitute the expressions A and D into CGIN, we get
CGIN = (p+ [T
(57)
17

---

Published as a conference paper at ICLR 2021
It should meet the following condition if the given frequeney response is true:
(p+1 1+1+ +e e)1 PL = U'diag(p + c + -AAUU"
(58)
We can obtain the following equation by p c + + c) substitution:
(p + 1 e pl. (p + +) - -/''diagA)UU".
(59)
Since UIUT= and Udiag (A)UT L. the condition in equation 58 satisfied.
By relying Proposition 58 we establish Theorem 5 as follows.
Proof. Even in regular graph, the theoretical frequency response of GIN is not identical and de- pends on the node degree, thus not spectral-designed. In addition, we can see the GIN con- volution support as the sum of two matrices where the second one (1 + <) is diagonalizable by eigenvectors U of graph Laplacian by & However, the first part, which is adjacency A, cannot be diagonalizable by U. Since the convolution support is not diagonalizable, we cannot write exact frequency response of GIN convolution but just an approximation of Proposition R assuming by the average node degree of the graph is p in
Thus, the second part of GIN support spectral.
+ 1 +1-1
(GIN(A) =
(60)
P
H ADDITIONAL RESULTS ON SPECTRAL ANALYSIS
H.1 CHEBNET
To get empirical frequency responses of ChebNet supports, used regular 1D graph, Cora, Cite- Seer. As confirmed in theoretical analysis, in all cases the frequency responses do not depend on graph. The magnitude (in absolute value) of the frequency responses are shown in Figure D
As stated by Theorem 2 the first two kernel frequency profiles of ChebNet are 4 (A) = 1 and
(A) = /mmxaax 1. where is the vector of ones. Since Amax for all graphs that we used in the analysis, we get 2z(A) = À - 1. The third one and following kernel frequency profiles can also be computed using (A) = (
(A),, leading to ( = 2X² 4A for example for the third kernel. One can easily confirm the functions in range of [0...2] by relevant plot Figure D..
Thanks to Chebyshev polynomial expansion, we do not need to calculate supports by eigendecom- position which makes the method computationally efficient. Besides, as spectral designed, ChebNet covers all the spectrum. Theoretically it can create all necessary filters if we use many ker- nels and stack the layers back to back. However higher order supports frequency responses are less smooth than lower order ones. This does not guarantee that the graph convolution transferability is maintained, For this reason, in literature, generally a few (up to first 3) supports are used (Defferrard et al. 2016 Kipf Welling 2017).
H.2 CAYLEYNET
Since CayleyNet is spectral, its supports frequency response is consistent and does not change ac- cording to graph structure. It leads get the same empirical results for all our attempts on ID graph, Cora, CiteSeer graphs. Theorem 3 For instance, the first support frequency response is Φ (A) 1 as all-pass filter Figure (blue plot). If we assume zoom parameter is h 1, the second support frequency response be- comes (2 = (A)). To confirm that result, we can first check the case where À 0. Since -1 where its magnitude (absolute value) in the diagram is 1. Later, we can
result can be compared to relevant support result in Figure 1p.
((0) π, (0) check the case where = 1. Since f(1) = - x 2/2, thus (1) = O as seen in the orange plot in Figure [p. A is the cut-off frequency for the second support of CayleyNet.
Having suppir with different frequency responses makes the convolution productive in terms of output signal profile. Moreover, by learning zoom parameter, theoretically,
shrink (higher
18

---

Published as a conference paper at ICLR 2021
h value) expand (smaller h value) the frequency responses which is needed according to the problem. However, it makes the supports non-static. The supports need to be calculated in each learning epoch. Although, to limit the induced computational cost, approximation is computed using fixed number of Jacobi iterations (Levie et al., 2019). But still, it seems not efficient in benchmark problem. Instead, fixed value for the parameter might be used and h can be treated as an hyperparameter to be tuned according to validation set. Besides, it has no band specific supports, but band-pass might be obtained by using multi supports and stacked layers.
H.3 GCN
By a clear margin, the most popular method is GCN (Kip & Welling, 2017 in GNN literature, thanks to its simplicity and relatively good results on some benchmark dataset. However, as we prove in Theorem F it is low-pass filter. Since it has single support, one kind of filter which is low-pass, stacking that layer in deep architecture will not work. Because it continuously smooths the signal the graph and the final layer, there will only be smoothed signal.
Eignuvaluue
Fagenvalus valuo
Eigeuvalurs
Eigewalus
Eugervstons
Eigenvalues
Figure 5: Full frequency response of GCN on ID, Cora and CiteSeer graphs
The three standard frequency responses in Figure 2 have almost the same low-pass filter shape. It corresponds to function composed of decreasing part the three first quarters of the eigenvalues range, followed by an increasing part on the remaining range. This observation is coherent with the theoretical analysis. Hence, kernels used in GCN are transferable across the three graphs at hand. In Figure Za. the cut-off frequency of the 1-D linear circular graph is exactly 1.5, while it is about 1.35 for CiteSeer. This observation can explained by the fact that when considering 1-D linear circular graph, all nodes have a degree (p- 2), hence Aeut 1.5. Since the average node degree in CiteSeer is 2.77, therefore Acui As 1.36.
80
Magnitude
Magnitude
67
Eigenvalne
Eigenvalue
Figure 6: Heat map of GCN's frequency profiles on ENZYMES and PROTEIN dataset graphs.
Concerning the full frequency responses, there is no contribution outside the diagonal for the reg- ular line graph (Figure a). Conversely, some off-diagonal values are not null for CiteSeer and Cora (Figure 5 b-c). Again, this observation confirms the theoretical analysis in Appendix F We also provided heat map of frequency responses GCN convolution on more realistic biological graph dataset named ENZYMES and PROTEIN in Figure 6 The majority of the graph frequency
19

---

Published as a conference paper at ICLR 2021
responses have almost the same shape. However, some graph frequency responses are far away from the expected frequency response as illustrated with lighter color heatmap.
H.4 GIN
GIN model defined in Xu al. (2019) is not just layer but mini multi-layer model. The first layer is the main graph convolution layer which we analyzed, followed by at least one but preferably two MLP layers, According to Theorem D the frequency response of the main GIN convolution has - c+ of magnitude at zero eigenvalue and it decreases with respect to the eigenvalue. The outer node degree
scaling factor of the frequency response that does not have any effect of the character of filter. While increases, the cut-off frequency of the convolution increases, thus makes more low-pass effect. On the other hand, when decreases, the cut-off decreases, thus makes more high-pass effect while inner can be seen multiplicand of the effect. Theoretically, we can say that GIN's cut-off frequency Aea se + (1 + e)/p. which is the same with GCN, = 0.
Magnituda
Magnitude
2
E
Eigenvalues
Eigenvalues
1.5
Eigenvalues
Figure 7: Full frequency profiles of GIN-O and frequency responses of different values for Cora graph.
One can easily calculate the frequency response of adjacency as convolution support where C A. can be seen as special GIN support where = 1. Thus + (A) = p(1 A). The formulation is almost the same as the one given by (NT & Maehara 2019). It differs by the scaling factor and an approximation
the regular graph case, Since the eigenvalues of the normalized Laplacian lie on the interval [0, 2]. it works But, in most of applications, the eigenvalues greater than less likely. this case, there are less component pass. It results that using adjacency has more likely low-pass effect concluded in INT& Maehara 2019).
notch-like band-stop filter for intermediate frequency (A 1).
The experimental analysis of the spectral behavior of GIN Xu et al. 2019) first implies com- Then, the spectral representation of the obtained convolution matrix can be caleulated using Corollary 1.] This result leads to the frequency profiles illustrated in Figure b-c (ID and CiteSeer graph) and Figure (Cora graph). For regular iD circular graph where p 2. the frequency responses are absolutely what Proposition 3 inddicates. As shown in Figure 2p. the cut-off frequencies are 2. 1.5, 1.0, and 0.5 for (1,0, -1, 22) respectively. But for realistic graphs such as CiteSeer, since average degree is n 2.77, the cut-off frequencies are 1,72, 1.36, 1.0 and 0.63 for c (1, - -2 respectively as shown Figure The results for Cora graph are slightly different than CiteSeer Figure 7p because of the fact that average node degree is different. Since GIN does not have spectral designed support, in its full frequency profile, there are some non-zero components out of the diagonal as shown in Figure 7 for GIN-0 model Cora. Figure 8 and 9 show the heat map of frequency responses of the GIN model under e = (1,0, -2} on ENZYMES and PROTEIN collection of graphs.
pute the convolution kernel as given in equation 56 for e = -,, 0,
20

---

Published as a conference paper at ICLR 2021
Byomke
Egannca
Egenda
Figure 8: Heat map of different e valued GIN frequency profiles on ENZYMES
0
é = 2
Stgrenate
Figure 9: Heat map of different valued GIN frequency profiles on PROTEIN
H.5 GAT
One can see that, each support is function of trainable weights (W(h,e), a.!l))) in GAT, frequency profiles cannot be directly computed similarly to previous ones. We did bunch simulations for Cora graph. As the proposed method used for Cora problem, have generated 8 different
volution supports corresponding to 8 pairs of W(l.s) E R1433x8 (1433 features for each node) and (!.+)) R 16x1 trainable weights for the first layer (Veličković et al. 2018). We produce 240 (30 for each support) random pairs of W'(..) and (4.e) where activation function LeakyReLU has 0.2 negative slope in (Veličković al., 2018). Later, calculated frequency response of gener- ated supports by Corollary [.I The mean and standard deviation of the frequency profiles for these simulated GAT supports are shown in Figure 3 and its expected and standard deviation of the full
frequency response shown in Figure 10
Magnitude
Magnitude
Eigeuvalueg
Eigenvalues
Eigenvalues
Eigervalues
Figure 10: Full frequency profile of GAT and its standard deviation.
The full frequency profile is not symmetric as seen in Figure 10a. According to Figure 10b, varia- tions are mostly on the right side of the diagonal the full frequency profile. This related the fact that these convolution kernels not symmetric. However, the variation frequency profile might not be sufficient problems that need some specific band-pat filters.
In order to get trained attention head frequency responses in ENZYMES and PROTEIN datasets, randomly divided the dataset into 4 folds. We trained the 2-layer GAT model which has 25 attention heads each by using 3 folds. We calculated attention heads (50 C' matrices given in equation 12 25 each layer) for each graph in test fold. The density heat map in Figure 33-- are the frequency responses of these attention heads for ENZYMES and PROTEINS dataset respectively.
21

---

Published as a conference paper at ICLR 2021
Table 3: Sum of squared errors. All models have roughly 30k trainable parameters.
Prediction Target
GCN
GIN
GAT
ChebNet
Low-pass filter (21)
15.55
11.01
10.50
3.44
Band-pass filter (92)
79.72
63.24
79.68
17.30
High-pass filter (Py)
29.51
14.27
29.10
2.04
I WHICH FILTERS CAN THE GNN MODELS LEARN?
In this section, we seek to measure of the ability of GNN models to learn some specific filtering process. This study is very important in order to understand the learning capability of existing GNN models. Since the problem may need various types of filtering, the best GNN model has to be able to learn any kind of filtering.
For this purpose, we conduct an empirical analysis on real image with resolution of 100x 100 and its corresponding 2D regular 4-neighborhood grid graph. The input of the GNN is the adja- cency matrix of size 10000x 10000 and the pixel intensities given in 10000-length vector. We create three different spectral filters that correspond to low-pass, band-pass and high-pass effects and apply these filters the given input image. Our selection of spectral filters defined by 0.5)²) and (p)))
p (p) (epp--10pp)) (p()) = exp(-1000) pass, hand-pass and high-pass filters respectively, where p² u² v² and u and v are the normal- ized frequencies on each direction for given image resolution. Used input image and its filtering results can be found in Figure I1]
for low-
Since we do not use pixel positions, neither as node feature nor edge feature, we create these spectral filters to be learned in directional agnostic way. Therefore, the problem can be viewed as single graph node regression problem, where we train the GNN models to minimize the square error between output and targeted filtered image.
Figure 11: Input image, and its filtering results by 21, 42 and 43 respectively
In order assess ChebNet, GCN, GIN and GAT, one-length feature (intensity of the pixel) and the number of neurons in hidden layers is respectively 32, 64 and 64; the output layer is MLP that projects the final node representation onto the single output for each node. We used roughly 30k trainable parameter in ChebNet with 5 supports. For the other methods, we tuned the hidden neuron numbers in order be sure that they have a similar number of trainable parameters. Since the aim is not assessing the generalization performance, we do not use any regularization or dropout to address overfitting, but simply force the GNN learn the onput-output relation. We keep the iterations till there is no improvement for consecutive 100 iterations maximum 3000 iterations.
3-layer GNN architecture whose input is
BobleBgivve. the sum of squared errors between target and the output of the trained model. One can see that ChebNet constantly outperformed GCN, GIN and GAT for tasks. For learning low-pass filtering, the rest of the models did better compared to the high-pass and band-pass tasks. That is the fact that GCN, GIN and GAT have the ability to act as low-past filters. In addition to do better on the low ww-pass task, GIN also did relatively better the high-pas figh-pass task well. It is obvious that GIN can work as high pass if the parameter is selected negative (see Theorem [5). turns out that the trained values of in GIN for each layer are -5.27, -2.21 and - -0.47 for the high-pass task.
22

---

Published as a conference paper at ICLR 2021
The output of GNNs trained with hand-pass task. Images are taken from ChebNet, GIN, GAT and GCN respectively.
Figure 12:
Table 4:
ChebNet's of squared errors band-pas pass tasks with respect to S kernels and L stacked layers. All models have roughly 30k trainable parameters.
S=2
S=3
S=5
S=7
$=10
L=1
65.06
56.25
47.12
39.59
28.15
I.=2
55.85
45.96
26.81
18.92
13.33
L=3
50.13
36.60
17.30
9.84
7.32
L=4
44.88
24.89
11.90
8.91
6.96
Thanks to the spectral-designed convolution supports in ChebNet, it could learn high-pas, and low- pass tasks very well. However for band-pass tasks, even though it is the best in this category too, it still has large eπrоrs compared to the high-pass and low-pass tasks. This is due to the fact that the selected band-pass filter is very narrow, because the coefficient 1000 in the formulation makes the used ChebNet (with 5 convolution supports and 3 layers) unable to adapt this stiff (not smooth) filter function. Moreover, since ChebNet has no band specific convolutions, band specific output can be produced if the number of kernels increases (going wider) and/or the model goes deeper. To clarify this point, we conducted another test for band-pass task on ChebNet to show the effect of going deeper in the model and going wider (increase the convolution support) while keeping the trainable parameters fixed. These results are given in Table 4
According to Table 4 the ability of ChebNet learn the given frequency response becomes better with respect to the number of convolution supports and number of layers. However, this result is not surprising where is proved that any frequency response can be written by weighed sum of enough number of Chebyshev polynomials (Hammond et al. (201T)). When we train the ChebNet, it just finds these coefficients to create the target frequency response by minimizing the error. However, the interesting point is the incapability of GCN, GIN and GAT methods to even create reasonable approximations these targeted filter effects. For instance, it can seen in Figure 12 that ChebNet performed well to produce the desired band-pass output. However, GAT and GCN produce just different kind of low-pass filtering result instead of band-pass, while GIN at least can find edges (high-pass component) thank to its trainable parameter c. We also tested the deeper network for GCN, GAT and GIN as well and have not seen any significant improvement when we use deeper network.
J CAN GNN CLASSIFY GRAPHS ACCORDING TO FREQUENCY OF ITS SIGNAL?
In this section, we measure the generalization ability of GNN for graph classification problem where graph classes depend on the signal that the graphs carry. We generate 5000 images of 100x 100 pixels composed of random generated frequency patterns obtained by a sinusoidal function with frequency in the range [1-5]. We labelled the image as negative the pattern's frequency is in the ranges [2-2.5] or [4-4.5]. The rest of the frequency patterns are labeled belonging the positive class. Then, we randomly rotate and translate the image pattern, add white noise (with std=0.2) and normalize each image independently. From each image, we randomly sample 200 points in the
23

---

Published as a conference paper at ICLR 2021
Table 5: Test accuracy and binary cross entropy loss.
MLP
GCN
GIN
GAT
ChebNet
Accuracy
50
77.90
87.60
85.30
98.2
Loss
0.69
0.454
0.273
0.324
0.062
100x 100 image plane and divide the image into 200 regions by watershed algorithm (Meyer) 1994]. where each sampled point is the marker. From this preprocessing, we generate 5000 graphs, watershed region in the image, and if the two regions have intersection on the image plane, we assume these two nodes are connected by an edge the graph. We set the average intensity value each region I-length node feature. Even though we know the region center position, we do not use it in order to make the problem harder. Sampled generated image, randomly selected points and their watershed regions, and the graph can be found in Figure 13 for 30-node illustration.
each graph having 200 nodes. Each node corresponds
2.6
32
Figure 13: Sample graph in Band-Pass graph dataset. Random rotated and translated image pattern with frequency I, random sampled points and their watershed regions, and graph represent connected region and average region intensity value respectively.
We divided the dataset into train/valid/test subsets, with respectively 3000, 1000 and 1000 graphs. We resampled the same number of positive and negative examples, such that the dataset is balanced. We used 3 layers of GNN followed by a mean readout layer and finally two fully connected layers which have 10 and neuron respectively. Since the problem binary graph classification problem, we used binary cross entropy loss and no regularization. We roughly use 30K parameters in each model. The dropout ratio has been applied all GNN layer's inputs and optimized with respect to the validation set performance.
The results are found on Table Since the node distributions are all the same in the graphs (because the graph nodes were independently normalized), MLP cannot do better than random classifier. GCN does not perform well, probably because of its low-pass nature. Since GAT and GIN are better than GCN according to the spectral ability. they got better accuracy than GCN. Finally, ChebNet with convolution supports clearly outperforms the rest of them with a huge margin. These results show that models able to catch particular band of frequencies obtain the best results, whereas only low-pass based methods like GCN perform only slightly better than MLP. Therefore, this toy example confirms theoretical analysis.
To conclude, we have shown that if the model is able to perform different filtering operation, it can classify the graphs according to frequency of its signal.
K WHY LOW-PASS GNNS GIVE REASONABLE RESULTS ON SEMI SUPERVISED TASKS?
In the recent literature, GNNs are generally evaluated semi-supervised node classification prob- lems. The most well-known datasets are Cora, CiteSeer and PubMed paper citation graphs (Yang al. 2016). In these graphs, each node corresponds paper. If paper cites another one,
24

---

Published as a conference paper at ICLR 2021
Table 6: Comparison of methods the transductive learning problems using publicly defined train, validation and test sets. Results are on accuracy
Method
Cora
CiteSeer
PubMed
MLP
0.551
0.465
0.714
ChebNet
0.812
0.698
0.744
CayleyNet
0.819
0.701
0.751
GCN
0.819
0.707
0.789
GAT
0.830
0.725
0.790
LowPassConv
0.827 + 0.006
0.717 + 0.005
0.794 +: 0.005
there is unlabeled and undirected edge between the corresponding nodes. Binary features on the nodes indicate the presence of specific keywords in the corresponding paper. The learning task is to attribute class each node (i.e., paper) of the graph using for training the graph itself and very limited number of labeled nodes. Labeled data ratios are 5.1%. 3.6% and 0.3% for Cora, CiteSeer and PubMed respectively. Since the connected node's probability of being in the same class is high (0.83, 0.71, 0.79 for Cora, CiteSeer and PubMed respectively in Liu et al. (2020)), these graphs are classified assortative graphs. When the connected nodes are highly likely to be in the same class, label propagation based low-pass effected algorithms can give reasonable results.
To show empirical evidence that any ordinary low-pass filter can give comparable results by low- pass GNNs, we created fixed, response manually designed in the spectral domain by (Aa) (1 X/ >/mmax This GNN model is denoted as LowPassCon in Table 0 and its average accuracy and standard deviation over 20 random runs reported. use predefined train, validation and test sets as defined by Yang et al. (016)) and follow the test procedure of Kipf & Welling (2017) and Veličković et al. (2018) for fair comparison. According to Table 6, spectral-desight
single convolution support GNN whose frequency
GNN's such as CayleyNet and ChebNet slightly outperformed by other methods, including simple low-pass convolution GNN. On the other hand, GCN and GAT do not give significantly better results than ordinary low-pass graph convolution.
These results seem conficciigg with the idea having spectral well-designed graph convolutions. However, if the problem just needs low-pass filtering effect and if the model produces essary spectral component in the output, it may have a negative effect on the accuracy. Instead of just single low-pass convolution support, if we have many convolution supports with different spectral properties, it increases the trainable parameters for vain. Regularization may help to over- come this issue. This problem may be solved by learning the convolution support in the frequency domain by another secondary unsupervised task which is in our priority list to do.
unnec-
L DATASETS AND IMPLEMENTATION DETAILS
Figure 14:
Two sample graphs in MNIST-75 dataset (from 0 and from 1 class), the location of the nodes is just for illustration. Models do not use the node positions.
In our experiments, we used 3 citation graph datasets, named Cora CiteSeer and PubMed, an ar- tificial regular graph where each node degree is 2, named ID, 2 biological graph datasets named
25

---

Published as a conference paper at ICLR 2021
Table 7: Summary of the datasets used in experiments.
Cora
CiteSeer
PubMed
ID
Band-Pass
PROTEINS
ENZYMES
MINST-755
Graphs
1113
Nodes
2708
3327
19717
1001
200 each
39.06 each
32,63 each
75 each
Edgos
5429
4732
44338
1001
1072.6 each
72.82 each
62, each
694.7 each
Classes
7
NA
2
Training
140 Nodes
120 Nodes
60 Nodes
NA
3K
9-fold
9-fold
55K
Validation
Nodes
Test
1000 Nodes
1000 Nodes
1000 Nodes
NA
1K
NA
NA
10K
PROTEINS and ENZYMES, Band-Pass graph dataset which created by in order to evaluate the models, and a large scale MNIST-75 graph dataset. The details of these datasets can be found in Table 7 Two samples MNIST-75 dataset are shown in Figure 14
In our tests on MNIST-75, all hyperparameters are tuned by grid as follows: f-2 norm reg- ularization applied on trainable weights in {0, 10 10 50103. 10 1,10-4,10 10-5) and dropout in {0, 0.2, 0.4, 0.6] } for all models. In CayleyNet, we treated the zoom parameter as an hyperparameter and tuned it within the candidate values (0.5, 1, 1.5. 2) and also {1, 2, 3} which leads {3. 5. 7] numbers of supports. ChebNet support number is also another hyperparameter, we tuned it in set of (3,5,7] 7) For GAT, we tuned the number of heads and the number of output features by concate- nating not which can give the predefined layer feature. For a 64-feature output, two architectures were studied: heads each out concatenating. The same for 2e-fcature output layer well, using the same number of heads. For each layer of GIN model, there is one main GIN convolution layer followed by the same size of MLP. We tested the fixed and trainable well; finally concluded to a validation set result. All activation are ReL.U, but Elu (exponential linear unit) in GAT. In the output layer, the linear activation used in all models and the loss function is the cross entropy. We used Adam optimization with a 0.01 learning rate without decay. We fixed the number of iterations 100 under 64 batch size. The results were selected the iteration where the validation accuracy is maximum.
outputs with concatenating, and heads each has 64 output with-
trainable
according
26


Reviews:
[{"review_id": "u2i5ND63GY4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThis paper shows an equivalence framework between Graph Neural Networks (GNNs) defined in the spatial domain (based on local node neighbourhoods updates) and spectral domain (based on filters defined on eigenvalues of the graph Laplacian). Using this framework,  the paper derives the spectral equivalent of common spatial GNNs hence showing these act  low-pass filters in the spectral domain. The paper shows experimentally that on MNIST superpixel dataset, spatial GNNs show poor results compared to spectral GNNs. \n \n## Recommendation \nI recommend this paper be accepted (Accept/weak accept given reviewer confidence - 2/5)\n\n## Strong and weak points \n+ The paper does not present a new method but makes clear the connection between spatial-designed and spectral-designed GNNs which has not been previously documented to my knowledge. The connection between spatial and spectral GNNs is remarked upon in Bruna's original 2013 paper and is discussed in later papers (e.g., Kipf&Welling GCN, Wu+2019a_ICML). However, this paper makes the connection explicit. \n\n- On the flip side, the technical novelty in the paper might not be sufficient but I would still argue that the paper merits publication.  \n\n- One weak point of the paper is the lack of empirical evaluation on downstream tasks. I understand this is not the main focus of the paper  and these numbers are reported in the respective papers but I would like to see the numbers (even if directly taken from literature). The MNIST superpixel dataset gives a highly biased view for need of high-pass filter (which is provided by spectrally-designed GNNs). For example, see [Wu2019a, ICML'19] Tables or Table 2 in https://arxiv.org/pdf/2003.00982.pdf . \n\n\n## Questions to the authors \n- Since the theoretical frequency response of CayleyNet, ChebNet, GCN, GIN and GAT,  is one of the main contributions of this paper,  I think the paper would benefit from presenting this in a tabular form in the main text e.g.,  Method, Classification (design(spatial/spectral), support (fixed/trainable), frequency response dependent on graph structure, etc.) \n\n- The paper mentions the necessity of high-pass and band-pass filters. However, the paper does not show any toy example of a GNN which acts as a  band-pass filter.\n\n- The paper mentions Weisfeiler-Lehman test in the introduction as a theoretical tool for expressive power of GNNs and its limitations in that for \"as powerful as k-WL\" GNNs, the test cannot distinguish between their discriminative power. However, k-WL for $k \\ge 2$ implies non-local updates since multisets are considered. So is the above framework limited to 1-WL GNNs?  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eK4G9h4bGEO", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary: \n\nThe authors study the expressive power of GNNs from the spectral view and bridge the gap between spectral and spatial designs of graph convolutions by casting several popular GNN models into a common framework. The authors also shows the necessity of non-low-pass filters on some datasets.\n\n2. Strong points of the paper:\n\na) The writing is quite clear to understand.\n\nb) The experiments indicate the need to go beyond low-pass filtering.\n\n3. Clearly state your recommendation (accept or reject) with one or two key reasons for this choice:\n\nI am slightly leaning towards recommending a rejection to this paper, with the main reason being that I am not sure if the contributions are sufficiently significant, as I will elaborate below.\n\n4. Provide supporting arguments for your recommendation:\n\na) Regarding the results on the frequency responses obtained for the different models, those on ChebNet and CayleyNet seem not surprising since the spectrum is their starting point. The filtering properties of GCN have also been relatively well-studied, such as in [1, 2, 3, 4, 5], plus equation (10) only holds when the graph is roughly regular. \n\nb) In section 5, some of the claims ask for more justifications, such as “GCNs need a high number of convolutional kernels if the input-output pairs can be figured out certain simple filters”, and “since GIN is not spectral-designed, there is no guaranty that it works the same for different graph datasets”. They could be correct in the end, but it will be better to support them with either theoretical arguments or experimental evidence. For example, could you come up with specific examples that show the limits of GCNs and GINs mentioned here? \n\nc) For GAT, it is not clear whether using randomly sampled attention weights is representative of its normal filtering behavior.\n\n5. Ask questions you would like answered by the authors to help you clarify your understanding of the paper and provide the additional evidence you need to be confident in your assessment:\n\na) In what way is the theoretical analysis here helpful for our understanding of the different kinds of GNNs beyond existing work on the filtering properties of GNNs? \n\nb) As I mentioned above, it would be nice if some of the claims can be further supported.  \n\nc) On Page 3, the second line, what exactly does “$\\lambda_i$” mean? Does “i” refer to the i-th feature dimension or the i-th eigenvector?  \n\n6. Additional feedbacks:\n\nPossible typo: On Page 6, the third line from the bottom, should it be Figure 2a and Figure 2b instead of Figure 1a and Figure 1b?\n\nReferences:\n\n[1] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks.\n\n[2] Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters.\n\n[3] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification.\n\n[4] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper insights into graph convolutional networks for semi-supervised learning.\n\n[5] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, Jie Tang. Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec.", "extra_scores": {}, "extra_text": {}}, {"review_id": "dmm11HAMPK", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==== Summary ====\n\nThis work studies the performance of different Graph Neural Network (GNN) from a spectral perspective. In particular, it shows the kernel for all kinds of proposed GNN models can be expressed in a general form with a specific frequency response definition, which indicates the spectral property (spectrum) of the kernel. Based on this definition, this work empirically studies the band-pass property for kernels in different models and demonstrate the importance of such spectral perspective.\n\n==== Pros ====\n\n+ I like the spectral analysis, which is interesting, novel and appears to be important. \n+ The discussion on different GNN models is comprehensive and solid enough.\n+ The experimental result shows that it is important to have different kinds of filters \n\n==== Cons ====\n\nI do not have too much criticism about this work. I am interested to see if there could be some extra discussion/example about how should we choose the kernel for some specific problem, based on the spectral perspective. The experimental result in Sec 5.2 shows that for tasks on images using some kernel with spectrum cover the whole region has the best performance, then *how about other tasks such as semi-supervised learning?* It would be great if there is some guidance/analysis, otherwise we still need to determine the most suitable model based on empirical result. \n\nAnother question is that, the expressive power analyzed by WL-test involves the depth of the network, while in this work it appears that only one layer is considered, so I am wondering *what is the relation between the depth and the expressive power, from a spectral perspective?* To me it seems to be difficult to analyze, but I believe it is worth to address, as we have seen the importance of depth in CNNs. \n\n==== Reason for score ====\n\nThis paper is clear-written, the spectral perspective looks very interesting to me, the theoretical analysis appears to be correct and solid, and the experimental result verifies that the analysis from such perspective is important indeed.  Therefore I tend to vote a clear accept. \n\n==== Minor comments ====\n\n- Below Eq. (2), '$g_0, g_1$ ... trainable models', a typo?", "extra_scores": {}, "extra_text": {}}, {"review_id": "auUDzY82cVo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a spectral-based analysis method to analyze the modeling abilities of major GNNs. Specifically, the first use the concept of convolution support to unite the ideas of spatial-based methods and spectral-based methods. By further identifying the frequency profile of different models, the authors obtain an overview of which spectrum range different models may cover. The evaluation on regular and in-regular graph datasets validate their arguments. In general, the paper brings an interesting perspective in addition to the WL-test to reveal the expressive power of GNNs, and both the theory and evaluation sound solid. It would be better if the authors can further address a few issues.\n\nFirst, the authors summarize that in certain cases (e.g., sum pooling), the spatial based methods can be considered in the form of Eqn. 3 shows. Though the authors describe that advanced methods like GAT can also be described in this way, it would be great if the authors can make an explicit argument in the beginning of Sec. 3 to describe whether general spatial based methods (e.g., using max pooling, or other $upd(x, y)$ functions) can also be described in this way. \n\nI also suggest the authors to revise Definition 2 to further explain why each convolution support has the same frequency response over different graphs in a spectral designed case, as there might be some training parameters that can be affected by different graph structures. In addition, in Corollary 1.1, the authors indicate the frequency profile of any given graph convolution support can be defined as Eqn. 7, it is unclear if this also includes spatial-designed graph convolution.\n\nThe analysis in Sec. 5 is interesting, but it would be better if the authors can expand the discussion on how we can further utilize the obtained frequency profile to analyze the expressive power of different GNNs. Dividing different filters into low-pass, high-pass, and mid-band categories seem to be in a very coarse granularity and it would be better if the authors can discuss some potential directions for more detailed analysis. I’m also interested in if the number of kernels of the same category (e.g., low-pass filters) may affect model performance. It would be interesting to see if any experimental results are provided to analyze the impact of the number of kernels, the distribution of types rather than their categories only. \n\nIn summary, this work provides a new perspective in analyzing the expressive power of GNNs and I suggest the authors to further address the above issues.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a new theoretical tool to connect the gap between the spectral perspective and spatial perspective of graph neural networks. The frame-work is considerably broad and can deal with several existing methods. From this view point, the connection between the spatial and spectral perspectives are made explicit while they are noticed in an informal way by existing researches. The frequency response of several methods are analyzed through theories with support by some numerical experiments.

The idea of connecting spatial and spectral perspective would not be entirely new, but the main novelty of this paper is to make it explicit and analyzed the frequency response of well-known methods concretely. This is informative to the literature and extends some known results to more general settings. The numerical experiments well justify the plausibility of the theory. For reasons mentioned above, I think this paper is worth publishing in ICLR2021.
Decision: Accept (Poster)