Neural Algorithmic Reasoning
Petar Veličković
PHYS 7332 – Network Data Science 2
Northeastern University
2 April 2021

In this talk:(Classical) Algorithms

In this talk:(Classical) Algorithms

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

In this talk:(Classical) Algorithms(with a bit of neural spice)

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

Overview
Our aim is to address three key questions: (roughly ~20min for each)●

Why should we, as deep learning practitioners, study algorithms?
○ Further, why might it be beneﬁcial to make ‘algorithm-inspired’ neural networks?

●

How to build neural networks that behave algorithmically?
○ And why am I even telling you this in a “Graph Machine Learning” course?

●

Do algorithmic neural networks actually work when deployed?
○ If so, how are they actually being used?

Hopefully, also some ideas on where you might be able to apply the ideas above :)1

Motivation forstudying
algorithms

Why algorithms?
●

Essential “pure” forms of combinatorial reasoning○ ‘Timeless’ principles that will remain regardless of the model of computation○ Completely decoupled from any form of perception**though perception itself may also be expressed in the language of algorithms

Why algorithms?
●

Essential “pure” forms of combinatorial reasoning○ ‘Timeless’ principles that will remain regardless of the model of computation○ Completely decoupled from any form of perception*●

Favourable properties○ Trivial strong generalisation○ Compositionality via subroutines○ Provable correctness and performance guarantees○ Interpretable operations / pseudocode

Why algorithms?
●

Essential “pure” forms of combinatorial reasoning○ ‘Timeless’ principles that will remain regardless of the model of computation○ Completely decoupled from any form of perception*●

Favourable properties○ Trivial strong generalisation○ Compositionality via subroutines○ Provable correctness and performance guarantees○ Interpretable operations / pseudocode●

Hits close to home
○ Algorithms and competitive programming are how I got into Computer Science2

Maximum flow
and theFord-Fulkerson
algorithm

Maximum flow problem●

Flow network: graph G = (V, E), augmented with a capacity function, c: V x V → ℝ+
○ Capacity cuv denotes how much ﬂow is allowed on (u, v) edge●

Two special nodes: source, s, and sink, t○ Source unleashes “inﬁnite” capacity, sink receives “inﬁnite” capacity●

A ﬂow in G is any mapping f: V x V → ℝ+, such that:●

The value of a ﬂow is the total ﬂow emanating from the source:○ We are interested in maximising it!

Max-flow example (f = 17)

Ford-Fulkerson’s Algorithm●

Such a rigorously deﬁned problem often admits remarkably elegant and provably correctalgorithm blueprint!

*representing the capacities that remain after applying f●

Many speciﬁc ways to ﬁnd p yield different algorithms (e.g. Edmonds-Karp, Dinitz, etc…)○ This can be proven to terminate with correct solution

Ford-Fulkerson in action

Ford-Fulkerson in action

Ford-Fulkerson in action

Ford-Fulkerson in action

Ford-Fulkerson in action(the ﬂow may also be returned!)

Final solution!

Max-flow Min-cut theorem
Observing data in this way, also yields easy observation of connections, hence theorems!

3“Fundamentals
of a method forevaluating rail
net capacities”(Harris & Ross, 1955)

The core problem●

Classical algorithms are designed with abstraction in mind, enforcing their inputs toconform to stringent preconditions.
○ Keeping the inputs constrained enables an uninterrupted focus on “reasoning”○ Easily certify the resulting procedure’s correctness, i.e., stringent postconditions●

However, we must never forget why we design algorithms!

●

Unfortunately, this is at timeless odds with the way they are designed○ Let’s study an example from the 1950s.

Original interest in flows

https://apps.dtic.mil/dtic/tr/fulltext/u2/093458.pdf

The Warsaw Pact railway network
Find “the bottleneck”, i.e.
the minimum cut.
As we saw, this is directly
related to computing the
maximum ﬂow.
(this was intuitively assumed byHarris & Ross as well)

The core problem, as seen in 1955

An important issue for the community●

The “core problem” plagues applications of classical combinatorial algorithms to this day!

●

Satisfying their preconditions necessitates converting inputs into an abstractiﬁed form●

If done manually, this often implies drastic information loss
○ Combinatorial problem no longer accurately portrays the dynamics of the real world.
○ Algorithm will give a perfect solution, but in a useless environment●

The data we need to apply the algorithm may be only partially observable○ This can often render the algorithm completely inapplicable.

●

An issue of high interest for both combinatorial and operations research communities.

4

