# Training Sensitivity in Graph Isomorphism Network

Md. Khaledur Rahman  Indiana University Bloomington<EMAIL_ADDRESS>
(2020)

###### Abstract.

Graph neural network (GNN) is a popular tool to learn the lower-dimensional
representation of a graph. It facilitates the applicability of machine
learning tasks on graphs by incorporating domain-specific features. There are
various options for underlying procedures (such as optimization functions,
activation functions, etc.) that can be considered in the implementation of
GNN. However, most of the existing tools are confined to one approach without
any analysis. Thus, this emerging field lacks a robust implementation ignoring
the highly irregular structure of the real-world graphs. In this paper, we
attempt to fill this gap by studying various alternative functions for a
respective module using a diverse set of benchmark datasets. Our empirical
results suggest that the generally used underlying techniques do not always
perform well to capture the overall structure from a set of graphs.

graph neural networks; node classification; parameter sensitivity

††journalyear: 2020††copyright: acmcopyright††conference: Proceedings of the
29th ACM International Conference on Information and Knowledge Management;
October 19–23, 2020; Virtual Event, Ireland††booktitle: Proceedings of the
29th ACM International Conference on Information and Knowledge Management
(CIKM ’20), October 19–23, 2020, Virtual Event, Ireland††price: 15.00††doi:
10.1145/3340531.3412089††isbn: 978-1-4503-6859-9/20/10

##  1\. Indtroduction

Graphs can be considered as a transformation of knowledge from various domains
such as social networks, scientific literature, and protein-interaction
networks, where an entity can be denoted by a vertex and the relationship
between a pair of entities can be denoted by an edge. An effective
representation of a graph can help learn important characteristics from the
dataset. For example, a machine learning model can be applied to graph
representation to recommend friends in social networks. The traditional graph
data structure, such as the adjacency matrix, can be a naive representation
for machine learning models for making such predictions. However, we can not
accommodate memory for very large graphs as this representation has $O(n^{2})$
memory cost. As the size of the representable data in the graph format is
growing at a significant speed (reinsel2018digitization, ), it allows the
researchers to find an alternate efficient approach. Thus, an effective graph
representation learning or embedding technique has become a high demanding
problem.

Designing an effective graph embedding method can be extremely challenging as
most real-world graphs have a highly irregular structure. Several unsupervised
methods have been proposed in the literature to solve this problem sub-
optimally (perozzi2014deepwalk, ; grover2016node2vec, ). Graph layout
generation methods can also be used to generate embedding
(rahman2020batchlayout, ; rahman2020force2vec, ). Some of them generate good
quality embedding but have high runtime and memory costs while some of them
consume less runtime and memory costs but generate moderate-quality embedding.
Nevertheless, these methods can not incorporate domain-specific features which
might be helpful to learn a better representation of the graph.

Figure 1. A graph neural network with toy example: a hidden layer consists of
pooling (aggregation) layer and activation layer. There can be multiple hidden
layers in the network. Output layer represents the embedding of the the
network which is generally used for classification task.

Recently, Graph Convolutional Network (GCN) has gained much attention in the
literature (kipf2016semi, ). The basic idea is similar to that of
Convolutional Neural Networks (CNN) (krizhevsky2012imagenet, ) in the computer
vision domain where a convolution operator of a vertex aggregates
contributions from its neighboring vertices in each hidden layer. A toy
example is shown in Fig. 1. The _GraphSAGE_ method further contributes to this
field by proposing several effective aggregation functions
(hamilton2017inductive, ). On the other hand, _FastGCN_ runs faster than other
methods though it sacrifices the quality of the embedding a little
(chen2018fastgcn, ). Notably, Errica et al. have performed an extensive set of
experiments to compare only existing GNN tools (errica2019fair, ). These types
of methods are trained in a semi-supervised manner and used to predict the
label of unseen vertices which is often termed as _inductive_ learning
(hamilton2017inductive, ). This is a rapidly growing field; however, the
parameter sensitivity of GNN is overlooked in the literature. In this paper,
we have filled this gap by analyzing a GNN model, called Graph Isomorphism
Network (GIN) (xu2018powerful, ), for several optimization techniques,
aggregation functions, learning rate, and activation functions on a diverse
set of benchmark graphs. The summary of our contributions are given as
follows:

  * •

