Adaptive Stacked Graph Filter
Authors: Hoang NT
Takanori Maehara
Tsuyoshi Murata
Venue:  (2021)
Keywords: Graph Convolutional Network
vertex classification
graph signal processing
adaptive graph filter

Abstract: We study Graph Convolutional Networks (GCN) from the graph signal processing viewpoint by addressing a difference between learning graph filters with fully-connected weights versus trainable polynomial coefficients. We find that by stacking graph filters with learnable polynomial parameters, we can build a highly adaptive and robust vertex classification model. Our treatment here relaxes the low-frequency (or equivalently, high homophily) assumptions in existing vertex classification models, resulting a more ubiquitous solution in terms of spectral properties. Empirically, by using only one hyper-parameter setting, our model achieves strong results on most benchmark datasets across the frequency spectrum.

Under review as a conference paper at ICLR 2021
ADAPTIVE STACKED GRAPH FILTER
Anonymous authors Paper under double-blind review
ABSTRACT
We study Graph Convolutional Networks (GCN) from the graph signal processing viewpoint by addressing difference between learning graph filters with fully- connected weights versus trainable polynomial coefficients. We find that by stack- ing graph filters with learnable polynomial parameters, we can build highly adaptive and robust vertex classification model. Our treatment here relaxes the low-frequency (or equivalently, high homophily) assumptions in existing vertex classification models, resulting a more ubiquitous solution in terms of spectral properties. Empirically, by using only Syrea--aramettr setting, model achieves strong results on most benchmark datasets across the frequency spectrum.
INTRODUCTION
The semi-supervised vertex classification problem (Weston et al., 2012: Yang et al., 2016) in attributed graphs has become one of the most fundamental machine learning problems in recent years. This problem is often associated with its most popular recent solution, namely Graph Convolutional Networks (Kipf & Welling, 2017). Since the GCN proposal, there has been a vast amount of research to improve its scalability (Hamilton et al., 2017; Chen et al., 2018; Wu et al., 2019) as well as performance (Liao al., 2019; Li et al., 2019; Pei et al., 2020).
Existing vertex classification models often (implicitly) assume that the graph has large vertex ho- mophily (Pei et al., 2020), or equivalently, low-frequency property (Li et al., 2019; Wu et al., 2019); see Section 2.1 for graph frequency. However, this assumption is not true in general. For instance, let us take the Wisconsin dataset (Table 1), which captures a network of students, faculty, staff, courses, and projects. These categories naturally exhibit different frequency patterns', Connections between people are often now-frequency, while connections between topics and projects are often midrange. This problem becomes apparent as GCN-like models show low accuracies on this dataset; for example, see (Pei et al., 2020; Chen et al., 2020b; Liu et al., 2020).
This paper aims establishing GCN model for the vertex classification problem (Definition 1) that does not rely on any frequency assumption. Such a model can be applied to ubiquitous datasets without any hyper-parameter tuning for the graph structure.
Contributions. By observing the relation between label frequency and performance of existing GCN-like models, we propose to learn the graph filters coefficients directly rather than learning the MLP part GCN-like layer. We use filter stacking to implement trainable graph filter, which is capable of learning any filter function. Our stacked filter construction with novel learnable filter parameters is easy to implement, sufficiently expressive, and less sensitive to the filters' degree. By using only one hyper- apprr-parameter setting, show that our model is more adaptive than existing work on a wide range of benchmark datasets.
The rest of our paper is organized follows. Section 2 introduces notations and analytical tools. Section 3 provides insights into the vertex classification problem and motivations to our model's design. Section 4 presents an implementation of our model. Section summarizes related literature with a focus on graph filters and state-of-the-art models. Section 6 compares our model and other existing methods empirically. We also provide additional experimental results in Appendix A.
"FFreuunncy" is an equivalent concept "homophily" and will be explained in Section

---

Under review as a conference paper at ICLR 2021
2 PRELIMINARIES
We consider a simple undirected graph G = (V, E), where = .L....,,]] nu } is a set of n vertices and E S V X V is a set of edges. A graph G' is called an attributed graph, denoted by G(X), when it is associated with a vertex feature mapping X V +> R2, where d is the dimension of the features. We define the following vertex classification problem, also known in the literature as the semi-supervised vertex classification problem (Yang et al., 2016).
Definition 1 (Vertex Classification Problem). We are given attributed graph G(X), a set of training vertices Vn C V, training labels Yur Vtr c, and label set C. The task is to find a model h: V + C using the training data (Vur; Yu.) that approximates the true labeling function Y V C.
Let A be the adjacency matrix of the graph G. i.e., Ac, = =1 if (t,j) E E and O otherwise. Let d; - -, Aiy be the degree of vertex E V, and let D diag(d),.... ...... da) be the n n diagonal matrix of degrees. Let L D A be the combinatorial graph Laplacian. Let C = DD-1/2DD-1/ be the symmetric normalized graph Laplacian. We mainly focus on the symmetric normalized graph Laplacian due to its interesting spectral properties: (1) its eigenvalues range from 0 to 2: and (2) the spectral properties can be compared between different graphs (Chung & Graham, 1997). In recent literature, the normalized adjacency matrix with added self-loops, À + c, often used as the propagation matrix, where e is some diagonal matrix.
2.1 GRAPH FREQUENCY
Graph signal processing (Shuman et al., 2012) extends "frequency" concepts in the classical signal processing to graphs using the graph Laplacian. Let L UAU be the eigendecoopposition of the Laplacian, where E R=** is the orthogonal matrix consists of the orthonormal eigenvectors of L and A is the diagonal matrix of eigenvalues. Then, can regard each eigenvector ид "oscillation pattern" and its eigenvalue X as the "frequency" of the oscillation. This intuition supported by the Rayleigh quotient follows.
TTC Lx Earo (xlo( Lup(a((u)=(())) xx(x))²
r(C,x)
x TT.
Enevx(n)
where Ennp sums over all unordered pairs for which u and v are adjacent, .z) denotes the entry of vector x corresponding to vertex u, and Cu,y is the (u, u)-entry of L. From the definition we see that r(x) is non-negative and L is positive semi-definite. r(x) is also known characterization of eigenvalues of L (Hom & Johnson, 2012, Chapter 4). hence 0 I r(x) < 2 for any non-zero real vector We use the notation r(z) to denote the Rayleigh quotient when the normalized graph Laplacian is clear from context. The Rayleigh quotient r(x) measures how the data is oscillating. Hence, in this study, we use the term "frequency" and the "Rayleigh quotient" interchangeably. By the definition, the eigenvector u, has the frequency of X
variational
The labeling y of the vertices is low-frequency if the adjacent vertices are more likely to have the same label. This is a common assumption made by the spectral clustering algorithms (Shi & Malik, 2000; Ng et al., 2002; Shaham et al., 2018). Commonly used terms, homophily and heterophily, used in network science, correspond to fow-frequency and high-frequency. respectively.
2.2 GRAPH FILTERING
In classical signal processing, given signal is processed by filters in order to remove unwanted interference. Here, we first design frequency response f()) of the filter, and then apply the filter to the signal the sense that each frequency component ((A) of the data modulated as (A))&(A). Graph signal processing extends this concept as follows. Same as in classical signal processing, we design a filter f()). Then, represent given graph signal E RIVI linear combination of the eigenvectors as X = Σ; Z.u4 Then, we modulate each frequency component by f(A) as E: (())ax An important fact is that this be done without performing the eigendecomposition explicitly. Let f(C) be the matrix function induced from f()). Then, the filter is represented by f fC)...
As an extension of signal processing, graph signal processing deals with signals defined on graphs. In definition 1, each column of the feature matrix X E RRad a "graph signal". Let L = UAU be
2

