Foundations of Graph Neural Networks
(A Logician’s View)

We begin the formal part with the basic definitions relevant to the notes.

Observe that, according to this definition, the graphs are simple and undirected, and the edges are not labelled with numbers or colours (i.e., types). These assumptions are in most cases just for simplicity (and are customary in ML), and many of the results we will discuss generalise to other graphs.

Overall, the objective of graph learning is to learn graph or node embeddings (which are partially or fully unknown). Next, we define such embeddings.

Typical examples of the output space are $\{yes,no\}$ (in which case we can call the embedding binary classification), a finite set of classes (multi-class classification), and real numbers (regression). A common example of a practical graph embedding learning task with binary classification is predicting whether a molecule, represented as a graph, possesses a certain property, such as toxicity.

An example of a node embedding learning task is predicting the relevance of a paper in a citation network (for a particular user) – that is, to assign a number in $[0,1]$ for every paper. In these notes, we mostly focus on node embeddings, but our results can often be adapted to whole graphs.

In passing, it is worth noting that, in graph learning literature, graphs are often represented as two matrices: the adjacency matrix of the graph structure and the labelling matrix that stacks the labels of the nodes. However, such a representation becomes dependent on the order of the nodes, which is not specified in the graphs and should therefore be fixed in some way. In this case, it is usually required for graph embeddings and node embeddings (which now take matrix representations as input instead of graphs themselves) to be invariant and equivariant, respectively – that is, be independent of the order of nodes in the representation.

An immediate question after these definitions is why standard deep neural networks and other traditional ML formalisms cannot be used for graph learning. To answer this, let us first recall that a (fully-connected feed-forward) neural network (NN) consists of multiple layers of so-called neurons, where each neuron in each layer is connected to each neuron in the next layer with an assigned (learnable) numeric weight. The number of neurons in each layer is called its dimension. Such an NN realises a function mapping vectors of real numbers of the first layer dimension to such vectors of last layer dimension by feeding the input vector to the input layer neurons and computing the value $\lambda (n)$ of each non-input neuron $n$ as $f({\sum }_{n^{\prime }}{w}_{n^{\prime }\to n}\cdot \lambda (n^{\prime }))$, where $n^{\prime }$ ranges over the neurons of the previous layer, $w_{n^{\prime }\to n}$ is the weight assigned to the connection from $n^{\prime }$ to $n$, and $f$ is a non-linear function, such as sigmoid or ReLU. This architecture can be easily adapted for non-numeric outputs, such as classification, by applying an additional fixed function with appropriate range, for example, softmax, to the last-layer vector. Usually, the connection weights are obtained through (supervised) training, which optimises them via backpropagation to minimise the loss function – that is, the difference between the NN’s predictions and the ground-truth answers for known examples.

However, applying such (fully connected) NNs for graph learning faces several problems. The first one is scalability: when a layer has significantly many neurons, there can be prohibitively many weights. For example, for a rather reasonable $250\cdot 250$ grid graph (i.e., the graph with nodes $(i,j)$, for $i,j\in \{1,\mathrm{\dots },250\}$, and an edge between $(i,j)$ and $(i+1,j)$, and between $(i,j)$ and $(i,j+1)$ for all admissible $i,j$) with dimension 1 as input and just $500$ neurons per intermediate layer we already require at $250\cdot 250\cdot 500=31,250,000$ weights between the first two layers (assuming that the graph is represented as a vector by concatenating its rows). The second problem is that the inputs to an NN are always totally ordered, and so the same graph may be represented as an NN’s input vector in many ways. As a result, NNs do not respect graph symmetries – that is, may give different answers for the same node, depending on the graph’s representation; teaching an NN these symmetries often requires additional, sometimes prohibitive, training effort. The third, and more fundamental, problem is that each NN requires fixed-size input, whereas graph learning does not assume any restriction on the size of the input graph; in particular, a model trained on small graphs should be applicable to graphs of arbitrarily large size. While one could impose a hard bound on graph sizes, this is, of course, not a principled solution.