Towards aneurally spiced
solutionAbstractifying the core problem●

Assume we have real-world inputs, but our algorithm only admits abstract inputs○ For now, we assumed manually converting from one input to anotherAbstractifying the core problem●

Assume we have real-world inputs, but our algorithm only admits abstract inputs○ For now, we assumed manually converting from one input to another●

Whenever we have manual feature engineering of raw data, neural nets are attractive!

Attacking the core problem●

First point of attack: “good old deep learning”○ Replace human feature extractor with neural network○ Still apply the same combinatorial algorithm●

First issue: algorithms typically perform discrete optimisation○ This does not play nicely with gradient-based optimisation that neural nets require.

Backpropagating through classical algorithms
Vlastelica et al. (ICLR’20) provide a great approach for differentiating CO solver outputs

Black-box backprop

Algorithmic bottleneck●

Second (more fundamental) issue: data efﬁciency○ Real-world data is often incredibly rich
○ We still have to compress it down to scalar values●

The algorithmic solver:○ Commits to using this scalar○ Assumes it is perfect!

●

If there are insufﬁcient training data to properly estimate the scalars, we hit same issues!
○ Algorithm will give a perfect solution, but in a suboptimal environment

Breaking the bottleneck●

Neural networks derive great ﬂexibility from their latent representations○ They are inherently high-dimensional○ If any component is poorly predicted, others can step in and compensate!

●

To break the bottleneck, we replace the algorithm with a neural network!

P

Encoder

Decoder(The setting naturally aligns with encode-process-decode (Hamrick et al., CSS’18))

Properties of this construction●

Assuming our latent-state NN aligns with the steps of an algorithm, we now have:○ An end-to-end neural pipeline which is fully differentiable○ No scalar-based bottlenecks, hence higher data efﬁciency.

●

How do we obtain latent-state neural networks that align with algorithms?

P

Encoder

Decoder(Have we answered
Question 1?)●

Why should we, as deep learning
practitioners, study algorithms?
○ Further, why might it be beneficial to
make ‘algorithm-inspired’ neuralnetworks?

5

Algorithmic
reasoningAlgorithmic reasoning●

The desiderata for our processor network P are slightly different than usual:○ They are required to imitate the steps of the algorithm faithfully○ This means they must extrapolate!
○ (Related: how to best decide the weights of P to robustly match the algorithm?)●

Neural networks typically struggle in the extrapolation regime!

●

Algorithmic reasoning is an emerging area that seeks to ameliorate this issue○ Primarily through theoretical and empirical prescriptions○ These guide the neural architectures, inductive biases and featurisations that are
useful for extrapolating combinatorially●This is a very active research area, with many key papers published only last year!
○ We will navigate it by an increasingly complex sequence of toy algorithmic problems

Starting simple●●

Input: (ﬂat) representation of an object’s features (e.g. position, shape, color…)
Output: some property of the object (e.g. is it round and yellow?)Starting simple●●

Input: (ﬂat) representation of an object’s features (e.g. position, shape, color…)
Output: some property of the object (e.g. is it round and yellow?)

A canonical problem solvable by a multilayer perceptron (MLP).

Starting simple●●

Input: (ﬂat) representation of an object’s features (e.g. position, shape, color…)
Output: some property of the object (e.g. is it round and yellow?)

A canonical problem solvable by a multilayer perceptron (MLP).
●

A simple universal approximator that makes no assumptions about its input structure.

●

We will now gradually introduce inductive biases as we learn more about our problem.
○ Every step of the way, we will validate our choice theoretically or empirically.
○ N.B. _All_ architectures considered here will be universal approximators!
■ But proper choices of biases will drastically improve learning generalisation.

Summary statistics●●

Input: A set of 1D points, with features containing their coordinate and colour.
Output: Some aggregate property of the set (e.g. the furthest pairwise distance).

(Output: 10)

Summary statistics●●

Input: A set of 1D points, with features containing their coordinate and colour.
Output: Some aggregate property of the set (e.g. the furthest pairwise distance).

A summary statistic problem: requires reasoning about set element boundaries, computing the
maximal and minimal coordinate, and subtracting them.
MLPs have no way of dealing with set boundaries!
Introduce Deep Sets. (Zaheer et al., NeurIPS 2017)

Summary statistics●●

Input: A set of 1D points, with features containing their coordinate and colour.
Output: Some aggregate property of the set (e.g. the furthest pairwise distance).

