Graph neural networks (GNNs) are a class of artificial neural networks designed for tasks whose inputs are graphs. A graph consists of nodes (vertices) and edges (connections) that can represent entities and their relationships, such as atoms in a molecule or users in a social network. Unlike images or text, graphs do not have a canonical ordering of their nodes, so GNN architectures are typically designed to be permutation equivariant: reordering the nodes in the input reorders the corresponding node representations in the same way. For graph-level prediction tasks, GNNs use a permutation-invariant readout function, whose output is unchanged by node ordering.
The key design element of GNNs is pairwise message passing, where graph nodes iteratively update their representations by exchanging information with their neighbors. This allows the network to capture local structural patterns and dependencies. GNNs have become a cornerstone of machine learning on relational data, with applications spanning deep learning domains such as molecular biology, chemistry, physics, social networks, and natural language processing.
Historical Development
The concept of applying neural networks to graphs emerged in the late 1990s and early 2000s. Early recursive and convolutional approaches laid the groundwork, but the field gained significant momentum in the 2010s with the advent of more powerful computational resources and the success of deep learning in other domains. 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, proposing the term "augmented message passing" for such approaches. This highlights the central role of message passing in GNN design.
Architecture
The architecture of a generic GNN implements several fundamental layers. Permutation-equivariant layers map a representation of a graph into an updated representation of the same graph, typically via message passing. Local pooling layers coarsen the graph through downsampling, increasing the receptive field similarly to pooling in convolutional neural networks. Global pooling layers, also called readout layers, provide a fixed-size representation of the entire graph and must be permutation invariant. Examples of global pooling include element-wise sum, mean, or maximum.
Standard message-passing GNNs are at most as expressive as the Weisfeiler-Leman 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, can be designed. As of 2022, whether future architectures will overcome the message passing primitive remains an open research question.
Message Passing Layers
Message passing layers are permutation-equivariant layers that map a graph into an updated representation of the same graph. Formally, they can be expressed as message passing neural networks (MPNNs). Let G = (V, E) be a graph, where V is the node set and E is the edge set. For a node u in V, let N_u be its neighborhood, x_u its features, and e_uv the features of edge (u, v). An MPNN layer computes an updated node representation h_u as:
h_u = φ(x_u, ⊕_{v∈N_u} ψ(x_u, x_v, e_uv))
where φ and ψ are differentiable functions (e.g., artificial neural networks), and ⊕ is a differentiable, permutation-invariant aggregator such as sum, mean, or maximum. The aggregator combines messages from neighbors, and φ updates the node's representation. Each message passing layer increases the receptive field by one hop, allowing information to propagate across the graph.
Several GNN architectures implement different flavors of message passing. For instance, graph convolutional networks (GCNs) use a simple averaging of neighbor features, while graph attention networks (GATs) employ attention mechanisms to weight neighbor contributions. These variations affect the model's capacity and inductive bias.
Geometric Deep Learning
GNNs are part of the broader subject of geometric deep learning, which seeks to generalize neural network architectures to non-Euclidean domains. In this framework, certain existing architectures can be interpreted as GNNs operating on suitably defined graphs. For example, a convolutional neural network layer in computer vision can be considered a GNN applied to graphs whose nodes are pixels, with edges connecting adjacent pixels. Similarly, a transformer layer in natural language processing can be viewed as a GNN applied to complete graphs whose nodes are words or tokens in a passage of text. This perspective unifies seemingly disparate architectures under a common mathematical framework.
Applications
GNNs have been applied to a wide range of domains. In molecular drug design, molecules are represented as graphs with nodes for atoms and edges for atomic bonds, often including known chemical properties as features. Inputs may vary in size due to different numbers of atoms and bonds. A graph-level task might be to predict the efficacy of a molecule for a specific medical application, such as eliminating E. coli bacteria. GNNs have also been used in social network analysis, citation networks, and recommendation systems. In physics, they can model particle interactions, and in combinatorial optimization, they have been applied to NP-hard problems like the traveling salesman problem.
Implementations and Libraries
Several open-source libraries implement GNNs, making them accessible to researchers and practitioners. PyTorch Geometric is a popular library built on PyTorch, while TensorFlow GNN provides similar functionality for TensorFlow. The Deep Graph Library (DGL) is framework-agnostic, supporting multiple backends. jraph is designed for JAX, and GraphNeuralNetworks.jl and GeometricFlux.jl serve the Julia ecosystem. These libraries offer pre-built layers, pooling operations, and utilities for handling graph data, accelerating development and experimentation.
Challenges and Future Directions
Despite their success, GNNs face several challenges. The expressive power limitation relative to the Weisfeiler-Leman test restricts their ability to distinguish certain graph structures. Scalability to large graphs is another issue, as message passing can be computationally intensive. Research continues on more expressive architectures, such as those using higher-order features or augmented message passing. Additionally, theoretical understanding of GNNs' generalization and robustness is an active area of study. As of 2022, the field is rapidly evolving, with new architectures and applications emerging regularly.