Generalization Limits of Graph Neural Networks in Identity Effects
  Learning
Graph Neural Networks (GNNs) have emerged as a powerful tool for data-driven
learning on various graph domains. They are usually based on a message-passing
mechanism and have gained increasing popularity for their intuitive
formulation, which is closely linked to the Weisfeiler-Lehman (WL) test for
graph isomorphism to which they have been proven equivalent in terms of
expressive power. In this work, we establish new generalization properties and
fundamental limits of GNNs in the context of learning so-called identity
effects, i.e., the task of determining whether an object is composed of two
identical components or not. Our study is motivated by the need to understand
the capabilities of GNNs when performing simple cognitive tasks, with potential
applications in computational linguistics and chemistry. We analyze two case
studies: (i) two-letters words, for which we show that GNNs trained via
stochastic gradient descent are unable to generalize to unseen letters when
utilizing orthogonal encodings like one-hot representations; (ii) dicyclic
graphs, i.e., graphs composed of two cycles, for which we present positive
existence results leveraging the connection between GNNs and the WL test. Our
theoretical analysis is supported by an extensive numerical study.
Giuseppe Alessio D'Inverno, Simone Brugiapaglia, Mirco Ravanelli
# Generalization Limits of Graph Neural Networks

###### Abstract

Graph Neural Networks (GNNs) have emerged as a powerful tool for data-driven learning on various graph domains. They are usually based on a message-passing mechanism and have gained increasing popularity for their intuitive formulation, which is closely linked to the Weisfeiler-Lehman (WL) test for graph isomorphism to which they have been proven equivalent in terms of expressive power.

In this work, we establish new generalization properties and fundamental limits of GNNs in the context of learning so-called identity effects, i.e., the task of determining whether an object is composed of two identical components or not. Our study is motivated by the need to understand the capabilities of GNNs when performing simple cognitive tasks, with potential applications in computational linguistics and chemistry. We analyze two case studies: (i) two-letters words, for which we show that GNNs trained via stochastic gradient descent are unable to generalize to unseen letters when utilizing orthogonal encodings like one-hot representations; (ii) dicyclic graphs, i.e., graphs composed of two cycles, for which we present positive existence results leveraging the connection between GNNs and the WL test. Our theoretical analysis is supported by an extensive numerical study.

 Graph neural networks, identity effects, generalization, encodings, dicyclic graphs, gradient descent.

## I Introduction

Graph Neural Networks (GNNs) [1] have emerged as prominent models for handling structured data, quickly becoming dominant in data-driven learning over several scenarios such as network analysis [2], molecule prediction [3] and generation [4], text classification [5], and traffic forecasting [6]. From the appearance of the earliest GNN model [1], many variants have been developed to improve their prediction accuracy and generalization power. Notable examples include GraphSage [7], Graph Attention Networks [8], Graph Convolutional Networks (GCN) [9], Graph Isomorphism Networks [10], and Graph Neural Diffusion (GRAND) [11]. Furthermore, as the original model was designed specifically for labeled undirected graphs [12], more complex neural architectures have been designed to handle different types of graph structures, such as directed graphs [13], temporal graphs [14], and hypergraphs [15]. For a comprehensive review see, e.g., [16].

Over the last decade, there has been growing attention in the theoretical analysis of GNNs. While approximation properties have been examined in different flavors [17, 18, 1, 19], most of the theoretical works in the literature have focused on the _expressive power_ of GNNs. From this perspective, the pioneering work of [10] and [20] laid the foundation for the standard analysis of GNN expressivity, linking the message-passing iterative algorithm (common to most GNN architectures) to the _first order Weisfeiler Lehman (1-WL) test_[21], a popular coloring algorithm used to determine if two graphs are (possibly) isomorphic or not. Since then, the expressive power of GNNs has been evaluated with respect to the 1-WL test or its higher-order variants (called \(k\)_-WL test_) [20], as well as other variants suited to detect particular substructures [22, 23].

The assessment of the _generalization capabilities_ of neural networks has always been crucial for the development of efficient learning algorithms. Several complexity measures have been proposed over the past few decades to establish reliable generalization bounds, such as the Vapnik-Chervonenk (VC) dimension [24], Rademacher complexity [25, 26], and Betti numbers [27]. The generalization properties of GNNs have been investigated using these measures. In [28] the VC dimension of the original GNN model was established, and later extended to message passing-based GNNs by [29] for piecewise polynomial activation functions. Other generalization bounds for GNNs were derived using the Rademacher complexity [30], through a Probably Approximately Correct (PAC) Bayesian approach [31] or using random sampling on the graph nodes [32].

An alternative approach for assessing the generalization capabilities of neural networks is based on investigating their ability to learn specific _cognitive tasks_[33, 34, 35], which have long been of primary interest as neural networks were originally designed to emulate functional brain activities. Among the various cognitive tasks, the linguistics community has shown particular interest in investigating so-called _identity effects_, i.e., the task of determining whether objects are formed by two identical components or not [36, 37]. To provide a simple and illustrative example, we can consider an experiment in which the words \(\mathsf{AA},\mathsf{BB},\mathsf{CC}\) are assigned to the label "good", while \(\mathsf{AB},\mathsf{BC},\mathsf{AC}\) are labelled as "bad". Now, imagine a scenario where a subject is presented with new test words, such as \(\mathsf{XX}\) or \(\mathsf{XY}\). Thanks to the human ability of abstraction, the subject will be immediately able to classify the new words correctly, even though the letters \(\mathsf{X}\) and \(\mathsf{Y}\) were not part of the the training set. Besides its relevance in linguistics, the analysis of identity effects can serve as an intuitive and effective tool
to evaluate the generalization capabilities of neural networks in a variety of specific tasks. These tasks encompass the identification of equal patterns in natural language processing [38] as well as molecule classification or regression [3]. In the context of molecule analysis, the exploitation of molecular symmetries plays a crucial role as it can be exploited to retrieve molecular orientations [39] or to determine properties of molecular positioning [40]. Furthermore, the existence of different symmetries in interacting molecules can lead to different reactions.

Recently, in [41] it has been shown that Multilayer Perceptrons (MLPs) and Recurrent Neural Networks (RNNs) cannot learn identity effects via Stochastic Gradient Descent, under certain conditions on the encoding utilized to represent the components of objects. This finding raises a fundamental question that forms the core focus of our paper: "_Do GNNs possess the capability to learn identity effects?_"

Motivated by this research question, this work investigates the generalization limits and capabilities of GNNs when learning identity effects. Our contributions are the following:

1. extending the analysis of [41], GNNs are shown to be _incapable_ of learning identity effects via SGD training under sufficient conditions determined by the existence of a suitable transformation \(\tau\) of the input space (Theorem III.1); an application to the problem of classifying identical two-letter words is provided by Theorem III.3 and supported by numerical experiments in SSIV-B;
2. on the other hand, GNNs are shown to be _capable_ of learning identity effects in terms of binary classification of _dicyclic graphs_, i.e., graphs composed by two cycles of different or equal length, in Corollary III.6; a numerical investigation of the gap between our theoretical results and practical performance of GNNs is provided in SSIV-C.

The paper is structured as follows. SSII begins by providing a brief overview of fundamental graph theory notation. We then introduce the specific GNN formulation we focus on in our analysis, namely the Weisfeiler-Lehman test, and revisit the framework of rating impossibility theorems for invariant learners. In SSIII, we present and prove our main theoretical results. SSIV showcases the numerical experiments conducted to validate our findings. Finally, in SSV, we provide concluding remarks and outline potential avenues for future research.

## II Notation and background

We start by introducing the notation and background concepts that will be used throughout the paper.

### _Graph theory basics_

A node-attributed graph \(G\) is an object defined by a triplet \(G=(V,E,\alpha)\). \(V\) is the set of _nodes_ or _vertices_\(v\), where \(v\) can be identified as an element of \(\mathbb{N}:=\{0,1,2,\ldots\}\). \(E\) is the set of edges \(e_{u,v}\), where \(e_{u,v}=(u,v)\in V\times V\). The term \(\alpha:V\rightarrow\mathbb{R}^{k}\) is the function assigning a _node feature_ (or _vertex feature_) \(\alpha_{v}\) to every node \(v\) in the graph. The _number of nodes_ of a graph G is denoted by \(N:=|V|\). All node features can be stacked in a _feature matrix_\(\mathbf{X}_{G}\in N\times\mathbb{R}^{k}\). The _adjacency matrix_\(\mathbf{A}\) is defined as \(A_{ij}=1\) if \(e_{ij}\in E\), \(A_{ij}=0\) otherwise. The _neighborhood_ of a node \(v\) is denoted by \(\mathcal{N}_{v}=\{u\mid e_{u,v}\in E\}\).

