# What Do GNNs Actually Learn? Towards Understanding their Representations

Giannis Nikolentzos  LIX, École Polytechnique, France  Michail Chatzianastasis
LIX, École Polytechnique, France  Michalis Vazirgiannis  LIX, École
Polytechnique, France  Department of Computer Science, KTH Royal Institute of
Technology, Sweden

###### Abstract

In recent years, graph neural networks (GNNs) have achieved great success in
the field of graph representation learning. Although prior work has shed light
into the expressiveness of those models (i. e., whether they can distinguish
pairs of non-isomorphic graphs), it is still not clear what structural
information is encoded into the node representations that are learned by those
models. In this paper, we investigate which properties of graphs are captured
purely by these models, when no node attributes are available. Specifically,
we study four popular GNN models, and we show that two of them embed all nodes
into the same feature vector, while the other two models generate
representations that are related to the number of walks over the input graph.
Strikingly, structurally dissimilar nodes can have similar representations at
some layer $k>1$, if they have the same number of walks of length $k$. We
empirically verify our theoretical findings on real datasets.

##  1 Introduction

Graphs arise naturally in a wide variety of domains such as in bio- and chemo-
informatics [48], in social network analysis [20] and in information sciences
[25]. There is thus a need for machine learning algorithms that can operate on
graph-structured data, i. e., algorithms that can exploit both the information
encoded in the graph structure but also the information contained in the node
and edge features. Recently, graph neural networks (GNNs) emerged as a very
promising method for learning on graphs, and have driven the rapid progress in
the field of graph representation learning [52].

Even though different types of GNNs were proposed in the past years, message
passing models undoubtedly seem like a natural approach to the problem. These
models, known as message passing neural networks (MPNNs) [24] employ a message
passing (or neighborhood aggregation) procedure where each node aggregates the
representations of its neighbors along with its own representation to produce
new updated representations. For graph-related tasks, MPNNs usually apply some
permutation invariant readout function to the node representations to produce
a representation for the entire graph. The family of MPNNs has been studied a
lot in the past few years, and there are now available dozens of instances of
this family of models. A lot of work has focused on investigating the
expressive power of those models. It was recently shown that standard MPNNs
are at most as powerful as the Weisfeiler-Leman algorithm in terms of
distinguishing non-isomorphic graphs [53, 35].

The recent success of GNNs put graph kernels, another approach for graph–based
machine learning, into the shade. Unlike GNNs, graph kernels generate
representations (implicit or explicit) that consist of substructures of
graphs. Such substructures include random walks [27, 23], shortest paths [9]
and subgraphs [46, 30]. Therefore, the properties and the graph
representations produced by graph kernels are fully-understood. This is not
however the case for MPNNs since, despite the great activity in the field,
still little is known about the properties of graphs that are captured in the
representations learned by those models.

In this paper, we fill this gap by studying the node representations learned
by MPNNs, when all nodes are initialized with the same features. We focus on
standard models and show that GAT [49] and DGCNN [56] embed all nodes into the
same vector, thus they capture no structural properties of the neighborhoods
of nodes. Furthermore, we show that the representations that emerge at the
$k$-th layer of GCN [29] and GIN [53] are related to some notion of walks of
length $k$ over the input graph. We bound the Lipschitz constant of those
models with respect to the sum of (normalized) walks. This suggests that MPNNs
suffer from the following limitation: structurally dissimilar nodes can have
similar representations at some layer $k$ where $k>1$. We verify our
theoretical analysis in experiments conducted on real-world datasets. Our main
contributions are summarized as follows:

  * •

We show that some MPNNs capture no structural properties of graphs, while
other MPNNs learn node representations that are related to some notion of
walks over the input graph.

  * •

We empirically verify our theoretical findings with experiments on real-world
datasets.

  * •

We empirically show that structurally dissimilar nodes can have similar
representations at the $k$-th layer of a GNN if the have a similar sum of
(normalized) walks of length $k$ emanating from them.

##  2 Related Work

While GNNs have been around for decades [47, 44, 33], it is only in recent
years that the scientific community became aware of their power and potential.
The increased scientific activity in the field led to the development of a
large number of models [11, 31, 18, 3, 17]. Those models were categorized into
spectral and spatial approaches depending on which domain the convolutions
(neighborhood aggregations) were performed. Later, it was shown that all these
models follow the same design principle and can be seen as instances of a
single common framework [24]. These models, known as message passing neural
networks (MPNNs), use a message passing scheme where nodes iteratively
aggregate feature information from their neighbors. Then, to compute a
representation for the entire graph, MPNNs typically employ some permutation
invariant readout function which aggregates the representations of all the
nodes of the graph. The family of MPNNs has been studied a lot in the past few
years and 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 or permutation sensitive aggregation functions
[36, 45, 14, 12], schemes that incorporate different local structures or high-
order neighborhoods [26, 2], non-Euclidean geometry approaches [13], while
others have focused on efficiency [21]. Fewer works have focused on the
pooling phase and have proposed more advanced strategies for learning
hierarchical graph representations [54, 22]. Note also that not all GNNs
belong to the family of MPNNs [37, 41, 40]

A considerable amount of recent work has focused on characterizing the
expressive power of GNNs. Most of these studies compare GNNs against the WL
algorithm and its variants [28] to investigate what classes of non-isomorphic
graphs they can distinguish. For instance, it has been shown that standard
GNNs are not more powerful than the $1$-WL algorithm [53, 35]. Other studies
capitalized on high-order variants of the WL algorithm to derive new models
that are more powerful than standard MPNNs [35, 34]. Recent research has
investigated the expressive power of $k$-order GNNs in terms of their ability
to distinguish non-isomorphic graphs. In particular, it has been shown that
$k$-order GNNs are at least as powerful as the $k$-WL test in this regard
[32]. Recently, various approaches have been proposed to enhance the
expressive power of GNNs beyond that of the WL test. These include encoding
vertex identifiers [51], incorporating all possible node permutations [36,
16], using random features [43, 1], utilizing node features [55],
incorporating spectral information [4], utilizing simplicial and cellular
complexes [8, 7] and directional information [5]. It has also been shown that
extracting and processing subgraphs can further enhance the expressive power
of GNNs [39, 57, 6] . For instance, it has been suggested that expressive
power of GNNs can be increased by aggregating the representations of subgraphs
produced by standard GNNs, which arise from removing one or more vertices from
a given graph [15, 42]. The above studies mainly focus on whether GNNs can
distinguish pairs of non-isomorphic graph. However, it still remains unclear
what kind of structural information is encoded into the node representations
learned by GNNs. Some recent works have proposed models that aim to learn
representations that preserve some notion of distance of nodes [38], however,
they do not shed light into the representations generated by standard models.

