Graph neural networks (GNNs) are a class of artificial neural networks designed to operate on graph-structured data, where inputs consist of nodes (vertices) and edges (connections) that may lack a canonical ordering. Unlike standard neural networks that assume fixed-size, ordered inputs, GNNs are built to handle graphs of varying sizes and topologies, making them suitable for domains such as molecular chemistry, social network analysis, and combinatorial optimization. The core innovation of GNNs lies in their use of pairwise message passing, where each node iteratively updates its representation by aggregating information from its neighbors, enabling the network to capture local structural patterns and dependencies.
GNNs are typically designed to be permutation equivariant, meaning that reordering the nodes in the input graph results in a corresponding reordering of the node representations produced by the network. For graph-level prediction tasks, such as predicting a property of an entire molecule, GNNs employ a permutation-invariant readout function that aggregates node representations into a single fixed-size output, ensuring the result is unaffected by node ordering. This property is essential because graphs do not have a natural node order, and the network's output should be consistent regardless of how the graph is represented.
Historical Development
The concept of GNNs emerged from earlier work on neural networks for structured data, with foundational ideas dating back to the 1990s. Early approaches, such as recursive neural networks applied to directed acyclic graphs, laid the groundwork for processing graph-like structures. However, the modern formulation of GNNs, based on message passing and permutation equivariance, gained prominence in the 2010s with the rise of deep learning. Researchers at institutions like MIT CSAIL and Stanford AI Lab contributed to the development of architectures that could handle arbitrary graphs, leading to the establishment of GNNs as a distinct subfield within machine learning.
By the late 2010s, GNNs had become a standard tool in deep learning, with numerous variants proposed to improve their expressive power and scalability. The 2022 position paper "Weisfeiler and Leman Go Neural" and similar works formalized the relationship between GNNs and graph isomorphism testing, clarifying their theoretical limitations and inspiring research into more powerful architectures.
Architecture
The architecture of a generic GNN implements several fundamental layers that work together to process graph-structured inputs. These layers include permutation-equivariant layers, local pooling layers, and global pooling layers, each serving a distinct purpose in transforming the graph representation.
Permutation-equivariant layers are the core of GNNs, implemented via pairwise message passing between graph nodes. In a message passing layer, each node updates its representation by aggregating messages received from its immediate neighbors. This process increases the receptive field of the GNN by one hop per layer, allowing the network to incorporate information from progressively larger neighborhoods. The message passing operation can be formally expressed as a function that takes node features, neighbor features, and edge features as inputs, and produces an updated node representation.
Local pooling layers coarsen the graph via downsampling, reducing the number of nodes while preserving important structural information. This is analogous to pooling layers in convolutional neural networks (CNNs) and helps increase the receptive field of the GNN. Common examples include k-nearest neighbors pooling, top-k pooling, and self-attention pooling, each selecting a subset of nodes to retain based on different criteria.
Global pooling layers, also known as readout layers, provide a fixed-size representation of the entire graph. These layers must be permutation invariant, meaning that any permutation of the graph's nodes and edges does not alter the final output. Element-wise sum, mean, and maximum operations are typical choices for global pooling, aggregating node representations into a single vector that can be used for graph-level predictions.
Message Passing Layers
Message passing layers are the defining component of GNNs, implementing permutation-equivariant transformations through a process known as message passing neural networks (MPNNs). Given a graph G = (V, E) with node set V and edge set E, each node u in V has associated features x_u, and each edge (u, v) in E has features e_uv. The neighborhood of a node u, denoted N_u, consists of all nodes v such that (u, v) is an edge in E.
An MPNN layer updates the representation of each node u using a message passing function. The layer computes messages from each neighbor v to u, where the message is a function of the source node features, target node features, and edge features. These messages are aggregated using a permutation-invariant operation, such as sum, mean, or maximum, and then combined with the node's own features through a differentiable update function, typically a neural network. This process can be repeated for multiple layers, allowing information to propagate across the graph.
The design of message passing functions varies across different GNN architectures. Some use simple linear transformations, while others employ more complex attention mechanisms or gated recurrent units. The choice of aggregation operation also affects the network's expressive power and ability to capture different types of structural information.
Expressive Power and Limitations
Standard message-passing GNNs are at most as expressive as the Weisfeiler-Lehman graph isomorphism test, a classical algorithm for determining whether two graphs are isomorphic. This means that there exist distinct graph structures that cannot be distinguished by standard GNNs, as they may produce identical representations for non-isomorphic graphs. This limitation arises from the local nature of message passing, which relies on aggregating information from immediate neighbors and may fail to capture global structural patterns.
To overcome these limitations, researchers have proposed more powerful GNNs that operate on higher-dimensional geometries, such as simplicial complexes or hypergraphs, which can encode higher-order interactions beyond pairwise edges. As of 2022, whether future architectures will fully overcome the message passing primitive remains an open research question, with ongoing work exploring alternative paradigms such as graph transformers and equivariant neural networks.
Applications
GNNs have found applications across a wide range of domains, leveraging their ability to process graph-structured data. In molecular biology and chemistry, molecules are represented as graphs with nodes for atoms and edges for chemical bonds, often including known chemical properties as features. Graph-level tasks include predicting the efficacy of a molecule for a specific medical application, such as eliminating E. coli bacteria, or estimating physical and chemical properties like solubility and toxicity. This makes GNNs valuable tools in drug design and materials science.
In natural language processing, GNNs can be applied to syntactic dependency trees or semantic role graphs, capturing relationships between words in a sentence. They are also used in social network analysis to model user interactions, detect communities, and predict links. Citation networks, where nodes represent papers and edges represent citations, are another common application, enabling tasks such as paper classification and recommendation.
GNNs are also relevant to physics, where they can model particle interactions or simulate dynamical systems, and to NP-hard combinatorial optimization problems, where they can learn heuristics for tasks like graph coloring or traveling salesman problems. The versatility of GNNs has led to their adoption in both academic research and industry applications.
Relationship to Other Neural Network Architectures
In the broader context of geometric deep learning, certain existing neural network architectures can be interpreted as GNNs operating on suitably defined graphs. A convolutional neural network (CNN) layer, commonly used in computer vision, can be considered a GNN applied to graphs whose nodes are pixels, with edges connecting only adjacent pixels. This perspective highlights the shared principles of local connectivity and feature aggregation between CNNs and GNNs.
Similarly, a transformer layer, widely used in natural language processing and large language models, can be viewed as a GNN applied to complete graphs whose nodes are words or tokens in a passage of text. In this interpretation, the attention mechanism in transformers acts as a form of message passing, where each token aggregates information from all other tokens. This connection has inspired research into unifying these architectures and applying insights from GNNs to improve transformer-based models.
Software Libraries and Tools
Several open-source libraries have been developed to facilitate the implementation and deployment of GNNs. PyTorch Geometric, built on the PyTorch framework, provides a comprehensive set of tools for graph data processing and message passing layers. TensorFlow GNN offers similar functionality within the TensorFlow ecosystem. The Deep Graph Library (DGL) is a framework-agnostic library that supports multiple backends, including PyTorch, TensorFlow, and Apache MXNet. For users of Google JAX, jraph provides a lightweight library for graph neural networks. In the Julia programming language, GraphNeuralNetworks.jl and GeometricFlux.jl offer GNN implementations built on the Flux machine learning framework.
These libraries have lowered the barrier to entry for researchers and practitioners, enabling rapid prototyping and experimentation with various GNN architectures. They include implementations of standard message passing layers, pooling operations, and utilities for loading and processing graph datasets, making GNNs accessible to a broad audience.
Future Directions
Research on GNNs continues to evolve, with active areas of investigation including improving expressive power, scalability to large graphs, and robustness to noisy or incomplete data. The development of graph transformers, which combine attention mechanisms with graph structure, represents a promising direction for capturing long-range dependencies. Additionally, there is growing interest in applying GNNs to dynamic graphs, where nodes and edges change over time, and to heterogeneous graphs with multiple types of nodes and edges.
As of the early 2020s, GNNs have become a standard component of the machine learning toolkit, with ongoing contributions from academic institutions and industry research labs. The theoretical understanding of their capabilities and limitations continues to deepen, guiding the design of next-generation architectures that can tackle increasingly complex graph-based problems.