### _Graph Neural Networks_

Graph Neural Networks (GNNs) are a class of connection-ist models that aim to learn functions on graphs, or pairs graph/node. Intuitively, a GNN learns how to represent the nodes of a graph by vectorial representations (which are called _hidden states_), giving an encoding of the information stored in the graph. In its general form [1, 42], for each graph \(G=(V,E,\alpha)\in\mathcal{G}\) where \(\mathcal{G}\) is a node-attributed graph domain, a GNN is defined by the following recursive _updating scheme_:

\[h_{v}^{(t+1)}=\text{UPDATE}\big{(}h_{v}^{(t)},\text{AGGREGATE}(\{\!\!\{h_{u} ^{(t)}|u\in\mathcal{N}_{v}\}\!\!\})\big{)}, \tag{1}\]

for all \(v\in V\) and \(t=1,\ldots,T\), where \(T\) is the number of layers of the GNN and \(\{\!\!\{\cdot\}\!\}\) denotes a multiset. Here UPDATE and AGGREGATE are functions that can be defined by learnable or non-learnable schemes. Popular GNN models like GraphSAGE [7], GCN [9], Graph Isomorphism Networks [10] are based on this updating scheme. The model terminates with a READOUT function, chosen according to the nature of the task; for instance, global average, min or sum pooling, followed by a trainable multilayer perceptron are typical choices in the case of graph-focused tasks. At a high level, we can formalizate a GNN as a function \(g:\mathcal{G}\rightarrow\mathbb{R}^{r}\), where \(\mathcal{G}\) is a set of node-attributed graphs and \(r\) is the dimension of the output, which depends on the type of task at hand.

The updating scheme we choose as a reference for our analysis follows [20]. This model has been proven to match the expressive power of the Weisfeiler-Lehman test [20] (see also Theorem II.1 below), and can therefore be considered a good representative model of the message passing GNN class. The hidden dimension \(h_{v}^{(t+1)}\in\mathbb{R}^{h}\) of a node \(v\) at the message passing iteration \(t+1\), for \(t=1,\ldots,T-1\), is defined as

\[h_{v}^{(t+1)}=\sigma\big{(}W_{\text{upd}}^{(t+1)}h_{v}^{(t)}+W_{\text{agg}}^{ (t+1)}h_{\mathcal{N}_{v}}^{(t)}+b^{(t+1)}\big{)}, \tag{2}\]

where \(h_{\mathcal{N}_{v}}^{(t)}=\text{POOL}\llbracket h_{u}^{(t)}|u\in\mathcal{N}_{v} \rrbracket\), \(\sigma:\mathbb{R}^{h}\rightarrow\mathbb{R}^{h}\) is an element-wise activation function and POOL is the aggregating operator on the neighbor node's features. The aggregating operator can be defined as a non-learnable function, such as the sum, the mean or the minimum, across the hidden features of the neighbors. For each node, the initial hidden state is initialized as \(h_{v}^{(0)}=\alpha_{v}\in\mathbb{R}^{k}\). The learnable parameters of the GNN can be summarized as \(\Theta:=(W_{\text{upd}}^{(0)},W_{\text{agg}}^{(0)},b^{(0)},W_{\text{upd}}^{ (1)},W_{\text{agg}}^{(1)},b^{(1)},\ldots,W_{\text{upd}}^{(L)},W_{\text{agg}}^{ (L)},b^{(L)})\), with \(W_{\text{upd}}^{(0)},W_{\text{agg}}^{(0)}\in\mathbb{R}^{k\times h}\), \(W_{\text{upd}}^{(t)},W_{\text{agg}}^{(t)}\in\mathbb{R}^{h\times h}\), for \(t=1,\ldots,T\), and \(b^{(t)}\in\mathbb{R}^{h}\), for \(t=0,\ldots,T\).

### _The Weisfeiler-Lehman test_

The _first order Weisfeiler-Lehman test_ (in short, _I-WL test_) [21] is one of the most popular isomorphism tests for graphs, based on an iterative coloring scheme. The coloring algorithm is applied in parallel to two input graphs, giving a color partition of the nodes as output. If the partitions match, then the graphs are possibly isomorphic, while if they do not match,
then the graphs are certainly non-isomorphic. Note that the test is not conclusive in the case of a positive answer, as the graphs may still be non-isomorphic; nevertheless, the 1-WL test provides an accurate isomorphism test for a large class of graphs [43].

The coloring is carried out by an iterative algorithm which takes as input a graph \(G=(V,E,\alpha)\) and, at each iteration, computes a _node coloring_\(c^{(t)}(v)\in\mathcal{C}\) for each node \(v\in V\), being \(\mathcal{C}\subseteq\mathbb{N}\) a subset of natural numbers representing colors. The algorithm is sketched in the following.

1. At iteration 0, in the case of labeled graphs, the node color initialization is based on the vertex feature according to a specific hash function \(\operatorname{HASH}_{0}:\mathbb{R}^{k}\to\mathcal{C}\); namely, \(c^{(0)}(v)=\operatorname{HASH}_{0}(\alpha(v))\), for all \(v\in V\). For unlabeled graphs, a node color initialization is provided, usually setting every color as equal to a given initial color \(c^{(0)}\in\mathcal{C}\).
2. For any iteration \(t>0\), we set \[c^{(t)}(v)=\operatorname{HASH}((c^{(t-1)}(v),\llbracket c^{(t-1)}(n)|n\in \mathcal{N}_{v}\rrbracket)),\] \(\forall v\in V\), where \(\operatorname{HASH}\) injectively maps the above color-multiset pair to a unique value in \(\mathcal{C}\).

The algorithm terminates if the number of colors between two iterations does not change, i.e., when the cardinalities of \(\{c^{(t-1)}(v)|v\in V\}\) and \(\{c^{(t)}(v)|v\in V\}\), namely, are equal.

We conclude by recalling two results establishing the equivalence between GNNs' and 1-WL test's expressive power that will be instrumental for our analysis. A first result was proved in [10] and it characterizes the equivalence on a graph-level task for GNNs with generic message passing layers satisfying suitable conditions. Another characterization, reported below, is due to [20] and states the equivalence on a node coloring level, referring to the particular model defined in (2).

**Theorem II.1** (See [20, Theorem 2]).: _Let \(G=(V,E,\alpha)\) be a graph with initial coloring \(c^{(0)}(v)\in\mathbb{R}\) for each node \(v\in V\) (so that \(c^{(0)}\in\mathbb{R}^{|V(G)|}\)). Then, for all \(t\geq 0\) there exists a GNN of the form (2) such that the hidden feature vector \(h^{(t)}\in\mathbb{R}^{|V(G)|}\) produced by the GNN at layer \(t\) coincides with the color vector \(c^{(t)}\in\mathbb{R}^{|V(G)|}\) produced by the 1-WL test at iteration \(t\), i.e., \(c^{(t)}\equiv h^{(t)}\)._

### _Rating impossibility for invariant learners_

We now recall the framework of rating impossibility from [41], which we will then apply to the case of identity effects learning. In general, we assume to train a _learning algorithm_ to perform a rating assignment task, where the rating \(r\) is a real number. Let \(\mathcal{I}\) be the set of all possible inputs \(x\) (that could be, for instance, elements of \(\mathbb{R}^{d}\)). Our learning algorithm is trained on a dataset \(D\subseteq\mathcal{I}\times\mathbb{R}\) consisting of a finite set of input-rating pairs \((x,r)\). Let \(\mathcal{D}\) be the set of all possible datasets with inputs in \(\mathcal{I}\). The learning algorithm is trained via a suitable optimization method, such as Stochastic Gradient Descent (SGD) or Adaptive Moment Estimation (Adam) [44], that for any given training dataset \(D\) outputs the optimized set of parameters \(\Theta=\Theta(D)\in\mathbb{R}^{p}\), which, in turn, defines a model \(f=f(\Theta,\cdot)\). The rating prediction on a novel input \(x\in\mathcal{I}\) is then given by \(r=f(\Theta,x)\). In summary, a learning algorithm can thought of as a map \(L:\mathcal{D}\times\mathcal{I}\to\mathbb{R}\), defined as \(L(D,x)=f(\Theta(D),x)\).

