Analysing the Update step in Graph Neural Networks via Sparsification
Authors: changmin wu
Johannes F. Lutzeyer
Michalis Vazirgiannis
Venue:  (2021)
Keywords: graph neural network architectures
message-passing neural networks
neural network sparsification
deep learning

Abstract: In recent years, Message-Passing Neural Networks (MPNNs), the most prominent Graph Neural Network (GNN) framework, have celebrated much success in the analysis of graph-structured data. In MPNNs the computations are split into three steps, Aggregation, Update and Readout. In this paper a series of models to successively sparsify the linear transform in the Update step is proposed. Specifically, the ExpanderGNN model with a tuneable sparsification rate and the Activation-Only GNN, which has no linear transform in the Update step, are proposed. In agreement with a growing trend in the relevant literature the sparsification paradigm is changed by initialising sparse neural network architectures rather than expensively sparsifying already trained architectures. These novel benchmark models enable a better understanding of the influence of the Update step on model performance and outperform existing simplified benchmark models such as the Simple Graph Convolution (SGC). The ExpanderGNNs, and in some cases the Activation-Only models, achieve performance on par with their vanilla counterparts on several down-stream graph prediction tasks, while containing exponentially fewer trainable parameters. In experiments with matching parameter numbers our benchmark models outperform the state-of-the-art GNNs models. These observations enable us to conclude that in practice the Update step often makes no positive contribution to the model performance.

Under review as a conference paper at ICLR 2021
ANALYSING THE UPDATE STEP IN GRAPH NEURAL NETWORKS VIA SPARSIFICATION
Anonymous authors Paper under double-blind review
ABSTRACT
In recent years, Message-Passing Neural Networks (MPNNs), the most prominent Graph Neural Network (GNN) framework, have celebrated much success in the analysis of graph-structured data. In MPNNs the computations are split into three steps, Aggregation, Update and Readout. In this paper a series of models to succes- sively sparsify the linear transform in the Update step is proposed. Specifically, the ExpanderGNN model with a tuneable sparsification rate and the Activation-Only GNN, which has linear transform in the Update step, are proposed. In agree- ment with growing trend in the relevant literature the sparsification paradigm is changed by initialising sparse neural network architectures rather than expensively sparsifying already trained architectures. These novel benchmark models enable a better understanding of the influence of the Update step on model performance and outperform existing simplified benchmark models such as the Simple Graph Convolution (SGC). The ExpanderGNNs, and in some cases the Activation-Oni Onlly models, achieve performance on par with their vanilla counterparts on several down-stream graph prediction tasks, while containing exponentially fewer trainable parameters. In experiments with matching parameter numbers our benchmark models outperform the state-of-the-ar GNNs models. These observations enable to conclude that in practice the update step often makes positive contribution to the model performance.
INTRODUCTION
Recent years have witnessed the blossom of Graph Neural Networks (GNNs). They have become the standard tools for analysing and learning graph-structured data (Wu et al. 2020) and have demonstrated convincing performance in various application areas, including chemistry (Duvenaud al. 2015), social networks (Monti et al. 2019), natural language processing (Yao et al. 2019) and neural science (Griffa et al. 2017).
Among various GNN models, Message-Passing Neural Networks (MPNNs, Gilmer al. 2017 and their variants are considered to be the dominating class. In MPNNs, the learning procedure can be separated into three major steps: Aggregation, Update and Readout, where Aggregation and Update are repeated iteratively so that each node's representation is updated recursively based on the transformed information aggregated over its neighbourhood. With each iteration, the receptive field of the hidden representation is increased by 1-step on the graph structure such that at btth iteration, the hidden state of node is composed of information from its k-hop neighbourhood.
There is thus a division of labour between the Aggregution and the Update step, where the Aggregation utilises local graph structure, while the Update step is only applied to single node representations at a time independent of the local graph structure. From this natural question then arises: What is the Update step on the performance of GNNs?
impact of the
Wu et al. 2019) first challenged the role of Update steps by proposing simplified graph convolutional network (SGC) where they removed the non-linearities in the Update steps and collapsed the consecutive linear transforms into single transform. Their experiments demonstrated, surprisingly. that in some instances the Update step of Graph Convolutional Network (GCN, Kipf & Welling (207)) can be left out completely without the models' accuracy decreasing.

---

Under review as a conference paper at ICLR 2021
In the same spirit, we propose in this paper to analyse the impact of the Update step in systematic way. To this end, we propose two nested model classes, where the Update step is successively sparsified. In the first model class which refer to as Expander GNN, the linear transform layers of the Update step are sparsified; while in the second model class, the linear transform layers removed and only the activation functions remain in the model. We name the second model Activation-Ont GNN and it contrasts the SGC where the activation functions where removed to merge the linear layers.
Inspired by the recent advances in the literature of sparse Convolutional Neural Network (CNN) architectures (Prabhu et al. 2018), we propose to utilise expander graphs as the sparsifier of the linear layers (hence the model's 's name). Guided by positive graph theoretic properties, it optimises sparse network architectures at initialisation and accordingly saves the cost of traditional methods of iteratively pruning connections during training.
Through a series of empirical assessments on different graph learning tasks (graph and node classifi- cation as well graph regression), we demonstrate that the Update step can be heavily simplified without inhibiting performance or relevant model expressivity. Our findings partly agree with the work in (Wu et al., 2019). in that dense Update steps in GNN are expensive and often unnecessary. In contrast to their proposition, we find that there are many instances in which leaving the Update step out completely significantly harms performance. In these instances our Activation Only model shows superior performance while matching the number of parameters and efficiency of the SGC.
Our contributions can be summarised as follows.
(1) We explore the impact of the Update step in MPNNs through the newly proposed model class of Expander GNNs with tuneable density. We show empirically that sparse update step matches the performance of the standard model architectures.
(2) As extreme case of the Expander GNN, as well as alternative the SGC, we propose the Activation- Only GNNs that remove the linear transformation layer from the Update step and keep non-linearity in tact. We observe the Activation-Oni Only models to exhibit comparable, sometimes significantly superior performance to SGC while being equally time and memory efficient.
Both of our proposed model classes can be extrapolated without further efforts to a variety of models in the MPNN framework and hence provide practitioners with an array of efficient and often highly performant GNN benchmark models.
The rest of this paper is organised as follows. In Section 2 we provide an overview of the related work. Section 3 introduces preliminary concepts of MPNNs and expander graphs, followed by a detailed presentation of our two proposed model classes. Section discusses our experimental setting and empirical evaluation of the proposed models in a variety of downstream graph learning tasks.
2 RELATED WORKS
In recent years the idea of utilising expander graphs in the design of neural networks is starting to be explored in the CNN literature. Most notably, Prabhu al. (2018) propose replace linear fully connected layers in deep networks using an expander graph sampling mechanism and hence, propose novel CNN architecture they call X-nets. The great innovation of this approach is that well-performing sparse neural network architectures are initialised rather than expensively calculated. Furthermore, they are shown compare favourably in training speed, accuracy and performance trade-offs to several other state of the art architectures McDonald & Shokoufandehi (2019) and Kepner Robineti (2019) build on the X-net design and propose alternative expander sampling mechansisms to extend the simplistic design chosen in the X-nets. Independent of this literature branch, Bourely et al. (2077) explore different mechanisms to randomly sample expander graph layers. Across the literature the results based expander graph layers are encouraging.
Recently, two papers observed that simplifications in the update step of the GCN model is a promising area of research (Wu et al. 2019: Salha et al. 2019). Wu et al. (2019) proposed the Simple Graph Convolution (SGC) model, where simplification is achieved by removing the non-linear activation functions from the GCN model. This removal allows them to merge all linear transformations in the update steps into a single linear transformation without sacrificing expressive power. Salha et al. (2019) followed a similar rationale in their simplification of the graph autoencoder and variational
2

---