For grid graphs, a possible solution is to use Convolutional Neural Networks (CNNs) – a well-established neural approach widely used in, for example, image processing. The key idea behind CNNs is that all layers maintain the same number of neurons, and each neuron has connections only from a small window (i.e., neighbourhood) of neurons in the previous layer, centred on the corresponding neuron in that layer. Moreover, the weights are now shared across the windows – that is, are determined by the relative positions of the connected neurons in the grid (and the layer number) rather than by absolute positions. This drastically reduces the number of weights and allows CNNs to handle grids of arbitrary size. Thus, in essence, CNNs are designed to recognise local patterns.

As we will see next, GNNs generalise the idea of CNNs to arbitrary graphs.

Overall, GNNs are a family of ML architectures that leverage the structure of graphs to effectively learn graph and node embeddings. Following Gilmer et al. [7], who first noticed that many architectures for graph learning have a common pattern, and Barcelo et al. [3], we next give a formalisation of GNNs in a general abstract form, which serves as an umbrella for many GNN architectures. We begin with the syntax of GNNs for node embeddings.

In what follows, for brevity, in the case of $𝕐={ℝ}^{d_L}$ and $d_L=1$ (e.g., regression) we can take $\mathrm{OUT}$ to be identity and omit it. We now proceed with the semantics.

Thus, node-level AC-GNNs realise node embeddings. Since we focus on node embeddings in these notes, we will usually omit “node-level” when referring to AC-GNNs. For completeness, however, we also briefly describe how to adapt AC-GNNs to the graph level. In particular, the syntax of graph-level AC-GNNs is the same as in Definition 4 except it includes the output function $\mathrm{READOUT}:{\mathbb{N}}^{{ℝ}^{d_L}}\to 𝕐$ instead of $\mathrm{OUT}$; moreover, the semantics is the same as in Definition 5 except that there is one result for the entire graph, computed as $\mathrm{READOUT}(\{\{{𝒙}_v^{(L)}\mid v\in V\}\})$. Thus, graph-level AC-GNNs realise graph embeddings.

Our definition of the AC-GNN family of architectures is abstract; in fact, it does not have anything “neural” in it by itself. However, it covers most of concrete GNN architectures used in practice in graph learning, and which therefore have trainable weights. In particular, in these GNNs, the functions ${\mathrm{AGG}}^{(\mathrm{\ell })}$ and ${\mathrm{COMB}}^{(\mathrm{\ell })}$ rely on matrices and vectors of numbers, as well as on some non-linearity. There are many such architectures, and even an overview of them is beyond the scope of these notes. Instead, we limit ourselves to basic examples.

At this point, it is worth noticing a common abuse of terminology: when referring to “a GNN” (“AC-GNN”, “Sum-Plus GNN with sigmoid”, etc.), we may mean either a concrete instance specified by given aggregation, combination, etc. functions, or a family of such instances (also known as a GNN architecture), which is defined by restricting the functions to certain classes without specifying concrete members of these classes. For example, a sum-plus GNN with all matrix and vector weights given (e.g., trained) is an instance, but an untrained sum-plus GNN, where only the number of layers, the dimensions, and the structure of formula (2) are specified, is an architecture. Usually, this abuse does not cause any confusion, but we will specify what we mean if there is any risk of ambiguity.

