Polynomial Graph Convolutional Networks
Authors: Luca Pasa
Nicolò Navarin
Alessandro Sperduti
Venue:  (2021)
Keywords: Graph Convolutional Networks
Graph Neural Network
Deep Learning
Structured Data
Machine Learning on Graphs

Abstract: Graph Convolutional Neural Networks (GCNs) exploit convolution operators, based on some neighborhood aggregating scheme, to compute representations of graphs. The most common convolution operators only exploit local topological information. To consider wider topological receptive fields, the mainstream approach is to non-linearly stack multiple Graph Convolutional (GC) layers. In this way, however, interactions among GC parameters at different levels pose a bias on the flow of topological information. In this paper,  we propose a different strategy, considering a single graph convolution layer that independently exploits neighbouring nodes at different topological distances, generating decoupled representations for each of them. These representations are then  processed by subsequent readout layers. We implement this strategy introducing the Polynomial Graph Convolution (PGC) layer, that we prove being more expressive than the most common convolution operators and their linear stacking. Our contribution is not limited to the definition of a convolution operator with a larger receptive field, but we prove both theoretically and experimentally that the common way  multiple non-linear graph convolutions are stacked limits the neural network expressiveness. Specifically, we show that a Graph Neural Network architecture with a single PGC layer achieves state of the art performance on many commonly adopted graph classification benchmarks.

Under review as a conference paper at ICLR 2021
POLYNOMIAL GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Convolutional Neural Networks (GCNs) exploit convolution operators, based on some neighborhood aggregating scheme, to compute representations of graphs. The most common convolution operators only exploit local topological in- formation. To consider wider topological receptive fields, the mainstream approach is to non-linearly stack multiple Graph Convolutional (GC) layers. In this way, how- ever, interactions among GC parameters at different levels pose bias on the flow of topological information. In this paper, we propose a different strategy, considering single graph convolution layer that independently exploits neighbouring nodes at different topologiaal distances, generating decoupled representations for each of them. These representations We implement this strategy introducing the Polynomial Graph Convolution (PGC) layer, that we prove being more expressive than the most common convolution op- erators and their linear stacking. Our contribution is not limited to the definition of a convolution operator with larger receptive field, but we prove both theoretically and experimentally that the common way multiple non-linear graph convolutions are stacked limits the neural network expressiveness. Specifically, we show that a Graph Neural Network architecture with single PGC layer achieves state of the art performance on many commonly adopted graph classification benchmarks.
then processed by subsequent readout layers.
INTRODUCTION
In the last few years, the definition of machine learning methods, particularly neural networks, for graph-structured input has been gaining increasing attention in literature (Defferrad et al. 2016 Errica al. 2020). In particular, Graph Convolutional Networks (GCNs), based the definition of a convolution operator in the graph domain, are relatively fast to compute and have shown good predictive performance. Graph Convolutions (GC) are generally based on neighborhood aggre- gation scheme (Gimmer et al. 2017) considering, for each node, only its direct neighbors. Stacking multiple GC layers, the size the receptive field of deeper filters increases (resembling standard convolutional networks). However, stacking too many GC layers may be detrimental on the network ability to represent meaningful topological information (Li et al. 2018) due to a too high Laplacian smoothing. Moreover, in this way interactions among GC parameters at different layers pose bias on the flow of topological information. For these reasons, several convolution operators have been defined in literature, differing from one another in the considered aggregation scheme. We argue that the performance of GC networks could benefit by increasing the size of the receptive fields, but since with existing GC architectures this effect can only be obtained by stacking more GC layers, the increased difficulty in training and the limitation of expressiveness given by the stacking of many local layers ends up hurting their predictive capabilities.
Consequently, the performances of existing GCNs are strongly dependent on the specific architecture. Therefore, existing graph neural network performances are limited by (i) the necessity to select an appropriate convolution operator, and (ii) the limitation of expressiveness caused by large receptive fields being possible only stacking many local layers.
In this paper, we tackle both the issues following different strategy. We propose the Polynomial Graph Convolution (PGC) layer that independently considers neighbouring nodes at different topo- logical distances (i.e. arbitrarily large receptive fields). The PGC layer faces the problem of selecting a suitable convolution operator being able to represent many existing convolutions in literature, and being more expressive than most of them. As for the second issue PGC layer, directly considering larger receptive fields, can represent a richer set of functions compared to the linear stacking of two or more Graph Convolution layers, i.e. it is more expressive. Moreover, the linear PGC design allows

---

Under review as a conference paper at ICLR 2021
to consider large receptive fields without incurring in typical issues related to training deep networks. We developed the Polynomial Graph Convolutional Network (PGCN), an architecture that exploits the PGC layer to perform graph classification tasks. We empirically evaluate the proposed PGCN on eight commonly adopted graph classification henchmarks. We compare the proposed method to several state-of-the-ard GCNs, consistently achieving higher comparable predictive performances. Differently from other works in literature, the contribution of this paper is to show that the common approach of stacking multiple GC layers may not provide an optimal exploitation of topological information because of the strong coupling of the depth of the network with the size of the topological receptive fields. In our proposal, the depth of the PGCN decoupled from the receptive field size, allowing to build deep GNNs avoiding the oversmoothing problem.
2 NOTATION
We use italic letters to refer to variables, bold lowercase to refer to vectors, and bold uppercase letters to refer to matrices. The elements of a matrix A are referred to as aij (and similarly for vectors). We use uppercase letters to refer to sets or tuples. Let G (V, E, X) be graph, where V = { Un- Un-1) denotes the set of vertices (or nodes) of the graph, E C V x V is the set of edges, and X Rux* is a multivariate signal on the graph nodes with the i-th row representing the attributes of Us. We define A E TRnx as the adjacency matrix of the graph, with elements ag + (vi vy) E E. With (v)) we denote the set of nodes adjacent to node v. Let also DE 1 be the diagonal degree matrix where du E, aij. and L the normalized graph laplacian defined by L = D AD where I is the identity matrix.
With GConvo (x,: G)) denote a graph convolution with of parameters 6. A GCN with is levels of convolutions is denoted as GConee, (... ....GConu,, (Xe, G) ..., G). For a discussion about the most common GCNs we refer to Appendix A We indicate with X the input representation fed to a layer, where X = X if we are considering the first layer of the graph convolutional network, or X = ( if considering the i-th graph convolution layer.
3 POLYNOMIAL GRAPH CONVOLUTION (PGC)
In this section, we introduce the Polynomial Graph Convolution (PGC), able simultaneously and directly consider all topological receptive fields up to i hops. just like the ones that are obtained by the graph convolutional layers in a stack of size k. PGC, however, does not incur in the typical limitation related to the complex interaction among the parameters of the GC layers. Actually, we show that PGC is more expressive than the most common convolution operators. Moreover, we prove that a single PGC convolution of order l is capable of implementing k linearly stacked layers of convolutions proposed in the literature, providing also additional functions that cannot be realized by the stack. Thus, the PGC layer extracts topological information from the input graph decoupling in an effective way the depth of the network from the size of the receptive field. Its combination with deep MLPs allows to obtain deep graph neural networks that can overcome the common oversmoothing problem of current architectures. The basic idea underpinning the definition of PGC is to consider the case in which the graph convolution can be expressed the powers of a transformation T of the adjacency matrix. This definition is very general, and thus incorporates many existing graph convolutions as special cases. Given graph G = (V. F, X) with adjacency matrix A, the Polynomial Graph Convolution (PGC) layer of degree k. transformation T of A, and size m, is defined
polynomial of
PGCoRU, A) RR.TW, W.
where T(A) E Rax", R&,T E (2xx=((+11, RE.T = ( TIAXXXXXXIXXXXX.. [()) and W (k++))) is a learnable weight matrix. For the sake of presentation, we will consider W as composed of blocks: W = -Wo..... WalT, with W, E Raxim In the following, we show that PGC is very expressive, able implement commonly used convolutions as special cases.
2

---