Given the stochastic nature of neural network training, we adopt a nondeterministic point of view. Hence we require the notion of _equality in distribution_. Two random variables \(X,Y\) taking values in \(\mathbb{R}^{k}\) are said to be _equal in distribution_ (denoted by \(X\stackrel{{ d}}{{=}}Y\)) if \(\mathbb{P}(X\leq x)=\mathbb{P}(Y\leq x)\) for all \(x\in\mathbb{R}^{k}\), where inequalities hold componentwise. With this notation, rating impossibility means that \(L(D,x_{1})\stackrel{{ d}}{{=}}L(D,x_{2})\) for two inputs \(x_{1}\neq x_{2}\) drawn from \(\mathcal{I}\setminus D\). Sufficient conditions for rating impossibility are identified by the following theorem from [41] (here slightly adapted using equality in distribution), which involves the existence of an auxiliary transformation \(\tau\) of the inputs.

**Theorem II.2** (Rating impossibility for invariant learners, [41, Theorem 1]).: _Consider a dataset \(D\subseteq\mathcal{I}\times\mathbb{R}\) and a transformation \(\tau:\mathcal{I}\to\mathcal{I}\) such that_

1. \(\tau(D)\stackrel{{ d}}{{=}}D\) (_invariance of the data_).1 Footnote 1: By definition, \(\tau(D):=\{(\tau(x),r):(x,r)\in D\}\).
2. _Then, for any learning algorithm_ \(L:\mathcal{D}\times\mathcal{I}\to\mathbb{R}\) _and any input_ \(x\in\mathcal{I}\) _such that_ 1. \(L(\tau(D),\tau(x))\stackrel{{ d}}{{=}}L(D,x)\) _(invariance of the algorithm), we have_ \(L(D,\tau(x))\stackrel{{ d}}{{=}}L(D,x)\)_._

This theorem states that under the invariance of the data and of the algorithm, the learner cannot assign different ratings to an input \(x\) and its transformed version \(\tau(x)\). This leads to rating impossibility when \(\tau(x)\neq x\) and \(x,\tau(x)\in\mathcal{I}\setminus D\).

We conclude by recalling some basic notions on SGD training. Given a dataset \(D\), we aim to find parameters \(\Theta\) that minimize an objective function of the form

\[F(\Theta)=\mathcal{L}((f(\Theta,x),r):(x,r)\in D),\quad\Theta\in\mathbb{R}^{p},\]

where \(\mathcal{L}\) is a (possibly regularized) loss function. We assume \(F\) to be differentiable over \(\mathbb{R}^{p}\) in order for its gradients to be well defined. Given a collection of subsets \((D_{i})_{i=0}^{k-1}\) with \(D_{i}\subseteq D\) (usually referred to as training batches, which can be either deterministically or randomly generated), we define \(F_{D_{i}}\) as the function \(F\) where the loss is evaluated only on data in \(D_{i}\). In SGD-based training, we randomly initialize \(\Theta_{0}\) and iteratively compute

\[\Theta_{i+1}=\Theta_{i}-\eta_{i}\frac{\partial F_{D_{i}}}{\partial\Theta}( \Theta_{i}), \tag{3}\]

for \(i=0,1,\ldots,k-1\), where the sequence of step sizes \((\eta_{i})_{i=0}^{k-1}\) is assumed to be either deterministic or random and independent of \((D_{i})_{i=0}^{k-1}\). Note that, being \(\Theta_{i}\) a random vector for each \(i\), the output of the learning algorithm \(L(D,x)=f(\Theta_{k},x)\) is a random variable.

## III Theoretical analysis

In this section we present our theoretical analysis. More specifically, in SSIII-A we establish a rating impossibility theorem for GNNs under certain technical assumptions related
to the invariance of the training data under a suitable transformation \(\tau\) of the inputs; then, we illustrate an application to the case study of identity effects learning for a two-letter word dataset in SSIII-A1. In SSIII-B we prove that symmetric dicyclic graphs can be distinguished from the asymmetric ones by the 1-WL test, and consequently by a GNN.

### _What GNNs cannot learn: rating impossibility theorem_

We assume the input space to be of the form \(\mathcal{I}=\mathbb{R}^{d}\times\mathbb{R}^{d}\) and the learning algorithm

\[L(D,x)=f(B,Gu+Hv,Hu+Gv),\ \forall x=(u,v)\in\mathcal{I}, \tag{4}\]

where \(\Theta=(B,G,H)\) are trainable parameters and \(G,H\in\mathbb{R}^{d\times d}\). This class of learning algorithms perfectly fits the formulation given in [20], where the updating scheme is the one defined by (2). In this case,

\[G =W_{upd}^{(1)},\quad H=W_{agg}^{(1)},\] \[B =\left(b^{(1)},W_{upd}^{(2)},W_{agg}^{(2)},b^{(2)}\ldots,W_{upd} ^{(N)},W_{agg}^{(N)},b^{(N)}\right).\]

The learner defined by equation (4) mimics the behaviour of several GNN architectures, GCN included. In fact, when the graph is composed by only two nodes, the convolution ends up being a weighted sum of the hidden states of the two nodes. This property will have practical relevance in Theorem III.3 and its experimental realization in SSIV-B.

In the following result we identify sufficient conditions on the dataset \(D\) and the training procedure able to guarantee invariance of GNN-type models of the form (4) trained via SGD to a suitable class of transformations \(\tau\) (hence verifying condition (ii) of Theorem II.2).

**Theorem III.1** (Invariance of GNN-type models trained via SGD).: _Assume the input space to be of the form \(\mathcal{I}=\mathbb{R}^{d}\times\mathbb{R}^{d}\). Let \(\tau:\mathcal{I}\rightarrow\mathcal{I}\) be a linear transformation defined by \(\tau(x)=(u,\tau_{2}(v))\) for any \(x=(u,v)\in\mathcal{I}\), where \(\tau_{2}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}\) is also linear. Moreover, assume that_

* _the matrix_ \(T_{2}\in\mathbb{R}^{d\times d}\) _associated with the transformation_ \(\tau_{2}\) _is orthogonal and symmetric;_
* _the dataset_ \(D=\{((u_{i},v_{i}),r_{i})\}_{i=1}^{n}\) _is invariant under the transformation_ \(\tau_{2}\otimes\tau_{2}\)_, i.e.,_ \[(u_{i},v_{i})=\big{(}\tau_{2}(u_{i}),\tau_{2}(v_{i})\big{)},\quad\forall i=1, \ldots,n.\] (5)

_Suppose k iterations of SGD as defined in (3) are used to determine parameters \(\Theta_{k}=(B_{k},G_{k},H_{k})\) with objective function_

\[F(\Theta)=\sum_{i=1}^{n}\ell\big{(}f(B,Gu_{i}+Hv_{i},Hu_{i}+Gv_{i}),r_{i} \big{)}+\lambda\mathcal{R}(B),\]

_for some \(\lambda\geq 0\), with \(\Theta=(B,G,H)\) and where \(\ell\), \(f\) and \(\mathcal{R}\) are real-valued functions such that \(F\) is differentiable. Suppose the random initialization of the parameters \(B\), \(G\) and \(H\) to be independent and that the distributions of \(G_{0}\) and \(H_{0}\) are invariant with respect to right-multiplication by \(T_{2}\). Then, the learner \(L\) defined by \(L(D,x)=f(B_{k},G_{k}u+H_{k}v,H_{k}u+G_{k}v)\), for \(x=(u,v)\), satisfies \(L(D,x)\stackrel{{ d}}{{=}}L(\tau(D),\tau(x))\)._

Proof.: Given a batch \(D_{i}\subseteq D\), define \(J_{i}:=\{j\in\{1,\ldots,n\}:\)\(((u_{j},v_{j}),r_{j})\in D_{i}\}\) and

