Everything is Connected

Graph Neural Networks from the Ground Up
Petar Veličković
Eastern European Machine Learning Summer School (EEML)
12 July 2021

In this talk:
Neural networks for graph-structured data
(Graph Neural Networks; GNNs)

Graphs are everywhere!

In many ways, graphs are
the main modality of data
we receive from nature.

Graph representation
learning is likely criticalon the path to AGI.

A very hot research topic

GRL is currently experiencing
its “ImageNet” moment

Rich ecosystem of libraries

github.com/rusty1s/pytorch_geometricgraphneural.network

dgl.aigithub.com/deepmind/graph_nets

github.com/deepmind/jraphRich ecosystem of datasets

ogb.stanford.edu

https://pytorch-geometric.readthedocs.
io/en/latest/modules/datasets.html

github.com/graphdeeplearning/benchmarking-gnns

graphlearning.io

1

Fantastic GNNs
in the Wild
(Compressed & updated talk from EEML 2020)

Impactful applications in science and industry

Impactful applications in science and industry

Virtual drug screening

Impactful applications in science and industry

Recommender systems

Impactful applications in science and industry

Chip design (TPUv5)

Impactful applications from DeepMindImpactful applications from DeepMind

Glassy dynamics

Impactful applications from DeepMind

Combinatorial optimisation

Impactful applications from DeepMind

Travel-time Prediction in Google Maps

2Talk roadmap

What will we cover today?
●

Hopefully I’ve given you a convincing argument for why GNNs are useful to study○ For more details and applications, please see e.g. my EEML 2020 talk●My aims for today: empower you to make immediate contributions to GRL○ Followed by Nikola’s Colab tutorial to facilitate implementation!

●Derive GNNs from ﬁrst principles (permutation invariance and equivariance)○ Similar in spirit to my previous talk at Cambridge●Categorise existing GNNs into three spatial “ﬂavours”●

Present interesting open problems at the “bleeding edge”

Agenda●Talk by me on GNN foundations (this talk!)●

Lab session by Nikola Jovanović (right after this talk!)●

Mentoring session on GNNs with me (right after the lab! :) )●Ask questions in #graph-ml-geometric-dl at any point!
○ We’ll do our best to get around to them, either online or ofﬂine :)●Have fun with graphs!

Where do we begin?
●

We will ﬁrst look at graphs without connections (sets)○ Much simpler to analyse○ Most conclusions will naturally carry over to graphs○ Still very relevant! (point clouds / LiDAR)

3

Permutation
invariance andequivarianceLearning on sets: Setup●

For now, assume the graph has no edges (e.g. set of nodes, V).

●Let xi ∈ ℝk be the features of node i.

●

We can stack them into a node feature matrix of shape n x k:●That is, the ith row of X corresponds to xi●Note that, by doing so, we have speciﬁed a node ordering!
○ We would like the result of any neural networks to not depend on this.

What do we want?

What do we want?

What do we want?

Permutations and permutation matrices●It will be useful to think about the operations that change the node order○ Such operations are known as permutations (there are n! of them)○ e.g. a permutation (2, 4, 1, 3) means y1 ← x2, y2 ← x4, y3 ← x1, y4 ← x3.

●To stay within linear algebra, each permutation deﬁnes an n x n matrix○ Such matrices are called permutation matrices○ They have exactly one 1 in every row and column, and zeros everywhere else
○ Their effect when left-multiplied is to permute the rows of X, like so:Permutation invariance●

We want to design functions f(X) over sets that will not depend on the order●

Equivalently, applying a permutation matrix shouldn’t modify the result!

●We arrive at a useful notion of permutation invariance. We say that f(X) is permutation
invariant if, for all permutation matrices P:●One very generic form is the Deep Sets model (Zaheer et al., NeurIPS’17):
where 𝜓 and 𝜙 are (learnable) functions, e.g. MLPs.
○The sum aggregation is critical! (other choices possible, e.g. max or avg)

Permutation equivariance●

Permutation-invariant models are a good way to obtain set-level outputs●

What if we would like answers at the node level?
○ We want to still be able to identify node outputs, which a permutation-invariant
aggregator would destroy!

