Graphs are one of the most ubiquitous kinds of data. However, data analysis methods have been developed primarily for numerical data, and to make use of them, graphs need to be represented as elements of some Euclidean space. An increasingly popular way of representing them in this way are graph neural networks (GNNs). Because data analysis applications typically require identical results for isomorphic graphs, the representations learned by GNNs also need to be invariant with respect to graph isomorphism. That motivated recent research into the possibilities of recognizing nonisomorphic pairs of graphs by GNNs, primarily based on the Weisfeiler-Lehman (WL) isomorphism test. This paper reports the results of a first experimental comparison of four variants of two important GNNs based on the WL test from the point of view of graph representation for downstream classification by means of a support vector machins (SVM). Those methods are compared not only with each other, but also with a recent generalization of the WL subtree kernel. For all GNN variants, two different representations are included in the comparison. The comparison revealed that the four considered representations of the same kind of GNN never significantly differ. On the other hand, there was always a statistically significant difference between representations originating from different kinds of GNNs, as well as between any representation originating from any of the considered GNNs and the representation originating from the generalized WL kernel.
In the present time, graph-structured data are one of the
most ubiquitous kinds of data. However, from the point
of view of data analysis and knowledge discovery in
data, they received attention only during the last decades.
Therefore, data analysis methods for common tasks such
as classification, regression and clustering have been
developed primarily for numerical data, and if they are used
for graph-structured data, graphs needs to be represented
as vectors in some Euclidean space. This requirement is
not specific for graphs, but can also be encountered with
_______________________
Copyright ©2021 for this paper by its authors. Use permitted under
Creative Commons License Attribution 4.0 International (CC BY 4.0).
other kinds of non-numerical data, the best-known
example probably being textual data. The seminal papers about
graph representation [
An increasingly popular way of representing graphs by
vectors is using graph neural networks [
The WL-test iteratively constructs neighbourhood
subtrees rooted in graph vertices. Such a construction can also
be used for graph kernels [
This work-in-progress paper reports a first experimental comparison of two important WL-test-based GNNs with the general relaxed WL kernel from the point of view of graph representation for downstream classification by means of an SVM. Of each GNN, four variants were available, and for all employed GNN variants, two different representations were included into the comparison. The comparison was performed on 20 graphsets created from benchmark datasets and its results were tested for statistical significance.
The next section gives an overview of message-passing neural networks, which are the most common kind of GNNs, and at the same time the kind to which the known WL-test-based GNNs belong. It also recalls the principles of the relaxed WL kernel. The key part of the paper is Section 3, in which the performed experimental comparison is described and its first results are presented. Finally, Section 4 concludes the paper and indicates possible furhter research. 9c : V ! f0; 1gdc , called colouring, where dc dl , 8v 2 V : (c(v))1 + + (c(v))dc = 1, and c fulfils c = (l1; : : : ; ldc ), i.e. the coloring is part of the general labelling, which may in addition contain also other components.
Using this notation and the symbol N(v) for the
neighbours of vertex v in the graph G, the WL isomorphism
test [
Denote AG and A0G the adjacency matrices of G and G0,
respectively, and 1#V the vector (1; : : : ; 1) of length #V .
Then the situation that the WL isomorphism test cannot
reject isomorphism of G and G0 can be characterized by
the following three equivalent conditions [
G0 within #V iterations; (ii) for each tree T , the number of homomorphisms from T to G equals the number of homomorphisms from T to G0; (iii) there exists a matrix X 2 0; 1#V #V solving the following system of linear equations:
AGX = X A0G; X 1#V = 1#V ; 1#>V X = 1#>V : (4) Observe that if G and G0 are really isomorphic, then the equations (4) are solved by the permutation matrix X fulfilling A0G = X >AGX , which transforms AG into A0 . G
Algorithm 1 Weisfeiler-Lehman isomorphism test Require: Graphs G; G0 with sets of vertices V;V 0, sets of edges E; E0, and colourings c; c0 such that V \ V 0 = 0/ ; #V = #V 0, maximal number of iterations h #V 1: Define the colouring c0 : V [ V 0 ! f0; 1gdc [ f0; 1gdc0 by c0(v) = (c(v)
if v 2 V c0(v) if v 2 V 0 5: 6: else 7: 8: 2: Set S0 = c0(V [ V 0) 3: Order S0 as s01; : : : ; s0#S0 4: if exists j = 1; : : : ; #S0 such that #fv 2 V : c0(v) = s0 g 6= #fv 2 V 0 : c0(v) = s0jg then j
Return the fact that G and G0 are not isomorphic Set i = 1 Define the colouring c1 : V [ V 0 ! S0 N0#S0 by c1(v) = (c0(v); (s1; : : : ; s#S0 )); where s j = #fu 2 N(v) : c0(u) = s0jg for j = 1; : : : ; #S0 by 9: Set S1 = c1(V [ V 0) 10: Order S1 as s11; : : : ; s1#S1 11: end if 12: while i < h and #fv 2 V : ci(v) = sijg = #fv 2 V 0 : ci(v) = sijg for j = 1; : : : ; #Si do 13: Increment i = i + 1 14: Define the colouring ci : V [ V 0 ! Si 1 N0#Si 1 ci(v) = (ci 1(v); (s1; : : : ; s#Si 1 )); where s j = #fu 2 N(v) : c0(u) = s0jg for j = 1; : : : ; #Si (3) 15: Set Si = ci(V [ V 0) 16: Order Si as si1; : : : ; si#Si 17: end while 18: if exists j = 1; : : : ; #Si such that #fv 2 V : ci(v) = s0 g 6= #fv 2 V 0 : ci(v) = s0jg then
j 19: Return the information that G and G0 are not isomorphic 20: else 21:
Return the information that the WL test did not reject the isomorphism of G and G0 within h iterations 22: end if (1) (2)
Finally, a feedforward artificial neural network NN will for the purpose of this paper be a stationary connectionist feedforward structure
NN = (I; O; H;C; F ; (Fe)e2C; (Yn )n2H[O) where (5) I; O and H are mutually disjoint sets of input, output and hidden neurons; C
I 8n 2 O : inp(n) = fx 2 I [ H : (x ; n) 2 Cg 6= 0/ , inp(n) is the input set of the neuron n; 8n 2 H : inp(n) 6= 0/ ; out(n) 6= 0/ ; 9Dom R#I : F fF : Dom ! R#Og, F is the set of mappings computable by the NN; 8n 2 H [ O 9Domn R#inp(n) : Yn fy : Domn ! Rg, the elements of Yn are called somatic operators available for the neuron n; 8e 2 C 9Dome R : Fe fj : Dome ! Rg, the elements of Fe are called synaptic operators available for the connection e; all mappings computable by the NN fulfil the following condition of resursive composability: 8F 2 F 8n 2 H [ O 8x 2 inp(n) 9yn 2 Yn 9j(x ;n) 2 F(x ;n)8X 2 Dom 9AX : I [ H [ O ! R – the activation state of NN corresponding to the input X , fulfilling AX jI = X ; AX jO = F(X ); (6) 8n 2 H [ O : AX (n) = yn ((j(x ;n)(AX (x )))x 2inp(n)): (7)
The above definition covers in particular multilayer
perceptrons and radial basis functions, for which a plethora of
theoretical results is available, such as the classical
universal approximation results concerning density of F in
general function spaces [
Rq9w : W ! fF : Dom ! R#Og such that F = w(W ): (8) Needless to say, the parametrizability of F also induces the parametrizability of the sets of somatic operators Yv; v 2 H [ O and synaptic operators Fe; e 2 C. 2.2
Message-passing neural networks (MPNN) are probably
the kind of neural networks most often used for graph
data. They are characterized by the following two
properties [
C \ (H
H)
H` 1
H`: (9) [ 1 ` L 2. The structure of their connections as well as their somatic and synaptic operators attempts to reflect the structure and properties of the graphs to which the network is applied. The approach that is most typical, and at the same time perfectly suitable for the kind of graphs considered in this paper, consists in: network connections attempt to reflect the structure of graph edges, in particular input and output sets of neurons attempt to reflect the neighbourhoods of graph vertices; in each layer ` = 0; : : : ; L, a group of neurons nv;1; : : : ; nv;d` 2 H` can be assigned to a vertex v 2 V , with d0 = dl , and the vector yv(`) = (ynv;1 ; : : : ; ynv;d` ) of their somatic operators for a layer ` < L fulfils yv(`+1) = fu(p`)(yv(`); fag (yu(1`); : : : ; yu(#`N)(v) )); (`) (10) where fu(p`) : Rd`
Rdag ! Rd`+1 is called update function, fu1; : : : ; u#N(v)g = N(v), fa(g`) : Rd` #N(v) ! Rdag is called aggregation function, and dag 2 N with a usual choice dag = d` or dag = d`+1; synaptic operators are not used. 3. The resulting mapping F composed according to (6) is required to be either invariant or equivariant with respect to permutations of the d0 columns of its input matrix. Needless to say, equivariance – preserving in the output the permutation of the input columns, is possible only if jOj = d0.
An important concept relevant to MPNN as well as to other kinds of GNNs is consistency with graph colouring. An MPNN is consistent with the colouring c of a graph G if it fulfils yu(0) = yv(0) , c(u) = c(v): (11)
Because (yv(`))v2V is for each ` = 1; : : : ; L a mapping into the Euclidean space Rd` #V , or equivalently, into the Euclidean space Rd`#V , it can be used for graph representation. Usually, however, only (yv(L))v2V is used to this end. In our experiments reported in Section 3, both possibilities were used.
Network 1-GNN was proposed in [
(`) = s (W1(`)yv(`) + b(`) + fag (yu(1`); : : : ; yu(#`N)(v) ));
(`) fa(g`)(yu(1`); : : : ; yu(#`N)(v) ) = #N(v) å W2(`)yu(`j); (12) j=1 where W1(`);W2(`) 2 Rd`+1 Rd` ; b(`) 2 Rd`+1 , and s is a component-wise non-linear activation function, e.g. a sigmoid or ReLU.
From the point of view of a relationship between this
kind of networks and the WL test, it is important that
for a 1-GNN consistent with the graph colouring, and for
the colouring ci constructed in the i-th iteration of
Algorithm 1, i min(h; L), it was proven in [
(`) = f m(`l)p((1 + e`))yv(`) + fag (yu(1`); : : : ; yu(#`N)(v) ));
(`) fa(g`)(yu(1`); : : : ; yu(#`N)(v) ) = #N(v) å yu(`j); (13) j=1 where e` > 0 and f m(`l)p : Rd` ! Rd`+1 is an MLP producing the representation of the graph in the (` + 1)st layer.
A relationship between GIN and the WL test is based
on applying the universal approximation resultsfor MLPs
[
[8x 2 X : #f j = 1; : : : ; p : x j = xg = = #f j = 1; : : : ; p : x0j = xg] ) h(c; X ) = h(c; X 0): (15) 2.3
The relaxed WL kernel [
To overcome this drawback, the exact match is in [
r C1 [ [ Ckrr = Si; r : Si ! f1; : : : ; kr g;
r 8k = 1; : : : ; kr ; 8s 2 Ck : r(s ) = k: (17) Moreover, for each Si, not only one such partitioning r is used, but a finite set Qi = fr1i ; : : : ; r#iQi g of them. This turns (16) finally into the definition of a relaxed WL kernel:
h kR(h-)WL(G; G0) = å å å å d (r(ci(v)); r(ci(v0))): i=0 r2Qi v2V v02V 0 (18) Its name originates from the fact that kR(h-)WL is more general than k(h)
WLsubtree, to which it turns if Qi = frig with ri(s ) = fs g for i = 1; : : : ; h; s 2 Si.
The construction of the partitionings r 2 Qi; i = 1; : : : ; h;
in (18) is based on replacing each s 2 Si for i = 1; : : : ; h
with a set of isomorphic unfolding trees. An unfolding
tree T i(G; v) of depth i in a graph G rooted in a vertex
v 2 V will be defined in accordance with [
From the point of view of graph representation, it is important that (16) and (18) are actually scalar products of vectors, which suggests to use those vectors as Euclideanspace representations of the graphs G and G0 in downstream data analysis applications. In particular for the WL subtree kernel, define a vector f WL(G) 2 RnWL with h nWL = åi=0 #Si as
f WL(G) = (f0W;1L; : : : ; f0W;#LS0 ; f1W;1L; : : : ; fhW;#LSh ); where for i = 0; : : : ; h; j = 1; : : : ; #Si,
fiW;jL = #fv 2 V : ci(v) = s ijg: Then (16) can be indeed rewritten as the scalar product kW(h)Lsubtree(G; G0) = f WL(G)>f WL(G0): Similarly for the relaxed WL kernel, define a vector f R-WL(G) 2 RnR-WL with nR-WL = åi=0 å#j=Q1i kri as h j f R-WL(G) = (f0R;1-WL; : : : ; f0R;#-WS0L; f1R;1-W;1L; : : : ; f1R;1-W;krL1 ; 1 ); (22) f1R;2-W;1L; : : : ; f1R;#-WQ1L;kr#1Q1 ; f2R;1-W;1L; : : : ; fhR;#-WQhL;k h r#Qh where for i = 0; : : : ; h; j = 1; : : : ; #Gi; k = 1; : : : ; kri , j fiR;j-;WkL = #fv 2 V : rij(ci(v)) = kg: Then (18) can be rewritten as the scalar product kR(h-)WL(G; G0) = f R-WL(G)>f R-WL(G0):
It is useful to realize that the label sets Si for i = 0; : : : ; h on which the definitions of f WL and f R-WL rely, were defined only for a pair of graphs (G; G0), as Si = ci(V [ V 0), cf. Line 15 od Algorithm 1. For dealing with a whole set G of graphs such that each G 2 G has its own sets of vertices V G and edges EG as well as its own labelling l G and colouring cG, then it is convenient to generalize their definition to (19) (20) (21) (23) (24) (25) Si = [ ciG(vG); i = 0; : : : ; h:
G2G It is this definition that we used in our experiments.
Experimental Comparison
For the experimental comparison, we implemented the
1GNN and GIN networks using layers and neural networks
learning methods available in the PyTorch Geometric
library [
To be able to asses the statistical significance of the comparison results, we performed the comparison on 20 mutually disjoint graphsets GS1–GS20, adopting the usual assumption that for the employed data, disjointness is a sufficient condition for statistical independence. Those graphsets were obtained from real-world benchmark sets of graph data. Due to our objective of investigating the suitability of the compared graph representation methods for downstream classification, we used datasets from binary graph classification tasks to this end.
We have chosen four benchmark sets of graph data,
which are available both in the PyTorch Geometric library
[
1. BZR is a set of 405 ligands for the benzodiazepine
receptor, classified with respect to their activity in
benzodiazepine binding [
The precise origin of the graphsets GS1–GS20 in those four benchmark sets is listed in Table 1. 3.2
Before starting the experiments, we need two make two decisions concerning the compared GNNs: First, what network topology to use, and how to obtain a graph representation from a trained network. Second, a decision concerning the comparison as a whole, including the relaxed WL kernel – how to evaluate the suitability of each representation for downstream classification. We now address each of those design decisions in some detail. Topology of the Compared GNNs . Due to the fact that the GNNs were trained on classification data, and also due to the default settings of the employed GenWL implementation of the relaxed WL kernel, both of them contained the following layers: (i) an input layer, which receives the colourings of vertices, i.e. the components (l1; : : : ; ldc ) of the label l , no matter whether the label has possibly still other components, i.e. whether dc = dl or dc < dl ; (ii) 5 MPNN layers of the same size, specific for 1-GNN and for GIN; (iii) an average-pooling layer averaging over vertices of the graph; (iv) a crossentropy-classification layer.
As to the MPNN layers, we investigated 2 variants of them, differing in size: (iia) The size of all 5 layers equals the average number of vertices among the graphs in the graphset. (iib) The size of all 5 layers equals the maximal number of vertices among the graphs in the graphset.
GNN values used for graph representation were obtained as the activities, i.e. the results of somatic operators, in neurons of the MPNN layers. In both compared GNNs, the activities are obtained separately for each vertex of each graph. Therefore, activities for each graph are first averaged over all of its vertices, in accordance with using an average pooling layer during their training. According to the neurons that were actually used to this end, two kinds of graph representation were considered: (i) representation restricted to activities of neurons of the last MPNN layer, which is a restriction commonly encountered in representation learning by artificial neural networks; (ii) representation with activities of neurons of all MPNN layers, which is more similar to the representation (24) based on the relaxed WL kernel.
Apart from the GNN topology, the hyperparameter values of all compared methods were set to their defaults in the employed implementation, and if no default was available, to values obtained through slight tuning.
Evaluation of graph representations with respect to their
suitability for downstream classification was by means of
accuracy on test data obtained in classification using as
input each of the representations. To this end, a linear
support vector machine (SVM) classifier was employed,
in accordance with the default setting in the GenWL
implementation of the relaxed WL kernel [
The results for both kinds of GNN-based representations for the 4 considered networks, i.e. 1-GNN and GIN with both variants (iia) and (iib) of the MPNN layers, as well as the results for the R-WL -based representation are presented in Table 2. For each of those representations, the mean and standard deviation of the accuracies on the validation folds are reported, from 10-fold cross-validation on each of the 20 graphsets.
According to Table 2, the highest accuracy has been most frequently, namely 8 times among the 20 employed graphsets, achieved with the representation by activities of the last layer of the the variant (iia) of MPNN layers of a 1-GNN, as well as with the representation by activities of all layers of the the variant (iib) of MPNN layers of a 1-GNN. However, the differences between accuracies in Table 2 are not only due to essential differences between the considered representations, but also due to random influences. To separate the former from the latter requires to assess statistical significance of those differences. 3.4
To assess the statistical significance of the obtained results,
we first tested the basic null hypotheses that the mean
classification accuracy for all 9 representations coincides.
To this end, we applied the Friedman test with 10
replicates to the results for all 200 validation folds from the
cross-validation of SVM-classification on the 20
graphsets. This basic null hypothesis was strongly rejected, with
the achieved significance p = 4 10 92. For the post-hoc
analysis, we employed the Wilcoxon signed rank test with
two-sided alternative for all 36 pairs of the investigated
representations, because of the inconsistence of the more
commonly used mean ranks post-hoc test, to which
recently Benavoli et al. pointed out [
The results of the pairwise comparisons of the 9 investigated representations and of their significance testing are presented in Table 3. A number na;b in a row of the table corresponding to a representation a and a column corresponding to a representation b states in how many among the graphsets GS1–GS20, the representation a lead to a higher mean classification accuracy than the representation b. If na;b > nb;a and the difference between the representations a and b is according to the Wilcoxon signed rank test significant at the familywise level 5%, after the Holm correction, then na;b is in bold.
The boldfaced significant differences in Table 3 reveal that representations originating from the same kind of GNNs never lead to significantly different accuracy, neither those originating from a 1-GNN, nor those originating from a GIN. On the other hand, if one of the representations originates from a 1-GNN and the other from a GIN, then the difference between the accuracies is significant, and similarly if one of them is GNN-based and the other originates from the relaxed WL kernel. Combined with the results in Table 2, this means that any of the four representations originating from the 1-GNN yields most frequently the highest accuracy, whereas the differences between those four representations are not significant. The fact that the accuracies of the four representations originating from the same kind of GNNs were neither for 1GNN nor for GIN significantly different, suggests to test the stronger hypothesis that the mean classification accuracy of all those four representations coincides. For 1GNN, the Friedman test indeed did not reject that hypothesis, with quite high achieved significance p = 0:19. For GIN, it rejected the hypothesis on the usual significance level 5%, but even on the significance level 4% it did not reject it any more (achieved significance p = 0:043). This work-in-progress paper experimentally compared 8 variants of graph representations based on two recently proposed graph neural networks inspired by the WL isomorphism test, as well as a representation based on a recent generalization of the WL subtree kernel. They were compared not with respect to their distance in the embeding space, but with respect to downstream classification by means of an SVM. The results of that comparison indicate that the highest classification accuracy is achieved with representations originating from 1-GNN networks. At the same time, the comparison revealed that any two representations originating from different kinds of GNNs always lead to significantly different accuracies, and also the accuracies of a GNN-based representation and of the representation originating from the relaxed WL kernel differ significantly. On the other hand, the four accuracies of representations originating from the same kind of GNNs are never significantly different. Moreover, the data even don’t contradict a stronger hypothesis that the mean classification accuracy of all those representations coincides.
The result that the representation based on the relaxed WL kernel was inferior to the GNN-based representations is explainable by the fact that the kernel was designed for dense and structurally more diverse graphs, whereas the reported investigation was performed on simple molecular graphs.
However, the paper presents really only first results that, in our opinion, indicate usefulness of a possible further research in this direction, which we consider interesting due to the crucial role nowadays played by representation learning. Needless to say, such a research would have to be more comprehensive with respect to the employed graph data, as well as with respect to the involved representation methods.
As to the employed data, we used 20 comparatively small disjoint graphsets from only four different benchmark datasets, to be able to assess the statistical significance of the differences between the compared representations. To use instead a similar number of separate benchmarks, would lead to much larger graphsets and would allow to cover a broader spectrum of applications, and to drop the assumption that for the employed data, disjointness is a sufficient condition for statistical independence. The benchmarks for future investigation should include also dense and structurally diverse graphs, i.e. the kind of graphs for which the relaxed WL kernel is intended. In addition, it would be interesting to know how the GNNbased representations change if instead of the colouring components (l1; : : : ; ldc ) of a labelling l , the complete labeling is used.
As to the involved representation methods, it would be
interesting to compare the relaxed WL kernel with
methods based on other GNNs inspired by the WL test. Indeed,
other variants of the WL subtree kernel have been
sufficiently compared with the relaxed WL kernel in [
The authors are deeply indebted to Till Hendrik Schulz for repeated discussions and for his help with the relaxed WL kernel and with its implementation GenWL. The research reported in this paper has been supported by the Charles University SVV project 260575 and partially supported by the Czech Science Foundation (GACˇ R) grant 18-18080S.