Graph Representation Learning
for Algorithmic Reasoning
Petar Veličković

DL4G@WWW2020
21 April 2020

Problem-solving approaches

Neural networks

Algorithms
Algorithm ﬁgures: Cormen, Leiserson, Rivest and Stein. Introduction to Algorithms.

Problem-solving approaches

Neural networks+++-

Operate on raw inputs
Generalise on noisy conditions
Models reusable across tasks
Require big data
Unreliable when extrapolating
Lack of interpretability

Algorithms++++-

Trivially strongly generalise
Compositional (subroutines)
Guaranteed correctness
Interpretable operations
Inputs must match specNot robust to task variations

Problem-solving approaches

Neural networks+++-

Operate on raw inputs
Generalise on noisy conditions
Models reusable across tasks
Require big data
Unreliable when extrapolating
Lack of interpretability

Algorithms++++-

Trivially strongly generalise
Compositional (subroutines)
Guaranteed correctness
Interpretable operations
Inputs must match spec
Not robust to task variations

Is it possible to get the best ofboth worlds?

Problem-solving approaches

Neural networks+++-

Operate on raw inputs
Generalise on noisy conditions
Models reusable across tasks
Require big data
Unreliable when extrapolating
Lack of interpretability

Algorithms

This talk!
++++-

Trivially strongly generalise
Compositional (subroutines)
Guaranteed correctness
Interpretable operations
Inputs must match spec
Not robust to task variations

Is it possible to get the best ofboth worlds?

Neural Graph-Algorithmic Reasoning●

Can neural nets robustly reason like algorithms?

●Algorithms manipulate (un)ordered sets of objects, and their relations.
⇒ They operate over graphs.
○ Supervise graph neural networks on algorithm execution tasks!

Input●GNNCall this approach neural graph algorithm execution.

OutputWhy?

Benchmarking
graph neural nets

Stronggeneralisation

Multi-task learning

Algorithm
discoveryWhy?

Benchmarking
graph neural nets

Stronggeneralisation

Multi-task learning

Algorithm
discoveryBenchmarking GNNs●

Popular GNN benchmark datasets often unreliableBenchmarking GNNs●

Popular GNN benchmark datasets often unreliable○ Complexity not very highBenchmarking GNNs●

Popular GNN benchmark datasets often unreliable○ Complexity not very high●Algorithms prove very favourable○ Inﬁnite data○ Complex data manipulation○ A clear hierarchy of models emerges!

Benchmarking GNNs●

Popular GNN benchmark datasets often unreliable○ Complexity not very high●Algorithms prove very favourable○ Inﬁnite data
○ Complex data manipulation○ A clear hierarchy of models emerges!

●

A clearly speciﬁed generating function○ No noise in the data
○ Enabling rigorous credit assignment

Benchmarking GNNs●

Popular GNN benchmark datasets often unreliable○ Complexity not very high●Algorithms prove very favourable○ Inﬁnite data
○ Complex data manipulation○ A clear hierarchy of models emerges!

●A clearly speciﬁed generating function○ No noise in the data
○ Enabling rigorous credit assignment●The world is propped-up on polynomial-time algorithms○ Applicable to NP-hard problems (see e.g. Joshi, Laurent and Bresson, NeurIPS’19 GRL)Why?

Benchmarking
graph neural nets

Stronggeneralisation

Multi-task learning

Algorithm
discovery

Strong generalisation●

Learning an algorithm is not learning input-output mapping!

(Graves et al., 2014)

Strong generalisation●Learning an algorithm is not learning input-output mapping!

●

Imitating individual operations enables strong generalisation.
○ Consider how humans devise algorithms “by hand”.
○ Scales to much larger test graph sizes.

Strong generalisation●Learning an algorithm is not learning input-output mapping!

●

Imitating individual operations enables strong generalisation.
○ Consider how humans devise algorithms “by hand”.
○ Scales to much larger test graph sizes.

●Grounds the GNN in the underlying algorithmic reasoning○ Deep learning is about learning representations○ Learn representations of manipulations!Why?

Benchmarking
graph neural nets

Stronggeneralisation

Multi-task learning

Algorithm
discovery

Multi-task learning●Learning representations of manipulations⇒ lots of potential for representational reuse.
○ Many algorithms share subroutines.

Multi-task learning●

Learning representations of manipulations⇒ lots of potential for representational reuse.
○ Many algorithms share subroutines.

●

Representations can positively reinforce one another!
○ Meta-representation of algorithms.
○ Plentiful opportunity for:■ Multi-task learning■ Meta-learning■ Continual learningwith clearly deﬁned task relations!

Multi-task learning●Learning representations of manipulations⇒ lots of potential for representational reuse.
○ Many algorithms share subroutines.

●

Representations can positively reinforce one another!
○ Meta-representation of algorithms.
○ Plentiful opportunity for:■ Multi-task learning■ Meta-learning■ Continual learningwith clearly deﬁned task relations!

●

Output of easier algorithm can be used as input for a harder one.

Why?

Benchmarking
graph neural nets

Stronggeneralisation

Multi-task learning

Algorithm
discoveryAlgorithm discovery●

Inspecting intermediate outputs of an algorithm can decode its behaviour!

●