A summary statistic problem: requires reasoning about set element boundaries, computing the
maximal and minimal coordinate, and subtracting them.
MLPs have no way of dealing with set boundaries!
Introduce Deep Sets. (Zaheer et al., NeurIPS 2017)●●

Permutation-invariant and object-aware!
Can be extended to powerful variants aggregating over subsets at a time
○ See Janossy pooling (Murphy et al., ICLR 2019)

Relational argmax●●

Input: A set of 1D points, with features containing their coordinate and colour.
Output: Some relational property of the set (e.g. the colours of two furthest points)(Output: red and purple)

Relational argmax●●

Input: A set of 1D points, with features containing their coordinate and colour.
Output: Some relational property of the set (e.g. the colours of two furthest points)

A relational argmax problem: requires identifying an optimising (pairwise) relation.
Deep Sets at a disadvantage: output MLP must disentangle all pairwise relations, imposing
substantial pressure on its internal representations. (this will be a common and recurring theme)
Introduce Graph Neural Networks (GNNs). (Scarselli et al., TNN 2009)

Relational argmax●●

Input: A set of 1D points, with features containing their coordinate and colour.
Output: Some relational property of the set (e.g. the colours of two furthest points)

A relational argmax problem: requires identifying an optimising (pairwise) relation.
Deep Sets at a disadvantage: output MLP must disentangle all pairwise relations, imposing
substantial pressure on its internal representations. (this will be a common and recurring theme)
Introduce Graph Neural Networks (GNNs). (Scarselli et al., TNN 2009)●●●

Permutation-invariant, object-aware, and relation-aware!
Directly provides “pairwise embeddings” within its inductive bias
(Powerful paradigm: higher-order relations can be decomposed into multi-step pairwise)Architectures so far
MLPs~ feature extraction

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

GNNs (Scarselli et al., TNN 2009)~ (pairwise) relations

Algorithmic alignment●

At each step, we progressively made stronger assumptions about what kind of reasoning
our problem needed, leading to stronger inductive biases.

●

Under this, “noise-free”, algorithmic reasoning lens, can we formalise what it means for an
inductive bias to be favourable, and prove that it is favourable in some circumstance?

●

Yes!
(Xu, Li, Zhang, Du, Kawarabayashi and Jegelka. ICLR 2020)●

Theorem: better structural alignment implies better generalisation!
○ GNNs ~ dynamic programming(tl;dr: it relies on PAC-like frameworks, using sample complexity as a notion of favourability)

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

Dynamic programming●●

Input: A weighted graph with a provided source node
Output: All shortest paths out of the source node (shortest path tree)Dynamic programming●●

Input: A weighted graph with a provided source node
Output: All shortest paths out of the source node (shortest path tree)

Standard computer science task, solvable by dynamic programming methods (e.g.
Bellman-Ford). Note that, at each step, Bellman-Ford selects an optimal neighbour in each node.
So far, we used the sum aggregator to aggregate GNN neighbourhoods. It is universal, but does
not align with the task (and can lead to exploding signals)!
Introduce the max aggregator.

Dynamic programming●●

Input: A weighted graph with a provided source node
Output: All shortest paths out of the source node (shortest path tree)

Standard computer science task, solvable by dynamic programming methods (e.g.
Bellman-Ford). Note that, at each step, Bellman-Ford selects an optimal neighbour in each node.
So far, we used the sum aggregator to aggregate GNN neighbourhoods. It is universal, but does
not align with the task (and can lead to exploding signals)!
Introduce the max aggregator.
Naturally aligns with many search-like reasoning procedures, has explicit credit assignment,
and is more robust to larger-size out-of-distribution tests!

Empirical validation into max aggregation●

A recent exploration of Transformers studies the effect of alignment on learning stability.
(Richter and Wattenhofer. 2020)●

Specify a case distinction task that clearly aligns with max.

Max is stable under most hyperparameters!

(Richter and Wattenhofer. 2020)

Shortest paths, cont’d●

The GNN will still struggle on the shortest-path task when generalising out-of-distribution!
○ A critical component of proper reasoning systems.

●

It can overﬁt to the distribution of inputs of a particular (training) size, side-stepping theactual procedure it is attempting to imitate.

●

Introducing step-wise supervision.
(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)●

Instruct the GNN computation to respect the intermediate outputs of the algorithm!
(other aspects, such as algorithm multi-task learning, are out-of-scope of this talk)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

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

Evaluation: Shortest paths (+ Reachability)

Trained on 20-node graphs!
Aggregators other than max

