SoGCN: Second-Order Graph Convolutional Networks
Authors: Peihao Wang
Yuehao Wang
Hua Lin
Jianbo Shi
Venue:  (2021)
Keywords: Graph Convolutional Networks
Filter Representation Power
Graph Polynomial Filters

Abstract: We introduce a second-order graph convolution (SoGC), a maximally localized kernel, that can express a polynomial spectral filter with arbitrary coefficients.  We contrast our SoGC with vanilla GCN, first-order (one-hop) aggregation, and higher-order (multi-hop) aggregation by analyzing graph convolutional layers via generalized filter space.  We argue that SoGC is a simple design capable of forming the basic building block of graph convolution, playing the same role as $3 \times 3$ kernels in CNNs.   We build purely topological Second-Order Graph Convolutional Networks (SoGCN) and demonstrate that SoGCN consistently achieves state-of-the-art performance on the latest benchmark. Moreover, we introduce the Gated Recurrent Unit (GRU) to spectral GCNs. This explorative attempt further improves our experimental results.

Under review as a conference paper at ICLR 2021
SoGCN: SECOND-ORDER GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce second-order graph convolution (SoGC), maximally localized kernel, that can express a polynomial spectral filter with arbitrary coefficients. We contrast SoGC with vanilla GCN, first-order (one-hop) aggregation, and higher-order (multi-hop) aggregation by analyzing graph convolutional layers via generalized filter space. We argue that SoGC is a simple design capable of form- ing the basic building block of graph convolution, playing the same role as 3 x 3 kernels in CNNs. We build purely topological Second-Order Graph Convolutional Networks (SoGCN) and demonstrate that SoGCN consistently achieves state-of- the-art performance on the latest benchmark. Moreover, we introduce the Gated Recurrent Unit (GRU) to spectral GCNs. This explorative attempt further im- proves our experimental results.
INTRODUCTION
Deep localized convolutional filters have achieved great success in the field of deep learning. In image recognition, the effectiveness of 3 x 3 kernels as the basic building block in Convolutional Neural Networks (CNNs) shown both experimentally and theoretically (Zhoul 2020). We are spired to search for the maximally localized Graph Convolution (GC) kernel with full expressiveness power for Graph Convolutional Networks (GCNs).
Most existing GCN methods utilize localized GCs based on one-hop aggregation scheme as the basic building block. Extensive works have shown performance limitations of such design due to over-smoothing (Li al.) 2018 Oono & Suzuki 2019 Cai & Wang 2020). In vanilla GCNs (Kipf & Welling 2017 7) the root cause of its deficiency is the lumping of the graph node self-connection with pairwise neighboring connections. Recent works of Xf et al.) (2019); Dehmamy et al.) (2019); Ming Chen et al. (2020) disentangle the effect of self-connection by adding an identity mapping (so-called first-order GC). However, its lack of expressive power in filter representation remains
(Abu-El-Haija et al.) 2019). The work of (Ming Chen et al. 2020) conjectured that the ability to
express polynomial filter with arbitrary coefficients essential for preventing
smoothing.
A longer propagation distance in the graph facilitates GCNs to retain its expressive power, as pointed out by (Liao al., 20199 Luan al. 2019 AAbu-El-Haija et al., 2019). The minimum propagation distance needed to construct our building block of GCN remains the open question. We show that the minimum propagation distance is two: two-hop graph kernel with the second-order polynomials in adjacency matrices is sufficient. We call our graph kernel Second-Order GC (SoGC).
We introduce a Layer Spanning Space (LSS) framework to quantify the expressive power multi- layer GCs for modeling polynomial filter with arbitrary coefficients. By relating low-pass filtering on the graph spectrum (Hoang& & Machara 2019) with over- verrssmothhing one can see the lack of filter representation power (Ming Chen et al.) 2020) can lead the performance limitation of GCN.
Using the LSS framework, we show that SoGCs can approximate any linear GCNs in channel-wise filtering. Furthermore, higher-order GCs do not contribute more expressiveness, and vanilla GCN or first-order GCs cannot represent all polynomial filters in general. this sense, SoGC is the maximally localized graph kernel with the full representation power.
To validate our theory, we build Second-Orden Graph Convolutional Networks (SoGCN) using SoGC kernels. Our SoGCN using simple graph topological features consistently achieves state-

---