Under review as a conference paper at ICLR 2021
graph autoencoder models. These works have had immediate impact on the literature featuring as a benchmark model and object of study in many recent papers. The idea of omitting update steps ghen guided Chen et al. (2020) in the design of simplified models and has found successful application in
various areas where model complexity needs to be reduced |Waradpande et al. 20200 He et al. 2020)
very large graphs (~ 106 nodes/edges) need to be processed (Salha et al. 2020).
In our work we aim to extend these efforts by providing more simplified benchmark models for
GNNs without specific focus on the GCN.
INVESTIGATING THE ROLE OF THE UPDATE STEP
In this section, we present the two proposed model classes, where we sparsify or remove the linear transform layer in the Update step, with the aim systematically analyse the impact of the Update step. We begin in Section b. introducing the general model structure of MPNNs, the main GNN class study in this paper, and expander graphs, the tool we use to sparsify linear layers. We then demonstrate how expander graphs are used to sparsify linear layers and how an Expander GNN is constructed in Section 332 The idea of Activation-Onf GNNs is discussed in Section 3.3 and comparison to the SGC model is drawn.
3.1 PRELIMINARIES
3.1.1
MESSAGE-PASSING GRAPII NEURAL NETWORK
We define graphs G (A, X) in terms of their adjacancy matrix A [0. 1| which contains the information of the graph's 's node set V, and the node features X E Rnxd ........ xx,] of dimension d. Given a graph G, graph learning task aims at learning meaningful embeddings the node or graph level that can be used in downstream tasks such as node or graph classification. MPNNs, prominent paradígm that arose in recent years for performing machine learning tasks on graphs, learn such embeddings by iteratively aggregating information from the neighbourhoods of each node and updating their representations based on this information. Precisely, the learning procedure of MPNNs can be divided into the following phases:
Initial (optional). In this phase, the initial node features X are mapped from the feature space to a hidden space by a parameterised neural network (10), usually a fully-connected linear layer. (1)) ((0) (X) (h) (1) A(4), where the hidden representation of node is denoted as h which will be used as the initial point for later iterations.
Aggregation. In this phase, MPNNs gather, for each node, information from the node's neighbour- hood, denoted (i) for node i. The gathered pieces of information are called "messages", denoted by m.. Formally, if (-) denotes the aggregation function at iteration I, then
m f (th ((())).
(1)
Due to the isotropic nature of graphs (arbitrary node labelling), this function needs to be permutation invariant. also has be differentiable so that the framework will be end-to-end trainable.
Update. The nodes then update their hidden representations based their current representations and the received "messages". Let (l)) denote the update function at iteration I. For node i, we have
h (L+1) ( m
Readout (optional). After L aggregation and update iterations, depending on the downstream tasks, the MPNN will either output node representations directly or generate graph representation via a readout phase, g = R( (h ( j E V)). Just like the aggregation function, the readout function also needs to be permutation invariant and differentiable.
This paper focuses on the Update step. More precisely, we would like to find the answer to the question: What is the impact of the Update step on the performance of GNNs?
3

---

Under review as a conference paper at ICLR 2021
It is clear that the MPNN framework divides its learning procedure into two parts: the Aggregation step that utilises graph structure and the Update step, the main source of model parameters while being completely agnostic to graph structure. Thus, understanding the importance of the Update step could have a great impact on the design of parsimonious GNNs.
Note that various choices of Aggregation, Update and Readout functions are proposed in the literature. To avoid shifting from the subject of this paper, we work with the simplest and most widely used function choices, such as sum, mean and max aggregators for Aggregation, the Multi-Layer Perceptron (MLP) for the Update step and summation for the Readout. As an example to visualise our model in the subsequent sections we use the following matrix representation of the GCN computations.
H (L) o(A o (AH (()) W..)).
(3)
where a denotes nonlinear activation function, W contains the trainable weights of the linear transform in the update step and Á = Dー ADD is the symmetric normalised adjacency matrix with A = A + denoting the adjacency matrix with added self-loops and D being the corresponding degree matrix.
Now we proceed to define the class of expander graphs, which serves necessary background knowledge for our chosen sparsification mechanism the Update step.
3.1.2 EXPANDER GRAPHS
Expander graphs are a well studied class of graphs. They can be informally defined as being highly connected and sparse, i.e., in expander graphs relatively few edges present and arranged in such way that many edges have to be cut to disconnect the graph (the cut definition is only one way in which the "high connectivity" of expanders can be measured) (Hoory et al. 2006 Lubotzky 2012). Formally, expander graphs can be characterised by the expansion ratio, which we will now define.
Definition 1 (Expander Graph). For 0 < 8 R. G is 6-expander graph if for all S V such that [ S 8, where [S] denotes the cardinality of set S and ds the boundary set of
[S] < [ S, i.e., the set of all vertices, which are connected to a vertex by an edge but are not in S. Then, the expansion ratio h()) is defined to be the minimal 8 such that G is an d-expander graph.
2 we have [08]
Expander graphs have been successfully applied in communication networks where communication comes at a certain cost and is to be used such that messages are spread across the network efficiently (Lubotzky 2012). We believe that expander graphs have a promising future in the neural network literature. In neural network each parameter (corresponding to an edge in the neural network architecture) incurs a comuputational cost both when training the model and when obtaining inference. Therefore, the number of parameters in the model is directly linked to the computational effort and thereby, energy, the model requires to run. Designing neural network architectures using the concept of expander graphs leads to neural network architectures, where fewer edges are placed in such way that the overall computational structure remains highly connected. In Böleskei et al. (2019) the connectedness of sparse neural network architecture function class which can be approximated by sparse neural networks. Hence, utilising neural networks parameters to optimise the connectedness of the network maximises the expressivity of the neural network. In Kepner& & Robinett (2019) and Bourely et al. (2017) the connectedness of the neural network architecture graph was linked via the path-connectedness and the graph Laplacian eigenvalues- to the performance of neural network architectures. Therefore, for both the expressivity of the neural network and its performance the connectedness is parameter of interest and expander graphs utilise a given budget of edges, corresponding to parameters in the neural network, to achieve graphs which are highly connected.
linked to the complexity of given
3.2 SPARSIFYING THE UPDATE STEP: EXPANDER GNN
In order to study the influence of the Update step in GNNs, we propose an experimental design, where its linear transform (of the MLPs) is gradually sparsified. By observing the trend of model performance change (on downstream tasks) with respect to the sparsity the linear transform layer, measure the impact of the Update step.
4

---

Under review as a conference paper at ICLR 2021
Linear Layer as a graph The fully-connected linear transform layer in MLPs can be represented by a bipartite graph B[S S2, E), where $1 and S2 are two sets of nodes and E the set of edges that satisfy Vu E Si, Vo E 32, 2) E E; Vu, S (resp.S2), B(u, v) E E. The number of edges, or number of parameters, is [S | and the edges can be encoded in matrix form by W E R
the weight matrix in Equation that maps the input node features of dimension [S to output node features of dimension [g]]
3.2.1 EXPANDER LINEAR LAYER
Following Prabhu et al. (2018), we choose expander graphs as the sparsifiers for the linear transform layer. When compared to pruning algorithms which sparsify neural network layers by iteratively removing parameters according to certain metric during training, the expander sparsifiers have two advantages:
(1) Good properties of expander structures allow consecutive linear layers to be highly connected when only a smaller number of edges is present. The expander design assures that paths exist between consecutive layers, avoiding the risk of layer-collapse that is common in many pruning algorithms, where the algorithm prunes all parameters (weights) in one layer and cuts down the flow between input and output (Tanaka et al.; (2020).
(2) The expander sparsifier removes parameters at initialisation and keeps the sparsified structures fixed during training, which avoids the expensive computational cost stemming from adapting the neural network architecture during or after training and then retraining the network as is done in the majority of pruning algorithms (Frankle & Carbin 2019 Han al. 2015).
Given the bipartite graph corresponding to a linear transform layer B(S,, S2, E), we follow the design of Prabhu et al. (2018) construct the sparsifier by sampling its subgraph of specific expander structure.
Definition 2. Suppose [S|] < [2)]. For each vertex u S₁, uniformly sample d vertices }u=).=...... from S, to be connected to u. Then, the constructed graph B [S,, E') ) is a subgraph of with edge set E' = {(u, : u E $1, E fl..... d}}. Else if [$1 > [Sa]. we define the expander sparsifier with the roles of $ and S₂ reversed meaning that we sample nodes from Sj.
Definition 3 (layer density). We refer the density of the expander linear layer as the ratio of the number of sampled connections to the number of connections in the original graph. For example, the fully-connected layer has density 1. The sampling scheme in Definition 2 returns an expander linear layer of density T
When we replace all linear layers in the Update steps of a GNN with expander linear layers constructed by the sampling scheme Definition 2 we get the Expander GNN. An illustration can be found in Appendix B Bipartite expander graphs as defined in Definition 2 are also discussed in the field of so called "lossless expanders" in Hoory et al. (2006) pp. 517-522), where several expander graph concepts discussed in the context of bipartite graphs.
3.2.2 IMPLEMENTATION OF EXPANDER LINEAR LAYER
The most straightforward way of implementing the expander linear layer is to store the weight matrix W as a sparse matrix. However, due the known issue inefficiency of hardware acceleration on sparse matrices (Wen et al./ 2016), we use masks, similar to those of pruning algorithms, to achieve the sparsification.
mask M E {0, 1) S, x is of the same dimension as weight matrix and Mu, 1 if and only if (u, v) E EE' An entrywise multiplication is then applied the mask and the weight matrix so that undesired parameters in the weight matrix are removed, i.c., Equation (3) can be rewritten as,
(1) O W()). (y())...M(4 (()),,
(4)
where @ denotes the Hadamard product. Theoretically, replacing fully connected linear layers by expander linear layers should both save memory cost and speed up computation. However, this practical implementation, which is adapted to current hardware constraints, worsens the computation time slightly by adding new operations. Contrariwise, the inference computation time is significantly improved by the sparsification. This behaviour of the training and inference time is shared with many pruning approaches, where the training time is increased and the significant time saving comes at the inference stage (Frankle & Carbin 2019). In Section 4.2 we observe this effect in practice.
5

---

Under review as a conference paper at ICLR 2021
3.3 AN EXTREME CASE: ACTIVATION- ONLY GNN
A natural extension for the Expander GNN is to consider the extreme case where linear transformation layer is removed by removing the trainable weight matrix W from the update step. [aama al. (2020) argue that the non-linearity present in GNNs, in form of the activation functions, has the effect of frequency mixing in the sense that "part of the energy associated with large cigenvalues" is brought "towards low eigenvalues where it can be discriminated by stable graph filters." This theoretical insight that activation functions help capture information stored in the high energy part of graph signals is strong motivation to consider the extreme case, which we refer to as the Activation-One Only GNN models, in which each mnessage-passing step is immediately followed by pointwise activation function and the linear transformation of the update step is forgone. Hence, in Activation-Only GNN, Equation
B will be rewritten as,
H = oo (AH
(5)
This proposed simplification is applicable to a wide variety GNN models, whose extract formula- tions can be found in Appendix C.3 al. 2019).
For comparison we display the model equation of the SGC (Wu
H (
where W W(L), Here the nonlinear activation functions have been removed and the linear transformations have been collapsed into single linear transformation layer. Interestingly, observe that the repeated application of the symmetric matrix Á to the input data X is equivalent to an unnormalised version of the power method approximating the eigenvector corresponding to the largest eigenvalue of Á. Hence, if sufficiently many layers I, are used then inference drawn in the SGC model simply on the basis of the first cigenvector of A.
4 EXPERIMENTS AND DISCUSSION
In this section, we empirically study the impact of the Update step on model performance. Specifically, in Section[4.] we provide an overview of the experimentation setup and the vanilla GNNs we compare against. Then, in Sections 4.2 4.3 and 4.4 we observe the performance of the proposed benchmark models on the tasks of graph classification, graph regression and node classification, respectively. The full set of results can be found in Appendix A.3 In Section 4.5 we compare the performance of Expander GNNs and vanilla GNNs when they have equally many parameters.
4.1 GENERAL SETTINGS AND BASELINES
We experiment on eleven datasets from areas such as chemistry, social networks, computer vision and academic citation, for three major graph learning tasks. Details of the used datasets can be found in Appendix C.. Throughout this section we refer to the standard, already published, architectures as "vanilla" architectures. We compare the performance of the vanilla GNN models, the Expander GNN models with different densities (10% 50%, 90%), the Activation Only GNN models with different activation functions (ReLU, PReLU, Tanh), as well the SGC for the GCN models.
To ensure that our inference is not specific to a certain GNN architecture only, we evaluate the performance across representative GNN models of the literature state-of-the-art, The considered models are the Graph Convolutional Network (GCN, Kipf & Welling (201))(0))) (2017), the Graph Isomorphism Network (GIN, Xu et al. (2019)). the GraphSage Network (Hamilton et al. (0017). and the Principle Neighborhood Aggeragation (PNA, Corso et al. (2020)), along with a ML. baseline that only takes the node features into account while ignoring the graph structure. The Activation-Oni) model class is defined in the context of GNN architecture and cannot be sensibly extrapolated to the MLP. Therefore, we consider only the vanilla and Expander variants for the MLP benchmark.
Since we aim to observe the performance of our benchmark models independent of the GNN choice we use the model hyperparameters found to yield a fair comparison of GNN models in Dwivedi et al. (2020). Other experiment details, such as the choice of loss functions for different tasks, dataset splits as well as the extact message- message-passing formulation of the models we studied and their variants can be found in Appendix C

---

Under review as a conference paper at ICLR 2021
ENZYMES
DD
Proteins
PROTEINS (GCN)
944
70-
00-
40
23-
20-
8.30
12-
3:34
IMDO-BINARY
MNIST
CIFAR10
PROTEINS (GCN)
100
20
202
Figure 1: (a,b.c.e): Accuracy of different model types for GCN, GIN and MLP on ENZYMESIDDPROTENNSII BITFIINS/MDDBBBIAARY.. (f.g): Accuracy of different model types for GCN, GIN and MLP on MNIST/CIFARIO, I0; (d): Training time (per epoch) of different model type for GCN on PROTEINS; (h): Number of parameters required for GCN on PROTEINS.
4.2 GRAPH CLASSIFICATION
Figure Ia). (b), (c) and (c) show the experiment results of the GCN, GIN and MLP models and their Expander and Activation-Only variants on the ENZYMES, DD, PROTEINS and IMDB-BINARY datasets for graph classification. The evaluation metric is classification accuracy, where the average accuracy, obtained from a 10-folder cross validation, is used.
One direct observation from Figure (b), (c) and (e) is that the Expander GNN models, even at 10% density, perform on par with the vanilla models. Surprisingly, the same is true for the Activation- Only model on the ENZYMES, DD and PROTEINS datasets. IMDB-BINARY is our only graph classification dataset where the node attributes are initialised to all be equal. This uninformative initialisation, surprisingly, seems to lead to an increased performance if the lincar update step is present, visible in the performance gap of the Activation-Onf models and the Expander GCN models. While for GIN model we still observe the Activation-Only model and to match the performance of the Expander GIN. Different activation functions often do not cause significantly different results. However, in a few cases The influence of different activation functions is non-negligible only in few cases, e.g., in Figure (c) the PReLU activation model outperforms the Tanh activation. The SGC performs either on par or worse than the Activation-Onle model.
It is a known fact that the simple MLP can achieve better performance than GNNs (Luzhnica et al. 2019) on the several of the TU datasets, Dwivedi al. (2020) have shown that more complex GNN models can outperform the MLP on the aforementioned datasets. However, this known shortcoming has no impact on our conclusion, where we compare model performance within a GNN model class rather than between GNN model classes.
In Figure d and (h) we observe the Activation-Onis model to be comparable to the SGC in computation time and in the scale of model parameters. Both models are significantly more efficient than vanilla and Expander models. As stated Section 3.2.2 the training time efficiency of the Expander GNN models is slightly less than that of the vanilla models as is expected in the training of a sparsified architecture.
Figure 1t) and (g) show the graph classification results for the MNIST and CIFAR10 datasets. Interestingly, the GCN Activation- Only model outperforms the SGC by a larger margin than we observed on the TU datasets. It seems that especially for these computer vision datasets the presence of activation functions in the GCN architecture has a large positive impact on model performance in the graph classification task.
7

---

Under review as a conference paper at ICLR 2021
CORA
OTESEER
PUBMED
ogim-arary
14
60
70
30
0.7 ZINC
2.-
20
72-
48
12
Artiation PoLLi
Tacls
Pacseber
Vendo
Figure 2:
(a,b,c,d): Accuracy of different model types for GCN/GIN/MLP COOLWCTESEERPPBBEEDob......
datasets; (e): Mean Absolute Error of different model types for GCNGGINGrrphSgg//PAANN
ZINC dataset; (f.g.h): Accuracy vs. number of
parameters plot on a logarithmic x-axis on (f) ogbn-arxiv for GCN models with different sparsifiers
and (g.h) CITESEER/PUBMED for vanilla and Expander GCN with same parameter budget.
In summary, almost for all graph classification datasets we find the linear transformation in the update step of the GCN and GIN make little to positive contribution the model performance. The activation function in the update step however turns out to be great importance on the vision datasets, where as for the TU collection it seems be of little consequence. Overall, the Activation-Only benchmark outperforms the SGC on all observed datasets.
4.3 GRAPH REGRESSION
In Figure aa)) the Mean Absolute Error (MAE) of our studied and proposed models on the ZINC dataset for graph regression is displayed. Similar to the graph classification task, the Expander GCN and GraphSage models are on the same level with vanilla models, regardless of their densities. The performance of the Expander GIN and PNA models exhibits greater variance accross the different densities, especially in the case of PNA models the performance is increasing as the network gets denser indicating that the density of the Update step does positively contribute to the model performance of the PNA for the task of graph regression on the ZINC dataset. The Activation-Oni this task, again confirming the insight
models perform worse than their Expander counterparts from the results the Expander GNNs that the linear transform in the update step does improve performance in this graph regression task. Again we see that Activation- Only GCNs outperform the SGC benchmark in this set of experiments.
Hence, for the task of graph regression observe that both the linear transformation and non-linear activation function in the Update step have a positive impact on model performance. We might have been able expect that the addition of the transformation performed in the Update step is of greater impact in regression task, which is evaluated on continuous scale, than in a classification task, where only discrete label needs to inferred.
4.4 NODE CLASSIFICATION
Results from the node classification experiments four citation graphs (CORA, CITESEER, PUBMED and ogbn-arxiv) can be found in Figure aa),, (b), (c) and (d), respectively. For medium- have the same observation with the graph classification and graph regression tasks discussed in Sections 4.2 and 4.3) the Expander mod- els, regardless of their sparsity, performing on par with the vanilla ones. Only the CITESEER
sized datasets such CORA, CITESEER and PUBMED,
8