\[F_{D_{i}}(\Theta)=\sum_{j\in J_{i}}\ell(f(B,Gv_{j}+Hu_{j},Hv_{j}+ Gu_{j}),r_{j})+\lambda\mathcal{R}(B).\]

Moreover, consider an _auxiliary objective function_, defined by

\[\tilde{F}_{D_{i}}(B,G_{1},H_{1},H_{2},G_{2})=\] \[\sum_{j\in J_{i}}\ell(f(B,G_{1}v_{j}+H_{1}u_{j},H_{2}v_{j}+G_{2} u_{j}),r_{j})+\lambda\mathcal{R}(B).\]

Observe that \(F_{D_{i}}(\Theta)=\tilde{F}_{D_{i}}(B,G,H,H,G)\). Moreover,

\[\frac{\partial F_{D_{i}}}{\partial B}(\Theta) =\frac{\partial\tilde{F}_{D_{i}}}{\partial B}(B,G,H,H,G) \tag{6}\] \[\frac{\partial F_{D_{i}}}{\partial G}(\Theta) =\frac{\partial\tilde{F}_{D_{i}}}{\partial I}(B,G,H,H,G)+\frac{ \partial\tilde{F}_{D_{i}}}{\partial L}(B,G,H,H,G)\] (7) \[\frac{\partial F_{D_{i}}}{\partial H}(\Theta) =\frac{\partial\tilde{F}_{D_{i}}}{\partial J}(B,G,H,H,G)+\frac{ \partial\tilde{F}_{D_{i}}}{\partial K}(B,G,H,H,G) \tag{8}\]

Moreover, replacing \(D_{i}\) with its transformed version \(\tau(D_{i})=\{((u_{j},\tau_{2}(v_{j})),r_{j})\}_{j\in D_{i}}\), we see that \(F_{\tau(D_{i})}(\Theta)=\tilde{F}_{D_{i}}(B,G,HT_{2},H,GT_{2})\). This leads to

\[\frac{\partial F_{\tau(D_{i})}}{\partial B}(\Theta) =\frac{\partial\tilde{F}_{D_{i}}}{\partial B}(B,G,HT_{2},H,GT_{2}) \tag{9}\] \[\frac{\partial F_{\tau(D_{i})}}{\partial G}(\Theta) =\frac{\partial\tilde{F}_{D_{i}}}{\partial G_{1}}(B,G,HT_{2},H,GT_ {2})\] \[\quad+\frac{\partial\tilde{F}_{D_{i}}}{\partial G_{2}}(B,G,HT_{2}, H,GT_{2})T_{2}^{T}\] (10) \[\frac{\partial F_{\tau(D_{i})}}{\partial H}(\Theta) =\frac{\partial\tilde{F}_{D_{i}}}{\partial H_{1}}(B,G,HT_{2},H, GT_{2})T_{2}^{T}\] \[\quad+\frac{\partial\tilde{F}_{D_{i}}}{\partial H_{2}}(B,G,HT_{2}, H,GT_{2}). \tag{11}\]

Now, denoting \(\ell=\ell(f,r)\) and \(f=f(B,u,v)\), we have

\[\frac{\partial\tilde{F}_{D_{i}}}{\partial G_{1}} =\sum_{j\in D_{i}}\frac{\partial\ell}{\partial f}\frac{\partial f }{\partial u}u_{j}^{T}, \frac{\partial\tilde{F}_{D_{i}}}{\partial H_{1}} =\sum_{j\in D_{i}}\frac{\partial\ell}{\partial f}\frac{\partial f }{\partial u}u_{j}^{T},\] \[\frac{\partial\tilde{F}_{D_{i}}}{\partial H_{2}} =\sum_{j\in D_{i}}\frac{\partial\ell}{\partial f}\frac{\partial f }{\partial u}v_{j}^{T}, \frac{\partial\tilde{F}_{D_{i}}}{\partial G_{2}} =\sum_{j\in D_{i}}\frac{\partial\ell}{\partial f}\frac{\partial f }{\partial u}u_{j}^{T}.\]

In addition, thanks to assumption (5), we have \(u_{j}^{T}T_{2}^{T}=u_{j}^{T}\) and \(v_{j}^{T}T_{2}^{T}=v_{j}^{T}\) for all \(j\in J_{i}\). Thus, we obtain

\[\frac{\partial\tilde{F}_{D}}{\partial G_{1}}T_{2}^{T} =\frac{\partial\tilde{F}_{D}}{\partial G_{1}}, \frac{\partial\tilde{F}_{D}}{\partial H_{1}}T_{2}^{T} =\frac{\partial\tilde{F}_{D}}{\partial H_{1}}, \tag{12}\] \[\frac{\partial\tilde{F}_{D}}{\partial H_{2}}T_{2}^{T} =\frac{\partial\tilde{F}_{D}}{\partial H_{2}}, \frac{\partial\tilde{F}_{D}}{\partial G_{2}}T_{2}^{T} =\frac{\partial\tilde{F}_{D}}{\partial G_{2}}. \tag{13}\]