We develop a set of research questions and address them by parameter tuning to
learn the sensitivity of GIN.

  * •

We conduct an extensive set of experiments to analyze the results on a diverse
set of benchmark datasets.

  * •

Our empirical results provide a new insight that the traditionally used ADAM
optimization technique and the ReLU activation function do not always perform
better than other alternatives for all types of graphs. This presumably
directs us to consider other techniques rather than a single one.

##  2\. Problem Setting

###  2.1. Background

We represent a graph by $G=(V,E)$, where, $V$ is the set of vertices, $E$ is
the set of edges and each $z_{i}$ of a set $Z$ represents 1-dimensional
embedding of $i^{th}$ vertex. We represent neighbors of a vertex $u$ in $G$ by
$N(u)$. In a GNN, domain-specific features or one-hot-encoded representation
of vertices are fed to the input layer. In a hidden layer, an aggregation
(pooling) function gathers contribution from the neighbors of a vertex to
learn the structural properties of the graph that goes through an activation
function (see Fig. 1). Multiple hidden layers can be placed in the network in
a cascaded style. The embedding $Z$ of a graph $G$ is produced in the output
layer. A cross-entropy based objective function is optimized to update the
embedding in a semi-supervised way. The representation of hidden layers in GIN
(xu2018powerful, ) can be expressed as follows:

(1) $h^{l}_{u}=MLP\big{(}(1+\epsilon^{l})h^{l-1}_{u}+\sum_{v\in
N(u)}h^{l-1}_{v}\big{)}\vspace{-0.3cm}$

Here, $h^{l}_{u}$ is the activation of $l^{th}$ hidden layer for vertex $u$
and $h^{0}_{u}=X$, where, $X$ is the input features. MLP represents the multi-
layer perceptron that helps learn the representation of the network and
$\epsilon$ denotes the fraction of considerable activation from the previous
layer for the same vertex $u$. A non-linear activation function is used in the
MLP of Equation 1 and a popular choice is Rectified Linear Units (ReLU)
(nair2010rectified, ). There are several options to optimize the performance
of a GNN by tweaking units such as activation function, optimization
technique, or hyper-parameter tuning.

###  2.2. Activation Functions

We employ several activation functions in the GIN, each of which has some
benefits over others. We assume that $x$ represents the product of
contributions of activation from all neighbors in a hidden layer and the
weight matrix of the corresponding layer. Then, the ReLU, LeakyReLU, Sigmoid,
and Tanh activation functions compute the activations using the terms
$\max(0,x)$, $\max(0,x)+0.01\times\min(0,x)$, $\frac{1}{1+e^{-x}}$, and
$\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}$, respectively. Specifically, we use
PyTorch implementations for these activation functions. Generally, the state-
of-the-art tools employ one activation function in a GNN such as ReLU in GCN
(kipf2016semi, ) or LeakyReLU in GAT (velivckovic2017graph, ), but they do not
distinguish among different activation functions. In this paper, we study the
above mentioned four standard activation functions.

###  2.3. Optimization techniques

We discuss five techniques to optimize the cross entropy-based loss function
in GIN. We study these techniques due to the fact that the graph datasets have
irregular structures and one single technique might not perform well to
optimize the objective function.

SGD: The Stochastic Gradient Descent (SGD) is a widely used algorithm to
optimize weights in neural networks (bottou1991stochastic, ). This approach
updates weight parameters with respect to each training sample which reduces
huge computation costs of convergence in the Gradient Descent (GD) approach.