---

Under review as a conference paper at ICLR 2021
dataset, observe that the GIN Expander model with 10% density shows small but non negligible drop in performance compared to the vanilla model; while the 50% and 90% dense Expander models remain comparable to the vanilla one. The Activation- Only models also perform well as better than (on CITESEER) the vanilla model. The performance of the GCN Activation Onll model and SGC are equally good across all three datasets.
These conclusions remain true for large-scale datasets like ogbn-arxiv with 169,343 nodes and 1,166,243 edges. The ExpanderGCNs are on par with the vanilla GCN while the Activation-Onl model and SGC perform slightly worse. However, the training time of Activation-Oni model and SGC five times faster than that of the Expander and vanilla models. The PReLU Activation Only model performs better than the SGC, while the other two Activation Only models do worse.
We observe that in the node classification task both the linear transformation and the non-linear activation function offer no benefit for the medium scale datasets. For the large-scale dataset we find that the linear transformation can be sparsified heavily without loss in performance, but deleting entirely does worsen model performance.
4.5 SPARSIFICATION VS. SHRINKAGE
In Figure (f) we compare the results from an ExpanderGCN to the those achieved by a GCN model, where the Expander Linear Layer, presented in Definition 2 is replaced by deterministic sparsificsftion construction from Bourely et al. (0177) the "Regular Rotating Edge Construction" (RREC). [Bourely et al. (2017) observe that sparsifiers obtained from the RREC sampler have significantly lower algrbraic connectivity than the Expander Linear Layer sampler which we chose to utilise in the Expander GNNs. We observe that Expander GCNs outperform the RREC sampled GCN for almost all parameter budgets. Therefore, we confirm that the Expander Linear Layer is an appropriate choice for the Expander GNN model class.
The experiments in Sections 4.2 4.3 and 4.4 show that the linear transform layer in the Update step of GNN can be sparsified to an arbitrary level without loss of performance. From this a natural question then arises: Will shrunk model, i.e., model with smaller hidden dimension used in the Update step, matching the number of parameters of the sparsified Expander GNN, perform on par with its Expander GNN counterpart?
To study this question we compare the performance of vanilla GCNs to Expander GCNs with equally many parameters, but doubling the size of the hidden dimension of the vanilla GCN. Figure (g) and (h) show the experiment results on two citation datasets. We observe that for most parameter values the Expander GCN outperforms the vanilla GCN. This phenomenon becomes more evident when the number of parameter is small. In conclusion, it seems to always be beneficial to choose a sparsified large model rather than compact model with equally many parameters.
5 CONCLUSION
With extensive experiments across different GNN models and graph learning tasks, we are able to confirm that the Update step can be sparsified heavily without a significant performance cost. In fact for seven of the eleven tested datasets across variety of tasks we found that the linear transform can be removed entirely without loss in performance, i.c., the ActivationnOniy models performed on par with their vanilla counterparts. The Activation GCN model consistently outperformed the SGC model and especially in the computer vision datasets we witnessed that the activation functions seem to be crucial for good model performance accounting for an accuracy difference of up to 59%. These findings partially support the hypothesis by Wu et al.] (2019) that the update step can be simplified significantly without a loss performance. Contrary to Wu et al. (2019) we find that the nonlinear activation functions result in significant accuracy boost and the linear transformation in the update step can be removed or heavily sparsified.
The Activation-Onie GNN is an effective and simple benchmark model framework for any message passing neural network. It enables practitioners to test whether they can cut the large amount of model parameters used in the linear transform of the update steps. If the linear transform does contribute positively to the model's 's performance then the Expander GNNs provide a model class of tunable sparsity which allows efficient parameter usage.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Helmut Bölcskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, pp- 4-4,, 2019.
Alfred Bourely, John Patrick Boueri, and Krzysztof Choromonski. Sparse neural networks topologies. wrXiv:1706005633 2017.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection graph classification, 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. TrXiv:2004.057/36 2020.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224 2232, 2015.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv:2003, 00982, 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.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. 7th International Conference on Learning Representations (ICLR), 2019.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Stability of graph neural networks to relative perturbations. International Conference on Acoustics, Speech, and Signal Processing (ICASSP). pp. 9070 9074. IEEE, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning (ICML). pp. 1263 1272, 2017.
Alessandra Griffa, Benjamin Ricaud, Kirell Benzi, Xavier Bresson, Alessandro Daducei, Pierre Vandergheynst, Jean-Philippe Thiran, and Patric Hagmann. Transient networks of spatio-temporal connectivity map communication pathways in brain functional systems. Neurolmage, pp. 490 502. 2017.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the s1 International Conference on Neural Information Processing Systems (NIPS), pp. 1025 - 1035. Curran Associates Inc., 2017.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Light- gen: Simplifying and powering graph convolution network for recommendation. arXiv preprint arXiv:2002.021226 2020.
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, pp. 439 -611, 2006.
Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zine: free tool to discover chemistry for biology. Journal of chemical information and modeling, pp. 1757 1768, 2012.
10