---

Under review as a conference paper at ICLR 2021
the cigendecomposition where U Rax* consists of orthonormal eigenveetors. Signal X is filtered by function f of the cigenvalues as follow.
X = -UU(AA X f(C)x
(2)
In general, different implementations of ((C) lead to different graph convolution models. For instance, GCN and SGC (Wu et al., 2019) are implemented by f(L) -I- (D++)++++-1))))
1-------1/- 1/2)A: where the constant term stems from the fact that self-loops are added to vertices and k is the filter order. Generally, the underlying principle to learn or construct the appropriate filter function / such that it transforms X into more expressive representation. The filter in GCN is called low-pass filter because it amplifies frequenunncy components (Li et al., 2018; NT Machara, 2019).
SPECTRAL PROPERTIES OF FILTERS
Towards building a ubiquitous solution, we take an intermediate step to study the vertex classification problem. Similar to the unsupervised clustering problem, an (implicit) low-frequency assumption commonly made. However, the semi-supervised vertex classification problem more involved because vertex labels have complicated non-local patterns. Table shows three groups of datasets, each with different label frequency ranges. Notably, WebKB datasets (Wisconsin, Comell,, Texas) have mixed label frequencies; some labels have low frequencies while others have midrange frequencies. Therefore, in order to relax the frequency assumptions, we need to learn the filtering function fA) in a similar way as proposed by Defferrard et al. (2016).
The filtering function f(A) is often approximated using a polynomial of the graph Laplacian as
S(C) R (C) O.C.
(3)
Because polynomials can uniformly approximate any real continuous function on compact interval (see, e-g., (Brosowski & Deutsch, 1981)), )), such approximation scheme well-justified.
Kipf& & Welling (2017) derived their GCN formulation as follows. In their equation 5, they approxi- mated a graph filter Je by Chebyshev polynomials Tи
g0 x 1/2
(4)
Then, they took the first two terms and shared the parameters as Og -01 to obtain their equation
(2IN L) go x R 0 IN + A1122 -122) x
(5)
Finally, they extended scalar 0 to matrix to accommodate multiple feature dimensions as
Z 1/
Kipf Welling (2017) claimed that the weight matrix θ can learn different filters, and subsequent works (e.g., (Veličković et al., 2018; Spinelli et al., 2020; Chen et al., 2020b)) also learned filters by O. However, neither theory nor practice it is the case (Oono & Suzuki, 2020). the construction suggest, GCN layer only represents filter of the form f(() ~ 2 X. To properly learn different graph filters, we should learn the multiplying parameters 6, .......0. 0g in equation 3. In the next section, we propose learning model which directly learns these multiplying parameters.
4 MODEL DESCRIPTION
The previous discussion provided several insights: (1) Vertex classification model's frequency is decided by its filter, (2) a mechanism to match the frequencies of data is necessary, and (3) directly learning the polynomial filter's coefficients is more desirable if we do not want to make any frequency assumption. Based on these observations, we implemented an adaptive Stacked Graph Filter (SGF) model. Figure visually describes SGF.
3

---

Under review as a conference paper at ICLR 2021
Stacked Filter
H
X
W
0
W out
in
((A)
((A)
Corstant Tensor
Mr
A/C.
Variable Tersor
Operater
Loss
Q
Hi
Rackprop
Forward
Singlo Filter
SLaciod Filler
Figure Block description of SGF. A/C means we can plug either the augmented normalized adjacency matrix or the symmetric normalized Laplacian into this model. In each filter layer, the scalar ag controls the filter's tangent and the scalar Be controls the filter's s vertical translation.
Design decisions. The novelty of model is the stacked filter, and directly learn the filtering function by filter coefficients a and 3, which makes SGF work well universally without frequency hyper-paramettrs. The deep filter module consists of filters stacked on top of each other with skip- connections to implement the ideas in Proposition 2. Each filter layer has two learnable scalars: as and Be which control the shape of the linear filter (Figure 1). Two learnable linear layers Wi, and Wout with non-linear activation serve as a non-linear classifier (NT & Maehara, 2019).
The input part our architecture resembles APPNP (Klicpera al., 2019) in the sense that the input signals (vertex features) are passed through a learning weight, then fed into filtering. The output part of our architecture resembles SGC (Wu et al., 2019) where we learn the vertex labels with filtered signals. This combination naturally takes advantages of both bottom-up (APPNP) and top-down (SGC) approaches. Compared to APPNP and SGC, besides the different filter learning, our model performs filtering (propagation) the latent representation and classifies the filtered representation, whereas APPNP propagates the predicted features and SGC classifies the filtered features.
From the spectral filtering viewpoint, approach is most similar to ChebyNet (Defferrard et al., 2016) since both models aim to learn the filtering polynomial via its coefficients. Chebyshev polyno- mial basis is often used in signal processing because it provides optimal interpolation points (Cheney, 1966; Hammond et al., 2011). However, since we are learning the coefficients of an unknown polyno- mial filter, all polynomial bases are equivalent. To demonstrate this point, we implement the Stacked Filter module (Figure 1) using ChebNet's ' recursive formula in Section 6. We find that Chebyshev polynomial basis approach has similar performance to the stacked approach with one slight caveat on choosing Amax We empirically show this problem by setting the scaling factor Amux = 1.5. Note that, as pointed out by Kipf Welling (2017), such problem can be migrated simply by assuming Amax so all eigenvalues stay in 1, 1].
Given an instance of Problem 1, let be activation function (e.g., ReLU), À 1 (D L + -112 be the augmented adjacency matrix, and 33 be the filter parameters at layer f, a K-layer SGF given by:
SGF: Input À
SGF: Input &
Ho (XWin)
Ho o(XW.n) Ht ozCHe BeHo, f= =1..KK
H; ugHHe BeHo, e f= 1...KK
ÿ = H Wont
ÿ = H Wout
SGF can be trained with conventional objectives (e.g., negative log-likelihood) to obtain solution to Problem 1. We present our models using the augmented adjacency matrix to show its similarity to existing literature. However, noted in Figure 1, we can replace Á with L.
4

---

Under review as a conference paper at ICLR 2021
The stacked filter is easy to implement. Moreover, it can learn any polynomial of order-K as follows. The bloedd-orm of the stacked filter (Figure 1) is given by
K
K
3x
+
ag)
k-it1
= ==
where 30 1. Because each term of equation 7 contains unique parameter, we obtain the following.
Proposition 2. Any polynomial poly(C) of order K can be represented by the form equation 7.
Note that the same result holds if we replace C in equation 7 by A. In practice, we typically set the initial values of a; = 0.5 and update them via the back-propagation. The learned o is then likely to satisfy aaıl < 1, which yields a further property of the stacked filter: it prefers a low- degree filter, because the coefficients of the higher-order terms are higher-order in a; which vanishes exponentially faster. This advantage is relevant when we compare with a trivial implementation of the polynomial filter that learns 02 directly (this approach corresponds to horizontal stacking and ChebyNet (Defferrard et al., 2016)). In Appendix A.I, we compare these two implementations and confirm that the stacked filter is more robust in terms of filter degree than the trivial implementation.
RELATED WORK
GCN-like models cover subset of increasingly large literature graph-structured data learning with graph neural networks (Gori et al., 2005; Scarselli et al., 2008). In general, vertex classification and graph classification learning behind modern graph learning models can also be split into two views: graph propaga- tion/diffusion and graph signal filtering. In this section, we briefly summarize recent advances in the vertex classification problem with a focus on propagation and filtering methods. For a more comprehensive view, readers can refer to review articles by Wu et al. (2020), Grohe (2020), and also recent workshops graph representation learning?.
the two main benchmark problems. The principles for representation
Feature Propagation. Feature propagation/message pastsig and graph signal filtering are two equivalent views on graph representation learning (Defferrard et al., 2016; Kipf & Welling, 2017). 7). From the viewpoint of feature propagation (Scarselli et al., 2008; Gilmer et al., 2017), researchers focus on novel ways to propagate and aggregate vertex features to their neighbors. Klicpera et al. (2019) proposed PPNP and APPNP models, which propagate the hidden representation of vertices. More importantly, they pioneered in the decoupling of the graph part (propagation) and the classifier part (prediction). Abu-El El-Haija et al. (2019) also proposed to use skip-commections to distinguish between 1-hop and 2-hop neighbors. Zeng al. (2020) later proposed GraphSAINT aggregate features from random subgraphs to further improve their model's expressivity. Pei et al. (2020) proposed more involved geometric aggregation scheme named Geom-GCN to address weaknesses of GCN-like models. Most notably, they discussed the relation between network homophily and
GCN's s performance, which similar to label frequency r(Y) in Table 1. Spinelli et al. (2020) introduced an adaptive model named AP-GCN, in which each vertex can learn the number of "hops" propagate its feature via a trainable halting probability. Similar our discussion Section 3, they still use a fully-connected layer to implement the halting criteria, which controls feature propagation. AP-GCN's architecture resembles horizontal stacking graph filters where they learn coefficients 9 directly. However their construction only allows for binary coefficients". We later show that full horizontal stacking models (more expressive than AP-GCN) is less stable in terms of polynomial order than our approach (Appendix A.1). More recently, Liu al. (2020) continued to address the difficulty of low homophily datasets and proposed a non- aggregation based on 1D convolution and the attention mechanism, which has "reconnecting" effect increase homophily.
Graph Filtering. GCN-like models can also be viewed as graph signal filters where vertex feature vectors signals and graph structure defines graph Fourier bases (Shuman et al., 2012; Defferrard et al., 2016; Li et al., 2018; 88; Wu et al., 2019). This graph signal processing view addresses label efficiency (Li al., 2019) and provides an analogue for understanding graph signal processing using
"See, e.g., ht / / /r plus gii.uu.giiiee. thub. 1
IIn the manuscript, they showed construction using coefficients of graph Laplacian, but the actual imple- mentation used GCNConv (which is T L c) from pytorch-gcometric.
5

---

Under review as a conference paper at ICLR 2021
traditional signal processing techniques. For example, the Lanczos algorithm is applied in learning graph filters by Liao et al. (2019). Bianchi et al. (2019) applies the ARMA filter to graph neural networks. Similar (Klicpera et al., 2019), Wu et al. (2019) and NT & Machara (2019) also follow the decoupling principle but in a reversed way (flter-then-claasiff)) (Chen et al., 2020b) built a deep GCN named GCNII which holds the current best results for original splits of Cora, Citeseer, and Pubmed. They further showed that their model can estimate any filter function with an assumption that the fully-connected layers can learn filter coefficients (Chen al., 2020b, Proof of Theorem 2).
EXPERIMENTAL RESULTS
We conduct experiments on benchmark and synthetic data to empirically evaluate our proposed models. First, compare our models with several existing models in terms of average classification accuracy. Our experimental results show that our single model can perform well across all frequency ranges. Second, we plot the learned filter functions of model to show that model can learn the frequency range from the data such visualization is difficult in existing works as the models' filters fixed before the training process.
6.1 DATASETS
We use three groups of datasets corresponding to three types of label frequency (low, midrange, high). The first group is low-frequency labeled data, which consists of citation networks: Cora, Citeseer, Pubmed (Sen et al., 2008); and co-purchase networks Amazon-Photo. Amazon- Ceazzun- (Shchur et al., 2018). The second group is network datasets with midrange label frequency (close to I): Wisconsin, Cornell, Texas (Pei al., 2020); and Chameleon (Rozemberezki et al., 2019). The last group consists of a synthetic dataset with high label frequency (close to 2). For the Biparite dataset, we generate connected bipartite graph on 2,000 vertices (1,000 on each part) with an edge density of 0.025. We then use the bipartite parts binary vertex labels. Table gives overview of these datasets; see Appendix B.3 for more detail.
Table 1: Overview of graph datasets, divided to three frequency groups
DATASETS
V
E
C
r(Y)
r(X)
Type
Cora
2,708
5,278
1,433
7
0.23 + 0.04
0.91 0.10
Citation
Citeseer
3,327
4,676
3,703
6
0.27 + 0.03
0.19
Citation
Pubmed
19,717
44.327
500
3
0.55
0.87
Citation
Amz-Photo
7,487
119,043
745
8
0.04
0.04
Co-purchase
Lanz-Computer
13,381
245,778
767
10
0.27
0.04
Co-purchase
Wisconsin
251
450
1703
5
0.87 + 0.08
0.89 0.23
Web
Cornell
183
277
1703
5
0.86 + 0.11
0.86 0.32
Web
Texas
183
279
1703
5
0.98
+ 0.03
0.84 0.32
Web
Chameleon
2,277
31,371
2325
5
0.81 0.05
0.99 0.01
Wikipedia
Bipartite 2,000
50,182
50
2
2.0 + 0.00
1.0 0.00
Synthetic
6.2 VERTEX CLASSIFICATION
We compare our method with some of the best models in the current literature. Two layers MLP (our model without graph filters), GCN (Kipf Welling, 2017), SGC (Wu et al., 2019), and APPNP (Klicpera et al., 2019) are used as baseline. Geom-GCN-(LP.) (Pei et al., 2020), JKNet+DE (Xu al., 2018; 8: Rong et al., 2019), and GCNII (Chen al., 2020a) are currently among the best models. We implement the Chebyshev polynomial filter in (Defferrard al., 2016) and set Amax = 1.5. The Literature section of Table and 3 shows the best results found in the literature where these models set at the recommended hyper-pane ppper-pprrmeters and recommended variants for each dataset. In our experiment, we fix the graph-related hyper-parameters parameters of each model and report the classification results. Our model contains 16 layers of stacked filters (A) and has 64 hidden dimensions. Learning rate is set at 0.01, weight decay is 5e 10-1, and dropout rate for linear