●We may instead seek functions that don’t change the node order○ i.e. if we permute the nodes, it doesn’t matter if we do it before or after the function!

●

Accordingly, we say that f(X) is permutation equivariant if, for all permutation matrices P:

Important constraint: Locality●

Want signal to be stable under slight deformations of the domain●

Highly beneﬁcial to compose local
operations to model larger-scale ones○○∈𝔊

local ops won’t globally propagate errors
e.g. CNNs with 3 x 3 kernels, but very deep●

Accordingly, we would like to support locality in our layers!

●cf. Fourier Transform vs. Wavelets
What does this mean for sets?

∉𝔊

General blueprint for learning on sets●

Equivariance mandates that each node’s row is unchanged by f. That is, we can think ofequivariant set functions as transforming each node input xi into a latent vector hi:

where 𝜓 is any function, applied in isolation to every node. Stacking hi yields H = f(X).

(remark: this is typically as far as we can get with sets, without assuming or inferring additional structure)

General blueprint for learning on sets●

Equivariance mandates that each node’s row is unchanged by f. That is, we can think ofequivariant set functions as transforming each node input xi into a latent vector hi:

where 𝜓 is any function, applied in isolation to every node. Stacking hi yields H = f(X).
●We arrive at a general blueprint: (stacking) equivariant function(s), potentially with aninvariant tail---yields (m)any useful functions on sets!

Here, ⨁ is a permutation-invariant aggregator (such as sum, avg or max).
(remark: this is typically as far as we can get with sets, without assuming or inferring additional structure)

4

Learning ongraphs

Learning on graphs●

Now we augment the set of nodes with edges between them.
○ That is, we consider general E ⊆ V x V.

●

We can represent these edges with an adjacency matrix, A, such that:●

Further additions (e.g. edge features) are possible but ignored for simplicity.

●

Our main desiderata (permutation {in,equi}variance) still hold!

What’s changed?

What’s changed?

Permutation invariance and equivariance on graphs●The main difference: node permutations now also accordingly act on the edges●We need to appropriately permute both rows and columns of A
○ When applying a permutation matrix P, this amounts to PAPT

●We arrive at updated deﬁnitions of suitable functions f(X, A) over graphs:

Invariance:
Equivariance:Locality on graphs: neighbourhoods●On sets, we enforced equivariance by applying functions to every node in isolation●Graphs give us a broader context: a node’s neighbourhood○ For a node i, its (1-hop) neighbourhood is commonly deﬁned as follows:

N.B. we do not explicitly consider directed edges, and often we assume i ∈ Ni●

Accordingly, we can extract the multiset of features in the neighbourhoodand deﬁne a local function, g, as operating over this multiset: g(xi, XNi).

A recipe for graph neural networks●

Now we can construct permutation equivariant functions, f(X, A), by appropriately applying
the local function, g, over all neighbourhoods:●To ensure equivariance, we need g to not depend on the order of the vertices in XNi○ Hence, g should be permutation invariant!

A recipe for graph neural networks, visualised

General blueprint for learning on graphs

General blueprint for learning on graphs

General blueprint for learning on graphs

General blueprint for learning on graphs

General blueprint for learning on graphs

5Message
passing ongraphs

What’s in a GNN layer?
●As mentioned, we construct permutation-equivariant functions f(X, A) over graphs byshared application of a local permutation-invariant g(xi, XNi).
○ We often refer to f as “GNN layer”, g as “diffusion”, “propagation”, “message passing”●

Now we look at ways in which we can actually concretely deﬁne g.
○ Very intense area of research!

●

Fortunately, almost all proposed layers can be classiﬁed as one of three spatial “ﬂavours”.

The three “flavours” of GNN layers

Convolutional GNN●

Features of neighbours aggregated with ﬁxed weights, cij●

Usually, the weights depend directly on A.
○ ChebyNet (Defferrard et al., NeurIPS’16)○ GCN (Kipf & Welling, ICLR’17)○ SGC (Wu et al., ICML’19)●Useful for homophilous graphs and scaling up○ When edges encode label similarity

Attentional GNN●Features of neighbours aggregated with implicit weights (via attention)●Attention weight computed as ɑij = a(xi, xj)○ MoNet (Monti et al., CVPR’17)○ GAT (Veličković et al., ICLR’18)○ GaAN (Zhang et al., UAI’18)●

