Simple Spectral Graph Convolution
Authors: Hao Zhu
Piotr Koniusz
Venue: ICLR 2021 Poster (2021)
Keywords: Graph Convolutional Network
Oversmoothing

Abstract: Graph Convolutional Networks (GCNs) are leading methods for learning graph representations. However, without specially designed architectures, the performance of GCNs degrades quickly with increased depth. As the aggregated neighborhood size and neural network depth are two completely orthogonal aspects of graph representation, several methods focus on summarizing the neighborhood by aggregating K-hop neighborhoods of nodes while using shallow neural networks. However, these methods still encounter oversmoothing, and suffer from high computation and storage costs. In this paper, we use a modified Markov Diffusion Kernel to derive a variant of GCN called Simple Spectral Graph Convolution (SSGC). Our spectral analysis shows that our simple spectral graph convolution used in SSGC is a trade-off of low- and high-pass filter bands which capture the global and local contexts of each node. We provide two theoretical claims which demonstrate that we can aggregate over a sequence of increasingly larger neighborhoods compared to competitors while limiting severe oversmoothing.  Our experimental evaluations show that SSGC with a linear learner is competitive in text and node classification tasks. Moreover, SSGC is comparable to other state-of-the-art methods for node clustering and community prediction tasks.

Published as a conference paper at ICLR 2021
SIMPLE SPECTRAL GRAPH CONVOLUTION
Hao Zhu, Piotr Koniusz*
Australian National University Canberra, Australia
Data61/ 1/CSIRO Canberra, Australia
(hao, zhu, piotr. koniusz ) eaa.eannuuu.... au
ABSTRACT
Graph Convolutional Networks (GCNs) are leading methods for learning graph representations. However, without specially designed architectures, the perfor- mance of GCNs degrades quickly with increased depth. As the aggregated neigh- borhood size and neural network depth are two completely orthogonal aspects of graph representation, several methods focus on summarizing the neighborhood by aggregating K -hoop neighborhoods of nodes while using shallow neural networks. However, these methods still encounter oversmoothing, and suffer from high com- putation and storage costs. In this paper, we use a modified Markov Diffusion Ker- nel to derive variant of GCN called Simple Spectral Graph Convolution GC) Our spectral analysis shows that our simple spectral graph convolution used S'GC is trade-off of low- and high-pass filter bands which capture the global and local contexts of each node. We provide two theoretical claims which demon- strate that we can aggregate over sequence of increasingly larger neighborhoods compared to competitors while limiting severe oversmoothing. Our experimen- tal evaluations show that SC with linear learner is competitive in text and node classification tasks. Moreover, S²GC is comparable to other state-of-the-art methods for node clustering and community prediction tasks.
INTRODUCTION
In the past decade, deep learning has become mainstream in computer vision and machine learn- ing. Although deep learning has been applied for extraction of features on the Euclidean lattice (Euclidean grid-structtred data) with great success, the data in many practical scenarios lies on non-Euclidean structures, whose processing poses challenge for deep learning. By defining a con- volution operator between the graph and signal, Graph Convolutional Networks (GCNs) generalize Convolutional Neural Networks (CNNs) to graph-structuree inputs which contain attributes. Mes- sage Passing Neural Networks (MPNNs) (Gilmer et al. 2017) unify the graph convolution as two functions: the transformation function and the aggregation function. MPNN iteratively propagates node features based on the adjacency of the graph in a number of rounds.
Despite their enormous success in many applications like social media, traffic analysis, biology, recommendation systems and even computer vision, many of the current GCN models use fairly shallow setting as many of the recent models such GCN (Kipf & Welling 2016) achieve their best performance given 2 layers. In other words, 2-layer GCN models aggregate nodes in two-hops neighborhood and thus have no ability extract information K K-hops neighborhoods for K > 2. Morcover, stacking more layers and adding non-linearity tend to degrade the performance of these models. Such a phenomenon is called oversmoothing (Li al. 2018a), characterized by the effect that as the number of layers increases, the representations of the nodes in GCNs tend to converge similar, non-distinetive from one another value. Even adding residual connections, an effective trick for training very deep CNNs, merely slows down the oversmoothing issue (Kipf & Welling. 2016) in GCNs. It appears that deep GCN models gain nothing but the performance degradation from the deep architecture.
One solution for that is to widen the receptive field of aggregation function while limiting the depth of network because the required neighborhood size and neural network depth can be regarded as
Thhe corresponding author. The code available wttpt:ttt/////t.. http:///ggtttuuuuc htt.c/////.eeaao////eeaaaeaa/

---