Opportunity for deriving novel algorithms, e.g.
○ Improved heuristics for intractable problems.
○ Optimising for GNN executors (e.g. GPU/TPU).

Algorithm discovery●

Inspecting intermediate outputs of an algorithm can decode its behaviour!

●

Opportunity for deriving novel algorithms, e.g.
○ Improved heuristics for intractable problems.
○ Optimising for GNN executors (e.g. GPU/TPU).

●

Machine learning ← Competitive programming!
○ My way into computer science :)Algorithm discovery●Inspecting intermediate outputs of an algorithm can decode its behaviour!

●Opportunity for deriving novel algorithms, e.g.
○ Improved heuristics for intractable problems.
○ Optimising for GNN executors (e.g. GPU/TPU).

●Machine learning ← Competitive programming!
○ My way into computer science :)●Conjecture: Can perform soft subroutine reuse from polynomial-time algorithms.

Programming language hierarchy
High level

Middle level

Low level

GNN-Algorithmic hierarchy(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)Algo-level(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

Step-level(Yan, Swersky, Koutra, Ranganathan and Hashemi. 2020)

Unit-level

GNN-Algorithmic hierarchy(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)●●●Learns an algorithm end-to-end only
Strong theoretical link between generalisation power and algorithmic alignment
GNNs align well with dynamic programming!

Algo-level(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)●●●Supervises on atomic steps of an algorithm
Out-of-distribution testing of various GNNs
Multi-task learning + maximisation aggregators generalise stronger!

Step-level(Yan, Swersky, Koutra, Ranganathan and Hashemi. 2020)●●●Learns to execute tiny operations, then composes them
Binary encoding and conditional masking
Achieves perfect strong generalisation!

Unit-level

GNN-Algorithmic hierarchy(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)

Algo-level(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

Step-level(Yan, Swersky, Koutra, Ranganathan and Hashemi. 2020)

Unit-level(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)

What Can Neural Networks Reason About?
●Which networks are best suited for certain types of reasoning?
○ Theorem: better structural alignment implies better generalisation!
○ GNNs ~ dynamic programming

Architectures under study
MLPs~ feature extraction

Deep Sets (Zaheer et al., NeurIPS 2017)~ summary statistics

GNNs~ (pairwise) relations(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)

Empirical results(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)

GNN-Algorithmic hierarchy(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)

Algo-level(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

Step-level(Yan, Swersky, Koutra, Ranganathan and Hashemi. 2020)

Unit-level

Neural Execution of Graph Algorithms(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

Supervise on appropriate output values at every step.

Bellman-Ford algorithm

Message-passing neural network

Components of the executor●

Encoder network*●

Processor network●

Decoder network*●

Termination network*●Repeat as long as*algorithm-speciﬁc●Hypothesis: MPNN-max is a highly suitable processor(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

Evaluation(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)●

Evaluate on parallel and sequential algorithms.
○ Parallel: Reachability (BFS), Shortest paths (Bellman-Ford)○ Sequential: Minimal spanning trees (Prim)○ Explicit inductive bias on sequentiality (learnable mask!)●Generate graphs from a wide variety of distributions:○ Ladder, Grid, Tree, 4-Caveman, 4-Community, Erdős-Rényi, Barabási-Albert○ Attach random-valued weights to each edge

●Study the “human-programmer” perspective: test generalisation from small graphs (20nodes) to larger graphs (50/100 nodes).

●Learn to execute BFS and Bellman-Ford with same processor!

(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

Evaluation: Shortest paths (+ Reachability)

Trained on 20-node graphs!
Trained without reachability objective

Trained without step-wise supervisionEvaluation: Sequential execution

The sequential inductive bias is very helpful!

(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

GNN-Algorithmic hierarchy(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)

Algo-level(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)

Step-level(Yan, Swersky, Koutra, Ranganathan and Hashemi. 2020)

Unit-level

Neural Execution Engines(Yan, Swersky, Koutra, Raganathan and Hashemi. 2020)●Teach a neural net to strongly perform tiny tasks (e.g. sum, product, argmin)○ Compose tasks to specify algorithms○ The building blocks must stay robust with long/OOD rollouts!

●Key components:○ Bitwise embeddings○ Transformers○ Conditional masking

(Yan, Swersky, Koutra, Raganathan and Hashemi. 2020)

Learning to selection sort by composing argmin

(Yan, Swersky, Koutra, Raganathan and Hashemi. 2020)

Learning to selection sort by composing argmin

Composing subroutines (Dijkstra)(Yan, Swersky, Koutra, Raganathan and Hashemi. 2020)

Recursive subroutines (Merge sort)(Yan, Swersky, Koutra, Raganathan and Hashemi. 2020)

Conclusions●Algorithmic reasoning is an exciting novel area for graph representation learning!
○ Three concurrent works explore it at different levels:■ Algo-level (Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)■ Step-level (Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)■ Unit-level (Yan, Swersky, Koutra, Raganathan and Hashemi. 2020)●Many questions left to be answered, at all levels of the hierarchy!
○ <Your contribution here/>Thank you!
Questions?
petarv@google.com | https://petar-v.com
In collaboration with Charles Blundell, Raia Hadsell, Rex Ying, Matilde Padovano,Lars Buesing, Matt Overlan, Razvan Pascanu and Oriol Vinyals