Useful as “middle ground” w.r.t. capacity and scale○ Edges need not encode homophily○ But still compute scalar value in each edge

Message-passing GNN●Compute arbitrary vectors (“messages”) to be sent across edges●Messages computed as mij = 𝜓(xi, xj)○ Interaction Networks (Battaglia et al., NeurIPS’16)○ MPNN (Gilmer et al., ICML’17)○ GraphNets (Battaglia et al., 2018)●Most generic GNN layer○ May have scalability or learnability issues○ Ideal for computational chemistry, reasoning and simulation

6

Perspectives
on GNNs

Towards the bleeding edge●

Now I will present and state three areas full of open problems, which can be easily
expressed using the tools we’ve built up so far●This can enable you to make immediate contributions to the area.

●If you’ve read up on graph machine learning before, there’s a good chance you will haveseen at least some of these.

●

Happy to chat about these (or related) open problems at any point :)ILatent GraphInferenceWhat to do when there is no graph?
●So far, we’ve assumed something (seemingly) very innocent: that the graph is given to us!

●

In practice, the given graph may often be suboptimal for the task we’re solving○ For various connectivity querying on graphs, maintaining the right set of edges canmake a difference between linear-time and (amortised) constant-time complexity!

●Taken to the extreme: what to do when there is no graph?
○ Assume we’re given a node feature matrix, but no adjacency○ We’ve seen one “solution” for this already…

Option 1: Assume no edges
Deep Sets (Zaheer et al., NeurIPS’17)

No edges (set)Option 2: Assume all edges
Interaction Nets (Battaglia et al., NeurIPS’16)
Relational Nets (Santoro et al., NeurIPS’17)
Transformers (Vaswani et al., NeurIPS’17)
Let the GNN decide which edges matter!
Using conv-GNNs no longer makes sense.
If we use attentional GNNs we recover:

Does this look familiar?
All edges (fully-connected graph)A note on Transformers
Transformers are Graph Neural Networks!
●●Fully-connected graphAttentional ﬂavour

The sequential structural information is injected throughthe positional embeddings. Dropping them yields afully-connected GAT model.
Attention can be seen as inferring soft adjacency.
See Joshi (The Gradient; 2020).

The “truth” likely lies in between●

Empty graph ignores a potential wealth of information●

Full graph can be hard to scale (quadratic complexity, large neighbourhoods)●

Ideally, we want to infer the adjacency matrix A, then use it as edges for a GNN!

●

Commonly termed “latent graph inference”.

●Choosing edges is a discrete decision -- inherently hard to backpropagate!

Option 3a: Infer edges to use (variational)
Neural Relational Inference (Kipf, Fetaya et al., ICML’18)

Specify prior over edges, use encoder to derive posterior, sample to infer graph (~VAE setup)k-NN graphs●The NRI approach above gives a way to reason about the graph structure probabilistically○ But it still requires running a fully-connected GNN!

●

Ideally, we want to infer a sparse graph without ever doing a dense GNN○ (at least at inference time...)●

The current workhorse of such approaches is the k-nearest neighbour (k-NN) graph○ Each node stores features hi○ Connect it only to its k nearest neighbours in h (e.g. based on Euclidean distance).

●

Open problem: Can we (should we) do better?

Option 3b: Infer edges to use (no learning)
Dynamic Graph CNN (Wang et al., 2018)

Literally take k nearest neighbours to decide edges at every layer, without any new parameters

Option 3c: Infer edges to use (reinforcement learning)
Differentiable Graph Module (Kazi et al., 2020)

Sample (probabilistically) a k-NN graph, optimise downstream performance as RL reward

Option 3d: Infer edges to use (supervised learning)
Pointer Graph Networks (Veličković et al., NeurIPS’20)

Directly supervise the k-NN graph using ground-truth knowledge (e.g. data structure rollouts)

IIGraphIsomorphism
TestingHow powerful are Graph Neural Networks?
●GNNs are a powerful tool for processing real-world graph data
○ But they won’t solve any task speciﬁed on a graph accurately!

