---
id: TECH-GNN-001
title: "Graph Neural Networks"
alternative_names:
  - "GNN"
  - "Graph Networks"
  - "Message-Passing Neural Networks"
category: "Technical → Neural Architectures"
volume: III
chapter: 18
entry_type: "Technical Article"
level: 3
status: "Draft"
last_reviewed: 2026-10-15
version: "0.1.0"
prerequisites:
  - "TECH-NN-001"
related_entries:
  - "TECH-ARCH-001"
  - "TECH-CNN-001"
  - "TECH-RNN-001"
  - "TECH-DL-001"
  - "APP-SCI-001"
---

# Graph Neural Networks

## 1. Concise Definition
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.

## 2. Overview & Significance
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](../vol07_applications/APP-SCI-001_ai_in_science.md)). 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.

## 3. Historical Development
Scarselli et al. (2009) introduced a "graph neural network model" 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. Technical / Conceptual Explanation

### 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)$:

$$m_v^{(k)} = \bigoplus_{u \in \mathcal{N}(v)} \psi\big(h_v^{(k-1)}, h_u^{(k-1)}, e_{uv}\big), \qquad h_v^{(k)} = \phi\big(h_v^{(k-1)}, m_v^{(k)}\big),$$

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
$$H^{(l+1)} = \sigma\!\big(\tilde D^{-1/2}\,\tilde A\,\tilde D^{-1/2} H^{(l)} W^{(l)}\big),\quad \tilde A = A + I,$$
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.

## 5. Types, Components & Classifications
- **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](./TECH-ARCH-001_transformer_architecture.md) 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).

## 6. Applications & Concrete Examples
**Deployed.** PinSage, a GraphSAGE-style model, was built and deployed at Pinterest on a graph the authors report as roughly 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.

## 7. Advantages, Limitations & Unresolved Questions
**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.

## 8. Current State of Knowledge
As of 2026-10-15, 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.

## 9. Future Trajectory & Strategic Outlook
**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.

## 10. Related Entries & Knowledge Graph
- **Foundational Concepts**:
  - [[TECH-NN-001] Artificial Neural Networks](./TECH-NN-001_artificial_neural_networks.md): Layers, parameters and training that GNNs build on.
  - [[TECH-ML-001] Machine Learning](./TECH-ML-001_machine_learning.md): Supervised, semi-supervised and inductive learning settings.
- **Related Methods & Technologies**:
  - [[TECH-CNN-001] Convolutional Neural Networks](./TECH-CNN-001_convolutional_neural_networks.md): The grid-structured special case of local aggregation.
  - [[TECH-RNN-001] Recurrent Networks and LSTM](./TECH-RNN-001_recurrent_networks_and_lstm.md): The sequence-structured counterpart.
  - [[TECH-ARCH-001] Transformer Architecture](./TECH-ARCH-001_transformer_architecture.md): Self-attention as aggregation over a fully connected graph.
  - [[TECH-DL-001] Deep Learning](./TECH-DL-001_deep_learning.md): General training and optimisation context.
- **Applications**:
  - [[APP-SCI-001] AI in Science](../vol07_applications/APP-SCI-001_ai_in_science.md): Molecules, materials and weather as graph problems.

