Everything is Connected: Graph Neural Networks
In many ways, graphs are the main modality of data we receive from nature.
This is due to the fact that most of the patterns we see, both in natural and
artificial systems, are elegantly representable using the language of graph
structures. Prominent examples include molecules (represented as graphs of
atoms and bonds), social networks and transportation networks. This potential
has already been seen by key scientific and industrial groups, with
already-impacted application areas including traffic forecasting, drug
discovery, social network analysis and recommender systems. Further, some of
the most successful domains of application for machine learning in previous
years -- images, text and speech processing -- can be seen as special cases of
graph representation learning, and consequently there has been significant
exchange of information between these areas. The main aim of this short survey
is to enable the reader to assimilate the key concepts in the area, and
position graph representation learning in a proper context with related fields.
Petar Veličković
# Everything is Connected: Graph Neural Networks

###### Abstract

In many ways, **graphs** are the main modality of data we receive from **nature**. This is due to the fact that most of the patterns we see, both in natural and artificial systems, are elegantly representable using the language of graph structures. Prominent examples include molecules (represented as graphs of atoms and bonds), social networks and transportation networks. This potential has already been seen by key scientific and industrial groups, with already-impacted application areas including traffic forecasting, drug discovery, social network analysis and recommender systems. Further, some of the most successful domains of application for machine learning in previous years--images, text and speech processing--can be seen as special cases of graph representation learning, and consequently there has been significant exchange of information between these areas. The main aim of this short survey is to enable the reader to assimilate the key concepts in the area, and position graph representation learning in a proper context with related fields.
Introduction: Why study data on graphs?

In this survey, I will present a vibrant and exciting area of deep learning research: graph representation learning. Or, put simply, building machine learning models over data that lives on _graphs_ (interconnected structures of _nodes_ connected by _edges_). These models are commonly known as _graph neural networks_, or **GNNs** for short.

There is very good reason to study data on graphs. From the molecule (a graph of _atoms_ connected by chemical _bonds_) all the way to the connectomic structure of the brain (a graph of _neurons_ connected by _synapses_), graphs are a universal language for describing living organisms, at all levels of organisation. Similarly, most relevant artificial constructs of interest to humans, from the transportation network (a graph of _intersections_ connected by _roads_) to the social network (a graph of _users_ connected by _friendship links_), are best reasoned about in terms of graphs.

This potential has been realised in recent years by both scientific and industrial groups, with GNNs now being used to discover novel potent antibiotics (Stokes et al., 2020), serve estimated travel times in Google Maps (Derrow-Pinion et al., 2021), power content recommendations in Pinterest (Ying et al., 2018) and product recommendations in Amazon (Hao et al., 2020), and design the latest generation of machine learning hardware: the TPUv5 (Mirhoseini et al., 2021). Further, GNN-based systems have helped mathematicians uncover the hidden structure of mathematical objects (Davies et al., 2021), leading to new top-tier conjectures in the area of representation theory (Blundell et al., 2021). It would not be an understatement to say that billions of people are coming into contact with predictions of a GNN, on a day-to-day basis. As such, it is likely a valuable pursuit to study GNNs, even without aiming to directly contribute to their development.

Beyond this, it is likely that the very _cognition_ processes driving our reasoning and decision-making are, in some sense, _graph-structured_. That is, paraphrasing a quote from Forrester (1971), nobody really imagines in their head all the information known to them; rather, they imagine only selected _concepts_, and _relationships_ between them, and use those to represent the real system. If we subscribe to this interpretation of cognition, it is quite unlikely that we will be able to build a generally intelligent system without some component relying on graph representation learning. Note that this finding does not clash with the fact that many recent skillful ML systems are based on the Transformer architecture (Vaswani et al., 2017)--as we will uncover in this review, Transformers are themselves a special case of GNNs.
The fundamentals: Permutation equivariance and invariance

In the previous section, we saw _why_ it is a good idea to study data that lives on graphs. Now we will see _how to learn_ useful functions over graph-structured data. The exposition largely follows Bronstein et al. (2021).

With graph-structured inputs, we typically assume a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\); that is, we have a set of _edges_\(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\), which specifies pairs of nodes in \(\mathcal{V}\) that are connected.

