Algorithmic Inductive Biases
Petar Veličković

Mila Tea Talk Series
3 July 2020

Introduction, motivation, and disclaimer●

We will investigate structural inductive biases, and when is the right time to impose them,through the lens of learning representations of algorithms and data structures.

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

Introduction, motivation, and disclaimer●

We will investigate structural inductive biases, and when is the right time to impose them,through the lens of learning representations of algorithms and data structures.

●Algorithms are a natural ground for studying these rigorously:○ Know exactly how the inputs and outputs are produced;○ No noise involved;○ Algorithm has interpretable subroutines and control ﬂow;
○ Credit assignment can be directly investigated.

●

In this talk, I will be dealing primarily with reasoning over sets of ﬂat object representations.
○ Assume perception / “System 1” is either solved or not present in the problem

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 themaximal 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 themaximal 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 farMLPs~ 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)●I will only present this proof intuitively.
(tl;dr: it relies on PAC-like frameworks, using sample complexity as a notion of favourability)(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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 nodeOutput: 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

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

Credit assignment, and catching “cheating”
executors●We directly illustrate how to verify if the learned function is “useful” on the reachability
task, plotting step-wise accuracy and explaining GNN outputs. (Ying et al., NeurIPS 2019)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) expressed by a 1in nodes u and v, 0 otherwise●Output: has adding /removing edge (u, v) resulted
in one component less?

●Very challenging for(fully-connected) GNNs
○ Hidden state must
usefully remember
everything added so far○ Vulnerable tooversmoothing!

Graph refinement●

Are the input graph edges most relevant?

●Consider Dijkstra’s pathﬁnding algorithm (right):○ Graph edges used for relaxation○ But choosing which node to use next?
○ Relies on global state (or edges of a heap).

●Also useful to add edges which facilitate useful information propagation●For the incremental connectivity queries, iterating only over the current graph’s edges
leads to linear-time query answering.

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

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

Pointers through Transformers(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. 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. 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. 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. 2020)

Further supervised to answer queries at every point in time.

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

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

Which nodes contribute to the decision? (|V|=20)●Count how often is each node “used” in the ﬁnal embedding that answer queries!
○ Check the two merged nodes and nodes on path to root
○ Comparing baseline GNN (left) and PGN (right) on 20-node test

Which nodes contribute to the decision? (|V|=50)●

Count how often is each node “used” in the ﬁnal embedding that answer queries!
○ Check the two merged nodes and nodes on path to root
○ Comparing baseline GNN (left) and PGN (right) on 50-node test

Which nodes contribute to the decision? (|V|=100)●

Count how often is each node “used” in the ﬁnal embedding that answer queries!
○ Check the two merged nodes and nodes on path to root
○ Comparing baseline GNN (left) and PGN (right) on 100-node test

Pointer accuracies(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. 2020)●It appears that our learnt data structure substantially deviates from ground-truths!

●

What did it learn to do?

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

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

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 obtainedform 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. 2020)

PGN iterations on Union(i, i+1): initial state

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

So far, so good....

(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. 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. 2020)

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

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

PGN iterations on Union(i, i+1): (5, 6)(Veličković, Buesing, Overlan, Pascanu, Vinyals and Blundell. 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!

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

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?

Thank you!
Questions?
petarv@google.com | https://petar-v.com
In collaboration with Charles Blundell, Raia Hadsell, Rex Ying, Matilde Padovano,
Heiko Strathmann, Lars Buesing, Matt Overlan, Razvan Pascanu and Oriol Vinyals