Graph Neural Networks

A graph neural network (GNN) is a neural network whose input is a graph (a set of nodes, optionally with edges, node features and edge features) and whose computation respects the graph's structure, so that its outputs do not depend on an arbitrary ordering of the nodes. Most GNNs build node representations by repeatedly aggregating information from each node's neighbours, an operation usually called message passing.

Many data sets are relational rather than grid-like or sequential: molecules are atoms joined by bonds, social and citation networks are people or documents joined by links, and meshes used in physical simulation are points joined by edges. Convolutional networks assume a regular grid and recurrent networks assume an ordered sequence; neither fits irregular, variable-size relational data directly. GNNs supply the corresponding architecture family, and are one of the principal examples of building a structural symmetry (here, permutation of nodes) into a model as an inductive bias (Battaglia et al., 2018; Bronstein et al., 2021).

Within the encyclopedia, GNNs matter for three reasons. They are the standard neural approach to learning on molecules and other structured scientific data (see APP-SCI-001 AI in Science). They provide a common formal language in which convolutional, recurrent and attention-based layers can be described as special cases of operations on graphs (Bronstein et al., 2021). And they are a testbed for questions about expressive power that are hard to pose for other architectures.

Scarselli et al. (2009; IEEE Trans. Neural Networks 20(1), January 2009) presented a "graph neural network model" (a GNN model is also credited by Alon and Yahav (2021) to Gori et al. (2005) and Scarselli et al. (2008); those earlier papers are not cited here) in which each node's state is computed by iterating a contraction-style update over its neighbours until a fixed point is reached, and then fed to an output function. Earlier work on recursive neural networks over trees and directed acyclic graphs is the stated lineage of that model.

The modern wave began in 2016–2017. Kipf and Welling (2017) proposed the graph convolutional network (GCN), a simple layer derived as a first-order approximation of spectral graph convolutions, for semi-supervised node classification. Hamilton et al. (2017) introduced GraphSAGE, which learns aggregation functions over sampled neighbourhoods and can therefore produce embeddings for nodes not seen during training (the "inductive" setting). Gilmer et al. (2017) unified several existing models under a message-passing neural network (MPNN) framework and applied it to molecular property prediction. Veličković et al. (2018) added learned attention weights over neighbours (graph attention networks, GAT). Battaglia et al. (2018), a 27-author position paper, generalised these into a "graph network" block that also updates edge and global attributes.

From 2018 the theoretical analysis of expressive power (Xu et al., 2019) and of failure modes such as over-smoothing (Li et al., 2018) and over-squashing (Alon & Yahav, 2021) became a distinct research thread. Bronstein et al. (2021) placed GNNs inside a broader "geometric deep learning" programme organised around symmetry groups.

#4.1 Graph data and permutation symmetry

A graph is $G=(V,E)$ with node features $x_v$ and optionally edge features $e_{uv}$. Let $A$ be the adjacency matrix. A function $f$ on node features is permutation equivariant if relabelling the nodes by a permutation matrix $P$ permutes the outputs in the same way, $f(PX, PAP^{\top}) = P f(X,A)$. A graph-level output must be permutation invariant. Message-passing layers satisfy these properties by construction because they combine neighbours with symmetric (order-independent) operations.

#4.2 Message passing

In the framework of Gilmer et al. (2017), layer $k$ computes, for each node $v$ with neighbourhood $\mathcal{N}(v)$:

where $\bigoplus$ is a permutation-invariant aggregator (sum, mean or max) and $\psi,\phi$ are learned functions, typically small neural networks. After $K$ layers, $h_v^{(K)}$ depends on the $K$-hop neighbourhood of $v$. For graph-level prediction a readout such as $h_G = \rho\big(\{h_v^{(K)}: v\in V\}\big)$ is applied with another invariant pooling function. Parameters are shared across nodes, so the same model applies to graphs of any size.

#4.3 Representative layers

The GCN layer of Kipf and Welling (2017) is

with $\tilde D$ the degree matrix of $\tilde A$ and $W^{(l)}$ a learned weight matrix; its cost is linear in the number of edges. GraphSAGE replaces the fixed normalisation with a learned aggregator over a sampled neighbour subset, which bounds the per-node cost (Hamilton et al., 2017). GAT computes, for each edge, a normalised attention coefficient $\alpha_{vu}=\mathrm{softmax}_u\, e(h_v,h_u)$ and uses it to weight neighbour messages (Veličković et al., 2018).

#4.4 Expressive power

Xu et al. (2019) show that standard message-passing GNNs are at most as discriminative as the one-dimensional Weisfeiler–Leman (1-WL) graph isomorphism test, and that, with injective update and aggregation (the Graph Isomorphism Network, GIN, using sum aggregation), they can reach that bound. Consequently, some non-isomorphic graphs cannot be distinguished by these models regardless of training. This is a mathematical result about a model class, not an empirical tendency.

#4.5 Depth-related failure modes

