Abstract
Graph neural networks have driven a series of recent developments in, e.g., drug discovery, recommender systems, and social network analysis. At their core, GNNs are designed to extract numerical representations for each node in a graph, recursively combining representations of neighboring nodes. This tutorial paper covers some popular and influential GNN models, and discusses their applications in different disciplines. We hope this work will help popularize GNNs in the local community, and foster scientific advances in machine learning and data science.
Introduction: Beyond Euclidean Data
Traditional machine learning architectures, such as Multi-Layer Perceptrons (MLPs) and Convolutional Neural Networks (CNNs), are highly effective for data with a fixed, grid-like structure (e.g., images or sequences). However, many real-world phenomena—including molecular structures, power grids, and social networks—are inherently relational and best represented as graphs: sets of nodes and edges with irregular topologies.
Standard ML models often struggle with these datasets because they cannot naturally capture the irregular topologies and relational dependencies of non-Euclidean structures. Graph Neural Networks (GNNs) bridge this gap by learning numerical representations (embeddings) directly from graph data, enabling inference at multiple levels.
Common GNN Tasks
GNNs are typically applied to three main levels of inference:
- Node Classification: Predicting the label of an individual node.
- Relational Inference (Link Prediction): Predicting the existence or type of relationship between nodes.
- Graph Classification/Regression: Predicting a property for an entire graph (e.g., the toxicity of a molecule).
Methodological Paradigms
The paper categorizes GNN architectures into two primary paradigms:
1. Message-Passing GNNs (Spatial)
This is the dominant approach, conceptualizing the graph as a communication network. Nodes iteratively "pass messages" to their neighbors to update their own states.
- GCN (Graph Convolutional Network): Aggregates neighbor information using a weighted sum normalized by node degrees.
- GIN (Graph Isomorphism Network): Designed to be as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test, using injective functions to distinguish different neighborhood structures.
- GAT (Graph Attention Network): Employs self-attention mechanisms to dynamically weigh neighbor importance.
- SGC (Simple Graph Convolution): A simplified linear model that removes non-linearities to enhance speed and interpretability.
2. Spectral GNNs
These models define convolution in the frequency domain using the Graph Laplacian. While mathematically rigorous, early spectral models were computationally expensive. Modern "spectrum-free" approximations, like ChebNet, have made this paradigm more practical.
Theoretical Insights
- The Weisfeiler-Lehman (WL) Connection: A critical theoretical bound for GNNs is their ability to distinguish non-isomorphic graphs. Most GNNs are bounded by the 1-WL test; GIN was specifically engineered to reach this limit.
- Permutation Invariance: To be effective, a GNN's output must be independent of the arbitrary ordering of a node's neighbors. This necessitates the use of symmetric aggregation functions like
sum,mean, ormax. - Transductive vs. Inductive Learning: GNNs often operate in transductive settings, where the model has access to the full graph structure during training but only observes labels for a subset of nodes.
Applications and Field Growth
GNNs have seen explosive adoption across diverse scientific domains, including biomedicine (molecular fingerprints), computer vision (3D point clouds), and NLP (syntactic dependency trees). The research landscape has shifted dramatically in recent years; the volume of GNN literature has grown from fewer than 100 papers in 2015 to over 15,000 annually by 2021.
Future Frontiers
Despite their success, several challenges remain. Explainability is vital for high-stakes applications like medicine, while Temporal Dynamics must be addressed as real-world networks evolve over time. Furthermore, Scalability for massive graphs and the integration of Graph Transformers represent the current cutting edge of the field.
Summary updated