---

Under review as a conference paper at ICLR 2021
layers is 0.7. From intuition that the filter should discover the required frequency pattern before the linear layers, we set the learning rate of linear layers to be one-fourth the main learning rate. This experimental setup shows that SGF can adapt the label frequency without setting specific hyper-parameters. In Table 2, SGF performs comparably with the current state-of-the-an On the other hand, in Table 3, SGF is not only better than others in our experiments but also surpassing the best results in the literature. Note that we also the exact same SGF model across all experiments.
Table 2: Vertex classification accuracy for low- low-frequency datasets
DATASETS
METHODS
Cora
Citeseer
Puhmed
Photo
Computer
Our experiments (Average over 10 runs of stratified 0/6.2 splits)
MLP
75.01 +
73.24 + 1.28
83.56
0,44
85.05
1.62
80.42 = 0.73
SGC (A: = 2)
87.15 + 1.57
75.00 + 0.93
87.97
0.35
93.67
0.68
90.87 = 0.43
APPNP (a = 0.2)
88.07 + 1.32
76.71 + 0.88
88.21
0.37
94.70 + 0.50
91.16 = 0.44
GCNII (0.5, 0.5)
86.21 + 1.40
76,86 + 1.29
89.77 + 0.52
92.57 = 0.61
88.71 = 0.55
SGF-Cheby (Ammx 2.0)
88.42 + 1.60
76.85
1.01
87.74 + 0.37
91.26 + 1.76
89.71 = 0.55
SGF-Cheby (Amax 1.5)
30.05 + 0.60
21.11 + 0.03
41.72
2.99
26.79
1.82
36.99 0.03
SGF
88.97 + 77.58
1.11
90.12
0.40
95.58
0.55
92.15 = 0.41
Literature (Best result among their variants)
GCN
85.77
73.68
88.13
(not avail.)
(not avail.)
GAT
86.37
74.32
87.62
(not avail.)
(not avail.)
Geom-GCN
85.27
77.99
90.05
(not avail.)
(not avail.)
APPNP
87.87
76.53
89.40
(not avail.)
(not avail.)
JKNet+DE
87.46
75.96
89.45
(not avail.)
(not avail.)
GCNII
88.49
77.13
90.30
(not avail.)
(not avail.)
Table 3: Vertex classification accuracy for midrange and high frequency datasets
DATASETS
METHODS
Wisconsin
Comell
Texas
Chamelcon
Bipartite
Our experiments (Average
10 runs of stratified 0.6/0.2/0.2 splits)
MLP
83.72 + 3.40
80.13 1 4.59
80.30 5.55
45.63 + 1.88
48.34 = 1.67
SGC (k= = 2)
56.27 1 6.79
53.37 + 5,41
51.49 + 6.75
26.51 + 2.44
48.07 = 1.47
APPNP (a 0.2)
71.02 + 5.98
74.55 + 4.49
66.95 + 6.02
54.58 + 1.67
50.89 = 1.08
GCNII (0.5, 0.5)
71.57 5.13
74.47
1: 5.42
73.78 1 6.72
55.81 1 1.55
49.70 = 1.75
SGF-Cheby (Amax 2.0)
76.28 1 4.23
69.32
1: 5.67
77.59
4.36
70.16 2.08
100.0 -
SGF-Cheby (Amux = 1.5)
52.34 + 6.11
59.25
+ 3.14
62.22
+ 5.43
28.71
= 3.19
100.0 = 0.00
SGF
87.06 + 4.66
82.45
+ 6.19
5.63 80.56
58.77 + 1.90
100.0 0.00
Literature (Best results among their variants)
GCN
45.88
$2.70
$2.16
28.18
(not avail.)
GAT
49.41
54,32
58.38
42.93
(not avail.)
Geom-GCN
64.12
60.81
67.57
60.90
(not avail.)
APPNP
69.02
73.51
65.41
$4.30
(not avail.)
JKNet+DE
50.59
61.08
57.30
62.08
(not avail.)
GCNII
81.57
76.49
77.84
62.48
(not avail.)
Results in Table 3 also suggest that the ability to adapt of the state of the art model GCNII is sensitive its parameters a and In our experiment, we the 9 parameter to 0.5 for all datasets, while in their manuscript the recommended values are around 1.5 depending the dataset. With the recommended hyper-parameters, GCNII can achieve the average accuracy 81.57% on Wisconsin data. However, its performance dropped around 3 10% with different values. This comparison highlights model's 's ability to adapt to a wider range datasets without any graph-related syper-parameters
The Chebyshev polynomial basis performs comparably to the staking implementation in the previous sections. The value Amux = 1.5 is choosen because the typical maximum eigenvalue of real-world networks often this value. However, in practice, should set Amax 2 as
discussed
7