Published as a conference paper at ICLR 2021
two separate aspects of design. To this end, SGC (Wu et al. 2019) captures the context from K- hops neighbours in the graph by applying the K-th power of the normalized adjacency matrix in a single layer of neural network. This scheme is also used for attributed graph clustering (Zhang al. 2019). However, SGC also suffers from oversmoothing as K ~> oo, as shown in Theorem | PPNP and APPNP (Klicpera et al.] (0T9a) replace the power of the normalized adjacency matrix with the Personalized PageRank matrix to solve the oversmoothing problem. Although APPNP relieves the oversmoothing problem, it employs a non-linear operation which requires costly computation of the derivative of the filter due to the non-linearity over the multiplication of feature matrix with learnable weights. In contrast, we show that our approach enjoys free derivative computed in the feed-forward step due to the use of linear model. Furthermore, APPNP aggregates over multiple k-hop neighborhoods (k=0,... ..... K) but the weighting scheme favors either global or local context making it difficult if not impossible to find good value of balancing parameter. In contrast, our approach aggregates over k-hop neighborhoods in a well-balanced manner.
GDC [Klicpera et al. 2019b) further extends APPNP by generalizing Personalized PageRank (Page 1999) to an arbitrary graph diffusion process. GDC has more expressive power than SGC (Wu 2.19). PPNP and APPNP (Klicpera et al. 2019a) but it leads to dense transition matrix which makes the computation and space storage intractable for large graphs, although authors suggest that the shrinkage method can be used to sparsify the generated transition matrix. Noteworthy also orthogonal research directions of [Snn et al. (2019); Koniusz & Zhang (2020); Flinas et al. (2020) which improve the performance of GCNs by the perturbation of graph, high-order aggregation of features, and the variational inference, respectively.
ct al.
et al.
To tackle the above issues, we propose a Simple Spectral Graph Convolution GS² network for node clustering and node classification in semi-supervised and unsupervised settings. By analyzing the Markov Diffusion Kernel (Fouss et al. 2012). we obtain a very simple and effective spectral filter: we aggregate k-step diffusion matrices over k = 0, K steps, which is equivalent to aggregating over neighborhoods of gradually increasing sizes. Moreover, we show that our design incorporates larger neighborhoods compared to SGC and copes better with oversmoothing. We explain that limiting overdominance of the largest neighborhoods in the aggregation step limits oversmoothing while preserving the large context of each node. We also show via the spectral analysis that SCGC is a trade-off between the low- and high-pass filter bands which leads to capturing the global and local contexts of each node. Moreover, et al. 2019a) are related and explain why S'GC captures a range of neighborhoods better than APPNP. Our experimental results include node clustering, unsupervised and semi-supervised node classification, node property prediction and supervised text classification. We show that GC is highly competitive, often significantly outperforming ofte-oofthhe-rt methods.
show how SCGC and APPNP (Klicpera
2 PRELIMINARIES
Notations. Let G = (V, E) be a simple and connected undirected graph with n nodes and m edges. We use (1.... n to denote the node index of G, whereas d, denotes the degree of node j in G. Let A be the adjacency matrix and D be the diagonal degree matrix. Let A = A + I, denote the adjacency matrix with added self-loops and the corresponding diagonal degree matrix D, where I, E S is an identity matrix. Finally, let X E Raxd denote the node feature matrix, where each node v is associated with a d- d-dimensional feature vector X,. The normalized graph Laplacian matrix is defined as L I D D-1/2 D-D 1/2 E ST, that is, a symmetric positive semidefinite matrix with eigendecomposition UAUT, where A is a diagonal matrix with eigenvalues of L, and U e gaxn is a unitary matrix that consists of the eigenvectors of L.
Spectral Graph Convolution (Defferrard et al., 2016). We consider spectral convolutions on graphs defined the multiplication of signal x 1 with filter go parameterized by 0 R in the Fourier domain:
go (L) * r = UgZ (A)U x,
(1)
where the parameter 0 E R" is vector of spectral filter coefficients. One can understand go function operating on eigenvalues of L, that is, g (A). To avoid cigendecomposition, (A) can be approximated by a truncated expansion in terms of Chebyshev polynomials Ta(A) up to the K-th
2

---

Published as a conference paper at ICLR 2021
order (Defferrard al. 2016):
K-1 Σ (A), km0
(A) ~
(2)
with a rescaled A 2Ammn A In where Amax denotes the largest eigenvalue of L and 0 E R is now a vector of Chebyshev coefficients.
Vanila Graph Convolutional Network (GCN) Kipff & Welling 2016). The vanilla GCN is first-order approximation of spectral graph convolutions. If one sets K = 1, 0o = 2, and 01 = -1 for Eq. 2 they obtain the convolution operation go go( * x = D A-DD1//AADD///
Finally,
by the renormalization trick, replacing matrix I + D 1/2 AD 1/2 by a normalized version T = D D-1/2AD 1/2 (D (A + I.)(D I.. -1/2 leads to the GCN layer with non-linear function d:
H o TH w()).
Graph Diffusion Convolution (GDC) Klicpera et al. 2019b). A generalized graph diffusion is given by the diffusion matrix:
T
with the weighting coefficients 0g and the generalized transition matrix T. Eq. can regarded as related to the Taylor expansion of matrix-values' functions. Thus, the choice of 0g and T must at least ensure that Eq. Sq..Dconvers converges. Klicpera et al. (2019b) provide two special cases as low-pass filters ie., the heat kernel and the kernel based on random walk with restarts. If S denotes the adjacency matrix and D is the diagonal degree matrix of S, the corresponding graph diffusion convolution is then defined as D 1/2SD x/2x. Note that 0g can be a learnable parameter, or it can be chosen in some other way. Many works use the expansion in Eq. 4 but different choices of 0g realise very different filters, making each method unique.
Simple Graph Convolution (SGC) (Wu et al. 2019). A classical MPNN (Gilmer et al. 2017) averages (in each layer) the hidden representations among 1-hop neighbors. This implies that each node in the K-th layer obtains feature information from all nodes that are K K-hops away in the graph. By hypothesizing that the non-lineant non-linearity between GCN layers is not critical, SGC captures information from K-hops neighborhood in the graph by applying the K-th power of the transition matrix in single neural network layer. The SGC can be regarded as a special case of GDC without
non-linearity and without the normalization by D 112 if we set 0x = and 0ick = 0 in Eq. and T= = T, which yields:
= softmax XW).
Although SGC is an efficient and effective method, increasing K leads to oversmoothing. Thus, SGC uses a small K number of layers. Theorem [ shows that oversmoothing is result of conver- gence to the stationary distribution in the graph diffusion process when time i + xo.
Theorem 1. (Chung & Graham 1997 Let d2 denote the second largest eigenvalue of transition matrix T D A of a non con-bipartite graph, p(t) be the probability distribution vector and the stationary distribution. If walk starts from the vertex i, (o(0) = 1, then after I steps for every vertex, we have:
-
-
(6)
APPNP. Klicpera et al. (2019a) proposed to the Personalized PageRank to derive fixed filter of order K. Let XX) denote the output of a two-layer fully connected neural network on the feature matrix X, then the PPNP model is defined as H al, (1 a)T- To avoid calculating the inverse of matrix T. Klicpera al. (2019a) also propose the Approximate PPNP (APPNP), which replaces the costly inverse with an approximation by the truncated power iteration:
(I+1) = - @ + oH
(7)
where O = fo(X) = XeW or ( MLP(()))))))) By decoupling feature transfor- mation and propagation steps, PPNP and APPNP aggregate information from multi-hop neighbors.
3

---

