Frequency Analysis for Graph Convolution Network
Authors: Hoang NT
Takanori Maehara
Venue:  (2020)
Keywords: graph signal processing
frequency analysis
graph convolution neural network
simplified convolution network
semi-supervised vertex classification

Abstract: In this work, we develop quantitative results to the learnablity of a two-layers Graph Convolutional Network (GCN). Instead of analyzing GCN under some classes of functions, our approach provides a quantitative gap between a two-layers GCN and a two-layers MLP model. Our analysis is based on the graph signal processing (GSP) approach, which can provide much more useful insights than the message-passing computational model. Interestingly, based on our analysis, we have been able to empirically demonstrate a few case when GCN and other state-of-the-art models cannot learn even when true vertex features are extremely low-dimensional. To demonstrate our theoretical findings and propose a solution to the aforementioned adversarial cases, we build a proof of concept graph neural network model with stacked filters named Graph Filters Neural Network (gfNN).


Under review as a conference paper at ICLR 2020
FREQUENCY ANALYSIS FOR GRAPH CONVOLUTION NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
In this work, we develop quantitative results to the learnability of a two-layers Graph Convolutional Network (GCN). Instead of analyzing GCN under some classes of functions, our approach provides a quantitative gap between a two-layers GCN and two-layers MLP model. Our analysis based on the graph signal processing (GSP) approach, which can provide much more useful insights than the pesssag--passing computational model. Interestingly, based on our analysis, we have been able to empirically demonstrate a few cases when GCN and other state-of-the-e models cannot learn even when true vertex features are extremely low-dimensional. To demonstrate our theoretical findings and propose a solution to the aforemmntioned adversarial cases, we build a proof of concept graph neural network model with stacked filters named Graph Filters Neural Network (gINN).
INTRODUCTION
Graph neural networks (GNN) is a class of neural networks which can learn from graph-structured data. Recently, graph neural networks for vertex classification and graph isomorphism test have
achieved excellent results on several benchmark datasets and continuously set new state-of-the-ar
performance (Kipf and Welling, 2017 Veličković al. 2019 Wu al. 2019 Klicpera et 2019).
Many variants of GNN have been proposed to solve problems in social networks (Hamilton et al. 2017: Zhang al. 2018a). biology (Veličković et al. 2017; 2019), chemistry (Fout et al. [2017
Gilmer et al. 2017). natural language processing (Bastings et al.) 2017; Zhang et al. [0T 8b. Wu reasoning for vision (Santoro al. 2017). and few/zero-shor learning (Gareia and Kampffmeyer et al., (019). Due to the rise of GNNs in machine learning applications, understanding GNNs theoretically has gathered lots of attention in the machine learning community.
ct al. 2019
Bruna 2017
While most theoretical results of GNNs are based on the message-passinng passing model (Xu et al., 2019 Keriven and Peyré 2019), there are a limited number of theoretical results for the filtering approach. However, in practice, the graph filtering view have inspired many computationally fast and high accu- racy models such as ChebNet (Defferrard et al. (2016), GCN (Kipf and Welling (017)) SplineConv (Fey et al. 2018), LanczosNet (Liao et al. 2019), and label efficient models (Li al. 2019). In this work, we theoretically study the GCN model (Kipf and Wellingl 2017) and the SGC model (Wu et al. 2019). Instead of showing which class of function GCN or GNN model can theoretically learn, we develop quantitative bounds for the gaps between GCN/SGC and a two-layers fully connected neural network. Our theoretical results imply few cases where SGC and GCN would fail to work: high-frequency labels, noisy features, and complex features. Interestingly, we also find other state- of-the-art GNN models such as GraphSAGE Hamilton et al. (2017) or DGI Veličković et al. (2019) failed to perform in our high-frequency labels experiments.
Recently, Wu et al. (019) showed that graph convolutional networks (GCN) can be broken down into two steps: low-pass filtering and feature learning. Such simplification not only improves GCN's computational speed and accuracy in a wide range of problems but also allows a better understanding of the GCN model. To show the low-pass filtering nature of GCN-like models, Wu et al. (2019) used the Rayleigh quotient to bound the maximum eigenvalue when self-loops are added to the graph, which means adding self-loops created stronger low-pass filter (Wu et al.) [019 Lemma 3, Theorem 1). Similar low-pass observation and results have also been mentioned by other works by Li et al. (2088) Qiu et al. (0188), and [i et al. (001)). We adopt SGC's two steps simplification and

---

Under review as a conference paper at ICLR 2020
Nede lned (14))
0.3 www 2411
0.25
soloman
saltraa
soltmma
0.7
Wk
Recurey
0.6
0.5
0.4
W2
W.
(f(A)
0.
01
X
X
1000
1500
2000
2500
of Frequincy components
GCN
SGC
gineN
Figure 1: Accuracy by frequency components
Figure 2: A simple realization of gfNN
the graph signal processing perspective (Ortega et al. 2018) to our work and further extend their implications demonstrate when GCN or SGC does not perform well.
We claim the following contributions:
Our first contribution is another proof for (Wu et al. 2019 Theorem 1) using the Courant- Fisher- Weyl's Iss min-max principle. Our result (Theorem 3 Section has the advantage of showing the monotone shrinking of all eigenvalues. In addtion, our proof on generalized eigenvalues is simpler and shorter.
Our second and main contribution is the exploration of cases when SGC or GCN fails to work and the following performance gap Theorem:
Theorem 1 (Informal, see Theorem 7 g). Under Assumption the outcomes of SGC, GCN, and gfNN are similar to those of the corresponding NNs using "true features".
Our third contribution is to empirically verify Assumption 2 since our Theorem 7 Tand 8 are based on this assumption (stated below).
Assumption 2. Input features consist of frequency-limited true features and noise. The true features have sufficient information for the machine learning task.
As base model for analysis, we build a proof of concept model named g/NN (Figure 2
This model
adopts the two steps simplification from SGC with two major differences: 1. We use a two-layers MLP as the classifier; and 2. We use two different filters (low-pass and high-pass). Our theorem 7 implies that, under Assumption 2 both gfNN (with appropriate filter) and GCN Kipf and Welling (2017) have similar high performance. Since gfNN does not require multiplications of the adjacency matrix during the learning phase, it much faster than GCN. Besides, gfNN maintains an expected behavior in the aforementioned cases when other GNN models do not work.
2 GRAPH SIGNAL PROCESSING
Graph signal processing (GSP) regards data on the vertices as signals and applies signal processing techniques to understand the signal characteristics. By combining signals (feature vectors) and graph structure (adjacency matrix its transformations, GSP has inspired the development of learning algorithms on graph-structured data (Shuman et al. (2012). In a standard signal processing problem, it is common to assume the observations contain some noise and the underlying "true signal" has low-frequency Rabiner and Gold (1975). Our Assumption 2 is of similar nature.
Many recent GNNs were built upon results from graph signal processing. The most common practice is to multiply the (augmented) normalized adjucency matrix - 2 with the feature matrix X. The product (I X)X is understood features averaging and propagation. In graph signal processing literature, such operation filters signals on the graph without explicitly performing cigendecomposition on the normalized Laplacian matrix, which requires O(z²) time Vaseghi (2008). Here, refer to this augmented normalized adjacency matrix and its variants as graph filters and propagation matrices interchangeably.
In this section, we introduce the basic concepts of graph signal processing. We adopt recent formulation Girault al. (2018) of graph Fourier transform irregular graphs.
2

---

The graph Fourier transform is a basis expansion by the generalized eigenvectors. Let U = (ui,..., un,] be the matrix whose columns are the generalized eigenvectors. Then, the graph Fourier transform F: Rn + R" is defined by Fx = ;= U T Dr, and the inverse graph Fourier trans- Uš. Note that these are actually the inverse transforms since Under review as a conference paper at ICLR 2020
Let G EV) be simple undirected graph, where V [l....,n] ,n] be the set of Z vertices and & be the set of edges Let A = (az)) E Rux" be the adjacency matrix of G. D diag(d(1),..... ((()) E R be the degree matrix of G, where d(i) the degree of vertex D- AD 1/2 be the normalized Laplacian of G, where I E m==*= is the identity matrix, and Liw -1- A be the random walk Laplacian of G. Also, for 7 E R with 7 > let A A+71 be the augmented adjacency matrix, which is obtained by adding 7 self loops G. = D+1 be the corresponding augmented degree matrix, and ī, = D À I, L 1 D-1/2AD-1/2 Liw = Dー Á be the corresponding augmented combinatorial, normalized, and random walk Laplacian matrices.
Σjev a(i, j)
V. L D E R.** be the combinatorial Laplacian of G.
vector æ E Rn defined on the vertices of the graph is called a graph signal. To introduce graph Fourier transform, we need to define two operations, variation and inner product, on the space of graph signals. Here, we define the variation A: R" + R and the D-inner product by
(xx) = Σ (a(1) =(j))² (i.))E
Læ; (2.0) LL; E -(d(t))))(ibvl)) = x Dy. (1)
We denote by ||=||5 := ((2, i) the norm induced by D. Intuitively, the variation A and the inner product ( specify how to measure the smoothness and importance of the signal, respectively. In particular, our inner product puts more importance on high-degree vertices, where larger Y closes the importance more uniformly. We then consider the generalized eigenvalue problem (variational form): Find u1. uI:...; Un E R" such that for each E (I,...,,) n). , u; is a solution to the following optimization problem:
minimize (u)) subject to (u, u) = 1, (u, 1 0, j E n..
The solution u, is called an i-th generalized eigenvector and the corresponding objective value A == (u,) is called the i-th generalized eigenvalue. The generalized eigenvalues and eigenvectors are also the solutions to the following generalized eigenvalue problem (equation form):
Lu XDu.
Thus, if (A, u) is a generalized eigenpair then (A, D1/2u) an eigenpair of É. A generalized eigenvector with a smaller generalized eigenvalue is smoother in terms of the variation A. Hence, the generalized eigenvalues are referred to as the frequency of the graph.
form F-1 is defined by F
FF U DU = I.
The Parseval identity relates the norms of the data and its Fourier transform:
||ا|ا
||
(4)
Let h: IR + R be an analytic function. The fiter specified by h is a mapping x + y defined by the relation in the frequency domain: ő(A) = hA))a(A). In the spatial domain, the above equation is equivalent to y hL..)).. where h h(L,,)) is defined via the Taylor expansion of h; see Higham (2008) for the detail of matrix functions.
In machine learning problem on a graph, each vertex E V has d-dimensional feature x(i) Rdd We regard the features as d graph signals and define the graph Fourier transform of the features by the graph Fourier transform of each signal. Let X [x(1):.... (0.j,..,,,((,,,)), x(n)) be the feature matrix. Then, the graph Fourier transform is represented by FX X =: UT かx and the inverse transform is - = U X. We denote X = [x(A1);..... :x(,)) as the frequency components of X.
..,
We only consider unweighted edges but it is easily adopted to positively weighted edges.
3

---

Under review as a conference paper at ICLR 2020
3 EMPIRICAL EVIDENCE OF ASSUMPTION 2
The results of this paper deeply depend on Assumption Thus, we first verify this assumption in real-world datasets: Cora, Citeseer, and Pubmed [Sen al. (2008). These citation networks, in which vertices are scientific papers and edges are citations. We consider the following experimental setting: 1. Compute the graph Fourier basis U from Ł; 2. Add Gaussian noise to the input features:
X' + X' + (N x²) for o = {0, 0.01, 0.05); ; 3. Compute the first k-frequency component: Xr = U|: A] X1/2x;; 4. Reconstruct the features: X D-1//U' &) 5. Train and report test accuracy
of 2-layers perceptron the reconstructed features Xg. Figure plots fine-graine frequency components experiment on Cora without early stopping.
Noise (o):
0.05
citescer
pubmed
Accuracy
0.6
0.5
04
0.2
Number frequency components
Figure Average performance of 2-layers MI.Ps on frequency-limited feature vectors with early stop- ping using the validation data (ma seexx_xpchh=500 The two horizontal lines show the performance of our model and a 2-layers MLP on original feature.
In Figure we incrementally add normalized Laplacian frequency components to reconstruct feature vectors and train a 2-layers MIPs. We see that all three datasets exhibit a low-frequency nature. The classification accuracy of 2-layers MIP tends to peak within the top 20% of the spectrum (green boxes). By adding artificial Gaussian noise, we observe that the performance at low-frequency regions is relatively robust, which implies a considerable denoising effec
These experiments have confirmed our assumption that the informative features (to given set of labels) lie in a low-frequency region in the three benchmark datasets. Note that such low-frequency nature, while coincides with low intrinsic dimensionality, has different behavior. For instance, we will show later that despite having low intrinsic dimensionality, high-frequency sets of features and labels lead to bad performance in both GCN and SGC. Interestingly. we observe the same performance degradation other message- pagggnggg models like GraphSAGE (Hamilton et al., 2017).
We further confirm the low-frequest frequency nature of the benchmark datasets' labels by computing the Rayleigh quotient for each label type the dataset. Note that our Laplacian normalized, the maximum value of Rayleigh quotient (corresponds to the highest eigenvalue) is 2. Figure cllearl shows the low- www-frquency nature of the labels in Cora, Citeseer, Pubmed, and Reddit datasets.
4 MULTIPLYING ADIACENCY MATRIX IS Low PASS FILTERING
Computing the low- low-frequency components is expensive since requires 0(V23) time to compute the eigenvalue decomposition of the Laplacian matrix. Thus, a reasonable alternative is to use a low-pass filter. Many papers on graph neural networks iteratively multiply the (augmented) adjacency matrix Anw (or Á) to propagate information. In this section, we see that this operation corresponds to a low-pass filter.
As proven in previous work, multiplying the normalized adjacency matrix corresponds to applying graph filter h(A) 1 X (Wu et al. 2019: Li et al. 2018 2019). Since the cigenvalues of the normalized Laplacian lie on the interval [0, 2]. this operation resembles a band-stop filter that removes intermediate frequency components. However, since the maximum eigenvalue of the normalized Laplacian is 2 if and only if the graph contains a non-trivial bipartite graph as a connected
component (Chung) 1997 Lemma 1.7). Therefore, for other graphs, multiplying the normalized
Thhe standard deviation of clean signal less than 0.01 for all three datasets. See Table for more detail.
4

---

Under review as a conference paper at ICLR 2020
pubmed
Badaahh
roddlt
Bayfcah custore.
Label
Figure 4: Rayleigh quotients of one-hot encoded label vectors for Cora, Citeseer, Pubmed, and Reddit
angn-eugm)tted) adjacency matrix acts as a low-pass filter (i.e., high-frequent components must decrease). We can increase the low-pass filtering effect by adding self-loops (i.e., considering the augmented adjacency matrix) since shrinks the eigenvalues toward zero as follows
Theorem 3. Let (x(7) be the i-th smallest generalized eigenvalue of (i, L) =D++1l Then, X.(7) is non-negative number, and monotonically non-increasing in 0. Moreover, )a(7) is
strictly monotonically decreasing if (:(0) # O.
Note that y cannot be too large. Otherwise, all the eigenvalues would be concentrated around zero, ie., all the data would be regarded as Slow-frequency hence, we cannot extract useful information from the low-frequency components. In practice, 7 is often set at (Kipf and Welling. 2017).
From another point of view, the graph filter (a()) = 1 X can also be derived from first-order approximation of Laplacian regularized least squares Belkin and Niyogi (2004). Let consider the problem of estimating a low-frequency true feature [x()) from the observation (x(i) Then, natural optimization problem is given by
min Σ |x(1) - x(1)
(x))) 4(X)
(5)
TEV
where A(X) = Ep Ax)())). Note that, since A(X) = ExEA A1(((1) it is maximum
posteriori estimation with the prior distribution of &(() N 7/)). The optimal solution this problem is given by X = (I + - The corresponding filter is (A()) = (1 + A)- and hence h(A) 1- À is its first-order Taylor approximation.
5 BIAS- VARIANCE TRADE-OFF FOR Low PASS FILTERS
In the rest of this paper, we establish theoretical results under Assumption a more precise assumption as follows.
To be concrete, we pose
Assumption (Precise Version of the First Part of Assumption consists of true features (x(i))ev and noise {z(i)}ev. The true features have frequency at most 0 < e & 1 and the noise follows white Gaussian noise, i.e.. each entry of the graph Fourier transform of independenty identically follows a normal distribution N(0, o²).
2 Observed features (x(i) heev
Using this assumption,
evaluate the effect of the low-pass filter follows.
Lemma 5. Suppose Assumption 4 For any 0 < å < 1/2, with probability at least 1 - 8, we have
X A X|In
s kke X + O (Voog(1/8))(((), V
Ell Z1]n]
(6)
'The shrinking of the maximum eigenvalue has already been proved in (Wu et al. 2019 Theorem 1), Our theorem is stronger than theirs since show the "monotone shrinking" of "all" the eigenvalues. In addition, our proof is simpler and shorter.

---

Under review as a conference paper at ICLR 2020
where R(2k) is a probability that random walk with random initial vertex returns the initial vertex after 2k steps.
The first and second terms of the right-hand side of equation are the bias term incurred by applying the filter and the variance term incurred from the filtered noise, respectively. Under the assumption, the bias increases a little, say. O(vc). The variance term decreases in O(1 /d//dg///2 where deg is typical degree of the graph since R(2k) typically behaves like ((1/deg' ) for small & Therefore, we can obtain a more accurate estimation the true data from the noisy observation by multiplying the adjacency matrix if the maximum frequency of X is much smaller than the noise-to-signal ratio | | I|
This theorem also suggest choice of k. By minimizing the right-hand side by k obtain:
Corollary 6. Suppose that E|[lZ|| b) S x|| D for some = O(1). Let k' be defined by k" and suppose that there exist constants Ca and d such that R(2k) Ca/d
Ologg(0g(1//)p) for k S k". Then, by choosing k*, the right-hand side of equation 6 is Ō(ve)
This concludes that we can obtain an estimation of the true features with accuracy Ö(Vi) by multiplying Arw several times.
6 GRAPH FILTER NEURAL NETWORK
In the previous section, we see that low-pass filtered features At X are accurate estimations of the true features with high probability. In this section, analyze the performance of this operation. In practice, k = 2 is sufficient for most datasets. Therefore, for simplicity, we set k =. 2.
Let the multi-layer (two-layer) perceptron be
hMnP(X|Wi, W2) - 02 (X
(7)
where 01 is the entry-wise ReLU function, and 0g is the softmax function. Note that both or and 02 are contraction maps, i.e., (Xx I S | - -YIID
gfNN As toy model for analysis and experiments, we define our gINN models. comes with two flavors: low-frequency and high-frequency. In this section, we provide the analysis for the low-frequency version and emprical results (Section ( for high-frequency version.
X NgNNN-oww (X, AWW,, W2) 1MPP( X|W, W2)
(8)
harNN-high (X, A,W, W2) /MLP (2, X ( W2)
(9)
Under the second part of Assumption our goal to obtain a result similar to h(XWW, W2). The simplest approach is train a multi-layer perceptron (XMLP([[i,, W2) with the observed feature. The performance of this approach is evaluated by
(1 W2) hMuP(X W1, W2)l b < [Z)))P(W)))(W)))
(10)
where p(W) is the maximum singular value of W.
Now, we consider applying graph filter Å&e to the features, then learning with a multi-layer perceptron, i.e., h X W2). Using Lemma we obtain the following result.
Theorem 7. Suppose Assumption 4 and conditions in Corollary 6 with probability at least 1 for < 1/22,
By choosing k as Corollary 6
| W2) hMur (Ag, X Wo)lll Ö
(11)
This means that if the maximum frequency of the true data is small, we obtain a solution similar to the optimal one.
"This exactly holds for class of locally tree-like graphs Dembo random graphs and the configuration models. *O(-) suppresses logarithmic dependencies.
gempbo et al. 2013). which includes Erdos-Rent

---

Under review as a conference paper at ICLR 2020
Comparison with GCN Under the same assumption, analyze the performance of two- layers GCN. The GCN is given by
hoCK (X W2) = (A,,
(12)
Theorem 8. Under the same assumption to Theorem 7
we have
| ( W1, W2) hack ( Wo S O(V0)))1Z)ol
(13)
This theorem means that GCN also has a performance similar to MLP for true features. Hence, in the limit of 0 and Z + all MLP, GCN, and the gfNN have the same performance.
In practice, gfNN has two advantages over GCN. First, gfNN is faster than GCN since it does not use the graph during the training. Second, GCN has risk of overfitting to the noise. When the noise is so large that cannot be reduced by the first-order low-pass filter, Arw the inner weight W1 is trained using noisy features, which would overfit to the noise leading to low test accuracy.
Comparison with SGC Recall that degree-2 SGC is given by
h XW2))
(14)
i.e., it a gfNN with a one-layer perceptron. Thus, by the same discussion, SGC has a performance similar to the perceptron (instead of the MLP) applied to the true feature. This clarifies an issue of SGC: the true features are non-linearly separable, SGC cannot learn the correct function.
EXPERIMENTS
We first show the advantage of models like gfNN-low and SGC over GCN by injecting Gaussian noise to the three benchmark citation networks. In accordance with Theorem g we that GCN-like models have low noise tolerance while gfNN-low and SGC are much more robust. Our experiments on citation networks are conducted in the same transductive setting used by Kipf and Welling (0017)
and Wu et al. 2019). Training details are provided in Appendix and C.
Experimental results in Figure[Jcoonfrms our hypothesis for the three benchmark datasets. We see that when a high level of noise is injected to fow-frequency datasets (especially Cora), the performance of GCN can degrade much faster than SGC or gfNN. is also trivial (LG) and MLP on raw features exhibit similar behavior when noise is introduced.
that Logistic Regression
g/NN (1oo))
SGC
*
GCN
+
LG
MLP
pubmed
0.8
0.7
0.6
Accuracy
0.4
0.2
0.00
0.01
0.02
0.03
0.04
0.05
0.00
0.01
0.02
0.03
0.04
0.05
0.00
0.01
0.02
0.03
0.04
0.05
Noice (o)
Noise (o)
Noise (0)
Figure 5: Benchmark test accuracy on Cora (left), Citeseer (middle), and Pubmed (right) datasets. The noise level is measured by standard deviation of white noise added to the features.
Next, we experiment on two synthetic datasets: Two Circles and BA-High. These datasets are synthesized to show: SGC cannot learn non-linearly separable features; and 2. SGC, GCN, DGI (Veličković al. 2019), and GraphS (Hamilton et al. 2017) fail when it comes to high-frequency labels (even when the features are informative). Two circles dataset is generated by generating 4, 000 points sampled from two nested circles and define a 5-nearest neighbors graph the data points. Visualization of this dataset is given in Appendix E. We generate BA-High dataset by constructing BA-graph with 200 and
10 (200 nodes, every new node are attached to 10 neighbors
7

---

Under review as a conference paper at ICLR 2020
selected from existing nodes). We then find the maximal independent set for the graph and use this set as label 1. The rest the nodes are label O. For each node with label 1, we generate a 50-dimensions feature vector from Gaussian (+e, 1.0). We do the same for all nodes with label but with Gaussian W(-c, 1.0). In Table 1 we report the results at 0.5.
Unsurprisingly, SGC cannot learn the non-linearly separable feature in the Two Circle experiment (Table I while other more complex models perform as expected (similar performance as an MLP). More interesting is the results of the BA-High experiment (Table Figure/6). Surprisingly, we find all popular GNN models cannot quite learn under this simple setting. Although the node features are informative (a simple LogReg MLP can have accuracy larger than 90%), most GNN models reported less than 60% accuracy. In Figure we show a simple solution to this setting: Use high frequency eigenvectors or high-pass filter (giNN-High).
SGC (km))
GCN
High-fiie Eigenvectors (last
C4
13
SGC (K=3)
GraphSAGE
gfNNU-High
4.3
Figure 6: Performance on freuueryyyyncy labels
For comparison purpose, we present our results benchmark datasets in Table 1 Model details presented in Appendix C. Dataset details are presented in Table (Appendix E).
Table 1: Average test accuracy original train/val/test splits (50 times)
Cora
Citeseer
Pubmed
Reddit
2Circles
BA BA-Higg
DGI
83.1 1 0.2
72.1 0.1
80.1 1 0.2
94.5 1 0.3
99.2 0.1
85.2
0.6
54.6 1 1.8
GCN
80.0
6.1
79.3 1.3
84.9 - 0.8
+8.9-222
SGC
77.6 2.2
65.6
78.4 1.1
94.9 0.2
89.0
53.5 1.4
55.5 +
g(NN-low giNN-high
82.3
71.8
7.2
94.8 0.2
89.3
0.8
55.4 2.3
24.2
22.5 22.5222
43.6 1.3
10.3 226
86.6
48.3 1835355
96.2 4 1.0
DISCUSSION
Recently, Kampffmeyer et al. (2019) observed that GCN models might have too strong Laplacian smoothing effect (low-Irequency in our terms) for zero-shot learning application. This is an example of an application where the frequency of data might be band-limiter or higher than benchmark graph datasets. Some other possible scenario in a social network might include more complex and high-frequency nature that GNN models like GCN cannot learn well. One possible solution to this scenario is to use both low- and high-pass filters like gfNN and select the model by validation data or leam from both filters.
Our analysis and experimental results showed that GNN models work well on benchmark datasets because these datasets have the low-frequency nature in both feature vectors and labels. With high- frequency labels, popular GNN models will perform badly. While there is not yet any real-world benchmark dataset which node labels are of high-frequende nature, such setting is not entirely impossible given the complexity a network. For instance, a relationship network would be less likely to have same-gender links. Therefore, gender labels might exhibit high-frequency nature.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima's an. Graph convo- lutional encoders for syntax-aware neural machine translation. Empirical Methods in Natural Language Processing, 2017.
Mikhail Belkin and Partha Niyogi. Semi-supervised learning riemannian manifolds. Machine Learning, 56(1-3):209-236 2004.
Rajendra Bhatia. Matrix analysis, volume 169, Springer Science & Business Media, 2013.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. International Conference Learning Representations, 2018.
Fan 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, pages 3844-3852, 2016.
Amir Dembo, Andrea Montanari, and Nike Sun. Factor models on locally tree-like graphs. The Annals of Probability, 1166)44162-4213, 2013.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. SplineCNN: Fast geometric deep learning with continuous B-spline kernels. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Advances in Neural Information Processing Systems, pages 6530-6539, 2017.
Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. International Conference on Learning Representations, 2017.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 1263-1272. JMLR, 2017.
Benjamin Girault, Antonio Ortega, and Shrikanth S. Narayanan. Irreullarit- graph fourier transforms. IEEE Transactions on Signal Processing, 66(21):5746-5761 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
Nicholas Higham. Functions of matrices: theory and computation, volume 104. SIAM, 2008
Michael Kampffmeyer, Yinbo Chen, Xiaodan Liang, Hao Wang, Yujia Zhang, and Eric Xing. Rethinking knowledge graph propagation for zero-shot learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1 11887-1 1496, 2019.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. arXiv preprint 1rXiv:1905.04990 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
In International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations, 2019,
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.

---

Under review as a conference paper at ICLR 2020
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9582-9591, 2019.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. arXiv preprint UrXiv:190100444 2019.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5)8808-288 82008-828.00 2018.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 459 4699467.42 ACM, 2018.
Lawrence R. Rabiner and Bernard Gold. Theory and application of digital signal processing. Englewood Cliffs, NJ, Prentice-Hall, Inc., 1975.
Adam Santoro, David Raposo, David G. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. simple neural network module for relational reasoning. In Advances in Neural Information Processing Systems, pages 4967-4976, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rar Collective classification network data. Al magazine, 29(3):93-93, 2008
David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending digh-dimessional data analysis to networks and other irregular domains. arXiv preprint arXiv:/211.0053 2012.
Saeed V. Vaseghi. Advanced digital signal processing and noise reduction. John Wiley & Sons, 2008.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2017.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. International Conference on Learning Representations, 2019.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on International Conference on Machine Learning, volume 97. JMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representationss 2019.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit-Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In Proceedings of the Thirty Fourth Conference on Uncertainty in Artificial Intelligence (UAI), 2018a.
Yuhao Zhang, Peng Qi, and Christopher D. Manning. Graph convolution over pruned dependency trees improves relation extraction. Empirical Methods in Natural Language Processing, 2018b.
Marinka Zimik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 3311119199- 2017.
10

---

Under review as a conference paper at ICLR 2020
APPENDIX
A PROOFS
Proof of Theorem 3 Since the generalized eigenvalues of (D + y1, L) are the eigenvalues of positive semidefinit matrix (D + + + - these are non-negative real numbers. To
obtain the shrinking result, we use the Suurant-Fisher-e Weyl's min-max principle (Bhatia 2013
Corollary III. 1.2): For any 0 S 71 < 72,
x. La (D 721)x x Lx
A1(12) =
min H Hssubspace, 2,
max
(15)
min
max
(16)
H mubsspace (inbpporrdi(()=iivEEHe T T 111)
= -x()))
(17)
Here, the second inequality follows because x (D <x xT + 72)x for all + 0 Hence, the inequality is strict if x. Lx & O, i.e {x(71) + 0.
Lemma 9. If X has a frequency at most then [Ib[C)||3 < max x(t)|
Proof. By the Parseval identity,
||
Σ (())|
(18)
I max h(t) Σ |*{())1
(19)
1E[0,c]
AEA
max rE[U,c] x+t]||
(20)
max h(t]| rE[0.e]
(21)
n
Proof of Lemma
5
By substituting X = X + Z, we obtain
|| - X X - [|([ ) D +
(22)
By Lemma 9 the first term is bounded by v vkel X n- By the Parseval identity equation the second term is evaluated by
(1- -
[ 1((2)11
(23)
AEA
Σ
(1 A)2k 2(h,
(24)
AEA.PE(I (I....a)
By (Laurent and Massart
2000 Lemma 1), we have
Prob
Σ (1 ^)2* (s(A, -2) 1) 1)22
A)ak E (1- 21 St
(25)
A.p
A.p
By substituting
log(1/8) with 8 - 1/2, we obtain
Ex(1 222h 2)2h
Prob
2(, 2 50 foondlog(1//)
< - 5.
(26)
A.p
Note that E] = ad and
E1 2)2h
Lr( A2(
R(2k)
(27)
since (i.j) entry of A2k is the probability that a random walk starting from i E V is on j E V at 24 step, we obtain the lemma.
11

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 7 By the Lipschitz continuity of o, we have
||/MLP X W1, W2) hMLP (A. W2)ll s ||x A X (ID((W))((W))
(28)
By using Lemma 5 obtain the result.
Lemma 10. If X has a frequency at most e then there exists Y such that Y has a frequency at most ve and (X) - 3 S |
Proof. We choose Y by truncating the frequency components greater than vc. Then,
[x((X) - -12 = Σ
(a)(1)
(29)
Xeve
1
(A)
(30)
Ve
Σ
[((x(())
(31)
(U,i)E
E
[a(u)) - x
(32)
(LDDER
(33)
$ (((()
(34)
V.
(35)
Proof of Theorem 8 From Lemma 10 by taking the square root and absolute values of both sides,
we have (Xa Y < 1/4 |/
By setting Y = ar AArm X), since is an activation function, we have:
[lo(8) -
= = (X)Il
(36)
(37)
Consequently, we consider the D-norm stated in Theorem 8
11 (XW:))) XAw,
(38)
s (10((W1) A ( (Am p(Wa)
(39)
(I1Lo | Å X (oo((W)) p(W2)
(40)
< (1(11111811 H0)) p(W2)
(41)
B GFNN MODEL DETAILS
Our gfNN model is implemented in Pytorch. While other number of hidden layers are possible, we find that 1 hidden layer with 256 units (2 layers MLP) is enough for all benchmark datasets. Other changes does not significantly influence the experimental results. It worth mentioning that each gINN model actually has identical neural networks inside, one to learn from low-pass filter Anw and the other for high-pass filter L.w. We use PReLU (0.25) as the activation function since there are a slight improvement (about 1 1%) in validation accuracy when training with PReLU compare ReLU.
To optimize our model. we use the Pytorch built-in Adam optimizer. We fix the hyperparameters accross all datasets:
12

---

Under review as a conference paper at ICLR 2020
Weight decay: 1 x 10
Learning rate: 0.01
Batch size: 32
Early stopping: 40 epochs patience (Max. 500 epochs).
All datasets have three sets: train, valdiation, and test. The validation set is used for early stopping and model selection (high/low). The test accuracy reported for all experiments.
C BASELINE DETAILS
We set GCN Kipf and Welling 2017) at two layers with 64 hidden units, ReLU activation, no dropout. keep the setting SGC (Wu et al. 2019) as recommended by the original implementation (200 epochs, 1r=0.1, weight decay: 1 X 10 ReLU activation). For DGI (Veličković et al. 2019), GraphSAGE Hamilton et al. (017). and GIN (Xu et al., (019). we follow the authors' default paramter tuning. The result for GraphSAGE is reported the best result from "small" models (mean,
sum, seq) for 200 epochs training, we also set number of level-1 neighbors at 25 and level-2 at 10.
D DATASET DETAILS
We provide evaluation for the semi-supervised node classification performance of SGC the Cora, Citeseer, and Pubmed citation network datasets Sen et al. (2008). We also follow Wu et al. (0019) run experiments on Reddit Chen et (2018) and Hamilton al. (0117) PPI Zitnik and Leskoved 2017).
Table 2: Rorldworld benchmark datasets and synthetic datasets for vertex classification
Dataset
Nodes
Edges
Features (X)
(xx,ox)
Classes
Train/Val/Test
Cora
2,708
5,278
1,433
(0.0007, 0.0071)
7
140/500/1. 1,000
Citeseer
3,327
4,732
3,703
(0.0003, 0.0029)
6
120/500/1, (000000/0000000000000
Pubmed
19,717
44,338
500
(0.0019, 0.0087)
3
60/500/1. ,000
Reddit
231,443
11,606,919
602
151, 151,708/23,699/55553
PPI
56,944
818,716
121
44,906/6.514/55524
Two Circles
4,000
10,000
2
2
80/80/3,840
BA-High
200
2000
50
(0,1)
2
10/10/180
The Two Circle dataset is visually presented in Figure 7 (test accuracies are shown in the corner). The coordinates of each data point are used as features.
Original data
SGC
GCN
gfNN
4,485
0.862
0.872
Figure 7: Decision boundaries on 500 generated data samples following the two circles pattern
BA-High dataset generation procedure is described in Figure
We have similar experimental results on different type random graphs: ER, Configuation, and Block Model. The experimental results GCN/SGC can be explained simply with Figure 9
In Figure 2 the color blue and orange indicate label and label 0 a 100 node BA-graph. is trivial to see that any simple machine learning model can learn from the original feature. However, after only one filter, the features become indistinguisable. More low-pass filter applications will lead to uniform feature (Theorem
13

---

Under review as a conference paper at ICLR 2020
L.)
((-+
Generate G
Find maximal indep. set
Assign random signal
Figure 8: BA-High generation steps
Signal Shift Phenomenon
10
Original
Value
-5
10
Filtered (k=1)
-10-
Vertex Index
Figure 9: Plot for dimensional features in BA-High setting. We set e = 5.0 for clarity purpose.
14


Reviews:
[{"review_id": "rklob41CKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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\nSeveral theoretical analyses have been conducted on MPNN-type NNs. On the other hand, although many graph neural network models take the approach of graph filtering, there is little theoretical analysis on graph NNs that take the filtering approach. This paper analyzed the learnability of filtering type graph NNs.\nFirst, the authors hypothesized that the data used practical tasks consisted of true low-frequency information and high-frequency noise (Assumption 2), and verified the correctness of the assumption.\nNext, the authors quantitatively evaluated the difference between the case where we feed noisy data to a graph NN and the case where we feed noiseless data to an MLP. The authors showed that a two-layer GCN approximately behaves as a noise-filtering + a two-layered MLP (Theorem 8). Based on this observation, the authors proposed gfNN, which directly models the latter architecture. We can interpret gfNN as an SGC whose final linear transformation is replaced with an MLP.\nFinally, the authors empirically showed that gfNN achieved the same level of accuracy as existing GNNs in the citation network tasks. Furthermore, the authors created a dataset that has meaningful information in the high-frequency area (BA-High). It was shown that the existing GNN, including gfNN, did not perform well, while a GNN designed to pass high frequency (gfNN-high) can predict accurately.\n\n\nDecision\n\nI judge that this paper contributes to deepning the understanding of graph NNs and is worth to be accepted based on the following three points.\nFirst, it enabled us to understand what causes the oversmoothing phenomena. Several studies have shown that Laplacian-type graph convolution works as a low pass filter. However, most of them considered a linear setting and did not explain how the graph convolution behaves when a graph NN has non-linear activation functions. Compared to them, their result admits non-linearity.\nSecond, by showing that we can approximate a GCN by a noise filter followed by an MLP, this paper has made the relationship between a GCN and an SGC clearer.\nFinally, the authors experimentally showed that existing graph NNs do not have predictive power when useful information is in high-frequency domains. It gives insights on what graph NNs can and cannot solve.\nFor these reasons, I think this paper has contributed to a deeper understanding of graph NNs and sufficiently significant.\n\n\nSuggestions\n\n- If I understand correctly, the title of Section 4 reflects the content of Lemma 5 in Section 5 rather than the content of Theorem 3 and (5). I recommend the authors to reconsider the titles of Sections 4 and 5.\n- Could you add more explanations to the proof of Theorem 8 in Appendix A. Especially, I could not understand how the term $\\tilde{O}(\\epsilon^{1/4})$ is derived.\n\n\nQuestions\n\n- I could not find implementations of graph NNs in the notebook to the code (I only found the ls result of dataset directories). Do you plan to release the experiment code?\n- At the beginning of Section 6, the authors wrote that they set $k$ to $2$ (hence two-layered GNNs are in consideration). But Theorems 7 and 8 considered the optimal $k^\\ast$ in Corollary 6. Which is correct?\n- In Section 3, the authors claimed that the performance of MLPs is relatively more robust to the Gaussian noise in the low-frequency regime compared to the high-frequency regime. Certainly, the decrease in performance at $\\sigma = 0.01$ is massive in the high-frequency setting for the CiteSeer dataset. However, it is hard to see this trend in Cora and Pubmed. Therefore, I think it is a little too aggressive to conclude that claim.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxiGab2tS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper shows the graph signal convolution in GCN-based models is typically a low-pass filter. Besides, the authors propose a simplified GCN-framework named gfNN, which is demonstrated on various benchmark datasets.  To be honest, the paper is well-motivated, well-written. And,  I enjoyed reading through the paper. \n\nHowever, I have some concerns regarding the technical contributions of this paper.\n(1) \"GNN is a low-pass filter\" is not a new observation. Various works (SGC, [Shuman, et al., 2013]) have studied this observation before. \n(2) If the frequency of the label vector is higher than the threshold of the low-pass filter (e.g., gfNN), will the model be problematic? \n(3) It seems the only difference between SGC and gfNN is that gfNN is equipped with one more hidden layer. The authors claim that gfNN perform better than SGC is because \"the true features are non-linearly separable\". If it is the case, then the technical contribution of gfNN is trivial. \n\nOverall, I still like this paper due to its interesting point of the presentation. I vote for weak accept, but I am fine if it is rejected. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1xVuu6aKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The authors extend the existing work SGC [1] to a nonlinear version, which addresses the limitations of dealing with nonlinear feature. It further extends the theoretical finding in [1] about the low-pass filtering functionality of graph convolutional networks and shows its advantage in dealing with graph signal processing problem. Evaluation of the proposed method is performed on 7 datasets for node classification task.\nPros:\n1. This work goes into detail of the theoretical finding of SGC.\n2. Authors conduct extensive experiments on multiple datasets.\nCons:\n1. The proposed graph neural network mode is an extension of the existing model SGC, which address the limitation of SGC to model the node feature nonlinearity. It is a good extension, but the novelty is limited.\n2. Authors further extend the theoretical finding in [1] and verify the fact that low-pass filtering functionality of graph neural network provide better noise robustness than two layer MLP. It has some novelty, but the novelty is incremental.\n3. In the experiment, the performance gap between SGC and gfNN is very small on noise robustness study and traditional node classification. The performance gap between GCN and gfNN is also small on noise robustness study is also small, which can not support the conclusion \"GCN has a risk of overfitting to the noise\"\n4. The paper has the problem of notation missing, e.g on page 2, Fig1 is never mentioned; on page 7, the notation of \"LG\" is missed in Fig 5.\n5. The code link is given but no code is missing.\n[1]Wu, Tianyi Zhang, Amauri Holanda de Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q.Weinberger. Simplifying graph convolutional networks. ICML2019\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies two-layer graph convolutional networks and two-layer multi-layer perceptions and develops quantitative results of their effect in signal processing settings. The paper received 3 reviews by experts working in this area. R1 recommends Weak Accept, indicating that the paper provides some useful insight (e.g. into when graph neural networks are or are not appropriate for particular problems) and poses some specific technical questions. In follow up discussions after the author response, R1 and authors agree that there are some over claims in the paper but that these could be addressed with some toning down of claims and additional discussion. R2 recommends Weak Accept but raises several concerns about the technical contribution of the paper, indicating that some of the conclusions were already known or are unsurprising. R2 concludes "I vote for weak accept, but I am fine if it is rejected." R3 recommends Reject, also questioning the significance of the technical contribution and whether some of the conclusions are well-supported by experiments, as well as some minor concerns about clarity of writing. In their thoughtful responses, authors acknowledge these concerns.  Given the split decision, the AC also read the paper. While it is clear it has significant merit, the concerns about significance of the contribution and support for conclusions (as acknowledged by authors) are important, and the AC feels a revision of the paper and another round of peer review is really needed to flesh these issues out. 
Decision: Reject