Graph neural networks (GNNs) are a class of artificial neural networks designed for tasks whose inputs are graphs, such as molecular structures, social networks, or citation networks. Unlike standard neural networks that assume fixed-size, ordered inputs, GNNs operate on graphs of arbitrary size and topology. Because graphs generally have no canonical node ordering, GNN architectures are typically designed to be permutation equivariant: reordering the input nodes reorders the corresponding node representations in the same way. For graph-level prediction tasks, GNNs use a permutation-invariant readout function, ensuring the output is unchanged by node ordering.
The key design element of GNNs is pairwise message passing, where nodes iteratively update their representations by exchanging information with neighbors. This allows the network to capture both local and global structural information. A prominent application is molecular drug design, where molecules are represented as graphs with atoms as nodes and bonds as edges, often including chemical properties as features. Graph-level tasks include predicting the efficacy of a molecule for a specific medical use, such as eliminating E. coli bacteria. GNNs have also been applied in natural language processing, social network analysis, physics, and NP-hard combinatorial optimization.
Historical Development
The concept of applying neural networks to graph-structured data emerged in the late 1990s and early 2000s. Early work by researchers such as Franco Scarselli and colleagues introduced recursive neural networks for graphs, which processed graph structures in a recurrent manner. Around the same time, convolutional approaches were developed, leading to the first graph convolutional networks. These early architectures laid the foundation for modern GNNs, which have evolved through contributions from many academic and industrial research groups.
A significant milestone was the introduction of message passing neural networks (MPNNs) in 2017, which unified many existing GNN variants under a common framework. Since then, numerous architectures have been proposed, each implementing different flavors of message passing. A 2022 position paper argued that many architectures described as going "beyond" message passing can instead be interpreted as message passing over suitably modified graphs, coining the term "augmented message passing" for such approaches.
Architecture
The architecture of a generic GNN typically includes three fundamental types of layers: permutation-equivariant layers, local pooling layers, and global pooling layers. Permutation-equivariant layers, often implemented via message passing, update node representations by aggregating messages from immediate neighbors. Each such layer increases the receptive field by one hop, allowing nodes to incorporate information from farther parts of the graph.
Local pooling layers coarsen the graph via downsampling, similar to pooling in convolutional neural networks for images. Examples include k-nearest neighbors pooling, top-k pooling, and self-attention pooling. Global pooling layers, also known as readout layers, produce a fixed-size representation of the entire graph and must be permutation invariant. Common readout functions include element-wise sum, mean, or maximum.
Standard message-passing GNNs are at most as expressive as the Weisfeiler-Lehman graph isomorphism test, meaning there exist distinct graph structures that cannot be distinguished by such networks. More powerful GNNs operating on higher-dimensional geometries, such as simplicial complexes, have been proposed. As of 2022, whether future architectures will overcome the message passing primitive remains an open research question.
Message Passing Layers
Message passing layers are the core of most GNNs. Formally, they can be expressed as message passing neural networks (MPNNs). Given a graph G = (V, E) with node features x_u and edge features e_uv, an MPNN layer updates each node's representation h_u using a differentiable function φ and a message function ψ:
h_u = φ(x_u, ⊕_{v∈N_u} ψ(x_u, x_v, e_uv))
Here, N_u denotes the neighborhood of node u, and ⊕ is a permutation-invariant aggregation function such as sum, mean, or max. The message function ψ computes a message from each neighbor, and the aggregation combines these messages. The update function φ then combines the node's own features with the aggregated messages to produce the new representation.
Different GNN architectures vary in how they define ψ and φ. For example, graph convolutional networks (GCNs) use a simple normalized sum of neighbor features, while graph attention networks (GATs) employ attention mechanisms to weight neighbor contributions. These variations allow GNNs to capture different aspects of graph structure.
Geometric Deep Learning
GNNs are part of the broader field of geometric deep learning, which aims to generalize neural networks to non-Euclidean domains. In this context, many existing architectures can be interpreted as GNNs operating on suitably defined graphs. For instance, a convolutional neural network layer in computer vision can be viewed as a GNN applied to graphs where nodes are pixels and edges connect adjacent pixels. Similarly, a Transformer (architecture) layer in natural language processing can be seen as a GNN applied to complete graphs whose nodes are words or tokens in a passage of text.
This perspective has led to cross-pollination between fields. Techniques developed for GNNs, such as attention mechanisms, have influenced transformer architectures, and insights from transformers have informed GNN design. The unified view of geometric deep learning has been articulated by researchers including Michael Bronstein and Joan Bruna, among others.
Applications
GNNs have found applications across a wide range of domains. In molecular biology and chemistry, they are used for drug discovery, protein function prediction, and materials design. For example, GNNs can predict molecular properties or generate novel molecules with desired characteristics. In social networks, GNNs power recommendation systems, community detection, and link prediction. Citation networks, where papers are nodes and citations are edges, benefit from GNNs for topic classification and impact prediction.
In physics, GNNs model particle interactions and simulate dynamical systems. They are also applied to NP-hard combinatorial optimization problems, such as the traveling salesman problem or graph coloring, where they can learn heuristics. In natural language processing, GNNs are used for semantic parsing, relation extraction, and knowledge graph reasoning. Additionally, GNNs have been employed in computer vision for scene graph generation and point cloud processing.
Software Libraries
Several open-source libraries implement GNNs, making them accessible to researchers and practitioners. PyTorch Geometric, built on PyTorch, is one of the most widely used libraries, offering a rich collection of GNN layers and datasets. TensorFlow GNN provides similar functionality for the TensorFlow ecosystem. The Deep Graph Library (DGL) is framework-agnostic, supporting both PyTorch and TensorFlow. For users of JAX, jraph offers GNN primitives. In the Julia language, GraphNeuralNetworks.jl and GeometricFlux.jl provide GNN implementations.
These libraries have accelerated research and deployment of GNNs by providing efficient implementations of message passing, pooling, and readout operations. They also include utilities for handling graph data, such as batching and data loading, which are essential for training on large graphs.
Challenges and Future Directions
Despite their success, GNNs face several challenges. One major issue is scalability, as message passing over large graphs can be computationally expensive. Techniques such as graph sampling and mini-batch training have been developed to address this. Another challenge is oversmoothing, where repeated message passing causes node representations to become indistinguishable, limiting the depth of GNNs.
Expressiveness is another active area of research. Since standard GNNs are limited by the Weisfeiler-Lehman test, researchers have explored higher-order GNNs, graph transformers, and architectures that operate on simplicial complexes or hypergraphs. These approaches aim to capture more complex structural information. As of 2022, the question of whether message passing will remain the dominant paradigm is open, with ongoing work on augmented message passing and alternative primitives.
Interpretability and robustness are also important. Understanding what GNNs learn and making them robust to adversarial attacks on graphs are active research topics. As GNNs are increasingly deployed in high-stakes domains like healthcare and autonomous systems, addressing these challenges will be crucial for their broader adoption.