Trained without step-wise supervisionSequential algorithms(Veličković, Ying, Padovano, Hadsell and Blundell. ICLR 2020)●

Now consider algorithms such as Prim’s algorithm for minimum spanning trees (MST).

●

This algorithm is inherently sequential: it adds one node at a time to the (partial) MST.

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

Now consider algorithms such as Prim’s algorithm for minimum spanning trees (MST).

●

This algorithm is inherently sequential: it adds one node at a time to the (partial) MST.

Our previous model was forced to produce outputs for every node at every step. But in mostcases, these outputs don’t change, making the system vulnerable to overﬁtting.
Introduce a sequential inductive bias:●●

At each step, select exactly one node to update, leaving all others unchanged.
Can assign a score to every node by shared network, and choose argmax.
○ Optimise using cross-entropy on algorithm trajectories.

Evaluation: Sequential execution

The sequential inductive bias is very helpful!

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

Incremental connectivity task●

Input: (u, v) representing an edge to add●

Queries: are nodes (i, j) connected?

●

Are the input graph edges most relevant?
○●(relatedly: what to do when there is no graph?)

Iterating only over the current graph’s edges leads to linear-time query answering.
b

c

e

h

d

f

g

Connected components with disjoint-set unions
Maintaining a disjoint-set union (DSU) data structure allows answering such queries sublinearly!
b

c

e

h

d

f

g

GNNs with supervised pointer mechanisms●●

Core idea: learn an (auxiliary) graph to be used for a GNN.
○

Derive based on the latent state.

○

A way to provide “global context”, or reﬁne computational graph.

Contrary to prior work, we let each node learn one pointer to another node.
○

Can model (and supervise on!) many inﬂuential data structures;○

Preserves sparsity (O(V) edges used);○

Relies on step-wise predecessor predictions, which we already covered.
(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

Pointers through Transformers(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)●

Compute queries, keys and attention coefﬁcients as usual●

Choose the largest coefﬁcients as new pointers, forming the pointer adjacency matrix:●

Use the (symmetrised) pointer adjacency matrix to form neighbourhoods for the GNN!

●

We optimise coefﬁcients by using cross-entropy on ground-truth state of a data structure.

Masking inductive bias●

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

Efﬁcient data structures are sublinear because they only modify a small fraction of (e.g.
logarithmically many) nodes at once!

Masking inductive bias

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)●

Efﬁcient data structures are sublinear because they only modify a small fraction of (e.g.
logarithmically many) nodes at once!

●

Forcing to update all pointers at once is wasteful (and detrimental to performance!)○ Let’s revisit and generalise our sequential inductive bias!

●

If we know the data structure will only update a subset of pointers at any point, we canlearn to predict this subset mask, µi ﬁrst -- then discard updates to other nodes.
○ This inductive bias proved critical.