As we are interested in representation learning over the nodes, we attach to each node \(u\in\mathcal{V}\) a feature vector, \(\mathbf{x}_{u}\in\mathbb{R}^{k}\). The main way in which this data is _presented_ to a machine learning model is in the form of a _node feature matrix_. That is, a matrix \(\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times k}\) is prepared by stacking these features:

\[\mathbf{X}=\left[\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{|\mathcal{V }|}\right]^{\top} \tag{1}\]

that is, the \(i\)th row of \(\mathbf{X}\) corresponds to \(\mathbf{x}_{i}\).

There are many ways to represent \(\mathcal{E}\); since our context is one of linear algebra, we will use the _adjacency matrix_, \(\mathbf{A}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}\):

\[a_{uv}=\begin{cases}1&(u,v)\in\mathcal{E}\\ 0&(u,v)\notin\mathcal{E}\end{cases} \tag{2}\]

Note that it is often possible, especially in biochemical inputs, that we want to attach more information to the edges (such as distance scalars, or even entire feature vectors). I deliberately do not consider such cases to retain clarity--the conclusions we make would be the same in those cases.

However, the very act of using the above representations imposes a _node ordering_, and is therefore an arbitrary choice which does not align with the nodes and edges being unordered! Hence, we need to make sure that permuting the nodes and edges (\(\mathbf{PAP}^{\top}\), for a permutation matrix \(\mathbf{P}\)), does not change the outputs. We recover the following rules a GNN must satisfy:

\[f(\mathbf{PX},\mathbf{PAP}^{\top}) =f(\mathbf{X},\mathbf{A})\] (Invariance) (3) \[\mathbf{F}(\mathbf{PX},\mathbf{PAP}^{\top}) =\mathbf{PF}(\mathbf{X},\mathbf{A})\] (Equivariance) (4)

Here we assumed for simplicity that the functions \(f\), \(\mathbf{F}\) do not change the adjacency matrix, so we assume they only return graph or node-level outputs.
Further, the graph's edges allow for a _locality_ constraint in these functions. Much like how a CNN operates over a small neighbourhood of each pixel of an image, a GNN can operate over a neighbourhood of a node. One standard way to define this neighbourhood, \(\mathcal{N}_{u}\), is as follows:

\[\mathcal{N}_{u}=\{v\ |\ (u,v)\in\mathcal{E}\vee(v,u)\in\mathcal{E}\} \tag{5}\]

Accordingly, we can define the multiset of all neighbourhood features, \(\mathbf{X}_{\mathcal{N}_{u}}\):

\[\mathbf{X}_{\mathcal{N}_{u}}=\{\!\{\mathbf{x}_{v}\ |\ v\in\mathcal{N}_{u}\}\!\} \tag{6}\]

And our local function, \(\phi\), can take into account the neighbourhood; that is:

\[\mathbf{h}_{u}=\phi(\mathbf{x}_{u},\mathbf{X}_{\mathcal{N}_{u}})\qquad\qquad \mathbf{F}(\mathbf{X})=\left[\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_ {|\mathcal{V}|}\right]^{\top} \tag{7}\]

Through simple linear algebra manipulation, it is possible to show that if \(\phi\) is permutation invariant in \(\mathbf{X}_{\mathcal{N}_{u}}\), then \(\mathbf{F}\) will be permutation equivariant. The remaining question is, how do we define \(\phi\)?

## 3 Graph Neural Networks

Needless to say, defining \(\phi\) is one of the most active areas of machine learning research today. Depending on the literature context, it may be referred to as either "diffusion", "propagation", or "message passing". As claimed by Bronstein et al. (2021), most of them can be classified into one of three spatial flavours:

\[\mathbf{h}_{u} =\phi\left(\mathbf{x}_{u},\bigoplus_{v\in\mathcal{N}_{u}}c_{vu} \psi(\mathbf{x}_{v})\right)\] (Convolutional) (8) \[\mathbf{h}_{u} =\phi\left(\mathbf{x}_{u},\bigoplus_{v\in\mathcal{N}_{u}}a( \mathbf{x}_{u},\mathbf{x}_{v})\psi(\mathbf{x}_{v})\right)\] (Attentional) (9) \[\mathbf{h}_{u} =\phi\left(\mathbf{x}_{u},\bigoplus_{v\in\mathcal{N}_{u}}\psi( \mathbf{x}_{u},\mathbf{x}_{v})\right)\] (Message-passing) (10)