Note, however, that many recent advanced GNN architectures do not fall into the AC-GNN framework. In fact, most such architectures have been developed as attempts to address the expressivity limitations of AC-GNNs, many of which were identified in the papers I will refer to below. Among these limitations is, for example, the fact that the node embedding “the node is reachable from a node with label $1$” is not expressible by any AC-GNN, as each AC-GNN has a fixed number of layers. Recurrent GNNs [13] are, in principle, capable of learning (i.e., expressing) such reachability. Another example of a limitation is that the node embedding “the node is on a cycle of length 5” is also not expressible by any AC-GNN. However, 5-WL GNNs [11] can, in principle, detect a 5-cycle. Finally, the node embedding “the node is such that there is another node with label 1 somewhere in the graph” is also not expressible by any AC-GNN, but GNNs with global readouts [3] can look globally, even in other connected components, in the input graph. In these notes, we primarily focus on AC-GNNs and briefly discuss more powerful architectures at the end.

So, we intuitively see that different GNN architectures (within or outside the AC-GNN framework) can do some things and cannot do others. However, before studying this issue in a principled way, we need to understand what this formally means. Based on the state of the art, we next consider several related notions for GNNs, each sometimes called expressive power: distinguishing (or separating) power (Section 3), (uniform) expressive power (Section 4), non-uniform expressive power (Section 5), and (non-uniform) approximation power (also Section 5). Understanding expressive power (for different notions of expressibility) may reveal, for example, the following: which information in graphs is used by a given GNN-based embedding method, which embeddings could – in principle – be learned by this method, and which more powerful methods may be needed for the application at hand. However, before proceeding to our first notion, we emphasise that “weaker expressivity” (of any kind) does not mean “worse,” since it just presupposes more a priori knowledge, which is embedded in the GNN architecture and hence does not need to be re-learned from examples.

Before we move to the definition, we briefly discuss the role of the test in CS. First, the WL test [19] is a classical formalism, so it is a useful reference point for distinguishability. For example, it is well-known that, on the graph level, it has the same distinguishing power as FOL with two variables and counting (C²), and its node level version – that is, the stable colouring, which is relevant to Theorem 9, – as graded modal logic (we will come back to this logic in Section 4.2). However, the main property of this test is that it is a complete yet not sound test for isomorphism between two graphs:

• $\mathrm{■}$

  if it rejects, then the graphs are not isomorphic, but

• $\mathrm{■}$

  if it accepts, then they may be isomorphic or not.

This test is useful, because, on the one hand, the answer “accept” for non-isomorphic graphs is possible for only special, practically rare cases, and, on the other hand, the complexity of checking isomorphism of two graphs is likely intractable (to be more precise, this is a big open problem in CS: neither polynomial algorithm nor NP-hardness proof is known).

As we will see, the WL test works with graphs where nodes are assigned with colours, which is, in principle, different from the graphs with numeric labellings as in Definition 1. However, this mismatch is not essential for us: in this section, we can assume that each numeric vector has a unique corresponding colour.

Note that the colouring always stabilises, as each iteration refines the colouring of the previous one. Figure 1 depicts two examples of the WL test applied to pairs of graphs (where the nodes in the input graphs are all of the same colour, which is just the property of these examples, but not required in the definition). In Figure 1(a), the stable colourings for the two graphs are different and so the test rejects, while in Figure 1(b) they are the same and so it accepts; however, in both cases the graphs are not isomorphic.

Thus, for every node $v$ in every graph $G$, the colour ${\mathrm{WL}}_v^{(\mathrm{\ell })}$ of $v$ after $\mathrm{\ell }$ iterations of the WL test is given by the following, where each ${\mathrm{INJ}}^{(\mathrm{\ell })}$ is an injective function mapping a colour and a multiset of colours to another colour:

• $\mathrm{■}$

  ${\mathrm{WL}}_v^{(0)}≔\lambda (v)$,

• $\mathrm{■}$

  ${\mathrm{WL}}_v^{(\mathrm{\ell })}≔{\mathrm{INJ}}^{(\mathrm{\ell })}({\mathrm{WL}}_v^{(\mathrm{\ell }-1)},\{\{{\mathrm{WL}}_u^{(\mathrm{\ell }-1)}\mid u\in {𝒩}_G(v)\}\})$.

As we know, an AC-GNN for each such node $v$ works as follows:

• $\mathrm{■}$

  ${𝒙}_v^{(0)}≔\lambda (v)$,

• $\mathrm{■}$

  ${𝒙}_v^{(\mathrm{\ell })}≔{\mathrm{COMB}}^{(\mathrm{\ell })}({𝒙}_v^{(\mathrm{\ell }-1)},{\mathrm{AGG}}^{(\mathrm{\ell })}(\{\{{𝒙}_u^{(\mathrm{\ell }-1)}\mid u\in {𝒩}_G(v)\}\}))$.

In other words, the WL test works exactly as an AC-GNN with injective aggregation and combination functions – that is, if WL assigns the same value to two nodes at iteration $\mathrm{\ell }$, then every AC-GNN also assigns the same value to these two nodes at layer $\mathrm{\ell }$. Moreover, we can say that the WL test realises a node embedding (or a class of embeddings, but all with the same distinguishing power) that assigns to each node the colour of the stable colouring. This correspondence is the essence of the proof of Theorem 9: the “WL simulates AC-GNNs” direction follows from the injectiveness, while for the “GNNs simulate WL” direction, we just need to choose the number of layers sufficiently large so that the WL stabilises on the two given graphs (recall that the definition of distinguishability allows for a separate GNN for every two graph-node pairs).

Let us now return to the fact that WL works as an AC-GNN with injective ${\mathrm{AGG}}^{(\mathrm{\ell })}$ and ${\mathrm{COMB}}^{(\mathrm{\ell })}$ functions. Such functions obviously exist. However, the immediate question is whether they can be truly “neural,” in a manner similar to our Sum-Plus GNNs. We can try

for some smart $f$ such that ${\sum }_{x\in X}f(x)$ is always injective. Unfortunately, it can be proven that such an $f$ that remains injective for arbitrarily large $X$ does not exist. Luckily, we can use the idea that enabled us to capture, in terms of distinguishability, the WL test with non-fixed number of iterations until stabilisation with AC-GNNs with fixed number of layers: we do not need $X$ to be arbitrarily large, but only as large as the number of nodes in the input graphs, thus ensuring that ${\mathrm{AGG}}^{(\mathrm{\ell })}$ is injective for these graphs (though not for all graphs). Such a function $f$ exists, and can be constructed using a straightforward generalisation of so-called deep sets [22]. The resulting GNN is essentially the so-called GIN¹¹1This stands for “Graph Isomorphism Network,” though this name is somewhat misleading, as their relevance to graph isomorphisms is debatable. [20].

We have started this section by stating that distinguishability is historically the first and most popular notion of expressibility for GNNs. However, is it really adequate for our understanding of what GNNs can and cannot do? We contend that this may not be the case. Indeed, we observe that

• $\mathrm{■}$

  the WL test realises a node embedding,

• $\mathrm{■}$

  each AC-GNN realises a node embedding, and

• $\mathrm{■}$

  AC-GNNs have the same distinguishing power as WL.

However, this does not guarantee that there is an AC-GNN that gives the same answer as the WL test for every node in every graph; in fact, this claim is obviously incorrect, since each AC-GNN has a fixed number of layers, whereas the WL test may require an arbitrarily large number of iterations, depending on the graph. To compare GNNs with other formalisms from this perspective we need a stronger, uniform notion of expressivity.

Bisumulation is a classical notion that appears in many areas of CS: verification, databases, modal logics, etc. Intuitively, a bisimulation is a relation between nodes of two graphs showing that they can match each other’s moves along edges step by step, so that the nodes are behaviourally indistinguishable. We next give a standard definition followed by a stronger version that takes the number of successors into account, which is more relevant for GNN expressibility.

Note that, in this definition, graphs $G_1$ and $G_2$ may be the same. Another observation is that a union of two usual or counting bisimulations is also such a bisimulation, so we can refer to the maximal bisimulation and the maximal counting bisimulation. Notably, the same-colouring relation of the result of the WL test is the maximal counting bisimulation.