##  3 Preliminaries

###  3.1 Notation

Let $\mathbb{N}$ denote the set of natural numbers, i. e., $\\{1,2,\ldots\\}$.
Then, $[n]=\\{1,\ldots,n\\}\subset\mathbb{N}$ for $n\geq 1$. Let also
$\\{\\!\\!\\{\\}\\!\\!\\}$ denote a multiset, i. e., a generalized concept of
a set that allows multiple instances for its elements. Let $G=(V,E)$ be an
undirected graph, where $V$ is the vertex set and $E$ is the edge set. We will
denote by $n$ the number of vertices and by $m$ the number of edges, i. e.,
$n=|V|$ and $m=|E|$. The adjacency matrix $\mathbf{A}\in\mathbb{R}^{n\times
n}$ is a symmetric matrix used to encode edge information in a graph. The
elements of the $i^{\text{th}}$ row and $j^{\text{th}}$ column is equal to $1$
if there is an edge between $v_{i}$ and $v_{j}$, and $0$ otherwise. Let
$\mathcal{N}(v)$ denote the the neighbourhood of vertex $v$, i. e., the set
$\\{u\mid\\{v,u\\}\in E\\}$. The degree of a vertex $v$ is
$d(v)=|\mathcal{N}(v)|$. We denote by $w_{v}^{(k)}$ the number of walks of
length $k$ starting from node $v$. Finally, let $\tilde{w}_{v}^{(k)}$ denote
the sum of normalized walks of length $k$ where each walk
$(v_{1},v_{2},\ldots,v_{k})$ is normalized as follows
$\nicefrac{{1}}{{\big{(}(1+d(v_{2}))\ldots(1+d(v_{k-1}))\sqrt{(1+d(v_{1}))(1+d(v_{k}))}\big{)}}}$.

###  3.2 Message Passing Neural Networks

As already discussed, most GNNs can be unified under the framework MPNN
framework [24]. These models follow a neighborhood aggregation scheme, where
each node representation is updated based on the aggregation of its neighbors
representations. Let $\mathbf{h}_{v}^{(0)}$ denote node $v$’s initial feature
vector. Then, for a number $K$ of iterations, MPNNs update node
representations as follows:

$\begin{split}\mathbf{m}_{v}^{(k)}&=\text{AGGREGATE}^{(k)}\Big{(}\\{\\!\\!\\{\mathbf{h}_{u}^{(k-1)}|u\in\mathcal{N}(v)\\}\\!\\!\\}\Big{)}\\\
\mathbf{h}_{v}^{(k)}&=\text{COMBINE}^{(k)}\Big{(}\mathbf{h}_{v}^{(k-1)},\mathbf{m}_{v}^{(k)}\Big{)}\end{split}$

where $\text{AGGREGATE}^{(k)}$ is a permutation invariant function. By
defining different $\text{AGGREGATE}^{(k)}$ and $\text{COMBINE}^{(k)}$
functions, we obtain different MPNN instances. In this study, we consider the
neighborhood aggregation schemes of four models, namely ($1$) Graph
Convolution Network (GCN) [29]; ($2$) Deep Graph Convolutional Neural Network
(DGCNN) [56]; ($3$) Graph Attention Network (GAT) [50]; and ($4$) Graph
Isomorphism Network (GIN) [53]. The aggregation schemes of the four models are
illustrated in Table 1.

