Graph neural network

Graph convolutional network

The graph convolutional network (GCN) was first introduced by Thomas Kipf and Max Welling in 2017.^[10]

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}}$.^[10] 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.

Graph attention network

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

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

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}}$.

Gated graph sequence neural network

The gated graph sequence neural network (GGS-NN) was introduced by Yujia 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 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.

Differentiable pooling

Differentiable pooling, or DiffPool, is a node-clustering pooling method introduced in 2018.^[41] Instead of selecting a subset of the original nodes, DiffPool learns a soft assignment of nodes to clusters (by using scores between 0 and 1). These clusters become the nodes of the coarsened graph used by the next GNN layer.

Given a node-feature matrix ${\displaystyle \mathbf {X} }$ and an adjacency matrix ${\displaystyle \mathbf {A} }$, DiffPool uses two graph neural networks. One computes updated node embeddings,

${\displaystyle \mathbf {Z} =\operatorname {GNN} _{\mathrm {embed} }(\mathbf {X} ,\mathbf {A} )}$

and the other computes an assignment matrix,

${\displaystyle \mathbf {S} =\operatorname {softmax} (\operatorname {GNN} _{\mathrm {pool} }(\mathbf {X} ,\mathbf {A} ))}$

where ${\displaystyle S_{ij}}$ denotes the soft assignment of node ${\displaystyle i}$ to cluster ${\displaystyle j}$. The coarsened node-feature matrix and adjacency matrix are then computed as

${\displaystyle \mathbf {X} '=\mathbf {S} ^{T}\mathbf {Z} }$

${\displaystyle \mathbf {A} '=\mathbf {S} ^{T}\mathbf {A} \mathbf {S} }$

In this formulation, each new node in ${\displaystyle \mathbf {X} '}$ represents a learned cluster of nodes from the previous graph, and edges in ${\displaystyle \mathbf {A} '}$ represent aggregate connectivity between clusters. Because the assignment matrix is differentiable, DiffPool can be trained end-to-end together with the surrounding GNN layers. The original formulation additionally introduced auxiliary losses to encourage nearby nodes to be assigned to similar clusters and to encourage confident cluster assignments.^[41]

Top-k pooling

We first set ${\displaystyle \mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}}$ where ${\displaystyle \mathbf {p} }$ is a learnable projection vector that computes a scalar projection value for each node.

The top-k pooling layer ^[29] 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.^[29]

Self-attention pooling

Using ${\displaystyle \mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )}$ as 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} '=(\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.

Social networks

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

Combinatorial optimization

GNNs are used as fundamental building blocks for several combinatorial optimization algorithms.^[51] Examples include computing shortest paths or Eulerian circuits for a given graph,^[39] deriving chip placements superior or competitive to handcrafted human solutions,^[52] and improving expert-designed branching rules in branch and bound.^[53]

Cyber security

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^[54] and within paths^[55] to detect malicious processes, or on the edge level^[56] to detect lateral movement.

Water distribution networks

Water distribution systems can be modeled as graphs. GNNs have been applied to water demand forecasting,^[57] interconnecting District Metered Areas (DMAs) to improve the forecasting capacity. Another application is the development of metamodels.^[58]

Computer Vision

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

Text and NLP

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

Atomic simulations and materials science

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.^{[citation needed]}

Early GNN architectures for this domain include SchNet (2017), which introduced continuous-filter convolutional layers for learning on 3D molecular structures,^[61] and DimeNet (2020), which incorporated angular information between atoms to improve geometric expressivity.^[62] Subsequent equivariant architectures such as NequIP^[63] and MACE,^[64] 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.^[65] 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 learning interatomic potentials (MLIPs) — models trained across diverse chemical domains rather than on system-specific data. Examples include CHGNet,^[66] M3GNet,^[67] 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.^[68] GNoME, developed by Google DeepMind, applied GNNs to predict the stability of crystal structures, reporting the identification of millions of new stable candidate materials.^[69]