An Empirical Study of the Expressiveness of Graph Kernels and Graph Neural Networks
Authors: Giannis Nikolentzos
George Panagopoulos
Michalis Vazirgiannis
Venue:  (2021)

Abstract: Graph neural networks and graph kernels have achieved great success in solving machine learning problems on graphs. Recently, there has been considerable interest in determining the expressive power mainly of graph neural networks and of graph kernels, to a lesser extent.  Most studies have focused on the ability of these approaches to distinguish non-isomorphic graphs or to identify specific graph properties. However, there is often a need for algorithms whose produced graph representations can accurately capture similarity/distance of graphs. This paper studies the expressive power of graph neural networks and graph kernels from an empirical perspective. Specifically, we compare the graph representations and similarities produced by these algorithms against those generated by a well-accepted, but intractable graph similarity function. We also investigate the impact of node attributes on the performance of the different models and kernels. Our results reveal interesting findings. For instance, we find that theoretically more powerful models do not necessarily yield higher-quality representations, while graph kernels are shown to be very competitive with graph neural networks.

Under review as a conference paper at ICLR 2021
AN EMPIRICAL STUDY OF THE EXPRESSIVENESS OF GRAPH KERNELS AND GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks and graph kernels have achieved great success in solving machine learning problems on graphs. Recently, there has been considerable in- terest in determining the expressive power mainly of graph neural networks and of graph kernels, to lesser extent. Most studies have focused on the ability of these approaches to distinguish non-isomorphic graphs or to identify specific graph properties. However, there is often need for algorithms whose produced graph representations can accurately capture similarity/distance of graphs. This paper studies the expressive power of graph neural networks and graph kernels from empirical perspective. Specifically,
compare the graph representations and similarities produced by these algorithms against those generated by well- accepted, but intractable graph similarity function. We also investigate the impact of node attributes on the performance of the different models and kernels. Our results reveal interesting findings. For instance, we find that theoretically more powerful models do not necessarily yield higher-quality representations, while graph kernels are shown to be very competitive with graph neural networks.
INTRODUCTION
In recent years, graph-structured data has experienced an enormous growth in many domains, rang- ing from chemo- and tio-informatics to social network analysis. Several problems of increasing interest require applying machine learning techniques to graph-structured data. Examples of such problems include predicting the quantum mechanical properties of molecules (Gilmer et al. 2017) and modeling physical systems (Battaglia et al. 2016). To develop successful machine learning models in the domain of graphs, we need techniques that can both extract the information that is hidden in the graph structure, and also exploit the information contained within node and edge at- tributes. In the past years, the problem of machine learning graphs has been governed by two major families of approaches, namely graph kernels (Nikolentzos et al. 2019) and graph neural networks (GNNs) (Wu et al. (2020).
Recently, much research has focused on measuring the expressive power of GNNs (Xu et al. 2019
Morris al.] 2019 Murphy al. 2019 Maron et al. 2019a Sato et al., 2019 Keriven & Peyré 2019 Chen et al. 2019; Dasoulas et al. 2020 Nikolentzos et al.) 2020; Barceló et al.) 2020). On the other hand, in the case of graph kernels, there was a limited number of similar studies (Kriege et al. 20188. This is mainly due to the fact that the landscape of graph kernels is much more diverse than that of GNNs. Indeed, although numerous GNN variants have been recently proposed, most of them share the same basic idea, and can be reformulated into a single common framework, so- called message passing neural networks (MPNNs) (Gimer et al. (017). These models employ message passing procedure to aggregate local information of vertices and are closely related to the Weisfeiler-Lehman (WI.) test of graph isomorphism, powerful heuristic which can successfully test isomorphism for broad class of graphs (Arvind et al. 2015).
When dealing with learning problems on graphs, a practitioner needs to choose one GNN or one graph kernel for her particular application. The practitioner is then faced with the following ques- tion: Does this GNN variant or graph kernel capture graph similarity better than others? Unfortu- nately, this question is far from being answered. Most of the above studies investigate the power of GNNs in terms of distinguishing between non-isomorphic graphs or in terms how well they can approximate combinatorial problems. However, in graph classification/regrsssoo problems, we

---

Under review as a conference paper at ICLR 2021
not that much interested in testing whether two (sub)graphs are isomorphic to each other, but mainly in classifying graphs or in predicting real values associated with these graphs. In such tasks, it has been observed that stronger GNNs do not necessarily outperform weaker GNNs. Therefore, it seems that the design of GNNs is driven by theoretical considerations which are not realistic in practical settings. Ideally, would like to learn representations which accurately capture the similarities or distances between graphs.
A practitioner can then choose an algorithm based on its empirical performance. Indeed, GNNs and graph kernels are usually evaluated on standard datasets derived from bio-/chermo-nformaaicc and from social media (Morris et al., 2020). However, several concerns have been raised recently with regards to the reliability of those datasets, mainly due to their small size and to inherent isomor- phism bias problems (Ivanov et al., 2019). More importantly, has been observed that the adopted experimental settings are in many cases ambiguous or not reproducible (Errica et al. (020). The ex- perimental setup is not standardized across different works, and there are often many issues related to hyperparameter tuning and to how model selection and model assessment are performed. These issues easily generate doubts and confusion among practitioners that need a fully transparent and reproducible experimental setting.
Present work. In this paper, empirically evaluate the expressive power of GNNs and graph kernels. Specifically, we Then, we compare the graph representations and similarities produced by GNNs and graph kernels against those generated by an intractable graph similarity function which we consider to be an oracle function that outputs the true similarity between graphs. We perform a large number of experiments where we compare several different kernels, architectures, and pooling functions. Secondly, we study the impact of node attributes on the performance of the different models and kernels. We show that annotating the nodes with their degree and/or triangle participation can be beneficial in terms of performance in the case of GNNs, while it is not very useful in the case of graph kernels. Finally, we investigate which pairs of graphs (from our dataset) lead GNNs and kernels to the highest error in the estimated simialrity. Surprisingly, we find that several GNNs and kernels assign identical or similar representations to very dissimilar graphs. We publicly release code and dataset to reproduce our results, in order to allow other researchers to conduct similar studie!]]
a dataset that contains instances of different families of graphs.
2 RELATED WORK
Over the past years, the expessiveness of graph kernels assessed almost exclusively from perimental studies. Therefore, still, there is no theoretical justification on why certain graph kernels perform better than others. From the early days of the field, it was clear though that the mapping induced by kernels that are computable in polynomial time is not injective (and thus these kernels cannot solve the graph isomorphism problem) (Gärtner et al. (000). Recently, Kriege et al. (2018) proposed a framework to measure the expressiveness of graph kernels based on ideas from property testing. It was shown that some well-established graph kernels such as the shortest path kernel, the graphlet kernel, and the Weisfeiler-Lehman subtree kernel cannot identify basic graph properties such as planarity or bipartitness.
With the exception of the work of Scarselli et al. (2008), until recently, there has been little attempt to understand the expressive power GNNs. Several recent studies have investigated the connections between GNNs and the Weisfeiler-Lehman For instance, it was shown that standard GNNs do not have more power in terms of distinguishing between non-isomorphic graphs than the WL algorithm (Morris et al.) 2019 Xu et al. 2018). Morris et al. (2019) proposed family of GNNs which rely on a message passing scheme between subgraphs of cardinality k. and which have exactly the same power in terms of distinguishing non-isomopphic graphs as the set-based variant of the k-WL algorithm. In a similar spirit, (Maron et al.) 2019a) introduced k-order graph networks which are at least as powerful
(WL) test of isomorphism and its higher-order variants.
the folklore variant of the k- WL graph isomorphism test in terms of distinguishing non-isomorphic graphs. These models were also shown be universal (Maron et al. tensors and therefore are not practical. Chen et al. (2019) show that the two main approaches for studying the expressive power of GNNS, namely graph isomorphism testing and invariant function
& Peyré 2019), but require using high order
Code available at: https://github. http:////ggttuub..co////xxx/////
2

