Title: 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 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 cases 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).
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-art performance (Kipf and Welling, 2017; 

:

Under review as a conference paper at ICLR 2020 the graph signal processing perspective (Ortega et al., 2018) to our work and further extend their implications to 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 min-max principle. Our result (Theorem 3, Section 4) 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, 8). Under Assumption 2, 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 and 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 a base model for analysis, we build a proof of concept model named gfNN (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 is 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 or 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 adjacency matrix I -L with the feature matrix X . The product (I -L)X is understood as features averaging and propagation. In graph signal processing literature, such operation filters signals on the graph without explicitly performing eigendecomposition on the normalized Laplacian matrix, which requires O(n 3 ) time Vaseghi (2008) . Here, we 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 a recent formulation Girault et al. (2018) of graph Fourier transform on irregular graphs.

Let G = (V, E) be a simple undirected graph, where V = {1, . . . , n} be the set of n ∈ Z vertices and E be the set of edges.1 Let A = (a ij ) ∈ R n×n be the adjacency matrix of G, D = diag(d(1), . . . , d(n)) ∈ R n×n be the degree matrix of G, where d(i) = j∈V a(i, j) is the degree of vertex i ∈ V. L = D -A ∈ R n×n be the combinatorial Laplacian of G, L = I -D -1/2 AD -1/2 be the normalized Laplacian of G, where I ∈ R n×n is the identity matrix, and L rw = I-D -1 A be the random walk Laplacian of G. Also, for γ ∈ R with γ > 0, let Ã = A+γI be the augmented adjacency matrix, which is obtained by adding γ self loops to G, D = D + γI be the corresponding augmented degree matrix, and L = D -Ã = L, L = I -D-1/2 Ã D-1/2 , Lrw = I -D-1 Ã be the corresponding augmented combinatorial, normalized, and random walk Laplacian matrices.

A vector x ∈ R n defined on the vertices of the graph is called a graph signal. To introduce a graph Fourier transform, we need to define two operations, variation and inner product, on the space of graph signals. Here, we define the variation ∆ : R n → R and the D-inner product by

∆(x) := (i,j)∈E (x(i) -x(j)) 2 = x Lx; (x, y) D := i∈V (d(i) + γ)x(i)y(i) = x Dy. (1)

We denote by x D := (x, x) D the norm induced by D. Intuitively, the variation ∆ and the inner product (•, •) D 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 γ closes the importance more uniformly. We then consider the generalized eigenvalue problem (variational form): Find u 1 , . . . , u n ∈ R n such that for each i ∈ {1, . . . , n}, u i is a solution to the following optimization problem: minimize ∆(u) subject to (u, u) D = 1, (u, u j ) D = 0, j ∈ {1, . . . , n}.

(

The solution u i is called an i-th generalized eigenvector and the corresponding objective value λ i := ∆(u i ) is called the i-th generalized eigenvalue. The generalized eigenvalues and eigenvectors are also the solutions to the following generalized eigenvalue problem (equation form):

EQUATION

Thus, if (λ, u) is a generalized eigenpair then (λ, D1/2 u) is an eigenpair of L. A generalized eigenvector with a smaller generalized eigenvalue is smoother in terms of the variation ∆. Hence, the generalized eigenvalues are referred to as the frequency of the graph.

The graph Fourier transform is a basis expansion by the generalized eigenvectors. Let U = [u 1 , . . . , u n ] be the matrix whose columns are the generalized eigenvectors. Then, the graph Fourier transform F : R n → R n is defined by Fx = x := U Dx, and the inverse graph Fourier transform F -1 is defined by F -1 x = U x. Note that these are actually the inverse transforms since

FF -1 = U DU = I.

The Parseval identity relates the norms of the data and its Fourier transform:

EQUATION

)

Let h : R → R be an analytic function. The graph filter specified by h is a mapping x → y defined by the relation in the frequency domain: ŷ(λ) = h(λ)x(λ). In the spatial domain, the above equation is equivalent to y = h( Lrw )x. where h( Lrw ) is defined via the Taylor expansion of h; see Higham (2008) for the detail of matrix functions.

In a machine learning problem on a graph, each vertex i ∈ V has a d-dimensional feature x(i) ∈ R d . 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); . . . , x(n)] be the feature matrix. Then, the graph Fourier transform is represented by FX = X =: U DX and the inverse transform is F -1 X = U X. We denote X = [x(λ 1 ); . . . ; x(λ n )] as the frequency components of X.