Under review as a conference paper at ICLR 2021
3.1 GRAPH CONVOLUTIONS IN LITERATURE AS PGC INSTANTIATIONS
The PGC layer in equation is designed to be a generalization of the linear stacking of some of the most common spatially localized graph convolutions. The idea is that spatially localized convolutions aggregate over neighbors (the message passing phase) using a transformation of the adjacency matrix (e.g. normalized graph Laplacian). We provide in this section formal proof, as a theoretical contribution of this paper, that linearly stacked convolutions can be rewritten as polynomials of powers of the transformed adjacency matrix.
We start showing how common graph convolution operators can be defined as particular instances of single PGC layer (in most cases with k 1). Then, we prove that linearly stacking any two PGC layers produces a convolution that can be written single PGC layer as well.
Spectral:
The Spectral convolution (Defferrard et al. 2016) can be considered the application of Fourier transform to graphs. It is obtained via Chebyshev polynomials of the Laplacian matrix. A layer of Spectral convolutions of order h- can be implemented by a single PGC layer instantiating T(A) to be the graph Laplacian matrix (or one of its normalized versions), setting the PGC & value to k*, and setting the weight matrix to encode the constraints given by the Chebyshev polynomials. For instance, can get the output H of Spectral convolution layer with k* by the following PGC:
Wo W₂
W 3W3 3
= X, L'x where W
W E Re
(2)
2W2
4W3 3
The Graph Convolution Kipt Welling 2017) (GCN) is a simplification of the spectral convolution. The authors propose to fix the order E = 1 of the Chebyshev spectral convolution to obtain a linear first order filter for each graph convolutional layer neural network. By setting
GCN:
= and T(A) = D AD E Raxx, with A = A + I and di = E, āej. we obtain the following equivalent equation:
= ADD : where W
W1
where O is a 8 x m matrix with all entries equal to zero and W, E Rexm is the weight matrix of GCN. Note that the GCN does not consider node differently from its neighbors, thus in this case there is no contribution from the first component of RR,T.
GraphConv: In Morris et al. (2019) powerful graph convolution has been proposed, that is inspired by the Weisfeiler-Lehman graph invariant. In this case, T(A) A (the identity function), and k is again set to 1. single GraphConv layer can be written as:
W W
H X, AX,W, where W
and Wo, W1 E gx
The Graph Isomorphism Network (GIN) convolution was defined in Xu al. (2019) as: H' MLP((1 + x) + AX). Technically, this is composition of convolution (that is linear operator) with multi-layer perceptron. Let us thus decompose the MLP() as f g. where is an affine projection via weight matrix W, and f incorporates the element-wise non-linearity, and the other layers of the MLP. We can thus isolate the GIN graph convolution component and define it as specific PGC istantiation. We let & and T() the identity function before. A single GIN layer can then be obtained as:
GIN:
H XXX]/, where W W- [[(
[1+c)W, W,
(5)
Note that, differently from GraphComv, in this case the blocks of the matrix W are tied. Figure in Appendix depicts the expressivity of different graph convolution operators in terms of the respective constraints on the weight matrix W. The comparison is made easy by the definition of the different
graph convolution layers as instances of PGC layers. Actually, it is easy to see from eqs. ( that GraphConv is more expressive than GCN and GIN.
3

---

Under review as a conference paper at ICLR 2021
3.2 LINEARLY STACKED GRAPH CONVOLUTIONS AS PGC INSTANTIATIONS
In the previous section, we have shown that common graph convolutions can be expressed as particular instantiations of PGC layer. In this section, we show that single PGC layer can model the linear stacking of any number of PGC layers (using the same transformation 7). Thus, a single PGC layer can model all the functions computed by arbitrarily many linearly stacked graph convolution layers defined in the previous section. We then show that a PGC layer includes also additional functions compared to the stacking of simpler PGC layers, which makes more expressive.
Theorem 1. Let us consider two linearly stacked PGC layers using the same transformation T. The resulting linear Graph Convolutional network can be expressed by a single PGC layer.
Due to space limitations, the proof reported in appendix C Here it is important to know that the proof of Theorem tells that single PGC of order ls can represent the linear stacking of any q (T-compatible) convolutions such that k = Di= d4, where d; is the degree of convolution at level i. We will now show that single PGC layer can represent also other functions, i.e. it more general than the stacking of existing convolutions. Let us consider, for the sake of simplicity, the stacking of 2 PGC layers with a: (that are equivalent GraphCony layers, see eq. equation 4 each with
parameters W (w6", W = 1,2, w-(". w E TR w w E IR The same reasoning be applied to any other convolution among the ones presented in Section 3.1
We can explicitly write the equations computing the hidden representations:
H xw!" + AXW
H (2) = H 11) 0 + A w
(7)
= X ( A + w (!" w() + W(.
A single PGC layer implement this second order convolution
w
(( (2)
0
H 2) = A'x
w
W
w
(8)
Let us compare it with PGC layer that corresponds the same 2-layer architecture but that has no constraints on the weight matrix, i.e.:
Wo
2 AxXX
W
W. E Raxma i= 0, 1,
W₂
Even though it is not obvious at first glance, equation is more constrained than equation g
i.e. there are some values of Wo. W1, W2 in equation 9 that cannot be obtained for any W [W:!), [()] and 22 (w " in equation 8 as proven by the following theorem.
Theorem 2. PGC layer with & = 2 is more general than two stacked PGC layers with k: = with the same number of hidden units m.
We refer the reader to Appendix Coror the proof. Notice that the GraphConv layer is equivalent to a PGC layer with &- 1 (if no constraints on W are considered, see later in this section). Since the GraphConv is, in turn, more general than GCN and GIN, the above theorem holds also for those graph convolutions. Moreover, Theorem
2 trivially implies that linear stack of q PGC layers with k is less expressive than a single PGC layer with = q.
If we consider that in many GCN architectures it is typical, and useful, to concatenate the output of all convolution layers before aggregating the node representations, then it is not difficuut to see that such concatenation consider a network that generates a hidden representation that is the concatenation of the different representations computed on each layer, i.e. H = H H E R m = my + m2. We can represent 2-layer GraphConv network single PGC layer as:
be obtained by making wider the weight matrix of PGC. Let thus
(
( W2
= = AXX A
w (1)
w!l))
W( + ( w(
(10)
W (
4

---

Under review as a conference paper at ICLR 2021
More in general, if we consider GraphCony convolutional layers (see eq. (4) ) each with parameters
W (w()) W ,....,,, k w W E 1Rm--xmm my 8, m Σj= the weight
matrix W (=)k))) can be defined follows:
Fo.(wW)
(o,)(W0) w ( W W
(i2( w
(L)(
W W
0
Fa,(W w(
Fa (Wa
W W
(II)
F3,3 (W() W W()
where F,,,, i,j E (O,....,A)) k), S j. are defined as
Pgy(WO) ..... W = Σ
II
(1 (E 8=1 S.L. E =i=
We can now generalize this formulation by concatenating the output of k + PGC convolutions of degree ranging from 0 up to k. This gives rise to the following definitions:
Wo.0
Wo,1
Wa,2
Wo,
(XWao)
W 1,3
WL
WI.
(XWo. + ((A)XW1.)
W22
W2d
W
-=
(12)
(XWo + T(A) XW
We.
where we do not put constraints among matrices Wi E Rexm, m === Et my. which are considered mutually independent. Note that as consequence of Theorem 2 the network defined in equation [2 is more expressive than the one obtained concatenating different Graphioon layers as defined in equation [] It can also be noted that the same network can actually be seen as a single PGC layer of order k + I with constraint on the weight matrix (i.e., be upper triangular block matrix). Of course, any weights sharing policy can be easily implemented, e.g. by imposing vj W., W. which corresponds the concatenation of the representations obtained at level by single stack of convolutions. In addition to reduce the number of free parameters, this weights sharing policy allows the reduction the computational burden since the representation level obtained by summing to the representation of level i the contribution of matrix W, i.e. A A'W,
3.3 COMPUTATIONAL COMPLEXITY
As detailed in the previous discussion, the degree of PGC layer controls the size of its considered receptive field. In terms of the number of parameters, fixing the node attribute size and the size m of the hidden representation, the number of parameters of the PGC is O(s k m), i.e. it grows linearly in k. Thus, the number of parameters of PGC layer of the same order of magnitude compared to l stacked graph convolution layers based on message passing (Gilmer et al. 2017) (i.e. GraphConv, GIN and GCN, presented in Section 3.II.
If we consider the number of required matrix multiplications, compared to message passing GC networks, our case is possible to pre-compute the terms TAA)xX before the start of training, making the computational cost of the convolution calculation cheaper compared to message passing. In Appendix E. we report an example that makes evident the significant improvement that can be gained in training time with respect to message passing.
4 POLYNOMIAL GRAPH CONVOLUTIONAL NETWORK (PGCN)
In this section, we present neural architecture that exploits the PGC layer to perform graph classification tasks. Note that, differently from other GCN architectures, in our architecture (exploiting the PGC layer) the depth of the network is completely decoupled from the size & of the receptive field. The initial stage of the model consists of a first PGC layer with 1. The role of this first layer is to develop initial node embedding to help the subsequent PGC layer fully exploit its power. In fact,
5

---

Under review as a conference paper at ICLR 2021
in bioinfromatics datasets where node labels X are one-hot encoded, all matrices X, AX, A'X are very sparse, which we observed, in preliminary experiments, influences in a negative way learning. Table Appendix (ooomirrreecm the sparsity of the PGC representation using the original one-hot encoded labels against their emhedding obtained with the first PGC layer. The analysis shows that using this first layer the network can work significantly denser representations of the nodes. Note that this first stage of the model does not significantly bound the PGC-layer expressiveness. A dense input for the PGC layer could have been obtained by using an embedding layer that is not graph convolutional operator. However, this choice would have made difficult to compare our results with other state-of- offtthe-rt models in Section 6 since the same input transformation could have been applied to other models as well, making unclear the contribution of the PGC layer to the performance improvement. This why we decided to use PGC layer with
(equivalent to a GraphConv) to compute the node embedding, making the results fully comparable since we are using only graph convolutions in our PGCN. For what concerns the datasets that do not have the nodes' label (like the social networks datasets), using the PGC layer with & = 1 allows to create a label for each node that will be used by the subsequent larger PGC layer to compute richer node's 's representations. After this first PGC layer, PGC layer described in eq. equation 12 of degree i is applied. In order to reduce the number of hyperparameters, we adopted the same number I+II of columns (i.e., hidden units) for
m
matrices W t.j. i.e. W., E R graph-level representation s E R.= based on the PGC layer output H is obtained by an aggregation layer that exploits three different aggregation strategies over the whole set of nodes V, j = I....,m: m:
avg avg (1 lo V)), sT = max max((1 E V)), 9gmT = sum (ghg E V)), 5
[s] 2ng max
888 ,81 eum ang 8 8m ,m
maa saum
The readout part of the model is composed of q dense forwar layers, where we consider and the number of neurons per layer as hyper-parameters. Each one of these layers uses the ReLU
activation function, and is defined as yj Le (LLLuWWadoowwy y,-1 + breadout).
0,..., 4
where yo- = s. Finally, the output layer of the PGCN for a c-class classification task is defined as: LogSof (mo (Woaaaoolyyyyyoo yn + boue).
COMPARISON VS MULTI-SCALE GCN ARCHITECTURES IN LITERATURE
Some recent works in literature exploit the idea of extending graph convolution layers to increase the receptive field size. In general, the majority of these models, that concatenate polynomial powers of the adjacency matrix A, are designed to perform node classification, while the proposed PGCN is developed to perform graph classification. In this regard, we want to point out that the novelty introduced in this paper is not limited to a novel GC-layer, but the proposed PGCN is a complete architecture to perform graph classification. Atwood & Towsley (2016) proposed a method that exploits the power series of the probability transition matrix, that is multiplied (using Hadamard product) by the inputs. The method differs from the PGCN even in terms of how the activation is computed and even because the activation computed for each exponentiation is summed, instead been concatenated. Similarly in [Defferrard et al. (2016) the model exploits the Chebyshev polynomials, and, differently from PGCN sums them over k. This architectural choice makes the proposed method less general than the PGCN. Indeed, as showed in Section 3.] the model proposed in (Defferrard ct al.
2016 is an instance of the PGC.
2018 the authors proposed to modify the common aggregation layer in such a way that, for each node, the model aggregates all the intermediate representations computed in the previous GC-layers. In this work, differently from PGCN, the model exploits the message passing method introducing a bias in the flow of the topological information. Note that, as proven in Theorem 2 PGC layer of degree k is not equivalent to concatenate the output of k stacked GC layers, even though the PGC layer can also implement this particular architecture.
In (Xu et al.
Another interesting approach is proposed in (Tran et al. 2018), where the authors consider larger receptive fields compared to standard graph convolutions. However, they focus on a single convolution definition (using just the adjacency matrix) and consider shortest paths (differently from PGCN that exploits matrix exponentiations, i.e. random walks). In terms of expressiveness, it is complex to compare methods that exploit matrix exponentiations with methods based on the shortest paths. However, it is interesting notice that, thanks the very general structure of the PGC layer, it is
6

---

Under review as a conference paper at ICLR 2021
easy to modify the PGC definition in order to use the shortest paths instead of the adjacency matrix transformation exponentiations. In particular, we plan to explore this option as the future development of the PGCN.
Wu et al. introduce a simplification of the graph convolution operator, dubbed Simple Graph Convolution (SGC) (Wu et al.] 2019). The model proposed is based the idea that perhaps the nonlinear operator introduced by GCNs is not essential, and basically, the authors propose to stack several linear GC operators. In Theorem we prove that staking k GC layers is less expressive than using a single PGC layer of degree k. Therefore, we can conclude that the PGC Layer is a generalization of the SGC.
In (Liao et al. 2019) the authors construct a deep graph convolutional network, exploiting particular localized polynomial filters based on the Lanczos algorithm, which leverages multi-scale information.
This convolution can be easily implemented by PGC layer. In (Chen et al. 2019 the authors propose to replace the neighbor aggregation function with graph augmented features. These graph augmented features combine node degree features and multi-scale graph propagated features. Basically, the proposed model concatenates the node degree with the power series of the normalized adjacency matrix. Note that the graph augmented features differ from Rg,T, used in the PGC layer. Another difference with respect to the PGCN resides on the subsequent part of the model. Indeed, instead of projecting the multi-scale scale features layer using structured weights matrix, the model proposed in (Chen et al. 2019 aggregates the graph augmented features of each vertex and project each of these subsets by using MLP. The model readout then sums the obtained results over all vertices and projects it using another MLP.
Luan et al. 2019) introduced two deep GCNs that rely on Krylov blocks. The first one exploits GC layer, named snowball, that concatenates multi-scale features incrementally, resulting in a densely- connected graph network. The architecture stacks several layers and exploits nonlinear activation functions. Both these aspects make the gradient flow more complex compared to the PGCN. The second model, called Truncated Krylov, concatenates multi-scale features in each layer. In this model. differently from PCGN, the weights matrix of each layer has no structure, thus topological features from all levels are mixed together. A similar approach is proposed in (Rossi et al. 2020). Rossi et. al proposed alternative method, named SIGN, to scale GNN to very large graph. This method uses as a building block the set of exponentiations of linear diffusion operators. In this building block, every exponentiation of the diffusion operator is linearly projected by learnable matrix. Moreover, differently from the PGC layer, a nonlinear function is applied on the concatenation of the diffusion operators making the gradient flow more complex compared to the PGCN.
Very recently Liu et al. 2020) proposed a model dubbed Deep Adaptive Graph Neural Network, to learn node representations by adaptively incorporating information from large receptive fields. Differently from PGCN, first, the model exploits an MLP network for node feature transformation. Then it constructs a multi-scale representation leveraging on the computed nodes features transfor- mation and the exponentiation of the adjacency matrix. This representation is obtained by stacking the various adjacency matrix exponentiations (thus obtaining a 3-dimensional tensor). Similarly to (Luan et al., 2019)) also in this case the model projects the obtained multi-scale representation using weights matrix that has no structure, obtaining that the topological features from all levels are mixed together. Moreover, this projection uses also (trainable) retainment scores. These scores measure how much information of the corresponding representations derived by different propagation layers should be retained to generate the final representation for each node in order to adaptively balance the information from local and global neighborhoods. Obviously, that makes the gradient flow more complex compared to the PGCN, and also impact the computational complexity.
6 EXPERIMENTAL SETUP AND RESULTS
In this section, we introduce our model set up, the adopted datasets, the baselines models, and the hyper-parameters selection strategy. We then report and discuss the results obtained by the PGCN.
For implementation details please refer to Appendix G
Datasets. We empirically validated the proposed PGCN on five commonly adopted graph classifica- tion benchmarks modeling bioinformatics problems: PTC (Helma et al., (200)), NCII (Wale et al. 2008), PROTHINS, (Borgwardt et al. 2005), D&D (Dobson & Doig. 2003) and ENZYMES (Borg
7

---

Under review as a conference paper at ICLR 2021
Model \.
Dataset
PTC
NCH1
PROTEINS
D&D ENZYMES COLLAB
IMDB-B IMDB-M
PSCN1
60.00
76.34
75.00
76.27
72.60
71.00
45.23
+4.82
#1.68
+2.51
+2.64
#2.15
22.29
22.84
FGCNN2
58.82
81.50
74.57
77.47
+1.80
+0.39
+0.80
+0.86
DGCNN
57.14
72.97
73.96
78.09
+2.19
#0.87
#0.41
+0.72
DGCNNS
76.4
72.9
76.6
38.9
57.4
53.3
38.6
+1.7
#3.5
#4.3
#5.7
#1.9
=5.0
+2.2
GIN
80.0
73.3
75.3
59.6
75.9
66.8
42.2
#1.4
#4.0
#2.9
#4.5
#1.9
=3.9
+4.6
DIFFPOOL"
76.9
73.7
75.0
59.5
67.7
68.3
45.1
+1.9
=3.5
+3.5
#5.6
#1.9
=6.1
+3.2
GraphSAGE
76.0
73.0
72.9
58.2
71.6
69.9
47.2
#1.8
+4.5
+2.0
#6.0
#1.5
=4.6
+3.6
Baseline 3
69.8
75.8
78.4
65.2
55.0
50.7
36.1
+2.2
#3.7
#4.5
#6.4
#1.9
#2.4
+3.0
PGCN
60.50
82.04
75.31
79.45
70.5
74.1
72.60
47.39
#0.67
+0.26
+0.31
#0.29
+1.77
#1.69
+3.80
#3.51
Table 1: Accuracy comparison between PGCNN and several state-of-the-ar models on graph classification task."
Niepert et al. 2016).
Navarin al. 2020
"Erric et al. 2020).
wardt et al. 2005 Moreover, we also evaluated the PGCN on 3 large graph social datasets: COLLAB. IMDB-B, MMBB-M (Yanardag & Vishwanathan 2015). report more details Appendix D
Baselines and Hyper-parameter selection. We compare PGCN versus several GNN architectures, that achieved state-of-the-art results on the used datasets. Specifically, we considered PSCN (Niepert)
et al. 2016). Funnel GCNN (FGCNN) model (Navarin et al.) 2220)) DGCNN (Zhang al. (0018).
GIN Xu et al. 2019), DIFFPOOL (Ying et al., 2018 and GraphSage (Hamilton et al. 2017 Note
that these graph classification models exploit the convolutions presented in Section 3.1 From
Errica
et al.
2020) we report also the results of a baseline models that structure-agnostic.
The results were obtained by performing 5 runs of 10-fold cross- validation. The apper-parameters
of the model (number of hidden units, learning rate, weight decay, k; ②) were selected using grid
search, where the explored
of values were changed based the considered dataset. Other details about validation are reported in Appendix
The results reported in Xu al. (2019); Chen et al. (2019); Ying al. (2018) are not considered in our comparison since the model selection strategy is different from the one we adopted and this makes the results not comparable. The importance of the validation strategy is discussed in |Errcca
et al.] (2020), where results of fair comparison among the considered baseline models are reported. For the sake completeness, we also report (and compare) in Appendix the results obtained by evaluating the PGCN method with the validation policy used in Xu et al. (2019); Chen et al. (2019)
Ying et al. 2018).
6.1 RESULTS AND DISCUSSION
The results reported in Table show that the PGCN achieves higher results in all (except one) considered datasets compared to competing methods. In particular, on NCII and ENZYMES the proposed method outperforms state-of-the-an results. In fact, in both cases, the performances of PGCN and the best competing method are more than one standard deviation apart. Even for PTC, D&D, PROTEINS, IMDB-B and IMDB-M datasets PGCN shows slight improvement over the results of FGCNN and DGCNN models. Furthermore, the results of PGCN in Bioinformatics datasets achieves a significant lower standard deviation (evaluated over the runs of 10-fold cross-validationn For what concerns the COLLAB datasets, PGCN obtained the second higher result in the considered state-of-te the-art methods. Note however that the difference with respect to the first one (GIN) within the standard deviation.
8

---

Under review as a conference paper at ICLR 2021
Dataset k
3
5
6
Dataset
3
5
PTC
74.0
68.86
69.14
14
69.43
COLLAB
76.91
76.32
76.96
76.72
12.81
+2.44
+2.33
+1.78
+1.47 =1.45
+2.14
+ +1.60
NCI1
82.68
83.16
84.40
81.04
IMDB-B
76.70
76.60
76.38
77.88
+0.22
+0.70
#0.14
+0.83
+3.48
=3.84
+2.90
+3.11
PROTEINS
79.20
78.48
78.48
78.84
IMDB-M
52.37
52.7
52.41
52.97
+0.81
+0.56
+1.04
+0.80
+3.02
=2.84
#2.85
+2.67
D&D
81.95
82.03
81.69
82.54
#1.19
+1.06
+0.68
11.09
ENZYMES
77.50
76.83
78. 17 77.18
#1.27
+0.85 10.68 +0.92
Table 2: PGCN accuracy comparison on the validation set of the datasets for different values of k.
Significativity of our results. To understand if the improvements reported in Table I are significant or can be attributed to random chance, we conducted the two-tailed Wilcoxon Signed- Ranks test between our proposed PGCN and competing methods. This test considers all the results for the different datasets at the same time. According to this test, PGCN performs significantly better (p-value 0.05) than PSCN, DGCNN', GIN, DIFFPOOL and GraphSAGE. As for FGCNN and DGCNN", four datasets are not enough to conduct the test.
Impact of receptive field size on PGCN. Most of the proposed GCN architectures in literature generally stack 4 or fewer GCs layers. The proposed PGC layer allows to represent a linear version of these architectures by using a single layer with an even higher depth (k), without incurring in problems related to the flow of the topological information. Different values of k have been tested to study how much the capability of the model to represent increased topological information helps to obtain better results. The results of these experiments in this table are referred to the validation sets, since the choice of is part of the model selection procedure. We decided take into account range of k values between and 6 for bioinformatics datasets, and between 3 to 9 for social networks datasets. The results show that it is crucial to select an appropriate value for k. Several factors influence how much depth is needed. is important to take into account that the various datasets used for the experiments refer to different tasks. The quantity and the type of topological information required (or useful) to solve the task highly influences the choice of k. Moreover, also the input dimensions and the number of graphs contained in a dataset play an important role. In fact, using higher values of & increases the number columns of the R&,T matrix (and therefore the number of parameters embedded in W), making the training of the model more difficult. is interesting to notice that in many cases our method exploits a larger receptive field (i.e. a higher degree) compared to the competing models. Note that the datasets where better results are obtained with k = (PTC and PROTEINS) contain a limited amount of training samples, thus deeper models tend to overfit arguably for the limited amount of training data.
reported in Table 2 The accuracy results
7 CONCLUSIONS AND FUTURE WORKS
In this paper, we analyze some of the most common convolution operators evaluating their expres- siveness. Our study shows that their linear composition can be defined instances of more general Polynomial Graph Convolution operator with higher expressiveness. We defined an architecture exploiting single PGC layer to generate a decoupled representation for each neighbor node at a different topological distance. This strategy allows us to avoid the bias on the flow of topological information introduced by stacking multiple graph convolution layers. We empirically validated the proposed Polynomial Graph Convolutional Network on five commonly adopted graph classification benchmarks. The results show that the proposed model outperforms competing methods in almost all the considered datasets, showing also more stable behavior.
In the future, we plan to study the possibility to introduce an attention mechanism by learning a transformation T that can adapt to the input. Furthermore, will explore whether adopting our PGC operator as a large random projection can allow to develop novel model for learning on graph domains.

---

Under review as a conference paper at ICLR 2021
REFERENCES
James Atwood and Don Towsley. Diffusiinn-oonvllttional neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Karsten Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl_I): i47-i56, 2005.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv preprint arXiv:1905.04559, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, pp. 3844-3852, 2016.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. Proceedings of the 34th International Conference on Machine Learning. pp. 1263-1272, apr 2017. BRLLtttp://axxiv.oo
/10es//77000 704. 01212
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformatics, 17(1):107-108, 2001.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.669 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. networs.. In ICLR, pp. 1-14, 2017. ISBN 978 1970688 doi: 10.165110000-666//201522222 URL
http://arx org/ awwgg//b///ae 1609 02907
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Inielligence, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep
graph convo- convo-lutional networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp- 338 338-348,73 2020.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In Advances in neural information processing systems, pp. 10945-10955, 2019.
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498-4) 511, 2009.
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 Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602 4609, oct 2019. doi: 10.11.0....... 1609/aaii v33101 v33001.33014444344 33014602, URLbttp:: /
abs 02244]
10

---

Under review as a conference paper at ICLR 2021
Nicolò Navarin, Dinh Van Tran, and Alessandro Sperduti. Learning kemel-basee embeddings in graph neural networks. In 24th European Conference on Artificial Intelligence ECAI 2020, 2020.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In ICML, pp. 2014-2023, 2016.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. / /98, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80 2008.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(77): 2539-2561, 2011.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures, IEEE Trans. Neural Networks, 8(3):714-735, 1997. doi: 10.1109/72.572108. URL
https://do/ www.oro................oo.... 110.0..1111...... 572108
Dinh V Tran, Nicolò Navarin, and Alessandro Sperduti. On filter size in graph convolutional networks. In 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 15411. IEEE, 2018.
Nikil Wale, Ian Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying Graph Convolutional Networks. ICML, feb 2019. URL http://
www.v.orgg/bb//1902..
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. volume 80 of Proceedings of Machine Learning Research, pp.
Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL httpp:pp/pproeeecoo......rressss
html
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference on Learning Representations, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pp. 4800-4810, 2018
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018

---

Under review as a conference paper at ICLR 2021
A GRAPH NEURAL NETWORKS
A Graph Neural Network (GNN) is a neural network model that exploits the structure of the graph and the information embedded in feature vectors of each node to learn a classifier or regressor on graph domain. Due to the success in image processing, convolutional-baser neural networks have become one of the main architectures (ConvGNN) applied to graph processing. The typical structure of a ConvGNN comprises a first part of processing where convolutional layers are used in order to learn representation h. E Rm for each vertex v E V. These representations are then combined to get representation of the whole graph, so that standard feed-forward (deep) neural network can be used to process it. Convolutional layers are important since they define how the (local) topological information is mixed with the information attached to involved nodes, and what is the information to pass over to the subsequent computational layers. Because of that, several convolution operators
for graphs have recently been proposed (Defterrard et al. 2016 Kipf & Welling 2017 2019 Xu et al. 2019).
Morris et al.
The first definition of neural network for graphs has been proposed by Sperduti & Starita (9977 MMore recently, [ichelli (2009) proposed the Neural Network for Graphs (NN4G), exploiting an idea that has been re-bbanded later as graph convolution, and (Sarselli et al. (2008) defined a recurrent neural network for graphs.In In the last few years, several models inspired by the graph convolution have been proposed. Many recent works defining graph convolutional networks (GCNs) extend the NN4G formulation (Micheli (209). for instance the Graph Convolutional Network (GCN) (Kipf & Welling, 2017 is based on a linear first-order filter based on the normalized graph Laplacian for each graph convolutional layer in neural network. SGC (Wu et al. 2019) proposes a fast way to compute the result of several linearly stacked GCNs. Note that SGC considers just the GCN convolution, while our proposed PGC is more expressive than any number of linearly stacked graph convolutions among the ones presented in Section 3.1 of the main paper. DGCNN (Zhang et al. 2018) adopts a graph convolution very similar GCN (Kipf & Welling 2017) (a slightly different propagation scheme for vertices' representations is defined, based on the random-walk graph Laplacian). While GCN is focused on node classification, DGCNN is suited for graph classification since incorporates the readout.
A more straightforward approach in defining convolutions on graphs is PATCHY-SAN (PSCN) (Niepert et al., 2016). This approach is inspired by how convolutions are defined over images. It consists in selecting a fixed number of vertices from each graph and exploiting a canonical ordering on graph vertices. For each vertex, it defines a fixed-size neighborhood, exploiting the same vertex ordering. requires the vertices of each input graph to be canonical ordering, which is as complex as the graph isomorphism problem (no polynomial-tima algorithm is known).
Another interesting proposal for the convolution over the node neighborhood is GraphSage Hamilton et al. (2017). which proposes to perform an aggregation over the neighborhoods by using sum, mean or max-pooling operators, and then perform a linear projection in order to update the node representation. In addition to that, the proposed approach exploits a particular neighbors sampling scheme. GIN (Xu et al.) 2019) is an extension of GraphSage that avoids the limitation introduced by using sum, mean max- max-pooling by using more expressive aggregation function on multi-sets. DiffPool (Ying et al. 2018)) is an end-to-end architecture that combines a differentiable graph encoder with its polling mechanism. Indeed, the method learns adaptive pooling strategy to collapse nodes on the basis of a supervised criterion.
The Funnel GCNN (FGCNN) model (Navarin et al. 2020) aims to enhance the gradient propagation using a simple aggregation function and LeakyRel.U activation functions. Hinging on the similarity of the adopted graph convolutional operator, that is the GraphConv, to the way feature space representations by Weisfeiler-Lehmaa (WL) Subtree Kernel (Shervashidze et al.) (01T)) are generated, it introduces loss term for the output of each convolutional layer to guide the network to reconstruct the corresponding explicit WL features. Moreover, the number of filters used at each convolutional layer is based on a measure of the WL kernel complexity.
B EXPRESSIVENESS OF COMMONLY USED GRAPH CONVOLUTIONS
Thanks to the possibility to express commonly used graph convolutions as instances of PGC, and from the discussion in Section 3 of the paper, it is easy to characterize the expressiveness of commonly
12

---

Under review as a conference paper at ICLR 2021
used graph convolutions. In Figure functions which can be implemented by GCN, GIN, GraphConv, Spectral.
we represent the inclusion relationships among the sets of
Spectral
GraphConv
GIN
GCN
Figure I: Expressiveness of commonly used graph convolution operators. Each ellipse represents the of functions that can be implemented by single graph convolution operator.
C PROOFS OF THEOREMS
Theorem 1.
Let consider two linearly stacked PGC layers using the transformation T. The resulting linear Graph Convolutional network can be expressed by a single PGC layer.
Proof. With loss of generality, let the first PGC being of degree ky, while the second stacked PGC of degree 22, i.c.
H (1) X T(A)* X_W(1,
( H T(A)
(
where
w
w
W
i = 1.2.
w(i) (i)
kg
By expanding H
inside H
equation, get:
[[XW(") +... + T(A) X
T(A) 22 ( T(A)* & XW (we)
(X
T(A)*
h xw ki
w(
T(A) XW w
T(A) &o XW 1) (w!")
(13)
Ki
In this case, by defining D1 = kih. D2
{0..., k2). and auxiliary functions F,(,
i 0, hn + k2, defined
F(W()) w(2)=
Σ w(w@) (D) &.t. 21
21
matrix W can be written as
Fo(WO) W (W(W) W
W
FaytK, (W(), W
13

---

Under review as a conference paper at ICLR 2021
and consequently the hidden representation becomes
H [XA)(A) ... ((A) T(A) ((A)))t) X|W,
which is the output of a PGC with & + k2-
Theorem 2. PGC layer with k 2 is more general than two stacked PGC layers with l 1 with the same transformation T and the same number of hidden units m.
Proof. Since all PGCs use the same transformation T, we can focus on the weights only. We prove our theorem providing a counterexample, i.e. we fix m 1. (the input dimension) and show an instantiation of the weight matrix W = [W; WT, W of a PGC layer with k = 2 that cannot be expressed by the composition of two PGC layers with k = (equivalent to GraphConv). consider the simplest case in which Wo. w, W2 E IR, i.e. they are 1 x 1 matrices. Let now Let us also, for the sake of clarity, rename the 1 x matrices of the two PGCs with k- = 1 as: w(1) + a, w t b. w( + w( + d. We get the following system of equations:
us
consider the case where Wi = 5, W = 7, W
0
ab = ad + cb cd = 3
0 = 5/b
a 5/b d 3/c
d = 3/c
(14)
15/cb + eb =
(cb)2 7cb + 15
where assume b and are different from zero (it is easy to that either b 0 would not lead to any solution). If we compute the of the third equation (solving for cb), we get = 449 - 60 = iV, i.e. a complex number. Thus there is no real value for ob that satisfies our system of equations. We thus conclude that there are values that can assign the parameters of the PGCs with k= that would lead to the considered PGC weight matrix.
Moreover, Theorem 2 implies the following corollary.
Corollary 2.1. A linear stack of T -compatible PGC layers with h = 1 is less expressive than a single T-PGC layer with q-
Proof. Since all PGCs use the same transformation T.
focus the weights only. We
prove the corollary by induction. The base case is provided by Theorem 2 Let us now prove the inductive case. Let assume that stack of PGC layers with i 1 (with parameters
..) set 00d) = (WU) E 22xm j o......)) is less expressive than a single PGC layer with =
(with parameters set g W ((++1))xm) and let us prove the
result for i 1. We PGC layers
can consider the set of functions that can be implemented by the stack of with & = 1 the composition of two functions coming from two differrent sets: the first one PGC k=1 = {fl 0(0) s.t. f PGC(" (O(")) is the set of functions that can be computed stack- ing i PGC layers with h 1, and the second one PGC(4) {f)= s.t. f = PGC (())),
is the set of functions computed by a single PGC layer with A = 1. We can then characterize the set of functions PGC(++) as:
PGO (i+1) og f PGC 1 P k.
(1) From Theorem 1, we know that PGC kmi+1 2 (foglff f PCO E PGC km1) J. Since we know
that ( kmt C PGC(()) is more general), we conclude that PGC(1)
k=it1 5 PGC(( L
D DATASETS
We empirically validated the proposed PGC-GNN on five commonly adopted graph classification benchmarks modeling bioinformatics problems: PTC (Helma et al. 2001). NCII (Wale et al. 2008). PROTEINS, (Borgwardt et al. 2005), D&D (Dobson & Doig 2003) and ENZYMES (Borgwardt et al. 2005). The first two of them contains chemical compounds represented by their molecular graph, where each node is labeled with atom type, and the edges represent bonds between them.
14

---

Under review as a conference paper at ICLR 2021
Dataset
#Graphs
#Node
#Edge
Avg #Nodes/Grrap Avg. Avg.#tigges/Graph
PTC
344
4915
10108
14.29
14.69
NCI1
4110
122747
265506
29.87
32.30
PROTEINS
1113
43471
162088
39.06
72.82
D&D
1178
334925
1686092
284.32
715.66
ENZYMES
600
19580
74564
32.63
124.27
COLLAB
5000
372474
24572158
74.50
4914.43
IMDB-B
1000
19773
193062
19.773
193.06
IMDB-M
600
19502
197806
13.00
131.87
Table 3: Datasets statistics.
PTC contains chemical compounds and the task is to predict their carcinogenicity for male rats. In NCII the graphs represent anti-cancer sereens for cell lung cancer. The last three datasets, PROTEINS, D&D and ENZYMES, contain graphs that represent proteins. Each node corresponds to an amino acid and an edge connects two of them if they are less then 6Å apart. particular ENZYMES, differently than the other considered datasets (that model binary classification problems) allows testing the model on multi-class classification over classes. We additionally considered three large social graph datasets: COLLAB, IMDB-B, IMDB-M (Yanardag & Vishwanathan 2015). In COLLAB each graph represents a collaboration network of a corresponding researcher with other researchers from three fields of physics. The task consists in predicting the physics field the researcher belongs to. IMDB-B and IMDB-M are composed graphs derived from actor/actress who played in different movies on IMDB, together with the movie genre information. Each graph has a target that represents the movic genre. IMDB-B models a binary classification task, while IMDB-M contains graphs that belong to three different classes. Differently from the bioinformatics datasets, the nodes contained in the social datasets do not have any associated label. Relevant statistics about the datasets are reported in Table
E PGCN COMPUTATION COMPLEXITY EXAMPLE
Consider a dataset with ng graphs, and the 2-layers GraphConv defined with message passing formulation in equations equation 66 and equation 7 (assuming mi = m2 = =m). Each GraphCom layer requires 3 matrix multiplications. The AX term in the first layer be pre-computed since remains the same over all training. Thus a 2-layer GCN performs 5 ng matrix multiplications in the forward pass for each epoch (generally the size of A different for each graph, but for the sake of discussion we can assume their dimension is comparable). Assuming 100 epochs for training, the total number of such multiplications is then 5 100 nG + 1. we now consider the PGC formulation with & = 2 in eq. equation (that we recall is more expressive than 2 stacked GraphConv layers, as shown in Section D. the number of matrix multiplications required for each graph is 6. However, the terms A.X and A X remain the same, for each graph, during all the training. They can thus be pre-computed and stored memory. With this implementation, eq. equation 9 would require just 3 matrix multiplications, for total number of matrix multiplications for 100 training epochs of 3 100- ng + 3. While this does not modify the asymptotic complexity of PGC compared to message passing, it significantly improves the training times.
F INITIAL NODE EMBEDDINGS
Some datasets that we used in the experiments, encode node labels (i.c., X) by using one-hot encoding. That makes the nodes representations very sparse. preliminary experiments, we observed that such sparse representations negatively influence learning. In Table 4 we show how the use of a sparse node representation as input leads to have sparse input matrices X, A.,...,,A A Specifically, in order to estimate the difference in terms of the sparsity degree with or without an initial PGC layer with lo = 1, we computed the average ratio between the number null entries (we round all the embedding values to the 4th decimal digit) and the total number of entries of the input matrices on the whole dataset for all the used bioinformatics datasets. We evaluated the sparsity of each PCG-layer block, considering the values of k in the interval [0,...,5). It is interesting notice
15

---

Under review as a conference paper at ICLR 2021
input
PTC
NCI1
PROTEINS
D&D
ENZYMES
X
0.94
0.97
0.67
0.99
0.26
P
0
0
AX
0.98
0.96
0.45
0.95
0.13
PPGCk=1 (X)
0
3.67
10
9.28 10
0
1.87 10 3
A²X
0.90
0.95
0.38
0.89
0.11
A PG (X)
3.67 10
9.28 10
1.87 10
A
0.89
0.95
0.36
0.86
0.10
A PGCK-1 (X)
0
3.67
10-3
9.28 10
2.39 10
1.87 10
A-X
0.88
0.94
0.35
0.87
0.10
A PGCK=1(X)
0
3.67
10-3
9.28 10
0
1.87 - 10-3
A
0.8
0.94
0.35
0.81
0.10
A PGC (X)
3.67
10
9.28
10
1.71
10 -8
1.87 10
Table 4: Average ratio of the number of null entries over the total number of entries in the input components up l without (top row) and with (bottom) the PGCk= layer for the used datasets. Note that the value corresponds to dense matrix, while the value I to a null matrix.
that in all datasets the use of the initial PGC leads to a sparsity ratio near (therefore the subsequent PGC-layer has in input dense embeddings). That is very useful, in particular for datasets like NCI1, PTC, and D&D, where the percentage of zeros in the labels representation is near 90%.
G PGCN IMPLEMENTE IMPLEMENTATION DETAILS
We implemented the PGCN in PyTorch- Geomm--Ge (Fey & Lenssen 2019). To reduce the covariate shift during training and to attenuate overfitting, we applied batch normalization and dropout on the output of each yj layer. We used the Negative Log Likelihood loss, the Adam optimizer (Kingma & Ba 2014), and the identity function for TT For more details please check the publicly available code For our experiments, we adopted types of machines, respectively equipped with:
2 x Intel(R) Xeon(R) CPU ES- E5-2630L v3, 192GB of RAM and a Nvidia Tesla V100;
2 x Intel(R) Xeon(R) CPU ES-2650 v3, 160 GB of RAM and Nvidia T4.
H SPEED OF CONVERGENCE
Here, we discuss the results in terms of computation demand between proposed PGCN and FGCNN Navarii et al. 2020). We decided to compare these two models since they present similar readout layer, therefore the comparison best highlights how the different methodology manage the number of considered k-hops, from the point of view of performance. In Table we report the average time (over the ten folds) to perform a single epoch of training and perform the classification with both method. In the evaluation we considered similar architectures using layers for the FGCNN and == 3 for PGCN. The other parameters in both models, to ensure fair comparison. The batch sizes used for this evaluation are the same selected by the PGCN model selection. The results show a significant advantage in using a PCG layer instead of the message passing based method exploited by FCGNN.
were set with the aim to get almost the same number of
Concerning the speed of convergence of the two models, in Figure 2 we report the training curves for two representative datasets (D&D and NCT). In the x-axis report the computational time in seconds, while in the y-axis we report the loss value. Both curves end after 200 training epochs. From the curves it can be seen that PGCN converges faster or with a similar pace than FCGNN.
omitted for double-blind review.
16

---

Under review as a conference paper at ICLR 2021
Train
Classification
Dataset
Model
PGCN
FGCNN
PGCN
FGCNN
D&D
0.718#0.098
0.975=0.146
0.054+0.011
0.055=0.006
ENZYMES
0.164+0.015 0.247=0.032
0.011#0.001 0.016#0.002
NCII
0.813+0.119 1.568=0.263
0.052+0.005 0.089=0.011
PROTEINS
0.296=0.033
0.456=0.0599
0.024+0.003
0.027=0.004
PTC
0.084+0.009
0.139
0.006+0.002
0.009=0.003
COLLAB
1.507+0.175 2.048=0.378
0.137=0.014 0.109=0.014
IMDB-B
0.223+0.024
0.373=0.054
0.018#0.003 0.027=0.004 0.022+0.003 0.034=0.005
IMDB-M
0.326#0.044
0.554=0.087
Table 5: Time in second to perform single training epoch (2nd and 3rd column) and to perform
classification (4th and 5th column), using PGCN and FGCNN (Navarin al. 2020), respectively.
D&D
NCI-1
ROON
FOON
PGZN
5.0200
PGON
9.035
0.0155
3.000
0.0100
8.020
3.015
0.0375
0.0250
8.005
25
130
375
350
200
Figure 2: PGCN and FGCNN training curves for D&D and NCI-1 datasets.
I HYPER-PARAMETERS SELECTION
Due the high computational time required to perform extensive grid search, we decided limit the number of values taken into account for each hyper-parameter, by performing preliminary tests to identify useful ranges of values.
The
of the model (number of hidden units, learning rate, weight decay, k) were selected by using limited grid search, where the explored sets of values do change based on the considered dataset. Due to the high time requirements of performing an extensive grid search, we decided to limit the number of values taken into account for each hyper-parameet by performing some preliminary tests. tests. Prelimirll tests showed that for the social network datasets, it is more convenient to use the Laplacian as T(A). This behavior could be due to lack of label associated to nodes. In Table 6 we report the sets of hyper-parameters values used for model selection via grid search. As evaluation measure, we used the average accuracy computed over the 10-fold cross- validation the validation sets, and used the same set of selected paprr-parameters for each fold. For what concerns the selection of the epoch, it was performed for each fold independently based on the accuracy value the validation set.
17

---

Under review as a conference paper at ICLR 2021
Dataset/k
m
learning rate
weight decay
|drop out batch size.
readoot((Hlaeers (dims))
PTC
15, 30, 60
10 5- 10
5- 10
55 10
0.4,0.6
16, 16,32
3, 5,
[m/2]. ml
NCII
50, 100
10"
9,5 5. 10
5- 10
9.5 1.5-10 10
0|0.3,055|
16,32
3,4,5,
[m//2], [m ml
PROTEINS
25,50 50
10 9,5 10
4, 10
45 10
0..3.0.5|
16,32
3,4,5,6
[m/2]. 2 [m ml
D&D
50, 75
101100",,00 1.5 10-9
9.510..001100 5. 10
10.-1000000000 0.3.
16,32
3,4,5,
1 [m/ 22. [m m)]
ENZYMES
50, 100
10 1013,10-4 10
5
1.-10 10110111 0.3,0055
16, 32
3,4,5, 6| 1 m2/ [m mm]
COLLAB
7, 15,30
10 10- 10-1""100" 10-4
5--009.5- 10-1
0,0.5
16,32
3,9.7.9
1
[m/2], /2. 2 [m ml]
IMDB-B
50, 75
10
10
5- 4.5 10
0,0.5
16,32
3.5, 7.9
[m/ [m 2, mm]
IMDB-M
50, 76, 100
10
5 10-5
5 1--10-,5, 10
0,0.5
16,32
3,5, 7, 9.
1 [m/2]. [m
Table 6: Sets of hyper-parameters values used for model selection via grid search.
Model
Dataset
PTC
NCII
PROTEINS D&D ENZYMES COLLAB IMDB-B IMDB-M
GIN Xu et al. 2019
64.6
82.7
76.2
80.2
75.1
52.3
+7.0
=1.7
+2.8
#1.9
#5.1
+2.8
GFN Chen al.
2019
82.77
76.46
78.78
70.17
81.50
73.00
51.80
+1.49
+4.06
+3.49
+5.58
+2.42
+4.35
+5.16
GCN Chen et al.
2019
83.65
75.65
79.12
69.50
81.72
73.30
51.20
11.69
13.24
13.00
17.37
11.64
45.29
15.13
DIFFPOOL Ying et
2018
76.25
80.64
62.53
75.48
PGCN
74.0
84.40
79.20
82.54
78.17
76,96
77.88
52.97
+2.81
40.14
-0.81
+1.09
10.68
#2.14
#3.11
42.67
Table 7: PGCN accuracy comparison using different values of k. The validation policy is the same used Xu al. (2019; Chen al. (2019): not reported.
Ying et al. (2018). In Ying al. (2018) the variance is
J EXPERIMENTAL RESULTS OMITTED IN THE RESULTS COMPARISON
As validation test methodology we decided to follow the method proposed in Errica et al. 2020). that in our opinion, turns out be the fairest. For this reason, some results reported in the literature cannot be directly compared with the ones that we obtained.
Specifically, the results reported in Xu et al. (2019); Chen al. 2019); Ying al. (0088) are not considered in our experimental comparison since the model selection strategy is different from the one we adopted. Indeed the results reported r cannot compared with the other results reported in Table 1 of the paper, because the authors state "The hyper-purameters
tune for euch dataset are [...] the number of epochs, i.e., a single epoch with the best cross validation accuracy averaged over the 10 folds was selected.". Similarly, for the result reported in Chen et al. (2019) for the GCN and the GFN models, the authors state "We run the model for 100 epochs, and select the epoch in the same way Xu al. (2019), i.e., single epoch with the best cross-validation accuracy averaged over the 10 folds is selected". In both cases, the model selection strategy is clearly biased and different from the one we adopted. This makes the results not comparable.
Moreover, in Xu et al. (2019) the node descriptors are augmented with structural features. In GIN experiments the authors add a one-hot representation of the node degree. We decided use a common setting for the chemical domain, where the nodes are labeled with a one-hot encoding of their atom type. The only exception ENZYMES, where common to use 18 additional available features. Also in Ying et (2018) there is similar problem since the authors add the degree and the clustering coefficient to each node feature vector. For the sake of completeness in Table 7 we report the results obtained by the proposed method following the same validation policy used in Xu et al. (2019); Chen jct al. (2019); Ying et al. (2018). The table shows that the PGCN outperforms the methods proposed in the literature in almost all datasets.
18


Reviews:
[{"review_id": "wfX447KggK", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "##########################################################################\n\nSummary:\n\nThis work proposes the Polynomial Graph Convolutional Networks (PGCNs), which is built upon the Polynomial Graph Convolution (PGC). The PGC is able to aggregate k-hop information in a single layer and comes with the hyper-parameter k. The PGCNs are composed of a PGC with k=1, followed by a PGC with a chosen k (usually > 1), and a complex readout layer using avg, max, and sum over all nodes. Theoretically, the proposed PGC has two major benefits as claimed: 1) Common graph convolution operators can be represented as special cases of the PGC; 2) A PGC with k = q (q > 1) is more expressive than linearly stacked q PGCs with k=1. The PGCNs are thus more general, expressive, and efficient than existing GNNs. Experimental studies are conducted on common graph classification benchmarks, showing the improved performances of the PGCNs.\n\n##########################################################################\n\nReasons for score:\n\nOverall, I vote for rejection. My major concerns lie in three aspects, as detailed in Cons below: 1) Some statements to motivate this work are not well explained and supported. 2) The proposed idea seems quite similar to several previous studies; 3) The experimental studies are not convincing to me in order to show the effectiveness of the proposed PGC.\n\n##########################################################################\n\nPros:\n\n1. The presentation is good and the proposed method is clearly described. I like the theoretical analysis in 3.2, which explains clearly how to build PGCNs with PGC.\n\n2. This paper targets at two interesting problems in the literature: 1) designing more powerful graph convolution operator; 2) building GNNs with similar power as deeper GNNs. The deeper version of existing GNNs is usually not powerful as expected. As a result, building GNNs to achieve the expected power is an important topic.\n\n3. The experimental details are provided in the appendix.\n\n##########################################################################\n\nCons:\n\n1. Some statements to motivate this work are not well explained and supported. In particular, in the abstract and section 1, the authors indicate that interactions among non-linearly stacked graph convolution (GC) parameters at different levels pose a bias on the flow of topological information. This statement is not well explained and supported with analysis or experimental results.\n\n2. The proposed idea seems quite similar to several previous studies. The proposed PGC is quite similar (or equivalent, with minor differences) to concatenating outputs of linearly stacked GCs and then going through a linear transformation. First, such concatenation is proposed in [1]. Second, linearly stacking GCs, or equivalently using a polynomial powers of the adjacency matrix A (possibly with some transformations), is studies in multiple studies like [2,3,4]. I didn't capture the key differences between this work and these previous studies. Only [2] is discussed in the appendix. [4] is mentioned in the experiments, but no discussion in terms of method differences is provided.\n\n[1] Xu et al. \"Representation Learning on Graphs with Jumping Knowledge Networks\", ICML 2018\n\n[2] Wu et al. \"Simplifying Graph Convolutional Networks\", ICML 2019\n\n[3] Liu et al. \"Towards Deeper Graph Neural Networks\", KDD 2020\n\n[4] Chen et al. \"Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification\", ICLR 2019 RLGM workshop\n\n3. The experimental studies are not convincing to me in order to show the effectiveness of the proposed PGC. As mentioned in Summary, the PGCNs use a quite complex readout layer, which is different from all the GNNs in comparison. Ablation studies on this readout layer should be provided in order to show that the improvement is indeed from the PGC.\n\n##########################################################################\n\nQuestions during rebuttal period: \n\nPlease address and clarify the cons above \n\n\n##########################################################################\n\nComments after the rebuttal period: \n\nI will keep my score. The authors' responses addresses my first concern. However, the differences from previous studies are still not significant to me. In addition, no matter the authors claim the proposal of a complete architecture or a new operator, ablation studies are necessary to backup the designing of each part.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "srTgOEkK8YW", "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": "Summary: The paper proposes Polynomial Graph Convolution (PGC), which enjoys a larger-than-one-hop receptive field within a single layer. This is done by first propagating information with a fixed (not learned) propagation matrix (e.g. adjacency matrix or graph Laplacian), and then projecting the information from different topological distances with a learned linear layer. PGC is shown to be theoretically more expressive than linearly stacking simple graph convolutions; experiments on several graph classification tasks show good performance.\n\nRecommendation: Overall, I am slightly leaning to reject. The paper is interesting, but the theoretical contribution is rather straight-forward, and to warrant acceptance I would look for strong empirical performance together with an analysis of what is contributing to the gains. While some of the gains PGCN obtains look promising, others do not seem statistically significant; some results and baselines from related works are not compared against, and the effect of a strong node aggregation scheme is not discussed. Finally, it is unclear if the proposed method can be generalized to use edge types.\n\nMain pros:\n1. The paper is clear and easy to understand; even relatively small claims are backed up by proofs.\n2. The relationship between linearly stacking k GraphConvs and using a single k-PGC layer is cleanly explained and motivates the work well. Decoupling receptive field size from network depth is a natural goal.\n3. I appreciate the authors taking care to fairly evaluate their PGCN following [1]. This is crucial as many GNN works are iterating on metrics computed on the evaluation set despite it being available to the model selection procedure; as noted by authors, this includes the GIN results from [2].\n\nMain cons:\n1. I have several concerns about the results (Table 1):\n- Best mean performance is bolded, but many of the gains (esp. PTC, PROTEINS, IMDB-B, IMDB-M) seem within noise levels due to high variance. Instead of saying \"PGCN shows a slight improvement\", it would be better to perform a statistical significance test, and clearly mark which improvements are significant (by bolding several joint-top values).\n- Many results are taken from [1], but simple baselines of [1] that do not consider graph structure are omitted. These baselines outperform all GNNs in [1] for some benchmarks, e.g. getting 78.4 for D&D and 65.2 for ENZYMES (which is between the results of the best baseline and PGCN); to get a full picture these baselines should be included.\n- [1] also shows that adding simple node features can make a big difference for IMDB-B and IMDB-M; for example, adding node degree features improves GIN on IMDB-B from 66.8 to 71.2. While PGCN is not using node degree features, for IMDB it's using the Graph Laplacian as T(A) (Appendix H), which implicitly encodes some degree information. As [1] already has results with node degree features included, it would be nice to see how PGCN compares.\n- PGCN uses a powerful node aggregation scheme (Page 6). What aggregation methods are used in the baselines? What is the contribution of using this stronger aggregation scheme instead of a more standard weighted sum?\n2. Section 3.3 and Appendix E mention that PGCN can be more efficient to train than standard GNNs because the propagation (i.e. multiplying node features by powers of T(A)) can be computed once. This only applies to the very first PGCN layer, and as authors state, before using a non-trivial (k > 1) PGC layer, one would typically use either 1-PGC (as done in the paper) or a learned linear projection, in order to avoid propagating highly sparse raw node features. It's therefore unclear if this training speedup can be really obtained in practice without sacrificing accuracy; one could use a random (not learned) linear projection as the initial \"densification\", but it's hard to say if that would work. Either way, if this speedup can really be obtained, it would be good to see supporting results (preferably on a large dataset where training time is indeed an issue).\n3. Can PGC take edge types into account? I understand some of the benchmark datasets contain molecules, and thus have typed edges (single, double, triple); was that information utilized by PGCN? Considering edge types is straight-forward for GNNs that only perform a single learned propagation step, since the propagation matrix can be selected based on the edge type; it's unclear what to do for PGC which uses a fixed propagation matrix.\n\nOther comments:\n- The abstract and introduction say \"interactions among GC parameters at different levels pose a bias on the flow of topological information\". I'm assuming this refers to entanglement of weights as in Equation 8, but when reading the intro this got me confused, since there was no reference, and the claim did not seem obvious.\n- Propagation in PGCN does not use any non-linearity or normalization, so it seems values can grow exponentially with k, especially on dense graphs. Was this observed to be a problem?\n- \"GraphConv is more expressive than GCN and GIN\" - this is not fully true, since GCN as defined in the paper uses the Laplacian instead of the adjacency matrix.\n- The analysis shows the relation between PGC and linearly stacking GraphConv's, but in practice one wouldn't linearly stack them, and rather use non-linearities in between. Can anything be said in that case?\n- \"they (...) consider shortest paths, (...) that choice limits significantly the expressiveness\" - I'm not fully convinced: PGC cannot be stronger than the WL test, while using shortest path information allows to exceed that (since it makes it possible to tell apart two disconnected cycles from a single larger cycle).\n- The paper compares only against GraphConv-like layers; it would be interesting to compare (empirically) to a larger class of GNNs, such as GAT [3], GGNN [4] or GNN-FiLM [5].\n\nTypos and small formatting issues (did not influence my rating recommendation):\n- Page 1: \"faces the problem\" -> \"addresses the problem\"\n- Page 1: \"being able to\" -> \"by being able to\"\n- Page 3: \"start showing\" -> \"start by showing\"\n- Page 6: In equation for y_j, I believe j should start with 1\n- Pages 6 & 14: \"PCG\" -> \"PGC\"\n\n\nReferences:\n- [1] A Fair Comparison of Graph Neural Networks for Graph Classification\n- [2] How Powerful are Graph Neural Networks?\n- [3] Graph Attention Networks\n- [4] Gated Graph Sequence Neural Networks\n- [5] GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulation\n\n----------------------------------------------------------------------------------------------------\n\nComments after rebuttal:\n\nI have reviewed the response from the authors, and I decided to keep my score. Although the paper is certainly interesting, for ICLR it is borderline. While I agree that many works in the literature choose to treat their network as a monolithic architecture, and thus do not explore the effects of different components, I would still encourage the authors to add an ablation of the readout method, as that would help assess the interaction between that and the choice of the graph propagation scheme.", "extra_scores": {}, "extra_text": {}}, {"review_id": "pzMAoE468Lb", "reviewer": "AnonReviewer3", "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": "The article presents a novel framework for Graph Convolutional Neural Networks (GCNs). The method called  Polynomial Graph Convolution (PGC) is based on concatenating the powers of a transformed adjacent matrix in a given layer. The paper shows that various popular variants of GNNs can be expressed using the PGC framework.  Theoretical results presented show that PGC with higher degree is more expressive that deeper std. GNNs. Numerical results are presented on graph classification task that illustrate the performance of the method.\n\n--------------\nStrengths:\n1. Paper presents a novel framework.\n2. Numerical results look promising.\n3. The method presents a more expressive method.\n\n--------------\nWeakness:\n1. Novelty seems limited.\n2. Node and edge task experiments are missing.\n3. Certain claims need to be substantiated.\n\n--------------\nDetails:\nI have the following comments:\n1. Novelty seems limited. It is unclear how the proposed method/framework is different from the Krylov subspace based work of (Luan et al. 2019) and also the Chebyshev polynomials approach of (Defferrard et al., 2016). Both these methods boil down to considering powers (polynomials) of the Laplacian, i.e., different topological distances in the model. Authors should clarify the key differences.\n\n2. Experimental results section can be enhanced. Currently, the paper  considers only the graph classification task, where only global information suffices. GCN are more interesting in local, graph level tasks, in particular for prediction tasks on nodes and edges, e.g., link prediction, node and edge classification. It is unclear why these tasks were not considered. Moreover, methods of  (Kipf and Welling, 2016), (Luan et al. 2019) and (Defferrard et al., 2016), that are most relevant to this work are not considered for experimental comparisons.\n\n3. The claim in Theorem 2, that PGC with k =2 is more expressive than two stacked PGC with k = 1, is du to that fact that the former has number of parameters higher than the latter. Is this correct? (Due to the structure of weight matrix W)\n\n4.  There are few statements that need to be substantiated and explained. E.g.,\n(a) It is claimed there is a bias in deeper GCNs, but no explanation is given.\n(b) Similarly, PGC being more expressive (for the asme number of parameters) needs to be explained.", "extra_scores": {}, "extra_text": {}}, {"review_id": "IAFCJs-8yST", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the current graph convolution and proposes a novel polynomial graph convolutional network (PGCN). Under the framework of PGCN, several other graph convolutions can be seen as a special case.\n\nQuality:\nThe paper is technically sound and maintains a high presentation quality. \n\nClarity:\nThe mathematical proof is clear and the whole paper is easy to follow.\n\nOriginality:\nThe paper is somewhat original but the proposed PGCN still lacks generalization, which will be pointed out in the following part.\n\nSignificance:\nThe significance is not very prominent.\n\n\nPros: \n1. The paper proposes a novel graph convolution named with PGCN. Under the framework of PGCN, several other graph convolutions can be regarded as a special case. \n2. The whole paper is described clearly and easy to follow.\n\n\nCons:\n1. The core idea of PGCN mainly relies on the exponential power of different order applying on adjacent matrix A. It is easy to prove that by exponentiating the adjacency matrix to the K-th power, the node's receptive field can be extended to the K-th nearest neighboring nodes. However, this approach has been successfully adopted in different articles, as a result, the proposed PGCN is of limited originality without further analysis, either in theoretical aspect or technical aspect.\n2. The mathematical proof in section 3.1 and section 3.2 shows that the stronger expressive ability comes from the less constraints of learnable parameters W. However, reducing the constraints may lead to the training process  more difficult than other graph convolution. To dispel this concern, the author needs to provide more detailed experimental results, especially the training convergence curves of different graph convolutions.\n3. In terms of efficiency, the K-th order exponential method in equation (1) can improve the nodes' receptive field but brings heavy computational burden. In Table 3, All the evaluated dataset has a limited number of nodes in each graph. The maximum average number is 284.32 while the minimum average number is 13.00. The generalization of PGCN on large scale graph remains a serious concern. In Appendix E, the author has also noticed the computing efficiency and adopted a pre-computing strategy, which means the proposed PGCN is not an out-of-box model. In a word, although the proposed model shows stronger expression ability, the generalization and efficiency still remains a big concern.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All four reviewers expressed significant concerns on this submission during review. None of them is willing to change their evaluations and supports this work during discussions. Thus a reject is recommended.
Decision: Reject