Neural Algorithmic Reasoning
Petar Veličković
DLG-KDD’21
15 August 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 ~10min 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” context?

●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“Fundamentalsof 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 know, this is directly
related to computing themaximum ﬂ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.

4Towards aneurally spicedsolution

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

5

Algorithmicreasoning

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!

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

Blueprint of algorithmic reasoning, in-depth

6An 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 latentspace○ 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 envs.

...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! :)7Summary andconclusions

Overview, revisited
Our aim is was to address three key questions: (roughly ~10min 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” context?

●

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