Graph neural network

Graph neural networks (GNNs) are specialized artificial neural networks that are designed for tasks whose inputs are graphs.¹²³⁴⁵

One prominent example is molecular drug design.⁶⁷⁸ Each input sample is a graph representation of a molecule, where atoms form the nodes and chemical bonds between atoms form the edges. In addition to the graph representation, the input also includes known chemical properties for each of the atoms. Dataset samples may thus differ in length, reflecting the varying numbers of atoms in molecules, and the varying number of bonds between them. The task is to predict the efficacy of a given molecule for a specific medical application, such as eliminating E. coli bacteria.

The key design element of GNNs is the use of pairwise message passing, such that graph nodes iteratively update their representations by exchanging information with their neighbors. Several GNN architectures have been proposed,^2391011 which implement different flavors of message passing,¹²¹³ started by recursive² or convolutional constructive³ approaches. As of 2022, it is an open question whether it is possible to define GNN architectures "going beyond" message passing, or instead every GNN can be built on message passing over suitably defined graphs.¹⁴

In the more general subject of "geometric deep learning", certain existing neural network architectures can be interpreted as GNNs operating on suitably defined graphs.¹² A convolutional neural network layer, in the context of computer vision, can be considered a GNN applied to graphs whose nodes are pixels, and only adjacent pixels are connected by edges in the graph. A transformer layer, in natural language processing, can be considered a GNN applied to complete graphs whose nodes are words or tokens in a passage of natural language text.

Relevant application domains for GNNs include natural language processing,¹⁵ social networks,¹⁶ citation networks,¹⁷ molecular biology,¹⁸ chemistry,¹⁹²⁰ physics²¹ and NP-hard combinatorial optimization problems.²²

Open source libraries implementing GNNs include PyTorch Geometric²³ (PyTorch), TensorFlow GNN²⁴ (TensorFlow), Deep Graph Library²⁵ (framework agnostic), jraph²⁶ (Google JAX), and GraphNeuralNetworks.jl²⁷/GeometricFlux.jl²⁸ (Julia, Flux).

The architecture of a generic GNN implements the following fundamental layers:¹²

1. Permutation equivariant: a permutation equivariant layer maps a representation of a graph into an updated representation of the same graph. In the literature, permutation equivariant layers are implemented via pairwise message passing between graph nodes.¹²¹⁴ Intuitively, in a message passing layer, nodes update their representations by aggregating the messages received from their immediate neighbours. As such, each message passing layer increases the receptive field of the GNN by one hop.
2. Local pooling: a local pooling layer coarsens the graph via downsampling. Local pooling is used to increase the receptive field of a GNN, in a similar fashion to pooling layers in convolutional neural networks. Examples include k-nearest neighbours pooling, top-k pooling,²⁹ and self-attention pooling.³⁰
3. Global pooling: a global pooling layer, also known as readout layer, provides fixed-size representation of the whole graph. The global pooling layer must be permutation invariant, such that permutations in the ordering of graph nodes and edges do not alter the final output.³¹ Examples include element-wise sum, mean or maximum.

It has been demonstrated that GNNs cannot be more expressive than the Weisfeiler–Leman Graph Isomorphism Test.³²³³ In practice, this means that there exist different graph structures (e.g., molecules with the same atoms but different bonds) that cannot be distinguished by GNNs. More powerful GNNs operating on higher-dimension geometries such as simplicial complexes can be designed.³⁴³⁵¹³ As of 2022, whether or not future architectures will overcome the message passing primitive is an open research question.¹⁴

Message passing layers are permutation-equivariant layers mapping a graph into an updated representation of the same graph. Formally, they can be expressed as message passing neural networks (MPNNs).¹²