Pointer Graph Network (PGN)●(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

Further supervised to answer queries at every point in time.

Overall PGN dataflow(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN Results

Incremental connectivity
Trained without masking objective

Fully dynamic connectivity
Trained on ground-truth pointer graphs

Pointer accuracies(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)●

It appears that our learnt data structure substantially deviates from ground-truths!

●

What did it learn to do?

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

Litmus test: repeated Union(i, i+1)●

To illustrate the pointer structure, let’s consider a toy example with:○ n = 7 nodes○ Sorted ascending by rank
○ Repeatedly calling Union(i, i+1) for all i in [0, n)●

The ground-truth DSU pointers obtained
form a “worst-case”* scenario:●

We will perform a trained PGN rollout.

*not really damaging for DSU, but potentially troublesome for GNNs (large diameter).

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN iterations on Union(i, i+1): initial state(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN iterations on Union(i, i+1): (1, 2)

So far, so good....

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN iterations on Union(i, i+1): (2, 3)

Differs from ground-truth already -- and shallower!
Continuing from here...

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN iterations on Union(i, i+1): (3, 4)

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN iterations on Union(i, i+1): (4, 5)

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN iterations on Union(i, i+1): (5, 6)

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. NeurIPS 2020)

PGN iterations on Union(i, i+1): (6, 7)

We recover a completely valid DSU tree…
...but one which cuts the diameter in half
⇒ more favourable for GNN!
Conditioned entirely through PGN’s hidden state!

Summary
Let’s think back to the inductive biases we’ve introduced, starting from a basic MLP:
●
●
●
●
●
●
●

DeepSets ⇔ object-level;
GNNs ⇔ relational;
Max aggregator ⇔ search-like;
Step-wise imitation ⇔ algorithm-like;
Sequential bias ⇔ one-object-at-a-time;
Pointers ⇔ latent-graph-like;
Masking ⇔ data-structure-like.

For each bias, we had a clear motivation for why we introduced so, and an obvious means of
doing either theoretical or empirical analysis.
None of the biases were too problem-speciﬁc.
In general, when solving a (reasoning) task, ask yourself:●●

What is the kind of reasoning procedure I’d like my neural network to perform?
How to constrain the network to compute (intermediate) results in this manner?

tl;dr of algorithmic reasoning●

Graph neural networks (GNNs) align well with dynamic programming (Xu et al., ICLR’20)●

Interesting inductive biases explored by Veličković et al. (ICLR’20):○ Encode-process-decode from abstract inputs to outputs○ Favour the max aggregation○ Strong supervision on trajectories●

Further interesting work:○ IterGNNs (Tang et al., NeurIPS’20)○ Shufﬂe-exchange nets (Freivalds et al., NeurIPS’19)○ PGN (Veličković et al., NeurIPS’20)○ PMP (Strathmann et al., ICLR’21 SimDL)●

Latest insights: linear algorithmic alignment is highly beneﬁcial (Xu et al., ICLR’21)

Blueprint of algorithmic reasoning

“Learning to Simulate Complex Physics with Graph Networks” (ICML 2020)

Aside: Connection to simulations

Video page: sites.google.com/view/learning-to-simulate

You might’ve come across a very exciting recent body of work for simulating physics with GNNs

Why are simulations of interest
for algorithms?
(a few examples)Physics simulations / collision detectors have algorithms...

… and data structures! (Quadtree / k-d tree)

Numerical integrators? (hence ODEs)
Ultimately, computers cannot really do real numbers...

Simulations of life (Gillespie)A very deep connection
It should come as no surprise that physics-simulating GNNs are largely recommending thesame inductive biases as algorithmic reasoning :)(See also: Kyle Cranmer’s recent guest lecture at USI Lugano)(Have we answered
Question 2?)●

How to build neural networks thatbehave algorithmically?
○ And why am I even telling you this ina “Graph Machine Learning” course?

6

An algorithmic
implicit plannerReinforcement learning (RL) settingReinforcement learning (RL) setting (with planning)Reinforcement learning (RL) setting (variables)
action, a

policy, π(a | s)transitions, P(s’ | s, a)rewards, R(s, a)state, sreward, r ; state, s’Reinforcement learning (RL) setting
action, a

Want to optimise:

Discounted
cumulative rewardG = ∑t≥0 𝛾t rt

policy, π(a | s)transitions, P(s’ | s, a)rewards, R(s, a)state, sreward, r ; state, s’Intro to value iteration●

Value Iteration: dynamic programming algorithm for perfectly solving an RL environment

where v(s) corresponds to the value of state s.
●

Guaranteed to converge to optimal solution (ﬁxed-point of Bellman optimality equation)!

Optimal policy takes actions that maximise expected value: argmaxa ∑s’ V*(s’) P(s’ | s, a)●

BUT requires full knowledge of underlying MDP (P / R)
○ Prime target for our previously studied blueprint :)Algorithmic reasoning over Value Iteration●

How would a human feature engineer make VI applicable?
○ Looking back to our blueprint example…

●

As before, we will try to automate away the manual feature extraction

Latent-space transition models●

Assume we have encoded our state (e.g. with a NN) into embeddings, z(s) ∈ ℝk●

To expand a “local MDP” we can apply VI over, we can then use a transition model, T○ It is then of the form T : ℝk x A → ℝk
○ Optimised such that T(z(s), a) ≈ z(s’)●

Many popular methods exist for learning T in the context of self-supervised learning●

Contrastive learning methods try to discriminate (s, a, s’) from negative pairs (s, a, s~)Using a transition model to expand

We can use a learned transition
model on every action, to be
exhaustive (~breadth-ﬁrst search)
Doesn’t scale with large action
spaces / thinking times; O(|A|K)
Can ﬁnd more interesting rollout
policies, e.g. by distillingwell-performing model-free ones.

TreeQN / ATreeC●

Assume that we have reward/value models, giving us scalar values in every expanded node●We can now directly apply a VI-style update rule!

●

Can then use the computed Q-values directly to decide the policy●

Exactly as leveraged by models like TreeQN / ATreeC (Farquhar et al., ICLR’18)○ Also related: Value Prediction Networks (Oh et al., NeurIPS’17)