---

Under review as a conference paper at ICLR 2021
Jeremy Kepner and Ryan Robinett. Radix-net: Structured sparse matrices for deep neural networks. In 2019 JEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 268 274. IEEE, 2019.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. http:://rrapkkrrsgn cs. tu tu-dou---oooooo doorumndd.. de
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations (ICLR), 2017.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems 32, pp. 4202 4212. Curran Associates, Inc., 2019.
Alexander Lubotzky. Expander graphs in pure and applied mathematics. Bulletin of the American Mathematical Society, pp. 113 162, 2012.
Enxhell Luzhnica, Ben Day, and Pietro Liò. On graph classification networks, datasets and baselines. In Workshop on Learning and Reasoning with Graph-Structtured Data (ICML), 2019.
Andrew WE McDonald and Ali Shokoufandeh. Sparse super-regular networks. In 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pp. 1764 1770. IEEE, 2019.
Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M Bronstein. Fake news detection social media using geometric deep learning. arXiv:1902.06673. 2019.
Ameya Prabhu, Girish Varma, and Anoop Namboodiri. Deep expander networks: Efficient deep networks from graph theory. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 20 35, 2018.
Guillaume Salha, Romain Hennequin, and Michalis Vazirgiannis. Keep it simple: Graph autoencoders without graph convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Guillaume Salha, Romain Hennequin, and Michalis Vazirgiannis. Simple and effective graph autoencoders with one-hop linear models. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery Databases (ECML-PKID)), 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, pp. 93 93, 2008.
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv:2006.0544 2020.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Wu, Yuxiao Dong. and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1): 396-413, 2020. doi: 10.1 (a1162/gsssaa/ at 00021. URL htl.ttts:: http:://doooooooo /t//o/.org//....o 116.0.......... _ss_a_
00021
Vikram Waradpande, Daniel Kudenko, and Megha Khosla. Deep reinforcement learning with graph-based state representations. arXiv preprint arXiv:2004.1300 13965,, 2020.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, pp. 2074-2082, 2016.
Felix Wu, Amauri H Souza Jr, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In 7th International Conference Machine Learning (ICLR), 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, pp. 21, 2020.
11

---

Under review as a conference paper at ICLR 2021
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations (ICLR), 2019.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 7370 7377, 2019.
12

---

Under review as a conference paper at ICLR 2021
APPENDIX
A COMPLETE EXPERIMENT RESULTS
A.1 GRAPH CLASSIFICATION
Table Full results of GCN/GIN/LLP on Four TU Datasets
ENZYMES
DD
ACC
Time Epochós)
#Parameters
ACC
Time per Epochis)
#Parzmetees
Simple
GCN
63.07 + 8.06
0.2004
57853
75.90
3.93
1.3541
43643
74.79
6.71
0.2486
GCN
rela
66.33 + 5.31
0.2132
37853
74.88 3.41
1.3915
sela
66.17 + 6.99
0.206
75.64 4.54
1.3948
Activations
65.67 7.04
0,2154
76.57 5,20
Jelu
52.17 + 5.78
0.3219
70.12 4.30
1,644
pretu
0,3531
69.19
51,00
5.88
0,3122
70.03 3.27
sela
53.83 + 7.34
0.3201
72.49 4,30
1.6772
softshrnk
$6,83
7.97
0.3165
71.22 3.39
1.6558
10%
66.33 + 6.78
0.2863
22775
74.53
3.50
1.5731
210664
GCN
50%
64.83 +
0.285
58203
74.28
2.52
1.5856
56960
90%
0.2917
93209
75.13
65.83 1: 7.75
0,379
8918
68.59
2.70
1.6605
6730
Expander
GIN
50%
67.00 + 6.05
0.3822
20070
70.03
4.20
14647
28789
90%
67.50 +: 5.74
0.3729
49222
68.93
3.26
50335
MLP
30%
74.07
+ 5.72
0.1783
39661
70.66
2.69
1.07
58020
90%
73.17 1: 7.65
0.1772
92811
76.24
3.80
1.0621
91631
Vanilla
GIN
67.67
7.68
0,3692
S4260
68.76
5.55
1.6522
55978
MLP
74.17
+ 6.34
0.1646
101481
77.43
3.98
1.0533
108447
PROTEINS
IMDB-BINARY
Time per Epoch(s)
#Pammeetess
Time per Epochts)
PPorametess
Simple
0,3374
0.3297
0,3464
61.30
prelu
75.29 1 4.85
0,3654
61.00 3.92
0.388
GCN
rolu
76.48 + 4.61
0.348
3031
61.90 4.01
0.3497
31499
softshrink
70.53 + 3.27
0,3462
50.00 0.00
0.344
Activations
tanh
70.89 + 2.70
0,3452
61.20 4.56
0.3522
70.34 4.78
0,5144
69.50 3.88
relu
68.62 +: 5.97
0,4897
67.90 3.96
0.5262
GIN
4410
1282
0,438)
60.00
softstzink
3.06
0,4929
69.20
sanh
71,96 + 4.26
0.494
67.30 5.62
0.5233
10%
76.55
150
0.4524
22781
71.60 5.50
0.4673
19920
GCN
76.36
55048
90%
75.38 + 4.01
0.4476
94502
72.30
6.65
014835
813113
10%
70.53 + 3.06
0.5481
6819
72.00
6.16
0.6968
5890
Expander
27455
90%
70.71
2.55
0,5655
48091
70.30
0.6127
41975
10%
69.00
+ 4.99
0.2856
25453
50.00
0.00
0.357
22558
50%
64.15
4.32
0,2852
58928
50.00
0.00
0.2896
$1244
50.00
GCN
76.73 4 3.85
0,4388
1036977
72.70
3.68
0.4433
89045
Vanilla
GIN
72.51
2.39
0,5309
53250
69.00 6.23
0.6135
46650
13