As we may see, counting bisimulation (same as the usual one) may depend on nodes arbitrary far from each other in the graph. The following partial version (in fact, a family of versions) looks only up to a fixed depth, making it an approximation of the general notion.

For example, the same-colouring relation of the intermediate result of WL after $\mathrm{\ell }$ iterations is the maximal $\mathrm{\ell }$-partial counting bisimulation (which exists and is unique for the same reasons as in the general case).

Every type of bisimulation corresponds to a specific class of node embeddings.

In other words, no invariant embedding can separate bisimilar nodes. It is immediate that every $\mathrm{\ell }$-partial counting bisimulation invariant embedding is also $(\mathrm{\ell }+1)$-partial counting bisimulation invariant. Thus, we have the following:

• $\mathrm{■}$

  every AC-GNN with $L$ layers realises an $L$-partial counting bisimulation invariant embedding, since both care about only tree-unravellings (i.e., infinite trees rooted at the nodes whose branches correspond to all starting from the nodes);

• $\mathrm{■}$

  every $L$-partial counting bisimulation invariant embedding is realised by an AC-GNN with $L$ layers, since we can take injective aggregation and combination and make the final output function do all the job.

These observations give rise to the following semantic characterisation of uniform expressivity of AC-GNNs by Pflueger et al. [13].

Observe that even though $\mathrm{\ell }$ is not bounded in this theorem, “partial” is essential: there exist counting bisimulation invariant embeddings that are not realised by any AC-GNN. It is also not surprising that we may need an AC-GNN with functions of arbitrary complexity (e.g., not even computable) to express some (arbitrarily complex) invariant functions. Thus, there may not be any “real” GNN – that is, of form (2) or similar – that expresses many such functions. However, it is a good upper bound for all subclasses of AC-GNNs.

The semantic characterisation of Theorem 15 opens up a possibility to compare (uniform) expressibility of GNNs with those of logical formalisms. Logics are fundamental in many areas of computer science, and we have a very fine-grained landscape of logics in terms of expressive power. Therefore, it could be beneficial to leverage this knowledge for GNNs. Comparing GNNs and logics is very natural: they have a lot in common, since both realise functions with graph-like domains. For example,

• $\mathrm{■}$

  node-level GNNs realise node embeddings – that is, functions from graph-node pairs to output sets, and

• $\mathrm{■}$

  unary logic (e.g., FOL) formulas realise functions from structure-element pairs to $\{yes,no\}$.

A similar correspondence exists for graph-level GNNs and logical sentences.

However, even if both logic and GNNs work with similar objects, they are not exactly the same in their full generality. Therefore, we first need to find common ground – that is, unify the input and output spaces. For the input, we observe that every finite logical structure over the signature with one symmetric binary relation $E$ and several unary relations can be seen as a graph in the GNN sense: we just need to assign a dedicated position in the embedding vector to each unary predicate and use the 1-0 encoding of what holds in the structure; for example, if $A(a)$ and $C(a)$ hold in a structure for the signature with unary predicates $A,B,C$, then this can be seen as the label $(1,0,1)$ of node $a$ in the graph. For the output, we can restrict our attention to AC-GNNs with output space $\{yes,no\}$ – that is, to binary node classification. Note that real-life instances of AC-GNNs (Sum-Plus GNNs, GraphSAGE, GCNs, etc.) can be converted to such by, for example, a threshold as the output function. For the rest of the paper, we usually silently assume only such inputs (i.e., logical structures and, equivalently, GNN graphs with 1-0 labellings) and outputs (i.e., $\{yes,no\}$ as in binary classification), and we will say explicitly when it is not the case.