Cora Published as a conference paper at ICLR 2021
Eigenvalues After Filtering
eig D-112 AD 1122
1.5
0.5
((A)= _ A
Elgenvalus
-0.5
0.5
02
0.5 Eigenvalues Before Filtering
-0.5
500
1000
1500
2000
2500
Index
(a)
(h)
Figure 1: (a) Function f(A) = K Σ A with X E [-1,1], K E {1,4,8,16) (b) Sorted by
index, cigenvalues of D 11/2 ADD 1/2 and push-forward eigenvalues f(A) * * A
network (K = 16).
METHODOLOGY
Below, firstly outline two claims which underlie the design of network, with the goal of mitigating oversmoothing. Moreover, we analyze the Markov Diffusion Kernel (Fouss et al.) 2012) and note that acts low-pass spectral filter of various degree. Based the feature mapping function underlying this kernel, we present our Simple Spectral Graph Convolution network and discuss its relation with other models. Finally, we provide the comparison of computational and storage complexity requirements.
3.1 MOTIVATION
Our design follows Claims and II described in Section A.3 which includes their detailed proofs.
Claim I. By design, our filter gives the highest weight to the closest neighborhood of node, as neighborhoods N of diffusion steps A: 0,.... K obey N((T)) C (((TT) .... ....C.(TT C (TT)). ). That is, smaller neighborhoods belong larger neighborhoods too.
Claim II. As K + xc, the ratio of energies contributed by SºGC to SGC is 0. Thus, the energy of receptive field (largest k) will dominate the sum energy of our filter. Thus, SCGC can incorporate larger receptive fields without undermining contributions of smaller receptive fields. This is substantiated by Table where SCGC achieves the best results for K 16, whereas SGC achieves poorer results by comparison, whose peak is at K =4 (note that larger K is better).
3.2 MARKOV DIFFUSION KERNEL
Two nodes are considered similar when they are diffused a similar way through the graph, as then they influence the other nodes in similar manner (Fouss et al.) 2012). Moreover, two nodes are close neighbors if they are the same distinct cluster. The Markov Diffusion distance between nodes and j time K is defined as:
dy(K) [X((K) (((K))x((X)))) (K)
(8)
where the average visiting rate x; (K) after K steps for a process that started time k computed as follows:
(K) = K k=
T (0)
(9)
By defining Z(K) 1 K Ek=1 Th we reformulate Eq.
8 as the following metrie:
(K) ( IZ(K)(x;
(0)
(10)
4

---

Published as a conference paper at ICLR 2021
The underlying feature map of Markov Diffusion Kernel (MDK) is given (0K)xx(0) for node i.
The effect of the linear projection Z(K) (filter) acting on spectrum as f(A) - Σ A (we sum from 0 to include self-loops) is plotted in Figure I from which we observe the following properties: (i) Z(K) preserves leading (large) eigenvalues of T and (ii) the higher K is the stricter the low-pass filter becomes but the filter also preserves the high frequency. In other words, as K grows, this filter includes larger and larger neighborhood but also maintains the closest locality of nodes. Note that I=I- T. where L is the normalized Laplacian matrix and T is the normalized adjacency matrix. Thus, keeping large positive cigenvalues for T equals keeping small cigenvalues for L.
3.3 SIMPLE SPECTRAL GRAPH CONVOLUTION
Based on the aforementioned Markov Diffusion Kernel, we include self-loops and propose the Sim- ple Spectral Graph Convolution (S+GC) network with the softmax classifier after the linear layer:
K
y = softmax
T'XW).
(11)
Let |x:1|2 1, Vi (each is row in X). If - 0o then H=Σ representation of the normalized Laplacian Regularization problem given below:
0c k=
T
is the optimal diffused
arg min s.1. 1,,
(H), where gH)) - 2
h
1
+ 2
Σ h X xi11) (12)
d
and each vector h, denotes the i-th of H. Compared with the more common form in (Zouu et al. 2004), we impose [h: |1, = to minimize the difference between h, and x; via the cosine distance rather than the Euclidean distance. Differentiating (H) with respect H, have (I T>-1, where (I = T
LH X 0. Thus, the optimal representation However, the infinite expansion resulting from Eq. 12 is in fact suboptimal due to oversmoothing. Thus, include in Eq. 11 a self-loop T II, the [0, parameter (Table evaluaats its impact) to balance the self-information of node vs. consecutive neighborhoods, and we consider finite K. We generalize the Eq. as:
K Σ k=1
(I w)
Ý = softmax
(13)
K
GDC uses the entire filter matrix S of size n x n as S is re-normalized numerous times by its degree. Klicpera et al. (2019b) explain that 'most graph diffusions result in dense matrix S
Relation of SCC to GDC.
In contrast, approach is simply computed as (ΣK1 T W (plus the self-loop), where X is of size n x d, and < n, where n and are the number of nodes and features, respectively. The T x step is computed as T (T (... (TX)... ...)), which requires K sparse matrix-matrix multiplications between sparse matrices of size extremely large graphs as SCG does not need to sparsify dense filter matrices (in contrast to GDC).
and dense matrix of size x d. Thus, S²GC can handle
Relation of S²GC to APPNP. Let H XW as we use the linear step in our SCGC. Then and only then, for = 0 and H = XW, APPNP expansion yields H = (1 a) TXW + oXW ((1- T x. which is equal our Z(1)XW EE* k= T TX + X (T +
W) if 0.5, K = 1, except for scaling (constant) of H
In contrast, for 1 and general case H fX: W). APPNP yields 2 (1-a)2T² f(:; W)+
(1 (1-a)aTf(Xx a W) from which is easy to note specific weight coefficients (1 a1-a)?,
(1 - a)a and associated with 2- 1-, and O-hops. This shows that the APPNP expansion is very different to the SCGC expansion in Eq. [3] In fact. SCGC and APPNP are only equivalent a = 0.5,
K and is the linear transformation.
5

---

In contrast, the storage cost of GDC approximately On and the computational cost approx- imately O K| El). where is the node numbers, K is the order of terms and |F] is the number of graph edges. APPNP, SGC and S²GC have much lower cost than GDC. Note that K'FFld >> Knd Published as a conference paper at ICLR 2021
Table I: Computational and storage complexities ((-)-
Stage
Complexity
APPNP
GDC
SGC
S.GC
Forward
Computation Cost
K| + Knd
2 K
K|bin
K|
K KBBld + Knd
Propagation
Storage Cost
nd +
2 n2
nd + |
nd + E
Backward
Computation Cost
K]
0
Propagation
Storage Cost
nd +
0
0
Moreover, as APPNP assumes H = f(X; W) ReLU((X)) (or MLP in place of ReLU), their optimizer has to backpropagate through f(X; W) to obtain 8f
ow and multiply this result with the above expansion e.g., oW = (1 - a f X; W) + (1 - a a W) + (x; W).
2H
In contrast, we use the linear function XW. Thus, 2XW yields X. Thus, the multiplication of our expansion with X for the backpropagation step is in fact obtained in the forward pass which makes our approach very fast for large graphs.
oW
Relation of SCGC to AR. The AR filter (Li et al. 2019) uses the regularized Laplacian kernel Smola & Kondor 2003) which differs from the (modified) Markov Diffusion Kernel used by Specifically, the regularized Laplacian kernel uses the negated Laplacian matrix -L yielding Kg
Z a* (-L)* = (I + aL)- where L = I- T, which is related to the von Neumann diffusion - a A In contrast, the Markov Diffusion Kernel is defined as KMD (K) Z Z(K)ZT(K)) where Z(K)= K Σ T and - --IAAAD------
kernel KvN = kk
(0018) combine interme- diate node representations from each layer by concatenating them in the final layer. However, (Xu et al. (0188) use non-linear layers, which results in a completely different network architecture and the usual slower processing time due to the complex backpropagation chain.
Relation of GC to Jumping Knowledge Network (JKN). Xu et al.
3.4 COMPLEXITY ANALYSIS
For S2GC, the storage costs is O( + nd), where |E| is the total edge count, nd relates to saving the T X during intermediate multiplications T TT (...
(..) (TX)...)). The computational cost is O Knd). Each sparse matrix multiplication TX costs |E]d We need K such multiplications, where Knd and nd are costs of summation over filters and adding features X.
and n >> d. We found that APPNP, SGC and SC have similar computational and storage costs in the forward stage. We note that symbol d in APPNP is not the dimension features X but dimension of f(X), which is the number of categories.
For the backward stage including computations of the gradient of the classification step, the compu- tational costs of GDC, SGC and GC are independent of K and |E] because the graph convolution for these methods does not require backpropagation (the gradients is computed in the forward step). In contrast, APPNP requires backprop explained earlier.
Table T summarizes the computational and storage costs of several methods. Table 2 demonstrates that APPNP is over 66x slower than S*GC on the large scale Products dataset (OGB benchmark) despite, for fairness, we use the same basic building blocks of PyTorch among compared methods.
4 EXPERIMENTS
In this section, we evaluate the proposed method on four different tasks: node clustering, community prediction, semi-supervised node classification and text classification.

---