Under review as a conference paper at ICLR 2021
A
AP
1+1
A
(a) Vanilla GC
(b) First-Order GC
(c) Our SoGC
Figure I: Vertex domain interpretations of vanilla GC, First-Order GC and SoGC. Denote / as the zero-hop aggregator, A the first-hop aggregator and A² the second-hop aggregator. Nodes in the same colored ring share the same weights. (a) I and A of vanilla GC share the same weights. (b) First-order GC disentangles / from A. (c) SoGC introduces weights for A in addition.
of-the-art performance on the GNN benchmark datasets (Dwivedi et al. 2020), including citation networks, super-pixel classification, and molecule regression.
To our best knowledge, this work the first study that identifies the importance of the two-hop neighborhood in the context of GCNs' ability to express polynomial filter with arbitrary coeffi- cients. Our model is a special but non-trivial case Defferrard et al. (2016). Kipf & Welling (2017) conducted an ablation study with GC kemelss of different orders but missed the effectiveness of the second-order relationships. The work of Abu-FilHaaja et al. (2019) talked about muti-hop graph kernels; however, they did not identify the critical importance of the second-order form. In contrast, we clarify the prominence of SoGCs in theories and experiments.
Our research on graph convolution using pure topologically relationship is orthogonal to those uses geometric relations (Monti et al. [2017] Fey et al. 2018 Pei et al. (2020), or those with expressive edge features (Li et al. [016;] Gilmer al. 2017 Corso al. 2020). and hyper-edges (Morris al. Maron et al. [2188 2019). is also independent with graph sampling procedures (Rong et al.
2019
2019
Hamilton al.
al. 2019
PRELIMINARIES
We hegin by reformulating spectral GCNs and introducing notation. We interested in finite graph set G = GG Assume each graph G E G is simple and undirected, associated with a finite vertex set V(G,, an edge set { [u, u) : Vu ++ v). and a symmetric normalized adjacency matrix A(G) (Chung & Graham 1997 Shi & Malik 2000). Without loss of generality
and for simplicity, [VG N for every G G. Single-channel features æ E R supported in
graph G E G is vectorization of function (GG)
R.
Graph Convolutions (GCs) is known as Linear Shift-Invariant (LSI) operators to adjacency matrices Sandryhaila & Moura 2013). By this definition, GCs can extract features regardless of where local structures fall. Given parameter space Z C R, we write single-channel GC (Sandryhaila & Moura 2013 Defferrard et 2016) mapping G IR N R such that
fo(G, = Σ OAA(G)
k=0
where 00 0x]² Q*+1 parameterizes the GC. K reflects the localization of fo:
a linear combination features aggregated by A( Moreover, we reformulate two popular models, vanilla GC (Figure Ta) and first-order GC (Figure lb). as below:
x)) (A(G) + I) [G x) (0, f)T)..
(2)
The general spectral GCNs stack L layers of GCs (Equation 1 with nonlinear activations. Let f() be GC layers with parameters (1)) +1 [L.. the single-channel GCNs can be written as:
F(G,.) go ((4) aa ( f
( (G,
o o..
We can replace the Laplacian matrix L in Defferrard et al. 2016) with the normalized adjacency matrix A since L A.
2

---

Under review as a conference paper at ICLR 2021
(a) Vanilla GCN
(b) SoGCN wo GRU
(c) Vanilla GCN + GRU
(d) SoGCN + GRU
22
12
Magnitude
20 Frequency
20
10 Frequency
10 Frequency
Frequency
Figure 2: Visualizing output activation in graph spectrum domain for vanilla GCN, SoGCN, and GRU variants. The test is conducted on a graph from the ZINC dataset. The spectrum is defined projection of activation functions the graph eigenvectors. SoGCN preserved higher-order spectrum, while vanilla GCN shows over-smoothing. See Appendix F for more visualizations on the ZINC dataset.
where is element- wise activation function, the superscripts denote the corresponding layer number, 9 is a task-specified readout function (e.g.. softmax), the inputs are graph G E 9 and signals R.V. The compositionality principle of deep learning suggests L being large, while K being small and localized (LeCun et al. 2015).
3 OVERVIEW: SECOND-ORDER GRAPH CONVOLUTION
We are interested in the overall graph convolution network's representation power of expressing polynomial filter (Equation D with arbitrary coefficients. A multi-layer GCN approximate K- order polynomial filter E
K k Og (G) 0g E Q k 0, 0.... K, by stacking basic building blocks of graph convolution (GC) layers (Wu et al. 2019 Ming Chen al. 2020).
We formally define the second-order GC (SoGC) using the second-order polynomials adjacency matrices:
Ja(G, x) = (02A(G)² + 0, A(G) + 0o1) x,
(4)
where 0, E RRi 0, 2, are trainable paremeters in the context of machine learning. Its vertex- domain interpretation illustrated in Figure Tc first glance, seems that we could stack two one-hop graph convolution (GC) kernels to approximate SoGC. However, shown in Section 4.3 that is not the case.
The critical insight is that graph filter approximation can be viewed polynomial factorization problem. known that any univariate polynomial can be factorized into sub-polynomials of degree two. Based this fact, show by stacking enough SoGCs (and varying their parameters) can achieve decomposition of any polynomial filters.
In contrast, first-order GCs not universal approximators; two stacked one-hop GCs cannot model every two-hop GC. Polynomial filter completeness SoGC leads to better performance of GCNs. As shown in Figure [ networks built with SoGC can overcome over-smoothing and extract features on high-frequency bands. In the next section, we demonstrate our formal arguments on polynomial approximation.
REPRESENTATION POWER ANALYSIS
4.1 LAYER SPANNING SPACE FRAMEWORK
To illustrate the representation power of GC layers, establish Layer Spanning Space (LSS) framework to study the graph filter space spanned by stacking multiple graph kernels.
First, we present mathematical devices in Definition with Lemma 1 as below.
3

---

Under review as a conference paper at ICLR 2021
Definition 1. Suppose the parameter space S R. The Linear Shift-Inaaiint (LSI) graph
filter space of degree K > with respect to a funite graph set G is defined as A {fo : IN - e E where fo follows the definition in Equation [
Definition 2. Let spectrum sei S(g) - {A: AA: E S(A(G)), YG E } where S(A) denotes the eigenvalues of A. Define spectrum capacity I [(()]] particular, = (N 1) if every graph adjacency matrix has no common eigenvalues other than 1.
Lemma 1. A of degree K 0 has dimension min(K 1,T) vector space.
Proof of Lemma I from Theorem 3 of Sanddrhaila Moura (013). The complete version can be found in Appendix [
Here, we induce a finite-dimension filter space by Lemma
For simplicity, we will model the linear composition of filters to analyze its representation power. The nonlinear activation effects are beyond the scope of this work. Following Definition | let A be the full filter space of degree r 1 and B be the low-level filter space as a set of polynomials in adjaceney matrices (Equation stacking L layers as below:
1. Denote the GC at 1-th layer by f(l) E B, then we yield the LSS of
Be { F: f( f(4) (G
4 II (A(G)) 1=1
(5)
where (xx) varies in certain class of polynomials. We assess the expressive capability of GC layers by comparing the LSS with A. Kernels in B have full representation power if A C B². We are interested in Bx, which denotes all localized filters of degree at most K. The LSS of Bg modeled as:
{ f: f(f
L -I
BK
( k A(G))*
a, x, 0 E
(6)
1=1 k=
where the number of layers bounded by S [(T 1)/K], according to Lemma
4.2 UNIVERSAL REPRESENTATION POWER OF SoGC
In this section, present Theorem D to demonstrate the universal representation power of SoGCs as claimed in Section 3 Formally, we add superscripts to Equation 4 to indicate the layer number. Then we leverage fundamental polynomial factorization theorem conclude Theorem ass below.
Theorem 1. For any f E A, there exists ( E BB2 with coefficients 0% of ol E ER,-=1 L such that f = f2 ....o f22 where L S - [1)2]
The complete proof is presented Appendix D Theorem D can be regarded as the universal approxi- mation theorem of linear GCNs, which implies multi-layer SoGCs have full filter expressiveness.
Theorem T also demonstrates how GCNs with SoGCs benefit from depth, which coincides with the view of Dehmamy et al. (2019). Figure 3a verifies our SoGCN can overcome over-smoothing and successfully utilize depth to attain performance gain.
4.3 REPRESENTATION POWER OF OTHER GRAPH CONVOLUTION
In this section, we show that vanilla and first-order GCs lack expressiveness, while higher-order GCs reduce compactness and increase fitting difficulty.
Vanilla vs. second-order. Extensive works have shown the performance deficiency of vanilla GCNs (Hoang & Macharal 2019: Luan al. 2019 Oono & Suzuki 2019 Cai & Wang 2020 Based on the LSS framework, we can point out a similar issue but from novel perspective. Let us
write f(") x) g()) (A(G) + D)x Bo the I-th GC layer Then L of them can represent
LSS as follows:
ByC- = { f f:f(G. f() = -
AH 1=
Notice that we use Bo to denote the filter space with lumping of self-connection with pairwise neighhor nodes, since the zero-degree are too trivial. We assume the renormalization trick he merged into 0.
4

---

Under review as a conference paper at ICLR 2021
by letting f ((L) ..l.)...ol ...g(), No matter how large L is or how optimizer tunes the parameters g(), dim B = which signifies Big degenerates to a negligible subspace of A.
First-order vs. second-order: We denote first-order GCs as [ = - By. In the spirit of Section 4.1 write the LSS as:
A(G) +00) =))
Dar
B f f(G.))
II A(G) 66" x. 00. 6000 E ER
which is isomorphic to a polynomial space whose elements split over the real domain. Compared with B/ (Equation] 7). Bf represents a much larger subset of A. This highlights the importance of
the first-order term the identity mapping mentioned in (Xu et al. 2019 Dehmamy et al. 2019 Ming Chen et al., (020).
The limitations also become obvious since not all polynomials polynomials. These polynomials only occupy a small proportion in the ambient polynomial space Li 2011), which indicates first-order GCs are not universal approximators in general.
be factorized into first-order
Higher-order vs. second-order. GCs of degree K 2 2 are called higher-order GCs. They model multi-hop GCNs such Luan et al. (2019); Liao et al. (2019); |Abu-El-Haija et al.) (2019). Higher-order GCs have equivalent expressive power to SoGCs, since they can be reduced to SoGCs long coefficient sparsity can be achieved. But this by-product-an uncertain sparsity of coefficients-is not compatible with pradient-based optimization algorithms. Extensive experiments (Defferrard et al. 2016) have shown the ineffectiveness of learning higher-order kernels, because cigenvalues of graph adjacency matrices diminish when powered. This results in decreasing nu- merical rank of AG))* k. which prevent higher-order GCs from aggregating larger-scale information. SoGCs can alleviate this problem by preventing the loss of information due to higher-order powering operation. Finally, higher-order GC lacks nonlinearity. SoGCN can bring a better balance between the expressive power of low-level layers and nonlinearity among them.
5 SECOND-ORDER GRAPH CONVOLUTIONAL NETWORKS
In this section, we introduce other building blocks of GCNs and establish our Second-Order Graph Convolutional Networks (SoGCN) following the fashion of deep learning. First, promote SoGC to the multi-channel version analogous to Kipf & Welling (2017). Then we cascade a feature embed- ding layer, multiple SoGC layers, and append readout module. Suppose the multi-channel input is X E NXD supported in graph G' G. denote the output of /-th layer (1) V the final node-level output as Y E RXx XF, or graph-level output as Y R we formulate our novel deep
GCN based on SoGC as follows:
(0) = p (X; Ø).
(9)
x (141) = a
X xx
(10)
= ==T(x((1;; (x(1);
(11)
are trainable weights for linear filters; p RN NxE an equivariant embedder (Maron et al. 2018 with parameters क; NxE - NxE is an activation function. For neve- readout, T NxE + N can be decoder (with parameters V) or a nonlinear activation (e.g., softmax) in place of the prior laver. For graph-level output, N + R should be an invariant readout function (Maron et al. 2018), e.g., channel- wise sum, mean or max (Hamilton et al., 2017). In practice, we adopt ReLU as nonlinear activation (i.c., ReLU),, a multi- layer perceptron (MLP) as the embedding function p. another MLP for node regression readout, and sum (Xu et al.
where ( E
2019 for graph classification readout.
5.1 GATED RECURRENT UNIT
Gated Recurrent Unit (GRU) has been served basic building block in pressage-passing GNN architectures (Li et al. 2016 Gilmer et al. 2017 Corso et al. 2020). In this subsection, we explore its application in spectral GCNs.
5

---

Under review as a conference paper at ICLR 2021
According to Cho et al. 22144) GRU can utilize gate mechanism to preserve and forget information. We hypothesize that a GRU can be trained to remove redundant signals and retain lost features on the spectrum. This function can be used to alleviate the oversmoothing problem of vanilla GCNs by maintaining information from previous layer and canceling the dominance of low-frequencies. By the same means, GRU can also relieve the side-effect of ReLU, which is proved to be a special low-pass filter (Oono & Suzuki 2019; Cai & Wang 2020). Even though piled-up SoGCs attain full expressiveness, we show by our experiment that GRU can still facilitate SoGCN in avoiding noises and enhancing features on the spectrum (Figure 2
Similar to Li al. (2016); Gilmer et al. (217)) we appends a shared GRU module after each GC layer, which takes the signal before the GC layer as the hidden state, after the GC layer as the current input. We note that GRU can cooperate with any spectral GCs (Equation []] When integrated with
SoGCN, we call this special variant SoGCN-GRU We formulate its implementation by replacing Equation T0 with Equation| 12]as as below.
X (1+1) = A X ( (1+1) + +A(G)X
O (+1) + +X *
come
(12)
( = GRU ReLU
x .)
where Xcons is the input, x²)) represents the hidden state, Z denotes parameters of the GRU.
Figure and Figure 6 verify our conjecture. We observe more steady low-frequency component on the spectrum head and more characteristic bands on the high-freuug feeh-freueecy tail. Our empirical study in Table 3 also indicates the effectiveness of GRU for spectral GCNs in general. Hence, we suggest including this recurrent module as another basic building block of our SoGCNs.
5.2 COMPARISON TO RELATED WORK
Spectral GCNs. Spectral GCN leverages polynomials in the adjacency matrix to represent graph convolutional layers (Bruna et al. 2014). Many works have been discussing how to design the polynomial and choose its degree to compose localized GC layer. ChebyNet (Defferrard et al., approximates graph filters using Chebyshev polynomials. Vanilla GCN (Kipf & Welling 2017 Wu et al., (219) further reduces the GC layer to degree-one polynomial with first-order and constant terms merged. However, these simplifications cause over-smoothing and performance loss. Our SoGC incorporates only one hop longer but obtains the full representation power. This design keeps each layer localized, simple, and easy to implement but makes the whole GCN much more powerful. Our work reveals the critical degree of polynomial filters where kernel size is minimized while filter representation power is maximized.
2016
Multi-Hop GCNs. To exploit multi-scale information, Luan et al. (2119) devises Snowball GCN and Truncated Krylov GCN to capture neighborhoods different distances. To simulate hop delta functions, Abu-EElHaaja et al. (2019) repeat mixing multi-hop features to identify more topological information. These models exhibit the strength of multi-hop GCNs over one-hop GCNs while leav- ing the propagation length as hyper-parameter. Modeling those multi-hop GCNs as our higher- order models, SoGCN possesses the identical representation power but has fixed size and better localization, making SoGC more suitable to be the basic building block in GCNs. It is noteworthy that, although Abu-EEl-aijaa et al. (2019) investigates the two-hop delta function (a Gabor- filter), their final proposed solution is only generic class of multi-hop GCNs. The discussion on two-hop delta functions cannot attain our theoretical results.
Expressiveness of GCNs. Most of the works on GCN's expressiveness are restricted to the over- smoothing problem: Li et al. (2018) first poses the over-smoothing problem; Hoang & Machara (2019) indicates GCNs are no more than low-pass filters: Luan et (2019) Oono & Suzuki (2019) demonstrate the asymptotic behavior of feature activation to subspace; Cai & Wang (2020) ex- amines the decreasing Dirichlet energy. Unlike them, our established LSS framework can identify specific issues of GCNs with algebraic and geometric interpretations. The over-smoothing prob- lem can be formulated as one of our sub-problems (Section 4.3). In this sense, SoGCN solves more general expressiveness issue than those relieving smoothing problem only (Xu et al.) 2018 [Rong et al.] 2019: Chen et al. 2020). [Mig Chen et al. (2020) introduces identity and initial mapping to recover filter expressiveness. Their analytic framework is also similar to ours. But

---

Under review as a conference paper at ICLR 2021
generalize their filter space to graph set, and upper bound its dimension. In the meanwhile, SoGCN's architecture is more lightweight. We investigate the overall expressive power of GCNs by discussing filter completeness. This direction is orthogonal to those studying passage-passing GNNs (Scarselli et al. 2008) and Weisfeiler-LLeann GNNs (Xu et al., 2019; Morris et al. 2019).
6 EXPERIMENTS
Experiments are conducted the synthetic dataset in Section 6.1 and on the GNN bench- marks (Dwivedi et al. (020) in Section 6.2
6.1 SYNTHETIC GRAPH SPECTRUM DATASET FOR NODE REGRESSION
To validate the expressiveness of SoGCN, and its power to preserve higher-order graph signal, we build a Synthetic Graph Spectrum (SGS) dataset for the node signal filtering regression task. We construct SGS dataset with random graphs. The learning task is mimic three types of hand-crafted filtering functions: high-pass, low-pass, and band-pass on the graph spectral space (defined over the graph eigenvectors). There 1k training graphs, 1K validation graphs, and 2k testing graphs for each filtering function. Each graph is undirected and comprises 80 120 nodes. Appendix [ covers more details of our SGS dataset. We choose Mean Absolute Error (MAE) the evaluation metric.
Experimental Setup. We compare SoGCN with vanilla GCN (Kipf & Welling 2017). first-order GCN, and higher-order GCNs on the synthetic dataset.
To evaluate each model's expressiveness purely on the graph kernel design, we remove ReLU acti- vations for all tested models. We adopt the Adam optimizer (Kingma & Ba (015) in our training process, with batch size of 128. The learning rate begins with 0.01 and decays by half once the validation loss stagnates for more than 10 training epochs.
The performance of graph node signal regression with High-Pass, Low-Pass, and Band- Pass filters (over graph spectral space) as learning target. Each model has 16 GC layers and 16 channels of hidden layers.
Table I:
Test MAE + s.d.
Model
#Param
High-Pass
Low-Pass
Band-Pass
Vanilla GCN
4611
0.308+00006
0.317=0.011
0.559+00.071
Vanilla GCN + ReLU
4611
0.466110.02
0.457=0.002
0.29910.000
Ist-Order GCN
8467
0.036:+0.004
0.032:#0.022
0.115++0.008
3rd-Order GCN
16179
0.021
0.022=0.001
0.04510.008
4th-Order GCN
20035
0.021
0.022:#0.02
0.049+000006
SoGCN
12323
0.021
0.023+0.002
0.050+10.004
Results and Discussion. Table summarizes the quantitative comparisons. SoGCN achieves the superior performance on all of the 3 tasks outperforming vanilla GCN and 1st-order GCN, which implies that SoGC graph convolutional kernel does benefit from explicit disentangling of the O, (zero-hop) and 0g A (second-hop) terms. Our results also show that higher-order (third-order and fourth-order) GCNs do not improve the performance further, even though they have many more parameters. SoGCN possesses a more expressive representation ability and a good trade-off trade-offbetween between performance and model size.
Figure 3 plots MAE results as we vary the depth and channel width of GC layers. Vanilla GCN can benefit from neither depth nor width. First-order GC. SoGC, and higher-order GC can leverage depth to span larger LSS. Figure Balillustrates the corresponding performance for each graph kernel types. SoGC and higher-order GC both outperform first-order GC as depth increases. Figure 3h shows the
This experimental group shows that ReL.U are always such beneficial synthetic dataset.

---

Under review as a conference paper at ICLR 2021
0.7
0.6
0.5
1e3t MAE
0.4
Test MAE
0.4
1st: order GCN
0.3
1st
3rd-arder
SoGCN
SoGCN
Vanilla GCN
0.1
0.1
0.0
0.0
100
Depth
(a) Relations between test MAE and depth.
(b) Relations between test MAE and width.
Figure 3: Relations between test MAE and depth width. Experiments of both (a) and (b) are conducted on synthetic Band-Pas dataset. Each model in (a) has 16 channels per hidden layer with varying depth. Each model in (b) consists 16 GC layers with varying width.
benefits of SoGC remain we find that depth has larger effect on GCNs.
to multi-channel construction. Comparing Figure 3a and 3b
6.2 GNN BENCHMARKS
We follow the benchmarks outlined Dwivedi et al. (2020) for evaluating GNNs on several datasets across variety of artificial and real-world tasks. We choose evaluate our SoGCN chemistry dataset (ZINC molecules) for the graph regression task, two semi-artificial computer vi- sion datasets (CIFARIO 10 and MNIST superpixels) for the graph classification task, and artificial social network datasets (CLUSTER and PATTERN) for the node classification task.
Table 2: Results and comparison with other GNN models on ZINC, CIFARIO, MNIST, CLUSTER and PATTERN datasets. For ZINC dataset, the parameter budget is set 500k. For CIFARIO, MNIST, CLUSTER and PATTERN datasets, the parameter budget is set to 100k. Red: the best model, Green: good models.
Test MAE + s.d.
Test ACC + s.d. (%)
Model
ZINC
MNIST
CIFARIO
CLUSTER
PATTERN
Vanilla GCN
0.367=0.011
90.705
55.710=0.381
53.445::2.029
03.800000077
Vanilla GCN-GRU
0.295
96.020+10.000
61.332-10849
57.932-10.668
70. 10410.61
GAT
0.384=0.007
95.535++0.205
64.223=00455
57.732+-03223
75.824+1.822
MoNet
0.292 0.006
90.805-10.032
65.911
58.064:10.131
85.482-100037
GraphSage
0.398
97.312.10.097
65.767110.30
50.45411..14
50.516110.001
GIN
0.387
96.485
55.255=1.527
58.38410.233
85.590:10.011
GatedGCN
0.350 0.020
97.340::0.143
67.312=00311
60.4041:0419
84.480+:01222
3WLGNN
0.
90.075
59.175111.99
57.130:16.539
85.661-10.353
SoGCN
0.238
96.785-4-0113
66.338-10.155
68.167:111161
85.735+t0.037
SoGCN-GRU
0.201=0.006
97.129:40.159
68.208=0.271
67.994#22.119
85.711+:00047
Experimental Setup. We compare our proposed SoGCN and SoGCN-GRU with state-of-the- art GNNs: vanilla GCN (Kipf & Welling 2017). GAT (Veličković et al., 2018), MoNet (Monti et al.
2017). GIN (Xu et al. 2019). GraphSage (Hamilton et al. (017)) GatedGCN (Bresson & Laurent 2017 and 3WL-GNN MMron et al. 2019). To ensure fair comparisons,
follow the same training and evaluation pipelines (including optimizer settings) and data splits of benchmarks. Furthermore,
This is the result of 3WLGGNN with 100k parameters. The test MAE of 3WLGNN with 500k parameters increased to 0.427++0.011.
8

---

Under review as a conference paper at ICLR 2021
Table 3: Results of ablation study on ZINC, MNIST and CIFARIO datasets. Vanilla GCN is the comparison baseline and the number in the (t and (4 represents the performance gain compared with the baseline.
Test MAE = s.d.
Test ACC + s.d. (%)
Model
ZINC
MNIST
CIFARIO
Vanilla GCN
0.367 0.011 (Baseline)
90.705 0.218 (Baseline)
55.710 0.381 (Baseline)
Ist-Order GCN
0.253 1 0.012 (L 0.113)
96.407 1 0.089 (t 5.701)
64.993 1 0.092 (f 9.283)
SoGCN
0,238 # 0.017 (1 0.129)
96.783 = 0.113 (f 6.080)
66.338 0.155 ( 10.628)
3rd-Order GCN
0.242 0.005 (4 0.125)
96.367 0.227 (f 5.662)
64.267 0.182 (1 8.557)
4th-Order GCN
0.243 = 0.009 (L 0.124)
96.167 = 0.198 (f 5.462)
64.230 = 0.212 (f 8,520)
Vanilla GCN GRU
0.295 = 0.005 (4 0.072)
96.020 + 0.090 (f 5.315)
61.332 0.381 (1 5.622)
Ist-Order GCN + GRU
0.226 + 0.015 (4 0.141)
96.945 1 0.093 (t 6.240)
62.372 = 0.522 (t 6.662)
SoGCN + GRU
0,201 = 0.006 (J 0.166)
97.729 = 0.159 (t 7.024)
68,208 0.271 (f 12.498)
3rd-Order GCN GRU
0.203 0.001 (L 0.164)
97.375 0.052 (t 6.670)
64.242 0.511 (t 8.532)
4th-Order GCN + GRU
0.204 = 0.004 (4 0.163)
97.304 = 0.296 (1 6.399)
64.697 = 0.341 (1 8.987)
adjust our model's depth and width to ensure it satisfies parameter budgets as specified in the benchmark. Note that we do not use any geometrical information to encode rich graph edge rela- tionship, as in models such GatedGCN-E-PE We only employ graph connectivity information for all tested models.
Results and Discussion. Table reports the benchmark results. Our model SoGCN makes small computational changes to GCN by adopting second-hop and zero-hop neighborhoods, and it out- performs models with complex tops almost all state-of-ther cite--fffthhrrrrre art GNNs on the ZINC. MNIST and CIFAR10 datasets. Whereas, GRU does not lift performance on the CLUSTER and PATTERN datasets for node classification task. As suggested by Li et al. (2018), graph node classification benefits from low-frequency features. That GRU suppresses low-frequency band will result in a slight performance drop on the CLUSTER and PATTERN datasets.
bessage-passing mechanisms. With GRU module, SoGCN GRU
Ablation Study on High-Order GCNs. To contrast the performance gain produced by different orders on the benchmarks, we evaluate Ist-Order GCN, 3rd-Order GCN, 4th-Order GCN as well as their GRU variants on the ZINC, MNIST and CIFAR10 datasets. Table presents the results of our ablation study, which are consistent to our experiments on the synthetic datasets (Section 6.1). As shown by our ablation study, aggregating zero-hop features brings about significant improvements (Vanilla GCN vs. Ist-Order GCN), and adopting the second-hop hop features further promotes the per- formance (1st-Order GCN vs. SoGCN). However, high-order GCNs are not capable of boosting the performance over SoGCN, On the contrary, high-order GCs can even lead to the performance decline (3rd-Order GCN vs. 4th-Order GCN vs. SoGCN). On the ZINC and MNIST datasets, we testify GRU's effectiveness for each tested model, but the gain brought by GRU is not as significant as aggregating the second-hop -hop features. On the CIFAR10 10 dataset, GRU fails to improve performance for 1st-Order GCN and 3rd-Order GCN.
7 CONCLUSION
What should be the basic building blocks for GCNs? To answer this, we seek the most localized graph convolution kernel (GC) with full expressiveness. We generalize the filter space to a finite graph set and establish our LSS framework to assess GC layers functioning on different hops. We show the second-order localized graph convolutional filter, called SoGC, possesses the full repre- sentation power than one-hop GCs. Thus, it becomes the most localized GC that we adopt as the basic building block establish our SoGCN. Both synthetic and benchmark experiments exhibit the prominence of our theoretic design. We also make an empirical study on the GRU module cooperating with spectral GCNs. Interesting directions for future work include analyzing two-hop aggregation schemes with message-passing GNNs and proving the universality of nonlinear GCNs.

---

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 architectures via sparsified neighborhood mixing. In ICML, 2019.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv:1711.07533 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. 2014.
Chen Cai and Yusu Wang. note on over-smoothing for graph neural networks. ICML, 2020.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In AAAI, 2020.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv: 1078, 2014.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. American Mathematical Soc., 1997.
Gabriele Corso, Luea Cavalleri, Dominique Beaini, Pietro Lio, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. In ICML, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS, 2016.
Nima Dehmamy, Alsert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. In NeurlPS, 2019.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv:2003.00982, 2020.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geometric deep learning with continuous b-spline kernels. In CVPR, 2018.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, 2017.
NT Hoang and Takanori Machara. Revisiting graph neural networks: All we have is low-pass pass filters. arXiv:1905.09550 2019.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 2015. 2015.
Guohao Li, Matthiss Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? ICCV, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
Wembo Li. Probability of all real zeros for random polynomial with the exponential ensemble. Preprint, 2011.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In ICLR, 2016.
10

---

Under review as a conference paper at ICLR 2021
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR, 2019.
Sitao Luan, Mingde Zhao, Xiao~Wen Chang, and Doina Precup. Break the ceiling; Stronger multi- scale deep graph convolutional networks. In NeurIPS, 2019.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In ICLR, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS, 2019.
Zhewei Wei Ming Chen, Bolin Ding Zengfeng Huang, and Yaliang Li. Simple and deep graph convolutional networks. In ICMI,, 2020.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2019.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. IEKE, 2018.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen. Geometric graph convolutional networks. In ICLR, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In ICLR, 2019.
Aliaksei Sandryhaila and José MF Moura. Discrete signal processing on graphs. IEEE Trans. Signal Process, 2013.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. TNN, 2008
Jianbo Shi and J. Malik. Normalized cuts and image segmentation. TPAMI, 2000.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. networks? ICLR, 2019.
How powerful are graph neural
Ding-Xuar Xuan Zhou Universality of deep convolutional neural networks. ACHA, 2020.
11

---

Under review as a conference paper at ICLR 2021
A
REMARK ON DEFINITION
Let us rewrite the A of degree K in Definition
== f: f(G
Σ 0% Ax) VO, R
(13)
which contains all LSI functions f: 9 RR + R with adjacency matrix as the graph shift. We show this in the following way. First, all linear transformations H invariant to the shift should
have HS SH. Second, specifying arbitrary graph G' G. any filter associated with it can be written as below:
K H(G) Σ ORA(G)* U
(E U
(14)
k==
where A(G) UAUT is the eigendecomposition of A(G). Then conclude the shift- invariance property by the following Lemma
Lemma 2. Diagonalizable matrices A1 and A2 are simultaneously diagonalized if and only if A₁ = A2A1.
B RING ISOMORPHISM: A T
We derive an equivalent form A, namely construct a tractable space for A. Notice that, this construction is essential to the proof of Lemma Theorem
Since G is finite, we can construct a block diagonal matrix T N consisting of all adjacency matrices on the diagonal.
A(G1)
E NISIIIII
(15)
A
Hereby, we stop to explain the big picture Definition with Equation 15 Obviously, the spectrum capacity I' represents the number of eigenvalues of T without multiplicity. Note that, eigenvalues of adjacency matrices sigmify graph similarity. The spectrum capacity I' identifies a set graphs by enumerating the structural patterns. Even if the graph set goes extremely large (to guarantee the generalization capability), the distribution of spectrum provide the upper bound of I, so our theories will not lose generality.
Now we get back to construct a matrix space T from A via a ring homomorphism क - T:
OGA(G)) Σ O
(16)
k=
Recall that ring homomorphism preserves the "summation" and "multiplication". Concretely, write the matrix space T as follows:
H:
H
Σ
0.
vo
R
(17)
K=U
In the following part, we prove that æ an isomorphism.
Proof. First, the definition of T (Equation 17 basically conclude the surjectivity. Second, for any fi * f2 E with parameter ogg Sy where O.... K, there exists G, E G. E RN such that (i x) + x)). And we have their images H T(fi), H2 (f2).. By padding with zeros like:
x'' = 0% O
of
0 (i
(18)
12

---

Under review as a conference paper at ICLR 2021
where O2 denote the all-zero vector of length N. We apply H1, H2 x':
Hi
| (o (E#=o ax AG)
1"
T
(o fi(G,,
0 (((]--))
T
(19)
H2æ' = (o/6-11) (Ei=o (
o ((99)1))
= -[0% (N-))) [2(G
N[ - 1)
T
(20)
Hence, H1 + H2 concludes the injectivity.
C PROOF OF LEMMA I
We first show A is a vector space, then we leverage the isomorphism to have equality dim A = dim T. Figuring out the dimension of T is much more tractable.
Proof. By verifying the linear combination is closed or simply implied from the ring isomorphism n, A least a vector space
Then Lemma follows from the Theorem 3 Sandryhaaaa & Moura (2013) We briefly conclude the proof in the following way. Let m((x) denote the minimal polynomial of T. We have = deg m(x)). Due to the isomorphism, dim A = dim T.
} is spanning set. If dim < + I, then there exists some polynomial p(x) with deg p(x) I K, such that ((A) = 0. This contradicts the minimality of m(z). dim T can only be K +1.
Suppose K + < r. First, dim cannot be larger than K + 1, because {I,T,... .... TK}
Suppose K + 2 r. For any H h(T) for some polynomial h(x) with deg h(x)(()) S K. By polynomial division, there exists unique polynomials ((r) and r(z) such that
h(z) (z))m(x) + r(x),
(21)
where deg r(x) dog m(x) T. Insert T into Equation 21
h(T) = (mT (T) + r()) = (T) + r(T)= rTT).
(22)
Therefore, {I,T,
T r11) form a basis T, i.e., dim T
Remark that, assume each graph contains the same number of vertices only for the sake of sim- plicity. Lemma[]still holds when the vertex numbers are varying, since the construction of Equation is independent of this assumption. However, we need the graph to be finite, otherwise I might be uncountable. We leave the discussion on infinite graph sets for future study.
D PROOF OF THEOREM
First, we borrow the concept of T (Equation basic yet powerful Lemma to conclude the proof of Theorem I starhhhtffor... Lemma 3. Over the field of reals. the degree of an irreducible non-trivia univariate polynomial is either one
place of A. Then we leverage the following
Proof. For any f E A. let map it to H h(AA) through the isomorphism æ (Equation 16 for some polynomial h(z) with deg h(x) < r (By Lemmal
By Lemma 3 factorize h(z)) into series of polynomials with the degree at most two, and then merge first-order polynomials into second-order ones until no paired first-order polynomials remaining. Finally, we obtain the following equation:
[D/2] II [=1
h(x))
(x),
(23)
13

---

Under review as a conference paper at ICLR 2021
where D deg h(z). If D is even, deg h() 2 for 1,... [D/2]. Otherwise, there exists some j E [L] such that deg (x) 1. Notice that, the remaining first-order polynomials is at most I, which indicates the sparsity coefficients is very low.
Now we obtain filters H (T) for I 1...,, [D/2]] The last step is applying the inverse of isomorphism to map H T back f()) A as below:
O.T
Σ (G))
(24)
k=
k=0
Recalling Section (() E B2 for = 1,... [D/2]. Since -- 1 also ring isomorphism,
H H(D222) HI) implies f F((D/2))
f()..
Remark that Theorem I can be considered as the GCN-version of Theorem 3 in Zhou 2020). It plays a key step in proving the universality nonlinear CNNs. Our Theorem [ strong tool for analyzing nonlinear GCNs.
thus, provides a
E SYNTHETIC GRAPH SPECTRUM (SGS) DATASET
Our SGS dataset works for node signal filtering regression tasks. We designed 3 types of graph signal filters: high-pass (HP), low-pass (LP) and band-pass (BP) filters, as given in Equation [25 For each type, generate 1000, 1000 and 2000 undirected graphs with graph signals and groundtruth response in the training set, validation set and test set, repectively. Each graph approximately has 80 120 nodes and 80 335 edges. Models trained each sub-dataset expected learn the corresponding filter by supervising the MAE loss.
Fir(()) = 1 expl -50(x 1)}
Fip(s)= 1 e 1)}
(25)
FBp(r)= = 1 - 1.05]] + 1
0.95)
Undirected graphs randomly sampled through rejection sampling of edges from complete graphs In detail, we randomly draw an integer N from [80, 120] as the number of nodes, and then generate a N x N random matrix B with each element independently sampled from Uni 1). Set threshold and we can construct an adjacency matrix A by letting a, = if bi, > 6, otherwise 0i.j O, where oi the element located the i-th row and j-th column of A.
Next, we need to generate spectral signals 8 for the graph. Independent sampling for each spectrum from probabilistic distribution will only generate noises. Hence, we synthesize spectrum by sum- ming random functions. We notice that pdf of the beta distribution Beta(a, b) is a powerful tool to construct diverse curves by tuning shape parameters a and b. Also, Gaussian function Norm(H, or) is able to yield diverse bell-shaped curves by tuning and σ. We sum 2 discretized beta functions, discretized Gaussian functions with random parameters to generate spectral signals. Equation 26 elaborates the generation process and parameter choosing in our experiments, where g a, the pdf of Beta(a, b) distribution, f[z; μ, a) is the pdf of Norm(u, or) distribution.
<[œ]
Σ giz /Na b.] + Σ
[E
1=1
ai by Unif(0.1,55
M Uniffo,
N) N} ar~ Unif
Unif
N N
/9
(26)
(J+1)'
Unif (0.5,
G max f[x; 0z)
14

---

Under review as a conference paper at ICLR 2021
In most real- world cases, graph signals usually represented in vertex-domain. With generated graph and its spectral signals, we can retrieve the vertex domain signals by inverse graph Fourier transformation: perform eigen-decomposition on the normalized adjacency matrix A of the graph to retrieve its graph Fourier basis Ü, then we can find vertex vertex-domain signals by Üs.
For supervising purpose. retrieve the groundtruth of each filter's response by applying each filter to the generated spectral signals, namely (s), E (HP, LP, BP]. Figure 4 illustrates an example of the generated spectral signals and its groundtruth filtering response of the filters.
Input
High-pass GT
Low-pass GT
Band-pass GT
Magnitude
50
100
50
100
200
Frequency
Frequency
Frequency
Frequency
Figure 4: An example of graph spectrum in our SGS dataset and its corresponding high-pass, low- pass and band-pass filtering response using our hand-crafted filters.
F MORE VISUALIZATIONS OF SPECTRUM
We compute spectrum follows: suppose have undirected and unweighted graph with malized adjacency matrix and node signal X E RND,, where N the number of nodes and D is the number of signal channels. Since A symmetric, the adjacency matrix A = TAUT. Then the spectrum of X computed by S U X. More information about the graph spectrum and graph Fourier transformation can be found in Ortega al. 20188.
perform an eigen-decomposition
Figure shows the output spectrum of Vanilla GCN, Ist-Order GCN and SoGCN on the synthetic Band-Pas Pass dataset. The visualizations are consistent to the Tad Figure Vanilla GCN almost loses all the band-pass frequency, resulting to pass part of medium-freet frequency band but still have an obvious distance from the groundtruth filter. SoGCN's filtering response close to the groundtruth response, showing strong ability to represent graph signal filters.
very poor performance. Tst-Order GCN learns
Figure gives more spectrum visualizations on the ZINC dataset. We can observe the spectrum impacts of GRU on Vanilla GCN and our SoGCN. Each curve in the visualization figure represents the spectrum of each output channel, i.e., we plot each column of as curve. (c) SoGCN
(a) Vanilla GCN
(b) Asterr GCN
Predicted
Predicted
Predicted
GT
GT
GT
Magnitude
300
Frequency
Frequency
Frequency
Figure 5: Visualizations of output spectrum the SGS Band-Pa dataset.
15

---

Under review as a conference paper at ICLR 2021
(a) Vanilla GCN
SoGCN w/o GRU
(c) Vanilla GCN GRU
(d) SoGGN GRU
Magnitude
22
20 Fraquency
20 Fraquency
Frequency
Frequency
23
15
30 Frequency
Frequency
Frequency
Frequency
20
12
-55
20
12 Frequency
Frequency
Frequency
Frequency
Figure 6: More visualizations of output spectrum the ZINC dataset.
16


Reviews:
[{"review_id": "vCCoqQ4J-Lj", "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": "The authors argue that second-order graph convolutions (SoGC) should be the building blocks for future graph networks. The argument is that some of the second-order functions cannot be represented by stacking first-order graph convolutions. In contrast, second-order can represent any higher-order ones. In general, the theory is sound and the results on the synthetic data and ZINC are strong and I don't see many flaws, but I would like to see more results on realistic datasets.\n\n##### Strengths\n- The method is quite simple.\n- The results on the synthetic dataset and ZINC are quite impressive.\n- The visualization in Figure 5 convinces me that SoGC can deal with the oversmoothing problem of vanilla GCNs.\n- The theoretical insights and proofs look correct to me, while I am not 100% confident. \n\n##### Weaknesses\n- MNIST and CIFAR 10 do not seem to be real use cases for Graph models. According to the [homepage of MNIST](http://yann.lecun.com/exdb/mnist/), none of the MNIST results in Table 2 is better than an SVM with degree 4 polynomial kernels, a 2-layer MLP with 800d, or a LeNet-1 which has only 3k parameters instead of 100k. It would be better to see results on more realistic datasets where graph networks are close to state-of-the-art.", "extra_scores": {}, "extra_text": {}}, {"review_id": "rgDNyZYxSwb", "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": "The submission identifies the importance of second-order filter by showing that two is the minimally necessary order to achieve full representation power. Based on this observation, this paper proposes Second-Order Graph Convolutional Networks. The proposed method is evaluated on graph classification benchmarks and demonstrates good empirical performance. As far as I know, the proposed method is novel and can inspire future analysis on the expressive power of graph convolution. \n\nStrength:\n- The proposed method, SoGC, is theoretically motivated by the fact that second order graph convolution has universal representation power (Thm. 1)\n- The proposed method demonstrates strong empirical performance on synthetic and real-world datasets\n\nWeakness and Questions:\n- The usage of GRU feels ad-hoc to me. Without using GRU, the proposed method in fact does not achieve state-of-the-art performance on CIFAR10 and MNIST, which is concerning. I understand that the authors attempt to analyze the effect of GRU in Section 5.1. However, the claim that \"GRU retains information from previous layers effectively ...\" needs more supporting evidence than Figure 2, which is conducted on a single graph from a single dataset. I encourage the authors to provide more in-depth analysis of GRU and connects it to the rest of the paper. \nFor more low-level questions: \n     - How is the input node order to the GRU decided? Will changing the input order affect results?\n     - In Figure 2, is the number of parameters controlled? \n     - Would GRU also improves the performance of vanilla GCN? As Figure 2 showed, GRU also changes the signal of a vanilla GCN significantly.\n- I would like to see an ablation study between the non-linear and linear versions of SoGCN. Given that in section 3 the analysis is only done for the linear version, I am curious about how well the linear model can perform. Also, the theory predicts that the linear Second Order GCN should outperform linear Vanilla GCN (this is like SGC?). I would like to see this prediction gets tested.\n- As the authors acknowledge in the introduction, Abu-El-Haija et al. (2019), MixHop, makes similar observations about higher-order GCN. I am curious about how these two models compare to each other performance-wise.\n- Minor note: The submission only evaluates the proposed method on graph classification task. Will the proposed method works for node classification or link prediction? Even if it doesn't, the authors should document the limitations of this method if it doesn't work for those tasks. \n\nTypos:\n- Page 1, the second to last paragraph: \"in channel-wise filtering Furthermore\" -> missing period\n- Page 6, \"we can whiteness the ineffectiveness\" -> \"witness\"\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "qjH00SIdTUy", "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 so-called second-order graph convolution, where an additional second-order term is introduced into traditional first-order graph convolution. The authors explain the merits of second-order graph convolution from the perspective of representation ability. The resulted second-order graph convolutional networks are compared with several graph convolutional networks on three benchmarks. \n\nStrengths:\n+: Incorporation of second-order information into graph convolution seems interesting, and such analogous idea has been verified in 2D convolutions.\n\n+: The proposed method is simple and easy to implement.\n\nWeaknesses:\n-: The idea on incorporation of second-order or higher-order information into convolution is not novel. For example, Factorized Bilinear (FB) [r1] and Second-Order Response Transform (SORT) [r2] introduce second-order terms into traditional 2D convolutions, and they also claim second-order terms have better representation ability. Besides, second-order or higher-order information have also been used for global pooling for convolution networks [r3, r4, r5], which also show better representation ability. This paper lacks discussions on above these works, which will bring a side effect on contributions of this paper.\n[r1] Factorized bilinear models for image recognition, ICCV 2017.\n[r2] SORT: Second-order response transform for visual recognition, ICCV 2017.\n[r3] Second-Order Pooling for Graph Neural Networks, arXiv, 2020.\n[r4] Deep CNNs Meet Global Covariance Pooling: Better Representation and Generalization, TPAMI 2020.\n[r5] Kernel pooling for convolutional neural networks, CVPR, 2020.\n\n-: The experimental results are not very convincing.\n(1) As shown in Table 2, pure soGCN achieves no improvement over compared methods, i.e., GatedGCN. GRU brings further gains for soGCN, but could GRU bring improvement for other compared methods?\n(2) Number of parameters hardly represents model complexity totally. The model with the same number of parameters can have different computational complexity. Therefore, more metrics on model complexity (e.g., FLOPs) are suggested for comparison in Table 2.\n(3) CIFAR10 and MNIST are too small and old to verify the effectiveness of different methods. The authors would better conduct experiments on more graph benchmarks. Besides, why higher-order  GCN are not compared on real-world benchmarks.\n(4) Why parameters number of 3WLGNN is 100K on ZINC ?\n\n-: The writing needs significant improvement.\n(1) The authors would better give more detailed descriptions on differences between the proposed soGCN and related works ([Defferrard, 2016] and [Kipf&Welling, 2017]), further clarifying the contributions of the proposed method.\n(2) I wonder the detailed computation methods and each curve in Fig.2, and why SoGCN is better than Vanilla GCN?\n(3) The comparisons in terms of representation ability in section 4.3 is not very clear. The authors would better add a table to summarize representation ability of different graph convolution.\n(4) Which method does MoNet indicate in Table 2 ?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "naBYXnNKMH0", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 is yet another paper on graph convolutional networks (GCNs). The investigated SoGCN is a second-order GCN, thus a special case of high-order GCNs (namely with multi-hop graph kernels), which have has been proposed earlier by many researchers, such as by Defferrard et al. (2016), by Kipf & Welling (2017) and by Abu-El-Haija et al. (2019). \n\nThe main interest is that a second-order GC is a universal approximator, because any univariate polynomial can be factorized into sub-polynomials of degree two, which is not the case of first-order GCs. \n\nThe paper has some theoretical derivations that seem interesting. However, the proposed second-order GC is a special case of well-studied frameworks, which have been widely studied in the literature, such as with the expressive power analysis. As a consequence, the derived theoretical results seem less relevant. \n\nIn conducted experiments, the authors do not consider the same comparative analysis in all experiments. For example, two versions of the nonlinear activation are considered in experiments on CIFAR10 (with and without GRU); however, they were not considered in other experiments. Moreover, it is not clear where the combined RELU and GRU is considered.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four reviewers have reviewed this paper. After rebuttal, the reviewers' recommendations were borderline. Rev. 4 remains concerned about relation of second-order approaches in CV and second-order filters. Indeed, there exists a connection although it is perhaps subtle in its nature and equally concerning is the connection with general Polynomial filters in many GCN papers. As other reviewers point out, MixHop and Jumping Knowledge also allow multi-hop designs. More importantly, APPNP and SGC networks allow multiple hops. From that point of view, the proposed approach is rather a recap of existing observations and contributions. Finally, even Rev. 2 has indicated that the paper is perhaps 'average' after checking with comments of other reviewers. Therefore, at this point, the paper is slightly below the acceptance threshold.

Decision: Reject