Table 1: Neighborhood aggregation schemes of the four considered models. Model | Update Equation
---|---
GCN | $\mathbf{h}_{v}^{(k)}=\text{ReLU}\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}}{\sqrt{(1+d(v))(1+d(u))}}\Bigg{)}$
DGCNN | $\mathbf{h}_{v}^{(k)}=f\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{1}{d(v)+1}\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}$
GAT | $\mathbf{h}_{v}^{(k)}=\sigma\Bigg{(}\sum_{u\in\mathcal{N}(v)}\alpha_{vu}\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}$
GIN-$\epsilon$ | $\mathbf{h}_{v}^{(k)}=\text{MLP}^{(k)}\Bigg{(}\Big{(}1+\epsilon^{(k)}\Big{)}\mathbf{h}_{v}^{(k-1)}+\sum_{u\in\mathcal{N}(v)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}$

For node-level tasks, final nodes representation $\mathbf{h}_{v}^{(K)}$ can be
directly passed to a fully-connected layer for prediction. For graph-level
tasks, a graph representation is obtained by aggregating its nodes final
representations:

$\mathbf{h}_{G}=\text{READOUT}\Big{(}\\{\\!\\!\\{\mathbf{h}_{v}^{(K)}|v\in
G\\}\\!\\!\\}\Big{)}$

The READOUT function is typically a differentiable permutation invariant
function such as the sum or mean operator.

##  4 What Do MPNNs Actually Learn?

We next investigate what structural properties of nodes these four considered
models can capture. Nodes are usually annotated with features that reveal
information about their neighborhoods. Such features include their degree or
even more sophisticated features such as counts of certain substructures [10]
or those extracted from Laplacian eigenvectors [19]. We are interested in
identifying properties that are captured purely by these models. Thus, we
assume that no such features are available, and we annotate all nodes with the
same feature vector or scalar.

######  Theorem 4.1.

Let $\mathcal{G}=\\{G_{1},\ldots,G_{N}\\}$ be a collection of graphs. Let also
$\mathcal{V}=V_{1}\cup\ldots\cup V_{N}$ denote the set that contains the nodes
of all graphs. All nodes are initially annotated with the same representation.
Without loss of generality, we assume that they are annotated with a single
feature equal to $1$, i. e., $\mathbf{h}_{v}^{(0)}=1$ $\forall
v\in\mathcal{V}$. Then, after $k$ neighborhood aggregation layers:

  1. 1.

DGCNN and GAT both map all nodes to the same representation, i. e.,
$\mathbf{h}_{v}^{(k)}=\mathbf{h}_{u}^{(k)}$ $\forall v,u\in\mathcal{V}$.

  2. 2.

GCN maps nodes to representations related to the sum of normalized walks of
length $k$ starting from them:

$\Big{|}\Big{|}\mathbf{h}_{v}^{(k)}-\mathbf{h}_{u}^{(k)}\Big{|}\Big{|}_{2}\leq\prod_{i=1}^{k}L_{f}^{(i)}\Big{|}\Big{|}\tilde{w}_{v}^{(k)}-\tilde{w}_{u}^{(k)}\Big{|}\Big{|}_{2}$

where $L_{f}^{(i)}$ denotes the Lipschitz constant of the fully-connected
layer of the $i$-th neighborhood aggregation layer.

  3. 3.

Under mild assumptions (biases of MLPs are ignored), GIN-$0$ maps nodes to
representations that capture the number of walks of length $k$ starting from
them:

$\Big{|}\Big{|}\mathbf{h}_{v}^{(k)}-\mathbf{h}_{u}^{(k)}\Big{|}\Big{|}_{2}\leq\prod_{i=1}^{k}L_{f}^{(i)}\Big{|}\Big{|}w_{v}^{(k)}-w_{u}^{(k)}\Big{|}\Big{|}_{2}$

where $L_{f}^{(i)}$ denotes the Lipschitz constant of the MLP of the $i$-th
neighborhood aggregation layer.

Figure 1: Euclidean distances of the representations generated at the third
layer of the different models vs. Euclidean distances of the number of walks
(or sum of normalized walks) of length $3$ starting from the different nodes.

Figure 2: The number of walks of length $2$ starting from the red nodes of the
three graphs is equal to $10$. These three nodes could be embedded closely to
each other even though they are structurally dissimilar.

The above result highlights the limitations of the considered models.
Specifically, our results imply that the DGCNN and GAT models encode no
structural information of the graph into the learned node representations.
Furthermore, combined with a sum readout function, these representations give
rise to a graph representation that can only count the number of nodes of the
graph. If the readout function is the mean operator, then all graphs are
embedded into the same vector. With regards to the other two models, we have
bounded the Lipschitz constant of GIN-$0$ and GCN with respect to the number
of walks and sum of normalized walks starting from the different nodes,
respectively.

To experimentally verify the above theoretical results, we trained the GIN-$0$
and GCN models on the IMDB-BINARY and the ENZYMES graph classification
datasets. For all pairs of nodes, we computed the Euclidean distance of the
number of walks (resp. sum of normalized walks) of length $3$ starting from
them. We also computed the Euclidean distance of the representations of the
nodes that emerge at the corresponding (i. e., third) layer of GIN-$0$ (resp.
GCN). We finally computed the correlation of the two collections of Euclidean
distances and the results are given in Figure 1. Clearly, the results verify
our theoretical results. The distance of the number of walks is perfectly
correlated with the distance of the representations generated by GIN-$0$ with
no biases, while the distance of the sum of normalized walks is perfectly
correlated with the distance of the representations produced by GCN. We also
computed the Euclidean distance of the representations of the nodes that
emerge at the third layer of the standard GIN-$0$ model (with biases), and we
compared them against the distances of the number of walks. We can see that on
both datasets, the emerging correlations are very high (equal to $0.99$). We
observed similar values of correlation on other datasets as well, which
indicates that the magnitude of the bias terms of the MLPs might be very small
and that our assumption of ignoring biases is by no means unrealistic.

Based on the above theoretical and empirical findings, it is clear that two
nodes can have dissimilar representations at the $k$-th layer, but obtain
similar representations at the $(k+1)$-th layer of some MPNN model. For
instance, for GIN-$0$, this can be the case if the two nodes have different
numbers of walks of length $k$, but similar numbers of walks of length $k+1$.
We give in Figure 2 an example of three nodes (the three red nodes) that have
structurally dissimilar neighborhoods, but their representations produced by
GIN-$0$ after two neighborhood aggregation layers are very similar to each
other (or identical in the case where biases are omitted). In all three cases,
the number of walks of length $2$ starting from the red nodes is equal to
$10$. It is also clear that the three nodes have different values of degree
from each other.

##  5 Conclusion

In this paper, we focused on four well-established GNN models and we
investigated what properties of graphs these models can capture. We found that
two of them capture no structural properties of graphs since they embed all
nodes into the same feature vector. The rest of the models learn node
representations that capture the number of (normalized) walks emanating from
the different nodes. We showed that the GIN-$0$ model can embed two
structurally dissimilar nodes to similar vectors if the numbers of walks of
length $k$ (for $k>1$) starting from the two nodes are similar to each other.
In the future, we plan to explore what is the impact of node features on the
learned representations and how the different neighborhood aggregation schemes
handle those features.

## References

  * [1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz.  The surprising power of graph neural networks with random node initialization.  arXiv preprint arXiv:2010.01179, 2020.
  * [2] Sami Abu-El-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, pages 21–29, 2019.
  * [3] James Atwood and Don Towsley.  Diffusion-Convolutional Neural Networks .  In Advances in Neural Information Processing Systems, volume 29, pages 1993–2001, 2016.
  * [4] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine.  Breaking the limits of message passing graph neural networks.  In International Conference on Machine Learning, pages 599–608. PMLR, 2021.
  * [5] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò.  Directional graph networks.  In International Conference on Machine Learning, pages 748–758. PMLR, 2021.
  * [6] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron.  Equivariant subgraph aggregation networks.  arXiv preprint arXiv:2110.02910, 2021.
  * [7] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein.  Weisfeiler and Lehman Go Cellular: CW Networks.  In Advances in Neural Information Processing Systems, pages 2625–2640, 2021.
  * [8] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein.  Weisfeiler and lehman go topological: Message passing simplicial networks.  In International Conference on Machine Learning, pages 1026–1037. PMLR, 2021.
  * [9] Karsten M Borgwardt and Hans-Peter Kriegel.  Shortest-path kernels on graphs.  In Proceedings of the 5th IEEE International Conference on Data Mining, pages 74–81, 2005.
  * [10] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein.  Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2022.
  * [11] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun.  Spectral Networks and Locally connected networks on Graphs.  In 2nd International Conference on Learning Representations, 2014\.
  * [12] David Buterez, Jon Paul Janet, Steven J Kiddle, Dino Oglic, and Pietro Liò.  Graph neural networks with adaptive readouts.  arXiv preprint arXiv:2211.04952, 2022.
  * [13] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec.  Hyperbolic Graph Convolutional Neural Networks.  In Advances in Neural Information Processing Systems, volume 33, pages 4868–4879, 2019.
  * [14] Michail Chatzianastasis, Johannes F Lutzeyer, George Dasoulas, and Michalis Vazirgiannis.  Graph ordering attention networks.  arXiv preprint arXiv:2204.05351, 2022.
  * [15] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro.  Reconstruction for powerful graph representations.  Advances in Neural Information Processing Systems, 34:1713–1726, 2021.
  * [16] 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, pages 2126–2132, 2020.
  * [17] 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, pages 3844–3852, 2016.
  * [18] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams.  Convolutional Networks on Graphs for Learning Molecular Fingerprints.  In Advances in Neural Information Processing Systems, volume 28, 2015.
  * [19] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Benchmarking Graph Neural Networks.  arXiv preprint arXiv:2003.00982, 2020.
  * [20] David Easley and Jon Kleinberg.  Networks, crowds, and markets: Reasoning about a highly connected world.  Cambridge University Press, 2010.
  * [21] Claudio Gallicchio and Alessio Micheli.  Fast and Deep Graph Neural Networks.  In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 3898–3905, 2020.
  * [22] Hongyang Gao and Shuiwang Ji.  Graph U-Nets.  In Proceedings of the 36th International Conference on Machine Learning, pages 2083–2092, 2019.
  * [23] Thomas Gärtner, Peter Flach, and Stefan Wrobel.  On Graph Kernels: Hardness Results and Efficient Alternatives.  In Learning Theory and Kernel Machines, pages 129–143. Springer, 2003.
  * [24] 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, pages 1263–1272, 2017.
  * [25] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard de Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel-Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann.  Knowledge Graphs.  ACM Computing Surveys, 54(4):1–37, 2021.
  * [26] Yilun Jin, Guojie Song, and Chuan Shi.  GraLSP: Graph Neural Networks with Local Structural Patterns.  In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 4361–4368, 2020.
  * [27] Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi.  Marginalized Kernels Between Labeled Graphs.  In Proceedings of the 20th International Conference on Machine Learning, pages 321–328, 2003.
  * [28] Sandra Kiefer.  The Weisfeiler-Leman Algorithm: An Exploration of its Powe.  ACM SIGLOG News, 7(3):5–27, 2020.
  * [29] Thomas N Kipf and Max Welling.  Semi-Supervised Classification with Graph Convolutional Networks.  In 5th International Conference on Learning Representations, 2017\.
  * [30] Nils Kriege and Petra Mutzel.  Subgraph Matching Kernels for Attributed Graphs.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 291–298, 2012.
  * [31] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated graph sequence neural networks.  arXiv preprint arXiv:1511.05493, 2015.
  * [32] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and Equivariant Graph Networks.  In 7th International Conference on Learning Representations, 2019\.
  * [33] Alessio Micheli.  Neural Network for Graphs: A Contextual Constructive Approachs.  IEEE Transactions on Neural Networks, 20(3):498–511, 2009.
  * [34] Christopher Morris, Gaurav Rattan, and Petra Mutzel.  Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings.  In Advances in Neural Information Processing Systems, volume 34, 2020.
  * [35] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks.  In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 4602–4609, 2019.
  * [36] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro.  Relational Pooling for Graph Representations.  In Proceedings of the 36th International Conference on Machine Learning, pages 4663–4673, 2019.
  * [37] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov.  Learning Convolutional Neural Networks for Graphs.  In Proceedings of the 33rd International Conference on Machine Learning, pages 2014–2023, 2016.
  * [38] Giannis Nikolentzos, Michail Chatzianastasis, and Michalis Vazirgiannis.  Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations.  In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pages 1037–1054, 2023.
  * [39] Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis.  k-hop graph neural networks.  Neural Networks, 130:195–205, 2020.
  * [40] Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis.  Permute Me Softly: Learning Soft Permutations for Graph Representations.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):5087–5098, 2023.
  * [41] Giannis Nikolentzos and Michalis Vazirgiannis.  Random Walk Graph Neural Networks.  In Advances in Neural Information Processing Systems, pages 16211–16222, 2020.
  * [42] Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer.  Dropgnn: random dropouts increase the expressiveness of graph neural networks.  Advances in Neural Information Processing Systems, 34:21997–22009, 2021.
  * [43] Ryoma Sato, Makoto Yamada, and Hisashi Kashima.  Random Features Strengthen Graph Neural Networks.  In Proceedings of the 2021 SIAM International Conference on Data Mining, pages 333–341, 2021.
  * [44] 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–80, 2009.
  * [45] Younjoo Seo, Andreas Loukas, and Nathanaël Perraudin.  Discriminative structural graph classification.  arXiv preprint arXiv:1905.13422, 2019.
  * [46] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt.  Efficient graphlet kernels for large graph comparison.  In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics, pages 488–495, 2009.
  * [47] Alessandro Sperduti and Antonina Starita.  Supervised Neural Networks for the Classification of Structures.  IEEE Transactions on Neural Networks, 8(3):714–735, 1997.
  * [48] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al.  A deep learning approach to antibiotic discovery.  Cell, 180(4):688–702, 2020.
  * [49] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph Attention Networks.  In 6th International Conference on Learning Representations, 2018\.
  * [50] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In ICLR, 2018.
  * [51] Clement Vignac, Andreas Loukas, and Pascal Frossard.  Building powerful and equivariant graph neural networks with structural message-passing.  Advances in Neural Information Processing Systems, 33:14143–14155, 2020.
  * [52] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A Comprehensive Survey on Graph Neural Networks.  IEEE Transactions on Neural Networks and Learning Systems, 32(1):4–24, 2020.
  * [53] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How Powerful are Graph Neural Networks?  In 7th International Conference on Learning Representations, 2019\.
  * [54] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec.  Hierarchical Graph Representation Learning with Differentiable Pooling.  In Advances in Neural Information Processing Systems, volume 32, pages 4800–4810, 2018.
  * [55] Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec.  Identity-aware graph neural networks.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 10737–10745, 2021.
  * [56] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen.  An End-to-End Deep Learning Architecture for Graph Classification.  In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 4438–4445, 2018.
  * [57] Muhan Zhang and Pan Li.  Nested Graph Neural Networks.  In Advances in Neural Information Processing Systems, pages 15734–15747, 2021.

##  Appendix A Proof of Theorem 4.1

We assume that all the nodes of the graph are initially annotated with a
single feature equal to $1$.

###  A.1 DGCNN

The DGCNN model that updates node representations as follows [56]:

$\begin{split}\mathbf{h}_{v}^{(k)}=f\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{1}{\text{deg}(v)+1}\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}\end{split}$