Published as a conference paper at ICLR 2021
Table 2: Timing (seconds) Cora, Citeseer, Pubmed and the large scale Open Graph Benchmark
(OGB) which includes Products.
methods
Cora
Citeseer
Pubmed
Products
SGC
0,45
0.55
0.78
9.8
APPNP
1.08
1.44
1.32
748
SCGC
0.67
0.81
0.79
11.4
Table 3: Clustering performance with three different metrics on four datasets.
Methods
Input
Cora
Cieeseer
Pubmed
Wiki
NM1%
Acc%
F1%
Acc
NM1%
k-meuns
Feature
34.65
16.73
25.42
38.49
17.02
30.47
57.32
29.12
57.35
33.37
30.20
24.5T
Spectral-f
Feature
36.26
15.09
46.23
21.19
33.70
59.91
32.55
58.61
41.28
43,99
25.20
Spectral-g
Graph
34.19
19.49
30.17
25.91
11.84
29.48
39.74
3.46
51.97
23.58
19.28
17.21
DeepWalk
Graph
46.74
31.75
38.06
36.15
9.66
26.70
61.86
16.71
47.06
38.46
32.38
25.74
GAF
Both
53.25
40.69
41.97
41.26
18.34
29.13
64.08
22.97
49.26
17.33
11.93
15.35
VGAE
Both
55.95
38.45
41.50
44.38
22.71
31.88
65.48
25.09
50.95
28.67
30.28
20.49
ARGE
Both
64,00
44,90
61.90
57.30
35.00
54.60
59.12
23.17
58.41
41.40
39.50
38.27
ARVGE
Both
62.66
45.28
62.15
54.40
26.10
52.90
58.22
20.62
23.04
41.55
40.01
37,80
AGC
Both
68.92
41.13
31.59
47.65
S-GC
Both
69.60
54.71
65.83
69.11
42,87
64.65
70.98
33.21
70.28
52.67
49.62
44.31
4.1
NODE CLUSTERING
We compare SCGC with three variants of clustering: (i) Methods that only use node features ie., k-means and spectral clustering (spectral-f) that construct a similarity matrix with the node features by linear kernel. (ii) Structural clustering methods that only use graph structures ie., spectral clustering (spectral-g) that takes the node adjacency matrix as the similarity matrix, DeepWalk (Per-) ozzz et al. 2014), and (iii) Attributed graph clustering methods that utilize both node features and graph structures: Graph Autoencoder (GAE) and Graph Variational Autoencoder (VGAE) (Kipf Welling 2016), and Adversarially Regularized Graph Autoencoder (ARGE), Variational Graph Autoencoder (ARVGE) (Pan al. 2018) and AGC (Zhang et al.) 2019). To evaluate the clustering performance, three performance measures are adopted: clustering Accuracy (Acc), Normalized Mu- tual Information (NMI) and macro F1 F1-score (F1). We run each method 10 times four datasets: Cora, CiteSeer, PubMed, and Wiki, and we report the average clustering results in Table B where top-1 results are highlighted bold. To adaptively select the order K, use the clustering per- formance metric: internal criteria based on the information intrinsic to the data alone Zhang et al. 2019))
4.2 COMMUNITY PREDICTION
We supplement our social network analysis by using SCGC to inductively predict the community structure on Reddit, a large scale dataset, as shown in Table 10 which cannot be processed by the vanilla GCN Kipf & Welling (016)) and GDC (Klicpera et al., 2019b) due to the memory issues. On the Reddit dataset, we train GCGC with L-BFGS using no regularization, and we set = 5 and 0.05. We evaluate SCGC inductively according protocol (Chen et al. (018)). We train SCGC on a subgraph comprising only training nodes and test on the original graph. On all datasets, we tune the number of epochs based on both the convergence behavior and the obtained validation accuracy.
For Reddit, we compare SCGC to the reported performance supervised and unsupervised variants of GraphSAGE (Hamilton et al. 2017), FastGCN (Chen al., 2018). SGC (Wu et al. 2019) and DGI (Velickovic et al. 2201)). Table 4 also highlights the setting of the feature extraction step for each method. Note that SC and SGC involve no learning because they do not learn any parameters to extract features. The logistic regression is used as the classifier for both unsupervised and no-learning approaches to train with labels afterward.
4.3 NODE CLASSIFICATION
For the semi-supervised node classification task, apply the standard fixed training, validation and testing splits (Yang et al. (2016) on the Cora, Citeseer, and Pubmed datasets, with nodes per class for training. 500 nodes for validation and 1,000 nodes for testing. For baselines, We include

---

Published as a conference paper at ICLR 2021
Table 4: Test Micro Fl Score (%) aver- aged over 10 runs on Reddit. Results of other models are taken from their papers. Setting
Table 5: Test accuracy (%) averaged 10 runs
on citation networks.
methods
Cora
Cileseer
Pubmed
Model
Test Fl
GCN
8T.4 0.4
70.91 0.5
79.01 0.4
SAGE-mcan
95.0
GAT
83.32 0.7
72.6: 0.6
78.51 0.3
Supervised
SAGE-LSTI
95.4
FastGCN
79.8= 0.3
68.8+ 0.6
77.4+ 0.3
SAGE-GCN
93.0
GIN
77.6+ 1.1
66.1+ 0.9
77.0+ 1.2
FasGGCN
DGI
82.5 0.7
71.6 0.7
78.4+ 0.7
SAGE-mcan
89.7
SGC
81.0 0.03
71.9 0.11
78.9 0.01
Unsupervised
SAGE-LSTM
90.7
MixHop
81,8
71.41088
80.0
SAGE-GON
APPNP
83.3
71.7:10.6
80,110.2
DGI
94.0
Chebynet
78.0 0.4
70.1 0.5
78.0 0.4
SGC
94.9
AR filter
80.8 0.02
69.3 0.15
78.1 0.01
No Learning
GC
95.3
Ours
83.5 0.02
73.6 0.09
80.2 0.02
Table Test accuracy (%) averaged over 10 runs on the large-scale OGB node property prediction
benchmark.
methods
Products
Mag
Arxiv
MLP
61.06+00.88
26.92:10.26
55.50++0223
GCN
75.64+0.221
30.43::.225
71.74::0.29
GraphSage
0.119
31.53:10.15
71.49:10.27
Softmax
47.70:10.03
24.13:10.03
52.77:0.56
SGC
68.87 0.01
29.47+-0.03
68.78+0002
S'GC
70.22+ 0.01
32.47=0.111
70.15+00.13
S'GC+MLP
76.84+1.20
32.72+1..3
72.01
three sate--of-thh-art shallow models: GCN (Kipf & Welling 2016), GAT (Veličković et al. 2017
FastGCN (Chen et al. 2018), APPNP (Kliepera et al. 2019a). Mixhop (Abu-EI-Haija et al. 2019
SGC (Wu al. 2019) DGI Velickovie et al.) 2019) and GIN (Xu et al. 2018a). We use the Adam SGD optimizer (Kigmma & Ba 2014) with a learning rate of 0.02 to train SCGC. We set a 0.05
and K 16 all datasets. To determine K and a, we used the MetaOpt package |Bersstra et al. (013)) with 20 steps to meta-optimize hyperparameters on the validation set of Cora. Following 0.05 across all datasets so K and are tuned to individual datasets at all. We will discuss the influence of and K later.
that, we fixed K 16 and
To evaluate the proposed method on large scale benchmarks (see Table G we use Arxiv, Mag and Products datasets to compare the proposed method with SGC, GraphSage, GCN, MLP and Softmax (multinomial Regression). On these three datasets, our method consistently outperforms SGC. On Arxiv and Products, our method cannot outperform GCN and GraphSage while MLP outperforms softmax classifier significantly. Thus, we argue that MLP plays more important role here than the graph convolution. To prove this point, also conduct experieeee use MLP in place of the linear classifier, and we obtain a more powerful variant S²GC. On Mag, S'GC+MLP outperforms SCGC by tiny margin because the performance of MLP is close to the one of softmax. On other two datasets, GCGMLPP a very strong performer. Our G²GC+MLP is the best performer Mag and Arxiv.
experiment GS*GC+MLP) for which
4.4 TEXT CLASSIFICATION
Text classification predicts the labels of documents. Yao et al. (2019) use 2-layer GCN to achieve state-of-the-ard results by creating a corpus-level graph, which treats both documents and words as nodes in graph. Word-to-word edge weights are given by Point-wise Mutual Information (PMI) and word-document edge weights are given by the normalized TF-IDF scores.
We experiments five widely used benchmark corpora including the Movie Review (MR), 20-Newsgroups (2ONG), Ohsumed, R52 and R8 of Reuters 21578. We first preprocessed all datasets by cleaning and tokenizing text as Kim (2014). We then removed stop words defined in NLTK6 and fow-frequency words appearing less than times for 20NG, R8, R52 and Ohsumed. We compare method with GCN (Kipf & Welling 2016) and SGC (Wu et al. 2019). The statisties of the
8

