Everything is Connected
Deep Learning on Graphs
Petar Veličković
MLinPL x CUAI Cambridge Pre-meeting
30 October 2021

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

Graph neural networks (GNNs)

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

Impactful applications in science and industry

Molecules are graphs!
●A very natural way to represent molecules is as a graph○ Atoms as nodes, bonds as edges○ Features such as atom type, charge, bond type...

GNNs for molecule classification●

Interesting task to predict is, for example, whether the molecule is a potent drug.
○ Can do binary classiﬁcation on whether the drug will inhibit certain bacteria. (E.coli)○ Train on a curated dataset for compounds where response is known.

GNNMoleculeInhibits E.coli?

Follow-up study●Once trained, the model can be applied to any molecule.
○ Execute on a large dataset of known candidate molecules.
○ Select the ~top-100 candidates from your GNN model.
○ Have chemists thoroughly investigate those (after some additional ﬁltering).

●

Discover a previously overlooked compound that is a highly potent antibiotic!

Halicin...Achieve wide acclaim!
Arguably the most popularised success story of graph neural networks to date!

(Stokes et al., Cell’20)

...Achieve wide acclaim!
Arguably the most popularised success story of graph neural networks to date!

(Stokes et al., Cell’20)

...Achieve wide acclaim!
Arguably the most popularised success story of graph neural networks to date!

(Stokes et al., Cell’20)

...Achieve wide acclaim!
Arguably the most popularised success story of graph neural networks to date!

(Stokes et al., Cell’20)

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 DeepMindGlassy dynamics

Impactful applications from DeepMind

Combinatorial optimisation

Impactful applications from DeepMind

Travel-time Prediction in Google MapsEnabling scalable traffic
predictions with GNNsin Google Maps

Traffic maps are graphs!
Transportation maps (e.g. the ones found on Google Maps) naturally modelled as graphs.

Nodes could be intersections, and edges could be roads.

Estimated Time of Arrival (ETA) Prediction●A critical service provided by Google Maps is ETA prediction.
○ Given a start-point and end-point, what is the expected travel time?
○ Important for both users and ride-sharing/delivery companies (using the Maps API).

●Relevant node features: road length, current speeds, historical speeds●Use anonymised, crowd-sourced real-time / historical trafﬁc data.
○ Not as reliable as e.g. physical speed sensors○ Trafﬁc conditions change dynamically and unpredictably○ Most trips between [10min, 1h], requiring near-future predictions

DeepMind’s approach: Graph Nets on Supersegments
Partition candidate route into supersegments, sampled proportionally to (est.) trafﬁc density.

Run a GNN over supersegment graph to estimate ETA (graph regression).

Overall pipeline
Rank candidate routes by predicted ETA, surface information to Google Maps.

Returns
Already deployed worldwide, signiﬁcantly reducing negative ETA outcomes!

I

Getting in on
the action

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-gnnsgraphlearning.io

Getting into it!

●I recently compiled a list of many useful GNN resources in a Twitter thread○ https://twitter.com/PetarV_93/status/1306689702020382720●When you feel ready, I highly recommend Aleksa Gordić’s GitHub repository on GATs:○ https://github.com/gordicaleksa/pytorch-GAT○ Arguably the most gentle introduction to GNN implementations

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

FurtherresourcesFurther insight: graph representation learning
If GNNs are new(ish) to you, I recently gave a useful talk on theoretical GNN foundations:
https://www.youtube.com/watch?v=uF53xsT7mjc

Further insight: bleeding-edge applications
For an in-depth view of bleeding edge applications of GNNs, check out my EEML 2020 talk:https://www.youtube.com/watch?v=fpb3j33RfTc

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