Everything is Connected: Graph Neural Networks

In plain words

Many real systems are naturally networks: molecules are atoms joined by bonds, social networks are people joined by friendships, and road networks are junctions joined by roads. A graph neural network is a model that learns from data of this shape, by letting each item look at its neighbours and combine what it sees.

This short survey argues that most of these models follow one recipe, and that other popular models, including the Transformer used for language, are special cases of it. The author also explains how the recipe must be designed so that it does not depend on how the nodes happen to be numbered. The last part covers graphs whose nodes sit in 3D space, such as atoms in a molecule, where the model must also not change when the whole structure is rotated or moved.

TL;DR

• A survey, not a method. It presents graph neural networks (GNNs) as one message-passing recipe with three spatial flavours §3.
• The output must not depend on how nodes are numbered: invariance for graph-level outputs, equivariance for node-level outputs §2 eq. 3 eq. 4.
• Convolutional, attentional and message-passing layers differ in how they weigh neighbours. Expressive power grows in that order, at a cost in interpretability, scalability or stability §3 eq. 8 eq. 9 eq. 10.
• On a complete graph, the attentional form is a Transformer forward pass §4 eq. 11.
• For 3D graphs, E(3)-equivariant layers use only distances between nodes, plus an explicit update for vector features §5 eq. 12 eq. 13 eq. 14.
• No experiments and no numbers of its own. All headline results are cited from other work.

Problem

Graph-structured data has no fixed node order, so a model over it must give the same answer for any relabelling of the nodes §2. The paper frames the task as learning functions over a graph given a node feature matrix and an adjacency structure §2. It also asks whether message-passing GNNs can represent all permutation-equivariant functions over graphs. It gives two opposing results: some limits on expressiveness §3 and a Turing-universality result under conditions §3. The paper does not settle the question and gives its own view §3.

Method

This is a survey. The method section below restates the framework it presents.

1. Setting §2. A graph has nodes V and edges E. Each node u has a feature vector x_u. The features are stacked into a node feature matrix X with one row per node eq. 1. The graph is written as an adjacency matrix A, where entry (u, v) is 1 when the nodes are linked eq. 2. The paper deliberately leaves out edge features, saying the conclusions would be the same with them §2.

2. Symmetry requirement §2. Reordering the nodes by a permutation matrix P changes X to PX and A to PAPᵀ. A graph-level function f must return the same value under this change (invariance) eq. 3. A node-level function F must permute its output in the same way (equivariance) eq. 4. The paper assumes the functions do not change the adjacency.

3. Locality §2. A GNN works on a neighbourhood N_u of each node. The neighbourhood is the set of nodes linked to u in either direction eq. 5. The features of these neighbours form a multiset eq. 6. A local function φ takes the node's own features and this multiset to give its new representation h_u eq. 7. The paper states that if φ is invariant to the order of the neighbours, the stacked output is equivariant. It calls this simple linear algebra and gives no proof §2.

4. Three spatial flavours §3. Each flavour has the form of a local function φ applied to the node and an aggregate of messages from its neighbours. ψ and φ are neural networks, and the aggregator is any permutation-invariant operation such as a sum, an average or a maximum §3.

• Convolutional: each neighbour's message is ψ of its features, scaled by a fixed coefficient c_vu eq. 8.
• Attentional: the scale is a learned function a of the two endpoints' features eq. 9.
• Message-passing: the message is ψ of both endpoints' features eq. 10.

The paper lists representative models for each flavour §3. Convolutional: ChebyNet, GCN and SGC. Attentional: MoNet, GAT and GATv2. Message-passing: interaction networks, MPNN and graph networks.

# Spatial GNN layer, three flavours  [§3] [eq. 8] [eq. 9] [eq. 10]
# Input:  features (N, k); neighbours[u] = nodes linked to u  [§2] [eq. 5]
# Output: updated features (N, d)

def gnn_layer(features, neighbours, message, update, aggregate):
    # Build the new representation for every node  [§3]
    new_features = []
    for u in all_nodes:
        # One message per neighbour; its form depends on the flavour:
        # convolutional c_vu * psi(x_v), attentional a(x_u, x_v) * psi(x_v),
        # message-passing psi(x_u, x_v)  [§3] [eq. 8] [eq. 9] [eq. 10]
        messages = [message(features[u], features[v])
                    for v in neighbours[u]]
        # Combine messages with a permutation-invariant aggregator  [§3]
        pooled = aggregate(messages)
        # Update the node from its own features and the pooled messages  [§3]
        new_features.append(update(features[u], pooled))
    return stack(new_features)

5. Tasks §3. The paper maps the layer to three tasks.

• Node classification: a shared classifier on each h_u. The output is equivariant §3.
• Graph classification: first aggregate all h_u into one vector, then classify it. The output is invariant §3.
• Link prediction: a classifier over the concatenation h_u ‖ h_v, optionally with edge features §3.

6. Expressiveness §3. The paper says the message-passing form is likely enough, provided the graph itself is changed where needed. It also cites a result that, under suitable initial features, enough depth-width product and suitable ψ and φ, these GNNs are Turing universal §3. The author gives this as personal opinion, and notes that a powerful GNN need not be easy to find with gradient descent §3.

7. Without an input graph §4. When no graph is given, there are two extremes. Setting A to the identity (no edges) reduces every flavour to a Deep Sets model applied to each node §4. Setting A to all ones (a complete graph) lets the network use every pair of nodes. The paper says convolutional layers still reduce to Deep Sets in that case, and attentional layers become the following equation §4 eq. 11:

# Attentional GNN on a complete graph = Transformer layer  [§4] [eq. 11]
# Input:  features x (N, k); attention a; psi and phi networks
# Output: updated features (N, d)

def complete_graph_layer(features, attention, psi, phi):
    # Every node attends to every node, so the neighbourhood is all nodes  [§4]
    new_features = []
    for u in all_nodes:
        # Weighted sum of the psi-transformed features of all nodes  [§4]
        weights = [attention(features[u], features[v]) for v in all_nodes]
        pooled = sum(weights[v] * psi(features[v]) for v in all_nodes)
        new_features.append(phi(features[u], pooled))
    return stack(new_features)

The paper says a complete graph allows the computation to be written as dense matrix products, which suit GPUs and TPUs, and that its storage cost is more favourable than the message-passing form §4. It concludes that Transformers are GNNs on a complete graph §4.

8. Latent graph inference §4. A GNN can also learn the edges it uses. The paper says edge selection is not differentiable and lists several families of solutions: nonparametric, supervised, variational, reinforcement learning and self-supervised §4. It gives no method details.

9. Geometric graphs §5. Nodes carry features f_u and 3D coordinates x_u. The model should be unchanged by rotations, translations and reflections, the group E(3) §5. The paper gives an E(n)-equivariant layer §5 eq. 12 eq. 13. The feature update uses only the squared distance between nodes. The coordinate update moves each node along the difference vectors to its neighbours.

# E(n)-equivariant message-passing layer  [§5] [eq. 12] [eq. 13]
# Input:  features f (N, d); coordinates x (N, 3); neighbours[u]
# Output: updated features and coordinates

def en_layer(features, coords, neighbours, psi_f, psi_x, phi):
    new_features = []
    new_coords = []
    for u in all_nodes:
        # Messages use only features and squared distance: rotation,
        # translation and reflection leave these unchanged  [§5] [eq. 12]
        messages = [
            psi_f(features[u], features[v], sq_dist(coords[u], coords[v]))
            for v in neighbours[u]
        ]
        new_features.append(phi(features[u], sum(messages)))
        # Move the coordinate along the difference vectors  [§5] [eq. 13]
        shift = sum(
            (coords[u] - coords[v])
            * psi_x(features[u], features[v], sq_dist(coords[u], coords[v]))
            for v in all_nodes if v != u
        )
        new_coords.append(coords[u] + shift)
    return stack(new_features), stack(new_coords)

For vector features such as forces, the paper gives a variant with an explicit vector update §5 eq. 14. It notes that this form is not enough when many kinds of tensor features are needed. It then points to Tensor Field Networks and SE(3)-Transformers as general characterisations of roto-translation equivariant layers §5.

Hyperparameters

The paper defines no model and no training run, so it gives no tuned values. The table lists the parameters the text names.

Results

The paper reports no experiments and no numerical results of its own §1 §5. The applications below are the paper's own examples, cited to other work. The paper gives no metric, dataset or baseline for any of them.

Paper vs code

No official code.

The paper is a survey and describes no implementation of its own. Its abstract, arXiv metadata and LaTeX source contain no code link. A GitHub repository search for the exact title returned no results. No third-party implementations were used.

Pitfalls

• Survey, not benchmark. Every application in the Results table is a claim the paper cites, not a result of this paper. No numbers can be checked here.
• Opinion stated as fact. The paper says the message-passing formalism is "likely all we need" and calls it the author's opinion §3. Transformers "winning the hardware lottery" §4 and the claim that billions of people use GNN predictions daily §1 are rhetorical and unquantified.
• The invariance argument is not proven. The step from a permutation-invariant neighbourhood function to an equivariant layer is called "simple linear algebra" with no derivation §2.
• The Transformer result depends on a complete graph. The equivalence holds only when every node's neighbourhood is all nodes and the attention function is the one written in eq. 11 §4. The Deep Sets reduction for the convolutional form is said to hold "in this case" and is asserted with "it can be shown" §4.
• Expressiveness is open. The paper cites limits on message passing §3 and a Turing-universality result §3, and it leaves the question open. Do not treat either as settled for a given task.
• Notation in the geometric section is inconsistent. The coordinate-update sum in eq. 13 runs over all nodes v ≠ u, while the feature update in eq. 12 runs over the neighbourhood N_u. The vector variant eq. 14 uses h_u, which the text does not define in that place, and a constant C that is not defined §5.
• Equation numbers are counted from the LaTeX source. The paper uses align environments, and each row is numbered. The numbers used here are the row order in the source eq. 3 to eq. 14. Check them against the compiled PDF before citing them elsewhere.
• Figures. The paper's abstract carries a graphical figure. It is not reproduced here, because figures from papers are not supported on this site.
• Representative lists are not exhaustive. Each model list in §3 is a sample, and the paper says it does not try to give a comprehensive overview of layers.

Lineage

• Builds on: the paper says its exposition follows Bronstein et al. (2021), "Geometric deep learning" §2. Deep Sets (Zaheer et al., 2017) is the reduction for graphs without edges §4. The Transformer (Vaswani et al., 2017) is the reference for the complete-graph case §4. None of these arXiv ids are in this wiki, so none are linked.
• Compared against: the three spatial flavours are compared by expressiveness, interpretability, scalability and stability §3. No experiments compare them.
• Superseded by: not stated.