---

Published as a conference paper at ICLR 2021
Table 7: Test accuracy the document classification task.
Model
20NG
R8
R52
Ohsumed
MR
Text GCN
$7.9
97.0 = 0.2
93.8 0.2
68.2 = 0.4
76.3 1: 0.3
SGC
88.5 0.1
97.2 = 0.2
94.0 + 0.2
68.5 0.3
75.9 0.3
S-GC
88.6 0.1
97,4 + 0.1
94.5 + 0.2
68.5 0.1
76.7 + 0.0
Table Summary of classification accuracy (%) w.r.t. various depths. In the linear model, the filter parame- ter K is equivalent to the number layers.
Table 9: Classification aceuracy (%) w.r.t
Dataset
Methed
Layers (K)
a.
2
8
16
32
64
Dataset
0.0
0.05
0.1
0.15
Cora
GCN
81.1
80.4
69.5
64.9
60.3
28.7
Cora
82.9
83.5
SGC
80.8
81.5
80.7
79.0
66.8
Citescer
72.8
73.6
73.0
73.6
S-GC
79.8
83.5
82.6
82.0
Pubmed
79.8
80.2
80.1
79.8
Cileseer
GCN
67.6
18.3
20.0
SGC
71.9
72.6
73.1
72.2
70.6
69.2
S²GC
70.7
72.6
72.7
73.6
74.0
73.4
Pubmed
GCN
79.0
76.5
61.2
40.9
22.4
35.3
SGC
79.2
79.7
78.4
76.4
71.6
68.6
SCGC
78.5
79.2
79.7
80.2
79.1
78.1
Table shows that SCGC rivals their models on 5 benchmark datasets. We provide the parameters setting in the supplementary material.
preprocessed datasets are summarized in Table
4.5 A DETAILED COMPARISON WITH VARIOUS NUMBERS LAYERS AND
Table Table&&summnn summaries the results for models with various numbers of layers (K is the number of layers and it coincides with the number of aggregated filters in SCGC). We observe that on Cora, Citeseer and Pubmed, our method consistently obtains the best performance with K 16, equivalent of 16 layers. Overall, the results suggest that SCGC can aggregate over larger neighborhoods better than SGC while suffering less from oversmoothing. In contrast to S²GC, the performance of GCN and SGC drops rapidly as the number of layers exceeds 32 due to oversmoothing.
Table 9 summaries the results for the proposed method for various ranging from to 0.15. The table shows that slightly improves the performance of SºGC. Thus, balancing the impact of self- loop by a w.r.t. other filters of consecutively larger receptive fields useful but the self-loop not mandatory.
CONCLUSIONS
We have proposed Simple Spectral Graph Convolution (S²GC), method extending the Markov Diffusion Kernel (Section 3.2) whose feature maps emerge from the normalized Laplacian Reg- ularization problem (Section 3.3) if K oc. cc. Our theoretical analysis shows that GCGC obtains right level of balance during aggregation of consecutively larger receptive fields. We have shown there exists connection between S²GC and SGC, APPNP and JKN by analyzing spectral properties and implementation of each model. However, as our Claims and show that we have designed filter with unique properties capture cascade of gradually increasing contexts while limiting oversmoothing by giving proportionally larger weights to the closest neighborhoods each node. We have conducted extensive and rigorous experiments which show that GCG is competi- tive frequently outperforming many state-of-the-as methods on unsupervised, semi-supervised and supervised tasks given several popular dataset benchmarks.
ACKNOWLEDGMENT
This research is supported by an Australian Government Research Training Program (RTP) Schol- arship.

---

Published 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 architectures via sparsified neighborhood mixing. In International Conference on Machine Learn- ing, pp. 21-29, 2019.
Afonso S Bandeira, Amit Singer, and Daniel A Spielman. A cheeger inequality for the graph con- nection laplacian. SIAM Journal on Matrix Analysis and Applications, 34(4):1611-1630 2013.
James Bergstra, Brent Komer, Chris Eliasmith, Dan Yamins, and David D Cox. Hyperopt: python library for model selection and hyperparameter optimization. Computational Science & Discovery, 8(1):014008, 2015. h
lop. Loo..org/1149944999///11111
014008
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Kenneth Ward Church and Patrick Hanks. Word association norms, mutual information, and lexi-
cography. Computational linguistics, 16(1):22-22) 1990.
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.
Pantelis Elinas, Edwin V Bonilla, and Louis Tiao. Variational inference for graph convolutional networks in the absence of graph data and adversarial settings. In Advances Neural Information Processing Systems, volume 33, pp. 18648-18660. Curran Associates, Inc., 2020.
François Fouss, Kevin Francoisse, Luh Yen, Alain Pirotte, and Marco Saerens. experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classifi- cation. Neural networks, 31:53-72, 2012.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint 174001100 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances neural information processing systems, pp. 1024-1034, 2017.
Yoon Kim. Convolutional neural networks for sentence classification.
arXiv preprint
arXiv: /408.:440...0 2014.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- 2016.
works. arXiv preprint
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019a.
Johannes Klicpera. Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems, pp. 13354-13366 13366, 2019b.
Piotr Koniusz and Hongguang Zhang. Power normalizations in fine-grained image, few-shot image and graph classification. TPAMI, 2020.
James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher- order cheeger inequalities. Journal of the ACM (JACM), (1(6) 2014.
10

---

Published as a conference paper at ICLR 2021
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the Thirty-Secona AAAI Conference on Artificial In- relligence (AAAI-18), pp. 3538-35453 Association for the Advancement of Artificial Intelligence, 2018a.
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/CVF Conference on Computer Vision and Puttern Recognition (CVPR), June 2019.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. arXiv preprint arXiv: 1801.03226 2018b.
Naoki Masuda, Mason Porter, and Renaud Lambiotte. Random walks and diffusion on networks. Physics reports, 716:1-58, 2017.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Infolab, 1999.
S Pan, R Hu, G Long, J Jiang, Yao, and C Zhang. Adversarially regularized graph autoencoder for graph embedding. In IJCAI International Joint Conference on Artificial Intelligence, 2018.
Bo Pang and Lillian Lee. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. arXiv preprint cx/0506075, 2005.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre-
sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710, 2014.
Anand Rajaraman and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2011.
Alexander J. Smola and Risi Kondor. Kernels and regularization on graphs, 2003.
Ke Sun, Piotr Koniusz, and Zhen Wang. Fisher-bures adversary graph convolutional networks. UAI, 115:465 2019.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference world wide web, pp. 1067-1077, 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.
Petar Velickovic, William Fedus, William Hamilton, Pietro Lio, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR (Poster), 2019.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: orXiv:/902.077 9022007553 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 80.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462, 2018b.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7370-7377, 2019.
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. arXiv preprint
2019.

---

Published as a conference paper at ICLR 2021
Table 10:
The statistics of datasets used for node classification and clustering.
Dataset
# Nodes
# Edges
class
feature
Train/Dev/Tes Nodes
Cora
2. 708
5, 429
7
1433
140/500/1, 000
Citeseer
3, 327
4, 732
6
3703
120/500/1, 000
Pubmed
19, 717
44, 338
3
500
60/500/1, 000
Reddit
232, 965
11, 606, 919
602
152K/24K/55K
wiki
2405
17981
17
4973
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16(16):321-22 2004.
A SUPPLEMENTARY MATERIAL
A.1 NODE CLUSTERING
For SCGC and AGC, we set max iterations to 60. For other baselines, we follow the parameter settings in the original papers. In particular, for DeepWalk, the number of random walks is 10, the number latent dimensions for each node is 128, and the path length of each random walk is 80. For DNGR, the autoencoder is of three layers with 512 neurons and 256 neurons in the hidden layers respectively. For GAE and VGAE, we construct encoders with a 32-neuron hidden layer and 16-neuron embedding layer, and train the encoders for 200 iterations using the Adam optimizer with learning rate equal 0.01. For ARGE and ARVGE, we construct encoders with 32-neuron hidden layer and a 16-neuron embedding layer. The discriminators are built by hidden layers with 16 and 64 neurons respectively. On Cora, Citeseer and Wiki, we train the autoencoder-relate models of ARGE and ARVGE for 200 iterations with the Adam optimizer, with the encoder and discriminator learning rates both set as 0.001; on Pubmed, we train them for 2000 iterations with the encoder learning rate 0.001 and the discriminator learning rate 0.008.
A.2 TEXT CLASSIFICATION
The 20NG dataset1 (bydate version) contains 18,846 documents evenly categorized into 20 dif- ferent categories. In total, 11,314 documents are the training set and 7,532 documents are in the test set.
The Ohsumed corpus2 is from the MEDLINE database, which is a bibliographic database of important medical literature maintained by the National Library of Medicine. In this work, we used the 13,929 unique cardiovascular diseases abstracts in the first 20,000 abstracts of the year 1991. Each document in the set has one or more associated categories from the 23 disease categories. As we focus on single-label text classification, the documents belonging to multiple categories are excluded so that 7,400 documents belonging only one category remain. 3,357 documents are in the training set and 4,043 documents are in the test set.
RS2 and R8 (all-terms version) are two subsets of the Reuters 21578 dataset. R8 has 8 categories, and split to 5,485 training and 2,189 test documents. R52 has 52 categories, and was split to 6,532 training and 2,568 test documents.
MR is movie review dataset for binary sentiment classification, in which each review only con- lains one sentence (Pang & Lee 2005) The corpus has 5,331 positive and 5,331 negative reviews. We used the training/test split Tang et al. 2015).
A.2.1 TEXT CLASSIFICATION
Parameters. We follow the setting of Text GCN (aoo al. 2019) that includes experiments four widely used benchmark corpora such as 20-Newsgroups (20NG), Ohsumed, R52 and R8 of Reuters 21578. For Text GCN, SGC, and our approach, the embedding size of the first convolution
12