(2) $W_{t+1}=W_{t}-\eta\frac{\partial\mathcal{L}}{\partial
W_{t}}\vspace{-0.20cm}$

Here, $t$ represents $t^{th}$ iteration, $\eta$ is the learning rate,
$\frac{\partial\mathcal{L}}{\partial W_{t}}$ is the gradient of loss function
$\mathcal{L}$ with respect to weight matrix $W$.

ADAGRAD: The ADAptive GRADient (ADAGRAD) is a variation of the SGD algorithm
which focuses on updating multi-dimensional weights using scaled learning rate
for each dimension (duchi2011adaptive, ). We can formally present this
updating equation as follows:

(3) $W_{t+1}=W_{t}-\frac{\eta}{\sqrt{\epsilon
I+diag(G_{t})}}\frac{\partial\mathcal{L}}{\partial W_{t}}\vspace{-0.2cm}$

Here, $I$ is the identity matrix, $\epsilon$ is a small value to avoid
division by zero, $G_{t}$ is a diagonal matrix where each diagonal entry
represents gradient in the corresponding dimension.

ADADELTA: ADADELTA is another variation of SGD that solves some of the
problems originated by the ADAGRAD approach such as decreasing learning rate
over iterations and manual selection of global learning rate
(zeiler2012adadelta, ). ADADELTA addresses these issues computing past
gradients over a fixed window of steps. To get rid of $\eta$, it also
considers accumulated weights similar to gradients. The whole weight update
can be represented as follows:

(4a) $\displaystyle U_{t}(g^{2})$ $\displaystyle=\alpha
U_{t-1}(g^{2})+(1-\alpha)g_{t}^{2}$ (4b) $\displaystyle\Delta W_{t}$
$\displaystyle=\sqrt{\frac{U_{t-1}(\Delta
W^{2})+\epsilon}{U_{t}(g^{2})+\epsilon}}$ (4c) $\displaystyle U_{t}(\Delta
W^{2})$ $\displaystyle=\alpha U_{t-1}(\Delta W^{2})+(1-\alpha)\Delta
W_{t}^{2}$ (4d) $\displaystyle W_{t+1}$ $\displaystyle=W_{t}-\Delta
W_{t}g_{t}\vspace{-0.1cm}$

Here, $g_{t}$ is gradient of $t^{th}$ iteration, i.e.,
$g_{t}=\frac{\partial\mathcal{L}}{\partial W_{t}}$, $U_{t}$ is a function that
computes accumulation of previous gradients and weights, $\alpha$ is a
decaying parameter that determines what percentages of previous gradient and
current gradient will be used, respectively.

RMSProp: RMSProp is similar to ADADELTA with the exception that it does
accumulate weight over iterations and it keeps learning rate in the updating
equation. This can be formally represented as the following equations:

(5a) $\displaystyle U_{t}(g^{2})$
$\displaystyle=0.9U_{t-1}(g^{2})+0.1g_{t}^{2}$ (5b) $\displaystyle W_{t+1}$
$\displaystyle=W_{t}-g_{t}\frac{\eta}{\sqrt{U_{t}(g^{2})+\epsilon}}\vspace{-0.2cm}$

ADAM: ADAptive Momentum (ADAM) estimation is a pioneering work that keeps
accumulations for the mean and the variance of gradients (kingma2014adam, ).
In this approach, a weighted average is calculated by taking a large fraction
of gradient from previous steps and a small fraction from the current step.
Similarly, the variance of the squared gradient is also taken as a weighted
average of past and current squared gradients. We can represent this as
follows:

(6a) $\displaystyle m_{t}$ $\displaystyle=\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$
(6b) $\displaystyle v_{t}$
$\displaystyle=\beta_{2}v_{t-1}+(1-\beta_{2})g_{t}^{2}$ (6c)
$\displaystyle\hat{m_{t}}$ $\displaystyle=m_{t}/(1-\beta^{t}_{1})$ (6d)
$\displaystyle\hat{v_{t}}$ $\displaystyle=v_{t}/(1-\beta^{t}_{2})$ (6e)
$\displaystyle W_{t+1}$
$\displaystyle=W_{t}-\eta\frac{\hat{m_{t}}}{\sqrt{\hat{v_{t}}}+\epsilon}$