Once again, we assume that all the nodes of the graph are initially annotated
with a single feature equal to $1$. We will show by induction that the model
maps all nodes to the same vector representation. We first assume that
$\mathbf{h}_{v}^{k-1}=\mathbf{h}_{u}^{k-1}=\mathbf{h}^{k-1}$ for all $v,u\in
V$. This is actually true for $k=1$ since $\mathbf{h}_{v}^{0}=1$ for all $v\in
V$. Then, we have that
$\mathbf{W}^{(k)}\mathbf{h}_{v}^{(k-1)}=\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}=\mathbf{W}^{(k)}\mathbf{h}^{(k-1)}$
for all $v,u\in V$. We also have that:

$\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{1}{\text{deg}(v)+1}=1$

Thus, we finally have that:

$\begin{split}\mathbf{h}_{v}^{(k)}=f\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{1}{\text{deg}(v)+1}\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}=f\Bigg{(}\mathbf{W}^{(k)}\mathbf{h}^{(k-1)}\Bigg{)}\end{split}$

for all $v\in V$. We have shown that this variant of the GCN model produces
the same representation for all nodes of all graphs and thus, it cannot
capture any structural information about the neighborhood of each node.

###  A.2 GAT

The GAT model updates node representations as follows:

$\begin{split}\mathbf{h}_{v}^{(k)}=\sigma\Bigg{(}\sum_{u\in\mathcal{N}(v)}\alpha_{vu}\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}\end{split}$