3. EMPIRICAL EVIDENCE OF ASSUMPTION 2:

The results of this paper deeply depend on Assumption 2. Thus, we first verify this assumption in real-world datasets: Cora, Citeseer, and Pubmed Sen et al. (2008) . These are 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 L; 2. Add Gaussian noise to the input features: In Figure 3 , we incrementally add normalized Laplacian frequency components to reconstruct feature vectors and train a 2-layers MLPs. We see that all three datasets exhibit a low-frequency nature.

X ← X + N (0, σ 2 ) for σ = {0,

The classification accuracy of a 2-layers MLP 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 effect2 .

These experiments have confirmed our assumption that the informative features (to a 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 a low intrinsic dimensionality, high-frequency sets of features and labels lead to a bad performance in both GCN and SGC. Interestingly, we observe the same performance degradation in other message-passing models like GraphSAGE (Hamilton et al., 2017) .

We further confirm the low-frequency nature of the benchmark datasets' labels by computing the Rayleigh quotient for each label type in the dataset. Note that our Laplacian is normalized, the maximum value of Rayleigh quotient (corresponds to the highest eigenvalue) is 2. Figure 4 clearly shows the low-frequency nature of the labels in Cora, Citeseer, Pubmed, and Reddit datasets.

4. MULTIPLYING ADJACENCY MATRIX IS LOW PASS FILTERING:

Computing the low-frequency components is expensive since it requires O(|V| 3 ) 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 Ãrw (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(λ) = 1 -λ (Wu et al., 2019; Li et al., 2018; 2019) Theorem 3. Let λ i (γ) be the i-th smallest generalized eigenvalue of ( D, L) = (D + γI). Then, λ i (γ) is a non-negative number, and monotonically non-increasing in γ ≥ 0. Moreover, λ i (γ) is strictly monotonically decreasing if λ i (0) = 0.

Note that γ cannot be too large. Otherwise, all the eigenvalues would be concentrated around zero, i.e., all the data would be regarded as "low-frequency"; hence, we cannot extract useful information from the low-frequency components. In practice, γ is often set at 1 (Kipf and Welling, 2017) .

From another point of view, the graph filter h(λ) = 1 -λ can also be derived from a first-order approximation of a Laplacian regularized least squares Belkin and Niyogi (2004) . Let us consider the problem of estimating a low-frequency true feature {x(i)} i∈V from the observation {x(i)} i∈V .

Then, a natural optimization problem is given by

EQUATION

where

∆( X) = d p=1 ∆(x(i) p ). Note that, since ∆( X) = λ∈Λ λ x(λ) 2 2

, it is a maximum a posteriori estimation with the prior distribution of x(λ) ∼ N (0, I/λ). The optimal solution to this problem is given by X = (I + Lrw ) -1 X. The corresponding filter is h (λ) = (1 + λ) -1 , and hence h(λ) = 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 2. To be concrete, we pose a more precise assumption as follows. Assumption 4 (Precise Version of the First Part of Assumption 2). Observed features {x(i)} i∈V consists of true features {x(i)} i∈V and noise {z(i)} i∈V . The true features X have frequency at most 0 ≤ 1 and the noise follows a white Gaussian noise, i.e., each entry of the graph Fourier transform of Z independently identically follows a normal distribution N (0, σ 2 ).

Using this assumption, we can evaluate the effect of the low-pass filter as follows. Lemma 5. Suppose Assumption 4. For any 0 < δ < 1/2, with probability at least 1 -δ, we have

EQUATION

where R(2k) is a probability that a random walk with a random initial vertex returns to the initial vertex after 2k steps.

The first and second terms of the right-hand side of equation 6 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( √ ). The variance term decreases in O(1/deg k/2 ) where deg is a typical degree of the graph since R(2k) typically behaves like O(1/deg k ) for small k.4 Therefore, we can obtain a more accurate estimation of 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

Z D / X D .

This theorem also suggest a choice of k. By minimizing the right-hand side by k, we obtain: This concludes that we can obtain an estimation of the true features with accuracy Õ( √ ) by multiplying Ãrw several times.

Corollary 6. Suppose that E[ Z D ] ≤ ρ X D for some ρ = O(1). Let

6. GRAPH FILTER NEURAL NETWORK:

In the previous section, we see that low-pass filtered features Ãk rw X are accurate estimations of the true features with high probability. In this section, we 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

EQUATION

where σ 1 is the entry-wise ReLU function, and σ 2 is the softmax function. Note that both σ 1 and σ 2 are contraction maps, i.e., σ i (X) -σ(Y

) D ≤ X -Y D .

gfNN As a toy model for analysis and experiments, we define our gfNN models. It 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 7) for high-frequency version.

h gfNN-low (X, A|W 1 , W 2 ) = h MLP ( Ã2 rw X|W 1 , W 2 ) (8) h gfNN-high (X, A|W 1 , W 2 ) = h MLP ( L2 rw X|W 1 , W 2 ) (9)

Under the second part of Assumption 2, our goal is to obtain a result similar to h( X|W 1 , W 2 ). The simplest approach is to train a multi-layer perceptron h MLP (X|W 1 , W 2 ) with the observed feature. The performance of this approach is evaluated by

EQUATION

where ρ(W ) is the maximum singular value of W . Now, we consider applying graph a filter Ãk rw to the features, then learning with a multi-layer perceptron, i.e., h MLP (h( Lrw )X|W 1 , W 2 ). Using Lemma 5, we obtain the following result. Theorem 7. Suppose Assumption 4 and conditions in Corollary 6. By choosing k as Corollary 6, with probability at least 1 -δ for δ < 1/2,

EQUATION

This means that if the maximum frequency of the true data is small, we obtain a solution similar to the optimal one.

Comparison with GCN Under the same assumption, we can analyze the performance of a twolayers GCN. The GCN is given by

EQUATION

Theorem 8. Under the same assumption to Theorem 7, we have

EQUATION

This theorem means that GCN also has a performance similar to MLP for true features. Hence, in the limit of → 0 and Z → 0, 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 a risk of overfitting to the noise. When the noise is so large that it cannot be reduced by the first-order low-pass filter, Ãrw , the inner weight W 1 is trained using noisy features, which would overfit to the noise leading to low test accuracy.

Comparison with SGC Recall that a degree-2 SGC is given by

EQUATION

i.e., it is 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: if the true features are non-linearly separable, SGC cannot learn the correct function.

7. 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 8, we see 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 (2017) and Wu et al. (2019) . Training details are provided in Appendix B and C.

Experimental results in Figure 5 confirms our hypothesis for the three benchmark datasets. We see that when a high level of noise is injected to low-frequency datasets (especially Cora), the performance of GCN can degrade much faster than SGC or gfNN. It is also trivial to see that Logistic Regression (LG) and MLP on raw features exhibit similar behavior when noise is introduced. 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 show: 1. SGC cannot learn non-linearly separable features; and 2. SGC, GCN, DGI (Veličković et al., 2019) , and GraphSAGE (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 on the data points. Visualization of this dataset is given in Appendix E. We generate BA-High dataset by constructing a BA-graph with n = 200 and n = 10 (200 nodes, every new node are attached to 10 neighbors selected from existing nodes). We then find the maximal independent set for the graph and use this set as label 1. The rest of the nodes are label 0. For each node with label 1, we generate a 50-dimensions feature vector from a Gaussian N (+ , 1.0). We do the same for all nodes with label 0 but with Gaussian N (-, 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 1 ) while other more complex models perform as expected (similar performance as an MLP). More interesting is the results of the BA-High experiment (Table 1 , 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 or MLP can have accuracy larger than 90%), most GNN models reported less than 60% accuracy. In Figure 6 , we show a simple solution to this setting: Use high frequency eigenvectors or high-pass filter (gfNN-High).

High-freq Eigenvectors (last 50) GCN ( k=2 3 gfNN-high 24.2 ± 1.9 22.5 ± 2.2 43.6 ± 1.3 10.5 ± 2.6 86.6 ± 0.1 48.3 ± 3.5 96.2 ± 1.0

8. DISCUSSION:

Recently, Kampffmeyer et al. (2019) observed that GCN models might have too strong Laplacian smoothing effect (low-frequency in our terms) for zero-shot learning application. This is an example of an application where the frequency of data might be band-limited 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 learn 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 highfrequency labels, popular GNN models will perform badly. While there is not yet any real-world benchmark dataset which node labels are of high-frequency nature, such setting is not entirely impossible given the complexity of a network. For instance, a relationship network would be less likely to have same-gender links. Therefore, gender labels might exhibit high-frequency nature.

APPENDIX A PROOFS:

Proof of Theorem 3. Since the generalized eigenvalues of (D + γI, L) are the eigenvalues of a positive semidefinite matrix (D + γI) 1/2 L(D + γI) 1/2 , these are non-negative real numbers. To obtain the shrinking result, we use the Courant-Fisher-Weyl's min-max principle (Bhatia, 2013, Corollary III. 1.2) : For any 0 ≤ γ 1 < γ 2 ,

EQUATION

≤ min

H:subspace,dim(H)=i max x∈H,x =0

x Lx x (D + γ 1 I)x (16)

EQUATION

Here, the second inequality follows because x (D + γ 1 )x < x (D + γ 2 )x for all x = 0 Hence, the inequality is strict if x Lx = 0, i.e., λ i (γ 1 ) = 0.

Lemma 9. If X has a frequency at most then h(L)

X 2 D ≤ max t∈[0, ] h(t) X 2 D .

Proof. By the Parseval identity,

EQUATION

Proof of Lemma 5. By substituting X = X + Z, we obtain

EQUATION

By Lemma 9, the first term is bounded by √ k X D . By the Parseval identity equation 4, the second term is evaluated by

EQUATION

By (Laurent and Massart, 2000 , Lemma 1), we have

EQUATION

By substituting t = log(1/δ) with δ ≤ 1/2, we obtain

EQUATION

Note that E[ Z 2 D = σ 2 nd, and

EQUATION

since (i, j) entry of Ã2k rw is the probability that a random walk starting from i ∈ V is on j ∈ V at 2k step, we obtain the lemma.

Proof of Theorem 7. By the Lipschitz continuity of σ, we have

EQUATION

By using Lemma 5, we obtain the result.

Lemma 10. If X has a frequency at most then there exists Y such that Y has a frequency at most √ and σ

(X) -Y 2 D ≤ √ X 2 D .

Proof. We choose Y by truncating the frequency components greater than √ . Then,

EQUATION

Proof of Theorem 8. From Lemma 10, by taking the square root and absolute values of both sides, we have σ(X) -Y D ≤ 1/4 X D .

By setting Y = σ( Ãrw X), since σ is an activation function, we have:

EQUATION

Consequently, we consider the D-norm stated in Theorem 8:

EQUATION

B GFNN MODEL DETAILS 

C BASELINE DETAILS:

We set GCN (Kipf and Welling, 2017) at two layers with 64 hidden units, ReLU activation, no dropout. We keep the setting of SGC (Wu et al., 2019) as recommended by the original implementation (200 epochs, lr=0.1, weight decay: 1 × 10 -4 , ReLU activation). For DGI (Veličković et al., 2019) , GraphSAGE Hamilton et al. (2017) , and GIN (Xu et al., 2019) , we follow the authors' default paramter tuning. The result for GraphSAGE is reported as 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 an evaluation for the semi-supervised node classification performance of SGC on the Cora, Citeseer, and Pubmed citation network datasets Sen et al. (2008) . We also follow Wu et al. (2019) to run experiments on Reddit Chen et al. (2018) and Hamilton et al. (2017) on PPI Zitnik and Leskovec (2017) . 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 0.485 0.862 0.872 GCN gfNN 7: Decision boundaries on 500 generated data samples following the two circles pattern BA-High dataset generation procedure is described in Figure 8 .

We have similar experimental results on different type of random graphs: ER, Configuation, and Block Model. The experimental results on GCN/SGC can be explained simply with Figure 9 In Figure 9 , the color blue and orange indicate label 1 and label 0 in a 100 node BA-graph. It 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 a uniform feature (Theorem 3).

We only consider unweighted edges but it is easily adopted to positively weighted edges.

The standard deviation of clean signal is less than 0.01 for all three datasets. See Table2for more detail.

The shrinking of the maximum eigenvalue has already been proved in(Wu et al., 2019, Theorem 1). Our theorem is stronger than theirs since we show the "monotone shrinking" of "all" the eigenvalues. In addition, our proof is simpler and shorter.

This exactly holds for a class of locally tree-like graphsDembo et al. (2013), which includes Erdos-Renyi random graphs and the configuration models.

Õ(•) suppresses logarithmic dependencies.

Figures and Tables:

Figure 1: Accuracy by frequency components

Figure 3: Average performance of 2-layers MLPs on frequency-limited feature vectors with early stopping using the validation data (max epochs=500). The two horizontal lines show the performance of our model and a 2-layers MLP on original feature.

k * be defined by k * = O(log(log(1/δ)ρ/ )), and suppose that there exist constants C d and d > 1 such that R(2k) ≤ C d / dk for k ≤ k * . Then, by choosing k = k * , the right-hand side of equation 6 is Õ( √ ). 5

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.

Figure 6: Performance on high-frequency labels For comparison purpose, we present our results on benchmark datasets inTable 1. Model details are presented in Appendix C. Dataset details are presented in Table 2 (Appendix E). Average test accuracy on original train/val/test splits (50 times)

Table content: <table><tr><td/><td>SGC (k=2)</td><td/><td/><td>)</td><td/><td/></tr><tr><td/><td>SGC (k=3)</td><td/><td colspan="2">GraphSAGE</td><td/><td>gfNN-High</td></tr><tr><td/><td>Cora</td><td>Citeseer</td><td>Pubmed</td><td>Reddit</td><td>PPI</td><td>2Circles</td><td>BA-High</td></tr><tr><td>DGI</td><td colspan="7">83.1 ± 0.2 72.1 ± 0.1 80.1 ± 0.2 94.5 ± 0.3 99.2 ± 0.1 85.2 ± 0.6 54.6 ± 1.8</td></tr><tr><td>GCN</td><td colspan="4">80.0 ± 1.8 69.6 ± 1.1 79.3 ± 1.3 -</td><td>-</td><td colspan="2">84.9 ± 0.8 58.9 ± 2.2</td></tr><tr><td>SGC</td><td colspan="7">77.6 ± 2.2 65.6 ± 0.1 78.4 ± 1.1 94.9 ± 0.2 89.0 ± 0.1 53.5 ± 1.4 55.5 ± 1.3</td></tr><tr><td>gfNN-low</td><td colspan="7">82.3 ± 0.2 71.8 ± 0.1 79.2 ± 0.2 94.8 ± 0.2 89.3 ± 0.5 85.6 ± 0.8 55.4 ± 2.</td></tr></table>

Weight decay: 1 × 10 -4 • 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 is reported for all experiments.

Table content: <table><tr><td>Our gfNN model is implemented in Pytorch. While other number of hidden layers are possible, we</td></tr><tr><td>find that 1 hidden layer with 256 units (2 layers MLP) is enough for all benchmark datasets. Other</td></tr><tr><td>changes does not significantly influence the experimental results. It worth mentioning that each gfNN</td></tr></table>

Real-world benchmark datasets and synthetic datasets for vertex classification

Table content: <table><tr><td>Dataset</td><td>Nodes</td><td>Edges</td><td colspan="2">Features (X) (µ X , σ X )</td><td colspan="2">Classes Train/Val/Test</td></tr><tr><td>Cora</td><td>2,708</td><td>5,278</td><td>1,433</td><td colspan="2">(0.0007, 0.0071) 7</td><td>140/500/1,000</td></tr><tr><td>Citeseer</td><td>3,327</td><td>4,732</td><td>3,703</td><td colspan="2">(0.0003, 0.0029) 6</td><td>120/500/1,000</td></tr><tr><td>Pubmed</td><td>19,717</td><td>44,338</td><td>500</td><td colspan="2">(0.0019, 0.0087) 3</td><td>60/500/1,000</td></tr><tr><td>Reddit</td><td colspan="3">231,443 11,606,919 602</td><td>-</td><td>41</td><td>151,708/23,699/55,334</td></tr><tr><td>PPI</td><td>56,944</td><td>818,716</td><td>50</td><td>-</td><td>121</td><td>44,906/6,514/5,524</td></tr><tr><td colspan="2">Two Circles 4,000</td><td>10,000</td><td>2</td><td>-</td><td>2</td><td>80/80/3,840</td></tr><tr><td>BA-High</td><td>200</td><td>2000</td><td>50</td><td>(0,1)</td><td>2</td><td>10/10/180</td></tr></table>

Peer review (iclr2020):
Summary Several 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. First, 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. Next, 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. Finally, 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. Decision I judge that this paper contributes to deepning the understanding of graph NNs and is worth to be accepted based on the following three points. First, 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. Second, 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. Finally, 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. For these reasons, I think this paper has contributed to a deeper understanding of graph NNs and sufficiently significant. Suggestions - 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. - Could you add more explanations to the proof of Theorem 8 in Appendix A. Especially, I could not understand how the term is derived. Questions - 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? - At the beginning of Section 6, the authors wrote that they set to (hence two-layered GNNs are in consideration). But Theorems 7 and 8 considered the optimal in Corollary 6. Which is correct? - 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 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.