Let ${\displaystyle G=(V,E)}$ be a graph, where ${\displaystyle V}$ is the node set and ${\displaystyle E}$ is the edge set. Let ${\displaystyle N_{u}}$ be the neighbourhood of some node ${\displaystyle u\in V}$. Additionally, let ${\displaystyle \mathbf {x} _{u}}$ be the features of node ${\displaystyle u\in V}$, and ${\displaystyle \mathbf {e} _{uv}}$ be the features of edge ${\displaystyle (u,v)\in E}$. An MPNN layer can be expressed as follows:¹²

${\displaystyle \mathbf {h} _{u}=\phi \left(\mathbf {x} _{u},\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)}$

where ${\displaystyle \phi }$ and ${\displaystyle \psi }$ are differentiable functions (e.g., artificial neural networks), and ${\displaystyle \bigoplus }$ is a permutation invariant aggregation operator that can accept an arbitrary number of inputs (e.g., element-wise sum, mean, or max). In particular, ${\displaystyle \phi }$ and ${\displaystyle \psi }$ are referred to as update and message functions, respectively. Intuitively, in an MPNN computational block, graph nodes update their representations by aggregating the messages received from their neighbours.

The outputs of one or more MPNN layers are node representations ${\displaystyle \mathbf {h} _{u}}$ for each node ${\displaystyle u\in V}$ in the graph. Node representations can be employed for any downstream task, such as node/graph classification or edge prediction.

Graph nodes in an MPNN update their representation aggregating information from their immediate neighbours. As such, stacking ${\displaystyle n}$ MPNN layers means that one node will be able to communicate with nodes that are at most ${\displaystyle n}$ "hops" away. In principle, to ensure that every node receives information from every other node, one would need to stack a number of MPNN layers equal to the graph diameter. However, stacking many MPNN layers may cause issues such as oversmoothing³⁶ and oversquashing.³⁷ Oversmoothing refers to the issue of node representations becoming indistinguishable. Oversquashing refers to the bottleneck that is created by squeezing long-range dependencies into fixed-size representations. Countermeasures such as skip connections¹⁰³⁸ (as in residual neural networks), gated update rules³⁹ and jumping knowledge⁴⁰ can mitigate oversmoothing. Modifying the final layer to be a fully-adjacent layer, i.e., by considering the graph as a complete graph, can mitigate oversquashing in problems where long-range dependencies are required.³⁷

Other "flavours" of MPNN have been developed in the literature,¹² such as graph convolutional networks⁹ and graph attention networks,¹¹ whose definitions can be expressed in terms of the MPNN formalism.

The graph convolutional network (GCN) was first introduced by Thomas Kipf and Max Welling in 2017.⁹

A GCN layer defines a first-order approximation of a localized spectral filter on graphs. GCNs can be understood as a generalization of convolutional neural networks to graph-structured data.

The formal expression of a GCN layer reads as follows:

${\displaystyle \mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)}$

where ${\displaystyle \mathbf {H} }$ is the matrix of node representations ${\displaystyle \mathbf {h} _{u}}$, ${\displaystyle \mathbf {X} }$ is the matrix of node features ${\displaystyle \mathbf {x} _{u}}$, ${\displaystyle \sigma (\cdot )}$ is an activation function (e.g., ReLU), ${\displaystyle {\tilde {\mathbf {A} }}}$ is the graph adjacency matrix with the addition of self-loops, ${\displaystyle {\tilde {\mathbf {D} }}}$ is the graph degree matrix with the addition of self-loops, and ${\displaystyle \mathbf {\Theta } }$ is a matrix of trainable parameters.

In particular, let ${\displaystyle \mathbf {A} }$ be the graph adjacency matrix: then, one can define ${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I} }$ and ${\displaystyle {\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}}$, where ${\displaystyle \mathbf {I} }$ denotes the identity matrix. This normalization ensures that the eigenvalues of ${\displaystyle {\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}}$ are bounded in the range ${\displaystyle [0,1]}$, avoiding numerical instabilities and exploding/vanishing gradients.

