Neural Algorithmic Sketching
Petar Veličković
SketchDL Workshop
CVPR 2021
19 June 2021

In this talk:SketchingAlso in this talk:(Classical) Algorithms

Also in this talk:(Classical) Algorithms

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

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

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

1

Sketches andalgorithms?

Sketches can be seen (roughly) analogous to graphs...

Visualising them requires a renderer! (algorithm :) )

Rendering algorithms can be way more complex than thisThe very process of sketching is often algorithmic●Hierarchical●Regular●Sequential●Sketching -> insight on generative factors!

●

Taken to the extreme, we could get...

Algorithms enable complex sketching from simple patterns●L-systems allow for sketching complex, hierarchical shapes as rollouts of a CFG○ Very amenable to algorithmic computation, e.g. parsing

Our aim for today●Capture the “algorithmic” aspect of sketching within a (graph) neural network●

Illustrate neural algorithmic reasoning as one approach for doing so○ We’ll use an algorithmic exposition for maximal rigour●

Outline some tasks that could beneﬁt from this
○ Largely a perspectives talk!
○ Potential useful “playground”●

I should highlight I’m not active
in sketch research!
○○Likely missing many rel. work
Hope to give interesting ideas!

2

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“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.

Max-flow example (f = 17)

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

3Towards 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.
○ Great solutions exist, however. See Vlastelica et al. (ICLR’20)

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●

Possible context for sketching -- low-data extraction of key points from an image?

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!

PEncoderDecoder(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?

PEncoderDecoder4Algorithmicreasoning

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We showed this works in RL

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

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: 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 7-page Opinion paper!
https://arxiv.org/abs/2105.02761

5Implications ofalgorithmic
sketching?

Blueprint of algorithmic reasoning

Backpropagating through the drawing algorithm

Now our“img2sketch” doesn’t
have to re-learn how
to do brush strokes!
Can be taken to theextreme with any
rendering algorithm.

Backpropagating through the “sketcher”

We already know we
can train abstract
models of this kind(e.g. SketchRNN)!

Backpropagating through any parser

Extract the“hierarchy”
within natural
images bymaking thempass througha parser.

[+[]-]-[-]+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