---

Under review as a conference paper at ICLR 2021
Table 2: Full results of GCN/GIN/MLP on Computer Vision datasets (MNIST/CIFARIO)
MNIST Time per Epochis)
CIBARIO
ACC
#Parameters
ACC
Time per Epochis)
MParameters
Simple
27.90
Ieha
83.52
48.5
GCN
prolu
83.84
103.11
47.90
41,3494
14641
reln
83.16
102 102.445
48.27
40.2591
77.67
Ieha
75.68
119.803
37.90
44.6216
Activations
GIN
poelu
71.60
115.862
5990
36.48
46.0211
6210
nolu
75.23
119 081
38.67
43.0776
teals
10%
$9.00
124.411
22713
50.27
45 0057
22741
GCN
50%
90.75
124.075
57346
50.69
45.1236
57492
10%
88.73
120.735
10973
35.93
44,4764
10695
Expunder
GIN
50%
92.31
119.554
30465
40.35
44.537
30575
10%
94.97
67.2461
31
27012
MI.P
50%
96.04
66 66.9236
61456
58.12
31.6178
61621
90%
66.7391
95425
58.85
33.6307
95727
90.77
134.991
52.04
44.337
Vanilla
GIN
90.33
120. 191
$4830
42.46
45.3386
55050
MLP
96.17
66.125
104044
58.66
31.5435
104380
14

---

Under review as a conference paper at ICLR 2021
A.2 GRAPH REGRESSION
Table 3: Full results of GCNVGIVVGrappsSeeee/NAAALLL on Molecule dataset (ZINC)
ZINC
Time per Epoch(s)
#Parameters
Simple
1,9847
34347
Iclu
0.5947
1.8624
prelu
0.5855
1,9273
relu
0.5967
1,8407
GCN
13177
selu
0.6128
1.8581
softshrink
0.6549
1,8574
tanh
0. 0.6086
1,8639
lelu
0.5368
2,8046
prelu
0.5743
2,8826
0.5524
2,8009
GIN
555
softshiik
tamh
0.5354
2,8263
Activations
lelu
0.4937
4,1406
prelu
0.494
4,3778
relu
0.4907
4.1238
GraphSage
selu
0.5365
4,1293
softshrink
I 15558
4,1428
tanh
0. 0.5665
4.121
lelu
0.5181
27.9922
prolu
0.5038
28. 1269
28.0074
PNA
3515
softshrink
0.5374
28.0993
tanh
0.4493
27,9598
10%
0.3958
2,5833
21877
GCN
50%
0.3856
2,5793
55517
90%
0.3845
2.5578
89157
10%
0,4888
3,0905
5835
GIN
50%
0.5274
3,1125
25195
90%
0.4456
3.0852
44555
10%
0.4721
4,461
11970
Expander
GraphSage
10%
0.6931
2,1455
23775
MLP
50%
0.6898
2,1426
59775
90%
0.6873
2,1.42
95775
10%
0.3798
32,0922
23735
PNA
50%
0.3384
32.148
102495
90%
0.2946
32,0666
181255
GCN
0.3823
2,5538
97857
GIN
0.4939
3,0569
49395
Vanilla
GraphSage
0.45226
15

---