A limitation of GCNs is that they do not allow multidimensional edge features ${\displaystyle \mathbf {e} _{uv}}$.⁹ It is however possible to associate scalar weights ${\displaystyle w_{uv}}$ to each edge by imposing ${\displaystyle A_{uv}=w_{uv}}$, i.e., by setting each nonzero entry in the adjacency matrix equal to the weight of the corresponding edge.

The graph attention network (GAT) was introduced by Petar Veličković et al. in 2018.¹¹

A graph attention network is a combination of a GNN and an attention layer. The implementation of attention layer in graphical neural networks helps provide attention or focus to the important information from the data instead of focusing on the whole data.

A multi-head GAT layer can be expressed as follows:

${\displaystyle \mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}^{k}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

where ${\displaystyle K}$ is the number of attention heads, ${\displaystyle {\Big \Vert }}$ denotes vector concatenation, ${\displaystyle \sigma (\cdot )}$ is an activation function (e.g., ReLU), ${\displaystyle N_{u}}$ is the set of immediate neighbor nodes of node ${\displaystyle u}$, including node ${\displaystyle u}$ itself, ${\displaystyle \alpha _{uv}^{k}}$ are attention coefficients for the ${\displaystyle k}$-th attention head, and ${\displaystyle W^{k}}$ is a matrix of trainable parameters for the ${\displaystyle k}$-th attention head.

For the final GAT layer, the outputs from each attention head are averaged before the application of the activation function. Formally, the final GAT layer can be written as:

${\displaystyle \mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}^{k}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

Attention in Machine Learning is a technique that mimics cognitive attention. In the context of learning on graphs, the attention coefficient ${\displaystyle \alpha _{uv}}$ measures how important node ${\displaystyle v}$ is to node ${\displaystyle u}$.

Normalized attention coefficients are computed as follows:

${\displaystyle \alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{z}\Vert \mathbf {e} _{uz}]\right))}}}$

where ${\displaystyle \mathbf {a} }$ is a vector of learnable weights, ${\displaystyle \cdot ^{T}}$ indicates transposition, ${\displaystyle \mathbf {e} _{uv}}$ are the edge features (if present), and ${\displaystyle {\text{LeakyReLU}}}$ is a modified ReLU activation function. Attention coefficients are then normalized via softmax to make them easily comparable across different nodes.¹¹

A GCN can be seen as a special case of a GAT where attention coefficients are not learnable, but fixed and equal to the edge weights ${\displaystyle w_{uv}}$.

The gated graph sequence neural network (GGS-NN) was introduced by Yujia Li et al. in 2015.³⁹ The GGS-NN extends the GNN formulation by Scarselli et al.² to output sequences. The message passing framework is implemented as an update rule to a gated recurrent unit (GRU) cell.

A GGS-NN can be expressed as follows:

${\displaystyle \mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0} }$

${\displaystyle \mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}}$

${\displaystyle \mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})}$

where ${\displaystyle \Vert }$ denotes vector concatenation, ${\displaystyle \mathbf {0} }$ is a vector of zeros, ${\displaystyle \mathbf {\Theta } }$ is a matrix of learnable parameters, ${\displaystyle {\text{GRU}}}$ is a GRU cell, and ${\displaystyle l}$ denotes the sequence index. In a GGS-NN, the node representations are regarded as the hidden states of a GRU cell. The initial node features ${\displaystyle \mathbf {x} _{u}^{(0)}}$ are zero-padded up to the hidden state dimension of the GRU cell. The same GRU cell is used for updating representations for each node.

Local pooling layers coarsen the graph via downsampling. Subsequently, several learnable local pooling strategies that have been proposed are presented.³¹ For each case, the input is the initial graph represented by a matrix ${\displaystyle \mathbf {X} }$ of node features, and the graph adjacency matrix ${\displaystyle \mathbf {A} }$. The output is the new matrix ${\displaystyle \mathbf {X} '}$of node features, and the new graph adjacency matrix ${\displaystyle \mathbf {A} '}$.