As we know from Theorem 15, AC-GNNs can express functions far beyond any usual logic. In fact, the families of node classifiers realised by common practical GNN architectures (GCNs, GraphSAGE, etc.) can also express a lot outside usual logics due to sophisticated aggregation over neighbours, and, especially, non-linearity (sigmoid, ReLU, etc.). There are results that identify (very expressive) logics capturing, in terms of expressive powers, some of such architectures; we will come back to them later, in Section 4.4. However, our first goal is to focus on all AC-GNN-based classifiers that are also expressible in FOL (with equality). In particular, our next result, which is due to Barcelo et al. [3], is the following.

We will sketch the proof of this result, where we will, for the backward direction, reduce to a neural subclass of AC-GNNs. Before this, however, we need to briefly introduce the graded modal logic (GML). In fact, it is a fragment of FOL with its own syntax (and terminology):

If the reader is more familiar with description logics, they may know this fragment as $𝒜ℒ𝒞𝒬$ with one role name $E$, also with its own syntax (and terminology):

However, as mentioned above, it is well known that we can see GML as the syntactic fragment of unary FOL specified by the following grammar, with the semantics inherited from FOL, and it will be convenient for us to assume this fragment when referring to GML:

In this syntax, we used counting quantifiers ${\exists }^{\ge n}$, which are syntactic sugar in FOL, since they are expressible via inequalities. This, however, comes with a cost of extra variables, and so FO², FOL with two variables, is strictly less expressive than C², FOL with two variables and counting quantifiers. As we can immediately see from the definition, GML is inside C² but not in FO².

We are ready to give an idea of the proof of Theorem 16. We start with the backward direction.

To prove this lemma, we construct an AC-GNN classifier instantiating equation (1) as

where $trReLU$ is the truncated ReLU defined as

while $𝑨,𝑪$ are matrices and $𝒃$ is a vector of weights such that each feature vector ${𝒙}_v^{(\mathrm{\ell })}$ of each node $v$ has one component ${𝒙}_v^{(\mathrm{\ell })}[{\phi }^{\prime }]\in \{0,1\}$ for each subformula ${\phi }^{\prime }$ of $\phi$ satisfying

• $\mathrm{■}$

  ${𝒙}_v^{(\mathrm{\ell })}[{\phi }_1\wedge {\phi }_2]=trReLU({𝒙}_v^{(\mathrm{\ell }-1)}[{\phi }_1]+{𝒙}_v^{(\mathrm{\ell }-1)}[{\phi }_2]-1)$,

• $\mathrm{■}$

  ${𝒙}_v^{(\mathrm{\ell })}[\neg {\phi }^{\prime }]=trReLU(-{𝒙}_v^{(\mathrm{\ell }-1)}[{\phi }^{\prime }]+1)$, and

• $\mathrm{■}$

  ${𝒙}_v^{(\mathrm{\ell })}[{\exists }^{\ge n}y.E(x,y)\wedge {\phi }^{\prime }(y)]=trReLU({\sum }_{u\in {𝒩}_G(v)}{𝒙}_u^{(\mathrm{\ell }-1)}[{\phi }^{\prime }]-(n-1))$.

As a result, for $L$ the structure depth of $\phi$, we have ${𝒙}_v^{(L)}[\phi ]=1$ if and only if $v\vDash \phi (x)$. Note that the matrices and the vector of the weights – that is, the aggregation and combination functions – are the same for all layers of the GNN. Such GNNs are sometimes called homogeneous.

The forward direction of Theorem 16 is claimed by the following lemma.

The proof relies on the following facts. First, we know from Theorem 15 that AC-GNN node classifiers are all partial counting bisimulation invariant. Then, as follows immediately from the definitions, every partial counting bisimulation invariant embedding is counting bisimulation invariant. Finally, Van Benthem-style (rather deep) theorem for GML by Otto [12] says that the counting bisimulation-invariant fragment of FOL is precisely GML (for both all and only finite structures, with only the latter relevant for us).