Here, $m_{t}$ is the momentum of mean gradients and $v_{t}$ is the momentum of
variance of gradients up to $t^{th}$ iteration and $\hat{m_{t}}$ and
$\hat{v_{t}}$ are bias corrected estimates, respectively. $\beta_{1}$ and
$\beta_{2}$ are two decaying parameters for the momentum of mean and variance,
respectively.

We study the characteristics of graph isomorphism network using these five
types of optimization techniques.

###  2.4. Aggregation/Pooling functions

We consider three aggregation functions in the GIN architecture
(xu2018powerful, ). The MAX function aggregates the maximum value from the
neighbors. The AVERAGE function sum up contributions from neighbors and
aggregates this value dividing by the number of neighbors. The SUM aggregation
function simply sums up the contributions from neighbors and send to the
activation function. Authors of GIN show that the SUM function can distinguish
different structures in the graph whereas other functions fail to do so. Thus,
we briefly revisit all these aggregation functions.

##  3\. Experiments

###  3.1. Experimental Setup

To conduct experiments, we use a server machine configured as follows:
Intel(R) Xeon(R) CPU E5-2670 v3 (2.30GHz), 48 cores arranged in two NUMA
sockets, 128GB memory, 32K L1 cache, and 32MB L3 cache. We run all experiments
using graph isomorphism network111https://github.com/weihua916/powerful-gnns/
which has two MLP layers and generates 64-dimensional embedding of a graph. We
set the batch size to 32, number of epoch to 50, and use default values for
several hyper-parameters unless otherwise explicitly mentioned. We report the
performance of all datasets in terms of accuracy measure i.e., higher the
value is better the result is. WLOG, we show the value of the accuracy measure
within the range 0 to 1 or multiplying by 100 to report percentage.

###  3.2. Datasets

We use a set of five graph classification datasets which include two
bioinformatics networks, and three social networks. We compute the average
degree by averaging the avg. degree across all graphs of a particular dataset.
This set of graphs have diverse properties such as they have a varying average
degree and the number of graphs for each dataset has variable proportions. We
provide a summary of the datasets in Table 1. More details about these
datasets can be found in the GIN paper (xu2018powerful, ).

Table 1. Benchmark datasets for graph embedding Name | #Graphs | Avg. $|V|$ | #Lab. | Avg. Deg.
---|---|---|---|---
PROTEINS | 1113 | 39.1 | 2 | 3.73
COLLAB | 5000 | 74.5 | 3 | 37.38
NCI1 | 4110 | 29.8 | 2 | 2.15
REDDITM | 5000 | 508.5 | 5 | 2.25
IMDBM | 1500 | 13.0 | 3 | 8.10

###  3.3. Results

Different graphs have different structural properties. So, we can presumably
say that various optimization techniques can show dissimilar results for
various graph datasets. Most of the previously proposed GNNs are lacking this
study. In this paper, we attempt to study these behaviors on several benchmark
datasets. Specifically, we employ different optimization techniques,
aggregation functions, and activation functions to study the sensitivity of
our focused GIN model. For all experiments, we perform 10-fold cross-
validation i.e., we report the results of training accuracy based on 90%
dataset and testing accuracy based on the remaining 10% dataset. We develop a
set of research questions which are discussed as follows.

Figure 2. Training accuracy of (a) NCI1 and (b) REDDITM datasets for different
optimization techniques.

####  3.3.1. Which optimization technique is robust for a GNN?