---

Published as a conference paper at ICLR 2021
Table 11: The statistics of datasets for text classification.
Dataset
# Docs
# Training
Test
# Words
# Nodes
# Classes
Average Length
20NG
18,846
11.314
7,532
42,757
61,603
20
221.26
R8
7,674
5,485
2,189
7,688
15,362
65.72
R52
9,100
6,532
2,568
8,892
17,992
52
69.82
Ohsumed
7,400
3,357
4,043
14,157
21,557
23
135.82
MR
10,662
7,108
3,554
18,764
29,426
2
20.39
layer is 200 and the window size is 20. We set the learning rate to 0.02, dropout rate to 0.5 and the decay rate to 0. The 10% of training set is randomly selected for validation. Following (Kipf) & Welling, 2016), we trained our method and Text GCN for a maximum of 200 epochs using the Adam (Kingma Ba 2014) optimizer, and we stop training if the validation loss does decrease for 10 consecutive epochs. The text graph was built according to steps detailed in the supplementary material.
To convert text classification into the node classification on graph, there are two relationships con- sidered when forming graphs: (i) the relation between documents and words and (ii) the connection between words. For the first type of relations, we build edges among word nodes and document nodes based on the word occurrence in documents. The weight of the edge between a document node and a word node is the Term Frequency-Invent 2011) (TF-IDF) of the word the document applied to build the Docs-words graph. For the second type of relations, we build edges in graph among word co-occurrences across the whole corpus. To utilize the global word co-occurrence information, we use a fixed-size sliding window on all doc- uments in the corpus to gather co-occurrence statistics. Point-wise Mutual Information (Church & Hanks 1990) (PMI), a popular measure for word associations, is used to calculate weights between word nodes according the following definition:
Document Frequency (Rajaraman & Ullman
PMI(i, log p(ú,j) p(i)p(j)
(14)
where p(i,j) W p()
W W #1 is the number of sliding windows in a corpus that contain word #W(i.) is the number of sliding windows that contain both word and word j. and #W is the total number of sliding windows in the corpus. A positive PMI value implies a high semantic correlation of words in a corpus, while negative PMI value indicates little semantic correlation in the corpus. Therefore, we only add edges between word pairs with positive PMI values:
W(..))
W W
W2
I
or
PMI(i,J)
if i are words, PMI(i.)) 0, i is document, word, if = j. otherwise.
TF-IDFy
Aij
(15)
A.3 GRAPH CLASSIFICATION
We report the average accuracy of 10-fold cross validation on a number of common benchmark datasets, shown in Table 12 where we randomly sample a training fold to serve as a validation set. We only make use of discrete node features. In case they are not given, we use one-hot encodings of node degrees as the feature input. We note that graph classification is task highly dependent on the global pooling strategy. There exist methods that apply sophisticated mechanisms for this step. However, with readout function and a highly scalable S2GC model, we comfortably outperform all methods on MUTAG, Proteins and IMDB- MMDB-Binary, even DiffPool which has a differentiable graph pooling module gather information across different scales. A stronger performer (Koniusz & Zhang 2020) uses the GIN-O backbone and second-order pooling with the co-called spectral power simple readout feature aggregation.
normalization, referred to MaxExp(F)). In contrast,
13

---