Theorem 16 does characterise a class of GNNs, but this class is not syntactically defined. Thus, an immediate question is whether we can find a (preferably nice-looking) syntactic subclass of AC-GNN classifiers that is equivalent in expressive power to a known logic. For GML (and plain modal logic) it may be hard, or even probably impossible for a reasonable notion of “nice-looking.” Our next result, which is due to Tena Cucala et al. [18], achieves this for a simple positive fragment of GML: unions of tree-shaped conjunctive queries (tree-UCQs).

As in the previous cases, we begin by defining the logic and the class of GNNs. A unary tree-shaped conjunctive query (tree-CQ) is an existentially quantified conjunction of unary and binary atoms with one free variable and with the shape of the directed tree with the variable as the root. More precisely, unary tree-CQs are a restriction of our FO fragment for GML that adheres to the following grammar:

then, a unary tree-UCQ is a disjunction (or union) of unary tree-CQs with the same free variable. In other words, unary tree-UCQs are the positive, counting-free fragment of GML.

To find a fragment of AC-GNNs that corresponds to unary tree-UCQs, we first observe that each unary tree-UCQ $Q$ is monotonic under homomorphisms – that is, is such that for every two graphs $G_1=(V_1,E_1,{\lambda }_1)$ and $G_2=(V_2,E_2,{\lambda }_2)$ with a function $h:V_1\to V_2$ for which

• $\mathrm{■}$

  $h(E_1)\subseteq E_2$ (i.e., the edges are preserved), and

• $\mathrm{■}$

  ${\lambda }_1(v)\le {\lambda }_2(h(v))$ for every $v\in V_1$ (i.e., the labellings of the nodes are also preserved with respect to the order)

we have that if $Q(v)$ is true, then $Q(h(v))$ is also true for every $v\in V_1$. However, as the following example shows, not all AC-GNNs are monotonic under homomorphisms.

Note that negative weights in matrices is not the only problem: sum can “count,” but UCQs cannot. Thus, our target fragment of AC-GNNs is also such.

It is not difficult to see that the node embedding of a monotonic max GNN is monotonic under homomorphisms. So, we have a hope that Theorem 19 indeed holds. In fact, we can prove the theorem by means of the following two lemmas.

This lemma can be proven using similar ideas as Lemma 17 for GML. The main differences are that we have to use max instead of sum, and we cannot use the truncated ReLU, since it is bounded, so we have to use the standard ReLU; however, this suffices, since we do not need to simulate negation and counting.

The proof of this lemma is based on three main ideas.

First, we can check whether a tree-CQ is sound for a monotonic max GNN – that is, whether, for all graphs and nodes, a positive answer of the tree-CQ implies a positive answer of the GNN. Indeed, we can run the GNN on the body of the tree-CQ (as the graph) and see the result for the free variable: monotonicity under homomorphisms ensures the result.

Second, we can restrict ourselves to tree-CQs of the depth at most the number of layers of the GNN, and there are only a finite number of non-equivalent such tree-CQs. Indeed, the bounded depth and tree shapes ensure this.

Third, for every graph $G$ and node $v$ for which the GNN outputs 1 for $(G,v)$, there is a sound tree-CQ that also outputs 1 for $(G,v)$. Indeed, we can run the GNN on $G$ and convert the “trace” to a tree-CQ.

So, the union of all (non-equivalent) tree-CQs sound for the GNN is what we need.

Monotonic max GNNs are a trainable neural architecture that shows reasonable performance on many practical tasks [18]. However, it is clearly a rather weak class, and it is a reasonable to ask whether the result of Theorem 19 can be extended to more expressive GNN classes and logics. It is also interesting even if we can guarantee only one direction, the one that some logic is more expressive than some class of GNNs. Indeed, a translation of GNNs to logic is useful, as the result can serve as an explanation, be used to reason together with other logical knowledge, etc. Next we will present three such results, but without the details of the (more complicated) proofs.

First, we consider monotonic sum GNN node classifiers, which are the same as monotonic max, except the aggregation function; in particular, they instantiate equation (1) as