---

Under review as a conference paper at ICLR 2021
approximation, are equivalent to each other. Futhermore, the authors propose GNN that is more powerful than 2- 2-WL. Barceló et al. (2020) rely on a connection between the WL algorithm and first order logic, and characterize the expressive power of GNNs in terms of classical logical languages. The impact of random features on the expressive power of MPNNs is considered in Saato et al.) (2020). Nikolentzos et al. (2020) show that standard GNNs cannot identify fundamental graph properties such as triangle- freeness and connectivity, and they propose a model that can identify these properties. Murphy et al. (2019) and Dasoulas et al. (2020) take into account all possible node permutations and produce universal graph representations. The emerging problems becomes intractable once the number of nodes is large and they propose approximation schemes to make the computation tractable in practice. Some recent works have studied the generalization properties of GNNs (Scarselli et al. 2018, Verma & Zhang, 2019 Garg et al., 2020). For a comprehensive overview of the expressive power of GNNs, the interested reader is referred to Sato (2020).
3 COMPARING GRAPHS TO EACH OTHER
Formally, for any two graphs G = (V1, Fi) and G2 = (V2, F22 on n vertices with respective n x n adjacency matrices A1 and A2. we define function f G G - E. where G is the space of graphs which quantifies the similarity of 11 and G2. Note that in the literature, this problem is often referred to as graph comparison. The problem of graph comparison has been the topic of numerous studies in computer science (Conte et al., 2004). Existing approaches are generally motivated by runtime considerations. These approaches are computable in polynomial time, but also limited in terms of expressive power. For instance, for similarity measures that take values between 0 and 1, [(G1, G1) = J(G = may hold even if G1 and G2 are not isomorphic to each other. this paper, we consider graph comparison function which is not computable in polynomial time. The function can be expressed as a maximization problem, and is defined as follows:
Σ j== [A @ PA.P 1i
[(1,, G2) = -aax
Pell
A
A2l1æ
where II denotes the set of n X n permutation matrices, C denotes the elementwise product, and Il- || is the Froebenius matrix norm. For clarity of presentation we assume n to be fixed (i. e., both graphs consist of vertices). In order to apply the function to graphs of different cardinality, one can append zero rows and columns to the adjacency matrix of the smaller graph to make its number of rows and columns equal n. Therefore, the problem of graph comparison can be reformulated as the problem of maximizing the above function over the set of permutation matrices. A permutation matrix P gives rise to bijection л. Vi + V22 The function defined above seeks for bijection such that the number of common edges [(, v) E E : (m(4),
E E221 is maximized. Then, the number of common edges is normalized such that it takes values between and 1. Observe that the above definition is symmetric in G and G2. The two graphs are isomorphic to each other if and only if there exists a permutation matrix P for which the above function is equal to Therefore, a value equal to 0 denotes maximal dissimilarity, while value equal to denotes that the two graphs are isomorphic to each other. Note that the compared graphs are not empty (i. e., they contain at least one edge), the function will take some value greater than 0. Solving the above optimization problem for large graphs is clearly intractable since there are ne! permutation matrices of size n. As mentioned above, existing approaches for comparing graphs to each other for generating graph representations are generally motivated by runtime considerations, and provide no guarantees on how well they approximate the above function other similar graph comparison functions. In this paper, we investigate how different graph comparison/representttoo learning approaches approximate the above-defined function from an empirical standpoint.
4 EMPIRICAL EVALUATION
4.1 DATASET
Since the function defined in equation I is intractable for large graphs, we generated graphs consist- ing of most 9 vertices. Furthermore, each graph is connected and contains at least 1 edge. We generated 191 pairwise non-isomorphic graphs. The dataset consists of different types of synthetic graphs. These include simple structures such as cycle graphs, path graphs, grid graphs, complete
3

---

Under review as a conference paper at ICLR 2021
Synthetic Dataset
Max # vertices
9
Min vertices
2
Frequency
1000
Average # vertices
7.29
800
Max # edges
36
600
Min # edges
1
400
Average # edges
11.34
200
# graphs
191
0.2
0.4
Similarity
Table 1:
Summary of the synthetic dataset that we used in our experiments.
Figure Distribution of similarities between the synthetically generated graphs.
graphs and star graphs, but also andomllygeneraate graphs such as Erdös-Rénye graphs, Barabási- Albert graphs and Watts-Strogatz graphs. Table shows statistics of the synthetic dataset that we used in our experiments. Figure [ illustrates the distribution of the similarities of the generated graphs as computed by the proposed measure. There are 191.192/2 18, 336 pairs of graphs in total (including pairs consisting of a graph and itself). Interestingly, most of the similarities take values between 0.5 and 0.8.
4.2 SELECTED APPROACHES
Suitable graph kernels and GNNs were selected according to the following criteria: (1) publicly available implementations, (2) strong architectural differences, (3) popularity, and (4) peer reviewed. We next present the graph kernels and GNNs that were included into our evaluation. For a detailed description of each kernel and each GNN, we refer the reader their respective papers.
Graph kernels. We selected the following 6 graph kernels: (1) the random walk kernel (RW)
Garrnner et al. 2003). (2) the shortest path kernel (SP) (Borgwardt Kriegel 22055.. (3) the graphlet kernel (GR) Shervashidze et al.] (209).. (4) the Weisteller-Lehman subtree kernel (WL) (Sher-) vashidze et al. 2011), (5) the pyramid match kernel (PM) (Nikolentzos et al., 2017), and (6) the
GraphHopper kernel (Feragen et al.] 2013). Note that GR can only operate on unlabeled graphs. The rest of the kernels can handle graphs with discrete node labels, while GraphHopper is the only kernel that can deal with continuous multi-dimensional node features.
GNNs.
We also selected the following GNNs: (1) GCN (Kipf Welling 2016). (2) GAT
Veličković et al. 2017). (3) 1-GNN (Moriss al. 2019), (4) GG-NN (Li al. 2015). (5) Graph-
SAGE (Hamilton et al. 2017). (6) GIN (Xu et al. 2019), (7) ChebNet (Defferrard et al. 2016). (8)
ARMA (Bianchi al. 2019), (9) 1-2-GNN (Morris al., 2019 (10) k-hop GNN (Nikolentzos et al. 2020), and (11) Provably Powerful GNN (Maron et al. 2019a). To produce graph represen- lations, we common pooling functions, namely the sum aggregator, the mean aggregator and the max aggregator.
4.3 BASELINES
We utilize some simple baselines whose purpose is understand the extent to which graph kernels and GNNs can indeed learn representations that capture graph similarity. The first baseline is function that randomly computes the similarity of two graphs by sampling number from [0, with uniform probability. The second baseline is a constant function. The outputs of this functions is equal to 1. Using such simple baselines as reference is crucial since they can provide feedback on the effectiveness of graph kernels and GNNs in the considered task. If the performance of GNN or kernel is close to that of one of the basclines, that would mean that the GNN/kernel fails to encode accurately graph representations, and therefore, graph similarities.
4.4 EXPERIMENTAL. SETTINGS
Normalization. As discussed above, the function defined in equation [0, 1). The similarity of two graphs G1 and G2 is equal to if and only if G2 and G2 are isomorphic
gives gives an output in the range
4

---

Under review as a conference paper at ICLR 2021
to each other. We normalize the obtained kernel values follows such that they also take values in the range [0, 1]: kiy- = ks/ Pu///ey /ka,. where kiy is the kernel between graphs G, and Gj. For the GNNs, we compute the cosine similarity between the graph representations of the penultimate layer as follows: +[ = ||= where z; is the representation of graph G,- Note that the ReLU function has already been applied to these representations, and thus the cosine similarity also takes values between 0 and 1. In fact, the two employed normalization schemes (i. e., for kernels and GNNs) are equivalent since a kernel value corresponds to an inner product between the representations of two graphs in some Hilbert space.
We should stress that the normalized kernel value and cosine similarity can take a value equal even if the compared graphs are mapped to different representations. Indeed, if the angle between the vector representations of two graphs 0%, then their normalized kernel value/cosine similarity is equal to 1. To avoid such a scenario, we could define a distance function between graphs and accordingly compute the Euclidean distance between the graph representations generated by the different approaches. However, it turns out that most widely-used learning algorithms compute the inner products between the input objects or some transformations of these objects. In fact, when learning with kernels, we usually normalize the kernel matrices using the equation defined above before feeding to a kernel method such as the SVM classifier. Therefore, we believe that evaluating the "similarity" of the obtained representations is of higher significance than evaluating their "distance".
Evaluation metries. To assess how well the different approaches approximate the similarity func- tion defined in equation [] we employed two evaluation metrics: the Pearson correlation coefficient and the mean squared error (MSE). The Pearson correlation coefficient measures the linear rela- tionship between two variables. It takes values between -1 and 1, while a value of 1 denotes total positive linear correlation. In our setting, high value of correlation would mean that the approach under consideration captures the relationships between the similarities (e. g., whether the similarity of pair of graphs is greater lower than that of another pair). The second measure, MSE, is equal to the average squared difference between the estimated values and the actual values. A very small value of MSE denotes that the derived similarities are very close to those produced by the func- tion defined in equation ! A credible graph representation Srariing/similaiity approach would yield both a high correlation and a small MSE. The former would ensure that similar/dissimilar graphs are indeed deemed dimilar/dissmmilar by the considered approach, while the latter would verify that the similarity values are on par with those produced by the function defined in equation [ Note that the correlation between the output of constant function and the output of equation i is not defined since the values produced by the constant function have a variance equal to zero
plypepparameters For RW, we set X to 0.01. For GR, we count all the graphlets of size 3. For the WL kernel, we choose the number of iterations from 21. 63. For PM, the dimensionality of the embeddings d and the number of levels L are set equal to 6 and 4, respectively. For the GraphHopper kernel, a linear kernel is used on the -aluue attributes.
For the GNNs, we use 2 neighborhood aggregation layers. For GraphSAGE, we use the mean function to aggregate the neighbors of a node, For ChebNet, we use polynomials of order 2, and for ARMA, we set the number of stacks K to 2 and the depth T also to 2. The hidden-dimension size of the neighborhood aggregation layers is set equal to 64. We apply the ReLU activation function to the output of each neighborhood aggregation layer. As mentioned above, we use 3 common readout functions: sum, mean and max. The output of the readout function is passed on to a fully- connected layer with 32 hidden units followed by ReLU nonlinearity. The output of the ReLU function corresponds to the representation of the input graph (i. e., each graph is represented by a 32-dimensional vector). For Provably Powerful GNN, we use network suffix that consists of an invariant readout function followed by 2 fully connected layers. To train all neural networks, we use the Adam optimizer with learning rate 0.001. We set the batch size 32 and the number of epochs to 100. We store the model that achieved the best validation accuracy into disk. At the end of training, the model is retrieved from the disk, and we use it to generate graph representations.
For deterministic approaches, we compute the graph similarities once and report the emerging correlation and MSE. For the remaining approaches (e. g., GNNs, since their parameters are randomly initialized), we repeat the experiment 10 times and report the average correlation, the average MSE and the corresponding standard deviations.
Protocol.
5

---

Under review as a conference paper at ICLR 2021
Corneetton
0.55
0.45
0.25
0.24
0.25
MSE
2.0
2024
616
GCN
1-das.
Erith SAGE
civ anki
Hopper
GNN Praedfil
Figure 2: Performance of the different approaches without node features. For GNNs, the different colors indicate the three pooling functions: sum (o), mean (o), and max The horizontal lines correspond to the two baselines (random, constant).
Implementations. For the graph kernels. we used the implementations contained in the GraKeL library (Siglidis al., 2020). For 1-2 GNN, k-hop GNN, and Provably Poewrful GNN, we use the publicly available implementations provided by the authors. The remaining GNNs were imple- mented using the Pytorch Geometric library (Fey & Lenssen 2019).
4.5 RESULTS
4.5.1 No FEATURES
In the first set of experiments, we do not use any pre-computed features, and therefore, the emerg- ing representationssiimilaaiee
rely solely on the representational capabilities of the different ap- proaches. Note that all GNNs except Provably Powerful GNN and most kernels require the nodes be annotated with either continuous attributes discrete labels. Therefore, for these approaches, we annotate each node with single feature (i. ei. the discrete label 1 or the real value 1.0).
For GNNs, we consider two alternatives: (1) we randomly initialize the parameters of the models and we perform feedforward pass generate the graph representations or (2) we randomly initialize the parameters of the models, we train the models on some independent dataset and then we perform the feedforward pass to generate the representations. Kernels are, in sense, unsupervised, and cannot be trained on any dataset. The obtained results for two aforementioned cases are illustrated in Figures and 3 Note that in the second case, the models were trained on the MMDB-BINAYY graph classification dataset (results for two other datasets are given in the Appendix).
In terms of correlation, 1-GNN and GIN the best-performing approaches followed by GG-NN and one variant of Chebnet. The 6 kernels along with 2-hop GNN and Provably Powerful GNN perform slighly worse than the above models. In terms of MSE, the kernels outperform in general the GNNs. Notably, some kernels such as WL and PM achieve very low values of MSE. On the other hand, most GNNs fail to outperform the random baseline. Specifically, the only models that outperform this baseline are 1-GNN, 2-hop GNN, GG-NN with sum pooling, Chebnet with sum pooling and Provably Powerful GNN with max pooling. With regards the three pooling functions, the sum operator seems to outperform the others. Furthermore, it is important to mention that more powerful architectures (e. g., 1-2-GNN. 2-hop GNN, Provably Powerful GNN) do not necessarily lead to higher correlation and lower MSE than standard, less expressive GNNs. We next investigate how the performance the GNNs changes when the models are first trained on the IMDB-BINARY dataset. The results are shown in Figure 3 We observe that there is decrease in correlation, and no GNN achieves higher correlation than the ones achieved by the WL and PM kernels anymore. On the other hand, the MSE of most GNNs also decreases. For instance. most GNNs now yield lower MSEs than the random baseline. However, still, GCN, GAT and GraphSAGE fail outperform this baseline.

---

Under review as a conference paper at ICLR 2021
Corneetton
0.55
0.45
0.25
0.24
0.35
MSE
2.0
2024
666
GCN
1-480.
Erith SAGE
ciu
anka
Hopper
GNN Prnerfil
Figure 3: Performance of the different approaches without node features. The GNNs were trained on the IMDB-BINARY dataset, and the different colors indicate the three pooling functions: sum (o), mean (o), and max (o). The horizontal lines correspond to the two baselines (random, constant).
Figure 4: Performance of the different approaches with node features. For GNNs, the different colors indicate the three pooling functions: sum (+), mean (+), and max (+). The horizontal lines correspond to the two baselines (random, constant).
4.6 THE EFFECT OF NODE FEATURES
In GNN literature, is common practice to local features (e. g-, degree) as node attributes. In previous studies, has been reported that using node degrees as input features leads to an increase in performance on almost all graph classification datasets (Errica al.) 20200). We next investigate what is the impact of such features on the learned graph representations. In the first set of experiments, we assign single feature to each node, e., its degree. the second set of experiments, each node is annotated with a 2- 2-dimensional vector where the two elements correspond to its degree and the number of triangles labels/attribute, and hence, it is excluded from the evaluation. Furthemore, all the other kernels except GraphHopper can only handle discrete node labels. For the first set of experiments, since degrees are natural numbers, we map each unique pair of features (i. e., degree and trangle participation) to a natural number.
which it participates. Note that the GR kernel cannot handle node
treat them node labels. For the second set of experiments,
Figures and 5 iillustrate the obtained results for the of randomly initialized GNNs and GNNs respectively. We observe that GraphHopper, the only kernel that can naturally handle multi-dimensiona continuous node features, takes advantage of the node degree and triangle participation information since it exhibits very high correlation and a small MSE. On the other hand, the quality of the representations learned by the remaining kernels when these features are taken into account. The addition of the degrees leads to slight increase in large increase in MSE. When both features are considered. there is still
trained on
be lower
correlation, but also large increase in MSE, but also decrease in correlation. This suggests that for kernels that are not designed to operate on graphs with continuous node attributes, using these features may result into a decrease in performance. In the case of randomly initialized GNNs, in the first set of experiments, we observe an increase in correlation between most models and the considered graph similarity function. The models, however, reach similar MSE levels to the previous ones, and most of them are still outperformed by the random baseline. This changes when triangle participation is taken into account. The correlations remain high, while now all the models outperform the random baseline. 1-2-GNN, 1-GNN and GG-NN achieve the highest levels of correlation, while 2-hop GNN, GG-NN and Provably Powerful GNN are the best-performing models in terms of MSE. Again, more compli-

---

Under review as a conference paper at ICLR 2021
2555 5.6 S
Figure 5: Performance of the different approaches with node features. The GNNs were trained on the IMDB-BINARY dataset, and the different colors indicate the three pooling functions: sum (o), mean (o), and max (o). The horizontal lines correspond to the two baselines (random, constant).
Pair P3 vs. Kg.
(b) Pair 2: Cg Sa-
(c) Pair 3: P3 T(9,3).
(d) Pair 4: C3 vs. 2)),
(e) Pair S7 vs. Cg.
(I) Pair 6: C3 vs. Cg.
Figure 6: Performance of 1-GNN with with respect to the different activation functions.
cated models do not necessarily outperform simpler models. When trained on correlation between the models and equation decreases. At the same time, the models yield lower and slightly higher MSEs in the first and second set of experiments, respectively.
the
4.6.1 WHICH PAIRS ARE HARD?
We next find for each approach the similarity that deviates most from the one computed using equa- tion [ These pairs of graphs can be thought as the most challenging for a model or kernel. For each approach,
find the pair of graphs which maximizes the absolute difference between the sim- ilarity computed using equation T and the one produced by the model/kernel. Note that for GNNs, focus on the worst-case scenario independent of the pooling function. The different pairs of graphs are illustrated in Figure [ Surprisingly, a lot of methods/kernels fail to accurately estimate the similarity structurally very dissimilar graphs. For instance, GCN, GAT, GraphSAGE, ARMA. Chebnet, SP and GraphHopper all found the first two graphs (the path graph P2 and the complete graph on 9 vertices)
be identical to each other e., similarities equal 1), while the output of equation [is is 0.166. In the case of the two kernels, this is because the implicit vector representa- tion of one graph a positive scalar multiple of the representation the other. With regards to GNNs, note that the above models use the mean function to aggregate the representations of their neighborhoods. When such neighborhood aggregation approaches are followed by mean or max pooling functions, they produce identical representations for the P2 and Kg graphs. Another pair of graphs which turns out to be challenging for several approaches is the one consisting of the cycle graph with 9 vertices and the star graph Sg, i., tree with internal node and 8 leaves. The out- put of equation for this pair is equal to 0.235, while the similarities produced by all the following approaches are greater than 0.900: GIN, 1-GNN, GG-NN, 2-hop GNN and RW. The of graphs correspond to the worst-case scenarios for Provably Powerful GNN, 1-2-GNN, PM and WL. respectively. The similarity between the path graph P2 and the Turán graph (99,3) ei. 3rd pair) is 0.192 according to equation I while the representations generated by Provably Powerful GNN yielded a similarity equal to 0.955. Likewise, the output of equation is 0.258 for the 4th pair of graphs, while 1 1-2-GNN produced a value equal to 0.922. The star graph S7 along with the cycle graph with vertices e., 5th pair) led PM to the worst similarity estimation. While equation gave a similarity of 0.251, the normalized kernel value was equal to 0.773. The last pair of graphs, the cycle graph with 3 vertices and the cycle graph with 9 vertices, turns out to be the hardest for the WL kernel. While the value of equation Tis 0.384, the normalized kernel value is equal to 1. Again, this is due to the fact that the vector representation one graph a positive scalar multiple of the representation of the other.
four pairs
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing. In Proceedings of the 36th International Conference on Machine Learning, pp. 21-29, 2019.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, pp. 339-350, 2015.
Lu Bai, Yuhang Jiao, Lixin Cui, and Edwin R Hancock. Learning Aligned-Spatio Graph Convolu- tional Networks for Graph Classification. In Proceedings of the 2019 Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 464-482, 2019.
Pablo Barceló. Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The Logical Expressiveness of Graph Neural Networks. International Conference on Learning Representations, 2020.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, al. Interaction Networks for Learning about Objects, Relations and Physics. In Advances in Neural Information Processing Systems, pp. 4502-4510 2016.
Filippo Maria Bianchi, Daniele Grattarola, Cesare Alippi, and Lorenzo Livi. Graph Neural Networks with Convolutional ARMA Filters. arXiv preprint drXiv:1901.013:4 2019.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest- poortess--athhho kernels on graphs. In Proceedings of the 5th IEEE International Conference on Data Mining, pp. 74-81, 2005.
Ines Chami, Zhitao Ying. Christopher Ré, and Jure Leskovec. Hyperbolic Graph Convolutional Neural Networks. In Advances in Neural Information Processing Systems, pp. 4868-4488 4879,887999 2019.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems, pp. 15894-15902, 2019.
Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18(03):265-22) 2004.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring Graph Neural Networks for Node Disambiguation. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 21 2126-2132, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems, pp. 3844-3852, 2016.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In 8th International Conference on Learning Represen- tations, 2020.
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. Scal- able kernels for graphs with continuous attributes. In Advances in Neural Information Processing Systems, pp. 216-224, 2013.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:
2019.
Claudio Gallicchio and Alessio Micheli. Fast and Deep Graph Neural Networks. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 3898-3905, 2020.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. In Proceedings of the 36th International Confer- ence on Machine Learning, pp. 2083-2099 2019.

---

Under review as a conference paper at ICLR 2021
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and Representational Limits of Graph Neural Networks. In Proceedings of the 37th International Conference on Machine Learning. 2020.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pp. 129-143. 2003.
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, pp. 1263-1272 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A New Model for Learning in Graph Domains. In Proceedings of the 2005 IEEE International Joint Conference on Neural Networks, volume 2. pp. 729-734, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning Large Graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Mark Heimann, Tara Safavi, and Danai Koutra. Distribution of Node Embeddings as Multiresolution Features for Graphs. In Proceedings of the 2019 IEEE International Conference on Data Mining, pp. 289-298 2019.
Sergei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding Isomorphism Bias in Graph Data Sets. arXiv preprint urXiv: 12091, 2019.
Yilun Jin, Guojie Song, and Chuan Shi. GraL Graph Neural Networks with Local Structural Patterns. In Proceedings of the 34th AAAI Conference Artificial Intelligence, pp. 4361-4368, 2020.
Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, and Chiranjib Bhattacharyya. Global graph kernels using geometric embeddings. In Proceedings of the 31st International Conference on Machine Learning, pp. 694-702, 2014.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized Kernels Between Labeled Graphs. In Proceedings of the 20th International Conference on Machine Learning, pp. 321- 328, 2003.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer- molecular design, 30(8): 595-608, 2016.
Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems, pp. (092-7101,2015
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02907 2016.
Thomas N Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Net- works. In Proceedings of the 5th International Conference Learning Representations, 2017.
Risi Kondor and Horace Pan. The Multiscale Laplacian Graph Kernel. In Advances in Neural Information Processing Systems, pp. 2990-2998, 2016.
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On Valid Optimal Assignment Kernels and Applications Graph Classification. In Advances in Neural Information Processing Systems, pp. 1623-1631, 2016.
Nils M Kriege, Christopher Morris, Anja Rey, and Christian Sohler. A Property Testing Framework for the Theoretical Expressivity of Graph Kernels. In Proceeding of the 27th International 2018.
Joint Conference on Artificial Intelligence, pp.
Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Deriving Neural Architectures from Sequence and Graph Kernels. In Proceedings of the 34th International Conference on Machine Learning, pp. 2024-2033 2017.
10

---

Under review as a conference paper at ICLR 2021
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks, arXiv preprint
2015.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In International Conference on Learning Representations, 2019b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. Proceedings of the 36th International Conference on Machine Learning, pp. 4363- 4371,
Christopher Morris, Kristian Kersting, and Petra Mutzel. Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs. In Proceedings of the 2017 IEEE International Conference on Data Mining, pp- 327-336, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Net- works. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4602-4609, 2019.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neu- mann. TUDataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational Pooling for Graph Representations. In Proceedings of 36th the International Conference Machine Learning, pp. 4663-4673, 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning Convolutional Neural Net- works for Graphs. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2014-2023, 2016.
Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching Node Embed- dings for Graph Similarity. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 2429-2435, 2017.
Giannis Nikolentzos, Polykarpos Meladianos, Stratis Limnios, and Michalis Vazirgiannis. A degen- eracy framework for graph similarity. In Proceedings of the 27th International Joint Conference Artificial Intelligence, pp. 2595 2901, 2018a.
Giannis Nikolentzos, Polykarpos Meladianos, Antoine (ean-Pierry Tixier, Konstantinos Skianis, and Michalis Vazirgiannis. Kernel Graph Convolutional Neural Networks. In Proceedings of the 27th International Conference on Artificial Neural Networks, pp. 22-32, 2018b.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: survey, arXiv preprini arXiv: 12218, 2019.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 2020.
Jan Ramon and Thomas Gärtner. Expressivity versus efficiency of graph kernels. In Proceedings of the 1st International Workshop on Mining graphs, Trees and Sequences, pp. 65-74, 2003.
Bastian Rieck, Christian Bock, and Karsten Borgwardt. Persistent Weisfeiler-Lhmman Proce- dure for Graph Classification. In Proceedings of the 36th International Conference on Machine Learning. pp. 5448 1448-5458,1 2019.
Ryoma Sato. Survey on The Expressive Power of Graph Neural Networks. arXiv preprint 04000, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation Ratios of Graph Neural Net- works for Combinatorial Problems. In Advances in Neural Information Processing Systems, pp. 4081-4090, 2019.
11

---

Under review as a conference paper at ICLR 2021
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks. arXiv preprint arXiv:2002.03155, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational Capabilities of Graph Neural Networks. IEEE Transactions Neural Networks, 20(1):81-102, 2008.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1):61-8)) 2009.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The aapnik-chervonenke dimension of graph and recursive neural networks. Neural Networks, 108:248-223 259, 2018.
Younjoo Seo, Andreas Loukas, and Nathanaël Perraudin. Discriminative structural graph classifica- tion. arXiv preprint 1905. 2019.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Proceedings of the 12th International Conference Artificial Intelligence and Statistics, pp. 488 495, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borg- wardt. Weisfciler-Lehman Graph Kernlls. Journal of Machine Learning Research, 12(9), 2011.
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. Grakel: A graph kernel library in python. Journal of Machine Learning Research, 2-(54):1-5, 2020.
Alessandro Sperduti and Antonina Starita. Supervised Neural Networks for the Classification of Structures. IEEE Transactions Neural Networks, 8(3):714-7335 1997.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein Weistciler-Lehman Graph Kernels. In Advances in Neural Information Processing Systems, pp. 6439, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph Attention Networks. In Proceedings of the 6th International Conference on Learn- ing Representations, 2018
Saurabh Verma and Zhi-Li Zhang. Stability and Generalization of Graph Convolutional Neural Networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? arXiv preprint arXiv: 181.0006,, 2018
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference on Learning Representations, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep Graph Kernels. In Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1365-1374 1374, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical Graph Representation Learning with Differentiable Pooling. In Advances in Neural Information Processing Systems, pp. 4800-4810, 2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware Graph Neural Networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 7134-7143, 2019.
12

---

Under review as a conference paper at ICLR 2021
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An End-to-Enn Deep Learning Architecture for Graph Classification. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 4438 0888-444, 2018.
A APPENDIX
A.1 EXPANDED RELATED WORK
Graph kernels. Graph kernels have attracted lot of attention in the past 20 years, and have been applied to several learning problems on graphs. A graph kernel symmetric, positive semidefi- nite function that maps graphs implicitly or explicitly into some Hilbert space, and then computes the inner product between the graph representations in that space. Early work in this area includes functions that compare substructures of graphs that are computable in polynomial time such as ran- dom walks (Gärtner et al.] 2003 Kashima et al., 2003), shortest paths (Borgwardt & Kriegel| 2005) and subtrees (Ramon & Gärtner (003). More recently, research in the field has been directed to- wards more scalable approaches. This led to the development of the Weisfeiler-Lehman subtree kernel which employs relabeling procedure inspired by the Weisfeiler-Lehman test of isomor- phism (Shervashidze et al. 2011). Several extensions of the Weisfeiler-Lehmae
kernel have also been explored in the previous years (Morris et al. 2017 Togninalli et al.. 2019; Rieck al. 2019). Other recent works use the orthonormal representations associated with the Lovász & number to produce subgraph representations (Johansson et al., 2014). employ assignment kernels to compare
substructures (Kriege et al. 2016 Nikolentzos et al. 2217), compare the neighborhood subgraphs of vertices using spectral approaches (Kondor Pan 2016). or use randomized binning approaches (Heimann et al. 2019). Recently, some frameworks have also been proposed for deriving variants of
graph kernels. These frameworks capitalize on recent advances in natural language processing (Ya-
nardag & Vishwanathan| 2015) For a thorough survey of graph kernels, the interested reader is referred to Nikolentzos et al. (2019)
graph decomposition techniques (Nikolentzos et al. 201 8a).
GNNs. GNNs have recently emerged as another promising family of approaches for performing machine learning tasks on graphs. These models have attracted a lot of attention in the past few years. The main advantage of GNNs over graph kernels is that they do not require expensive Gram matrix computations and that they can naturally handle node and edge attributes (continuous values in general). Most GNN variants that have been proposed in the past years (Li et al., 2015] Def- ferrard et al. 2016 Kearnes et al. 2016 Lei et al. 2017 Hamilton et al.] 2017 Kipf & Welling 2017 Velickovic al.) 2018: Zhang al.) 2018) all share the same basic idea, and can be refor- mulated into a single common framework, known as Message Passing Neural Networks (MPNNs) (Gilmer et al. 2017). These models employ an iterative message passing procedure, where each node updates its feature vector by aggregating the feature vectors of its neighbors. This procedure is typically followed by a pooling phase where a feature vector for the entire graph is produced using some permutation invariant function. All these models correspond to minor adaptations of previous works (Sperduti & Starita 1997, Gori et al.) 2005 Scarselli et al.) 2009). There have been proposed several extensions and improvements to the MPNN framework. Most studies have focused on the message passing procedure and have proposed more expressive aggregation functions (Mur-
phy al. 2019 Seo et al., 2019 Dasoulas et al. 2020), schemes that incorporate different local structures or high-order neighborhoods (Jin et al.] 2020; Abu-El-Haija et al., 2019), approaches that utilize node positional information (You et al. (019), non-euclidian geometry approaches (Chami ct al. 2019). while others have focused on efficiency (Gallicchio & Micheli] (2020). Fewer works have focused on the pooling phase and have proposed more sophisticated pooling functions (Ying et al., [2118] Gao & Ji (219)) Note that there exist GNNs that do not belong to the family of MPNNS (Niepert et al.) 2016) Nikolentzos et al.) 2018b Bai et al. 2019). survey of recent advancements in GNN models can be found in Wu et al. (2020).
Expressive power of graph kernels and GNNs, Over the past years, the expessiveness of graph kernels was assessed almost exclusively from experimental studies. Therefore, still, there is no theoretical justification on why certain graph kernels perform better than others. From the early days of the field, it was clear though that the mapping induced by kernels that are computable in polynomial time is not injective (and thus these kernels cannot solve the graph isomorphism problem) (Gärtner et al. 2003). Recently, Kriege et al. 2018) proposed framework to measure the
13