We first set

${\displaystyle \mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}}$

where ${\displaystyle \mathbf {p} }$ is a learnable projection vector. The projection vector ${\displaystyle \mathbf {p} }$ computes a scalar projection value for each graph node.

The top-k pooling layer ²⁹ can then be formalised as follows:

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

where ${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$ is the subset of nodes with the top-k highest projection scores, ${\displaystyle \odot }$ denotes element-wise matrix multiplication, and ${\displaystyle {\text{sigmoid}}(\cdot )}$ is the sigmoid function. In other words, the nodes with the top-k highest projection scores are retained in the new adjacency matrix ${\displaystyle \mathbf {A} '}$. The ${\displaystyle {\text{sigmoid}}(\cdot )}$ operation makes the projection vector ${\displaystyle \mathbf {p} }$ trainable by backpropagation, which otherwise would produce discrete outputs.²⁹

We first set

${\displaystyle \mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )}$

where ${\displaystyle {\text{GNN}}}$ is a generic permutation equivariant GNN layer (e.g., GCN, GAT, MPNN).

The Self-attention pooling layer³⁰ can then be formalised as follows:

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

where ${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$ is the subset of nodes with the top-k highest projection scores, ${\displaystyle \odot }$ denotes element-wise matrix multiplication.

The self-attention pooling layer can be seen as an extension of the top-k pooling layer. Differently from top-k pooling, the self-attention scores computed in self-attention pooling account both for the graph features and the graph topology.

Homophily principle, i.e., nodes with the same labels or similar attributes are more likely to be connected, has been commonly believed to be the main reason for the superiority of Graph Neural Networks (GNNs) over traditional Neural Networks (NNs) on graph-structured data, especially on node-level tasks.⁴¹ However, recent work has identified a non-trivial set of datasets where GNN's performance compared to the NN's is not satisfactory.⁴² Heterophily, i.e., low homophily, has been considered the main cause of this empirical observation.⁴³ People have begun to revisit and re-evaluate most existing graph models in the heterophily scenario across various kinds of graphs, e.g., heterogeneous graphs, temporal graphs and hypergraphs. Moreover, numerous graph-related applications are found to be closely related to the heterophily problem, e.g. graph fraud/anomaly detection, graph adversarial attacks and robustness, privacy, federated learning and point cloud segmentation, graph clustering, recommender systems, generative models, link prediction, graph classification and coloring, etc. In the past few years, considerable effort has been devoted to studying and addressing the heterophily issue in graph learning.⁴¹⁴³⁴⁴

Training GNNs on large graphs presents computational challenges that differ substantially from those in other neural network architectures. Two broad problem settings arise: training on a single very large graph (such as a social network with billions of nodes), and training on collections of large individual graphs (such as molecular systems requiring higher-order interaction modeling).

For the single large graph setting, sampling-based methods reduce memory requirements by operating on subgraphs rather than the full graph. Cluster-GCN partitions the graph into subgraphs using graph partitioning algorithms, training the model on each partition in sequence.⁴⁵ GraphSAINT instead samples subgraphs stochastically during training, constructing unbiased estimators for the full graph loss.⁴⁶ Distributed frameworks such as DistDGL⁴⁷ extend training to multi-machine settings, managing the inter-machine communication required for neighborhood aggregation when a graph's nodes are distributed across machines.

For tasks such as atomic simulations, a different bottleneck arises: GNN architectures that model higher-order interactions between triplets or quadruplets of atoms are memory-intensive at the level of individual graphs, making standard data parallelism — where each GPU processes a separate sample — insufficient when individual graphs exceed single-device memory. Graph Parallelism addresses this by distributing a single input graph across multiple GPUs, partitioning nodes and edges across devices rather than distributing samples across devices.⁴⁸. This approach enabled GNNs with hundreds of millions to billions of parameters to be trained on atomic systems that would otherwise exceed single-device memory, and has been applied to the development of large-scale universal interatomic potentials.

Graph neural networks are one of the main building blocks of AlphaFold, an artificial intelligence program developed by Google's DeepMind for solving the protein folding problem in biology. AlphaFold achieved first place in several CASP competitions.⁴⁹⁵⁰⁴⁰

Social networks are a major application domain for GNNs due to their natural representation as social graphs. GNNs are used to develop recommender systems based on both social relations and item relations.⁵¹¹⁶

GNNs are used as fundamental building blocks for several combinatorial optimization algorithms.⁵² Examples include computing shortest paths or Eulerian circuits for a given graph,³⁹ deriving chip placements superior or competitive to handcrafted human solutions,⁵³ and improving expert-designed branching rules in branch and bound.⁵⁴

When viewed as a graph, a network of computers can be analyzed with GNNs for anomaly detection. Anomalies within provenance graphs often correlate to malicious activity within the network. GNNs have been used to identify these anomalies on individual nodes⁵⁵ and within paths⁵⁶ to detect malicious processes, or on the edge level⁵⁷ to detect lateral movement.

Water distribution systems can be modelled as graphs, being then a straightforward application of GNN. This kind of algorithm has been applied to water demand forecasting,⁵⁸ interconnecting District Metered Areas(DMAs) to improve the forecasting capacity. Other application of this algorithm on water distribution modelling is the development of metamodels.⁵⁹

To represent an image as a graph structure, the image is first divided into multiple patches, each of which is treated as a node in the graph. Edges are then formed by connecting each node to its nearest neighbors based on spatial or feature similarity. This graph-based representation enables the application of graph learning models to visual tasks. The relational structure helps to enhance feature extraction and improve performance on image understanding.⁶⁰

Graph-based representation of text helps to capture deeper semantic relationships between words. Many studies have used graph networks to enhance performance in various text processing tasks such as text classification, question answering, Neural Machine Translation (NMT), event extraction, fact verification, etc.⁶¹

GNNs have become a primary tool for modeling atomic interactions in computational chemistry and materials science, where molecules and crystal structures are naturally represented as graphs with atoms as nodes and chemical bonds or spatial proximity as edges. A key advantage over traditional quantum chemistry methods such as density functional theory (DFT) is the reduction in computational cost from O(n³) to O(n), enabling simulations at previously impractical scales.

Early GNN architectures for this domain include SchNet (2017), which introduced continuous-filter convolutional layers for learning on 3D molecular structures,⁶² and DimeNet (2020), which incorporated angular information between atoms to improve geometric expressivity.⁶³ Subsequent equivariant architectures such as NequIP⁶⁴ and MACE,⁶⁵ which respect the rotational and translational symmetries of physical systems, achieved significant accuracy improvements on standard benchmarks including QM9, MD17, and the Materials Project.

Large open datasets have driven rapid progress in this area. The Open Catalyst 2020 (OC20) dataset, comprising over 260 million DFT calculations of adsorbate-catalyst surface interactions, established a widely used benchmark for energy and force prediction tasks relevant to catalyst discovery.⁶⁶. The Materials Project and Alexandria databases have similarly provided large-scale crystal structure data for training universal interatomic potentials. More recent datasets including OMat24 and OMol25 have extended coverage to organic molecules and complex materials at greater computational scale.

These datasets have enabled the development of universal [[machine-learned interatomic potential|machine learning interatomic potentials]] (MLIPs) — models trained across diverse chemical domains rather than on system-specific data. Examples include CHGNet,⁶⁷ M3GNet,⁶⁸ MACE-MP, and Meta FAIR's Universal Models for Atoms (UMA), the latter trained on approximately 500 million atomic structures spanning molecules, materials, and catalysts.⁶⁹ GNoME, developed by Google DeepMind, applied GNNs to predict the stability of crystal structures, reporting the identification of millions of new stable candidate materials.⁷⁰