Under review as a conference paper at ICLR 2021
A.3 NODE CLASSIFICATION
Table 4: Full results of GCN/GINMMLP on Three Citations dataset
CORA
CITESEER
ACC
Time per Epochis)
Paarameeess
Time per Fjoch(ss
aParamtters
Simple
0.0088
10038
72.70
22234
50.40
0.000
0.0112
10EES
72.70
0.00
0.0159
22224
GCN
rala
80.40 = 0.00
0.0888
10038
72.70 0.00
0.0124
22224
Activations
1003S
75:42 0.97
0.0244
30114
66.70
0.65
0,0211
86672
GIN
rola
75.42 = 0.97
00117
30114
66 70 0.65
0.0202
66672
30114
GCN
30%
80.42 + 0.28
0.0228
183351
69.43 + 0.34
0,0278
475654
90%
80.82 0,23
0.0213
332039
69.42 0.26
0.0259
854790
$7156
Expander
GIN
50%
77.06 0.81
0.017
230212
67.24 0.49
0,0253
532444
90%
77.36 + 1.40
0.0677
40R012
68.31
0.70
0.0229
937892
38063
MLP
50%
53.57
0.53
001111
185351
52.53
1.25
0.0175
475654
90%
54.06 =: 0.88
0.0102
332039
52.34
4: 1.64
0.0154
854790
0.0722
368903
69.
0.19
0.0194
949766
Vanilla
0.0126
446532
68.
MLP
53.21
1.69
0.0061
368903
52.44
1.71
0.0086
949766
PUBMED
ughn-arsiv
Time per Fpocc(s)
PParameters
ACC
Time per Fjoch(s)
iParameters
Simple
1303
0,050)
prelu
78.90.2 0.00
0.0201
1503
68.291: 0.13
0,0603
5160
GCN
relu
78. 90:2 0.00
0.0556
1903
63.0742 0.09
0,0519
$160
Activations
1anh
78 78.83
00157
1503
65.51
0,0518
5160
76.38.2
0,0255
4509
54,451:
15490
GIN
relu
76.46-B 1.12
0.0235
4509
$2.21 4: 3.47
0,071
15480
1anh
77.46:1
0.0266
4509
64.101 0.32
0.0711
15480
20392
GUN
50%
79. 79:34:2 0.28
0.4246
65027
71 0.55
0,2681
59944
90%
79.17 0.25
0.0236
116227
71.22: 0.71
0.2732
99112
22757
52768
Expander
GIN
50%
76.06:1 1.14
0.024
100325
69.1111 0.86
0,2742
1| 118688
90%
76.50:1 0.73
0.0236
177637
67.54:1 3.91
0.274
183968
10%
69.43:2
0.142
51.77:1
0.1109
20392
MLP
09.34:2
65027
54.83-2
0.1106
599444
90%
68.78:8 1.56
0.0145
116227
55.55 0.08
0.1107
99112
GUN
79.04:4 0.12
0.0215
129612
71.22: 0.76
0.2713
109056
Regular
MTP
68.872
1.78
0.0129
129027
55.6342 0.11
0.1098
100096
16

---

