Learning Parametrised Graph Shift Operators
Authors: George Dasoulas
Johannes F. Lutzeyer
Michalis Vazirgiannis
Venue: ICLR 2021 Poster (2021)
Keywords: graph neural networks
graph shift operators
graph classification
node classification
graph representation learning

Abstract: In many domains data is currently represented as graphs and therefore, the graph representation of this data becomes increasingly important in machine learning. Network data is, implicitly or explicitly, always represented using a graph shift operator (GSO) with the most common choices being the adjacency, Laplacian matrices and their normalisations. In this paper, a novel parametrised GSO (PGSO) is proposed, where specific parameter values result in the most commonly used GSOs and message-passing operators in graph neural network (GNN) frameworks. The PGSO is suggested as a replacement of the standard GSOs that are used in state-of-the-art GNN architectures and the optimisation of the PGSO parameters is seamlessly included in the model training. It is proved that the PGSO has real eigenvalues and a set of real eigenvectors independent of the parameter values and spectral bounds on the PGSO are derived. PGSO parameters are shown to adapt to the sparsity of the graph structure in a study on stochastic blockmodel networks, where they are found to automatically replicate the GSO regularisation found in the literature. On several real-world datasets the accuracy of state-of-the-art GNN architectures is improved by the inclusion of the PGSO in both node- and graph-classification tasks. 

Published as a conference paper at ICLR 2021
LEARNING PARAMETRISED GRAPH SHIFT OPERATORS
George Dasoulas* 122 Johannes F. Lutzeyer*1 & Michalis Vazirgiannis'
DaSciM, LIX, École Polytechnique, Institute Polytechnique de Paris, France
2 Noah's 's Ark Lab, Huawei Technologies France
dasoulas, johannes. hut.eeyerr/pollyteechlle....e
beteirg@lix..olyeehheee
ABSTRACT
In many domains data is currently represented as graphs and therefore, the graph representation of this data becomes increasingly important in machine learning. Network data is, implicitly or explicitly, always represented using graph shift op- erator (GSO) with the most common choices being the adjacency, Laplacian ma- trices and their normalisations. In this paper, a novel parametrised GSO (PGSO) is proposed, where specific parameter values result in the most commonly used GSOs and message-passingg operators in graph neural network (GNN) frame- works. The PGSO is suggested as a replacement of the standard GSOs that are used in state-of-the-ar GNN architectures and the optimisation of the PGSO pa- rameters is seamlessly included in the model training. It is proved that the PGSO has real eigenvalues and set of real eigenvectors independent of the parameter values and spectral bounds on the PGSO are derived. PGSO parameters are shown to adapt to the sparsity the graph structure in a study on stochastic blockmodel networks, where they are found to automatically replicate the GSO regularisation found the literature. On several real-world datasets the accuracy of state-of- the- art GNN architectures is improved by the inclusion of the PGSO in both node- and graph-classfficttion tasks.
INTRODUCTION
Real-world data and applications often involve significant structural complexity and as a conse- quence graph representation learning attracts great research interest (Hamilton et al.] [017b] Wu al. 2020). The topology of the observations plays a central role when performing machine learn- ing tasks on graph structured data. A variety of supervised, semi-supervised or unsupervised graph learning algorithms employ different forms of operators that encode the topology of these observa- tions. The most commonly used operators are the adjacency matrix, the Laplacian matrix and their normalised variants. All of these matrices belong to a general set of linear operators, the Graph Shift Operators (GSOs) (Sandryhaila & Moura 2013 Mateos et al. 2019).
Graph Neural Networks (GNNs), the main application domain in this paper, are representative cases of algorithms that use chosen GSOs to encode the graph structure, i.c., to encode neighbourhoods used in the aggregation operators. Several GNN models (Kipf & Welling, 2017: Hamilton et al. 2017a Xu et al.) 2019) choose different variants of normalised adjacency matrices GSOs. In- terestingly, in a variety of tasks and datasets, the incorporation of explicit structural information of neighbourhoods into the model is found improve results (Pei et al.! 2020 Zhang Chen 2018 You et al. 2019), leading us to conclude that the chosen GSO is not entirely capturing the informa- tion of the data topology. In most of these approaches, the GSO is chosen without an analysis of the impact of this choice of representation. From this observation arise our two research questions.
Question 1: Is there single optimal representation to encode graph structures or the optimal representation task- and data-dependent?
On different tasks and datasets, the choice between the different representations encoded by the different graph shift operator matrices has shown to be consequential decision. Due to the past
"Equal contribution.

---

Published as a conference paper at ICLR 2021
successful approaches that use different GSOs for different tasks and datasets, it is natural to assume that there is no single optimal representation for all scenarios. Finding an optimal representation of network data could contribute positively to range of learning tasks such as node and graph classification or community detection. Fundamental to this search is an answer to Question 1. In addition, we pose the following second research question.
Question 2: Can we learn such an optimal representation to encode graph structure in a numerically stable and computationally efficient way?
The utilisation of a GSO as a topology representation is currently hand-engineered choice of nor- malised variants of the adjacency matrix. Thus, the learnable representation of node interactions is transferred into either convolutional filters (Kipf & Welling] 2017; Hamilton et al. 2017a) or attention weights (Veličković al.] 2018), keeping the used GSO constant. In this work, we sug- gest parametrisation of the GSO. Specific parameter values in our proposed parametrised (and differentiable) GSO result in the most commonly used GSOs, namely the adjacency, unnormalised Laplacian and both normalised Laplacian matrices, and GNN aggregation functions, e.g., the aver- aging and summation message passing operations. The beauty of this innovation is that it can be seamlessly included in both message passing and convolutional GNN architectures. Optimising the operator parameters will allow us to find answers to our two research questions.
The remainder of this paper is organised as follows. In Section 2 we give overview of related work in the literature. Then in Section 3 we define our parametrised graph shift operator (PGSO) and discuss how it can be incorporated into many state-of-the-art GNN architectures. This is fol- lowed by a spectral analysis of our PGSO in Section [4] where we observe good numerical stability in practice. In Section we analyse the performance of GNN architectures augmented by the PGSO in a node classification task on a set of stochastic blockmodel graphs with varying sparsity and on learning tasks performed on several real-world datasets.
2 RELATED WORK
GSOs emerge in different research fields such as in physics, network science, computer science and mathematics, taking usually the form of either graph Laplacian normalisations or variants of the adjacency matrix. In an abundant number of machine learning applications the expressivity of GSOs is exploited, e.g., in unsupervised learning (von Luxburg, 2007: Kim et al., 2008), semi- supervised node classification on graph-structured data (Kipf & Welling, 2017 |Schlichtkrull et al.) 2018] and supervised learning on computer vision tasks (Chang & Yeung, 2006). The majority of these works assumes a specified normalised version of the Laplacian that encodes the structural information of the problem and usually these versions differ depending on the analysed dataset and the end-user task. Recently, new findings on the impact of the chosen Laplacian representation have emerged that highlight the contribution of Laplacian regularisation (Dall' Amico et al. 2020 Saade et al. 2014]] Dall' Amico et al. 2019). The different GSO choices in different tasks indicate data-dependent relation between the structure of the data and its optimal GSO representation. This observation motivates to investigate how beneficial a well-chosen GSO can be for learning task on structured data.
GNNs use a variety of GSOs to encode neighbourhood topologies, either normalisations of the adja- cency matrix (Xu et al. 2019 Hamilton et al.) (2017a) or normalisations of the graph Laplacian (Kipf) & Welling 2017; Wu et al. 2019). Due to the efficiecyy and the predictive performance of GNNs, a research interest has recently emerged in their expressive power. One of the examined aspects is that of the equivalence of the GNNs' expressive power with that of the Weisfeiler-Lehmanl graph isomorphism test (Dasoulas et al., 2020; Maron et al.) 2019 Morris et al. 2019 Xu et al.) 2019). Another research direction is that of analysing the depth and the width of GNNs, moving one step forward to the design of deep GNNs (Loukas) 2020 Li et al. 2018 Liu et al. 2020; Alon & Yahav) 2020). In this analysis, the authors study phenomena of Laplacian oversmoothing and combinatorial oversquashing, that harm the expressiveness of GNNs. In most of these approaches, however, the used GSO is fixed without a motivation of the choice. We hope that the parametrised GSO that is presented in this work can contribute positively to the expressivity analysis of GNNs.
We will now delineate our approach and that of closely related work by Kliepera et al. (2019). Klicpera et al. (2019) demonstrate that varying the choice of the GSO in the message passing step
2