where the other properties and requirements are the same as those for monotonic max GNNs in Definition 21.

For this class, we have the following theorem, which is also due to Tena Cucala et al. [18].

The logic in this theorem is defined in the same way as normal unary tree-UCQs, except that it relies on tree-CQs with sibling inequalities which are the same as tree-CQs except that they additionally allow inequalities between the tree siblings. This logic no longer has a nice grammar; it is not even subsumed by GML, since sibling inequalities give us more than just counting.

Note that Theorem 24 claims an analogue of only one direction of Theorem 19 – that is, that for every monotonic sum GNN node classifier there is a unary tree-UCQ with sibling inequalities realising the same embedding. It is not difficult to show that the other direction does not hold: there are some sibling inequalities not expressible by monotonic sum GNNs. However, even the claimed direction is a much more complicated result than for the max case. It is also much less intuitive, since the result of sum aggregation may grow bigger and bigger when we aggregate with more and more neighbours, and hence a fixed number of inequalities has to take care of all these arbitrarily large numbers. The key observation for the proof is that, due to monotonicity, if we pass a threshold that is sufficient for a positive overall answer, then we cannot drop below it by adding more neighbours.

Second, we have a look at a recent result similar to the one in Theorem 24, but for a much more expressive class of GNNs and logic. In particular, Benedikt et al. [4] considered sum-plus GNNs with eventually constant activation, which instantiate equation (1) as

where all the ${𝑨}^{(\mathrm{\ell })}$, ${𝑪}^{(\mathrm{\ell })}$, ${𝒃}^{(\mathrm{\ell })}$ are arbitrary matrices and vectors of appropriate dimensions, and the non-linear function $\sigma$ has the bounds

• $\mathrm{■}$

  $t_{\text{left}}$, such that $\sigma (x)=\sigma (t_{\text{left}})$ for each , and

• $\mathrm{■}$

  $t_{\text{right}}$, such that $\sigma (x)=\sigma (t_{\text{right}})$ for each $x>t_{\text{right}}$.

Note that this GNN class is indeed much more general than monotonic sum GNNs; however, the condition on $\sigma$ is not as mild as it may appear at first: truncated ReLU and many other functions satisfy it, but sigmoid and standard ReLU do not. Nonetheless, due to Benedikt et al. [4], we have a logic capturing this.

The definition of this logic is quite elaborate, and its full details are beyond the scope of these notes. We just note that it is an extension of GML with more powerful counting; in particular, instead of quantification of the form ${\exists }^{\ge n}y.(E(x,y)\wedge \phi (y))$, it has the following quantification, with the intuitive semantics:

where $n$, the $c_i$, and $d$ are constant natural numbers.

Finally, we mention GNNs with piecewise-linear activation [8]. This is a very general class of AC-GNNs where aggregation functions include all the common ones (sum, max, min, average, etc.) and the combination functions include all linear transformations of the two arguments with a piecewise-linear function on top (ReLU, truncated ReLU, etc.). We omit the details here, which are quite intricate. The same applies to the logic that captures these GNNs, GFO+C. Thus, we state the result (in fact, only a simplification of the result) without proof and refer interested readers to the paper by Grohe [8] for details. We just mention in the passing that GFO+C is within complexity class TC⁰ in the descriptive complexity sense, and the result implies that the same applies to the class of GNNs.

When comparing to logic, we focused on inputs with 1-0 node labellings (i.e., those that correspond to logical structures) and $\{yes,no\}$ outputs, which is clearly a significant restriction. In this section, we consider the case of arbitrary labellings in input graphs and $ℝ$ as the output space (i.e., regression). In this case, we can no longer compare to logic, but we can compare different architectures with each other. In particular, we have the following result by Rosenbluth et al. [15].

We again skip the proof, which in this case is of moderate difficulty, and refer the reader to the original paper [15].