Published as a conference paper at ICLR 2021
Table 12:
Graph classification.
Method
MUTAG
PROTEINS
COLLAB
IMDB- BINARY
GCN
74.6 7.7
73.1 + 3.8
2.1
72.6
SAGE
74.9 8.7
73.8 + 3.6
1.7
3.6
GIN-0
85.7
5.1
2.7
72.8
GIN-E
7.5
7..6
7.11 7.8
DifiPool
85.0 10.3
75.1
2.3
7
GIN-O+)MXEXX(FF)
88.9 + 5.8
76.8 + 2.9
8.77
77.8 3.6
S-GC
85.1 + 7.4
7.1
8.3
72.9 + 4.9
A.4 THEORETICAL ANALYSIS
Below we show that we can reduce oversmoothing compared to SGC while incorporating larger receptive fields.
Our design contains sum of consecutive diffusion matrices T 0,... K. As k increases, does the neighborhood of each node visited during diffusion T (analogy to random walks). This means that:
Claim Our filter, by design, will give the highest weight to the closest neighborhood of a node as neighborhoods N of diffusion steps 0, K obey N(T)) C N(T)) S .... C.TK) S
(T That is, smaller neighborhoods belong to larger neighborhoods too.
To this clearer, for the g-dimensional Euclidean lattice graph with infinite number of nodes, after t steps of random walk, the estimate of absolute distance the walk moves from the source to its current position given as:
2F (( r(t,g) = VV T(q+1)'
(16)
where rtt, q) is the absolute distance walked from the source to the current point and I(-) is the Gamma function. Moreover, if the number of dimensions g oo, we have r(t, g) S vt. It is clear then that the receptive field associated with the random walk (and thus diffusion at time t) obeys the monotonically increasing radius r. that is r(0) < r((1 .... r(() S S r(oo). To see that, simply plot Vt (and/or the more complicated expression that includes the Gamma function).
This proves Claim for the Euclidean lattice graph. That is, for consecutive diffusion steps T k 0, ..... K, our receptive field grows.
that filter is realized the sum of consecutive diffusion steps, that is + diff(s, 7) where the source of walk. It is easy see then that even if each walked distance was to contribute the energy proportional with r(t) to the summation term, we have:
Moreover,
1 ve
lim 200
= 0,
(17)
where the enumerator is the model of the total energy when aggregating over receptive fields from size 0 to oo in S²GC while the denominator is the total energy of SGC (filter is given by T.K that by ts.
The above proof shows that the above ratio of energies O, which means that:
Claim II. When the ratio of energies of two models is O, the energy of the difinitedimmensionall
receptive field (when t - oo) in S²GC is not going to dominate the sum energy of our filter. Thus, SºGC can incorporate larger receptive fields than SGC without eclipsing the contributions from smaller receptive fields as f + co on the Euclidean lattice graph.
However, in practice, work with siite-dimensionall oon-Euclidean graphs. Obtaining the abso- lute distance rtt) walked from the source is a difficult topic. As an example, see Eq. 184 in Masuda al. (2017).
14

---

Published as a conference paper at ICLR 2021
For this reason, below walked radius. That is to say the error of convergence to the stationary distribution is indicative of the absolute distance walked from the source/node. Specifically, we have:
simple approximation. We use Theorem I the proxy for the
Recall Theorem 1 that is let d2 denote second largest eigenvalue of transition matrix T D- A. p()) be the probability distribution vector and π the stationary distribution. If walk starts from the vertex i, (0) 1. then after steps for every vertex:
(p,(1) - F,
d2 X/
(18)
Then, the average walked distance r from node over t steps in a graph with n nodes and connec- tivity given by the second largest eigenvalue X2, denoted by r(i, t, n) is lower-bounded by F(i, t, as follows:
1)-l) P E 13EE-dd \ X12
n-1
r(i,t, (i,,,n) n)
11,1 2 fli,tn)
(19)
> (t)
va
where n is the number of nodes, t is the number of diffusion steps (think Th d, and dj are degrees of nodes i and j. Xe being the second largest eigenvalue intuitively denotes the graph connectivity (large X2 S 1 indicates low connectivity while low A2 indicates high connectivity in graph). E is the sum of square roots of node degrees and p (m-1)vdd is in fact constant for given graph.
E-vd.
While the above approximations may be loose for very small/large t, the important property to note that r(i, n) r(i, 1, -.... r(i t) which indicates that our filter indeed realises the sum over increasingly larger receptive fields. As smaller receptive fields are a subset of larger receptive fields given node i, that is (T [ S ... < S ((T)), this proves our Claim I.
To prove Claim for general connected non-bipartite graph, we have:
Σ f(itt',
lim 1-000
0,
(20)
f(i,tn)
Similar findings can be noted by carefully considering the meaning of so-called Cheeger constant
introduced in Section A.5 More details on spectral analysis of filters in GCNs can be found in
studies of Li al. 20 Sah and Li al. (008h).
A.S GRAPH PARTITIONING
Below we introduce the definitions of expansion and k-way Cheeger constant.
Definition A.1. For a node subset S C V. so-called expansion (SS) S.. where E(S) is the set of edges with one node in S and vol(S) ) the sum of degree of nodes in set S.
Definition A.2. The k-wayy Cheeger constant is given as: (k) = min ,S. max(o(S;) :
i (1,
k}} where the minimum over all collections of is non-empty disjoint subsets S1. S2, ... S C.
According to the definitions, the expansion in Def. A. describes the effect of graph partitioning according to subset while the k-way Cheeger constant reflects the effect of the graph partitioning into À parts-the the smaller the value the better the partitioning is. Higher-order Cheeger's inequal- ity (Bandeira et al. 2013 Lee et al. 2014) bridges the gap between the network spectral analysis and graph partitioning by controlling the bounds of k-way Cheeger constant:
AB
S (k()) S (R(2) VTe
(21)
where X is the k-th eigenvalue of the normalized Laplacian matrix and 0= < <2 .... < An
From inequality 21, we can conclude that small (large) eigenvalues control global clustering (local smoothing) effect of the graph partitioned into few large parts (many small parts). Thus, specific combination of low- and high-pass filtering of our design (see Figure a indicates the weight trade- off between large and small partitions contained by the node.
15


Reviews:
[{"review_id": "vb6wqSBSIVN", "reviewer": "AnonReviewer4", "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": "This paper proposes a graph convolutional network, S2GC. The major difference between S2GC and previous graph convolutional networks is the proposed “new” graph convolution filter. This paper also systematically analyses previous methods and discusses their relations with S2GC.\n\nThis paper gives a comprehensive review and discussion about preliminaries works. The authors also conduct extensive experiments on node clustering, community prediction, node classification, and text classification. \n\nMy major concerns are:\n\n1)\tThe major difference between S2GC and previous methods, such as GCN and GDC (eq 4), is the graph filter. However, the proposed filter is not a new one. As in discussed in sec 3.3, it is the solver of normalized Laplacian regularization problem (eq. 14), which has been well studied in the past few decades. For example, the AR filter in [a] is the same as the one in S2GC. [a] also provided detailed spectral analysis as this paper does. The difference is that [a] only used this filter for node classification, while this paper also tests on node clustering, community prediction and text classification.\n\n2)\tWhile the authors conduct many experiments, the proposed filter does not bring significant performance improvement, which, however, is consistent with the observations in [a]. In most cases, the improvements are marginal, if any.\n\n[a] Label Efficient Semi-Supervised Learning via Graph Filtering, CVPR2019\n\n=================== Post Rebuttal ======================================\n\nI would like to thank the authors for the feedback.\nI realize that the diffusion kernel used in this paper is different from the AR filter in the CVPR 2019 paper, but I was misled to think they are the same because of a wrong claim made by the authors. In their paper, right below Eq. (11) (of the latest version), the authors state that the limiting case of the diffusion kernel is the solution of the classical Laplacian regularization problem, which is not true. The solution of this problem is exactly the AR filter with alpha = 1, and it is not equivalent to the limiting case of the diffusion kernel. \n\nAs such, I increased my rating of the paper, but I still think the contribution of the paper is limited due to the following reasons.\n\n1.\tThere is not much novelty in using the diffusion kernel as the graph filter. The diffusion kernel has similar response function as the AR filter. If you plot the response functions and observe the functions within [-1, 1] (range of the eigenvalues), you may see they nearly overlap. Yes, the diffusion kernel filter let more high frequency signals pass, but the amount is quite small, and it does not make much difference. The theoretical claims are not insightful either. Claim 1 is obvious, and the conclusion of Claim 2 applies to other polynomial filters such as AR (AR can be expanded into a polynomial form, the CVPR 2019 paper also proposed a fast computation method similar to what used in this paper). \n\n2.\tThe performance of the diffusion kernel is not significantly better than other graph filters. Notice that, it is not fair to directly compare with the results in the CVPR 2019 paper, because those results were obtained without using the validation set (which normally contains 500 labeled examples as in the original GCN paper). Also, the results in the present paper are obtained by running through a wide range of k and selecting the best. Given same conditions, it is quite likely other graph filters can achieve the same performance. Also, some recent methods such as GMNN and GCNII achieved better results than the present paper. \n\nI hope the authors don’t think they are treated by harsher standards. The novelty of the CVPR 2019 work is not mainly about proposing a new filter, it is about providing insights into/unifying popular semi-supervised learning frameworks such as label propagation and GCN. Especially for GCN, there was no similar analysis on GCN two years ago (an early version of the CVPR 2019 paper is online (https://openreview.net/forum?id=SygjB3AcYX) months before the SGC paper).\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "k-itLprxYck", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a relatively simple formulation for a graph convolution that considers nodes at multiple distances from the root node.\nThe novelty of the proposed approach should be better detailed, and experimental results should be improved.\n\nThe proposed formulation in eq. 13 is uncannily similar to the one proposed by Defferrard et al https://arxiv.org/pdf/1606.09375.pdf known as Chebynet, with a different choice of polynomials. Authors also acknowledge their proposal is a special case of GDC. \nAuthor then follow the same principle as PPNP to incorporate information about node labels at each layer. These points pose an issue about the novelty of the proposed approach, that should be better discussed. \n\nPros:\n-The proposed method is relatively simple and shows good performance\n-In the conclusions and in the introduction, authors claim that their proposed approach avoids oversmoothing. However, this is not proven in the paper. If authors refer to the introduction of the term \\alpha X in the convolution, this was proposed by PPNP already, so it is not a contribution of the present paper. Author should discuss this point more in the manuscript.\n\nCons:\nExperimental results can be improved. \n-Table 1 does not report variance. Moreover, the proposed methods' performance are very close to the ones of SGC. Table 2 does not report variance. \n-How were the hyper-parameters K, \\alpha and the learning rate set for the different datasets? At least a study reporting the influence on the predictive performance of different choices should be provided. Even better, the hyper-parameters should be selected using a validation set. For more details about the importance of the evaluation procedure, please see https://openreview.net/pdf?id=HygDF6NFPB\n\nMinor:\n-The tables are not reported in the order they are mentioned in the text.\n-Page 1 \"the features of on the Euclidean\" -> features on Euclidean grids\n-Page 3 : APNNA -> APNNP?\n-Table 6: missing bold for SGC on Ohsumed dataset. S^2GC variance of 0.0 on MR looks strange.\n\n\n-----AFTER REBUTTAL\nI have carefully checked the author rebuttal, and it addressed several of my concerns. I thus improve my score to this paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TgP6xOwk5RX", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "**Summar**\nThe paper proposes a spectral-based graph convolution layer, called Simple Spectral Graph Convolution (S$^2$GC), which is based on the Markov Diffusion Kernel (MDK). The authors show that S$^2$GC is capable of aggregating k-hop neighbourhood information without oversmoothing. The paper provides a spectral analysis on S$^2$GC and shows the connections to several previous methods, such as GDC, SGC and APPNP. The authors also show that their proposed S$^2$GC advantages from both spatial and spectral methods. They demonstrate that their S$^2$GC on a series of experiments, such as node clustering and node classification.\n\n**Reasons for score**\nOverall, I recommend ``marginally above the acceptance threshold''. It is plausible the idea of using Markov Diffusion Kernel (MDK) to derive a spectral graph convolution which can effectively aggregate k-hop information, and at the same time prevent from oversmoothing due to the design of MDK. The primary concern is about the clarity of the paper on the explanation of the required computational and storage costs of the proposed S$^2$GC model. It is suggested that the authors can address it in the rebuttal period. The following are the detailed comments.\n\n**Pros** \n1. The paper takes one of the most important issues of graph convolution: oversmoothing when aggregating multi-hop neighbourhoods / using deep graph neural networks. The problem itself is practical and makes much sense.\n2. The paper provides a rigorous and detailed spectral analysis for their proposed S$^2$GC method and shows the connection and difference between S$^2$GC and some previous related spectral graph convolutions. Overall, the paper is well-written.\n3. The experiments provided in this paper are extensive and quite comprehensive. Specifically, the authors demonstrate the effectiveness and superiority of their proposed S$^2$GC through four different tasks. The experimental results are also convincing.\n\n**Cons**\n1. The paper provides an experiment (community prediction) on a large-scale dataset. I will suggest the authors use some large-scale datasets also for the semi-supervised node classification task, such as Open Graph Benchmark (OGB) --- Node Property Prediction dataset, in addition to the over-used classic citation networks.\n2. It would be more interesting if the authors could provide a strategy on choosing the optimal Step Parameter $K$ in practice. Alternatively, the authors can provide an experiment on how the performance of S$^2$GC model is influenced by different values of the Step Parameter $K$.\n3. It would be even better if the authors can elaborate the computational and storage costs of their S$^2$GC method compared to the previously mentioned methods in the paper, such as GDC, SGC and APPNP.\n\nQuestions during the rebuttal period: Please address and clarify the Cons above.\n\n**Typos**\n1. In the paragraph of Section 2 Preliminaries: Is the paragraph title \"APPNA\" supposed to be \"APPNP\"?\n2. In Section 4 Experiments: I would suggest swapping the order of Table 1 and Table 2 since Table 2 is mentioned before Table 1 in the text.", "extra_scores": {}, "extra_text": {}}, {"review_id": "3anNDtQuPHe", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nOne of the most important component of GCN is coming with suitable graph filters and crucial towards designing better GCNs. In this regard, authors proposed Simple Spectral Graph Convolution with Markov diffusion kernel as a graph filter which combines strengths of both spatial and spectral methods. The paper is written-well and easy to follow.  Simplicity and empirically strong results are the main contributions of the paper. However, experiments on graph classification, comparison with other graph filters and theoretical justification can help make the stronger case.\n\n\nPros:\nPaper proposes Markov diffusion kernel as the new filter for GCN which can be seen as a variant (or combo) of Simple Graph Convolution and  APPNP. The main Equation 13 solves both the issues of propagating information to higher depth i.e., oversmoothing and preserving the node self information. Although, both these two tricks are somewhat known but showing their dominance in the empirical performance is promising and novel to certain extent.\n\n\nCons:\nTheoretical analysis is quite limited. Note that a similar Theorem exits in (Li et al., 2018)[1] to show over smoothing issue in GCNs. A comparison or a contrast with Theorem 1 would be beneficial. Also paper lacks insights about GCNs on how to design better graph filters and comparison with other graph filters (see [2]).  Moreover, authors are missing graph classification task which is quite common to show the efficacy of a new graph filter and can help to make stronger case. \n\n\nReproducibility:\nPaper lacks the implementation details and it would be great if authors can open-source their code for reproducibility purposes. I am suspicious about the standard deviation being zero in Table 4 on Cora and Pubmed datasets suggesting that the either algorithm is too stable or experiments lacks the needed randomness for statistically significant results. \n\n\n\n[1] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for\nsemi-supervised learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial In-\ntelligence (AAAI-18), pp. 3538–3545. Association for the Advancement of Artificial Intelligence,\n2018.\n\n[2] Adaptive Graph Convolutional Neural Networks Ruoyu Li, Sheng Wang, Feiyun Zhu, Junzhou Huang", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a Simple Spectral Graph Convolution (S2GC) variant of GCNs, using a modified Markov Diffusion kernel. The approach proposed aims to tackle GCN performance degradation with increased depth (oversmoothing), by combining techniques from earlier works (Simple Graph Convolution and APPNP). This is complemented by a spectral analysis of the properties of the scheme, as well by a comparison to state-of-the art on several datasets.
Decision: Accept (Poster)