---

Under review as a conference paper at ICLR 2021
expressiveness of graph kernels based on ideas from property testing. It was shown that some well- established graph kernels such as the shortest path kernel, the graphlet kernel, and the Weisfeiler- Lehman subtree kernel cannot identify basic graph properties such as planarity or bipartitness.
With the exception the work of Scarselli et al. (2008), until recently, there has been little attempt to understand the expressive power of GNNs. Several recent studies have investigated the connections between GNNs and the Weisfeiler-Lehmne For instance, it was shown that standard GNNs do not have more power in terms of distinguishing between non-isomorphic graphs than the WL algorithm (Morris et al. 2019 Xu et al. 2018). Morris al. (2019) proposed family of GNNs which rely on message passing scheme between subgraphs of cardinality k, and which have exactly the same power in terms of distinguishing non-isonee -somooomopp graphs as the set-based variant of the k-Wl. algorithm. introduced k-order graph networks which are at least as powerful as the folklore variant of the k- WI. graph isomorphism test in terms of distinguishing non-isomorphic graphs. These models were also shown to be universal (Maron et al. 2019c Keriven & Peyré 2019), but require using high order tensors and therefore are not practical. Chen et al. (2019) show that the two main approaches for studying the expressive power of GNNS, namely graph isomorphism testing and invariant function approximation, are equivalent to each other. Futhermore, the authors propose a GNN that is more powerful than 2-W1. (Barceló al. (2020) rely on connection between the WL algorithm and first order logic, and characterize the expressive power of GNNs in terms of classical logical languages. The impact of random features on the expressive power of MPNNs considered in Saao et al. (2020). Nikolentzos et al. (2020) show that standard GNNs cannot identify fundamental graph properties such as freeness and connectivity, and they propose model that can identify these properties. MMrrphy et al. (2019) and Dasoulas et al. (2020) take into account all possible node permutations and produce universal graph representations. The emerging problems becomes intractable once the number of nodes is large and they propose approximation schemes to make the computation tractable in practice. Some recent works have studied the generalization properties of GNNs (Scarselli et al. 2018)] Veemm & Zhang] 2019 Garg et al., 2020). For comprehensive overview of the expressive power of GNNs, the interested reader is referred to Sato (2020).
(WL) test isomorphism and its higher-order variants.
similar spirit, (Maron et al.) 2019a)
A.2 EXPECTED VALUE OF SIMILARITY FUNCTION
The similarity function defined in equation D is intractable. However, we should mention that if instead of the maximum over all permutation matrices, we are interested in the expected value, this can be computed efficiently as follows:
F(Gr, = -Epill E Σラ [A & PA.PT] 1.
Σ
[Ai PP.P
|| |
A F
|
(2)
Furthermore, note that:
1 P1A + nl n!
1 PT n
2m2
Ep-n PA,P
P.A.P +....
(3)
nnn
where m2 is the number of edges of G2, n max(ni, n2) where ni and no are the number of nodes of G2 and G2, respectively, and Jn is the n x n matrix of ones. Then, from equation 2 and equation we have that:
f(G1, G2) 2m1 2ma/n(a-1) 2/m1m
/2mi /2m²
n(n 1)
where m, and m2 are the number of edges of G1 and G2, respectively. Interestingly, for classes of graphs where A = P PAP holds for any permutation matrix P. then f(G,, G2) f[G G2)- Clearly, the above is true for the class of complete graphs Kn.
A.3 FURTHER EXPERIMETAL RESULTS
A.3.1 IMPACT OF HYPERPARAMETERS
We next will investigate how performance varies with respect to two hyperparameters: (1) the di- mensionality of the hidden layers, and (2) the number of message passing layers. The greater the
14

---

Under review as a conference paper at ICLR 2021
0.8
Correlation
0.6
0.4
16
64
128
0.29
0.19
MSE
0.14
0.09
0.04
-0.01
16
32
64
128
Figure 7: Performance of 1-GNN with with respect to the dimensionality of the hidden layers.
value of these two hyperparameters. the larger the capacity of the model. Therefore, expect the models to produce better and better graph representations as these two hyperparameters increase. We study the impact of these hyperparameters
the performance of the 1-GNN model. The ob- tained results are shown in Figures 7 and 8 Note that the model not trained on any dataset. We observe that the correlation between NGNN and the considered similarity function increases the dimensionality of the hidden layers increases. With regards to the MSE metric, strikingly. we ob- serve that it also slightly increases as the dimensionality of the hidden layers increases. We next investigate how performance of the 1-GNN model changes as a function of the number of message passing layers. As can be seen in Figure the correlation between 1-GNN and the proposed func- tion first increases, while then decreases. The best results are obtained for 3 message passing layers. On the other hand, MSE generally decreases as the number of message passing layers increases.
A.3.2 IMPACT OF ACTIVATION FUNCTIONS
We also investigate what is the impact of different activation functions on the performance of 1- GNN. We experiment with four activation functions. namely tanh, sigmoid, ELU and ReLU. We also use message passing layers that contain no activation functions at all e., linear activation function). Again, we do not train the model any dataset. The obtained correlations and MSFs are given Figure g We can see that ELU and tanh yield most cases higher correlations and lower MSEs than the remaining activation functions, while sigmoid is the worst-performing activation function.
A.3.3 GNNS TRAINED ON MUTAG AND PTC-MR
We next present some results similar to those of Figures 3 and However, we now train the GNNs on two other standard graph classification datasets: MUTAG and PTC-MR. Note that these datasets contain node-labeled graphs, however, for the purposes this study, we ignore these labels. We first present the results for the case where nodes are not annotated with any pre-computed features. The results are shown in Figures 10 and [I We observe that GIN, 1-GNN and 1-2-GNN both trained on MUTAG and on PTC-MR generate representations that yield high values of correlation, while the representations produced by GCN and 2-hop GNN lead to the lowest levels of correla- tion. Interestingly, when GAT is combined with the max mean pooling functions, its generated
15

---

Under review as a conference paper at ICLR 2021
0.8
Correlation
0.6
0.4
0.34
0.29
0.24
MSE
0.19
0.14
0.04
-0.01
Figure 8: Performance of 1-GNN with with respect to the number of message passing layers.
0.8
Correlation
0.6
0.4
ELU
linear
ReLU
sigmold
tanh
0.34
0.24
MSE
0.19
0.14
++
0.09
0.04
-0.01
ELU
linear
ReLU
sigmoid
lanh
Figure 9: Performance of 1-GNN with with respect to the different activation functions.
representations achieve much lower correlation compared to the case where the model is followed by the sum aggregator. In terms of MSE, I-GNN, ARMA, ChebNet, 2-hop-GNN and GIN are the best berf-performing models, while GCN, GAT, GraphS and Provably Powerful GNN are the worst- perss--erformng models. For the models trained PTC-MR, much lower MSE is attained when the models are followed by the sum pooling function. With regards to the three pooling functions, in general, the operator outperforms the two other operators. For the models that were trained
16

---

Under review as a conference paper at ICLR 2021
Corneetton
0.55
0.45
0.25
-0.55
MSE
0.33
0.24
1-OKN
1-2-GNN
SAGE
GNK
Poweda
Figure 10: Performance of the different approaches without node features. The GNNs were trained on the MUTAG dataset, and the different colors indicate the three pooling functions: sum (+). mean (o), and max (+). The horizontal lines correspond to the two baselines (random, constant).
0.85
Conretation
0.35
-0.55
0.34
MSE
0.55
0.54
-0.53
00h
GAT
1-Ghh
Clazh
CS-RW
GIN
ARMA
2-2-GRR
2-h05
PROVDDS
Pranda
Figure 11: Performance the different approaches without node features. The GNNs were trained on the PTC-MR dataset, and the different colors indicate the three pooling functions: sum (o), mean (o), and max (+). The horizontal lines correspond to the two baselines (random, constant).
the PTC-MR dataset, the max operator achieves MSEs comparable or lower than those of the sum operator, but also achieves smaller correlations than those of the sum operator almost all cases.
We next evaluate the expressive power of the different models in the case of graphs whose nodes are annotated with local features such as their degree and the number triangles which they participate. The models are first trained on the two aforementioned datasets (i. e., MUTAG and PTC- MR), and then, the synthetic graphs are fed into them to produce a vector representation for each one of those graphs. The results illustrated in Figures 12 and 13 For both training scenarios, with single feature, GraphS GCN, 1-GNN and GAT achieve the highest correlations in general. The lowest MSEs emerge from 1-2-GNN, 1-GNN, 2-hop GNN and GraphSAGE. When both features passed on to the models, and for models trained on MUTAG, GCN, 1-GNN and ARMA followed by the sum pooling function yield high values of correlation. In terms of MSE, GCN and 1-GNN both with sum pooling and 2-hop GNN with max pooling reach the lower values than the remaining models. For models trained on PTC-MR, Provably Powerful GNN yields the highest correlation with equation [ followed by Chebnet, ARMA and GCN, in that order. All the models generally achieve the same levels of MSE, but ARMA, 1-2-GNN, 2-hopGNN and Provably Powerful GNN produce slightly lower MSEs than the others. We also observe that the use of the degree as feature leads to an increase in correlation, while the use of an extra feature (i. triangle participation) leads to decrease in correlation. In terms of MSE, we can that generally the of single feature results into a decrease in MSE, while the use of both features leads to a further decrease in MSE. With regards the pooling functions, in the case of the models trained MUTAG, the sum operator leads to much better performance (i. e., higher correlations and lower MSEs) compare to the other two operators. In the case of the models trained on PTC-MR, the operator still leads to
17

---

Under review as a conference paper at ICLR 2021
4.6 2 3.55
Figure 12:
Performance the different approaches with node features. The GNNs were trained on the MUTAG dataset, and the different colors indicate the three pooling functions: sum (o), mean (0), and max (+). The horizontal lines correspond to the two baselines (random, constant).
Figure 13: Performance of the different approaches with node features. The GNNs were trained on the PTC-MR dataset, and the different colors indicate the three pooling functions: sum (o), mean and max (+). The horizontal lines correspond to the two baselines (random, constant).
higher correlations in most cases, but in terms of MSE, no pooling function results into consistently better performance than the others.
18


Reviews:
[{"review_id": "qW37RKVPV-Y", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to study the expressiveness of some graph kernels and graph neural networks. To this aim, the authors build a synthetic dataset of graphs and compute the pairwise similarities, which are compared to an oracle function supposed to quantify how much two graphs are isomorphic.\n\nThe objective pursued in this paper seems to me to be interesting and useful for practitioners but the manuscript has important limitations.\n\n\n1- The oracle similarity introduced in the paper has good properties, that one can expect from a similarity function. However, taking this function as a reference oracle in the whole sequel is not properly justified. How is this similarity function canonical? It would be interesting to cite some references on this question.\n\nFor example, does the reference oracle give better accuracy scores on some classification problems than the kernels and neural networks used in the paper? This would be an important indication to justify the choice of this reference.\n\nSection 3: Even if I agree that the number of permutation matrices is of order n!, it does not prove that the optimization problem is intractable. There exist other algorithms than exhaustive search.\n\n\n2- The synthetic dataset is both small (only 191 graphs) and with a small variety of graphs (between 2 and 9 vertices, between 1 and 36 edges). Under these conditions, isn't it difficult to draw solid conclusions?\n\n\n3- I am not sure that we can expect from a GNN to evaluate accurately the similarity between two graphs from the synthetic dataset at stake, if it was trained on a very different classification dataset?\n\nI have another concern with the fact that some kernels and neural networks capture how the attributes are connected to each other, and do not really catch the topology of an unannotated graph. In this context, giving the same attribute value to all nodes as proposed on page 6 just to be able to use kernels designed for annotated graphs seems strange.\n\n\nFor all these reasons, I believe that the empirical study presented in this paper is not strong enough to justify its publication in this conference.\n\n\nTypos\npage 2: simiarlity\npage 2: expessiveness", "extra_scores": {}, "extra_text": {}}, {"review_id": "TDOBXcFjlsu", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper deals with supervised graph classification comparing GNN and graph kernel approaches. The authors define an intractable graph similarity functions, which boils down to a normalized graph edit distance. The authors then empirically study how well well-known graph kernel and GNN architectures align within their predictions with this distance. To that, the authors generate small-scale, random graph datasets consisting of various types of graphs.\n\nThe authors find out that graph kernels still seem to be competitive compared to GNNs, and in some settings, GNNs do not perform better than trivial baselines.\n\nPro:\n- Easy to read \n- Cover of related work is good\n\nCons:\n- Most results are already known, and have been found in previous studies\n- Not much insight is given, and no methodological contribution (How can we overcome limitations of current models?)\n- Generation of synthetic dataset seems arbitrary, no motivation given. Extremely small. \n\nRemarks:\n- Please give more motivation for dataset generation and details on generation\n- You might consider citing the works of Andreas Loukas on the limits of GNNs\n- p. 2. \"simialrity\" -> similarity\n- p. 3. please give a proof/citation that shows that solving (1) is indeed not tractable. Just stating number of permutations as a reason is not enough.\n- p. 4. The GR kernel can be trivially extended to work with labeled graphs, moreover RW kernel can also be extended to work with attributed graphs\n- p. 4. GraphHopper kernel is not SOTA\n\nQuestions:\n- Why should the similarity functions of (1) be suitable for all data distributions? E.g., on some data distributions local properties might be more important.\n- What is the motivation behind first training on IMDB-BINARY? This seems arbitrary.\n- Why did you fix GNN hyperparameters? How were the hyperparameters for the kernels chosen?", "extra_scores": {}, "extra_text": {}}, {"review_id": "NNEc3gfl7Ak", "reviewer": "AnonReviewer2", "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": "The paper is an empirical study on the expressive power of graph kernels (GKs) and graph neural networks (GNNs). The paper considers the question whether GKs and GNNs can approximate a fixed graph similarity. The chosen graph similarity is maximal when graphs are isomorphic. Its computation is intractable for most graphs (complexity in $n!$). Experiments are done on very small graphs (at most 9 nodes). Experimental results are provided without any clear conclusion.\n\nOne motivation of the paper is to complement many existing studies on the expressive power of GNNs. As most studies consider graph isomorphism testing, the present paper considers graph similarities. But the paper considers an intractable graph similarity related to the graph isomorphism property because the similarity is maximal when the graphs are isomorphic. Therefore it should be made clear what could be the benefit of the proposed approach. Moreover I am quite concerned with the following questions: why should graph kernels correspond to the chosen graph similarity ? Why should the dot product between graph representations at the penultimate layer correspond to the chosen graph similarity ? Experiments are done on very small graphs and the conclusions are not convincing enough. Therefore, in my opinion, the paper is not ready for publication.\n\nDetailed comments.\n\nIntroduction. The notion of graph similarity should be made more precise. Many graph similarities could be defined for graphs, some of them only based on the graph structure and others using node or edge features. Here, the paper only considers a structural graph similarity related to graph isomorphism. It is not clear to me whether GKs or GNNs should be able to compute this so-called \"true similarity between graphs\". It is not clear to me how the ability to compute such a graph similarity is related to the graph isomorphism property.\n\nRelated work. Please make precise the relation between this section and Appendix A.1\n\nSection 3. The choice of the similarity measure should be justified. Other graph similarities have been defined in the scientific literature. Some graph similarities use the graph structure and node features. Please make precise the objective of Appendix A.2\n\nSection 4. In Section 4.5.1, a second experiment is considered where \"the GNNs are first trained on the IMDB-BINARY dataset\". Please explain how are trained the GNNs in the first experiment and in the second experiment. As such I do not see why the dot product between graph representations at the penultimate layer should correspond to the chosen graph similarity. The GNNs could be trained to compute the chosen similarity. I do not understand why this has not been considered.\n\nSection 4. It is not easy to draw conclusions of the experimental results. \n\nThe paper does not have a conclusion.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "58pQniYfI-9", "reviewer": "AnonReviewer4", "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": "Summary: This paper provides an intensive empirical study on the expressiveness of graph kernels and graph neural networks. It defines an exact but computationally demanding similarity of graphs defined over all possible permutations for adjacency matrices, eq (1), and generate a synthetic dataset of graphs to the scale (up to 9 nodes) where we can compute this quantity. The nomalized kernel value of k_ij of graph kernels and the cosine similarities of GNN-embedded vectors are compared to this exact similarity eq(1) in terms of its correlation coefficients and mean squared errors over carefully chosen graph kernels and graph neural networks in the context of research about the expressiveness. The empirical results are presented when node features are all the same single values (1 or 1.0), and when node features are two values of the degree and the number of triangles in which it participates to. Also, the paper discussed several concrete examples that have a large disagreement on the similarity against the exact similarity eq(1).\n\nComments: This is a very interesting empirical study including not only GNNs but also graph kernels in the scope, but at the same time, it would be still very hard to interpret those presented results. This study is motivated by many existing papers on the GNN expressivenss, and there should be some explicit efforts (or discussions, at least) to connect and relate these empirical results to what we already know on this theme, for example, isomorphism, WL-test relationship, hard-to-discriminate examples, etc.\n\n- The most confusing points would be the disagreement between the correlation measures and the MSE measures. What can we conclude or learn from these results where graph kernels have lower MSE but also relatively lower correlation than GNNs? The paper even lacks any concluding remarks or conclusion section. (by the way, the caption of Fig.6 should be corrected)\n\n- All of the results are based on the criteria of eq (1), but whether this purely adjacency-matrix based similarity would be worth characterizing the expressiveness aspects of GKs and GNNs would be a bit unconvincing. In particular, we know WL-kernel or several GNNs would have a same level of expressiveness as WL tests. But then, why graph pairs in Figure 6 are hard to get its similarities...? A simple WL test seems enough to discriminate these pairs. Are there any rational explanations for this?\n\n- The pre-training (?) over IMDB-BINARY is also not well motivated, and would lack any context. It's from movie reviews in Internet Movie Database (IMDB). How can we expect any information useful for characterizing the synthetic dataset to be learned?\n\n- Also, the worst case analysis over sum, mean, max aggregators would be also misleading. As seen in the GIN paper (Xu et al, ICLR2019), the expressiveness study suggested that we need sum aggregators (rather than mean or max) for the purpose like the paper's synthetic dataset, didn't it?\n\n- In the context of the expressiveness study, it would be quite of great interest to scrutinize how the exact graph topology relates to the graph kernels or graph neural networks even for very small graphs. But in the practical context, the graph topology is only part of the information to generate a good vector representations of nodes or graphs for downstream tasks. Consider examples like the MNIST graph (28x28 2D grid graph) in the ChebNet paper, and how GNNs can use pixel values representing hand-written characters over the grid.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers liked the direction of the paper but unanimously agree that, in its current version, it is not strong enough to justify publication at ICLR. There was no rebuttal from the authors to consider. 
Decision: Reject