---

Published as a conference paper at ICLR 2021
of GNNs can lead to significant performance gains. In Klicpera al. (2019) two fixed diffusion operators with a much larger receptive field than the h-hop neighbourhood convolutions, are inserted into the architectures, leading significant improvement of the GNNs' performance. In our work here we replace the GSOs in GNN frameworks with the PGSO, which has a receptive field equal to the 1-hop neighbourhood of the nodes. We find that parameter values of our PGSO can be trained in a numerically stable fashion, which allows us to chose a parametric form unifying the most common GSOs and aggregation functions. As with standard GNN architectures the receptive field of the convolutions is increased in our architectures by stacking additional layers. Klicpera et al. (2019) increase the size of the receptive field and keep the neighbourhood representation fixed, while we keep the size of the receptive field fixed and learn the neighbourhood representation.
3 PARAMETRISED GRAPH SHIFT OPERATORS
We define notation and fundamental concepts in Section parametrised graph shift operator S) in Section 3.2 In Section
3.1 and introduce proposed
3.3 we provide a detailed discussion of how (A, can be applied to the message-passing operation in GNNs and we demon- strate use cases of the incorporation of ((A S) in different GNN architectures.
3.1 PRELIMINARIES
Let a graph G be tuple, G= EV, where V and E are the sets of nodes and edges and let [V] n. We assume the graph G to be attributed with attribute matrix X E Raxd, where the 7h row X contains the d-dimensional attribute vector corresponding to node v, We denote the n x n identity matrix by In and the n-dimensional column vector of all ones by 1, Given the node and edge sets, one can define the adjacency matrix, denoted A E [0, 1|=xn, where Aij o 0 if and only if (i, E E, and the degree matrix of as Diag(A1,
Recently the notion of GSO has been defined as a general family of operators which enable the propagation of signals over graph structures (Sandryhaila & Moura 2013; Shuman et al. 2013).
Definition 1. Graph Shift Operator A matrix S R is called Graph Shift Operator (GSO)
if it satisfies Siy = 0 for i + and (i,j) & E (Mateos et al. 2019 Gama et al. 2020).
This general definition includes the adjacency and Laplacian matrices as instances of its class.
Remark 1. According to Definition] [ the existence of an edge (i, E does not imply nonzero entry in the GSO, Sig A 0. Hence, the correspondence between GSO and graph is not bijective in general.
3.2 PARAMETRISED GSO
We begin by defining our parametrised graph shift operator. Definition 2. We define the parametrised graph shift operator (PGSO), denoted by ((A as
7A, m, -m, D.1 + m2 A, + m3ln,
where A. A al, and D. Diag(A,11) is the degree matrix of A.. We denote the parameter tuple corresponding the S) by S = (m1, m2, my, 61, 62, e3, a) consisting of scalar multiplica- tive parameters m1, M2, m3, scalar exponential parameters e1, 62, 63 and additive parameter a.
The main motivation of the parametrised form in Equation used GSOs and indeed we are able to generate a wide range of different graph shift operators by choosing differentt values for the parameter set S. In Table | we give examples of parameter values in (A, S)) which result the most commonly used GSOs and message-passingg operators in GNNs. Unlike the GSO, the PGSO uniquely identifies the graph it corresponds to, i.e., the GSO and PGSO do not share the property discussed in Remark
is to span the space of commonly
Although base the definition of (A, the adjacency matrix, can define the PGSO using other graph representation matrices, such as the non-backe banckttrrakking operator B, > (B,S), (rzakala et al. 2013 Bordenave al. 2015) the diffusion matrix 7), (Klicpera al. 2019)
3

---

Published as a conference paper at ICLR 2021
Table Known Graph Shift Operators as parameter choices S in ((A
(m m2, ma: C1, C2 C3. a)
Operator
Description
Adjacency matrix and Summation Aggregation Operator of GNNs
(0.1,0,0,0,0.0)
A
(1,-1,0,1,0,0,0)
D-A
Unnormalised Laplacian matrix L
Signless Laplacian matrix Q (Cvetković & Simić 2010)
(1,1,0,1,0,0.0)
D+A
(0,-1,1,0,-110,00)
In D
Random-walk Normalised Laplacian Lyw
00.-1,1,0-3
I, - D AD-
Symmetric Normalised Laplacian Leym
Normalised Adjacency matrix of GCNs
001,000,-2,-13
DT A A
2.
Kiipf & Welling 2017)
Mean Aggregation Operator of GNNs
1,0.0,0,-10000
D
(Xu al. 2019)
3.3 SUGGESTED METHOD: GNN-PGSO AND GNN-MPGSO
Next, we formally discuss how (), is incorporated in GNN models. Let a GNN model be denoted by X)) taking as input non-parametrised function of the adjacency matrix ((A)= [o, 1| Raxa and an attribute matrix (in case of an attributed graph) X RRadd Fur- ther, let K denote the number of aggregation layers that M consists of. The Parametrised Graph Shift Operator (PGSO) formulation transforms the GNN model M()(A), X) into the GNN-PGSO model (M,)(A, X). Moreover, we define the GNN-mPGSO model ("(IIK(AA, SiK)), X), where (A, eter tuple& S for l (1,...,KK) K}.
(1,A, St). ".),,..AAAA,, ((, )], i.e., we assign each GNN layer a different param-
Message-passing steps and convolutions In a spectral- based GNN (Wu et al. 2020), where the GSO is explicitly multiplied by the model parameters, it is straightforward replace the GSO with AA, S). However, with some further analysis (A, can also be incorporated in spatial-based GNNs, where the node update equation is defined message-passing step. Here illustrate the required analysis on the sum sum-base based aggregation operator, where we sum the feature vectors h2 Rd in the neighborhood of a given node v,, denoted ((x)). The sum operator of the neighborhood representations can be reexpressed as: E),,) h1 = Σ}= Aihhj. Using this observation we derive the application of S) in a message-passing step to be,
(T(A,S))); mm (Da); h; + m2
E(aa} (Aa)s (Da) E8 h2 + mahi-
(2)
j=1
Examples The following examples highlight the usage of the (A, operator:
1. In the standard GCN (Kipf & Welling 2017) the propagation rule of the node representation
(1)) [nnxd in computation layer /
1 (D (1
where W(() is the trainable weight matrix and a denotes a non-linear activation function. The GCN-PGSO and GCN-mPGSO models, respectively, perform the following propagation rules,
Hl++ = (1(,
and ((++ a
The Graph Isomorphism Network (GIN) (Xu et al. 2019) consists of the following propagation rule for node representation h E Rd of node in the computation layer I,
h (1+1) = o (100
Σ
(o
4

---

Published as a conference paper at ICLR 2021
Using the Equation
(2) the propagation rule is transformed into the GIN-PGSO formulation as,
hg (1+1)_ a (ma (Da),' + ma)h ((() + m2
E 6gh) w
(o
where Eue are edge weights defined as Gq (Da), (Da), Analogously, we can construct the GIN-mPGSO formulation by superscripting every parameter in S by (4).
Computational Cost the PGSO and mPGSO efficiently computable and optimisable. r(A, can be extended by using vector instead of scalar parameters. Although this extension leads to better expressivity, the computational cost is increased, as the number of parameters then depends on the size of the graph.
Since in [ the exponential parameters are applied only to diagonal matrices
4 SPECTRAL ANALYSIS OF (A,
In this section, we study spectral properties of 7(A, in theoretical analysis in Section 4. and through empirical observation in Section 4.2 The obtained theoretical results provide Tounda- tion for further analysis of methodology involving the PGSO and allow an efficient observation of spectral support bounds of commonly used GSOs, that instances of ( (A,
4.1 THEORETICAL ANALYSIS
Here we investigate the spectral properties of our (A, S). Throughout this section we assume that we work on undirected graphs. In Theorem [ we show that (A, has a real spectrum and eigen- vectors independent of the parameters S. In Theorem 2 we study the spectral support of (A, Theorem 1. 7(4, S) has real eigenvalues and set of real eigenvectors.
The proof of Theorem 1 follows directly from noticing that (A, which not symmetric in general, is similar to symmetric matrix and therefore shares eigenvalues with this symmetric matrix (Hor& & Johnson
1985 pp. 45,60); the full proof can be found in Appendix A.
Being able to guarantee real eigenvalues and eigenvectors for all parameter values of (A, enables practitioners to deploy our PGSO in spectral network analysis without having to replace elements of the algorithms which assume a real spectrum. As result of Theorem [ Jigenvallu computations can be stabilised by working with the symmetric, similar PGSO used in the proof of Theorem
Especially the theoretical analysis of the PGSO and algorithms involving the PGSO is aided by The- orem I There are several publications, where the complications and lack of results for complex valued graph spectra are discussed the case of directed graphs (Guo & Mohar 2017 Brualdi 2010 Li et al. 2015). To remain within the real domain independent of the parameter choice (for undirected graphs) enables analysts to access a wide variety of spectral results, which only hold for real symmetric matrices. An example of such a theorem is Cauchy's 's interlacing theorem (Bernstein)
2009 p. 709), which can be used to relate the adjacency matrix spectra of a graph and its subgraphs. Hall et al. (2009) and Porto & Allem (2017) have been able prove interlacing theorems for unnor- malised, signless and normalised Laplacians. The fact that the PGSO has a real spectrum presents a first step extend their work to potentially apply the PGSO independent of the parameter values. However, this is only one example of powerful theoretical result, which relies on a real spectrum and is accessible to our PGSO formulation due to the result shown in Theorem
Now that the spectrum of 7AAS)) has been shown to be real we study the spectral support of (A, S). A common way to prove bounds on the spectral support of a matrix is via direct appli- cation of the Gershgorin Theorem (Bernstein) 2009 p. 293) as done in Theorem 2
Theorem 2. Let C: m. mn(d; a)s1 m2(d; a) mg and R; |ma](d; d a)eztad where de denotes the degree of node v,. Furthermore, we denote eigenvalues of 7(A, S) by X S
d2 S ... < Am. Then, for all j _ (L....,n),
(C: Ra), "E((......) iE().....)
min
(C, R.)
(3)
The proof of Theorem
2 shown in Appendix A.2
5

---

Published as conference paper at ICLR 2021
(a)
10
Spectral bounds
Parameter Valles Ru
0.5
-5-
-10
-0.5
Epachs
Epochs
Figure 1: (a) bounds on the spectral support and (b) parameter values 7(A, S) plotted against the training epochs of GCN-PGSO applied to node classification task on the Cora graph. Note that optimal values of E2 and eg lie close together and hence appear as single line in (b).
Examples For the parametrisation of S) corresponding the adjacency matrix, obtain C = 0 and RG = d;. R; is clearly maximised by the maximum degree and therefore, from (3)
the spectral support of equal [-dmax dmax] as required. Similarly, the spectral supports of
L. Laym and Lyw. can be deduced by plugging in the corresponding parameters into the result in
B). For the operator used the message passing of the GCN (Kipf Welling (017)) Gershgorin bound such the one in Theorem
2 has not been calculated yet as far as we are aware. We obtain
C. ===1/ 1/(d, + 1) and R3 d (d, 1). Therefore, from (3) the spectral support of the Kipf and Welling operator is restricted to lie within [- (-dmax 1)/ [d/[dmaa [dmax +
the lower bound of this interval tends to I as dmax + 0o. So only in the limit is their spectral support symmetric around 0.
The bounds proven in Theorem 2 allow the observation of the spectral bounds for the many GSOs which can be obtained via specitic parameter choices made in our PGSO formulation. the con- text of GNNs such bounds of value since they allow statements about numerical stability and vanishing/explodin gradients to be made. For example in Kipt & Welling (2017) the observation that the spectrum of the symmetric normalised Laplacian is contained in the interval [0, 2] motivated them to make use of the "renormalisation trick" to stabilise their computations. Since the PGSO learned its spectral support varies throughout training. The bounds in Theorem enable us to monitor bounds on the spectral support in numerically efficient manner, avoiding the computation of eigenvalues at each iteration, as showcased in the empirical observation in Section 4.2
Since the majority of the commonly used graph shift operators correspond to specific parametri- sations of (A, the spectral properties of y (A, S) are general themselves, the sense that cannot establish spectral results for (AA, S), which have already been shown to not be present for one of its parametrisations. This generality and lack of specific spectral features, which hold for all parametrisations is precisely one of the strengths of utilising operator to manifest different spectral properties different tasks, when they are of benefit.
since it allows the graph shift
4.2 EMPIRICAL OBSERVATION
In this section, observe bounds on the spectral support, proven in Theorem (Figure ! a)) and optimal parameters (Figure [(b)) of the PGSO incorporated in the GCN during training on node- classification task on the Cora dataset. More details on the task will be provided Section 5.3
Surprisingly, the spectral support of the PGSO remains centered at 0 throughout training in Figure Πaa) without this being enforced by the design the PGSO. Recall that the centre of the spectral support intervals has the following parametric form C = (d; +a) m2,; + a2 + + It nice to observe that this desirable property 2017) is preserved throughout training. We also observe that the spectral bounds smoothly increase throughout training. The increasing support a direct result of the learned PGSO parameters.
"renormalised" operator used by Kipf Welling
As we expected from our analysis of Figure aa), we observe the parameters of the PGSO to be smoothly varying throughout training in Figure [[b.. The parameters Figure Tbb can be seen to have been initialised the values corresponding to the chosen GSO in the GCN and from there they smoothly vary towards new optimal values within the first 40 training epochs, which are then stable throughout the remainder of the training, ruling exploding gradients. It is nice note that

---

Published as a conference paper at ICLR 2021
in Section | Figure 4 (b
observe the accuracy of the GCN using the trained PGSO parameters, displayed in Figure I (b,, to slightly outperform the standard GCN.
EXPERIMENTS
We evaluate the performance the PGSO in a simulation study and on 8 rral-world datasets. In Sec- tion 5.1 we show the ability of (_A, S) to adapt to varying sparsity scenarios through a stochastic blockmodel study, in Section 5.2 we study the sensitivity of the GNN-PGSO's performance dif- ferent (A4, initialisations and in Section 5.3 we evaluate the contribution of PGSO and mPGSO to the GNN performance in real-world datasets.
5.1 SPARSITY INTERPRETATION OF (A,S))
The choice of graph shift operator depends on the structural information of a dataset and on the end task. For example, in graph classification tasks the datasets usually contain small and sparse graphs (Wu al. 2018), while in node classification tasks the graphs are larger and denser. In this section, we highlight the ability of 74, S) to adapt to different sparsity regimes.
Stochastic Blockmodels In order to simulate graphs with varying sparsity levels, utilise the parametrisation of stochastic blockmodel generation. Stochastic blockmodels (SBMss are well- studied generative models for random graphs that tend to contain community, i.c., block, structure (Holland et al. 1983 Karrer& & Newman 2011). Let & be the number of communities, {Ci,..., C be the h disjoint communities and Pty be the probability of edge occuring between a node u E C. and node u E Cj. SBMs offer flexible tool for random graph generation with specific properties, such as the detectability of the community structure (Decelle et al. 2011) and the sparsity level of the graph by choosing appropriate edge probabilities Pij. Here, we focus on restricted stochastic blockmodel parametrisation where the probabilities of an edge occurring between nodes within the same community are all equal to p. i.e., Psi p Vi E {l...., k), and the probabilities of an edge between nodes different communities are all equal to q, i.c., Pij = vi Hi i,j E {l.....)
Dataset and experimentation setup In this experiment, we consider 15 9 parameter combinations (p, q) E {(0.5, 0.25), (0.48, 0.24), ..., (0.22, 0.21),,1),, where by de- creasing the parameters and we increase the sparsity of the sampled networks. For each parameter set we sam- plc 25 graphs with 3 communities containing 200 nodes each. Figure 5 in Appendix B. contains plots of adja- cency matrices sampled from these 15 parameter combi- nations. The learning task performed by a GCN will be to assign community membership labels to each node. For all parameter choices the ratio p/g, i.e., the community detectability, is equal to 2, that the theoretical difficulty the task remains constant across the different sparsity lev- els. As in Dwivedi et al. (2020), all of the nodes have uninformative attributes, except for one node per commu- nity that carries its community membership its node at- tribute. We set the train/vall main/validation/tes splits equal to 80%, 10%, 10% of nodes, respectively, for each community. We use a 3-layer Graph Convolutional Network (Kipf Welling (017)) with hid- den size 64 and with our PGSO incorporated as the message passing operator and initialised to the GCN configuration. We, then, observe the learned parameter values of 7(A, S) after 200 epochs.
Figure
Mean and standard deviation of the PGSO parameters on SBM
Parameter Values Figure shows the average optimal parameter values of (A, found for each one of the 15 node classification datasets. We observe that all parameters remain close to constant the sparsity of the SBM samples increases, except for the additive parameter a, which can observed to clearly increase with increasing sparsity levels. The parameter a in the PGSO parametrisation plays very similar role to the regularisation parameter of the normalised adjacency matrix, which is observed to significantly improve the performance of the spectral clustering algo- rithm in the task of community detection in the challenging sparse in Dall' Amico et al. (2020)
7

---

Published as a conference paper at ICLR 2021
GDV openter
Sonvin Walk
-15
53
Spndhe
100
153
58
Spadhe
106
103
58
Spadte
100
100
56
Epoctt
100
193
5.
Epocte
100
159
Figure 3: Parameter evolution of (A, for 150 epochs, when applied on GCN-PGSO model for the node classification task on Cora.
and Qin & Rohe (2013). It very nice see that the PGSO automatically varies this regularisation parameter, replicating the beneficial regularisation observed in the literature, without this behaviour Figure 2 we can fur-
being incentivised in any way by the model design or the parametrisation. thermore observe that the eg and é3 values closely aligned for all sparsity levels indicating that symmetric normalisation of the adjacency matrix seems to be beneficial in this task.
5.2 SENSITIVITY ANALYSIS OF (A, TO DIFFERENT INITIALISATIONS
In Section we initialised a 3-layer GCN-PGSO model with the original GCN parameter config- uration, shown in Table 1 In this section, observe how sensitive the optimal parameters of S) and the final model accuracy are to different GSO initialisations.
Experimentation setup: We use the GCN-PGSO model, described Section 3.3 for the node classification task on the Cora dataset (MeCallum et al. 2000). We consider different initialisa- tions of (A,, S) that correspond
the GCN operator D, 1/2 D, 1/2 2) the adjacency matrix A, 3) the random-wale walk normalised Laplacian Lrw = I - D D-'A, 4) the symmetric normalised Laplacian T.aym = T D-1p//-------- and 5) naive all-zeros initialisation, where all ((A, parameters are set
O.
In Figure 3 we observe the parameter evolution of (A, S) over 150 epochs for the different initiali- sations. The parameter values obtained from the GCN, adjacency matrix and all-zeros initialisations exhibit a great amount of similarity; while the normalised Laplacian initilisations lead to similar optimal values for five of the seven parameters. For all initialisations observe that parameters mi, my, 61, 62, e3 monotonically increase until they converge. Parameters m2 and initially in- crease for the GCN, adjacency and all-zeros initialisations, while they initially decrease for the two normalised Laplacians. The achieved accuracy of the five initialisations is plotted in Appendix [B.4] where can be observed that the resulting accuracy from the two normalised Laplacian initiali- sations is slightly lower than the one achieved by the remaining three initialisations. Overall, the accuracy is not very sensitive to the different initialisations.
5.3 REAL- WORLD SCENARIOS
In this section, we evaluate the contribution of the parametrised GSO, when we apply it to a variety of graph learning tasks. In order to highlight the flexibility of (), perform both node classification and graph classification tasks.
Datasets: For node classification, we have used the well-examined datasets Cora and Cite- Seer (McCallum al.) 2000 Giles et al. 1998) and ogbn-arxiv, that is citation network from recently popular collection of graph benchmarks, the Open Graph Benchmark (Hu et al.) 2020). For graph classification, have used the extensively-studied TU datasets MUTAG. PTC-MR, IMDB- BINARY and IMDR-MULT7 (Kersting et al., (016) and OGBG-MOLHIV dataset from OGB (Hu al. 2020 Details and statistics of the datasets can be found in Appendix B.2.1
Experimentation Setup:
For the node classification datasets Cora and CiteSeer, we performed
cross validation with the train/validation/tsst splits being the same as Kipp' & Welling (2017). while for Ogbn-arxiv, used the same splitting method used in Hu al. (2020), according to
8

---

Published as a conference paper at ICLR 2021
Core
CloGect
Oger and
MUTAC
07.3
77.3
74
52.5
46/3
76.0
66.0
75.0
05.0
00.0
Sarded
-9
MOB-SIAARY
MULTI
PTC-44
OGBGMOLIIYY
75.0
25.0
70.0
15.0
40.3
0030
05.0
DAT
Figure 4: Classification accuracy results for both node and graph classification tasks (Validation ROC-AUC for OGBG-MOLHIV), Lower case letters denote a node classification task, while capital letters graph classification task.
the publication dates. For the TU datasets, we performed 10-fold cross validation with grid search hyper-parameterr optimisation and for OGBG-MOLHIV, following Hu et al. (2020) used scaf- fold splitting approach and measured the validation ROC-AUC. We compared the contribution of
PGSO and mPGSO 4 standard GNN baselines: 1) GCN:
Graph Convolutional Network (Kipf)
& Welling 2017). 2) GAT: Graph Attention Network /Velčkovié et al., 2018), 8) 3) SGC: Simplified
Graph Convolution (Wu et al., 2019) and 4) GIN: Graph Isomorphism Network (Xu et al. 2019). A
full description of the experimentation details for each task can be found in Appendix B.2.2
show the contribution of the PGSO and the mPGSO methods, when applied to standard GNNs. For all datasets and GNN architectures, the inclusion of the PGSO or the mPGSO improves the model performance. In the graph classification tasks the performance improvement is higher than the node classification tasks. Specifically, on MUTAG, PTC-MR and AMDB-BINALE we observe significant improvement of the classification accuracy for all GNNs. the comparison between PGSO and mPGSO we do not find a clear winner. For this reason, we prefer the PGSO variant, as more efficient and never harms the model's performance. In Appendix B.5 we study the convergence of optimal accuracy and loss values of the GNN-PGSO model in node- classification and a graph classifcation dataset. In both experiments we observe the PGSO model to converge slightly faster and to better accuracy and loss values than its conventional counterpart.
In Figure 4
CONCLUSION
In this work, parametrised graph shift operator (PGSO) is proposed, that encodes graph struc- tures and can be included in any graph representation learning scenario. Focusing on graph neural networks (GNNs), demonstrate that the PGSO can be integrated in the GNN model training. We proved that the PGSO has real eigenvalues and a set of real eigenvectors and derived its spec- tral bounds, which when observed in practice show that our learned PGSO leads to numerical stable computations. A study on stochastic blockmodel graphs demonstrated the ability of the PGSO to au- tomatically adapt networks with varying sparsity, independently confirming the positive impact of GSO regularisation which was found in the literature. Experiments on 8 real-world datasets, where both node and graph classification was performed, demonstrate that the accuracy of a representative sample of the current fate-offthheart GNNs can be improved by the incorporation of our PGSO. In answer to our two research questions posed in Section T our experimental results have shown that the optimal representation of graph structures is task and data dependent. We have furthermore found that PGSO parameters can be incorporated in the training of GNNs and lead to numerically stable learning and message passing operators.

---

Published as a conference paper at ICLR 2021
REFERENCES
Uri Alon and Fran Yahav. On the bottleneck of graph neural networks and its practical implications.
vrXiv:2006.05200 2020.
Dennis Bernstein. Matrix mathematics: Theory, facts, and formulas (second edition). Princeton, NJ:Princeton University Press, 2009.
Charles Bordenave, Mare Lelarge, and Laurent Massoulié. kon-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs. IEEE 56th Annual Sympo- sium on Foundations of Computer Science, pp. 1347 1357. IEEE, 2015.
Richard A Brualdi. Spectra of digraphs. Linear Algebra and its Applications, pp. 2181-2213, 2010.
Hong Chang and Dit- Yan Yeung. Graph laplacian kernels for object classification from single example. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 2011 2016, 2006.
Dragoš Cvetković and Slobodan K. Simić. Towards spectral theory of graphs based on the signless laplacian, ii Linear Algebra and its Applications, pp. 2257 2272, 2010.
Lorenzo Dall' Amico, Romain Couillet, and Nicolas Tremblay. Optimized deformed laplacian for spectrum-based community detection in sparse heterogeneous graphs. arXiv: arXiv:/901.0m 990.09911, 2019.
Lorenzo Dall' Amico, Romain Couillet, and Nicolas Tremblay. Optimal laplacian regularization for sparse spectral community detection. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3237 3241, IEEE, 2020.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neu- ral networks for node disambiguation. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, ISCAI-20, pp. 2126-2132. 2020.
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, pp. 066106, 2011.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv:2003.00988 2020.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Stability of graph neural networks to rel- ative perturbations. In International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 9070 9074. IEEE, 2020.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: automatic citation indexing system. In International Conference on Digital Libraries, pp. 89 - 98. ACM Press, 1998.
Krystal Guo and Bojan Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. Journal of Graph Theory, pp. 217-248, 2017.
Frank Hall, Kinnari Patel, and Michael Stewart. Interlacing results on matrices associated with graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, pp. 113 - 127, 2009.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Prucessing Systems (NIPS), pp. 1025 - 1035. Curran Associates Inc., 2017a
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017b.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, pp. 109 137, 1983.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge, UK: Cambridge University Press, 1985.
10

---

Published as a conference paper at ICLR 2021
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. 2000000000.00687, 2020.
Brian Karrer and Mark Newman. Stochastic blockmodels and community structure networks. Physical review E, pp. 016107, 2011.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. http::/graphkerree////
tu tmund. de
Choongrak Kim, Mookyung Cheon, Minho Kang, and Iksoo Chang. A simple and exact laplacian clustering of complex networking phenomena: Application to gene expression profiles. Proceed- ings of the National Academy of Sciences, pp. 4083 4087, 2008.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations (ICLR), 2017.
Johannes Kliepera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems 32, pp. 13354 13366. Curran As- sociates, Inc., 2019.
Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, pp. 20935 20940, 2013.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for sepi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Yuemeng Li, Xintao Wu, and Aidong Lu. Analysis of spectral space properties of directed graphs using matrix perturbation theory with application in graph partition. In IEEE International Con- ference on Data Mining, pp. 847-852. IEEE, 2015.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 338 348. Association for Computing Machinery, 2020.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In 8th International Conference on Learning Representations (ICLR), 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156 - 2167, 2019.
Gonzalo Mateos, Santiago Segarra, Antonio G Marques, and Alejandro Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Processing Maga- zine, pp. 16 43, 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, pp. 127 163, 2000.
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, pp. 4602 4609, 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geomet- ric graph convolutional networks. In 8th International Conference on Learning Representations (ICLR), 2020.
Guilherme Porto and Luiz Emilio Allem. Eigenvalue interlacing in graphs. Proceeding Series of the Brazilian Society of Applied and Computational Mathematics, pp. 010232,, 2017.

---

Published as a conference paper at ICLR 2021
Tai Qin and Karl Rohe. Regularized spectral clustering under the degree-corrected stochastic block- model. In Advances in neural information processing systems (NIPS), pp. 3120 3128, 2013.
Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian. In Advances in Neural Information Processing Systems (NIPS), pp. 406 4114, 2014.
Aliaksei Sandryhaila and José M. F. Moura. Discrete signal processing graphs. IEEE Transac- tions on Signal Processing, pp. 1644 1656, 2013.
Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The Semantic Web 15th International Conference (ESWC), pp. 593 607. Springer/Verlag, 2018
D. I. Shuman, S. K. Narang. P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending gigh-dimensional data analysis networks and other irregular domains. IEEE Signal Processing Magazine, pp. -8, 2013.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations (ICLR), 2018.
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, pp. 395 416, 2007.
Felix Wu, Amauri H Souza Jr, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In 7th International Conference on Machine Learning (ICLR), 2019.
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical Science, pp. 513 - 530, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long. Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, pp. 21, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? 7th International Conference on Learning Representations (ICLR), 2019.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. Proceedings of Machine Learning Research, pp. 7134 - 7143, 2019.
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems 31, pp. 5165-5175. 2018
APPENDIX
A PROOFS
A. PROOF OF THEOREM 1
In this appendix we prove that 7(A has real eigenvalues and a set of real eigenvectors. For this proof the definition of similar matrices is fundamental.
Definition 3. Two matrices Q E Caxn are similar via a nonsingular similarity matrix S E Ca if
V = S=
Next we note that (A, is similar to the symmetric matrix D. (e2-ss)/ (A)
Real, symmetric matrices have set of real eigenvalues and furthermore, possess set of real eigen- vectors. It is a known property of similar matrices that they share eigenvalues and that for a given eigenvector of Φ Sw is eigenvector of V (Horn & Johnson| 1985 pp. 45,60). Therefore, by the similarity relationship to a real symmetric matrix via a real similarity matrix, 7(A, S) has real eigenvalues and set of real eigenvectors.
12

---

Published as a conference paper at ICLR 2021
0-0.00
2- 46
2- 544
5-042
pa
pa pn 4.3
p- 0.30
5.9
024
322
020
Figure 5: List of adjacency matrices generated by stochastic blockmodels for varying sparsity by decreasing the probability tuple (p, 4).
A.2 PROOF OF THEOREM 2
In this proof we will again be utilising the property that similar matrices share eigenvalues by con- sidering the matrix D S)D)s which is similar to (A, The Gershgorin Theorem states that all eigenvalues of matrix contained in circles centred at the matrix's s diagonal elements with radii equal to the corresponding off-diagonal row-sums of the matrix elements in absolute value (Bernstein, 2009 293). In Theorem [ we showed that 7AA has a real spectrum and therefore the circles in the Gershgorin Theorem are in fact intervals on the real line in the case of (A, The parametrised form of D* DD is follows.
D D*,(A,))
D + m2 tes A, + m3Ja-
From 44) we can simply read off that the diagonal elements, denoted C₁, and off-diagonal row-sums of the matrix elements absolute value, denoted R, of D (A, D),)) take the following form,
R₂ = m (d: + a + m2(d; + aa tes + m3,
C = m2 (d; + de,
Hence, via the similarity relationship of Des (A, ST and (A, S) and direct application of the Gershgorin Theorem applied to D (A, D) -- we obtain the required result.
B EXPERIMENTS
B.1 STOCHASTIC BLOCK MODELS
In this section, we present a visualisation graphs generated from stochastic blockmodels (SBMs) with varying sparsity. Specifically, in Figure we display 15 adjacency matrices of graphs generated
from SBMs with edge probabilities (p. q) (0.50. 0.25) (0.22, 0.11)}. The format of this adjacency matrix visualisation is taken from Dwivedi al. (2020). The ordering of the node labels in Figure 5 corresponds to their block membership in order to highlight the block structure in the adjacency matrix plots.
13

---

Published as a conference paper at ICLR 2021
B.2 EXPERIMENTATION SETUP ON REAL- REAL-WORLD WORLD DATASETS
In this section, we present the dataset information and statistics and the experimentation details for the experiments in Section 5.3
B.2.1 DATASETS
The datasets used in the experimentation setup cover both node and graph classification tasks.
Cora and CiteSeer are citation networks (Kipf Welling 2017). where nodes correspond to documents and edges encode citation links. Both datasets contain node attributes, that are sparse bag-of-wordd representations the documents.
Ogbn-arxiv is citation network with directed edges, where each node corresponds to an arXiv paper and the edges denote citations from one paper another (Hu et al. (020). The dataset contains node attributes, that are averaged word embeddings of titles and the abstracts of dimensionality 128. The label of each node is the subject area of the paper and can take 40 values.
MUTAG and PTC-MR are a collection of bio-informatics networks (Kersting et al. 2016), where the label of each graph correspond to chemical property of the compound.
datasets containing collaborations between tors/actresses, where each graph is an ego-graph an actor/actress and edges occur when two actors/actresses are playing in the same movie (Kersting et al. (016)) These datasets do not contain node attributes, thus following the literature, we create node features by using one-hot encodings of the node degrees.
IMDB-BINARY and IMDB-MULTI
OGBG-MOLHIV is collection of graphs, that represent molecules (Wu al. 2018) Nodes are atoms and the edges correspond to chemical bonds between atoms. The graphs contain node features, that are processed as in Hu al. (2020).
In Table the dataset statistics of both node and graph classification tasks are displayed.
Table Datasets statistics
Dataset
# graphs
# avg.nodes/graph
# avggedges/graph
# classes
Cora
1
2,708
5,429
2
CiteSeer
3,327
4,732
Ogbn-arxiv
169,343
1,166,243
40
MUTAG
188
17.93
19.81
2
PTC-MR
344
14.29
14.32
2
IMDB-BINARY
1000
19.77
96.52
IMDB-MULTI
1500
13.00
76.34
3
OGBG-MOLHIV
41,127
25.5
27.50
2
B.2.2 EXPERIMENTATION DETAILS
In this section, we initially report the experimental setting that is common to all experiments and, then, separately provide the details which are specific to the different tasks (node classification and graph classification).
our experiments, we use the Adam optimizer (Kingma & Ba 2015) with weight decay on the parameters of 5 10-4 and an initial learning rate of 0.005 for the exponential parameters and an initial learning rate of 0.01 for all other model parameters. The differentiation between the two learning rates crucial for the model training, the fluctuation of the exponential parameters has higher impact on the model behavior than the rest the model parameters. We, also, used learning rate scheduler that decayed both the learning rates by 0.5 every 50 epochs.
14

---

Published as a conference paper at ICLR 2021
Node Classification Tasks We report below the experimental details used in the node classifica- tion datasets, regarding model selection, metrics and model design. The Cora and CiteSeer datasets formulated binary class classification problems, while the Ogbn-arxiv is formulated 40- class classification problem.
Model Selection: We perform cross-validation for all GNN, GNN-PGSO and GNN- mPGSO models with predefined dataset splits. For Cora and CiteSeer, we use the same train/validationneest splits in Kipf & Welling (2017) for the sake of comparison with other methods that use the same splits. For Ogbn-arxiv, we use the splitting method, de- scribed in Hu et (2020), that splits the data into the train split, containing all papers until 2017, the validation split, containing all papers published in 2018 and test split with the published papers since 2019.
Haper-per Tuning: We use grid search to tune the typer-parametee of the models (dimensionality hidden units, number of GNN layers, number of epochs and the batch size).
Evaluation Metric: For all node classification datasets (Cora, CiteSeer, Ogbn-arxiv), we use evaluation metric the validation accuracy.
Model Design: The number of hidden units that was grid- gric-searched was within {16, 32, 64).
The number of GNN layers that were used were within {1, 2, 3, 4].
Experiment Design: The number of epochs for the model training was {50, 100, 200), batch size within (16, 32, 64) and dropout ratio of 0.5.
Graph Classification Tasks In the same fashion we report below the details of the experimenta- tion setup of the graph classification tasks. The MUTAG, PTC-MR, MIDB-BINARY and OGBG- MOLHIV are formulated as binary class classification problems, while IMDB-MULTY is formulated as 3-class classification problem.
Model Selection: We perform 10-fold cross-validation for all mPGSO models. For MUTAG, PTC-MR, IMDB-BINARY and IMDB-MULTI, have used k random and stratified splits to provide balanced train/validation/tesl sets. For OGBG-MOLHIV we use the scaffold splitting as in Hu al. (2020), that seperates the graphs based on their 2D structural representations.
GNN-
Hyper-parameter Tuning: We use grid search to tune the hyper-parameters the models (dimensionality of hidden units, number of GNN layers, number of epochs and the batch
size).
Evaluation Metric:
For the MUTAG, PTC-MR, we use as evaluation metric the standard classification accuracy, while for the OGBG- MOLHIV
IMDB-MULTI datasets,
as Hu et al. 2020) the validation ROC-AUC.
Model Design: The number of hidden units that was grid-searched was within {16, 32, 64).
The number of GNN layers that were used were {1, 2, 3, 4, 5).
Experiment Design: The number of epochs for the model training was {100, 200, 300), the batch size within (16, 32, 64) and the dropout ratio of 0.5.
B.3 TABLES
Next, we present Tables 3 and 4 containing the detailed experimentation results. In Table 3 the average accuracies with their corresponding standard deviations for the node classification tasks are presented, in particular for the datasets Cora, CiteSeer and Ogbn-arxiv. In Table 4 the results for the graph classification tasks are presented, specifically MUTAG, PTC-MR, AMDB-BINARY IMDB-MULTI and OGBG-MOLHIV, We note that for the first 4 graph classification datasets compute the classification accuracy, while for OGBG-MOLHIV we use the validation ROC-AUC, following Hu al. 2020
B.4 MODEL PERFORMANCE FOR DIFFERENT INITIALISATIONS
In Figure 6 we show the train and validation accuracy achieved by the PGSO model discussed in Section 5.2 using the different initialisation configurations: GCN operator, adjacency matrix,
15

---

Published as a conference paper at ICLR 2021
Table 3: Classification accuracies for Cora and CiteSeer and validation ROC-AUC for Ogbn-arxiv.
Cora
CiteSeer
Ogbn-arxiv
GCN
81.4 + 0.4
70.9 + 0.5
71.74 0.29
SGC
81.0 + 0.1
71.9 = 0.2
70.91 0.31
GAT
83.0 + 0.7
72.5 + 0.6
71.82 + 0.22
GIN
77.6 + 1.5
69.6 + 0.9
71,49 + 0.27
GCN-PGSO
82.0 0.1
71.5 + 0.4
72.66 0.32
GCN-mPGSO
71.6 + 0.3
72.12 + 0.31
SGC-PGSO
81.4
73.1 1 0.5
70.99 + 0.28
SGC-mPGSO
81.6 0.3
72.8 + 0.2
71.12 + 0.27
GAT-PGSO
84.3 + 0.4
73.0
72.15 0.18
GAT-mPGSO
83.8 + 0.5
72.9 + 0.4
72.21 + 0.17
GIN-PGSO
77.8 + 0.8
69.9 + 0.8
71.68 + 0.22
GIN-mPGSO
78.1 + 1.3
70.2 + 1.5
71.72 0.28
Table 4: Classification accuracies for 5 graph classification datasets.
MUTAG
PTC-MR
IMDB-BINARY
IMDB-MULTI
OGEG-MOLHIV
GCN
85.8 + 3.1
64.3 2.1
71.4 2.4
50.3 + 1.8
76.06 0.97
SGC
84.4 + 1.7
64.1 + 1.2
71.6 + 1.4
50.9 + 2.0
75.72 + 0.87
GAT
86.1 + 2.3
63.8 + 1.5
70.8 + 1.5
50.1 + 1.1
74.12 + 0.99
GIN
89.4 + 5.6
64.4 + 1.9
75.1 5.1
52.3 + 2.8
75,58 + 1.41
GCN-PGSO
90.7 + 3.5
67.1 + 2.2
72.7 +: 3.2
51.0 + 1.5
76.75 + 1.12
GCN-mPGSO
90.2 + 2.8
69.0 + 1.9
72.4 + 1.8
50.8 + 1.2
76.21 + 1.01
SGC-PGSO
88.9 + 1.8
68.1 + 1.5
73.2 3.5
51.9 + 1.4
75.77 + 0.65
SGC-mPGSO
86.1 + 3.1
67.6 + 1.3
73.4 + 1.3
51.5 + 1.2
75.81 + 0.72
GAT-PGSO
87.2 + 3.9
64.2 + 0.7
71.2 + 0.7
50.6 + 0.7
75.43 + 0.91
GAT-mPGSO
86.8 + 4.3
64.4 +: 1.1
70.4 1.1
50.1 +: 1.3
74.23 + 1.11
GIN-PGSO
91.9 + 3.1
66.1 + 2.1
76.4 2.8
53.3 + 2.1
76.32 1.37
GIN-mPGSO
90.8 + 3.2
64.7 + 2.2
77.1 + 3.2
53.8 + 2.7
76.22 + 1.65
Figure 6: Train and Validation Accuracy on Cora using different initialisation configurations for PGSO
all-zeros, symmetric normalised Laplacian and mandom-wall Normalised Laplacian. For all experi- ments, used the same configuration of the syper-parameter for fair comparison.
16

---

Published as a conference paper at ICLR 2021
B.5 CONVERGENCE STUDY
In this appendix, we empirically analyse the contribution of the PGSO in a node classification and graph classification task regarding the accuracy and loss convergence. For the node classification task, we have used the Cora dataset and a GCN model. Both for the standard GCN and the GCN- PGSO models, we used the same experimentation configuration for a fair comparison. For the graph classification task, we have used PTC-MR dataset and a GIN model. Both for the standard GIN and the GIN-PGSO models, we used the same configuration for fair comparison. In Figures and 8 we show the accuracy and loss convergence using the standard model and the PGSO model. As we can see, for both the node classification and graph classification task, the PGSO incorporation into the model has positive impact on the achieved accuracy and the loss minimization throughout
training. Specifically, we observe a slightly faster convergence of accuracy and loss in better values
using the GCN-PGSO and GIN-PGSO models.
accurscy
convergence
Train PG50
Train Loss of GCN
24-
02
Than Accansoy al BOMPSDO Than Accasec
02-
KE. Ascanas CEN-
Accunaty
103
340
Figure 7: Accuracy and Loss convergence for the node classification task Cora
Train Accurary with and without POSO
Validiiion wecurncy with and without PCSO
Loss ceevergence with and without
2.00
of GM
Wi Minl
3.50
Tiahl Ancuriic
Trnai Anturriyy POOD
V.A AL Aermrry PO6O www.necuumryyy cf
40
180
120
140
20
80
100
160
22
60
60
100
123
160
Figure 8: Accuracy and Loss convergence for the graph classification task on PTC-MR
17


Reviews:
[{"review_id": "oHPDDJ75-sN", "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": "##########################################################################\nSummary:\n\nThe paper proposes a parametric form for a matrix representation of a graph to be used as a building block within graph neural networks (GNNs). In essence, people use different normalized versions of the adjacency and Laplacian matrices within GNNs. The authors, in turn, propose a generic parametrized version that encompasses those normalizations and that can be learned from data.\n\n##########################################################################\nReasons for score: \n \nMy overall evaluation is slightly positive. Although the methodological contribution is minor, my positive recommendation is based on the wide applicability of the simple idea proposed. The parametric graph shift operator can be readily used in existing applications of GNNs possibly boosting performance.\n \n##########################################################################\n\nPros: \n\n1. Simple contribution explained in a straightforward manner. This can help adoption by practitioners.\n\n2. Numerical experiments rightly illustrate the value of the contribution.\n \n\n##########################################################################\n\nCons: \n\n1. There is no clear justification for the specific parametric form in (1), other than it can recover existing choices of the GSO. This, of course, can be obtained with other conceivable parametrizations. The authors try to justify this by saying that (1) is the \"most general affine form of the adjacency matrix\", but this does not seem to be a rigorous statement. Most general in what sense? What is the space of all affine forms of matrices?\n\n2. The value of the theoretical analysis is unclear. The paragraph after Theorem 1 is supposed to highlight the value of having real eigenvalues. The authors mention \"without having to worry about complex values\", worrying in what sense? Why would it be difficult to implement the examples at the end of page 4 if the eigenvalues would be complex? The authors then mention the difficulty of doing spectral clustering with complex eigenvalues, but the connection with the ongoing discussion is quite loose.\n\n3. Similarly, the value of Theorem 2 is unclear to me. Why are these bounds useful? The discussion after Theorem 2 again tries to enlighten in that direction, but it falls short.\n  \n\n#########################################################################\n\nSome typos: \n(1) In Remark 1, \"absence of an edge\" should be \"existence of an edge\".\n\n#########################################################################\n\nEdit after author response: We thank the authors for their response to my concerns and those of other reviewers. I have updated my score from 6 to 7 based on their changes.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hXcOKMmHx02", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "The paper proposes a parameterized graph shift operator (PGSO) as a replacement of fixed, hand-picked GSOs for application to GNN architectures and the experiments illustrate that PGSOs automatically adapt to the regularized GSOs for different settings. The contribution is of interest to the ML community as existing studies show significant improvements in performance of GNNs by using certain GSOs in specific contexts and therefore, a data driven characterization of GSO helps introduce adaptivity to the network representation in GNNs.\n\nPros: The paper is well written and easy to follow. The theoretical and empirical spectral analysis of PGSO reveals its applicability to many existing GNN architectures. The experiments are sufficient to illustrate the utility of using PGSO over a constant GSO for different settings. \n\nCons: \n1. Remark 1 seems to contradict Definition 1. Do the authors mean 'presence' and not 'absence' of an edge in Remark 1?\n\n2. An explicit discussion on how PGSO parameters are learned or updated in every epoch is missing. \n\n3. The authors compare the final accuracy results of GNNS with PGSOs and those with constants GSOs. The evolution of accuracy with the number of epochs for some of these results will help evaluate the cost of learning the parameters of PGSOs. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "OZfy56V1qN7", "reviewer": "AnonReviewer1", "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 consider the problem of learning a parametrized graph shift operator (or message passing operator) in the context of graph neural networks. They consider a family of GSO (that they name PGSO) based on seven scalar parameters, and show that it includes most commonly used operators such as the adjacency matrix or the laplacian. The spectral properties of the PGSO are analyzed. Finally, some empirical results are provided demonstrating the PGSO as a drop-in replacement for standard GSO in GNN architectures.\n\nGraph neural networks have gathered a large amount of interest in the past years, and found widespread use in adapted problems. However, recent analyses have shown that typical architectures may have limited expressiveness (e.g. bounded by the WL test). The paper is overall well-written, and proposes a method which could be of interest to practitioners. On the other hand, the paper has some minor weaknesses, in that the proposed parametrization is redundant with some existing techniques (e.g. $m_3$ corresponds to residual connections, which are widely used), and, given the simplicity of the proposed method, a more comprehensive empirical evaluation could be beneficial. Additionally, the proposed operator is still restricted to 1-neighborhoods, and hence cannot by itself solve the expressiveness problems encountered by graph neural networks. This lack of expressiveness, in conjunction with the mixed empirical results (which show overall good performance improvement but with overlapping error bars), potentially lower the impact of this contribution.\n\nGiven the potential interest this method could hold for practitioners, I believe that the paper could be substantially improved by making the empirical evaluation more comprehensive. In particular, a more comprehensive analysis of the training dynamics (as in figure 1) as well as the effect of initialization would give a clearer picture of the effect of the PGSO in practice. Specifically, one might wonder about the importance of initialization for the $m_2$ parameter, given that it controls the influence of the edge information, and for example whether it is possible for it to change sign during training. Perhaps an informative experiment could be to initialize the PGSO at different commonly used GSO parameters (e.g. adjacency, Laplacian, normalized Laplacian), and observe how such initialization affects performance.\n\n==============================\n\nEdit after author response: we thank the authors for their response and providing some more empirical information. Overall I feel that this paper presents a neat idea that could be of interest to some people in the community, and I have modified my score from 6 to 7. It would be great for the authors to discuss the importance of initialization, as in particular, it seems to me that the sign of $m_2$ can never change  (from its initial value), indicating perhaps that practitioners should try initialization at either and select the better performing model.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "55dBb5beyA", "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 describes a parameterized family of \"graph shift operators\", defined for any graph on n vertices as an n x n matrix where the i,j-th entry is 0 whenever edge (i,j) does not appear in the graph. The paper studies some spectral properties of the parameterized family, and experiments with using them as components of graph neural networks.\n\nThis paper appears to me to be a hammer in search of a nail. It was not clear what problem is meant to be solved here. Nor does it seem that the topic is fundamental, scientific investigation. \n\nThe paper is generally poorly written and was difficult to follow. I suspect much of that relates to the lack of clarity in the problem. However, the writing is also unfocused at the paragraph level.\n\nIn short: this paper needs substantial work before it's ready for publication. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary:
The authors observe that a range of Laplacian-type operators used in
graph neural networks can be embedded in a parametric family, so that
the precise form of the Laplacian used can be determined by the
learning process. Empirical evaluation and some (limited) theoretical
analysis are provided. 

Discussion:
The authors have provided detailed replies and also additional
experiments. That has addressed major concerns, and most reviewers now
agree the paper is good. One reviewer is more skeptical, mostly
regarding presentation. I agree with some of the points raised in this
regard, but see them as less of an issue - I would consider the
presentation improvable, but acceptable.

One weakness I should mention is that the two theorems provided are
frankly trivial. I appreciate this is 'only' a conference
submission,
but I would nonetheless call the fact that symmetric matrices have real
eigenvalues (theorem 1) an observation, not a result. 
That similarly holds for any direct consequence
of Gershgorin's theorem (theorem 2). The entire page used to state this could perhaps be put to
better use for additional empirical results.


Recommendation:
The program committee (the AC and program chairs) were hesitating about this paper but decided to recommend acceptance. The idea is neat and simple, presentation and empirical evaluation are fine, if improvable (we strongly recommend the authors to invest time). What is phrased as theory is trivial, but also admittedly not the main focus of the paper. 



Decision: Accept (Poster)