Most of the GNNs use ADAM optimizer in the programming model (kipf2016semi, ;
hamilton2017inductive, ; chen2018fastgcn, ; xu2018powerful, ). So, we measure
the performance of different optimization techniques along with ADAM which are
discussed in Section 2.3. We use default values for other parameters in the
GIN model. We report the training accuracy of NCI1 and REDDITM datasets in
Figs. 2 (a) and (b). We observe that the ADAGRAD optimization technique shows
better accuracy curve for different iterations than other optimization
techniques. ADADELTA technique also shows better accuracy curve than ADAM. For
the REDDITM dataset, ADAGRAD again shows a better performance curve which is
more robust than other optimization techniques. So, we can clearly state from
the empirical evidence that the ADAGRAD optimization technique is better than
ADAM to use in the graph isomorphism network. We skip training results for
other graphs due to space restriction.

We show the results of test datasets for different optimization techniques in
Fig. 3 (a). We observe that the ADAGRAD also performs better than ADAM for
NCI1 and REDDITM datasets. In fact, ADAGRAD shows better or competitive
performance across all benchmark datasets. We perform a two-sided Wilcoxon
signed-rank test on 50 samples of test results which also supports our
findings ($p$-value ¡ 0.017) for all datasets (wilcoxon1992individual, ). This
empirical evidence gives us a new insight to use the ADAGRAD technique instead
of ADAM in graph neural networks.

Figure 3. Test accuracy of different datasets for different (a) optimization
techniques, (b) activation functions, (c) aggregation functions, and (d)
learning rates. Average value of test accuracy is reported over several
iterations.

Figure 4. Training accuracy of (a) NCI1 and (b) REDDITM datasets for different
activation functions.

####  3.3.2. Which activation function is more effective?

Similar to ADAM optimization technique, most existing graph neural networks
use ReLU activation function in the programming model (kipf2016semi, ;
hamilton2017inductive, ; xu2018powerful, ). So, we evaluate the performance of
other activation functions along with ReLU which are discussed in Section 2.2.
As usual, we use default values for other parameters in the model. We report
the results of training accuracy for NCI1 and REDDITM datasets in Figs. 4 (a)
and (b). The training accuracy for all activation functions shows spikes in
the learning curves. However, we observe that LeakyReLU and ReLU shows
competitive performance over several iterations while training the model. For
the REDDITM dataset, the Tanh activation function also shows competitive
performance.

We report the results for test datasets for all activation functions in Fig. 3
(b). We observe that LeakyReLU shows better or competitive performance than
other activation functions. Notice that the Tanh activation technique shows
better test accuracy than ReLU for REDDITM dataset. These experimental results
provide us a new insight that the LeakyReLU might be a better choice for
activation function in graph neural networks than ReLU.

####  3.3.3. Aggregation functions revisited

Authors of the GIN method demonstrate several scenarios where MAX and AVERAGE
aggregation functions can fail to distinguish between structural differences
of graphs. On the other hand, the SUM aggregation function can correctly
distinguish such structural differences. Our experimental results also support
this statement. We briefly report the results of the test datasets in Fig. 3
(c). We observe that all aggregation functions perform almost equally well for
PROTEINS and NCI1 datasets. However, the SUM function performs significantly
better than other functions for IMDBM, REDDITM, and COLLAB datasets. Thus, SUM
would be an order invariant powerful aggregation function for graph neural
networks.

Figure 5. Training accuracy of (a) NCI1 and (b) REDDITM datasets for different
number of hidden and MLP layers.

####  3.3.4. Hyper-parameter sensitivity

We also study several hyper-parameters in graph isomorphism network such as
hidden dimension, learning rate, the number of hidden layers, and the number
of layers in MLP. Notably, we use the default value for other parameters in
the model. The parameter sensitivity of the embedding dimension has been
studied in supervised learning (perozzi2014deepwalk, ; grover2016node2vec, ).
So, we also conduct experiments varying the size of the hidden dimension in
GIN for the REDDITM dataset. For this experimental setup, we get a test
accuracy of 39.1%, 39%, 39%, and 38.4% for 16, 32, 64, and 128-dimensional
embedding, respectively. Thus, we do not see any significant difference for
other datasets as well but in general, accuracy may drop for very higher-
dimensional representation.