●Canonical example: deciding graph isomorphism○ Am I able to use my GNN to distinguish two non-isomorphic graphs? (hG1 ≠ hG2)
○ If I can’t, any kind of task discriminating them is hopeless●We will assess the power of GNNs by which graphs they are able to distinguish.

Weisfeiler-Lehman Test
●Simple but powerful way of distinguishing: pass random hashes of sums along the edges○ Iterate until hashes don’t change.
○ “Possibly isomorphic” if hash histograms are the same.

Let’s run the WL Test!

Let’s run the WL Test!

Let’s run the WL Test!

Let’s run the WL Test!

Let’s run the WL Test!

Weisfeiler-Lehman Test
●Connection to conv-GNNs spotted very early; e.g. by GCN (Kipf & Welling, ICLR’17)●

Untrained GNNs can hence work very well!
○ Untrained ~ random hash●

The test does fail at times, however:GNNs are no more powerful than 1-WL
●Over discrete features, GNNs can only be as powerful as the 1-WL test described before!

GNNs are no more powerful than 1-WL●

Over discrete features, GNNs can only be as powerful as the 1-WL test described before!

●

One important condition for maximal power is an injective aggregator (e.g. sum)

GNNs are no more powerful than 1-WL●

Over discrete features, GNNs can only be as powerful as the 1-WL test described before!

●

One important condition for maximal power is an injective aggregator (e.g. sum)

●Graph isomorphism network (GIN; Xu et al., ICLR’19) proposes a simple,maximally-expressive GNN, following this principle:

Higher-order GNNs
●We can make GNNs stronger by analysing failure cases of 1-WL!
○ Very active area, with many open problems!

Higher-order GNNs●

We can make GNNs stronger by analysing failure cases of 1-WL!

●

For example, just like 1-WL, GNNs cannot detect closed triangles○ This is because, from a GNN’s perspective, all nodes look the same!
○ Can you think of a simple ﬁx?

Higher-order GNNs
●We can make GNNs stronger by analysing failure cases of 1-WL!

●For example, just like 1-WL, GNNs cannot detect closed triangles○ Augment nodes with randomised features (Sato et al., SDM’21)○ Now a node can “see itself” k hops away!

Higher-order GNNs●

We can make GNNs stronger by analysing failure cases of 1-WL!

●

For example, just like 1-WL, GNNs cannot detect closed triangles○ Augment nodes with randomised/positional features (Sato et al., SDM’21)■ Explored by RP-GNN (Murphy et al., ICML’19) and P-GNN (You et al., ICML’19)○ Can also literally count interesting subgraphs (Bouritsas et al., 2020)●Fixing “failure cases” of 1-WL yields many classes of higher-order GNNs

●They can broadly be categorised into three groups:○ Modifying features (as above)○ Modifying the message passing rule; e.g. DGN (Beaini, Passaro et al. (2020))○ Modifying the graph structure; e.g. 1-2-3-GNNs (Morris et al., AAAI’19)

Going beyond discrete features●

What happens when features are continuous? (real-world apps / latent GNN states)○ … the proof for injectivity of sum (hence GINs’ expressivity) falls apartWhich is best? Neither.
●There doesn’t seem to be a clear single “winner” aggregator here…

●In fact, we prove in the PNA paper (Corso, Cavalleri et al., NeurIPS’20) that there isn’t one!

●

The proof is (in my opinion) really cool! (relies on Borsuk-Ulam theorem)●

PNA proposes empirically powerful combination of aggregators for general-purpose GNNs:

III

Geometric
Deep LearningRemark on geometric deep learning●

We used the blueprint of invariances and equivariances to describe GNNs

●In fact, it is remarkably powerful! By combining an appropriate○ Local and equivariant layer speciﬁed over neighbourhoods○ Activation functions○ (Potentially: pooling layers that coarsen the structure)○ Global and invariant layer over the entire domain
we recover many standard architectures (including CNNs and Transformers!)●But also a more general class of geometric deep learning architectures

The “Five Gs” of geometric deep learning

Credits to Michael Bronstein

The “Five Gs” of geometric deep learning

Credits to Michael BronsteinSome architectures of interest

Thank you!
Questions?
petarv@google.com | https://petar-v.com

With many thanks to Will Hamilton, Joan Bruna, Michael Bronstein and Taco Cohen