where \(\psi\) and \(\phi\) are neural networks--e.g. \(\psi(\mathbf{x})=\text{ReLU}(\mathbf{W}\mathbf{x}+\mathbf{b})\), and \(\bigoplus\) is any permutation-invariant aggregator, such as \(\sum\), averaging, or max. The expressive power of the GNN progressively increases going from Equation 8 to 10, at the cost of interpretability, scalability, or learning stability. For most tasks, a careful tradeoff is needed when choosing the right flavour.
This review does not attempt to be a comprehensive overview of specific GNN layers. That being said: representative _convolutional_ GNNs include the Chebyshev network (Defferrard et al., 2016, ChebyNet), graph convolutional network (Kipf and Welling, 2017, GCN) and the simplified graph convolution (Wu et al., 2019, SGC); representative _attentional_ GNNs include the mixture model CNN (Monti et al., 2017, MoNet), graph attention network (Velickovic et al., 2018, GAT) and its recent "v2" variant (Brody et al., 2022, GATv2); and representative _message-passing_ GNNs include interaction networks (Battaglia et al., 2016, IN), message passing neural networks (Gilmer et al., 2017, MPNN) and graph networks (Battaglia et al., 2018, GN).

Given such a GNN layer, we can learn (m)any interesting tasks over a graph, by appropriately combining \(\mathbf{h}_{u}\). I exemplify the three principal such tasks, grounded in biological examples:

**Node classification.** If the aim is to predict targets for each node \(u\in\mathcal{V}\), then our output is equivariant, and we can learn a shared classifier directly on \(\mathbf{h}_{u}\). A canonical example of this is classifying protein functions (e.g. using gene ontology data (Zitnik and Leskovec, 2017)) in a given protein-protein interaction network, as first done by GraphSAGE (Hamilton et al., 2017).

**Graph classification.** If we want to predict targets for the entire graph, then we want an invariant output, hence need to first _reduce_ all the \(\mathbf{h}_{u}\) into a common representation, e.g. by performing \(\bigoplus_{u\in\mathcal{V}}\mathbf{h}_{u}\), then learning a classifier over the resulting flat vector. A canonical example is classifying molecules for their quantum-chemical properties (Gilmer et al., 2017), estimating pharmacological properties like toxicity or solubility (Duvenaud et al., 2015; Xiong et al., 2019; Jiang et al., 2021) or virtual drug screening (Stokes et al., 2020).

**Link prediction.** Lastly, we may be interested in predicting properties of _edges_\((u,v)\), or even predicting whether an edge _exists_; giving rise to the name "link prediction". In this case, a classifier can be learnt over the concatenation of features \(\mathbf{h}_{u}\|\mathbf{h}_{v}\), along with any given edge-level features. Canonical tasks include predicting links between drugs and diseases--drug repurposing (Morselli Gysi et al., 2021), drugs and targets--binding affinity prediction (Lim et al., 2019; Jiang et al., 2020), or drugs and drugs--predicting adverse side-effects from polypharmacy (Zitnik et al., 2018; Deac et al., 2019).

It is possible to use the building blocks from the principal tasks above to go beyond classifying the entities given by the input graph, and have systems that _produce_ novel molecules (Mercado et al., 2021) or even perform _retrosynthesis_--the estimation of which reactions to utilise to synthesise given molecules (Somnath et al., 2021; Liu et al., 2022).

