Graph neural networks (GNN) are specializedartificial neural networks that are designed for tasks whose inputs aregraphs.^{[1][2][3][4][5]}

One prominent example is molecular drug design.^[6][7][8] 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, like eliminatingE. coli bacteria.

The key design element of GNNs is the use ofpairwise message passing, such that graph nodes iteratively update their representations by exchanging information with their neighbors. Several GNN architectures have been proposed,^{[2][3][9][10][11]} which implement different flavors of message passing,^[12][13] started by recursive^[2] or convolutional constructive^[3] approaches. As of 2022^[update], 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.^[14]

In the more general subject of "geometricdeep learning", certain existing neural network architectures can be interpreted as GNNs operating on suitably defined graphs.^[12] Aconvolutional neural network layer, in the context ofcomputer vision, can be considered a GNN applied to graphs whose nodes arepixels and only adjacent pixels are connected by edges in the graph. Atransformer layer, innatural language processing, can be considered a GNN applied tocomplete graphs whose nodes arewords or tokens in a passage ofnatural language text.

Relevant application domains for GNNs includenatural language processing,^[15]social networks,^[16]citation networks,^[17]molecular biology,^[18] chemistry,^[19][20]physics^[21] andNP-hardcombinatorial optimization problems.^[22]

Open sourcelibraries implementing GNNs include PyTorch Geometric^[23] (PyTorch), TensorFlow GNN^[24] (TensorFlow), Deep Graph Library^[25] (framework agnostic), jraph^[26] (Google JAX), and GraphNeuralNetworks.jl^[27]/GeometricFlux.jl^[28] (Julia,Flux).

The architecture of a generic GNN implements the following fundamentallayers:^[12]

1. Permutation equivariant: a permutation equivariant layermaps 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.^[12][14] Intuitively, in a message passing layer, nodesupdate their representations byaggregating themessages 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 localpooling layer coarsens the graph viadownsampling. Local pooling is used to increase the receptive field of a GNN, in a similar fashion to pooling layers inconvolutional neural networks. Examples includek-nearest neighbours pooling, top-k pooling,^[29] and self-attention pooling.^[30]
3. Global pooling: a global pooling layer, also known asreadout 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.^[31] Examples include element-wise sum, mean or maximum.

It has been demonstrated that GNNs cannot be more expressive than theWeisfeiler–Leman Graph Isomorphism Test.^[32][33] In practice, this means that there exist different graph structures (e.g.,molecules with the sameatoms but differentbonds) that cannot be distinguished by GNNs. More powerful GNNs operating on higher-dimension geometries such assimplicial complexes can be designed.^[34][35][13] As of 2022^[update], whether or not future architectures will overcome the message passing primitive is an open research question.^[14]

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).^[12]

Let${\displaystyle G=(V,E)}$ be agraph, where${\displaystyle V}$ is the node set and${\displaystyle E}$ is the edge set. Let${\displaystyle N_u}$ be theneighbourhood of some node${\displaystyle u\in V}$. Additionally, let${\displaystyle {\mathbf{x}}_u}$ be thefeatures of node${\displaystyle u\in V}$, and${\displaystyle {\mathbf{e}}_{uv}}$ be the features of edge${\displaystyle (u,v)\in E}$. An MPNNlayer can be expressed as follows:^[12]

${\displaystyle {\mathbf{h}}_u=\varphi \left({\mathbf{x}}_u,\underset{v\in N_u}{⨁}\psi ({\mathbf{x}}_u,{\mathbf{x}}_v,{\mathbf{e}}_{uv})\right)}$

where${\displaystyle \varphi }$ and${\displaystyle \psi }$ aredifferentiable functions (e.g.,artificial neural networks), and${\displaystyle ⨁}$ is apermutationinvariantaggregation operator that can accept an arbitrary number of inputs (e.g., element-wise sum, mean, or max). In particular,${\displaystyle \varphi }$ and${\displaystyle \psi }$ are referred to asupdate andmessage functions, respectively. Intuitively, in an MPNN computational block, graph nodesupdate their representations byaggregating themessages 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/graphclassification 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 graphdiameter. However, stacking many MPNN layers may cause issues such as oversmoothing^[36] and oversquashing.^[37] 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^[10][38] (as inresidual neural networks), gated update rules^[39] and jumping knowledge^[40] can mitigate oversmoothing. Modifying the final layer to be a fully-adjacent layer, i.e., by considering the graph as acomplete graph, can mitigate oversquashing in problems where long-range dependencies are required.^[37]

Other "flavours" of MPNN have been developed in the literature,^[12] such as graph convolutional networks^[9] and graph attention networks,^[11] whose definitions can be expressed in terms of the MPNN formalism.

