Source-linked AI summary
Everything is Connected: Graph Neural Networks
Petar Veličković
TL;DR
Graphs provide a general representation for natural and artificial relational data, motivating graph representation learning and graph neural networks. The survey organizes core concepts and related model families, concluding that expressive GNN formalisms are broadly powerful while practical choices and supported feature types remain constrained.
Problem
Graph representation learning addresses how to build machine learning models for natural and artificial data whose relevant structure is represented by graphs.
Method
The survey synthesizes foundational GNN concepts, message-passing formalisms, graph-free alternatives, and geometric graph models.
Results
GNN expressive power increases across the surveyed formalisms, and Equation 10 models can be Turing universal under proper initial features, sufficient depth-width product, and suitable ψ and φ.
Takeaways & Limitations
GNNs provide a framework for learning node-, graph-, and edge-level tasks across applications involving graph-structured data.
Takeaways & Limitations
The formalism may be powerful yet difficult to optimize with stochastic gradient descent, and the scalar-feature model does not suffice for vector inputs requiring rotation.
Abstract
from arXiv · showhide
In many ways, graphs are the main modality of data we receive from nature. This is due to the fact that most of the patterns we see, both in natural and artificial systems, are elegantly representable using the language of graph structures. Prominent examples include molecules (represented as graphs of atoms and bonds), social networks and transportation networks. This potential has already been seen by key scientific and industrial groups, with already-impacted application areas including traffic forecasting, drug discovery, social network analysis and recommender systems. Further, some of the most successful domains of application for machine learning in previous years -- images, text and speech processing -- can be seen as special cases of graph representation learning, and consequently there has been significant exchange of information between these areas. The main aim of this short survey is to enable the reader to assimilate the key concepts in the area, and position graph representation learning in a proper context with related fields.
1 Introduction: Why study data on graphs?
Graph representation learning applies machine learning to interconnected data, represented as nodes and edges. Graphs describe natural systems and artificial networks, supporting applications from biology and transportation to recommendations and mathematical discovery.
- Graph neural networks (GNNs) are machine learning models for data represented as interconnected nodes and edges.
- Graphs provide a common representation for organisms and human-made systems, including molecules, brains, transportation networks, and social networks.
- GNNs support applications including antibiotic discovery, travel-time estimation, content and product recommendations, hardware design, and mathematical research.
- Graph-structured representations may also characterize cognition, while Transformers can be understood within the broader context of graph representation learning.
2 The fundamentals: Permutation equivariance and invariance
Graph data are represented with nodes, edges, features, and adjacency matrices, but these matrix representations impose arbitrary node orderings. GNN functions therefore must respect graph symmetries, using local neighborhood operations and permutation-aware mappings.
- A graph G = (V, E) consists of nodes V and edges E specifying connected node pairs.
- Node features xu are stacked into a feature matrix X, while the adjacency matrix A represents the graph’s edges.
- Using matrices imposes an arbitrary node ordering, so permuting nodes and edges must not change graph-level outputs.
- The survey’s simplified functions return graph- or node-level outputs without changing the adjacency matrix.
- GNNs can impose locality by operating on each node’s neighborhood, analogous to CNN operations over local pixel neighborhoods.
- If the local function φ is permutation invariant over neighborhood features, the resulting function F is permutation equivariant.
3 Graph Neural Networks
GNNs use diffusion, propagation, or message passing to learn graph functions across node neighborhoods. Their expressive power increases across model flavours, but practical choices require tradeoffs, and their theoretical universality depends on suitable conditions.
- Message passing, also called diffusion or propagation, is the mechanism used to define local GNN functions.
- The expressive power of GNNs progressively increases from Equation 8 to Equation 10, at the cost of interpretability, scalability, or learning stability.
- The survey does not comprehensively review specific GNN layers, and powerful GNNs may still be difficult to find using stochastic gradient descent.
- GNN layers support node classification, graph classification, and link prediction over biological and molecular graphs.
- Node classification applies a shared classifier to node representations, while graph classification aggregates node representations before classifying the whole graph.
- Link prediction classifies edge representations or predicts whether edges exist, including drug–disease, drug–target, and drug–drug relationships.
- Under proper initial features, sufficient depth-width product, and suitable ψ and φ, Equation 10 GNNs are Turing universal.
4 GNNs without a graph: Deep Sets and Transformers
When no adjacency matrix is available, GNNs can assume no edges, use a fully connected graph, or infer the graph structure. These choices connect Deep Sets and Transformers to graph representation learning.
- Deep Sets: Without an adjacency matrix, the pessimistic choice A = I reduces GNN equations to Deep Sets and exploits no graph-based modelling.Each node uses only its own feature, with Nu = {u}.
- Transformers: A fully connected graph, A = 11⊤, lets a GNN exploit all potential edges and is popular for graphs with few nodes.Convolutional GNNs still reduce to Deep Sets in this setting, motivating stronger architectures.
- Transformers: With a fully connected graph, attentional GNNs reduce to an equation that is essentially a Transformer forward pass.This connection is motivated by interactions between distant words when the task-specific graph is unknown.
- Transformers: Transformers are dominant GNN variants partly because fully connected computations use dense matrix products suited to GPUs and TPUs.Their storage complexity is also more favourable than that of message-passing variants.
- Latent graph inference: Latent graph inference learns a graph structure to supply edges for a GNN, but edge selection is non-differentiable and challenging.Proposed paradigms include nonparametric, supervised, variational, reinforcement, and self-supervised learning.
5 GNNs beyond permutation equivariance: Geometric Graphs
Geometric graphs extend ordinary permutation-based GNNs by incorporating spatial coordinates and requiring equivariance to Euclidean transformations. This framework supports applications such as protein structure modelling while exposing feature-type constraints.
- Geometric graphs: Geometric graphs assign nodes both features and 3D coordinates, motivating equivariance to permutations, rotations, translations, and reflections.Molecules and their three-dimensional conformers are a canonical example.
- E(3)-equivariant GNNs: E(3)-equivariant message-passing layers transform coordinates and features while producing updated features.The framework is designed for geometric graphs rather than discrete unordered graphs alone.
- Equivariance mechanism: Distances remain unchanged under rotations, translations, and reflections, so scalar output features can remain unchanged while coordinates transform accordingly.This invariance under isometries is the key mechanism behind the described model.
- Limitations: The described elegant geometric model only supports scalar features; vector inputs such as atomic forces must rotate with R.A proposed variant explicitly updates vector features to address this constraint.
- Related architectures: Tensor Field Networks and SE(3)-Transformers provide generic roto-translation-equivariant modelling for point clouds and general graphs.These architectures address settings where features become higher-order tensors.
- Applications: Geometric GNN building blocks appear in protein folding, protein design, and protein binding prediction, including AlphaFold 2 and MaSIF.The survey identifies structural biology as a prominent application area for geometric GNNs.