---

Under review as a conference paper at ICLR 2021
After training
Initialization
Wisconsin
Bipartite
Figure 2: Learned filtering functions f(X) on three datasets corresponding to three frequency ranges. Each row shows the learning results for each initialization. Lightened lines represent the learned filtering functions different runs. The average accuracy is shown on the top right corner.
704
F(At
R1A
A
Noc 102
-2
0-
2
10A
20A
FLA)
FEAL
Int. C
7-
Acc: B4.4
2.0
Acc: 79.2
1.6
Acc: 100
10
5
0.8
0-
3-
0.2
2
2
discussed by Kipf& & Welling (2017). Our experiments here intent to highlight the potential numerical instability problem due to the arbitarily large leading coefficient the Chebyshev polynomial basis. Since for vertex classification any polynomial basis is equivalent, numerical stable ones like our implementation of SGF is certainly more preferable in practice.
6.3 FILTER VISUALIZATION
Another advantage our model is the ability to visualize the filter function using an inversion of Proposition 2. The first row of Figure 2 shows the filtering functions at initialization and after training when input is the normalized augmented adjacency matrix. The second row shows the results when the input is the normalized Laplacian matrix. These two cases be interpreted starting with low-pass filter (A) or starting with high-past, filter (C). Figure 2 clearly shows that method can learn the suitable filtering shapes from data regardless of the initialization. We expect the visualization here can be used as effective exploratory tool and baseline method for future graph data.
6.4 ADAPTIVITY TO STRUCTURAL NOISE
Recently, Fox & Rajamanickam (2019) raised problem regarding structural robustness of graph neural network for graph classification.. Zügner et al. (2018) posed a similar problem related to adversarial attack graphs by perturbations of vertex feature graph structure for the vertex classification setting (Dai et al., 2018; Bojchevski & Günnemann, 2019; Zügner & Günnemann, 2019). Here, we evaluate the robustness of the models against the structural noise, where we perturb a fraction of edges while preserving the degree sequence". This structural noise collapses the relation between the features and the graph structure; hence, it makes the dataset to have the midrange frequency. This experimental setting shows that adaptive models like ours and GCNII are more robust to structural noise. the worst-case scenario (90% edges are swapped), the adaptive models are at least as good as MLP on vertex features. Figure 3 shows vertex classification results at each amount edge perturbation: from 10% to 90%. APPNP with a = 0.2 and SGC with weights to filtered features. On the other hand, APPNP with a = 0.8 is much more robust to structural noise as it depends more on the vertex features. This result suggests that adaptive models like and GCNII can be good baseline for future graph adversarial attack studies (SGF's advantage here is being much simpler).
have
similar behavior under structural noise since these models give
6.5 DYNAMICS OF a's AND 3'S
In addition to Section 6.3, this section studies the dynamic of a and / during training for two representative datasets: Cora (low-frequency) and Wisconsin (mid-frequency). We the value of a and in SGF (A) every 20 training epochs and plot the result. Figure 4 shows the values of and B in 16 layers of SGF top to bottom then left to right order (reshaped to 4 by 4 blocks). For the Cora dataset, that the over-smoothing effect is quickly migrated as the a's automatically go to with the exception of the last three layers. Similarly, the weights for skip-comnections - 8's quickly
hhttps: ://en wiki wikiipddaa...o org. http://grreeeeeeerriieeeeee
zation
8

---