where $\alpha_{vu}$ is an attention coefficient that indicates the importance
of node $u$’s features to node $v$. Once again, we assume that all the nodes
of the graph are initially annotated with a single feature equal to $1$. We
will show by induction that the model maps all nodes to the same vector
representation. We first assume that
$\mathbf{h}_{v}^{k-1}=\mathbf{h}_{u}^{k-1}=\mathbf{h}^{k-1}$ for all $v,u\in
V$. This is actually true for $k=1$ since $\mathbf{h}_{v}^{0}=1$ for all $v\in
V$. Then, we have that
$\mathbf{W}^{(k)}\mathbf{h}_{v}^{(k-1)}=\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}=\mathbf{W}^{(k)}\mathbf{h}^{(k-1)}$
for all $v,u\in V$. Since the attention coefficients are normalized, we have:

$\sum_{u\in\mathcal{N}(v)}\alpha_{vu}=1$

Thus, we finally have that:

$\begin{split}\mathbf{h}_{v}^{(k)}=\sigma\Bigg{(}\sum_{u\in\mathcal{N}(v)}\alpha_{vu}\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}=\sigma\Bigg{(}\mathbf{W}^{(k)}\mathbf{h}^{(k-1)}\Bigg{)}\end{split}$

for all $v\in V$. We have shown that the GAT model produces the same
representation for all nodes of all graphs and thus, it cannot capture any
structural information about the neighborhood of each node.

###  A.3 GCN

The GCN model updates node representations as follows:

$\mathbf{h}_{v}^{(k)}=\text{ReLU}\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}}{\sqrt{(1+\text{deg}(v))(1+\text{deg}(u))}}\Bigg{)}$

Note that the GCN model (as decribed in the original paper [29]) does not
perform an affine transformation of the node features, but instead a linear
transformation. In other words, no biases are present. Thus, the following
holds:

$\mathbf{h}_{v}^{(k)}=\text{ReLU}\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{\mathbf{W}^{(k)}\mathbf{h}_{u}^{(k-1)}}{\sqrt{(1+\text{deg}(v))(1+\text{deg}(u))}}\Bigg{)}=\text{ReLU}\Bigg{(}\mathbf{W}^{(k)}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{\mathbf{h}_{u}^{(k-1)}}{\sqrt{(1+\text{deg}(v))(1+\text{deg}(u))}}\Bigg{)}$
(1)

Let $L_{f}^{(k)}$ denote the Lipschitz constant associated with the fully
connected layer of the $k$-th neighborhood aggregation layer of GCN. In what
follows, we also denote $\mathcal{N}(v)\cup\\{v\\}$ as $\mathcal{N}^{+}(v)$.
Then, we have:

$\displaystyle||\mathbf{h}_{v}^{(1)}-\mathbf{h}_{u}^{(1)}||_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\text{ReLU}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\frac{\mathbf{W}^{(1)}\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(v))(1+d(w))}}\Bigg{)}-\text{ReLU}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\frac{\mathbf{W}^{(1)}\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(u))(1+d(w))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\text{ReLU}\Bigg{(}\mathbf{W}^{(1)}\sum_{w\in\mathcal{N}^{+}(v)}\frac{\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(v))(1+d(w))}}\Bigg{)}-\text{ReLU}\Bigg{(}\mathbf{W}^{(1)}\sum_{w\in\mathcal{N}^{+}(u)}\frac{\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(u))(1+d(w))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\quad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{\sqrt{(1+d(u))(1+d(w))}}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle||\mathbf{h}_{v}^{(2)}-\mathbf{h}_{u}^{(2)}||_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\text{ReLU}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\frac{\mathbf{W}^{(2)}\mathbf{h}_{w}^{(1)}}{\sqrt{(1+d(v))(1+d(w))}}\Bigg{)}-\text{ReLU}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\frac{\mathbf{W}^{(2)}\mathbf{h}_{w}^{(1)}}{\sqrt{(1+d(u))(1+d(w))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\text{ReLU}\Bigg{(}\mathbf{W}^{(2)}\sum_{w\in\mathcal{N}^{+}(v)}\frac{\mathbf{h}_{w}^{(1)}}{\sqrt{(1+d(v))(1+d(w))}}\Bigg{)}-\text{ReLU}\Bigg{(}\mathbf{W}^{(2)}\sum_{w\in\mathcal{N}^{+}(u)}\frac{\mathbf{h}_{w}^{(1)}}{\sqrt{(1+d(u))(1+d(w))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(2)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\text{ReLU}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{W}^{(1)}\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\text{ReLU}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{W}^{(1)}\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(2)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\text{ReLU}\Bigg{(}\mathbf{W}^{(1)}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\text{ReLU}\Bigg{(}\mathbf{W}^{(1)}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{h}_{w}^{(0)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(2)}L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(2)}L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{(1+d(w))\sqrt{(1+d(v))(1+d(x))}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{(1+d(w))\sqrt{(1+d(u))(1+d(x))}}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\quad\vdots$
$\displaystyle||\mathbf{h}_{v}^{(K)}-\mathbf{h}_{u}^{(K)}||_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\text{ReLU}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\frac{\mathbf{W}^{(K)}\mathbf{h}_{w}^{(K-1)}}{\sqrt{(1+d(v))(1+d(w))}}\Bigg{)}-\text{ReLU}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\frac{\mathbf{W}^{(K)}\mathbf{h}_{w}^{(K-1)}}{\sqrt{(1+d(u))(1+d(w))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\text{ReLU}\Bigg{(}\mathbf{W}^{(K)}\sum_{w\in\mathcal{N}^{+}(v)}\frac{\mathbf{h}_{w}^{(K-1)}}{\sqrt{(1+d(v))(1+d(w))}}\Bigg{)}-\text{ReLU}\Bigg{(}\mathbf{W}^{(K)}\sum_{w\in\mathcal{N}^{+}(u)}\frac{\mathbf{h}_{w}^{(K-1)}}{\sqrt{(1+d(u))(1+d(w))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(K)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\text{ReLU}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{W}^{(K-1)}\mathbf{h}_{w}^{(K-2)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\text{ReLU}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{W}^{(K-1)}\mathbf{h}_{w}^{(K-2)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(K)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\text{ReLU}\Bigg{(}\mathbf{W}^{(K-1)}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{h}_{w}^{(K-2)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\text{ReLU}\Bigg{(}\mathbf{W}^{(K-1)}\sum_{x\in\mathcal{N}^{+}(w)}\frac{\mathbf{h}_{w}^{(K-2)}}{\sqrt{(1+d(w))(1+d(x))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(2)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}\quad\ldots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ldots\,\text{ReLU}\Bigg{(}\sum_{z\in\mathcal{N}^{+}(y)}\frac{\mathbf{W}^{(1)}\mathbf{h}_{z}^{(0)}}{\sqrt{(1+d(y))(1+d(z))}}\Bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}\quad\ldots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ldots\,\text{ReLU}\Bigg{(}\sum_{z\in\mathcal{N}^{+}(y)}\frac{\mathbf{W}^{(1)}\mathbf{h}_{z}^{(0)}}{\sqrt{(1+d(y))(1+d(z))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(2)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}\quad\ldots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ldots\,\text{ReLU}\Bigg{(}\mathbf{W}^{(1)}\sum_{z\in\mathcal{N}^{+}(y)}\frac{\mathbf{h}_{z}^{(0)}}{\sqrt{(1+d(y))(1+d(z))}}\Bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}\quad\ldots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ldots\,\text{ReLU}\Bigg{(}\mathbf{W}^{(1)}\sum_{z\in\mathcal{N}^{+}(y)}\frac{\mathbf{h}_{z}^{(0)}}{\sqrt{(1+d(y))(1+d(z))}}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\frac{1}{{\sqrt{(1+d(v))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}\ldots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ldots\,\sum_{z\in\mathcal{N}^{+}(y)}\frac{1}{\sqrt{(1+d(y))(1+d(z))}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\frac{1}{{\sqrt{(1+d(u))(1+d(w))}}}\sum_{x\in\mathcal{N}^{+}(w)}\frac{1}{\sqrt{(1+d(w))(1+d(x))}}\quad\ldots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ldots\,\sum_{z\in\mathcal{N}^{+}(y)}\frac{1}{\sqrt{(1+d(y))(1+d(z))}}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}\frac{1}{(1+d(w))(1+d(x))\ldots(1+d(y))}\frac{1}{\sqrt{(1+d(v))(1+d(z))}}$
$\displaystyle\qquad\qquad\qquad\qquad\quad-\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}\frac{1}{(1+d(w))(1+d(x))\ldots(1+d(y))}\frac{1}{\sqrt{(1+d(u))(1+d(z))}}\Bigg{|}\Bigg{|}_{2}$

It turns out that the node representations learned at the $k$-th layer of a
GCN model are related to the normalized number of walks of length $k$ starting
from each node. Given a walk of length $k$ consisting of the following nodes
$(v_{1},v_{2},\ldots,v_{k})$, the walk is normalized by the product of the
degrees of nodes $v_{2},\ldots,v_{k-1}$ each increased by $1$ and of the
square root of the degrees of nodes $v_{1}$ and $v_{k}$ also increased by $1$.
Thus, the contribution of each walk is inversely proportional to the degrees
of the nodes of which the walk is composed.

###  A.4 GIN-$0$

The GIN-$0$ model updates node representations as follows:

$\mathbf{h}_{v}^{(k)}=\text{MLP}^{(k)}\Bigg{(}\Big{(}1+\epsilon^{(k)}\Big{)}\mathbf{h}_{v}^{(k-1)}+\sum_{u\in\mathcal{N}(v)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}=\text{MLP}^{(k)}\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\mathbf{h}_{u}^{(k-1)}\Bigg{)}$
(2)

We make the following assumption.

######  Assumption A.1.

We assume that the biases of the fully-connected layers of all MLPs are equal
to zero vectors.

Our results are also valid when given fully-connected layers of the form
$\text{fc}(\mathbf{x})=\mathbf{W}\mathbf{x}+\mathbf{b}$, the following holds
$||\mathbf{b}||\ll||\mathbf{W}\mathbf{x}||$. This is a reasonable assumption
which is common in real-world machine learning settings. Note that the
activation function of the MLPs of the GIN-$0$ model is the ReLU function
[53]. Without loss of generality, we assume that the MLPs consist of two
fully-connected layers. Given the above, the update function of the GIN-$0$
model takes the following form:

$\text{MLP}^{(k)}(\mathbf{x})=\text{ReLU}\Bigg{(}\mathbf{W}_{2}^{(k)}\,\text{ReLU}\bigg{(}\mathbf{W}_{1}^{(k)}\mathbf{x}\bigg{)}\Bigg{)}$
(3)

We next prove the following Lemma which will be useful in our analysis.

######  Lemma A.2.

Let MLP denote the model defined in Equation (3) above. Let also
$\mathcal{X}=\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{M}\\}$ denote a set of
vectors such that given any two vectors from the set, one is a scalar multiple
of the other, i. e., if $\mathbf{x}_{i},\mathbf{x}_{j}\in\mathcal{X}$, then
$\mathbf{x}_{i}=a\mathbf{x}_{j}$ where $a>0$. Then, the following holds:

$\sum_{i=1}^{M}\text{MLP}(\mathbf{x}_{i})=\text{MLP}\bigg{(}\sum_{i=1}^{M}\mathbf{x}_{i}\bigg{)}$

###### Proof.

For $a>0$, we have that $\mathbf{W}(a\mathbf{x})=a\mathbf{W}\mathbf{x}$.
Furthermore, we also have that
$\text{ReLU}(a\mathbf{x})=a\text{ReLU}(\mathbf{x})$. Then, we have:

$\text{MLP}(a\mathbf{x})=\text{ReLU}\Bigg{(}\mathbf{W}_{2}\,\text{ReLU}\bigg{(}\mathbf{W}_{1}(a\mathbf{x})\bigg{)}\Bigg{)}=a\text{ReLU}\Bigg{(}\mathbf{W}_{2}\,\text{ReLU}\bigg{(}\mathbf{W}_{1}(\mathbf{x})\bigg{)}\Bigg{)}=a\text{MLP}(\mathbf{x})$

We have assumed that $\mathbf{x}_{2}=a_{2}\mathbf{x}_{1}$,
$\mathbf{x}_{3}=a_{3}\mathbf{x}_{1},\ldots$,
$\mathbf{x}_{M}=a_{M}\mathbf{x}_{1}$. Then, we have that:

$\begin{split}\sum_{i=1}^{M}\text{MLP}(\mathbf{x}_{i})&=\text{MLP}(\mathbf{x}_{1})+\sum_{i=2}^{M}\text{MLP}(a_{i}\mathbf{x}_{1})\\\
&=\text{MLP}(\mathbf{x}_{1})+\sum_{i=2}^{M}a_{i}\text{MLP}(\mathbf{x}_{1})\\\
&=(1+a_{2}+\ldots+a_{M})\text{MLP}(\mathbf{x}_{1})\\\
&=\text{MLP}\Big{(}(1+a_{2}+\ldots+a_{M})\mathbf{x}_{1}\Big{)}\\\
&=\text{MLP}\bigg{(}\sum_{i=1}^{M}\mathbf{x}_{i}\bigg{)}\end{split}$

∎

It is trivial to generalize the above Lemma to MLPs that contain more than two
layers. We also prove the following Lemma.

######  Lemma A.3.

Let the MLPs of the GIN-$0$ model be instances of the MLP of Equation (3)
above. Let $\mathcal{V}$ denote the set of nodes of all graphs and let
$\mathcal{X}^{(k-1)}=\\{\\!\\!\\{\mathbf{h}_{1}^{(k-1)},\ldots,\mathbf{h}_{|\mathcal{V}|}^{(k-1)}\\}\\!\\!\\}$
be the multiset of node representations that emerged at the $(k-1)$-th layer
of the model. Suppose that given any two vectors from this multiset, one is a
scalar multiple of the other, i. e., if
$\mathbf{h}_{i}^{(k-1)},\mathbf{h}_{j}^{(k-1)}\in\mathcal{X}^{(k-1)}$, then
$\mathbf{h}_{i}^{(k-1)}=a\mathbf{h}_{j}^{(k-1)}$ where $a>0$. Then, the same
holds for the node representations that emerge at the $k$-th layer of the
model, i. e., for any two vectors
$\mathbf{h}_{i}^{(k)},\mathbf{h}_{j}^{(k)}\in\mathcal{X}^{(k)}=\\{\\!\\!\\{\mathbf{h}_{1}^{(k)},\ldots,\mathbf{h}_{|\mathcal{V}|}^{(k)}\\}\\!\\!\\}$,
we have that $\mathbf{h}_{i}^{(k)}=a\mathbf{h}_{j}^{(k)}$ where $a>0$.

###### Proof.

For $a>0$, we have that $\mathbf{W}(a\mathbf{x})=a\mathbf{W}\mathbf{x}$.
Furthermore, we also have that
$\text{ReLU}(a\mathbf{x})=a\text{ReLU}(\mathbf{x})$. Then, we have:

$\text{MLP}(a\mathbf{x})=\text{ReLU}\Bigg{(}\mathbf{W}_{2}\,\text{ReLU}\bigg{(}\mathbf{W}_{1}(a\mathbf{x})\bigg{)}\Bigg{)}=a\text{ReLU}\Bigg{(}\mathbf{W}_{2}\,\text{ReLU}\bigg{(}\mathbf{W}_{1}(\mathbf{x})\bigg{)}\Bigg{)}=a\text{MLP}(\mathbf{x})$

We have assumed that given some node $w\in\mathcal{V}$, then for any node
$u\in\mathcal{V}$, we have that
$\mathbf{h}_{u}^{(k-1)}=a_{u}\mathbf{h}_{w}^{(k-1)}$. Then, given any node
$v\in\mathcal{V}$, its representation is updated as follows:

$\begin{split}\mathbf{h}_{v}^{(k)}=\text{MLP}^{(k)}\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\mathbf{h}_{u}^{(k-1)}\Bigg{)}=\text{MLP}^{(k)}\Bigg{(}\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}a_{u}\mathbf{h}_{w}^{(k-1)}\Bigg{)}&=\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}a_{u}\text{MLP}^{(k)}\Bigg{(}\mathbf{h}_{w}^{(k-1)}\Bigg{)}\\\
&=c\text{MLP}^{(k)}\Bigg{(}\mathbf{h}_{w}^{(k-1)}\Bigg{)}\end{split}$

which concludes the proof. ∎

Thus, the above Lemma suggests that for MLPs of the form of Equation (3), the
node representations produced by GIN-$0$ are either scalar multiples of each
other and they point in the same direction or are all equal to the all-zeros
vector.

Let $L_{f}^{(k)}$ denote the Lipschitz constant associated with the MLP of the
$k$-th neighborhood aggregation layer of GIN-$0$. We assume that all the nodes
of the graph are initially annotated with a single feature equal to $1$. Then,
we have:

$\displaystyle||\mathbf{h}_{v}^{(1)}-\mathbf{h}_{u}^{(1)}||_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\textsc{MLP}^{(1)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\mathbf{h}_{w}^{(0)}\Bigg{)}-\textsc{MLP}^{(1)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\mathbf{h}_{w}^{(0)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}1\quad-\sum_{w\in\mathcal{N}^{+}(u)}1\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(1)}\Big{|}\Big{|}\text{deg}(v)-\text{deg}(u)\Big{|}\Big{|}_{2}$
$\displaystyle||\mathbf{h}_{v}^{(2)}-\mathbf{h}_{u}^{(2)}||_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\textsc{MLP}^{(2)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\mathbf{h}_{w}^{(1)}\Bigg{)}-\textsc{MLP}^{(2)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\mathbf{h}_{w}^{(1)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(2)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\textsc{MLP}^{(1)}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(0)}\Bigg{)}\quad-\sum_{w\in\mathcal{N}^{+}(u)}\textsc{MLP}^{(1)}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(0)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(2)}\Bigg{|}\Bigg{|}\textsc{MLP}^{(1)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(0)}\Bigg{)}\quad-\textsc{MLP}^{(1)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(0)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}(\text{due
to Lemma~{}\ref{lemma:1}})$ $\displaystyle\leq
L_{f}^{(2)}L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(0)}\quad-\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(0)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(2)}L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}1\quad-\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}1\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\vdots$
$\displaystyle||\mathbf{h}_{v}^{(K)}-\mathbf{h}_{u}^{(K)}||_{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\textsc{MLP}^{(K)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\mathbf{h}_{w}^{(K-1)}\Bigg{)}-\textsc{MLP}^{(K)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\mathbf{h}_{w}^{(K-1)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\leq
L_{f}^{(K)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\textsc{MLP}^{(K-1)}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(K-2)}\Bigg{)}\quad-\sum_{w\in\mathcal{N}^{+}(u)}\textsc{MLP}^{(K-1)}\Bigg{(}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(K-2)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(K)}\Bigg{|}\Bigg{|}\textsc{MLP}^{(K-1)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(K-2)}\Bigg{)}-\textsc{MLP}^{(K-1)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}\mathbf{h}_{x}^{(K-2)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}(\text{due
to Lemma \ref{lemma:1}})$ $\displaystyle\leq
L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(2)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\quad\textsc{MLP}^{(1)}\Bigg{(}\sum_{z\in\mathcal{N}^{+}(y)}\mathbf{h}_{z}^{(0)}\Bigg{)}\quad$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}(u)\cup\\{u\\}}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\quad\textsc{MLP}^{(1)}\Bigg{(}\sum_{z\in\mathcal{N}^{+}(y)}\mathbf{h}_{z}^{(0)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(2)}\Bigg{|}\Bigg{|}\textsc{MLP}^{(1)}\Bigg{(}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}\mathbf{h}_{z}^{(0)}\Bigg{)}\quad$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\textsc{MLP}^{(1)}\Bigg{(}\sum_{w\in\mathcal{N}(u)\cup\\{u\\}}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}\mathbf{h}_{z}^{(0)}\Bigg{)}\Bigg{|}\Bigg{|}_{2}(\text{due
to Lemma \ref{lemma:1}})$ $\displaystyle\leq
L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}\mathbf{h}_{z}^{(0)}\quad$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}\mathbf{h}_{z}^{(0)}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle=L_{f}^{(K)}L_{f}^{(K-1)}\ldots\,L_{f}^{(1)}\Bigg{|}\Bigg{|}\sum_{w\in\mathcal{N}^{+}(v)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}1\quad-\sum_{w\in\mathcal{N}^{+}(u)}\sum_{x\in\mathcal{N}^{+}(w)}\ldots\sum_{z\in\mathcal{N}^{+}(y)}1\Bigg{|}\Bigg{|}_{2}$

It turns out that for $k=1$, $\text{deg}(v)$ and $\text{deg}(u)$ are equal to
the number of walks of length $1$ starting from nodes $v$ and $u$,
respectively. Likewise, for $k=2$,
$\sum_{w\in\mathcal{N}(v)\cup\\{v\\}}\sum_{x\in\mathcal{N}(w)\cup\\{w\\}}1$
and
$\sum_{w\in\mathcal{N}(u)\cup\\{u\\}}\sum_{x\in\mathcal{N}(w)\cup\\{w\\}}1$
are equal to the number of walks of length $2$ starting from nodes $v$ and
$u$, respectively. And more generally, for $k=K$,
$\sum_{w\in\mathcal{N}(v)\cup\\{v\\}}\sum_{x\in\mathcal{N}(w)\cup\\{w\\}}$
$\ldots$ $\sum_{z\in\mathcal{N}(y)\cup\\{y\\}}1$ and
$\sum_{w\in\mathcal{N}(u)\cup\\{u\\}}\sum_{x\in\mathcal{N}(w)\cup\\{w\\}}\ldots\sum_{z\in\mathcal{N}(y)\cup\\{y\\}}1$
are equal to the number of walks of length $K$ starting from nodes $v$ and
$u$, respectively. Thus, the representations learned by GIN-$0$ are related to
the number of walks emanating from each node.