## 11. References & Foundational Literature
1. Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009). *The Graph Neural Network Model*. IEEE Transactions on Neural Networks, 20(1), 61–80. https://doi.org/10.1109/TNN.2008.2005605. [Introduces the original GNN model that computes node states by iterating over neighbours.]
2. Kipf, T. N., & Welling, M. (2017). *Semi-Supervised Classification with Graph Convolutional Networks*. International Conference on Learning Representations (ICLR 2017). https://arxiv.org/abs/1609.02907. [Defines the GCN layer and its linear-in-edges cost.]
3. Hamilton, W. L., Ying, R., & Leskovec, J. (2017). *Inductive Representation Learning on Large Graphs*. Advances in Neural Information Processing Systems (NeurIPS 2017). https://arxiv.org/abs/1706.02216. [GraphSAGE: learned aggregators over sampled neighbourhoods for inductive embeddings.]
4. Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). *Neural Message Passing for Quantum Chemistry*. International Conference on Machine Learning (ICML 2017). https://arxiv.org/abs/1704.01212. [Message-passing framework and molecular property prediction.]
5. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). *Graph Attention Networks*. ICLR 2018. https://arxiv.org/abs/1710.10903. [Learned attention weights over graph neighbours.]
6. Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gulcehre, C., Song, F., Ballard, A., Gilmer, J., Dahl, G., Vaswani, A., Allen, K., Nash, C., Langston, V., Dyer, C., Heess, N., Wierstra, D., Kohli, P., Botvinick, M., Vinyals, O., Li, Y., & Pascanu, R. (2018). *Relational inductive biases, deep learning, and graph networks*. arXiv:1806.01261. [Graph network block and the relational-inductive-bias framing.]
7. Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). *How Powerful are Graph Neural Networks?* ICLR 2019. https://arxiv.org/abs/1810.00826. [1-WL bound on message-passing GNNs and the GIN construction.]
8. Li, Q., Han, Z., & Wu, X.-M. (2018). *Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning*. AAAI 2018. https://arxiv.org/abs/1801.07606. [Analysis of GCN as Laplacian smoothing and the over-smoothing problem.]
9. Alon, U., & Yahav, E. (2021). *On the Bottleneck of Graph Neural Networks and its Practical Implications*. ICLR 2021. https://arxiv.org/abs/2006.05205. [Defines over-squashing.]
10. Bronstein, M. M., Bruna, J., Cohen, T., & Veličković, P. (2021). *Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges*. arXiv:2104.13478. [Symmetry-based unification of CNNs, GNNs and attention.]
11. Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., & Leskovec, J. (2018). *Graph Convolutional Neural Networks for Web-Scale Recommender Systems*. Proceedings of the 24th ACM SIGKDD Conference (KDD 2018). https://doi.org/10.1145/3219819.3219890. [PinSage deployment at Pinterest and its reported scale.]
12. Lam, R., Sanchez-Gonzalez, A., Willson, M., Wirnsberger, P., Fortunato, M., Alet, F., Ravuri, S., Ewalds, T., Eaton-Rosen, Z., Hu, W., Merose, A., Hoyer, S., Holland, G., Vinyals, O., Stott, J., Pritzel, A., Mohamed, S., & Battaglia, P. (2023). *Learning skillful medium-range global weather forecasting*. Science, 382(6677), 1416–1421. https://doi.org/10.1126/science.adi2336. [GraphCast results as reported by the authors.]

## 12. Evidential Classification Matrix
| Section / Claim | Evidence Category | Supporting Source | Confidence / Status |
| :--- | :--- | :--- | :--- |
| Message-passing formulation; permutation equivariance of such layers | Established | Gilmer et al. (2017); Battaglia et al. (2018) | High |
| Standard message-passing GNNs bounded by 1-WL; GIN attains the bound | Established (theorem) | Xu et al. (2019) | High |
| GCN layer and linear cost in edges | Established | Kipf & Welling (2017) | High |
| Over-smoothing and over-squashing as depth/range limits | Well Supported | Li et al. (2018); Alon & Yahav (2021) | Moderate to High; mitigations still debated |
| Production deployment for recommendation | Well Supported (single-organisation report) | Ying et al. (2018) | Moderate |
| GraphCast outperforms an operational system on most targets | Preliminary (single-group report in a peer-reviewed venue) | Lam et al. (2023) | Moderate |
| Relationship of self-attention to GAT on a complete graph | Well Supported | Bronstein et al. (2021) | Moderate |

## 13. Revision History
- **v0.1.0** (2026-10-15): Initial draft. Citations checked against arXiv/Crossref/publisher pages where marked; not independently fact-checked.