Under review as a conference paper at ICLR 2021
A.4
CONVERGE BEHAVIOR: AN EXAMPLE OF GCN ON PROTEINS DATASET
GCN
Activalion-Rdl GCN
Actvalions-RRal GCN
Activalkos-Tam BCN
Expanter-
Train (Log scclll
Expander:90% GCN Vanill GCN
10"
10"
50
100
150
200 #Epochs
250
300
350
400
Figure Train loss (cross-entropy) converging behaviour of different model type for GCN on Proteins dataset.
Figure exhhibit the loss convergence in training of GCN model class on PROTEINS dataset. We implement learning rate decay scheme and terminate the training process when learning rate drops to preset minimum value. Then if a model terminates ealier than its alternatives. it indicates that this model converges faster. we can see from the figure, Activation Only and SGC both terminate the process with less epochs than vanilla and Expander models. Similar to the main paper, we are able to draw the conclusion that Activation and SGC do not only have fewer parameters but that their training also converges faster, hence more efficient in time.
B ILLSTRATION OF EXPANDER MPNNS
Iteration
Iteration
Iteration
Aggregation
Update
Figure 4: Illustraioon of Expander MPNNs. The left part is the Aggregation or graph propagation step and the right part is theU/date step. The red lines on the left part represents preserved connections in MLPs sampled by expander sparsifier.
17

---

Under review as a conference paper at ICLR 2021
C EXTRA INFORMATION FOR EXPERIMENTS AND MODELS
C.I. DATASET DETAILS
Table 5: Properties of all datasets used in experiments.
Dataset
#Graphs
#Nodes (avg.)
#fidges (avg.)
Task
ENZYMES
600
32.63
62.14
DD
1178
284.32
715.66
datasets
PROTEINS
1113
39.06
72.82
Graph Classification
MNDB-IINARY
1000
19.77
193.06
MNIST
70K
70.57
282.27
Computer Vision
CIFARIO
60K
117.63
470.53
ZINC
12K
23.16
24.92
Graph Regression
CORA
2708
5278
CITESEER
3327
4552
Citations
Node Classification
PUBMED
1
19717
44324
ogbn-arxiv
169343
1166243
Differed on the learning tasks, the datasets we use can be classified into three categories. For graph classification, we have four TU datasets (Kersting al. 2016) which are either chemical or social network graphs, and two Image datasets (MNIST/CIFAR that constructed from original images following the procedure in Knyazev et al.] (2019). To perform this conversion they first extract small regions of homogeneous intensity from the images, named "Suuerpixels" (Dwivedi et al. 2020), and construct a K-nearest neighbour graph from these superpixels. The technique we implemented to extract superpixels, the choice of K and distance kernel for constructing nearest neighbour graph are the same as in Knyazev et al. (2019) and Dwivedi et al. 2020). For graph regression, we consider four
molecule graphs from the ZINC dataset (Irwin al. 2012) And for node classification,
citation datasets (Sen et al. 2008 Wang et al. 2020 Hu et al 2020), where the nodes are academic
articles linked by citations.
In Table we summarise the statistics of the aforementioned eleven datasets in detail. We display their number of graphs, number of nodes and of edges, as well as the tasks that are performed on them. In the number of nodes and edges column we show the values, or the average of these values if there are multiple graphs.
C.2 EXPERIMENT SETTINGS
In order ensure fair comparison across different GNN models, follow the recent bench- mark proposed in Dwivedi et al. (2020). Specifically, we use their datasets on computer vision (MNIST/CIFARII 10) and chemistry (TU datasets/ZINC dataset); follow the same training proce- dure, such as train/valid/test dataset splits, choice of optimiser, learning rate decay scheme, etc., as well the same typer-parametent such as initial learning rate, hidden feature dimensions, number of GNN layers, etc. We also implement the same normalisation tricks such as adding batch normalisation after non-linearit of each Update step. Their setting files (training procedue/hypprrprameeee are made public and can be found in this repository
For the node classification task on citation datasets, we follow the settings from Wu al. (2019). Our experiments found that the node classification task on citation graphs of smal/medium size can be easily overfit and model performances heavily depend on the choice hyperparameters. Using the same parameters with Wu et al. (2019), such as learning rate, number of training epochs and number of GNN layers, helps us achieve similar results with the paper on the same model, which allows fair comparison between the proposed Activation- Ciaivatioo-Ollyy models and the SGC.
C.3 MODEL DETAILS: GNNS UNDER THE MPNN FRAMEWORK
we present the message- message-passing GNN framework and explained the ideas which drive the Expander and Activation Only models that proposed. These ideas illustrated by example of GCN. In this section, we will recall the MPNN formulation. Normalisation layers such as batch normalisation are omitted in the formulation for the purpose of clarity. For each of the models,
In Section 3
18

---

Under review as a conference paper at ICLR 2021
present their vanilla version, Expander version and Activation Only version. As stated in Section we ignore the various variants of vanilla models and only work with variants of simple forms.
C.3.1 GRAPH CONVOLUTIONAL NETWORK
Vanilla GCN and Expander GCN We have shown the matrix form of Aggregation and Update iterations GCN in the main paper. Here we are going to revisit the message message-passing procedure in GCN from the angle of single node. At iteration 1,
(1) m.
(1) h
deg, JEN(()
deg,
h
(1+1) = (m, (9) ( W(),
where (()) the weight matrix (th linear transform layer and M (0) its corresponding mask. For vanilla GCNs, all entry of M is while for Expander GNN M sparse matrix. Equation (6) the Aggregation step, which constructs "messgae" equivalent to weighted average of neighbours
embeddings, then Equation ( Updates node i's representation based on constructed "message".
Activation-Only GCN
The Activation- model can then simply be written as,
h (4+1
V deg.
V deg,
JEN(
C.3.2 GRAPH ISOMORPHISM NETWORK
Vanilla GIN and Expander GIN The message- procedure of GIN is very similar to GCN, except that at the Aggregation step, it adds explicitly learnable ratio of the central node's own representation, defined as,
m 1 = (1+
Σ h
JEN(()
Its Update step is the same with Equation
Activation-Only GIN Similar to GCN, the Activation Only model can then be written as,
(1+1) =a (1+c)h + ++++, n )
JEN(S)
C.3.3 GRAPHSAGE NETWORK
Vanilla GraphSAGE and Expander GraphSAGE GraphSage also incorporates explicitly the central node's ' representation in the Aggregation step by concatenation. Their message-passing procedure is,
m (1)
-h1"
M w("). ((+1)
(9)
(1+1)
h
(1+1)
h
= am M
W!"),
(10)
(1+1)
112
where || denotes concatenation and MAX function takes maximum along each feature dimension.
Activation-Only GraphSAGE In Activation- Onll models for GraphSage, need to consider the issue of dimension incoherence after removing linear transforms. Since a simple removal of linear transforms will result in exponential growth in the dimension of hidden representation. One
19

---

Under review as a conference paper at ICLR 2021
convenient solution is replace concatenation with summation that the dimension of either or h remains unchanged after the iteration. The message-passinng passing steps then become,
m
h1 + MAX (A
(11)
h; (1+1)
h (1+1)
h
(I+1)
=a(m; (1)
(12)
1/2
A more complex way is to separate the propagation and update of "message" m and hidden represen- tation h. More precisely,
m MAX
( (1-1))
m; h!"
(13)
h; (1+1)
h (1+1)
h. (1+1) h: = (h! m ()),
(1+1)
(14)
where the dimension of h; grows proportionally to the number of iterations. Neither of the methods wut-weighted by the other based evidence from empirical experiments. However, from economic view on developping parsimonious GNN, Equation 11 is our preferred method.
C.3.4 PRINCIPAL NEIGHBOURHOOD AGGREGATION
Vanilla PNA and Expander PNA The PNA model concatenates in its Aggregation step the "mes- sages" obtained from different combinations of scalars and aggregators. This step can be written as (Fey & Lenssen 2019)
m (1)
a(h M o w(),
(15)
JEN(1)
where + is defined the outer product, denoted by @, of the arrays of scalars and aggregators, with cardinality oj and C2, respectively, as follow,
mean std max
1 S(D S(D.
a
X
min
scalars
aggregators
The Update step is the same as Equation
Activation-Only PNA Similar to the Activation-Oni GraphSage, the Activation-Only PNA also suffers from dimension incoherence issue, due to the concatenate operation. Instead concatenation, take the average of each representation obtained from combination of scaler and aggregator in Activation-Only models. Then the message-passing procedure becomes,
h
(++1
Σ
T
a an
C102
jEN(()
where denotes the number of scalars and denotes the number of aggregators used in the PNA.
C.3.5
GRAPII-AGNOSII BASELINE: MULTI-LAYER PERCEPTRON
Vanilla MLP and Expander MLP The MLP baseline has Aggregation steps. Its Update step is simply,
h ((+1)
(h) (1) M() @ w())
20

---

Under review as a conference paper at ICLR 2021
C.4 LOsS FUNCTIONS FOR DIFFERENT TASKS
After L message-passing iterations, we obtain H h1
(L) hn DiT E Raadd as the final node
embedding, where denote d its feature dimension. Depending on downstream tasks, either keep working with (I.) or construct graph-level representation g from H by,
π2
KEV
which is refer to as the Readout step in Section
g or (L)) is then fed into a fully-connected network (MLP) to be transformed into the desired form of output for further assessment, i.e., scalar value as prediction scores for graph regression. We denote this network as f(-), which, in our experiments, is fixed to be a three-layer MLP of the form
f()) (als W2) W3.
where W, E Rdx(E), W2 E RII W3 E x with k being the desired output dimension.
The final output, either ((g) or ((H(4)), is compared to the ground-truth by a task-specific loss function. For graph classification and node classification, we choose cross-entropy loss and for graph
regression, we use mean absolute eπror (or the L1 loss).
21


Reviews:
[{"review_id": "yn9_H4V90nq", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Post response update:**\nI would like to thank the authors for their response and revision addressing my concerns, at least to some extent. However, after careful consideration as well as looking at the other reviews (and responses), I am still not convinced the case can be made for increasing the score beyond marginal leaning towards accept, which was the original score I have marked for the paper. The paper does provide some interesting empirical evidence showing that GNNs can be simplified to by sparsifying, or even removing, the learned weights for combining different channels between message passing steps. However, this kind of simplification is not particular to GNNs (indeed, many popular network architectures are overparameterized and can be significantly sparsified), and has little effect on the incorporation of graph structure in the network. The activation-only experiments are perhaps more specific to GNNs, but on the other had, they mostly establish the importance of message passing, which has already been pretty well established in previous work (together with certain well described limitations of current designs). As other reviewers indicated, the insights provided here are intriguing, but it is not clear whether they meet the level of significance and impact expected from an ICLR publication. \n\n---\n\nMost popular graph neural networks (GNN) can be formulated as combining learned transformations between node features on graphs, parametrized by GNN weights, and nonlearned aggregation of information within neighborhoods determined by the graph structure. While most work on GNN focuses on how to improve the aggregation of information (for example, with message passing, convolutional graph filters, etc.), this work examines the redundancy in overparameterized network weights and shows it can often be significantly sparsified with relatively minor effect on network task performance, such as classification or regression accuracy. This, in turn, can lead to simpler models, with significantly less trained parameters, which in turn also leads to more efficient training process. The study here establishes this trend via extensive empirical study, using expander graph based sparsification of neural network weights (via modeling of neuron connections in each layer as a bipartite graph) following the sampling procedure proposed in Prabhu et al. (2018).\n\nMy main criticism of the paper is that it offers little insight specific to GNNs. Indeed, the so-called \"Update\" step considered here is essentially a way to mix together different channels of information at a node-wise level without considering graph structure, which is mainly used and encoded by the so-called \"Aggregate\" step in GNNs. As such, the sparsification here is not much different from the typical sparsification approaches applied to feed forward (or other) neural networks. It is generally a well accepted understanding in deep learning that neural networks are often unnecessarily overparameterized, and most of them can easily be pruned or sparsified (at least to some extent) without significantly degrading their task-specific results. Moreover, while several architectures are considered here (GCN, GIN, and standard MLP to provide a non-GNN baseline), it is not clear how well optimized the hyperparameters are for these networks prior to pruning. Are these networks as compact as they can be? or perhaps further tuning could also achieve a smaller network with roughly the same performance that doesn't need sparsification. Furthermore, the authors only consider a specific sparsification approach, but it seems to me that pretty much any sparsification or pruning approach could be applied here. How does the sparsification strategy affect the results? Perhaps a comparison of several sparsifiers could help establish the main argument of the paper, or justify the use of expander-graph sparsification, even though the graph here has nothing to do with the underlying data graph.\n\nHowever, all that being said, the paper does provide evidence showing that with very few weights (or even no learned weights at all), GNNs are able to retain reasonable results, indicating some information is extracted solely by the message passing regardless of the trained network components. The discussion here is framed as following up on indications and ideas provided by Wu et al. (2019), and it is effective in this respect. Therefore, there may be some value in continuing to push the discussion along the research line here, to promote the study and better understanding of the impact different components have on the performance of GNNs. With this in mind, I consider this paper a borderline case, while slightly leaning towards acceptance in order to give the authors an opportunity to improve the presentation here by considering and studying the impact of sparsification strategies and presparsification hyperparameter tuning on presented results, in order to address my concerns mentioned above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "olDx-NNqHMM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Analysing the update step in graph neural networks via sparsification\n\nSummary:\n\nThe paper is focused on the Update step in a message passing (graph convolution) neural network. Several sparse variants of the update step, including its complete removal and expander graphs with varying density, are compared in a thorough and comprehensive empirical study. \n\nPositive:\n\n1. The paper is quite well written and easy to follow.\n2. The research hypotheses are clear, and the experiments are well designed with that in mind.\n3. Technical details are presented in sufficient mathematical detail.\n\nNegative:\n\n1. The authors do not appear to supply a software implementation, which would have been of great benefit to the reader.\n2. The technical novelty/contribution of the paper is limited (main contribution is empirical)\n3. The data sets in the study could perhaps be more fittingly chosen, so that the benefit of the graph neural network is more evident in all data sets. Not necessary to get the main message from the results, but would provide stronger motivation in my view.\n4. The findings are not strongly justified by theory. Of course, not all work has to provide theoretical results, but a more technical discussion of the potential benefites of the motivation for particular Update structures could be interesting, and would strengthen the paper.\n\nRecommendation:\n\nRejection. While the paper is well presented and technically sound, it would be much stronger if it could provide some theoretical analysis/justification of its findings.\n\nFurther comments:\n\nThe graph representation of MNIST and CIFAR10 was not clear to me.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lhz7GgpoGNI", "reviewer": "AnonReviewer3", "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": "This paper proposed to sparsify the update step of MPNN (message passing neural network)-typed graph neural networks. Specifically, the authors borrowed the idea of upsampling from X-net in CNN and update step simplification from SGC. Although with some presentation issues, the general idea is easy to follow. The reported empirical prediction performance of the simplified models on several standard datasets is comparable to that of the baseline models. However, I have some concerns regarding the methodology and the experimental settings, which, at this stage.\n\n**Below listed are the main concerns or confusion regarding the paper. \n1. (Section 3.2) what’s the meaning of $|\\mathbb{S}_1|$ and $|\\mathbb{S}_2|$? By absolute, does it mean the number of nodes in the two sets? Also how is the size of $|\\mathbb{S}_1||\\mathbb{S}_2|$ defined? Do you mean $|\\mathbb{S}_1|*|\\mathbb{S}_2|$? \n2. (Section 3.2.1) When mentioning the pruning algorithms, it would be more appropriate to add related citations after the concept.\n3. (Section 3.2.1) As mentioned in the second point, the expander sparsifiers are claimed to 'avoid the expensive computational cost'. While there are no reputable citations over the statement, one would expect some specific evidence to support it. For example, what is the computational cost gap between the pruning methods and the expender sparsifiers? \n4. (Section 3.2.1) As $\\mathcal{B}$ is interpreted as a linear transform, it would be clearer to define from which space to which space it transforms the information.\n5. (Definition 2) What does it mean by 'without loss of generality'? \n6. (Definition 2) What is the size of the adjacency matrix $\\mathbf{A}' $? Do you define $\\mathbf{A}^{\n\\prime} \\in \\mathcal{R}^{d*d}$, $\\mathbf{A}^{\\prime} \\in \\mathcal{R}^{|\\mathbb{S}_1|*d}$, or some other specific dimensions? Also, are there any constraints on setting the value of $d$? \n7. (Section 3.3) It is not clear how Equation 4 is ended up with an 'activation-only' form when the density is 0, i.e., $d=0$. The $d=0$ would result in a zero matrix of $\\mathbf{M}$, which cuts off all the signal transformations within the network. As a result, the output $\\mathbf{H}^{L}$ should also be a zero matrix. If different update rules are used when $d=0$, it should be clearly stated, rather than 'deriving from the general case of Equation 4'.\n8. The figures are difficult to read or understand. First, the labels are ambiguous to me. For example, which 'simple' and 'vanilla' models are referred to exactly? Also, why the number of bars for each of the methods (GCN, GIN, MLP) are different? Why some of the datasets (ENZYMES, DD, etc.) include error bars while others do not? It is recommended for a more straightforward and informative presentation to substitute the figures with tables, which provide readable comparable numeric values.\n9. The experimental results, especially displayed in Figure 1, cannot suggest the proposed methods' power. According to Figure 1-(d) and 1-(f), the last 3 Expander methods (except expander-10\\%) require more time and parameters to obtain a 'comparable' accuracy. Adopting such a structure is then in question.\n10. The results in Figure 1 are surprising, where MLP based methods outperform other models significantly. What is the possible explanation of it?\n**It is also found that many sentences are difficult to understand due to the over-complicated expressions, expositional problems, and/or grammatical mistakes. Some examples which need improvement:\n1. (line1, Section 3.1.1) \"Given a graph…\": can be simplified to shorter sentences.\n2. (line 4, page 3) Maybe some grammar problems in \"The idea of … has found successful application\".\n3. (line 1, Section 3.1.2) \"Expander graphs…can be informally defined as being highly connected and sparse\". The meaning of \"sparse\" is not clear.\n4. (line 12, Section 3.1.2) \"Training each parameter … incurs some training and inference, computational\". This sentence is ambiguous.\n5. (line 13, Section 3.1.2) \"Using the expander graph concept … reducing thus cost, and it is the aim to utilise each parameter to its greatest efficiency\". The meaning of \"reducing thus cost\" and 'greatest efficiency' is not clear.\n\nGiven the problems stated above, the paper needs significant improvement and polishment before it can be considered acceptable. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "5Oc5pZ8BljM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### **Post Rebuttal** \nI thank the authors for the elaborated answers and additional experiments. Unfortunately, I believe that although this work introduces some interesting insights it needs a little more work to achieve the ICLR publication bar. \nI therefore keep my original score.\n---\n\n#### **Summary of Contribution Claims** \nThe paper questions the necessity of complicated and computationally expensive  dense Update steps in message passing GNNs.\nTo answer the question two GNN variants with simple Update steps, expander based sparse and activation only, are suggested. \nThe paper presents a wide empirical evaluation on various datasets, demonstrating the abilities of the suggested models,  showing that in many cases, a simple Update step is good enough. From a practitioner point of view, the activation only model can serve as a simple \"test\" model to check whether on a specific task, a linear transformation in the Update step is necessary. \n \n**Strengths** \n- Clarity of ideas - the ideas behind the design of suggested Update steps are clearly explained and motivated. \n- Novel observation - in some cases, even the extreme case of an activation only Update step achieves good results.\n\n**Weaknesses** \n- Novelty and Contribution - I have some concerns regarding the novelty and contribution of this paper. As the use of expander graphs to sparsify NN layers has already been used in other NN architectures, I would say that Expander GNN is an extension. Furthermore, since the paper leans towards improving the practical side of GNNs, I would say that the hardware limitations mentioned in the paper are of concern. \n\n- Motivation vs. Evaluation - the paper motivates the design of sparse Update steps by the reduced computational costs. However, in the experiments, only relatively small graph datasets are evaluated on, leaving, in my opinion, the question of the effectivity of this approach in the desired setting open.\n\n- Experiments -  as mentioned above, I feel that the datasets over which the method has been evaluated do not provide a convincing evidence to the effectiveness of the approach. I would like to see performance on some datasets used in the SGC paper. \n\n- Discussion - the analysis and discussion of the results is rather a translation of the presented graphs without providing insights and possible explanations for the observed phenomena. From the results discussion in the paper I take that the success of the simplified Update steps is task dependent however, I would like to have some understanding and characterization as to when or why things work the way they do?\n\n#### **Decision Recommendation**\nAlthough presenting interesting empirical results, and potentially valuable simplifications of GNNs, I feel that this paper can be improved by performing evaluation on more relevant datasets, and acquiring stronger theoretical understanding and explanation of the observed results.  \nI would suggest to reject the paper.  \n\n#### **Other Comments**\nThe paper title is a bit misleading, I would suggest changing Analyzing to Simplifying, since the paper mainly proposes the method and shows on par performance,  but the analysis is lacking.  \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on the update step in Message-Passing Neural Networks, specifically for GNN. A series of sparse variants of the update step, say complete removal and expander graphs with varying density, are compared in empirical studies. The findings are quite useful for practice, and the paper is organized and written well.  As observed by the reviewers, there are several concerns regarding the novelty and contribution of the work. Besides, theoretical analysis of the sparsification approach is lacking. The authors provided a good rebuttal and addressed some concerns, but not to the degree that reviewers think it passes the bar of ICLR. We encourage the authors to further improve the work to address the key concerns. 
Decision: Reject