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 (Keriven et al., 2020, 2021) 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 where is a finite set of vertices or nodes , and is a subset of the unordered pairs of , called edges .

Beyond this formalism, it is quite frequent to enumerate the vertices and consider the associated adjacency matrix defined by where

where means that there is an edge between and . Note that is a real symmetric matrix.

The graph in Figure 1 can be represented by the adjacency matrix

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 where is a finite set and is the neighbor function such if, and only if, .

The graph in Figure 1 can be represented by the adjacency list

We also say that a vertex has a degree of when it has exactly neighbors. Alternatively, is defined as the cardinal of .

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

• Digraphs (directed graphs) where is not a subset of but a subset of ;

• Graphs with self-loop, i.e., ;

• Multi/Hyper-graph where 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 , we add a (symmetric if undirected) function . It is then common to use the weighted adjacency matrix and weighted degree , defined as

Note that we recover the standard definition of a unweighted graph if when .

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

where is a probability measure over . The goal is to learn from it a function that generalize well in the sense that for , . This is typically – but not only – achieved using Empirical Risk Minimization (ERM), that is solving the minimizing problem

where is an adequate loss function, e.g, the loss , and is a candidate set of function . Modern (deep) learning is often considered in the interpolating regime, i.e., we seek highly parameterized models where the is expected to achieve a 0-error on the training set: , .

2.1 Graph classification

Classification of graphs aims to answer questions such as “Does this protein is useful (+1) or not (-1)?” Formally, it is an application (for binary classification)

where 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 , we typically have access to a training set .

2.2 Node classification

In contrast, node classification aims to answer “Does this atom of charge involved (+1) or not (-1) in the activity of the protein ?” Here, the map of interest has the form

where is the set of all functions , or equivalently, node features . To learn this function , the training set has the form . If both task are built around the idea of a graph , they fundamentally differ as graph classification aims to learn a domain whereas node classification aims to learn a function over this domain. Note that is isomorphic to , 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

Typical question would be “What is the energy of the atom in the activity of the protein ?”

3 Invariance and Equivariance

In the context of graph learning, we are interested in the behavior of the function with respect to the structure of the graph. In particular, we are interested in the behavior of with respect to the permutation of the vertices.

3.1 Reminders on groups

A group is a couple where is a set and a binary operation on . This (internal) binary operation satisfies three properties

• Associativity. For any , one has

• Existence of a unit element. There exists a unique element such that for any , one has

• Existence of an inverse. For any , there exists a unique such that

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 ;

• The set of rotations endowed with the composition ;

• The set of permutations endowed with the composition .

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 of onto a set is a map from to that maps to such that it is

• associative: for all , , one has ;

• identity law: for all , one has .

A natural group action encountered in geometry and imaging is the (natural) action of the 2D (resp. 3D) rotations (resp. ) onto the ambient space (resp. ). Intuitively, this is simply applying a rotation to a point in , and by extension to a subset .

Another well-known example is the action of on defined by

Remark that a group can act on different sets, for instance can act on the finite set by , and a group can act with two different actions on the same set (replace by ).

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 is a vector space, for all , and for all ,

3.3 Invariance and Equivariance

Consider a function . We say that is -invariant if for any , , one has

For instance, if is the group of 2D rotations and the Euclidean plane, then the Euclidean norm is -invariant: given any rotation , one has .

Consider now a group acting on and also² acting on . We say that is -equivariant if for any , , one has

Important examples includes function that index-based in . For instance, if and , then is -equivariant: .

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 , let say Lebesgue-integrable, one defines the convolution as

One may look at as a signal and 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 , , then,

where is the translation operator defined by .

In traditional signal processing, such filters 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 , its Fourier transform is defined as

On the space, might be view as the inner product between and the complex exponentials

The key property used in signal processing is that Fourier transform diagonalize the convolution: for any , then

I show in Figure 2 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 are the eigenfunctions of the Laplacian operator on the torus . If , then and

5 Graph Laplacian

The combinatorial graph Laplacian is a semidefinite positive symmetric matrix associated to the quadratic form

The spectral graph theory is more often concerned with the normalized version (Chung, 1997). It has several interesting properties (among many others):

An other important fact is that seeing as a map of , we can say that it is -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 is a real symmetric operator is fundamental. The spectral theorem tells us that there exists an orthonormal and real values such that

Observe that is not necessarly uniquely defined, and that associated to the eigenvector .

Recall that the Fourier transform on is defined as

where 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 . An important feature of the GFT is that there exists an inverse GFT, defined similarly to the real case:

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 , the filtering of by is given by:

where is applied pointwise. An important point: despite the notation, the filter is not a regular convolution. Observe that is -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, , we let (possibly not-well defined in the case of formal serie)

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 Henaff et al. (2015) and Defferrard et al. (2016).

A GCN with layers is defined as follows:

1. The signal at the input layer is some node features with dimension and built up columns .

2. For all , the signal at layer is obtained by propagation of the signal at layer with respect to analytic filters of the normalized Laplacian:

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

   • -equivariance (node classification). In this case, the output of the GCN is a node-signal defined as

     where is a MLP applied row-wise to the signal .

   • -invariance (graph classification). In this case, the output is a single vector given as a global pooling

6.2 Invariance and Equivariance of GCNs

In the definition of GCNs, it was roughly said that we can made the output either -equivariant or -invariant. But what do we mean exactly by that? We said that a permutation acts onto the space of GCNs with the action defined as

where we defined the action on the graph and the signal as

The action on the group is more easily defined in fact on the adjacency matrix. For any , let be the associated permutation matrix. Then, one can defined

Cutting the algebraic details, these two definitions are perfectly equivalent.

We can now state the result