TreeQN / ATreeC in action

High-level view●It’s good to take a recap and realise what we have done so far○ We mapped our natural inputs (e.g. pixels) to the space of abstract inputs○ (local MDP + reward values in every node)○ This allowed us to execute VI-style algorithms directly on the abstract inputs

High-level view●It’s good to take a recap and realise what we have done so far○ We mapped our natural inputs (e.g. pixels) to the space of abstract inputs○ (local MDP + reward values in every node)○ This allowed us to execute VI-style algorithms directly on the abstract inputs●

The VI update is differentiable, and hence so is our entire implicit planner.

Breaking the bottleneck●

We hit bottleneck-based data efﬁciency issues again!
○ If there are insufﬁcient training data to properly estimate the scalars…
○ Algorithm will give a perfect solution, but in a suboptimal environment●

To break the bottleneck, we replace the VI update with a neural network!

●

As before, we can use graph neural networks to perform VI-aligning computations.

Algorithmic reasoning●

GNN over state representations aligns with VI, but may put pressure on the planner○ Same gradients used to construct correct graphs and make VI computations●

To alleviate this issue, we choose to pre-train the GNN to perform value iteration-stylecomputations (over many synthetic MDPs), then deploying it within our planner●This exploits, once again, the concept of algorithmic alignment (Xu et al., ICLR’20)

Putting it all together!

XLVIN (Deac et al., NeurIPS’20 DeepRL)XLVIN Components●

Encoder (z: S → ℝk) provides state representations●

Transition (T: ℝk x A → ℝk) simulates effects of actions in latent space○ Pre-trained & Fine-tuned on the TransE loss (observed trajectories)●

Executor (X: ℝk x ℝ|A| x k → ℝk) simulates a planning algorithm (Value Iteration) in latent
space○ Pre-trained to execute VI on synthetic MDPs of interest, then frozen●

Policy / Value Head, computing action probabilities and state-values given embeddings○ Use PPO as the policy gradient method●

The soft executor enables VIN-like models (Tamar et al., NIPS’16) on general MDPs

Results on low-data Atari...why did it work?
●

Recall, our executor network was pre-trained and frozen●

The pixel-level encoder needed to learn to map rich inputs into the executor’s latent space○ Analogous to a human who tries to map real-world problems to algorithmic inputs!

●

We set out to investigate to what extent it succeeded.

Grid-world qualitative study●

We evaluate the quality of the embeddings before and after applying the executor, in agrid-world environment○ Here we can compute optimal V*(s)○ Evaluate linear decodability by linear regression!

●

Results verify our hypothesis!
○ Input values are already predictive○ But the executor consistently
reﬁnes them!

●

Our encoder learnt to correctly map
the input to the latent algorithm! :)(Have we answered
Question 3?)●

Do algorithmic neural networks actuallywork when deployed?
○ If so, how are they actually being
used?

7

Summary andconclusions

Overview, revisited
Our aim is was to address three key questions: (roughly ~20min for each)●

Why should we, as deep learning practitioners, study algorithms?
○ Further, why might it be beneﬁcial to make ‘algorithm-inspired’ neural networks?

●

How to build neural networks that behave algorithmically?
○ And why am I even telling you this in a “Graph Machine Learning” course?

●

Do algorithmic neural networks actually work when deployed?
○ If so, how are they actually being used?

Hopefully, also some ideas on where you might be able to apply the ideas above :)Further insight: Algorithmic reasoning
If you would like to know more details about constructing good processor networks:

https://www.youtube.com/watch?v=IPQ6CPoluok

https://drive.google.com/file/d/1_EQ9Yu7VEkvr
HaVHl_WbT5ABvxrSNY-s/view?usp=sharing

Further insight: Algorithmic implicit planningIf you would like to know more details about implicit planning and XLVIN:

https://www.youtube.com/watch?v=mGw9ewL8wCU

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

Want to know more?
Our 43-page survey on GNNs for CO!
https://arxiv.org/abs/2102.09544
Section 3.3. details algorithmic reasoning,with comprehensive references.

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

In collaboration with Charles Blundell, Raia Hadsell, Rex Ying, Matilde Padovano,Andreea Deac, Ognjen Milinković, Pierre-Luc Bacon, Jian Tang, Mladen Nikolić,
Christopher Morris, Quentin Cappart, Elias Khalil, Didier Chétalat, Andrea Lodi,
Lovro Vrček, Mile Šikić, Lars Buesing, Matt Overlan, Razvan Pascanu and Oriol Vinyals