What's a Graph Neural Network?

There is a lot of expository materials on Graph Neural Networks (GNNs) out there. I want here to focus on a short “mathematical” introduction to it, in the sense to quickly arrive to the concept of equivariance and invariance to permutations, and how GNNs are designed to deal with it, in order to discuss in a future post our work (??, ????) on the convergence of GNNs to some “continuous” limit when the number of nodes goes to infinity.

1 Graphs¶

Graphs are ubiquitous structure ¹ in mathematics and computer science. Graphs may represent several interactions, such as brain connectivity, computer graphic meshes, protein interactions or social networks. In its most elementary definition, a graph is a couple $G=(V,E)$ where $V$ is a finite set of vertices or nodes $V=\{v_1,\dots ,v_n\}$, and $E$ is a subset of the unordered pairs ${\mathcal{P}}_2(V)$ of $V$, called edges $E=\{e_{i_1{j}_1},\dots ,e_{i_m{j}_m}\}\subseteq {\mathcal{P}}_2(V)$.

Beyond this formalism, it is quite frequent to enumerate the vertices $1,\dots ,n$ and consider the associated adjacency matrix $A\in {\mathbb{R}}^{n\times n}$ defined by $A=(a_{i,j}{)}_{1\le i,j\le n}$ where $$a_{i,j}=\{\begin{array}{ll}1& \text{if }i\sim j,\\ 0& \text{otherwise.}\end{array}(1.1)$$ where $i\sim j$ means that there is an edge between $i$ and $j$. Note that $A$ is a real symmetric matrix.

The graph in Figure 1.1 can be represented by the adjacency matrix $$A=\left(\begin{array}{cccccc}0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 1& 0& 1\\ 1& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 0\end{array}\right).(1.2)$$

A popular way to encode it concretely on a computer is to use the so-called adjacency list, that we can represent mathematically speaking as a couple $G=(V,\mathcal{N})$ where $V$ is a finite set and $\mathcal{N}:V\to {\mathcal{P}}_2(V)$ is the neighbor function such $j\in \mathcal{N}(i)$ if, and only if, $\{i,j\}\in E$.

The graph in Figure 1.1 can be represented by the adjacency list $$\begin{array}{rl}1& \mapsto \{4,5\},2\mapsto \{5,6\},3\mapsto \{4,6\},\\ 4& \mapsto \{1,3\},5\mapsto \{1,2\},6\mapsto \{2,3\}.\end{array}(1.3)$$

We also say that a vertex $i$ has a degree $d_i$ of $k$ when it has exactly $k$ neighbors. Alternatively, $d_i$ is defined as the cardinal of $\mathcal{N}(i)$.

Note that when speaking about graphs, one might also think of more general structures such as

• Digraphs (directed graphs) where $E$ is not a subset of ${\mathcal{P}}_2(V)$ but a subset of $V\times V$;

• Graphs with self-loop, i.e., $E\subseteq {\mathcal{P}}_2(V)\cup V$;

• Multi/Hyper-graph where $E$ might have repeated edges;

• or quivers, i.e., multi-digraphs, etc.

Another important generalization is the consideration of weighted (di)graph where instead of dealing with a couple $G=(V,E)$, we add a (symmetric if undirected) function $\omega :V\times V\to {\mathbb{R}}_{>0}$. It is then common to use the weighted adjacency matrix $A^{\omega }$ and weighted degree $d_i^{\omega }$, defined as $$a_{i,j}^{\omega }=\{\begin{array}{ll}\omega (i,j)& \text{if }i\sim j,\\ 0& \text{otherwise,}\end{array}\text{ and }{d}_i^{\omega }=\sum _{j\in \mathcal{N}(i)}\omega ({\omega }_{i,j}).(1.4)$$ Note that we recover the standard definition of a unweighted graph if ${\omega }_{i,j}=1$ when $i\sim j$.

2 Graphs in supervised learning¶

As a reminder, we typically say that we are performing supervised learning when we have access to a training set $$\mathcal{T}=\{x_i,y_i{\}}_{i=1}^n\in (\mathcal{X}\times \mathcal{Y})\sim \mu \text{i.i.d.},(2.1)$$ where $\mu$ is a probability measure over $\mathcal{X}\times \mathcal{Y}$. The goal is to learn from it a function $\mathrm{\Phi }:\mathcal{X}\to \mathcal{Y}$ that generalize well in the sense that for $(x,y)\sim \mu$, $\mathrm{\Phi }(x)\approx y$. This is typically – but not only – achieved using Empirical Risk Minimization (ERM), that is solving the minimizing problem $$\arg \underset{\mathrm{\Phi }\in \mathfrak{F}}{min}\frac{1}{n}\sum _{i=1}^n\mathcal{L}(y_i,\mathrm{\Phi }(x_i)),(2.2)$$ where $\mathcal{L}:\mathcal{Y}\times \mathcal{Y}$ is an adequate loss function, e.g, the ${\ell }^2$ loss $\mathcal{L}(y,y^{\prime })=\Vert y-y^{\prime }{\Vert }_2^2$, and $\mathfrak{F}$ is a candidate set of function $\mathfrak{F}\subseteq {\mathcal{Y}}^{\mathcal{X}}$. Modern (deep) learning is often considered in the interpolating regime, i.e., we seek highly parameterized models where the $\mathrm{\Phi }$ is expected to achieve a 0-error on the training set: $\mathrm{\forall }i\in \{1,\dots ,n\}$, $\mathrm{\Phi }(x_i)=y_i$.

2.1 Graph classification¶

Classification of graphs aims to answer questions such as “Does this protein $G$ is useful (+1) or not (-1)?” Formally, it is an application (for binary classification) $$\overline{\mathrm{\Phi }}:\{\begin{array}{ll}\mathfrak{G}& \to \{-1,+1\}\\ G& \mapsto \mathrm{\Phi }(G)\end{array}(2.3)$$ where $\mathfrak{G}$ is the set of all graphs with a finite number of vertices. Here, the object of interest is the domain, e.g, the graph. To learn this function $\overline{\mathrm{\Phi }}$, we typically have access to a training set $(G_i,y_i{)}_{i=1}^n\in (\mathfrak{G}\times \{-1,1\}{)}^n$.

2.2 Node classification¶

In contrast, node classification aims to answer “Does this atom $i$ of charge $z(i)$ involved (+1) or not (-1) in the activity of the protein $G$?” Here, the map of interest has the form $$\mathrm{\Phi }:\{\begin{array}{ll}\mathcal{H}(V)& \to \{-1,+1\}\\ z& \mapsto \mathrm{\Phi }(z)\end{array}(2.4)$$ where $\mathcal{H}(V)$ is the set of all functions $z:V\to \mathbb{R}$, or equivalently, node features $z\in {\mathbb{R}}^{|V|}$. To learn this function $\mathrm{\Phi }$, the training set has the form $(z_i,y_i{)}_{i=1}^n\in (\mathcal{H}(V)\times \{-1,1\}{)}^n$. If both task are built around the idea of a graph $G$, they fundamentally differ as graph classification aims to learn a domain whereas node classification aims to learn a function over this domain. Note that $\mathcal{H}(V)$ is isomorphic to ${\mathbb{R}}^{|V|}$, and thus can be endowed an Hilbert structure using the canonical inner product.

Similarly to the Euclidean case, classification admits a continuous counterpart called regression, and one can define node regression as the task $$\mathrm{\Phi }:\{\begin{array}{ll}\mathcal{H}(V)& \to \mathbb{R}\\ z& \mapsto \mathrm{\Phi }(z)\end{array}(2.5)$$ Typical question would be “What is the energy $z(i)$ of the atom $i$ in the activity of the protein $G$?”

3 Invariance and Equivariance¶

In the context of graph learning, we are interested in the behavior of the function $\mathrm{\Phi }$ with respect to the structure of the graph. In particular, we are interested in the behavior of $\mathrm{\Phi }$ with respect to the permutation of the vertices.

3.1 Reminders on groups¶

A group is a couple $(\mathcal{G},\circ )$ where $\mathcal{G}$ is a set and $\circ$ a binary operation on $\mathcal{G}$. This (internal) binary operation satisfies three properties

• Associativity. For any $g_1,g_2,g_3\in \mathcal{G}$, one has

$$(g_1\circ g_2)\circ g_3=g_1\circ (g_2\circ g_3).(3.1)$$

• Existence of a unit element. There exists a unique element $e\in \mathcal{G}$ such that for any $g\in \mathcal{G}$, one has

$$g\circ e=e\circ g=g.(3.2)$$

• Existence of an inverse. For any $g\in \mathcal{G}$, there exists a unique $g^{-1}\in \mathcal{G}$ such that

$$g\circ g^{-1}=g^{-1}\circ g=e.(3.3)$$

Groups have a central place in the study of symmetry in algebra, and the notion of invariance emerges directly from it. Basic examples of groups includes

• The real line endowed with the addition $(\mathbb{R},+)$;

• The set of rotations endowed with the composition $(\mathrm{SO}(n),\circ )$;

• The set of permutations endowed with the composition $({\mathfrak{S}}_n,\circ )$.

3.2 Group action¶

Without diving in the subtilites of representation theory, we can recall that one of the most important tool of group theory is the notion of group action. A (left) group action $\cdot$ of $(\mathcal{G},\circ )$ onto a set $\mathcal{X}$ is a map from $\mathcal{G}\times \mathcal{X}$ to $\mathcal{X}$ that maps $(g,x)\in \mathcal{G}\times \mathcal{X}$ to $g\cdot x\in \mathcal{X}$ such that it is

• associative: for all $g_1,g_2\in \mathcal{G}$, $x\in \mathcal{X}$, one has $g_1\cdot (g_2\cdot x)=(g_1\circ g_2)\cdot x$ ;

• identity law: for all $x\in \mathcal{X}$, one has $e\cdot x=x$ .

A natural group action encountered in geometry and imaging is the (natural) action of the 2D (resp. 3D) rotations $\mathrm{SO}(2)$ (resp. $\mathrm{SO}(3)$) onto the ambient space ${\mathbb{R}}^2$ (resp. ${\mathbb{R}}^3$). Intuitively, this is simply applying a rotation to a point in ${\mathbb{R}}^n$, and by extension to a subset $S\subseteq {\mathbb{R}}^2$.

Another well-known example is the action of ${\mathbb{S}}_n$ on ${\mathbb{R}}^n$ defined by $$\sigma \cdot x=\left(\begin{array}{c}{x}_{\sigma (1)}\\ ⋮\\ x_{\sigma (n)}\end{array}\right)(3.4)$$

Remark that a group can act on different sets, for instance ${\mathfrak{S}}_n$ can act on the finite set $\{1,\dots ,n\}$ by $\sigma \cdot m=\sigma (m)$, and a group can act with two different actions on the same set (replace $\sigma$ by ${\sigma }^{-1}$).

These two examples of actions have a common property: they are linear group actions. Linear group actions are probably the most fundamental examples of actions, and a whole field is dedicated to their studies: group representations. A group action is said to be linear if $\mathcal{X}$ is a vector space, for all $g\in \mathcal{G}$, $x,x^{\prime }\in \mathcal{X}$ and for all $\alpha ,\beta \in \mathbb{R}$, $$g\cdot (\alpha x+\beta x^{\prime })=\alpha (g\cdot x)+\beta (g\cdot y).(3.5)$$

3.3 Invariance and Equivariance¶

Consider a function $f:\mathcal{X}\to \mathcal{Y}$. We say that $f$ is $\mathcal{G}$-invariant if for any $g\in \mathcal{G}$, $x\in \mathcal{X}$, one has $$f(g\cdot x)=f(x).(3.6)$$ For instance, if $\mathcal{G}=\mathrm{SO}(2)$ is the group of 2D rotations and $\mathcal{X}={\mathbb{R}}^2$ the Euclidean plane, then the Euclidean norm $f(x)=\Vert x\Vert$ is $\mathrm{SO}(2)$-invariant: given any rotation $r_{\theta }\in \mathrm{SO}(2)$, one has $\Vert r_{\theta }(x)\Vert =\Vert x\Vert$.

Consider now a group $\mathcal{G}$ acting on $\mathcal{X}$ and also² acting on $\mathcal{Y}$. We say that $f$ is $\mathcal{G}$-equivariant if for any $g\in \mathcal{G}$, $x\in \mathcal{X}$, one has $$f(g\cdot x)=g\cdot f(x).(3.7)$$ Important examples includes function that index-based in ${\mathbb{R}}^n$. For instance, if $\mathcal{G}={\mathfrak{S}}_n$ and $\mathcal{X}=\mathcal{Y}={\mathbb{R}}^n$, then $f(x)=\arg \underset{1\le i\le n}{min}{x}_i$ is ${\mathfrak{S}}_n$-equivariant: $f(\sigma \cdot x)=\sigma (\arg \underset{1\le i\le n}{min}{x}_i)$.

4 A Fourier look at graph signal processing¶

At this point, we are quite far from concrete application in machine learning. A first question is: what are the invariance or equivariance that we want to enforce? In the following section, we will consider the important example of shift-invariance as a building block of Convolutional Neural Networks.

4.1 Convolution¶

The convolution is a fundamental operation in signal processing. Given two real functions $g,h$, let say Lebesgue-integrable, one defines the convolution $g\ast h$ as $$(g\ast h)(t)={\int }_{\mathbb{R}}g(t-\tau )h(\tau )d\tau .(4.1)$$ One may look at $g$ as a signal and $h$ as a filter eventhough the two functions may play reversed-role. An important interpretation of the convolution is to see it as a local averaging method: it is indeed a sort of generalization of a moving average.

For our purpose, the important property of convolution is that it is shift-equivariant. This means that if we shift the input signal, the output signal is shifted in the same way: if $v\in \mathbb{R}$, $g,h\in L^1(\mathbb{R})$, then, $$(T_v\cdot g)\ast h=T_v\cdot (g\ast h).(4.2)$$ where $T_v$ is the translation operator defined by $T_v\cdot g(t)=g(t-v)$.

In traditional signal processing, such filters $h$ are given: Gaussian blur, sharpening, etc. In contrast, in machine learning, and especially for CNNs, such filter are learned during the training procedure (see course Introduction to Deep Learning).

Our issues here are

• What is a convolution on a graph?

• Even more basic, what is shift-equivariance on a graph?

There is no universal answer to these two questions.

4.2 Convolution and Fourier¶

For an integrable function $g:\mathbb{R}\to \mathbb{R}$, its Fourier transform $\mathcal{F}[g]:\mathbb{R}\to \mathbb{C}$ is defined as $$\mathcal{F}[g]:\omega \mapsto {\int }_{\mathbb{R}}g(t)e^{-2i\pi \omega t}dt.(4.3)$$

On the $L^2(\mathbb{R})$ space, $\mathcal{F}[g]$ might be view as the inner product between $g$ and the complex exponentials $$\mathcal{F}[g](\omega )={⟨g,{\exp }_{-2i\pi \omega }⟩}_{L^2(\mathbb{R})}(4.4)$$

The key property used in signal processing is that Fourier transform diagonalize the convolution: for any $g,h\in L^2(\mathbb{R})$, then $$\mathcal{F}[g\ast h]=\mathcal{F}[g]\mathcal{F}[h].(4.5)$$ I show in Figure 4.1 an example of the convolution of two functions and its Fourier transform.

The goal hence is to define what is a “Fourier transform” on graphs. To this end, we take yet another interpretation: the complex exponentials ${\exp }_{-2i\pi \omega }:t\mapsto e^{-2i\pi \omega t}$ are the eigenfunctions of the Laplacian operator on the torus $S^1=\mathbb{R}/\mathbb{Z}$. If $f={\exp }_{-2i\pi \omega }$, then $f^{\prime }(t)=-2i\pi \omega f(t)$ and $$f^{″}(t)=(-2i\pi \omega {)}^{2}f(t)=-4{\pi }^2{\omega }^{2}f(t).(4.6)$$

5 Graph Laplacian¶

The combinatorial graph Laplacian is a semidefinite positive symmetric matrix associated to the quadratic form $$⟨Lz,z⟩=\sum _{i\sim j}(x_i-x_j{)}^2.(5.3)$$ The spectral graph theory is more often concerned with the normalized version (??, a). It has several interesting properties (among many others):

An other important fact is that seeing $\mathcal{L}$ as a map of $G$, we can say that it is ${\mathfrak{S}}_n$-equivariant: if one reorders the nodes, it is sufficient to reorder lines and columns to get the new Laplacian matrix.

5.1 Graph Fourier Transform¶

The last point of Proposition prp-laplacian-graph, namely the fact that $\mathcal{L}$ is a real symmetric operator is fundamental. The spectral theorem tells us that there exists an orthonormal $U=[u_0\cdots u_{n-1}]\in {\mathbb{R}}^{n\times n}$ and $n$ real values ${\lambda }_0\le \cdots \le {\lambda }_{n-1}\in \mathbb{R}$ such that $$\mathcal{L}=UD{U}^T\text{where}D=\mathrm{diag}({\lambda }_0,\cdots ,{\lambda }_{n-1})\in {\mathbb{R}}^{n\times n}.(5.6)$$ Observe that $U$ is not necessarly uniquely defined, and that ${\lambda }_0=0$ associated to the eigenvector $1_n$.

Recall that the Fourier transform on $L^2(\mathbb{R})$ is defined as $$\mathcal{F}[g](\omega )={⟨g,{\exp }_{-2i\pi \omega }⟩}_{L^2(\mathbb{R})},(5.7)$$ where ${\exp }_{-2i\pi \omega }$ are the eigenvectors of the Laplacian. Analogously, we define the Fourier transform on a graph (GFT) as follow:

We can rewrite it in matrix form as $\mathcal{F}[z]=U^{\mathrm{\top }}z$. An important feature of the GFT is that there exists an inverse GFT, defined similarly to the real case: $$z(i)=\sum _{k=0}^{n-1}\mathcal{F}[z]({\lambda }_k)u_k(i)\text{for}i=1,\dots ,n.(5.9)$$

5.2 Filtering on graphs¶

Given the definition of the GFT, how to filter a signal? The idea is to act on the eigenvalues of the eigendecomposition, and let eigenvectors untouched. So given a filter $h:\mathbb{R}\to \mathbb{R}$, the filtering of $z\in {\mathbb{R}}^n$ by $h$ is given by: $$h\ast z={\mathcal{F}}^{-1}[h(D)\mathcal{F}[z]]=Uh(D)U^{\mathrm{\top }}z,(5.10)$$ where $h(D)$ is applied pointwise. An important point: despite the notation, the filter $h\ast z$ is not a regular convolution. Observe that $z\mapsto h\ast z$ is ${\mathfrak{S}}_n$-equivariant.

In practice, diagonalizing the Laplacian is too costly. What people use is polynomial, or analytical, filters of the Laplacian. Given a polynomial, or formal serie, $h=\sum _{k\ge 0}{\beta }_k{X}^k\in \mathbb{R}[[X]]$, we let (possibly not-well defined in the case of formal serie) $$h\ast z=\sum _{k\ge 0}{\beta }_k{L}^{k}z.(5.11)$$ Note that from a theoretical perspect, it is still only application on the eigenvalues. Figure fig-conv-graph illustrates the filtering of a graph signal by a low-pass filter.

6 Graph Neural Network¶

6.1 (Spectral) Graph Convolutional Network¶

Up to some subtles or notational differences, you probably encounter CNNs as parametric function defined layer-wise by a combination of

• non-linearities such as ReLU;

• convolution layers mapping a tensor to another;

• pooling (or subsampling) reducing the dimension using for instance a max- or mean-pooling;

• fully connected layers (Multi-Layer Perceptron, MLP) to produce an output.

In the context of GNNs, non-linearities will be the same (typically Lipschitz function different from the identity), convolution will be used as defined in the previous section, MLPs will be the same. But what about pooling? This is (mostly) an open question in the GNNs on how to produce good and efficient pooling operation, also known as graph coarsening. These architectures were defined around 2015, by (??, a) and (??, a).

A GCN with $M+1$ layers is defined as follows:

1. The signal at the input layer is some node features $Z^{(0)}=Z$ with dimension $d_0=d_z$ and built up columns $z_j^{(0)}\in {\mathbb{R}}^n$.

2. For all $\ell =1,\dots ,L$, the signal $Z^{(\ell +1)}\in {\mathbb{R}}^{n\times d_{\ell +1}}$ at layer $\ell +1$ is obtained by propagation of the signal $Z^{(\ell )}\in {\mathbb{R}}^{n\times d_{\ell }}$ at layer $\ell$ with respect to analytic filters of the normalized Laplacian: $$z_j^{(\ell +1)}=\rho (\sum _{i=1}^{d_{\ell }}{h}_{ij}^{(\ell )}(\mathcal{L})z_i^{(\ell )}+b_j^{(\ell )}{1}_n)\in {\mathbb{R}}^n,\mathrm{\forall }j=1\dots d_{\ell +1}.(6.1)$$

3. The output depends on the notion of invariance that one wishes to preserve.

   • ${\mathfrak{S}}_n$-equivariance (node classification). In this case, the output of the GCN is a node-signal ${\mathrm{\Phi }}_G(Z)\in {\mathbb{R}}^{n\times d_{\text{out}}}$ defined as $${\mathrm{\Phi }}_G(Z)={\text{MLP}}_{\theta }(Z^{(L)}),(6.2)$$ where ${\text{MLP}}_{\theta }$ is a MLP applied row-wise to the signal $Z^{(L)}$.

   • ${\mathfrak{S}}_n$-invariance (graph classification). In this case, the output is a single vector ${\overline{\mathrm{\Phi }}}_G(Z)\in {\mathbb{R}}^{d_{\text{out}}}$ given as a global pooling $${\overline{\mathrm{\Phi }}}_G(Z)=\frac{1}{n}\sum _{i=1}^n{\mathrm{\Phi }}_G(Z{)}_i.(6.3)$$

6.2 Invariance and Equivariance of GCNs¶

In the definition of GCNs, it was roughly said that we can made the output either ${\mathfrak{S}}_n$-equivariant or ${\mathfrak{S}}_n$-invariant. But what do we mean exactly by that? We said that a permutation $\sigma$ acts onto the space of GCNs with the action $\sigma \cdot {\mathrm{\Phi }}_G$ defined as $$\mathrm{\forall }Z\in {\mathbb{R}}^{n\times d_0},(\sigma \cdot {\mathrm{\Phi }}_G)(Z)={\mathrm{\Phi }}_{\sigma \cdot G}(\sigma \cdot Z),(6.4)$$ where we defined the action on the graph and the signal as $$\begin{array}{rl}\sigma \cdot G& =(\sigma \cdot V,\sigma \cdot E)\\ \sigma \cdot Z& =\left(\begin{array}{ccc}(z_1{)}_{\sigma (1)}& \cdots & (z_{d_0}{)}_{\sigma (1)}\\ ⋮& & ⋮\\ (z_1{)}_{\sigma (n)}& \cdots & (z_{d_0}{)}_{\sigma (n)}\end{array}\right)\end{array}(6.5)$$ The action on the group is more easily defined in fact on the adjacency matrix. For any $\sigma \in {\mathfrak{S}}_n$, let $P_{\sigma }$ be the associated permutation matrix. Then, one can defined $$\sigma \cdot A=P_{\sigma }A{P}_{{\sigma }^{-1}}=P_{\sigma }A{P}_{\sigma }^{\mathrm{\top }}.(6.6)$$ Cutting the algebraic details, these two definitions are perfectly equivalent.

We can now state the result

7 Another paradigm: Message-Passing Graph Neural Networks¶

Before ending this nose, let me mention that around 2017, (??, a) and (??, a) proposed a new architecture, or at least a new interpretation, that “forget” the spectral interpretation of GCNs. It is closer in the spirit to original graph neural network model proposed by (??, a), and is now the standard way to think of GNNs. I still believe that the spectral interpretation highlights important properties of GNNs, and is a good way to understand the behavior of GNNs.

Instead of a spectral interpretation, a neighborhood aggregation, or so-called message-passing architecture is proposed: $$z_j^{(\ell +1)}={\gamma }^{(\ell )}(z_j^{(\ell )},{◻}_{i\in \mathcal{N}(j)}{\rho }^{(\ell )}(z_j^{(\ell )},z_i^{(\ell )},e_{j,i})),(7.1)$$ where

• $z_j^{(\ell )}$ is the node feature at layer $\ell$ of node $j$;

• ${\gamma }^{(\ell )}$ (the update function) and ${\rho }^{(\ell )}$ (the message-passing function) are learnable functions such as traditional MLPs;

• $◻$ is an agregation function such as sum $\sum$ or maximum $max$;

• $e_{j,i}$ is a (potential) edge features.

In many papers, this is presented in the equivalent form (often with multisets for the aggregation) $$\begin{array}{rl}{m}_j^{(\ell )}& ={\mathrm{MSG}}^{(\ell )}(\{z_i^{(\ell )}:i\in \mathcal{N}(j)\cup \{j\}\})(7.2)\\ a_j^{(\ell )}& ={\mathrm{AGG}}^{(\ell )}(\{m_i^{(\ell )}:i\in \mathcal{N}(j)\})(7.3)\\ z_j^{(\ell +1)}& ={\mathrm{UPD}}^{(\ell )}(z_j^{(\ell )},a_j^{(\ell )}).(7.4)\end{array}$$

Let me mention several important examples of MPGNNs:

• Convolutional GNN. Wait what, didn’t we called them spectral GNNs? Yes, but we can look at them in a slightly more general way $$z_j^{(\ell +1)}={\gamma }^{(\ell )}(z_j^{(\ell )},{◻}_{i\in \mathcal{N}(j)}{c}_{i,j}{\rho }^{(\ell )}\left(z_i^{(\ell )}\right)),(7.5)$$ In practice, the community consider a more constrained version: $$z_j^{(\ell +1)}=\mathrm{ReLU}\left(\frac{1}{|\mathcal{N}(j)|}\sum _{i\in \mathcal{N}(j)}{W}^{(\ell )}{z}_i^{(\ell )}\right),(7.6)$$ where $W^{(\ell )}$ is a learnable matrix. This can be even more precisely specified (in matrix form) as $$Z^{\ell +1}=\mathrm{ReLU}(D^{-1}A{Z}^{\ell }{W}^{\ell ,\mathrm{\top }}),(7.7)$$ or in normalized form as $$Z^{\ell +1}=\mathrm{ReLU}(D^{-1/2}A{D}^{-1/2}{Z}^{\ell }{W}^{\ell ,\mathrm{\top }}),(7.8)$$

• Attentional GNN. $$z_j^{(\ell +1)}={\gamma }^{(\ell )}(z_j^{(\ell )},{◻}_{i\in \mathcal{N}(j)}a(z_j^{(\ell )},z_i^{(\ell )})),(7.9)$$ where $a$ is a learnable self-attention function.

Without diving into the details, I want to attract your attention that when dealing with a graph with only self-loop, or when $E={\mathcal{P}}_2(V)$, we obtain two popular architectures in the litteratures.

• When $\mathcal{N}(i)=\{i\}$ – so not a classical graph, you have to add a self-loop – the convolutional architecture boils down to the Deep Sets architecture (??, a).

• On the other extreme, when $i\sim j$ for all $i,j$ (again with self-loop), the attentional GNN is linked to the Transformer (??, a) architecture.

---

1. I think at this point this sentence is a meme in machine learning. At least, it is one for me.↩︎

2. In full generality, we may consider different groups but we will not need this generalization for our purpose of studying graph neural networks.↩︎