Li et al. (2018) analyse the GCN as a form of Laplacian smoothing and argue that stacking many layers makes node features of a connected component converge toward indistinguishable values (over-smoothing). Alon and Yahav (2021) identify over-squashing: when information from an exponentially growing receptive field must pass through fixed-size vectors along a few paths, long-range dependencies are compressed and lost. Both are active areas of mitigation research (rewiring, residual connections, global nodes), and neither is fully resolved.

• By task level: node classification, link prediction, and graph classification or regression.
• By layer family: convolutional (GCN-style, fixed neighbour weights), attentional (GAT, learned neighbour weights), and general message-passing (MPNN, with edge-conditioned messages). Battaglia et al. (2018) give the most general "graph network" block, which also carries edge and global state.
• By setting: transductive (all nodes available at training, as in the GCN experiments) versus inductive (new nodes or graphs at test time, as in GraphSAGE).
• By scale strategy: full-graph training versus neighbour sampling (GraphSAGE) or mini-batching on subgraphs for graphs with billions of edges.
• Graph transformers: models that apply self-attention over all nodes, with graph structure injected through positional or structural encodings. Bronstein et al. (2021) discuss self-attention in the transformer as a GAT-style operation on a fully connected graph, which makes the relation to TECH-ARCH-001 Transformer Architecture precise.
• Geometric GNNs: layers that are also equivariant to rotations and translations of 3-D coordinates, used for atoms and meshes; they are one instance of the symmetry-based programme described by Bronstein et al. (2021).

Deployed. PinSage, a graph convolutional model that uses random walks to select and structure each node's neighbourhood (a design related to, but not identical with, GraphSAGE's sampling), was developed and deployed at Pinterest and trained on a graph the authors report as 3 billion nodes and 18 billion edges, to generate item embeddings for recommendation (Ying et al., 2018); the figures are as reported in 2018 and describe that system only.

Published research results. Gilmer et al. (2017) applied MPNNs to molecular property prediction, the quantum-chemistry setting that motivated the framework. Lam et al. (2023) describe GraphCast, which the authors report predicts hundreds of weather variables over 10 days at 0.25-degree global resolution in under one minute and, in their evaluation, outperforms the most accurate operational deterministic system on 90% of 1,380 verification targets; the architecture is graph-based, operating on a mesh representation of the globe. These results are single-group reports (published in Science), and operational use of machine-learned forecasts is a separate matter from the benchmark comparison.

Benchmarks. Citation-network node classification (Kipf & Welling, 2017) remains a common teaching example but is small by current standards.

Other widely cited uses include traffic, knowledge-graph completion and combinatorial optimisation; these are not individually sourced here.

Advantages. Parameter sharing across nodes and permutation symmetry give sample-efficient handling of relational data of variable size. Per-layer cost for sparse graphs is linear in edges (Kipf & Welling, 2017).

Limitations. (1) Expressive power of standard message passing is bounded by 1-WL (Xu et al., 2019). (2) Over-smoothing and over-squashing limit depth and long-range information flow (Li et al., 2018; Alon & Yahav, 2021). (3) Neighbourhood size grows exponentially with depth, making full-batch training on very large graphs costly and motivating sampling (Hamilton et al., 2017). (4) Results depend heavily on how the graph is constructed; when the graph is itself an approximation (for instance, a mesh for a physical field), construction choices matter as much as the layer.

Unresolved. Whether richer message passing, higher-order methods or graph transformers offer the best accuracy-cost trade-off, and how GNNs compare with generic transformers given large data and compute, are open empirical questions; the literature does not show a single dominant design.

As of 2026-10-19, message passing, GCN/GAT/GraphSAGE-style layers and the 1-WL expressiveness bound are standard material in the literature (Well Supported to Established, depending on the specific claim; see section 12). Large-scale deployment is documented for recommendation (Ying et al., 2018) and published for weather forecasting and molecular modelling (Lam et al., 2023; Gilmer et al., 2017). This article does not tabulate current benchmark leaderboards for graph tasks; those change frequently and are not tracked in a stable article. See MODEL-001 for model records where applicable.

Observed trends. Work has moved from small citation graphs toward scientific domains with physical symmetries and toward hybrids with attention. The theoretical programme of Bronstein et al. (2021) frames this as design of architectures around the symmetry of the problem.

Near term (0–3 years). Continued use in scientific modelling and recommendation is the extrapolation of the existing record; no quantitative forecast is registered here.

Medium and long term. Whether graph-specific layers remain a distinct architecture family or are absorbed into general attention-based models is uncertain. This article asserts no forecast; accordingly no FCST- record is attached.

• Foundational Concepts:
  • TECH-NN-001 Artificial Neural Networks: Layers, parameters and training that GNNs build on.
  • TECH-ML-001 Machine Learning: Supervised, semi-supervised and inductive learning settings.
• Related Methods & Technologies:
  • TECH-CNN-001 Convolutional Neural Networks: The grid-structured special case of local aggregation.
  • TECH-RNN-001 Recurrent Networks and LSTM: The sequence-structured counterpart.
  • TECH-ARCH-001 Transformer Architecture: Self-attention as aggregation over a fully connected graph.
  • TECH-DL-001 Deep Learning: General training and optimisation context.
• Applications:
  • APP-SCI-001 AI in Science: Molecules, materials and weather as graph problems.