A natural question arises, following similar discussions over sets (Zaheer et al.,
2017; Wagstaff et al., 2019): Do GNNs, as given by Equation 10, represent _all_ of the valid permutation-equivariant functions over graphs? Opinions are divided. Key results in previous years seem to indicate that such models are fundamentally limited in terms of problems they can solve (Xu et al., 2019; Morris et al., 2019). However, most, if not all, of the proposals for addressing those limitations are still expressible using the pairwise message passing formalism of Equation 10; the main requirement is to carefully modify the _graph_ over which the equation is applied (Velickovic, 2022). To supplement this further, Loukas (2020) showed that, under proper initial features, sufficient depth-width product (\(\#\)layers \(\times\)\(\dim\mathbf{h}_{u}\)), and correct choices of \(\psi\) and \(\phi\), GNNs in Equation 10 are _Turing universal_--likely to be able to simulate _any_ computation which any computer can perform over such inputs.

All points considered, it is the author's opinion that the formalism in this section is likely all we need to build powerful GNNs--although, of course, different perspectives may benefit different problems, and existence of a powerful GNN does not mean it is easy to find using stochastic gradient descent.

## 4 GNNs without a graph: Deep Sets and Transformers

Throughout the prior section, we have made a seemingly innocent assumption: that we are _given_ an input graph (through \(\mathbf{A}\)). However, very often, not only will there not be a clear choice of \(\mathbf{A}\), but we may not have any prior belief on what \(\mathbf{A}\) even is. Further, even if a ground-truth \(\mathbf{A}\) is given _without noise_, it may not be the optimal _computation graph_: that is, passing messages over it may be problematic--for example, due to bottlenecks (Alon and Yahav, 2021). As such, it is generally a useful pursuit to study GNNs that are capable of modulating the input graph structure.

Accordingly, let us assume we only have a node feature matrix \(\mathbf{X}\), but no adjacency. One simple option is the "pessimistic" one: assume there are no edges at all, i.e. \(\mathbf{A}=\mathbf{I}\), or \(\mathcal{N}_{u}=\{u\}\). Under such an assumption, Equations 8-10 _all_ reduce to \(\mathbf{h}_{u}=\phi(\mathbf{x}_{u})\), yielding the Deep Sets model (Zaheer et al., 2017). Therefore, no power from graph-based modelling is exploited here.

The converse option (the "lazy" one) is to, instead, assume a _fully-connected_ graph; that is \(\mathbf{A}=\mathbf{1}\mathbf{1}^{\top}\), or \(\mathcal{N}_{u}=\mathcal{V}\). This then gives the GNN the full potential to exploit any edges deemed suitable, and is a very popular choice for smaller numbers of nodes. It can be shown that convolutional GNNs (Equation 8) would still reduce to Deep Sets in this case, which motivates the use of a stronger GNN. The next model
in the hierarchy, attentional GNNs (Equation 9), reduce to the following equation:

\[\mathbf{h}_{u}=\phi\left(\mathbf{x}_{u},\bigoplus_{v\in\mathcal{V}}a(\mathbf{x}_{ u},\mathbf{x}_{v})\psi(\mathbf{x}_{v})\right) \tag{11}\]

which is essentially the forward pass of a Transformer (Vaswani et al., 2017). To reverse-engineer why Transformers appear here, let us consider the NLP perspective. Namely, words in a sentence _interact_ (e.g. subject-object, adverb-verb). Further, these interactions are not trivial, and certainly not _sequential_--that is, words can interact even if they are many sentences apart1. Hence, we may want to use a _graph_ between them. But what _is_ this graph? Not even annotators tend to agree, and the optimal graph may well be task-dependant. In such a setting, a common assumption is to use a complete graph, and let the network infer relations by itself--at this point, the Transformer is all but rederived. For an in-depth rederivation, see Joshi (2020).

Footnote 1: This insight may also partly explain why RNNs or CNNs have been seen as suboptimal language models: they implicitly assume only neighbouring words directly interact.

Another reason why Transformers have become such a dominant GNN variant is the fact that using a fully connected graph structure allows to express all model computations using _dense matrix products_, and hence their computations align very well with current prevalent accelerators (GPUs and TPUs). Further, they have a more favourable storage complexity than the message passing variant (Equation 10). Accordingly, Transformers can be seen as GNNs that are currently winning the hardware lottery (Hooker, 2021)!

Before closing this section, it is worth noting a _third_ option to learning a GNN without an input graph: to _infer_ a graph structure to be used as edges for a GNN. This is an emerging area known as _latent graph inference_. It is typically quite challenging, since edge selection is a non-differentiable operation, and various paradigms have been proposed in recent years to overcome this challenge: nonparametric (Wang et al., 2019; Deac et al., 2022), supervised (Velickovic et al., 2020), variational (Kipf et al., 2018), reinforcement (Kazi et al., 2022) and self-supervised learning (Fatemi et al., 2021).

## 5 GNNs beyond permutation equivariance: Geometric Graphs

To conclude our discussion, we revisit another assumption: we have assumed our graphs to be a discrete, unordered, collection of nodes and edges--hence, only susceptible to permutation symmetries. But in many cases, this is not the entire story!
The graph, in fact, may often be endowed with some spatial _geometry_, which will be very useful to exploit. Molecules, and their three-dimensional conformer structure, are a classical example of this.

In general, we will assume our inputs are _geometric graphs_: nodes are endowed with both _features_, \(\mathbf{f}_{u}\), and _coordinates_, \(\mathbf{x}_{u}\in\mathbb{R}^{3}\). We may be interested in designing a model that is equivariant not only to permutations, but also 3D rotations, translations and reflections (the Euclidean group, \(\mathrm{E}(3)\)).

An \(\mathrm{E}(3)\)-equivariant message passing layer transforms the coordinates and features, and yields updated features \(\mathbf{f}_{u}^{\prime}\) and coordinates \(\mathbf{x}_{u}^{\prime}\). There exist many GNN layers that obey \(\mathrm{E}(n)\) equivariance, and one particularly elegant solution was proposed by Satorras et al. (2021):

\[\mathbf{f}_{u}^{\prime} =\phi\left(\mathbf{f}_{u},\bigoplus_{v\in\mathcal{N}_{u}}\psi_{ \mathrm{f}}\left(\mathbf{f}_{u},\mathbf{f}_{v},\|\mathbf{x}_{u}-\mathbf{x}_{v} \|^{2}\right)\right) \tag{12}\] \[\mathbf{x}_{u}^{\prime} =\mathbf{x}_{u}+\sum_{v\neq u}(\mathbf{x}_{u}-\mathbf{x}_{v}) \psi_{\mathrm{x}}\left(\mathbf{f}_{u},\mathbf{f}_{v},\|\mathbf{x}_{u}- \mathbf{x}_{v}\|^{2}\right) \tag{13}\]

The key insight behind this model is that rotating, translating or reflecting coordinates does not change their distances \(\|\mathbf{x}_{u}-\mathbf{x}_{v}\|^{2}\), i.e., such operations are _isometries_. Hence, if we roto-translate all nodes as \(\mathbf{x}_{u}\leftarrow\mathbf{R}\mathbf{x}_{u}+\mathbf{b}\), the output features \(\mathbf{f}_{u}^{\prime}\) remain unchanged, while the output coordinates transform accordingly: \(\mathbf{x}_{u}^{\prime}\leftarrow\mathbf{R}\mathbf{x}_{u}^{\prime}+\mathbf{b}\).

While indeed highly elegant, a model like this hides a caveat: it only works over _scalar_ features \(\mathbf{f}_{u}\). If our model needs to support any kind of _vector_ input (e.g. _forces_ between atoms), the model in Equation 12 would not suffice, because the vectors would need to appropriately rotate with \(\mathbf{R}\). Satorras et al. (2021) do propose a variant that allows for explicitly updating vector features, \(\mathbf{v}_{u}\):

\[\mathbf{v}_{u}^{\prime}=\phi_{\mathrm{v}}(\mathbf{h}_{u})\mathbf{v}_{u}+C \sum_{v\neq u}(\mathbf{x}_{u}-\mathbf{x}_{v})\phi_{\mathrm{x}}\left(\mathbf{ f}_{u},\mathbf{f}_{v},\|\mathbf{x}_{u}-\mathbf{x}_{v}\|^{2}\right),\quad \mathbf{x}_{u}^{\prime}=\mathbf{x}_{u}+\mathbf{v}_{u}^{\prime} \tag{14}\]

But these issues will continue to arise, as features get "tensored up". Hence, in such circumstances, it might be useful to instead characterise a generic equation that supports _all_ possible roto-translation equivariant models, and then learning its parameters. Such an analysis was done in Tensor Field Networks (Thomas et al., 2018) for point clouds, and then extended to \(\mathrm{SE}(3)\)-Transformers for general graphs (Fuchs et al., 2020).

Perhaps a fitting conclusion of this survey is a simple realisation: having showed how both Transformers and geometric equivariance constraints play a part within the context of GNNs, we now have all of the key building blocks to define some
of the most famous geometric GNN architectures in the wild, such as AlphaFold 2 (Jumper et al., 2021), but also similar protein-related papers which made headlines in both Nature Methods (Gainza et al., 2020, MaSIF) and Nature Machine Intelligence (Mendez-Lucio et al., 2021). It seems that protein folding, protein design, and protein binding prediction (Stark et al., 2022) all appear to be an extremely potent area of attack for geometric GNNs; just one of many solid reasons why the field of structural biology would benefit from these recent developments (Bouatta et al., 2021).