The graph convolutional network (GCN) was first introduced byThomas Kipf andMax Welling in 2017.^[9]

A GCN layer defines afirst-order approximation of a localized spectralfilter on graphs. GCNs can be understood as a generalization ofconvolutional 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 anactivation function (e.g.,ReLU),${\displaystyle \tilde{\mathbf{A}}}$ is the graphadjacency matrix with the addition of self-loops,${\displaystyle \tilde{\mathbf{D}}}$ is the graphdegree 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 theidentity matrix. This normalization ensures that theeigenvalues 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]}$, avoidingnumerical instabilities andexploding/vanishing gradients.

A limitation of GCNs is that they do not allow multidimensional edge features${\displaystyle {\mathbf{e}}_{uv}}$.^[9] 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 byPetar Veličković et al. in 2018.^[11]

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=\stackrel{K}{\underset{k=1}{\Vert }}\sigma \left(\sum _{v\in N_u}{\alpha }_{uv}{\mathbf{W}}^k{\mathbf{x}}_v\right)}$

where${\displaystyle K}$ is the number ofattention heads,${\displaystyle \Vert }$ denotesvector concatenation,${\displaystyle \sigma (\cdot )}$ is anactivation function (e.g.,ReLU),${\displaystyle {\alpha }_{ij}}$ are attention coefficients, 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}{\mathbf{W}}^k{\mathbf{x}}_v\right)}$

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

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}$ indicatestransposition,${\displaystyle {\mathbf{e}}_{uv}}$ are the edge features (if present), and${\displaystyle \text{LeakyReLU}}$ is amodified ReLU activation function. Attention coefficients are normalized to make them easily comparable across different nodes.^[11]

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 byYujia Li et al. in 2015.^[39] The GGS-NN extends the GNN formulation by Scarselli et al.^[2] to output sequences. The message passing framework is implemented as an update rule to agated 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 }$ denotesvector 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)}}$ arezero-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.^[31] 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}}^{\prime }}$of node features, and the new graph adjacency matrix${\displaystyle {\mathbf{A}}^{\prime }}$.

We first set

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

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

The top-k pooling layer^[29] can then be formalised as follows:

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

${\displaystyle {\mathbf{A}}^{\prime }={\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-wisematrix multiplication, and${\displaystyle \text{sigmoid}(\cdot )}$ is thesigmoid function. In other words, the nodes with the top-k highest projection scores are retained in the new adjacency matrix${\displaystyle {\mathbf{A}}^{\prime }}$. The${\displaystyle \text{sigmoid}(\cdot )}$ operation makes the projection vector${\displaystyle \mathbf{p}}$ trainable bybackpropagation, which otherwise would produce discrete outputs.^[29]

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^[30] can then be formalised as follows:

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

${\displaystyle {\mathbf{A}}^{\prime }={\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 }$ denoteselement-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.^[41] However, recent work has identified a non-trivial set of datasets where GNN's performance compared to the NN's is not satisfactory.^[42]Heterophily, i.e., low homophily, has been considered the main cause of this empirical observation.^[43] 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 andhypergraphs. 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 andpoint cloud segmentation,graph clustering,recommender systems,generative models,link prediction,graph classification andcoloring, etc. In the past few years, considerable effort has been devoted to studying and addressing the heterophily issue in graph learning.^[41][43][44]

Graph neural networks are one of the main building blocks ofAlphaFold, an artificial intelligence program developed byGoogle'sDeepMind for solving theprotein folding problem inbiology. AlphaFold achieved first place in severalCASP competitions.^[45][46][40]

Social networks are a major application domain for GNNs due to their natural representation associal graphs. GNNs are used to develop recommender systems based on bothsocial relations and item relations.^[47][16]

GNNs are used as fundamental building blocks for several combinatorial optimization algorithms.^[48] Examples include computingshortest paths orEulerian circuits for a given graph,^[39] derivingchip placements superior or competitive to handcrafted human solutions,^[49] and improving expert-designed branching rules inbranch and bound.^[50]

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^[51] and within paths^[52] to detect malicious processes, or on the edge level^[53] to detectlateral 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,^[54] interconnecting District Metered Areas(DMAs) to improve the forecasting capacity. Other application of this algorithm on water distribution modelling is the development of metamodels.^[55]

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.^[56]

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.^[57]

• A Gentle Introduction to Graph Neural Networks

• Neural network architectures
• Semisupervised learning
• Supervised learning
• Unsupervised learning
• Artificial neural networks
• Graph algorithms
• 2009 in artificial intelligence

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from July 2025
• Articles containing potentially dated statements from 2022
• All articles containing potentially dated statements