Now, let \((B_{0}^{\prime},G_{0}^{\prime},H_{0}^{\prime})\stackrel{{ d}}{{=}}(B_{0},G_{0},H_{0})\) and let \((B_{i}^{\prime},G_{i}^{\prime},H_{i}^{\prime})\) for \(i=1,\ldots k\) be the sequence generated by SGD, applied to the transformed data \(\tau(D)\). By assumption, we have \(B_{0}^{\prime}\stackrel{{ d}}{{=}}B_{0}\), \(G_{0}\stackrel{{ d}}{{=}}G_{0}^{\prime}\stackrel{{ d}}{{=}}G_{0}^{\prime}T_{2}\) and \(H_{0}\stackrel{{ d}}{{=}}H_{0}^{\prime}T_{2}\). We now show by induction that \(B_{i}^
\(H_{i}^{\prime}T_{2}\) for all indices \(i=1,\ldots,k\). Using equations (6) and (9) and the inductive hypothesis, we have

\[B_{i+1}^{\prime} =B_{i}^{\prime}-\eta_{i}\frac{\partial F_{\tau(D_{i})}}{\partial B} (B_{i}^{\prime},G_{i}^{\prime},H_{i}^{\prime})\] \[=B_{i}^{\prime}-\eta_{i}\frac{\partial\tilde{F}_{D_{i}}}{\partial B }(B_{i}^{\prime},G_{i}^{\prime},H_{i}^{\prime}T_{2},H_{i}^{\prime},G_{i}^{ \prime}T_{2})\] \[\overset{d}{=}B_{i}-\eta_{i}\frac{\partial\tilde{F}_{D_{i}}}{ \partial B}(B_{i},G_{i},H_{i},H_{i},G_{i})\] \[=B_{i}-\eta_{i}\frac{\partial F_{\tau(D_{i})}}{\partial B}(B_{i}, G_{i},H_{i})=B_{i+1}.\]

Similarly, using equations (7), (10) and (13) and the inductive hypothesis, we see that

\[G_{i+1}^{\prime} =G_{i}^{\prime}-\eta_{i}\frac{\partial F_{\tau(D_{i})}}{\partial G }(B_{i}^{\prime},G_{i}^{\prime},H_{i}^{\prime})\] \[=G_{i}^{\prime}-\eta_{i}\left(\frac{\partial\tilde{F}_{D_{i}}}{ \partial I}(B_{i}^{\prime},G_{i}^{\prime},H_{i}^{\prime}T_{2},H_{i}^{\prime},G _{i}^{\prime}T_{2})\right.\] \[\left.+\frac{\partial\tilde{F}_{D_{i}}}{\partial L}(B_{i}^{ \prime},G_{i}^{\prime},H_{i}^{\prime}T_{2},H_{i}^{\prime},G_{i}^{\prime}T_{2} )T_{2}^{T}\right)\] \[=G_{i}^{\prime}-\eta_{i}\left(\frac{\partial\tilde{F}_{D_{i}}}{ \partial I}(B_{i}^{\prime},G_{i}^{\prime},H_{i}^{\prime}T_{2},H_{i}^{\prime},G _{i}^{\prime}T_{2})\right.\] \[\left.+\frac{\partial\tilde{F}_{D_{i}}}{\partial L}(B_{i}^{ \prime},G_{i}^{\prime},H_{i}^{\prime}T_{2},H_{i}^{\prime},G_{i}^{\prime}T_{2} )\right)\] \[\overset{d}{=}G_{i}-\eta_{i}\left(\frac{\partial\tilde{F}_{D_{i} }}{\partial I}(B_{i},G_{i},H_{i},H_{i},G_{i})\right.\] \[\left.+\frac{\partial\tilde{F}_{D_{i}}}{\partial L}(B_{i},G_{i},H_ {i},H_{i},G_{i})\right)\] \[=G_{i}-\eta_{i}\frac{\partial F_{D_{i}}}{\partial G}(B_{i},G_{i},H _{i})=G_{i+1}.\]

One proceeds analogously for \(H_{i+1}^{\prime}\) using equations (8), (11) and (12). Similarly, one also sees that \(G_{i+1}^{\prime}T_{2}\overset{d}{=}G_{i+1}\) and \(H_{i+1}^{\prime}T_{2}\overset{d}{=}H_{i+1}\) combining the previous equations with symmetry and orthogonality of \(T_{2}\).

In summary, we have

\[L(D,x) =f(B_{k},G_{k}u+H_{k}v,H_{k}u+G_{k}v)\] \[\overset{d}{=}f(B_{k}^{\prime},G_{k}^{\prime}u+H_{k}^{\prime}v,H_ {k}^{\prime}u+G_{k}^{\prime}v)\] \[\overset{d}{=}f(B_{k}^{\prime},G_{k}^{\prime}u+H_{k}^{\prime}T_{2 }v,H_{k}^{\prime}u+G_{k}^{\prime}T_{2}v)\] \[=L(\tau(D),\tau(x)),\]

which concludes the proof. 

**Remark III.2** (On the assumptions of Theorem III.1).: At first glance, the assumptions of Theorem III.1 might seem quite restrictive, especially the assumption about the invariance of the distributions of \(G_{0}\) and \(H_{0}\) with respect to right-multiplication by the symmetric orthogonal matrix \(T_{2}\). Yet, this hypothesis holds, e.g., when the entries of \(G_{0}\) and \(H_{0}\) are independently and identically distributed according to a centered normal distribution thanks to the rotational invariance of isotropic random Gaussian vectors (see, e.g., [45, Proposition 3.3.2]). This is the case in common initialization strategies such as Xavier initialization [46]. In addition, numerical results presented in SSIV suggest that rating impossibility might hold in more general settings, such as when the model \(f\) includes ReLU activations (hence, when \(F\) has points of nondifferentiability) or for models trained via Adam as opposed to SGD.

#### Iii-B1 Application to identity effects

As a practical application of Theorem III.1 to identity effects, we consider the problem of classifying identical two-letter words of the English alphabet \(\mathcal{A}:=\{\mathsf{A},\mathsf{B},\ldots,\mathsf{Z}\}\), already mentioned in SSI and following [41]. Consider a training set \(D\) formed by two-letter words that do not contain \(\mathsf{Y}\) nor \(\mathsf{Z}\). Words are assigned the label 1 if they are composed by identical letters and 0 otherwise. Our goal is to verify whether a learning algorithm is capable of generalizing this pattern correctly to words containing the letters \(\mathsf{Y}\) or \(\mathsf{Z}\). The transformation \(\tau\) of Theorem III.1 is defined by

\[\tau(\mathsf{x}\mathsf{Y})=\mathsf{x}\mathsf{Z},\;\tau(\mathsf{x}\mathsf{Z})= \mathsf{x}\mathsf{Y},\;\text{and}\;\tau(\mathsf{x}\mathsf{y})=\mathsf{x} \mathsf{y}, \tag{14}\]

for all letters \(\mathsf{x},\mathsf{y}\in\mathcal{A}\), with \(\mathsf{y}\neq\mathsf{Y},\mathsf{Z}\). Note that this transformation is of the form \(\tau=I\otimes\tau_{2}\), where \(I\) is the identity map. Hence, it fits the setting of Theorem III.1. Moreover, since \(D\) does not contain Y nor \(\mathsf{Z}\) letters, \(\tau(D)=D\). Hence, condition (i) of Theorem II.2 is satisfied.

In order to represent letters as vectors of \(\mathbb{R}^{d}\), we need to use a suitable _encoding_. Its choice is crucial to determine the properties of the transformation matrix \(T_{2}\) associated with \(\tau_{2}\), needed to apply Theorem III.1. Formally, an encoding of an alphabet \(\mathcal{A}\) is a set of vectors \(\mathcal{E}\subseteq\mathbb{R}^{d}\), of the same cardinality of \(\mathcal{A}\), to which letters can be associated with. In our case, \(|\mathcal{A}|=26=|\mathcal{E}|\). We say that an encoding is _orthogonal_ if it is an orthonormal set of \(\mathbb{R}^{d}\). For example, the popular one-hot encoding \(\mathcal{E}=\{e_{i}\}_{i=1}^{26}\subseteq\mathbb{R}^{26}\), i.e., the canonical basis of \(\mathbb{R}^{26}\), is an orthogonal encoding.

In this setting, every word is modeled as a graph defined by two nodes connected by a single unweighted and undirected edge. Each node \(v\) is labeled with a node feature \(\alpha(v)\in\mathbb{R}^{d}\), corresponding to a letter's encoding. An example is depicted in Figure 1.

**Theorem III.3** (Inability of GNNs to classify identical two-letter words outside the training set).: _Let \(\mathcal{E}\subseteq\mathbb{R}^{26}\) be an orthogonal encoding of the English alphabet \(\mathcal{A}\) and let \(L\) be a learner obtained by training a GNN of the form (2) via SGD to classify identical two-letter words. Assume that words in the training set \(D\) do not contain the letter \(\mathsf{Y}\) nor \(\mathsf{Z}\). Then,

Fig. 1: Graph modeling of a two-letter word: a vertex feature \(\alpha(v)\in\mathbb{R}^{d}\) is attached to each node \(v\) of a two-node undirected graph, according to a given encoding \(\mathcal{E}\) of the English alphabet \(\mathcal{A}\). In this figure, \(\mathcal{E}\) is the one-hot encoding.
\(L\) assigns the same rating (in distribution) to any word of the form \(\mathsf{xy}\) where \(\mathsf{y}\in\{\mathsf{Y},\mathsf{Z}\}\), i.e., \(L(D,\mathsf{x}\mathsf{Y})\stackrel{{ d}}{{=}}L(D,\mathsf{x}\mathsf{Z})\) for any \(\mathsf{x}\in\mathcal{A}\). Hence, it is unable to generalize to identity effect outside the training set._

Proof.: As discussed above, the transformation \(\tau\) defined by (14) is of the form \(\tau=I\otimes\tau_{2}\). Moreover, the matrix associated with the linear transformation \(\tau_{2}\) is of the form \(T_{2}=B^{-1}PB\), where \(B\) is the change-of-basis matrix from the orthonormal basis associated with the encoding \(\mathcal{E}\) to the canonical basis of \(\mathbb{R}^{26}\) (in particular, \(B\) is orthogonal and \(B^{-1}=B^{T}\)) and \(P\) is a permutation matrix that switches the last two entries of a vector, i.e., using block-matrix notation,

\[P=\begin{bmatrix}I&0\\ \hline 0&0&1\\ &1&0\end{bmatrix},\quad I\in\mathbb{R}^{24\times 24}.\]

Hence, \(T_{2}\) is orthogonal and symmetric, and therefore fits the framework of the Theorem III.1.

On the other hand, as discussed in SSIII-A, every GNN of the form (2) is a model of the form (4). Thus, Theorem III.1 yields \(L(D,\mathsf{xy})\stackrel{{ d}}{{=}}L(\tau(D),\mathsf{(xy)})\), for all letters \(\mathsf{x},\mathsf{y}\in\mathcal{A}\). In particular, \(L(D,\mathsf{x}\mathsf{Y})\stackrel{{ d}}{{=}}L(\tau(D),\mathsf{ x}\mathsf{Z})\), which corresponds to condition (ii) of Theorem II.2. Recalling that \(\tau(D)=D\), also condition (i) holds. Hence, we can apply Theorem II.2 and conclude the proof. 

### _What GNNs can learn: identity effects on dicyclic graphs_

We now analyze the expressivity of GNNs to learn identity effects related to the _topology_ of the graphs in the dataset. This novel setting requires to design _ex novo_ the formulation of our problem. In fact, we are not focusing on the feature matrix \(X_{G}\) of a graph anymore, but on its adjacency matrix \(A\), which contains all the topological information. Here we focus on a particular class of graphs, which we call _dicyclic graphs_. A dicyclic graph is a graph composed by an \(m\)-cycle and an \(n\)-cycle, linked by a single edge. Since a dicyclic graph is uniquely determined by the length of the two cycles, we can identify it with the equivalence class \([m,n]\) over the set of pairs \((a,b)\), \(a,b\in\mathbb{N}\), defined as \([m,n]:=\{(m,n),(n,m)\}\). A dicyclic graph \([m,n]\) is _symmetric_ if \(m=n\) and _asymmetric_ otherwise.

In this section we provide an analysis of the expressive power of GNNs when learning identity effects on dicyclic graphs (i.e., classifying whether a dicyclic graph is symmetric or not). We start by proving a lemma that shows how information propagates through the nodes of a cycle, during the 1-WL test iterations, when one of the nodes has a different initial color with respect to all the other nodes.

**Lemma III.4** (1-WL test on \(m\)-cycles).: _Consider an \(m\)-cycle in which the vertices are numbered from \(0\) to \(m-1\) clockwise, an initial coloring \(c^{(0)}=[0,1,\ldots,1]^{T}\in\mathbb{N}^{m}\) (vector indexing begins from 0, and the vector is meant to be circular, i.e., \(c^{(0)}(m)=c^{(0)}(0)\)), and define the function \(\operatorname{HASH}\) as_

\[\begin{cases}\operatorname{HASH}(0,\{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
Termination of the 1-WL testAt iteration \(\lfloor\frac{m}{2}\rfloor-1\) we have

\[\begin{cases}c^{(\lfloor\frac{m}{2}\rfloor-1)}(i)=i&\text{if}\ \ 0\leq i\leq \lfloor\frac{m}{2}\rfloor-1\\ c^{(\lfloor\frac{m}{2}\rfloor-1)}(i)=\lfloor\frac{m}{2}\rfloor&\text{if}\ \ i= \lfloor\frac{m}{2}\rfloor\text{ or }i=\lceil\frac{m}{2}\rceil\.\\ \\ c^{(\lfloor\frac{m}{2}\rfloor-1)}(i)=m-i&\text{if}\ \ \lceil\frac{m}{2}\rceil+1\leq i<m \end{cases}\]

This concludes the proof. 

A graphical representation of Lemma III.4 can be found in Figure 2. This lemma represents the core of next theorem's proof, which establishes the ability of the 1-WL test to classify dicyclic graphs with identical cycles. Intuitively, if we have a dicyclic graph where node colors are uniformly initialized, one step of 1-WL test yields a coloring depending entirely on the number of neighbours for each node. In a dicyclic graph \([m,n]\) we always have \(m+n-2\) nodes of degree two and \(2\) nodes of degree three, so \(c^{(1)}(i)=1\) for all 2-degree nodes \(i\), and \(c^{(1)}(j)=0\) for the two 3-degree nodes \(j\). Hence, each cycle of the dicyclic graph satisfies the initial coloring hypothesis of Lemma III.4.

**Theorem III.5** (1-WL test on dicyclic graphs).: _The 1-WL test gives the same color to the 3-degree nodes of a uniformly colored dicyclic graph \([m,n]\) (i.e., \(c^{(0)}=0\in\mathbb{N}^{m+n}\)) if and only if \(m=n\). Therefore, the 1-WL test can classify symmetric dicyclic graphs._

Proof.: After one iteration on the 1-WL test, regardless of the symmetry of the dicyclic graph, we obtain a coloring in which only 3-degree nodes have a different color, whose value we set to 0. We can therefore split the coloring vector \(c^{(1)}\in\mathbb{N}^{m+n}\) in two subvectors, namely, \(c^{(1)}=[(c^{(1)}_{1})^{T},(c^{(1)}_{2})^{T}]^{T}\) corresponding to each cycle, respectively, and where \(c^{(1)}_{1}(0)\) and \(c^{(1)}_{2}(0)\) correspond to the 3-degree nodes. We treat the symmetric and the asymmetric cases separately.

The symmetric caseWe let \(c^{(0)}_{1}=c^{(0)}_{2}=c^{(0)}_{0}\), with \(c^{(0)}_{0}=[0,1,\dots,1]\). In this case, we run the 1-WL test in parallel on both vectors \(c^{(t)}_{1}\) and \(c^{(t)}_{2}\), where the HASH function in Lemma III.4 is extended on the 3-degree nodes as \(\text{HASH}(0,\{\!\!\{0,j,k\}\!\!\})=0\). Therefore, for each \(t\geq 0\),

\[c^{(t+1)}_{0}(0)=\text{HASH}(c^{(t)}_{0}(0),\{\!\!\{c^{(t)}_{0}(0),c^{(t)}_{0 }(1),c^{(t)}_{0}(m-1)\}\!\!\})=0.\]

Thanks to Lemma III.4 we obtain \(c^{(\lfloor\frac{m}{2}\rfloor)}_{1}=c^{(\lfloor\frac{m}{2}\rfloor)}_{2}\), which is a stable coloring for the whole graph, as the color partition is not refined anymore.

The asymmetric caseWithout loss of generality, we can assume \(m=\text{length}(c^{(t)}_{1})\neq\text{length}(c^{(t)}_{2})=m+h\) for some \(h>0\). We also assume for now that \(m\) is odd (the case \(m\) even will be briefly discussed later). We extend the HASH function from Lemma III.4 to colors \(j,k>\lfloor\frac{m}{2}\rfloor\). For \(j>\lfloor\frac{m}{2}\rfloor\) or \(k>\lfloor\frac{m}{2}\rfloor\) we define

\[\begin{cases}\text{HASH}(0,\{\!\!\{j,k\}\!\!\})=\infty\\ \text{HASH}(i,\{\!\!\{j,k\}\!\!\})=\lfloor\frac{m}{2}\rfloor+i&\text{if}\ j \neq k,\ i\leq\lfloor\frac{m}{2}\rfloor\\ \text{HASH}(i,\{\!\!\{j,k\}\!\!\})=\lfloor\frac{m}{2}\rfloor+i+1&\text{if}\ j=k,\ i\leq\lfloor\frac{m}{2}\rfloor\end{cases}.\]

Running in parallel the 1-WL test on the two cycles, computing the coloring vectors \(c^{(\lfloor\frac{m}{2}\rfloor+1)}_{1}\) and \(c^{(\lfloor\frac{m}{2}\rfloor+1)}_{2}\) up to iteration \(\lfloor\frac{m}{2}\rfloor+1\), for \(i=\lfloor\frac{m}{2}\rfloor+1\) we have \(c_{2}(i)=\lfloor\frac{m}{2}\rfloor+1\). Therefore, given the extension of the HASH function just provided, this new color starts to backpropagate on the indices \(i<\lfloor\frac{m}{2}\rfloor+1\), \(i>m-h-\lfloor\frac{m}{2}\rfloor-1\) until it reaches the index \(0\). As a consequence, it exists an iteration index \(T\) such that \(c^{(T)}_{2}(0)=\text{HASH}(0,\{\!\!\{j,k^{*}\!\!\}\!\})\) with \(k^{*}>\lfloor\frac{m}{2}\rfloor\) and, finally, \(c^{(T)}_{2}(0)=\infty\), giving \(c^{(T)}_{1}(0)\neq c^{(T)}_{2}(0)\), as claimed.

The case in which \(m\) is even works analogously, but we have to modify the HASH function in a different way to preserve injectivity. In particular, for \(j,k\leq m/2\), we define

\[\begin{cases}\text{HASH}(i,\{\!\!\{j,k\}\!\!\})=\frac{m}{2}&\text{if}\ j=k,i= \frac{m}{2}\\ \text{HASH}(i,\{\!\!\{j,k\}\!\!\})=\frac{m}{2}+1&\text{if}\ j\neq k,i=\frac{m}{2 }\end{cases}.\]

This concludes the proof. 

Theorem III.5 establishes in a deterministic way the power of the 1-WL test in terms of distinguishing between symmetric and asymmetric dicyclic graphs, given a sufficient number of iterations directly linked with the maximum cycle length in the considered domain. Examples of 1-WL stable colorings on dicyclic graphs are presented in Figure 3.

Employing well-known results in the literature concerning the expressive power of GNNs (see [10, 20] and in particular Theorem II.1), we can prove the main result of this subsection on the classification power of GNNs on the domain of dicyclic graphs.

Fig. 2: Graphical illustration of Lemma III.4: a 6-cycle reaches a stable coloring in \(\lfloor\frac{6}{2}\rfloor=3\) steps with \(\lfloor\frac{6}{2}\rfloor+1=4\) colors. Numbers are used to identify nodes.
**Corollary III.6** (GNNs can classify symmetric dicyclic graphs).: _There exist a GNN of the form (2) and a READOUT function able to classify symmetric dicyclic graphs._

Proof.: Let \([m,n]\) be a dicyclic graph and \(c^{(T)}\) be the stable coloring of \([m,n]\) produced by the 1-WL test with initial uniform coloring. By Theorem III.5 the graph can be correctly classified by the 1-WL test, i.e., by its stable coloring. Using Theorem II.1, a GNN \(f_{\Theta}\) exists such that \(f_{\Theta}\) can learn the stable coloring for each input graph for each iteration step \(t\). Let \(c^{(T)}\) be the stable coloring computed by a GNN for a dicyclic graph \([m,n]\). Let \((u,v)\) be the 3-degree nodes of the dicyclic graph. Then, the READOUT can be modeled as

\[\text{READOUT}(c^{(T)})=\begin{cases}1&\text{if }c^{(T)}(u)=c^{(T)}(v)\\ 0&\text{otherwise}\end{cases}.\]

With such a READOUT, the GNN assigns the correct rating to the dicyclic graph (i.e., 1 if the graph is symmetric, 0 otherwise). 

**Remark III.7** (The gap between theory and practice in Corollary III.6).: Corollary III.6 shows that GNNs are powerful enough to match the 1-WL test's expressive power for the classification of symmetric dicyclic graphs (as established by Theorem III.5). However, it is worth underlining that this result only proves the _existence_ of a GNN model able to perform this task. In contrast to the results presented in SSIII-A, this corollary does not mention any training procedure. Nevertheless, the numerical experiments in SSIV-C show that GNNs able to classify symmetric dicyclic graphs _can_ be trained in practice, albeit achieving generalization outside the training set is not straightforward and depends on the GNN architecture.

## IV Numerical results

This section presents the results of experimental tasks designed to validate our theorems. We analyze the consistency between theoretical and numerical findings, highlighting the significance of specific hypotheses, and addressing potential limitations of the theoretical results.

### _Experimental Setup_

We take in account two different models for our analysis:

* The Global Additive Pooling GNN (_Gconv-glob_) applies a sum pooling at the end of the message-passing convolutional layers [7]. In the case of the 2-letter words setting, the resulting vector \(h_{\text{glob}}\in\mathbb{R}^{h}\) undergoes processing by a linear layer, while in the dicyclic graphs setting, an MLP is employed. A sigmoid activation function is applied at the end.
* The Difference GNN (_Gconv-diff_), takes the difference between the hidden states of the two nodes in the graph (in the 2-letter words setting) or the difference between the hidden states of the 3-degree nodes (in the dicyclic graphs setting) after the message-passing convolutional layers. The resulting vector \(h_{\text{diff}}\in\mathbb{R}^{h}\) is then fed into a final linear layer, followed by the application of a sigmoid activation function.

The choice of the last READOUT part is driven by empirical observation on their effectiveness on the two different tasks.

Training is performed on an Intel(R) Core(TM) i7-9800X processor running at 3.80GHz using 31GB of RAM along with a GeForce GTX 1080 Ti GPU unit. The Python code is available at [https://github.com/AleDinve/gmn_identity_effects.git](https://github.com/AleDinve/gmn_identity_effects.git).

### _Case study #1: two-letter words_

#### Iv-B1 Task and datasets

To validate Theorem III.1, we consider a classification task using the two-letter word identity effect problem described in SSIII-A1, following the experimental setup presented in [41]. In accordance with the setting of SSIII-A1, each word is represented as a graph consisting of two nodes connected by a single unweighted and undirected edge (see Figure 1). Each node is assigned a node feature \(x\in\mathbb{R}^{26}\), corresponding to a letter's encoding.

The training set \(D_{\text{train}}\) includes all two-letter words composed of any English alphabet letters except Y and Z. The test set \(D_{\text{test}}\) is a set of two-letter words where at least one of the letters is chosen from \(\mathsf{Y},\mathsf{Z}\). Specifically, we consider \(D_{\text{test}}=\{\mathsf{Y}\mathsf{Y},\mathsf{Z}\mathsf{Z},\mathsf{Y}\mathsf{ Z},\mathsf{Z}\mathsf{Y},\mathsf{S}\mathsf{Z}\}\).

#### Iv-B2 Vertex feature encodings

In our experiments, we consider four different encodings of the English alphabet, following the framework outlined in SSIII-A. Each encoding consists of a set of vectors drawn from \(\mathbb{R}^{26}\).

* _One-hot encoding_: This encoding assigns a vector from the canonical basis to each letter: A is encoded as \(e_{1}\), B as \(e_{2}\),..., and Z as \(e_{26}\).
* _Haar encoding_: This encoding assigns to each letter the columns of a \(26\times 26\) orthogonal matrix drawn from the orthogonal group \(\text{O}(26)\) using the Haar distribution [47].

Fig. 3: Stable 1-WL coloring for different types of dicyclic graphs: as stated in Theorem III.5, 3-degree nodes have the same color in symmetric dicyclic graphs, and different color in the asymmetric ones.
* _Distributed encoding_: This encoding assigns a random combination of 26 bits to each letter. In this binary encoding, only \(j\) bits are set to 1, while the remaining \(26-j\) bits are set to 0. In our experiments, we set \(j=6\).
* _Gaussian encoding_: This encoding assigns samples from the multivariate normal distribution \(\mathcal{N}(0,I)\), where \(0\in\mathbb{R}^{n}\) and \(I\in\mathbb{R}^{n\times n}\). In our experiments, we set \(n=16\).

Observe that only the one-hot and the Haar encodings are orthogonal (see SSIII-A1) and hence satisfy the assumption of Theorem III.3. On the other hand, the distributed and the Gaussian encodings do not fall within the setting of Theorem III.3.

We run 40 trials for each model (i.e., Gconv-glob or Gconv-diff, defined in SSIV-A) with \(l\) layers (ranging from 1 to 3). In each trial, a different training set is randomly generated. The models are trained for 5000 epochs using the Adam optimizer with a learning rate of \(\lambda=0.0025\), while minimizing the binary cross-entropy loss. The hidden state dimension is set to \(d=64\), and Rectified Linear Units (ReLUs) are used as activation functions.

The numerical results are shown in Figures 4-5, where we propose two different types of plots:

* On the top row, we compare the ratings obtained using the four adopted encodings. The first two words, AA and a randomly generated word with nonidentical letters, denoted xy, are selected from the training set to showcase the training accuracy. The remaining words are taken from \(D_{\text{test}}\), allowing assessment of the generalization capabilities of the encoding scheme outside the training test. The bars represent the mean across trials, while the segments at the center of each bar represent the standard deviation.
* On the bottom row, we show loss functions with respect to the test set over the training epochs for each encoding. The lines represent the average, while the shaded areas represents the standard deviation.

Our numerical findings indicate that the rating impossibility theorem holds true for the one-hot encoding and the Haar encoding. However, notable differences in behavior emerge for the other two encodings. The 6-bit distributed encoding exhibits superior performance across all experiments, demonstrating higher rating accuracy and better loss convergence. The Gaussian encoding yields slightly inferior results, yet still showcases some generalization capability. It is important to note that despite variations in experimental settings such as architecture and optimizer (specifically, the use of ReLU activations and the Adam optimizer), the divergent behavior among the considered encodings remains consistent. This highlights the critical role of the transformation matrix \(T_{2}\) within the hypothesis outlined in Theorem III.3.

### _Case study #2: dicyclic graphs_

We now consider the problem of classifying symmetric dicyclic graphs, introduced in SSIII-B. In Corollary III.6 we proved the existence of GNNs able to classify symmetric dicyclic graphs. In this section, we assess whether such GNNs can be computed via training (see also Remark III.7). With this aim, we consider two experimental settings based on different choices of training and test set: an _extraction task_ and an _extrapolation task_, summarized in Figures 8 and 10, respectively, and described in detail below. Each task involves running 25 trials for the Gconv-glob and Gconv-diff models

Fig. 4: Numerical results for the rating task on the two-letter words dataset using Gconv-glob with \(l=1,2,3\) layers. The distributed and Gaussian encodings, which deviate from the framework outlined in Theorem III.1, exhibit superior performance compared to the other encodings. The other encodings makes the transformation matrix orthogonal and symmetric, being themselves orthogonal encodings.
defined in SSIV-A. The number of layers in each model is determined based on the specific task.

The models are trained over 5000 epochs using a learning rate of \(\lambda=0.001\). We employ the Adam optimizer, minimizing the binary crossentropy, and incorporate the AMSGrad fixer [48] to enhance training stability due to the large number of layers. The hidden state dimension is set to \(d=100\), and ReLU activation functions are utilized.

The results presented in Figures 6, 8, and 10 should be interpreted as follows: each circle represents a dicyclic graph \([m,n]\); the color of the circle corresponds to the rating, while the circle's radius represents the standard deviation.

#### Iv-A1 1-WL test performance

In Theorem III.5 we showed that the 1-WL test can classify symmetric dicyclic graphs. This holds true regardless of the length of the longer cycle, provided that a sufficient number of iterations is performed. The results in Figure 6 show that the 1-WL test achieves indeed perfect classification accuracy in \(n_{\max}\) iterations, where \(n_{\max}\) is the maximum length of a cycle in the dataset, in accordance with Theorem III.5.

#### Iv-A2 Extraction task

In this task, we evaluate the capability of GNNs to generalize to unseen data, specifically when the minimum length of cycles in the test dataset is smaller than the maximum length of those in the training dataset. More specifically, the training set \(D_{\text{train}}\) consists of pairs \([m,n]\) where \(3\leq m,n\leq n_{\max}\) and \(m,n\neq k\) with \(3\leq k\leq n_{\max}\), while the test set \(D_{\text{test}}\) comprises pairs \([k,a]\) with \(3\leq a\leq n_{\max}\). Figure 7 illustrates this setting.

In our experiments, we set \(n_{\max}=8\) and consider \(k\) values of 7, 6, and 5. The number of GNN layers is \(l=n_{\max}\). The numerical results are presented in Figure 8. We observe that the Gconv-diff model achieves perfect performance in our experiments (standard deviation values are not reported because they are too low), showing consistence with the theoretical setting. On the other hand, the Gconv-glob model demonstrates good, but not perfect, performance on the test set. A critical point in our numerical examples seems to be \(k=5\), which falls in the middle range between the minimum

Fig. 5: Numerical results for the rating task on the two-letter words dataset using Gconv-diff with \(l=1,2,3\) layers. The same observations to those in Figure 4 can be made here as well.

Fig. 6: Perfect classification of symmetric dicyclic graphs by \(n_{\max}\) iterations of the 1-WL test.

Fig. 7: Graphical illustration of the extraction task. In this example, \(n_{\max}=6\) and \(k=5\).
and maximum cycle lengths in the training set (3 and 8, respectively). This particular value is closer to the minimum length, indicating a relatively unbalanced scenario.

Overall, the different performance of Gconv-diff and Gconv-glob on the extraction task shows that, despite the theoretical existence result proved in Corollary III.6, the choice of architecture is crucial for achieving successful generalization.

#### Iv-B3 Extrapolation task

In this task, we assess GNNs' ability to generalize to unseen data with cycle lengths exceeding the maximum length in the training dataset. Specifically, the training set \(D_{\text{train}}\) comprises pairs \([m,n]\) where \(3\leq m,n\leq n_{\max}\), while the test set \(D_{\text{test}}\) consists of pairs \([n_{\max}+k,n^{\prime}]\) with \(0<k\leq g\) and \(3\leq n^{\prime}\leq n_{\max}+g\). Figure 9 illustrates the extrapolation task.

In our experiments, we set \(n_{\max}=8\) and consider values of \(g\) as 1, 2, and 3. The number of GNN layers is \(l=n_{\max}+g\). Numerical results are presented in Figure 10. In the extraction task, both models achieved perfect training accuracy. Conversely, in the extrapolation task, the Gconv-glob model struggles to classify the training set accurately, especially when the number of layers is equal to 9. This behavior may be attributed to the homogeneous nature of sum pooling at the end of the message passing, as it does not take into account the role of 3-degree nodes (which play a key role in our theory, as illustrated by Theorem III.5 and Corollary III.6).

On the other hand, the Gconv-diff model consistently achieves perfect training accuracy over the training set and achieves perfect generalization for \(g=1\), showing once again the importance of architecture choice in practice. However, when \(g\geq 2\) there is a noticeable region of misclassification for pairs \([m,n]\) where \(m,n\geq n_{\max}\). This behavior could be explained by the limited capacity of the hidden states, but the optimization process might also play a significant role. Moreover, for \(g\geq 2\) the numerical results of the extrapolation task resemble the rating impossibility phenomenon observed in the two-letter words framework. However, it is important to note that, at least for the Gconv-diff model, we observe significantly different ratings between graphs \([m,n_{\max}+g]\) where \(m<n_{\max}\) and graphs \([n_{\max}+i,n_{\max}+j]\) with \(i,j>0\). In contrast, in the two-letter words framework ratings typically do not exhibit such a consistent and distinguishable pattern.

Fig. 8: Extraction task performed by different GNN models, namely Gconv-glob (left) and Gconv-diff (right). We set \(n_{\max}=8\), \(l=8\) and, from top to bottom, \(k=7,6,5\).

Fig. 10: Extrapolation task performed by different GNN models, namely Gconv-glob (left) and Gconv-diff (right). We set \(n_{\max}=8\), \(l=8\) and, from top to bottom, \((l,g)=(9,1),(10,2),(11,3)\).

Fig. 9: Graphical illustration of the extrapolation task. In this example, \(n_{\max}=5\) and \(g=2\).
## V Conclusions

This work extensively investigates the generalization capabilities of GNNs when learning identity effects through a combination of theoretical and experimental analysis. From the theoretical perspective, in Theorem III.3 we established that GNNs, under mild assumptions, cannot learn identity effects when orthogonal encodings are used in a specific two-letter word classification task. On the positive side, in Corollary III.6 we showed the existence of GNNs able to successfully learn identity effects on dicyclic graphs, thanks to the expressive power of the Weisfeiler-Lehman test (see Theorem III.5). The experimental results strongly support these theoretical findings and provide valuable insights into the problem. In the case of two-letter words, our experiments highlight the key influence of encoding orthogonality on misclassification behavior. Our experiments on dicyclic graphs demonstrate the importance of architecture choice in order to achieve generalization.

Several directions of future research naturally stem from our work. First, while Theorem III.3 identifies sufficient conditions for rating impossibility, it is not known whether (any of) these conditions are also necessary. Moreover, numerical experiments on two-letter words show that generalization outside the training set is possible when using nonorthogonal encodings; justifying this phenomenon from a theoretical perspective is an open problem. On the other hand, our numerical experiments on dicyclic graphs show that achieving generalization depends on choice of the architecture; this suggests that rating impossibility theorems might hold under suitable conditions on the GNN architecture in that setting. Another interesting open problem is the evaluation of GNNs' expressive power on more complex graph domains. In particular, conducting extensive experiments on molecule analyses mentioned in SS1, which naturally exhibit intricate structures, could provide valuable insights into modern chemistry and drug discovery applications.

## Acknowledgments

GAD is partially supported by the Gruppo Nazionale per il Calcolo Scientifico (GNCS) of the Istituto Nazionale di Alta Matematica (INdAM). SB acknowledges the support of the Natural Sciences and Engineering Research Council of Canada of Canada (NSERC) through grant RGPIN-2020-06766 and the Fonds de Recherche du Quebec Nature et Technologies (FRQNT) through grant 313276. MR acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) through grant 263344. The authors are thankful to Aaron Berk for providing feedback on a preliminary version of this manuscript and to Kara Hughes for fruitful discussions on applications to the molecule domain.