Under review as a conference paper at ICLR 2021
(ecuray((3)
Cora
Accuray(X)
Citeseer
Acturrccy(A3 (F3)
Pubmed
73
85
207
70-
80
65-
800
75
APPNP
APPSP
APPNP (0.2) APPNN
50
APPNP
53
APPNT
40
50
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0.1 0.2 0.3 0.6 0.7 0.8 0.9
0.1 0.2 0.3
0.6 0.7 0.8 0.9
Proction of perturbated edges
Proction perturbated edges
Praction perturbated edges
Figure 3: Vertex classification accuracy for each amount of edge perturbation. Since GCNII has similar performance as our model in this setting, we only plot the results for SGF.
Init.
e
e=40
e=80
e=120
e=160
e=100
e=140
e=180
e=220
e626
e=300
1.0
B
(a) Cora
Init.
e=
e=
e=80
e=120
1-0
e=100
e=140
1-000
e=
e=266
e=300
2.0
ak
/
(b) Wisconsin
Figure Dynamic of a's and I's with fixed initialization at 0.5.
go with the exception of few last layers. For the Wisconsin dataset, almost no filtering because all a's go to zero quickly and there only one active skip-connection in the last layer. This single active skip-connection phenomenon further confirmed by the experiment on MLP (Table 3) where MLP performed comparably to graph-based models. These results further explained the ability adapt of model.
that there is
Additional Experiments. We provide several other experimental results in Appendix A. Section A. discusses the advantages of vertical stacking (SGF) versus naive horizontal stacking (learning 0 in equation 3 directly). Section A.2 discusses the difficulty of estimating the frequency range (Rayleigh quotient) of vertex labels when the training set is small. Section A.3 provide additional experiments where a's and 3's are initialized randomly. We show that our model is still adaptive even with uniform [-1, 1] initialization.
7 CONCLUSION
We show that simply by learning the polynomial coefficients rather the linear layers in the formulation of GCN can lead to a highly adaptive vertex classification model. Our experiment shows that by using only one setting, SGF is comparable with all current state-of-the-ard methods. Furthermore, SGF can also adapt to structural noise extremely well, promising a robust model in practice. Since objective is to relax the frequency assumption, one could expect our model will perform weakly when number of training data is limited. Because the estimation of label frequency becomes difficult with small number of data (Appendix A.2), designing learning model that is both adaptive and data-efficient is an exciting challenge. We believe an unbiased estimation (Proposition 4) with more involved filter learning scheme is needed to address this problem in the future.

---

Symposium on Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-EI-Haija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional ar- chitectures via sparsified neighborhood mixing. In International Conference on Machine Learning. pp. 21-29, 2019.
Filippo Maria Bianchi, Daniele Grattarola, Cesare Alippi, and Lorenzo Livi. Graph neural networks with convolutional arma filters. arXiv preprint 19Xiv:1901.013300 2019.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. International Conference on Machine Learming, pp. 695-704. PMLR, 2019.
Bruno Brosowski and Frank Deutsch. An elementary proof of the stone-weierstrass theorem. Pro- ceedings of the American Mathematical Society, pp. 89-92, 1981.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. 2018.
Lei Chen, Le Wu, Richang Hong, Kun Zhang, and Meng Wang. Revisiting graph based collaborative filtering: A linear residual graph convolutional network approach. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 27-34, 2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, 2020b.
Elliott Ward Cheney. Introduction to approximation theory. 1966.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network, 2020.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92 in CBMS Workshop Spectral Graph Theory. American Mathematical Society, 1997.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang. Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint arXiv:1806.02371, 2018.
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.
James Fox and Sivasankaran Rajamanickam. How robust are graph neural networks to structural noise? arXiv preprint arXiv: /9/2. 10206, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv: 774.0//222 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
Martin Grohe. word2vec. node2vec, graph2vec, x2vec: Towards theory of vector embeddings of structured data. In Proceedings of the 39th ACM Principles of Database Systems, pp. 1-16, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 1024-1034, 2017.
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 109251 2011.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
10

---

Under review as a conference paper at ICLR 2021
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirly-Second AAAI Conference on Artificial Intelligence, 2018.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 9582-9591, 2019.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. 2019.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. arXiv preprint arXiv:2005. 14612, 2020.
Andrew Ng. Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances neural information processing systems, pp. 849-856, 2002.
Hoang NT and Takanori Maehara, Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint wwXiv:1905009550 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Representation Learning, 2020.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint 2rXii:2002205287., 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. 2019.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv preprint (TtV::9909.132211 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Newral Networks, 20(1):61-80, 2008
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rat Collective classification in network data. Al magazine, 29(3)933-93, 2008
Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectralnet: Spec- tral clustering using deep neural networks. International Conference on Learning Representations, 2018.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /8/ 1.05668, 2018.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-996 2000.
David Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.
The emerging field of signal processing graphs: Extending high high-dimensional data analysis to networks and other irregular domains. arXiv preprint arXiv:1211.005. 2012.
Indro Spinelli, Simone Scardapane, and Uncini Aurelio. Adaptive propagation graph convolutional network. arXiv preprint arXiv:2002.10306 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference Representation Learing, 2018.

---

Under review as a conference paper at ICLR 2021
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In Neural networks: Tricks of the trade, pp. 639 635. Springer, 2012.
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 Machine Learning, volume 97. JMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint DrXiv:1806.03552. 2018.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 40 48, New York, New York, USA, 20 20-22/0 Jun 2016. PMLR.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning, arXiv preprint arXiv:1902.08412, 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-2856, 2018.
12

---

Under review as a conference paper at ICLR 2021
A EXTRA EXPERIMENTAL RESULTS
A.1 VERTICAL AND HORIZONTAL STACKING
Horizontal stacking is equivalent learning 0's in Equation 3 directly instead of stacking them vertically. In parallel to our work, Chien et al. (2020) explored the horizontal stacking idea with the pagerank matrix instead of the Laplacian matrix discussed here. We find that both vertical and horizontal can learn degree K polynomial, but vertical stacking naturally robust to the high order terms. Horizontally stacked filter even loses its ability to adapt when learning order 64 polynomials. Table 4 shows a comparison between vertical stacking (SGF) and horizontal stacking. We also report the average number of iteration until early stopping and average training time per epoch for the 64 filters case. All hyper-parameters are the same as in Table and 3. Figure 5 gives an example of 4 layers stacking to clarify the difference between horizontal and vertical.
Table 4: Vertex classification accuracy comparison between horizontal and vertical stacking
NUMBER OF STACKED FILTERS
DATASETS
16
32
64
#lteration
Time
SGF (Average over 10 runs of stratified 0.6/0.2/0.2 splits)
Cora
88.97 + 1.21
88.70 +: 1.29
88.75 + 1.07
234.5
115.4 ms
Pubmed
90.12 + 0.40
89.93 = 0.55
88.34 + 0.67
357.9
205.1 ms
Wisconsin
87.06 + 4.66
85.51 = 4.84
86.17 + 4.41
502.5
98.6 ms
Cornell
82,45 6.19
80.55 6.58
81.14 + 4.50
615.7
98.7 ms
SGF
CGF-Horizottal (Average over 10 runs of stratified 0.6/0.2/0.2 splits)
Cora
88.34 1.70
88.48 1.41
88.08 + 1.65
765.9
107.1 ms
Pubmed
87.38 + 0.38
87.27 = 0.40
87.10 + 0.37
603.8
130.6 ms
Wisconsin
84.03 2.39
78.42 + 6.70
60.19 + 4.96
1046.5
122.1 ms
Cornell
64.95 + 6.02
56.84 + 5.97
56.83 + 6.08
666.8
81.5 ms
0.
6.
X
X
(a) Vertical Filter Stacking
(b) Horizontal Filter Stacking
Figure 5: Block diagram example of order-4 stacked filters. Both of these models can learn order-4 polynomial as the filtering function.
A.2 RAYLEIGH QUOTIENT ESTIMATION FROM TRAINING DATA
To obtain accurate classification solution, the frequency of the model's output must be close the frequency of the true labels as follows.
Proposition 3. Let ÿ. y E RN be unit length vectors whose signs of entries indicate predicted labels and true labels for vertices in graph G. Let C E Ru be the symmetric normalized graph Laplacian
of graph G. Suppose the graph frequency gap is at least (r(ū) - r Li Lyy 2 Then we have:
|b v1 8/4
(8)
This proposition explains that model designed for specific frequency range (e.g., GCN, SGC, GAT, APPNP, etc for low-frequenc range) gives a poor performance on the other frequency ranges. This proposition also leads method to seek model (i.e., a filter) whose output matches the frequency of the true labels. Because the true label frequency is unknown in practice, we must estimate this quantity from the training data. Below, we discuss the difficulty of this estimation.
13

---

Under review as a conference paper at ICLR 2021
A naive strategy of estimating the frequency is to compute Rayleigh quotient the training set. However, training features X and training labels yn often have Rayleigh quotient close to (as shown in Table 1 for r r))),, and Figure 7 (Appendix) shows the results when compute the Rayleigh quotient of labels based on training data. This means that a naive strategy yields undesirable results and we need some involved process of estimating the frequeney.
If we can assume that (1) Training vertices are sampled i.i.d., and (2) we know the number of vertices in the whole graph (N [VD, we can obtain an unbiased estimation of the frequency of the true labels as follows.
Proposition 4. Let be the proportion of vertices will be used as training data, be the proportion of label y, N be the lotal number of vertices in the graph, Lu be the symmetric normalized Laplacian of the subgraph induced by the training vertices, and yo be the training labels. Assuming the truining set is obtained by sampling the vertices i.i.d. with probability p. we can estimate the Rayleigh quotient of true labels by
E(r(yn)) = AN 1N- (yTT Cnyn -11- -lyp diag(Cn))
Figure 6 shows an unbiased estimation results using Proposition 4. Unfortunately, at 10% training ratio, the observed variances are high across datasets; thus, we conclude that estimating the label frequency is generally difficult, especially for small training data.
Cora
Wisconsin
Bipartite
03
04
Amz Photo
Chameleon
Block Model
0.55
1.6-
645
3.35
633
125
81
33
85
07
06
05
11
02
03
00
62
05
00
(a) r(Y) E 00.0.6] (low)
(b) rYY E [0.6, 1.3] (mid)
(c) rYY E [1.3, (high)
Figure 6: Box plot of estimated Rayleigh quotient (frequency) by training ratio. For each training ratio, we randomly sample 10 training sets and compute Rayleigh quotients using equation (9).
Thus far, we have shown that estimating label's frequency given limited training data is difficult even with an unbiased estimator. The high data efficiency of GCN-like models could be contributed to the fact that they already assume the labels are low frequency. Without such assumption, we need more data in order to correctly estimate the frequency patterns.
A.3 RANDOM INITIALIZATION
While the main content of our paper showed the results for and B initialized at 0.5, our results generally hold even we initialize them randomly. Table demonstrates this claim by showing our model's performance with and | initialized randomly. SGF (0.5) is the setting showed in the main part of our paper. SGF (U[-1,1) initializes a and using a uniform distribution in [-1,1].
Both Table 5 and Figure 8 show that our model behaves similar to the fixed initialization at 0.5. It is worthwhile to mention that Figure 8a and 8b show SGF initialized randomly at the same seed but converged to two different solutions. The accuracies for these two particular cases are 89.7% for Cora nd 92.0% for Wisconsin. This result and the filter visualization in Section 6.3 refute the argument that our model is also biased toward "lowefrequency"..
14

---

Under review as a conference paper at ICLR 2021
Cora
Wisconsin
Bipartite
14-
01
03
05
1.0
0.1
09
13
02
05
Lo
641
e12
(a) r(Y) E [0.0.6] (low)
(b) r(Y) [0.6, 1.3] (mid)
(c) rY) E 2.0] (high)
Figure 7: Box plot of estimated Rayleigh quotient (frequency) by training ratio. For each training ratio, randomly sample 10 training sets and compute Rayleigh quotients using equation (1).
Table 5: Test accuracy when a and are initialized randomly
DATASETS
METHODS
Cora
Citeseer
Pubmed
Photo
Computer
SGF (0.5)
88.97 1.21
77.58
1.11
90.12 0.40
95.58 + 0.55
92.15 + 0.41
SGF (U[-1.1)
88.47 = 1.40
77.50 1.88
88.23 + 1.12
92.23 + 0.53
87.15 3.63
Wisconsin
Cornell
Texas
Chameleon
Bipartite
SGF (0.5)
87.06 + 4.66
82,45 + 6.19
80.56 + 5.63
58.77 + 1.90
100.0 = 0.00
SGF (U[-1,1]
88.66 3.40
79.13 1.60
79.67 3.62
57.83 + 2.47
100.0 = 0.00
Cora
Init.
e=40
e=
e=120
e=160
e=100
e=140
e=180
e=220
e6260
e=300
0.0
(b) Wisconsin
Figure 8: Dynamic of a's and Iss with random initialization (seed 0).
15

---

Under review as a conference paper at ICLR 2021
B EXPERIMENTAL DETAILS
B. SOURCE CODE
The source code is provided in src. zip. The instruction install Python environment and running examples can be found README. md. All results in this paper are obtained using a single machine with RTX Titan GPU (24GB). We also confirm the results CPU and another machine with GeForce 1080Ti GPU (IIGB). The provided source code works on both CPU and GPU.
B.2 EVALUATION PROCEDURE
For each dataset and each run, the following training procedure is implemented: Split, use train and validation vertices to estimate Rayleigh quotient; train the model with train set and choose the
using validation set, the hyper--araaeeers are dropout rate, learning rate, and number of layers; save the model every time best validation accuracy is reached; load the best model on validation set to evaluate on test set. Search set for each hyper-parameters:
Dropout rate: {0.4, 0.5, 0.6, 0.7,
Weight decay: {le 2, 3, 3,5, le 4, 5e - 5}
Learing rate: {0.001, 0.01, 0.02,
Number of layers: (4, 8, 16, 32, 64)
We the Syper-paramesn in bold text to report the result in the main part of our paper.
B.3
DATA SOURCE
Our datasets are obtained from the pytorch-geometric repository and the mode-clasificaiion-aatses repository GitHub. These datasets are "re-packed" with pickle and stored in src/ dat The original URLs are:
fi Fication
Citation Networks. Cora (ML), Citeseer, and Pubmed (Sen al., 2008) the set of three most commonly used networks for benchmarking vertex classification models. Vertices in these graphs represent papers, and each of them has bag-of-word vector indicating the content of the paper. Edges are citations between papers. Originally these edges are directed, but they are converted to undirected edges in the trade-off between information loss and efficiency of methods.
WebKB. WebKB dataset is a collection of university websites collected by CMUS, As we mentioned in previous sections, this dataset is special because it contains many different types of vertices that have mixed frequencies. We use the Wisconsin, Cornel, Texas subsets of this dataset.
Wikipedia. The Chameleon dataset belongs collection of Wikipedia pages where edges are references and vertex labels indicate the internet traffic. Originally this dataset was created for the vertex regression task, but here, we follow Pei (2020) to split the traffic amount into 5 categories.
The synthetic dataset is generated using NetworkX library and labeled by its bipartite parts. The features are generated randomly with Gaussian (0, 1).
B.4
OTHER METHIODS
Other methods are obtained from their respective repository on GitHub. The following are parameter settings for the "Our experiment" section of Table and 3. Since each dataset has a different hyper- parameter values, we follow the author's recommendation for the hyper-parameter not mentioned here. We confirm the results with the recommended hyper- parameters and report them the "Literature" sections.
'http:/ /t////wwww www. cmu. ammu.eduaat ft/////////ooo http://sccccccc//eeeeeeomaa
cmu. wwt../mwwb.ooooeeeeeeeeeeee 11 /wwp/wwkt
16

---

Under review as a conference paper at ICLR 2021
GCNII: 0 0.5, 0.5.
SGC: k = 2, Ir = 0.01, wd = 5 10 10-4, dropout = 0.7.
APPNP: K - 2, a = 0.2 and 0.8, Ir = 0.02, wd = 5 x 10-4, 4, dropout = 0.7. SGF-Cheby (our implementaion): Amax = {1.5, 2.0}. = 16 and other hyper-parameters are the same SGF.
17


Reviews:
[{"review_id": "ffPTbQW8Yyk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Adaptive stacked graph filter\nThe paper proposes a relatively simple formulation for a graph convolutional filter, that has the advantage of providing useful insights on the characteristic of the considered datasets. Many points of the paper are however not convincing in the present form, mainly regarding the novelty of the proposed formulation.\n\nThe paper proposes a graph convolution operator that is inspired by the well-known approximation of a graph filter using polynomials of the graph Laplacian.\n\nPros:\n- The paper proposes a simple filter formulation that allows to study the dependency on the neighborhood radius on different datasets.\n- The visualisation of the filters is interesting.\n-The reported experimental results are positive, even though in many cases the improvement does not seem significant.\n\nCons:\n-The proposed model is very similar to GCNII: Graph convolution by Kipf and Welling with a single scalar parameters instead of a parameter matrix + skip connections. The main difference with GCNII is the lack of the identity mapping. \nIn fact, eq. of H^l in page 4 is very similar to eq. 5 in https://arxiv.org/pdf/2007.02133.pdf. Authors should deeply discuss the differences between their proposal and other works in literature, clarifying their novel contribution.\n\nComments about specific sections follow.\nExperimental section:\n\t\t-In page 6, authors state that they fix the \\theta hyper-parameter of GCNII to 0.5, even though the recommended values are around 1.5.  Can you justify this choice? Also, since you run the experiments on GCNII, it would be interesting to see its performance on the bipartite dataset with \\theta = 1.5\n\t\t-In Table 3, the results from literature do not report the variance. In general, it seems like the results of the proposed method and baselines are pretty close, and in many cases inside the variance range.\n\nAppendix A:\nthe horizontal stacking variant is not explained in detail. From the figure it looks like several stacked layers with an aggregation that sums the weighted representation computed at each layer. I don't see why this should be \"horizontal\". Probably writing down the equations of this model would help.\n\nB.2. While authors state that for each dataset and for each run they select the hyper-parameters using the validation set, later in the same section they state that the results in the main paper are referred to the hyper-parameters in bold. I don't understand how the hyper-parameter selection procedure is adopted.\n\nMinor: \nTable 3, Chamaleon dataset. Missing bold on SGC. Texas: MLP is in bold while it shouldn't be\nPage 6: \"Note that we also the extact\" -> we use the\n\n-----REBUTTAL\nI acknowledge having checked authors' rebuttal and the revised version of the manuscript", "extra_scores": {}, "extra_text": {}}, {"review_id": "VXgr7O_yV5p", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to stack the graph filters with learnable polynomial parameters to construct the new graph neural network model. Generally, this paper is well organized and easy to read. Here are my concerns.\n\n1.Essentially, this paper argues that the approximation of Chebyshev polynomials in GCN can only capture the low-frequency features in the spectral domain, and proposes a more general approximation scheme by stacking the graph filter in the spatial domain.  However, the low-frequency property of GCN is highly related to the localized first-order approximation of graph convolutions. Without this first-order approximation, GCN model can capture the high-frequency information in graphs, e.g, ChebyNet [2] with large enough order K. It's better to add more discussions/comparisons with this kind of GCNs.  \n\nMoreover,  my core concern is the superiority of why the proposed polynomial approximation (in Equation 7) is better than the previous Chebyshev approximation from both theoretical and practical justifications.  In graph signal processing, using a polynomial series to approximate the graph filter has been well studied in the literature. As pointed out by [1], Chebyshev polynomial is a good approximator to approximate graph filters. It is better to add more justifications (e.g., numerical analysis) about the proposed approximation scheme.  \n\n2.Another concern is the experiment.\nDataset splitting: It seems like that this paper adopts the new splitting plan (stratified 0.6/0.2/0.2 splits) for all datasets. Meanwhile, the paper also reports the best results reported in the literature. However, I think it’s improper to put them in the same table since we can’t make a fair comparison under different data splitting.  Moreover, I would like to see the results of SGF on the public splitting of these datasets.\n\nHyperprameters: In Appendix B.4, the authors claim that they follow the hyperparameter recommendation in the original paper of baselines. However, it seems that some of the given hyperparameters are not the best hyper-parameters. For example, for Cora, \\alpha of GCNII is set to 0.2, while in   Appendix B.4, \\alpha=0.5 which inconsistent with the original paper [3].\nOn the other hand, In Appendix B.2, the authors adopt the random strategy to search the hyperparameters of SGF. Since the authors re-run all the experiments of baselines in the new splits, it’s better to conduct the same hyper-parameter search process for each baseline to ensure a fair comparison.\n\nThe filter parameters visualization: From the model construction perspective, since the only difference between SGF and GCNII/APPNP is the trainable filter parameters. Therefore, I’m curious about the value of \\alpha and \\beta after the training. Could you visualize the value of two parameters in each layer from SGF?\n\nOverall, I think this paper is marginally below the acceptance threshold.\n\n[1] David K. Hammond, Pierre Vandergheynst, and Re ́mi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011.\n[2] Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. \"Convolutional neural networks on graphs with fast localized spectral filtering.\" Advances in neural information processing systems. 2016.\n[3] Chen, M., Wei, Z., Huang, Z., Ding, B., & Li, Y. (2020). Simple and deep graph convolutional networks. arXiv preprint arXiv:2007.02133.\n \n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "V8RPke0cqDi", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY:\nThis paper addresses the problem of vertex classification using a new Graph Convolutional Neural Network (NN) architecture. The linear operator within each of the layers of the GNNN is formed by a polynomial graph filter (i.e., a matrix polynomial of either the adjacency or the Laplacian novelty). Rather than working on the frequency domain, the paper focuses on learning the polynomial coefficients of the filter on the vertex domain. The key novelty is the consideration of a stack architecture for which the polynomial filter is formed by the successive application (i.e., matrix multiplication) of filters of order one. Numerical experiments with real datasets showcase the merits, including superior classification performance, of the proposed architecture. \n \nSTRONG POINTS:\nThe paper is timely and fits nicely the scope of the conference.\n \nThe numerical experiments are convincing, offering insights, and demonstrating some of the advantages of the proposed architecture.\n \nThe writing is clear, making the paper easy to follow. \n \nWEAK POINTS:\nExcept for the numerical experiments, I find that the contribution is quite limited. The postulation of GCNN architectures based on polynomial graph filters where the focus is on learning the polynomial coefficients has been studied thoroughly in the literature. In general, the paper does a good job listing relevant works in that area, although some are missing (e.g., Gama - Ribeiro). Some of the existing works look at ARMA structures and recursive order-one filter implementations. I acknowledge that the architecture considered in those papers may not be exactly the same as the one proposed by the authors in this paper. I also appreciate that the application at hand (vertex classification) was not the goal of many of those papers. However, I still feel that the contribution falls short, especially for a top conference such as ICLR. In any case, I am open to change my mind if the authors are able to strengthen their theoretical claims or address my concerns in their rebuttal.\n\nI believe that the title should be changed. GCNN are not mentioned. The current title places the focus on Stacked Graph Filters. My first concern is that, within the linear paradigm (i.e., as polynomials of the adjacency/Laplacian matrix), this type of architectures have already been investigated. More importantly, the paper focuses on NN architectures, so I think it is reasonable to have that on the title.  \n\n \nOVERALL RECOMMENDATION:\nMarginal reject. The paper is topical, timely, and nicely written. It addresses a problem of interest and does so with contemporary machine learning tools. The results in real-world datasets are convincing. However, the contribution and novelty are limited, falling short of the average contribution at ICLR. \n \nADDITIONAL RECOMMENDATIONS:\nBeing able to obtain additional theoretical results would make the contribution more solid.\n\nFurther elaborating on the robustness of the architecture it is another change that would strengthen the manuscript.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SMtn1JswFjv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors proposed to learn the polynomial graph filter in their model. It can be viewed as adaptively learning the propagation part of APPNP and follows by a linear transformation (in features). They show the proposed model can perform well on both homophilic and heterophilic graphs.\n\nPros:\n1.\tThe idea of adaptively learn the polynomial filter seems correct and reasonable.\n2.\tResults on filter visualization and structural noise are interesting.\n\nCons:\n1.\tThe proposed methodology is not novel. A very similar idea has been proposed previously. (See Detail comments)\n2.\tProblems of over-smoothing.\n3.\tResults on experiment section (Table 2 and 3) are questionable. \n\nDetail comments:\n\nWhile the proposed idea of adaptively learning the polynomial graph filter is interesting, it has been proposed previously in not only the GNN literature [2] but also PageRank based methods [3]. Both of them proposed the idea of adaptively learn the polynomial graph filter, or equivalently the generalized PageRank weights. Hence, I do not think the current paper is completely novel. Nevertheless, the proposed methodology seems to be the correct answer for GNN to adapt to both homophilic and heterophilic graphs. One problem of the current proposed method is that why it can avoid over-smoothing when stacking many layers? The authors use a fixed initialization $\\alpha = 0.5$ which is the same as APPNP so at least at the very beginning it won’t suffer from over-smoothing. However, it is unclear how will the coefficients behave during and after training. Also, it is not clear how to initialize $\\beta$ in the model. Furthermore, if the proposed model can indeed adaptively learn the good polynomial graph filter, why doesn’t the random initialization work? Does that mean the implicit bias of the specific initialization proposed in the paper is necessary? If that is the case, then I do not see why the claim of “adaptive learning” is correct since it is actually sensitive to the initialization.\n\nBeside the methodology and novelty, I also find the experiment section questionable. Firstly, since the main theme of the paper is learning the polynomial filter, the authors should at least compare their method with ChebNet (GCN-Cheby)[5] which also use polynomial filter. Note that in both [4] and [2], they all show that ChebNet can better adapt to heterophilic graphs compare to GCN and GAT.\n\nOn the other hand, according to Appendix B.4, the authors use $K=2$ (propagation step) for APPNP. This is *NOT* the suggested hyperparameter reported in [1] ($K=10$). Note that the authors of [1] even show that if we choose a larger $K\\geq 10$, the performance can be slightly improved on Cora, Citeseer and PubMed. In contrast, SGF use $K=16$ which is not a fair comparison to APPNP. There should be a experiment that compares APPNP with SGF under the same $K$.\n\nFinally, the authors claim the performance of most baseline methods are found in the literature. However, this is also problematic to me. Note that in the original GCN and GAT paper, the date split is much sparse then the $0.6/0.2/0.2$ split proposed by the authors. Also, in the Geom-GCN paper they do test their model on Chameleon in the split $0.6/0.2/0.2$. Why is it stated as not available? Even if we assume all the problem above can be well explained, the improvement of the proposed model seems not statistically significant. For example, on Wisconsin, Cornell and Texas, although SGF has the highest accuracy in average, the standard deviation is very large. MLP is within 1 standard deviation. Please report the confidence interval to show that the gain of SGF is indeed statistically significant. On the other hand, SGF is worse than not only SGC but also GCNII by a large margin on Chameleon. If SGF can indeed learn the near-optimal polynomial filter, then why this is the case? At last, in the original Geom-GCN paper, they also have the Actor dataset. I think it would be great if the authors can put this result at least in the Appendix.\n\nBesides these weaknesses, I still find the paper well written. Also, the experiment on filter visualization and structural noise are quite interesting. I believe the paper can be greatly improved if all the concerns above can be addressed.\n\nMinor comments:\n\nIn page 2, the authors state that the normalized adjacency matrix with added self-loops is $\\tilde{A}= I-D^{-1/2}A D^{-1/2} + c$, where $c$ is some diagonal matrix. This is incorrect. Note that when we add self-loops, the degree matrix $D$ has to changed accordingly. Please see the correct expression in [1] for example.\n\nIn page 2, the Rayleigh quotient $r(\\mathcal{L},x)$ is defined with two input arguments but later the authors ignore $\\mathcal{L}$. While it is clear from the context, the notation is not rigorous.\n\nIn page 1 introduction section, the authors mention that the model does not need to tune the hyper-parameters. However, in the same page contribution section, the authors mention that they use one hyper-parameter setting. According to their experiment section, I think what they mean is the previous. It would be great to clarify the ambiguity here.\n\nReference:\n\n[1] “Predict then Propagate: Graph Neural Networks meet Personalized PageRank,” Klicpera et al., ICLR 2018.\n\n[2] “Adaptive Universal Generalized PageRank Graph Neural Network,” Chien et al., arXiv:2006.07988.\n\n[3] “Adaptive diffusions for scalable learning over graphs,” Berberidis et al., In Mining and Learning with Graphs Workshop @ ACM KDD 2018, pp. 1, 8 2018.\n\n[4] “Generalizing Graph Neural Networks Beyond Homophily,” Zhu et al., NeurIPS 2020. (arXiv:2006.11468) \n\n[5] “Convolutional neural networkson graphs with fast localized spectral filtering,” Defferrard et al., NeurIPS 2016.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The topic covered by the paper is timely, and the way the authors have addressed the problem seems correct. The provided empirical evidence seems to be sufficient to support the main claim of the paper. Presentation is well structured and clear.
Notwithstanding the above merits, the proposed approach seems to confirm other similar proposals presented in the literature, so the contribution of the paper seems to be limited. Although presentation is good, it is not highlighting enough the differences w.r.t. those proposals and the basic approximation result given by Chebyshev polynomials. Especially a better theoretical characterisation w.r.t. to approximation capabilities by Chebyshev polynomials (with no truncation) would have helped to better gain understanding of the merits of the proposed approach. Finally, some of the experimental results do not seem to have a significant  statistical difference w.r.t to the baselines, so it would have helped to have the result of a statistical test.
Decision: Reject