We report the results of test accuracy for different learning rates in Fig. 3
(d). We observe that a learning rate of 0.02 shows better results for PROTEINS
and NCI1 datasets whereas a learning rate of 0.01 shows better performance for
IMDBM, REDDITM, and COLLAB datasets. Thus, a learning rate of 0.01 would be a
reasonable choice for the GIN model. We show training accuracy in Figs. 5 (a)
and (b) for NCI1 and REDDITM datasets, respectively, varying the number hidden
layer and MLP layer. In both figures, L5_MLP2 means that the learning model
has 5 hidden layers and 2 MLP layers. We observe that increasing the number of
hidden layers in the model does not change the performance significantly;
however, increasing the number of MLP layers contributes to improve the
performance. So, a higher value for MLP layers might be a better option to
seek improved performance.

##  4\. Conclusions

Graph neural network has become a powerful toolbox for analyzing and mining
different graph datasets. However, this field is lacking a rigorous evaluation
of several underlying techniques that can be employed in GNN. For example,
most existing methods stick to a particular optimization technique such as
ADAM or an activation function such as ReLU. In this paper, we empirically
demonstrate that ADAGRAD and LeakyReLU might be better options for
optimization technique and activation function, respectively. We believe that
our findings would provide a new insight into the community for choosing
better underlying techniques while developing a new graph neural network.

## References

  * (1) Bottou, L. Stochastic gradient learning in neural networks.  Proceedings of Neuro-Nımes 91, 8 (1991), 12.
  * (2) Chen, J., Ma, T., and Xiao, C. FastGCN: fast learning with graph convolutional networks via importance sampling.  arXiv:1801.10247 (2018).
  * (3) Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization.  Journal of machine learning research 12, Jul (2011), 2121–2159.
  * (4) Errica, F., Podda, M., Bacciu, D., and Micheli, A. A fair comparison of graph neural networks for graph classification.  arXiv:1912.09893 (2019).
  * (5) Grover, A., and Leskovec, J. node2vec: Scalable feature learning for networks.  In KDD (2016), ACM, pp. 855–864.
  * (6) Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs.  In NIPS (2017), pp. 1024–1034.
  * (7) Kingma, D. P., and Ba, J. Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980 (2014).
  * (8) Kipf, T. N., and Welling, M. Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907 (2016).
  * (9) Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks.  In NIPS (2012), pp. 1097–1105.
  * (10) Nair, V., and Hinton, G. E. Rectified linear units improve restricted boltzmann machines.  In ICML (2010), pp. 807–814.
  * (11) Perozzi, B., Al-Rfou, R., and Skiena, S. DeepWalk: Online learning of social representations.  In KDD (2014), ACM, pp. 701–710.
  * (12) Rahman, M. K., Sujon, M. H., and Azad, A. BatchLayout: A batch-parallel force-directed graph layout algorithm in shared memory.  In 2020 IEEE Pacific Visualization Symposium (PacificVis) (2020), IEEE, pp. 16–25.
  * (13) Rahman, M. K., Sujon, M. H., and Azad, A. Force2Vec: Parallel force-directed graph embedding.  In Review (2020).
  * (14) Reinsel, D., Gantz, J., and Rydning, J. The digitization of the world from edge to core.  IDC White Paper (2018).
  * (15) Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks.  arXiv:1710.10903 (2017).
  * (16) Wilcoxon, F. Individual comparisons by ranking methods.  In Breakthroughs in statistics. Springer, 1992, pp. 196–202.
  * (17) Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826 (2018).
  * (18) Zeiler, M. D. Adadelta: an adaptive learning rate method.  arXiv:1212.5701 (2012).