11institutetext: Nokia Bell Labs, France
11email<EMAIL_ADDRESS>
https://www.bell-labs.com/about/researcher-profiles/alonsosilva/

# Large Language Models Playing Mixed Strategy Nash Equilibrium Games

Alonso Silva 11

###### Abstract

Generative artificial intelligence (Generative AI), and in particular Large
Language Models (LLMs) have gained significant popularity among researchers
and industrial communities, paving the way for integrating LLMs in different
domains, such as robotics, telecom, and healthcare. In this paper, we study
the intersection of game theory and generative artificial intelligence,
focusing on the capabilities of LLMs to find the Nash equilibrium in games
with a mixed strategy Nash equilibrium and no pure strategy Nash equilibrium
(that we denote mixed strategy Nash equilibrium games). The study reveals a
significant enhancement in the performance of LLMs when they are equipped with
the possibility to run code and are provided with a specific prompt to
incentivize them to do so. However, our research also highlights the
limitations of LLMs when the randomization strategy of the game is not easy to
deduce. It is evident that while LLMs exhibit remarkable proficiency in well-
known standard games, their performance dwindles when faced with slight
modifications of the same games. This paper aims to contribute to the growing
body of knowledge on the intersection of game theory and generative artificial
intelligence while providing valuable insights into LLMs strengths and
weaknesses. It also underscores the need for further research to overcome the
limitations of LLMs, particularly in dealing with even slightly more complex
scenarios, to harness their full potential.

###### Keywords:

Game Theory LLMs Generative AI.

##  1 Introduction

Generative artificial intelligence (Generative AI) has emerged as a dynamic
field within AI, empowering machines with algorithms that enable them to
generate unique content, including music, images, code, text, and human-like
conversations. One notable example is Large Language Models (LLMs), a specific
type of Generative AI model that undergoes training on extensive unlabeled
textual datasets. LLMs have demonstrated remarkable abilities in various
domains, including question answering, translation, summarization, code
generation, etc. [7]. Generative AI, and in particular LLMs have gained
significant popularity among researchers and industrial communities, paving
the way for integrating LLMs in different domains, such as robotics [8],
telecom [9], and healthcare [5].

If we take a step back, we notice that in recent years the rapid advancement
of artificial intelligence and machine learning technologies has led to
delegating an increasing number of tasks to machines. From automated customer
service chatbots to autonomous vehicles, these intelligent systems have
demonstrated remarkable capabilities in handling complex tasks and augmenting
human productivity. However, as our reliance on those machines grows, it
becomes crucial to comprehend the extent of what we are delegating. LLMs have
been employed in various domains, however amidst their impressive
capabilities, it is essential to acknowledge the potential drawbacks and
limitations they possess.

One of the known drawbacks of LLMs is their capacity to randomize (see for
example [4]), therefore we should approach with a certain level of skepticism
their performance on tasks when randomization is a critical factor. In the
realm of game theory, randomization plays a pervasive role. A prime
illustration of this phenomenon is found in the notion of a mixed strategy
Nash equilibrium. This concept entails a strategy wherein a player does not
consistently opt for the same action but rather elects each action with a
specific probability. This element of uncertainty adds depth and complexity to
the strategic decision-making process, as players strategically allocate their
choices based on the likelihood of favorable outcomes.

In this work, we focus our attention on the capabilities of LLMs to find the
Nash equilibrium in games with a mixed strategy Nash equilibrium and no pure
strategy Nash equilibrium (that throughout this work we denote mixed strategy
Nash equilibrium games). For other works, studying LLMs playing games, see for
example [3] and [2]. In particular, we study two classic mixed strategy Nash
equilibrium games: matching pennies and rock, paper, scissors, which we
describe in the following sections. These simple yet universally recognized
games provide an ideal platform to evaluate the LLM capabilities in a
controlled environment.

To perform our experiments, we used as LLM the quantized Mistral v0.3 model
which is an advanced language model that leverages quantization to improve
computational efficiency without significantly compromising performance. We
chose this open weights model to ensure that our experiments are designed and
conducted in a manner that allows other researchers to replicate them
accurately. This commitment to reproducibility not only validates our findings
but also facilitates further research in this area. Our code can be found on
https://github.com/alonsosilvaallende/LLMs_Playing_MSNE_Games. Another reason
to use this model is that one of the key aspects we use in this paper is the
model’s function-calling capabilities. This feature allows the model to call
functions to answer a user’s question.

##  2 Matching Pennies game

###  2.1 Problem description

Matching Pennies game is a classic game. It is a two-player zero-sum game,
meaning that any gain by one player is exactly offset by the loss of the other
player. The game works as follows:

  * $\bullet$

Each player has two possible actions: to play Heads or Tails.

  * $\bullet$

Both players reveal their choices simultaneously.

  * $\bullet$

If both choices match (both Heads or both Tails), Player 1 wins. If the
choices do not match (one Heads and one Tails), Player 2 wins.

The payoff matrix of the Matching Pennies game is given by Table 1.

Table 1: Payoff matrix of the Matching Pennies game | Heads | Tails
---|---|---
Heads | (1,-1) | (-1,1)
Tails | (-1,1) | (1,-1)

In the Matching Pennies game, the mixed strategy Nash equilibrium occurs when
each player chooses Heads or Tails with equal probability (50% chance of Heads
and 50% chance of Tails). This is because, given that the other player is
playing a 50-50 strategy, each player’s expected payoff is the same regardless
of their own strategy. Therefore, they have no incentive to deviate from the
50-50 strategy, which makes it a Nash equilibrium.

###  2.2 Game-playing capabilities of the LLM based purely on its pre-existing
knowledge

In this subsection, we investigate the capabilities of the LLM to play the
game. First, we assess the LLM’s ability to recognize the game to see if it is
included in its pre-existing knowledge. To do this we use the following
prompt:

`PROMPT:` What is the mixed strategy Nash equilibrium for the matching pennies
game?

The response generated by the LLM indicates that indeed the Nash Equilibrium
of this game is included in its pre-existing knowledge:  `ANSWER:` The
Matching Pennies game is a two-player, zero-sum game where each player
secretly chooses either heads (H) or tails (T). If both players choose the
same option, the player who chose first wins the coin, and if they choose
differently, the second player wins. In a Nash equilibrium, neither player has
an incentive to deviate from their strategy if they believe the other player
will stick to theirs. However, in the Matching Pennies game, there is no pure
strategy Nash equilibrium because both players would have an incentive to
deviate from their strategies if they knew what the other player was going to
do. Instead, the Matching Pennies game has a mixed strategy Nash equilibrium.
In this case, each player should randomly choose heads or tails with equal
probability (0.5). This way, neither player can gain an advantage by deviating
from their random choice, as they have no information about the other player’s
decision. So, the mixed strategy Nash equilibrium for the Matching Pennies
game is each player choosing H and T with a 50% probability.

We assess the model’s ability to play the game of matching pennies without any
additional instruction. This evaluation is significant as it tests the model’s
capacity to comprehend and follow the game’s rules based purely on its pre-
existing knowledge. To do this we use the following prompt:  `PROMPT:` Respond
to the following text with one of the following answers: ‘heads’, ‘tails’.
Provide your response in JSON format containing a single key ‘answer’. Text:
Let’s play matching pennies. I have made my choice. Now, you should make your
choice. What do you play? The idea of using JSON format with a single key is
to make the postprocessing of the LLM’s answers easier (we just need to
extract the answer from the JSON instead of having to search within a
potentially long answer which was the action played by the LLM). This idea was
taken from the Scikit-LLM library [1].

We tested $1000$ different seeds. The probabilities of obtaining Heads or
Tails are given by Table 2.

Table 2: Probabilities of obtaining Heads or Tails in the Matching Pennies game without any additional instruction. $p_{\rm Heads}$ | 77.9%
---|---
$p_{\rm Tails}$ | 22.1%

The responses generated by the LLM indicate that despite both the Matching
Pennies game and its mixed strategy Nash equilibrium being included in its
pre-existing knowledge, the LLM is unable to play according to this strategy.

###  2.3 Let LLMs run code

In this subsection, we allow the LLM the possibility to run code. To encourage
the LLM to use this possibility we add the following text to the prompt:

`Use Python`

Therefore, we use the following prompt:

`PROMPT:` Let’s play matching pennies. I have made my choice. Now, you should
make your choice. Use Python

The response generated by the LLM is the following:

    import random
    choice = random.randint(0,1)
    print("Heads" if choice == 0 else "Tails")

This response indicates that despite the LLM being unable to play according to
the mixed strategy Nash equilibrium, it doesn’t have a problem generating the
code to play the game according to the mixed strategy Nash equilibrium.
Therefore, if we allow the LLM to run the code it generated, it indeed plays
the mixed strategy Nash equilibrium.

###  2.4 Modified Matching Pennies game

In this subsection, we consider a modification of the Matching Pennies (that
we call the Modified Matching Pennies game) with the payoff matrix given by
Table 3.

Table 3: Payoff matrix of the Modified Matching Pennies game | Heads | Tails
---|---|---
Heads | (7,-1) | (-1,1)
Tails | (-1,1) | (1,-1)

In this Modified Matching Pennies game, the only modification is that if both
players choose Heads, the first player receives a payoff of 7 instead of 1 in
the original matching pennies game. All the other payoffs are the same.

The mixed strategy Nash equilibrium of the Modified Matching Pennies [6] is
given by:

  * $\bullet$

Player 1 plays both options (Heads and Tails) with equal probability $1/2$.

  * $\bullet$

Player 2 plays Heads with probability $1/5$ and Tails with probability $4/5$.

To make the LLM play the Modified Matching Pennies Game, we need to be more
explicit on the payoff matrix since the LLM does not know it. We also need to
add to the prompt the phrase "Use Python" to encourage it to use this
possibility. Therefore, we use the following prompt:  `PROMPT:` Let’s play a
modification of the Matching Pennies game. More precisely, each of us has two
possible actions: to play Heads or Tails. We both reveal our choices
simultaneously. If both of us play Heads, then I gain 7 points and you lose 1
point, if both of us play Tails, then I gain 1 point and you lose 1 point. If
our choices do not match (one Heads and one Tails), you gain 1 point and I
lose 1 point. I have made my choice. Now, you should make your choice. What do
you play? Use Python The response generated by the LLM is the following:

    import random
    choice = "Heads" if random.randint(0,1) == 0 else "Tails"
    print("I have played", choice)

This response is the same as the unmodified classic Matching Pennies game. The
LLM is unable to find the randomization needed to play the mixed strategy Nash
equilibrium of this slightly modified game.

##  3 Rock, Paper, Scissors game

###  3.1 Problem description

The classic game of Rock, Paper, Scissors (RPS) is also a two-player zero-sum
game. The game works as follows:

  * $\bullet$

Each player has three possible actions: Rock, Paper, or Scissors.

  * $\bullet$

Both players reveal their choices simultaneously.

  * $\bullet$

Rock crushes Scissors, Scissors cuts Paper, and Paper covers Rock.

The payoff matrix of the original Rock, Paper, Scissors game is given by Table
4. Given that payoff matrix, it is well-known that the mixed strategy Nash
equilibrium for this game is for each player to play with equal probability of
$1/3$ each of the $3$ possible actions.

Table 4: Payoff matrix of the Rock, Paper, Scissors game | Rock | Paper | Scissors
---|---|---|---
Rock | (0, 0) | (-1, 1) | (1, -1)
Paper | (1, -1) | (0, 0) | (-1, 1)
Scissors | (-1, 1) | (1, -1) | (0, 0)

###  3.2 Game-playing capabilities of the LLM based purely on its pre-existing
knowledge

In this subsection, we investigate the capabilities of the LLM to play the
game. First, we assess the LLM’s ability to recognize the game to see if it is
included in its pre-existing knowledge. To do this we use the following
prompt:

`PROMPT:` Let’s play rock, paper, scissors. I have made my choice. Now, you
should make your choice. What do you play?

The response generated by the LLM indicates that indeed the Nash Equilibrium
of this game is included in its pre-existing knowledge:  `ANSWER:` In a one-
shot Rock, Paper, Scissors (RPS) game between two players, there is no pure
strategy Nash equilibrium because if both players choose the same strategy,
they can be beaten by a deviation to another strategy. However, in repeated
games with perfect information and no bounds on the number of repetitions, a
mixed strategy Nash equilibrium can exist. In this case, each player randomly
chooses their move (rock, paper, scissors) with probabilities that make it
unprofitable for either player to deviate from their chosen strategy. One
possible set of such probabilities is: \- Player 1 plays rock with a
probability of 1/3, paper with a probability of 1/3, and scissors with a
probability of 1/3. \- Player 2 plays rock with a probability of 1/3, paper
with a probability of 1/3, and scissors with a probability of 1/3. In this
mixed strategy Nash equilibrium, neither player has an incentive to deviate
from their chosen strategy because the expected payoff for each move is the
same against every possible move of the other player. This results in a draw
on average, as each player wins approximately one-third of the games against
the other player’s strategies.

Table 5: Probabilities of obtaining Rock, Paper, or Scissors without any additional instruction $p_{\rm Rock}$ | 51.6%
---|---
$p_{\rm Paper}$ | 0.0%
$p_{\rm Scissors}$ | 48.4%

The responses generated by the LLM indicate that despite both the matching
pennies game and its mixed strategy Nash equilibrium being included in its
pre-existing knowledge, the LLM is unable to play according to this strategy.

###  3.3 Let LLMs run code

In this subsection, similar to the Matching Pennies game, we allow the LLM the
possibility to run code. To encourage the LLM to use this possibility, we use
the following prompt:

`PROMPT:` Let’s play rock, paper, scissors. I have made my choice. Now, you
should make your choice. Choose your choice first in code.

The response generated by the LLM is the following:

    import random
    choice = ["rock", "paper", "scissors"]
    computer_choice = random.choice(choice)
    user_input = input("Enter your choice (rock, paper or scissors): ")
    if user_input == computer_choice:
     print("It’s a tie!")
    elif (user_input == "rock" and computer_choice == "scissors") or \
     (user_input == "paper" and computer_choice == "rock") or \
     (user_input == "scissors" and computer_choice == "paper"):
     print("You win!")
    else:
     print("Computer wins!")

Similar to the case of the Matching Pennies game, this response indicates that
despite the LLM being unable to play according to the mixed strategy Nash
equilibrium, it doesn’t have a problem generating the code to play the game
according to the mixed strategy Nash equilibrium.

###  3.4 Modified Rock, Paper, Scissors Game

In this subsection, we consider a modification of the Rock, Paper, Scissors
game (that we call the Modified Rock, Paper, Scissors game) with the payoff
matrix given by Table 6.

Table 6: Payoff matrix of the Modified Rock, Paper, Scissors game | Rock | Paper | Scissors
---|---|---|---
Rock | (0, 0) | (-2, 2) | (1, -1)
Paper | (2, -2) | (0, 0) | (-1, 1)
Scissors | (-1, 1) | (1, -1) | (0, 0)

To make the LLM play the Modified Rock, Paper, Scissors Game, we need to be
more explicit on the payoff matrix since the LLM does not know it. We also
need to add to the prompt the phrase "Choose your choice first in valid Python
code." to encourage it to use this possibility. Therefore, we use the
following prompt:

`PROMPT:` Let’s play once a modification of rock, paper, scissors. More
precisely, if I play rock and you play scissors, then I gain 1 dollar and you
lose 1 dollar, if I play scissors and you play paper, then I gain 1 dollar and
you lose 1 dollar, however, if I play paper and you play rock then I gain 2
dollars and you lose 2 dollars. The same holds by changing our roles. I have
made my choice. Now, you should make your choice. What do you play? Choose
your choice first in valid Python code.

The mixed strategy Nash equilibrium of the Modified Rock, Paper, Scissors game
[6] is given by Table 7.

Table 7: Nash equilibrium strategy for the Modified Rock, Paper, Scissors game with payoff matrix given by Table 6 $p_{\rm Rock}$ | 1/4
---|---
$p_{\rm Paper}$ | 1/4
$p_{\rm Scissors}$ | 1/2

The response generated by the LLM is the following:

    import random
    choice = [’rock’, ’paper’, ’scissors’]
    user_choice = input(’Enter your choice (rock, paper or scissors): ’)
    computer_choice = choice[random.randint(0, 2)]
    if user_choice == computer_choice:
     print(’It is a tie!’)
    elif (user_choice == ’rock’ and computer_choice == ’scissors’) or \
     (user_choice == ’scissors’ and computer_choice == ’paper’) or \
      (user_choice == ’paper’ and computer_choice == ’rock’):
     print(’You lose 1 dollar. The computer plays’, computer_choice)
    else:
     print(’You win 1 dollar. The computer plays’, computer_choice)

This response is similar to the response of the unmodified classic Rock,
Paper, Scissors game. The LLM is unable to find the randomization needed to
play the mixed strategy Nash equilibrium of this slightly modified game (nor
the modification of the payments).

##  4 Conclusions

Our study on the intersection of game theory and generative artificial
intelligence, particularly focusing on Large Language Models (LLMs), has
provided valuable insights into the capabilities and limitations of LLMs in
identifying Nash equilibria in mixed strategy games. Our findings demonstrate
that LLMs can significantly enhance their performance when they are enabled to
run code and are given specific prompts that encourage this functionality.
This capability allows LLMs to perform well in standard game scenarios where
the strategies are well-defined and well-documented.

However, the study also highlights critical limitations in the adaptability of
LLMs when confronted with games that involve complex randomization strategies
or slight modifications from standard scenarios. In such cases, the
performance of LLMs noticeably declines, suggesting that while LLMs are
proficient in handling familiar and straightforward game dynamics, their
effectiveness is reduced in more complex or altered game setups.

This research underscores the necessity for ongoing development in the field
of generative AI to enhance the robustness and flexibility of LLMs. Future
research should focus on improving the ability of LLMs to handle a broader
array of game types, particularly those that deviate from standard forms, to
fully leverage the potential of LLMs in practical and theoretical
applications. Additionally, further studies are required to explore the
integration of advanced machine learning techniques that could aid LLMs in
better understanding and adapting to complex game strategies.

Overall, our work contributes to the expanding knowledge base at the
intersection of game theory and artificial intelligence and opens up new
avenues for research in enhancing the capabilities of generative AI systems in
complex decision-making scenarios.

####  4.0.1 Acknowledgements

The work presented in this paper has been partially carried out at LINCS
(http://www.lincs.fr).

## References

  * [1] Scikit-LLM, https://github.com/koderEngine/scikit-llm
  * [2] Akata, E., Schulz, L., Coda-Forno, J., Oh, S.J., Bethge, M., Schulz, E.: Playing repeated games with large language models (2023)
  * [3] Brookins, P., Debacker, J.: Playing games with GPT: What can we learn about a large language model from canonical strategic games? SSRN Electronic Journal (2023), https://api.semanticscholar.org/CorpusID:259714625
  * [4] Hopkins, A.K., Renda, A., Carbin, M.: Can LLMs generate random numbers? Evaluating LLM sampling in controlled domains. In: ICML 2023 Workshop: Sampling and Optimization in Discrete Space (2023), https://openreview.net/forum?id=Vhh1K9LjVI
  * [5] Javaid, M., Haleem, A., Singh, R.P.: Chatgpt for healthcare services: An emerging stage for an innovative perspective. BenchCouncil Transactions on Benchmarks, Standards and Evaluations 3(1), 100105 (2023). https://doi.org/https://doi.org/10.1016/j.tbench.2023.100105, https://www.sciencedirect.com/science/article/pii/S2772485923000224
  * [6] Spaniel, W.: Game Theory 101: The Complete Textbook. CreateSpace Independent Publishing Platform (2011), https://books.google.de/books?id=4d2xoAEACAAJ
  * [7] Yenduri, G., Ramalingam, M., Selvi, G.C., Supriya, Y., Srivastava, G., Maddikunta, P.K.R., Raj, G.D., Jhaveri, R.H., Prabadevi, B., Wang, W., Vasilakos, A.V., Gadekallu, T.R.: GPT (Generative Pre-trained Transformer)— a comprehensive review on enabling technologies, potential applications, emerging challenges, and future directions. IEEE Access 12, 54608–54649 (2023), https://api.semanticscholar.org/CorpusID:258762263
  * [8] Zeng, F., Gan, W., Wang, Y., Liu, N., Yu, P.S.: Large language models for robotics: A survey (2023)
  * [9] Zou, H., Zhao, Q., Bariah, L., Bennis, M., Debbah, M.: Wireless multi-agent generative ai: From connected intelligence to collective intelligence (2023)


# How to transfer algorithmic reasoning knowledge to learn new algorithms?

Louis-Pascal A. C. Xhonneux
Université de Montréal
Mila
<EMAIL_ADDRESS>

&Andreea Deac
Université de Montréal
Mila
<EMAIL_ADDRESS>
Petar Veličković
DeepMind, London UK
<EMAIL_ADDRESS>
&Jian Tang
HEC Montréal
Mila
<EMAIL_ADDRESS>Corresponding author

###### Abstract

Learning to execute algorithms is a fundamental problem that has been widely
studied. Prior work [1] has shown that to enable systematic generalisation on
graph algorithms it is critical to have access to the intermediate steps of
the program/algorithm. In many reasoning tasks, where algorithmic-style
reasoning is important, we only have access to the input and output examples.
Thus, inspired by the success of pre-training on similar tasks or data in
Natural Language Processing (NLP) and Computer Vision, we set out to study how
we can transfer algorithmic reasoning knowledge. Specifically, we investigate
how we can use algorithms for which we have access to the execution trace to
learn to solve similar tasks for which we do not. We investigate two major
classes of graph algorithms, parallel algorithms such as breadth-first search
and Bellman-Ford and sequential greedy algorithms such as Prim and Dijkstra.
Due to the fundamental differences between algorithmic reasoning knowledge and
feature extractors such as used in Computer Vision or NLP, we hypothesise that
standard transfer techniques will not be sufficient to achieve systematic
generalisation. To investigate this empirically we create a dataset including
9 algorithms and 3 different graph types. We validate this empirically and
show how instead multi-task learning can be used to achieve the transfer of
algorithmic reasoning knowledge.

##  1 Introduction

Transfer learning [2] has been responsible for significant successes in
multiple areas of machine learning, including Natural Language Processing
(NLP) [3, 4] and Computer Vision (CV) [5]. Pre-training and reusing the
learned weights, by freezing them as feature extractors, or fine-tuning from
them as an initialisation, are common approaches to transfer in these domains.
This has enabled successful learning on problems where data is limited in some
form.

_Algorithmic reasoning_ on graphs [1, 6] is a fundamental problem that has
been studied under the assumption that we have access to the execution traces
of the algorithms we want to learn. In practice, such as many real world
reasoning tasks, this may not be true. Due to the limited data, we look to
transfer learning to enable us to solve algorithmic tasks without intermediate
steps. Specifically, we investigate how to transfer knowledge between similar
graph algorithms in the setting where we have access to the execution traces
for some (e.g. Prim [7, 8]), but not others (e.g. Dijkstra [9]). This has not
been explored before, but is important as many reasoning related fields care
deeply about systematic generalisation, while only having input-output pairs
to learn from. One such example is knowledge graph link prediction. There
exists a reasoning process that can answer the question: what is the tail
entity given the head entity and the relation. However, we do not have access
to its execution trace, i.e. the step-by-step deductions of the reasoning
process, but we do have input-output pair examples. We envision that the set-
up studied and the direction proposed in this paper will help to learn neural
networks that can solve reasoning-style problems by using other reasoning
knowledge as an inductive bias. A slightly different, but related application
may be when the data the graph algorithm needs to operate on is encoded in a
high-level space. This is a scenario encountered in reinforcement learning and
concurrent work Deac et al. [10] has already started investigating the process
of pre-training an encoder with graph algorithms.

Veličković et al. [1] successfully trained graph neural networks (GNNs) [11,
12, 13, 14] to execute graph algorithms. Two key ingredients were access to
the intermediate steps of the algorithm and algorithmic alignment [15].
Algorithmic alignment [15] refers to the concept of a computation structure—in
our case neural networks—and the structure of an algorithm ‘aligning’—in this
paper graph algorithms. ‘Alignment’ means there exists a mapping between
substructures of the computation architecture and simple substeps of the
algorithm, where the substructures can ‘easily’ compute the corresponding
substep they are mapped to—for some definition of easy, usually linear.

Extending this work, we enable solving tasks without access to the
intermediate steps using other similar algorithms as an inductive bias. To do
this we add several new algorithms. Further, since the algorithms studied in
[1] were all expressible with only linear components in the GNN, we extend
their architecture with a more expressive encoder to enable algorithmic
alignment with more tasks.

One assumption we make is that the algorithms are similar (e.g. both Prim and
Dijkstra greedily select nodes from a priority queue). This shared algorithmic
knowledge should serve as an inductive bias to enable a neural network to
systematically generalise, even when learning only on input-output pairs. We
hypothesise that due to differences between feature extraction and algorithmic
reasoning, successful approaches to transfer as used in CV and NLP will
provide only minimal improvements when transferring from one base algorithm to
a target algorithm. While features across images may be similar, the features
of algorithms differs (e.g. shortest distance in Dijkstra and lightest edge to
the tree in Prim), but are processed in a conceptually similar manner. Our
intuition is that this conceptual relationship may not yield weights that are
near each other in the weight space, thus making transfer difficult. We
instead propose to use the base algorithms as inductive biases by training
them with the intermediate steps along side training the target algorithm, for
which we do not provide intermediate supervision. Our second hypothesis is
that this will help systematic generalisation. We validate both
hypotheses—transfer does not help, while multi-task learning
helps—empirically.

The contributions of this paper are:

  1. 1.

presenting a new benchmark for transferring algorithmic reasoning knowledge on
graphs;

  2. 2.

sampling the best trajectory to stabilise training when no execution traces
are available;

  3. 3.

show that standard transfer techniques fail to significantly improve
systematic generalisation;

  4. 4.

demonstrate how systematic generalisation can instead be improved on
algorithmic tasks with multi-task learning.

##  2 Related Work

Neural Execution: Many papers have studied how to execute algorithms before
[16, 17, 18, 19, 20]. With the rise of graph representation learning [21, 22,
23] and graph neural networks [11, 12, 13, 14], recent work has looked at
executing graph algorithms [1, 6]. This line of work assumes access to the
intermediate steps of the algorithm. Further, people have looked at teaching
transformers to learn explicitly denoted subroutines and then learn how to
combine them [24]. The key difference between our work and prior work is that
we look at the setting of learning graph algorithms where we do not have
access to the execution trace and we do not denote subroutines explicitly.
Instead we propose to use similar algorithms as an inductive bias and look at
how to enable this transfer of algorithmic knowledge.

Transfer learning: Transfer learning was originally proposed in the 1970s [25,
26]. Today, it is a common tool in NLP and Computer Vision to use pre-trained
models and fine-tune them on the target task [2, 3, 5]. This is helpful when
the target task is similar and the available data is limited in some way. Our
work differs in two ways; firstly, we focus on algorithmic reasoning
knowledge, which we hypothesis will require different techniques than reusing
weights. Secondly, the data on the target task is partially missing
specifically the execution trace of the algorithm is missing.

##  3 Background

This section gives background on the algorithms and graphs used for the
experiments. To be precise we consider a graph to be a tuple $G=(V,E)$ with a
set of vertices $V$ and a set of edges $E\subseteq V\times V$111Throughout the
paper we use graphs that are simple with weights..

This section explains the algorithms studied in this paper in more detail.
After that, we give a brief introduction into graph neural networks, the
standard architecture paradigm for graph inputs.

###  3.1 Algorithms

We broadly study two classes of algorithmic reasoning: parallel and sequential
reasoning. Specifically, the parallel algorithms (shown in Algorithm 1)
studied in this paper exchange messages with their neighbours until an
equilibrium is reached. Sequential algorithms, presented in Algorithm 2,
greedily remove elements from a priority queue and updating the neighbouring
nodes’ keys.

Algorithm 1 Parallel

Input: graph $G$, weights $w$, source index $i$

initialise_nodes($G.\text{vertices}$, $i$)

repeat

for $(u,v)\in G.\text{edges}()$ do

$\text{relax\\_edge}(u,v,w)$

end for

until none of the nodes change

Algorithm 2 Sequential

Input: graph $G$, edge weights $w$, source node index $i$

initialise_nodes($G.\text{vertices}$, $i$)

$Q\leftarrow\text{PriorityQueue}(G.\text{vertices})$

repeat

$u\leftarrow Q.\text{pop\\_min}()$

for $v\in G.\text{neighbours}(u)$ do

$\text{relax\\_edge}(u,v,w)$

end for

until $Q$ is empty

Different algorithms will implement their own relax_edge and initialise_nodes
functions, however, the overall framework stays the same and can be learned by
our GNN architecture (§ 4.1). For the sequential algorithms each node has a
state feature indicating whether it has been removed from the priority queue,
a key feature for the priority queue, and a pointer to the predecessor node.

We study the following algorithms:
Parallel 1. Breadth-first search (BFS) 2. Bellman-Ford 3. Widest path
(parallel) 4. Most reliable-path (parallel) Sequential 1. Prims 2. Dijkstra 3.
Depth-first search (DFS) 4. Widest path (parallel) 5. Most reliable-path
(parallel)

We give the pseudo-code for all algorithms in the supplementary. Note that the
relax_edge function is increasingly difficult to learn for the neural network
as you go down the list: Prims uses the edge weight as a key, thus the
relax_edge function is the identity, for Dijkstra and Depth-first search
addition is necessary to compute the edge update, for Widest-path we need to
take a maximum, which with a ReLU activation can still be done exactly, and
for Most reliable-path the neural network needs to learn to approximate
multiplication.222We note that the tasks are all linear time in the size of
the graph. More challenging problems such as NP-hard problems are primarily
more difficult because of their increased run-time and hence longer sequences
allowing for more accumulation of errors. As long as we have algorithmic
alignment [15] between the architecture and the algorithm in question there is
no additional challenge to NP-hard problems except the length of their
sequence and hence more opportunities to introduce errors and propagate them.

###  3.2 Graph Neural Networks

A general framework to describe several graph neural network architecture is
the message passing framework introduced by Gilmer et al. [13]. Such graph
neural networks (GNNs) consist of three parts: a message function $M$, an
update function $U$, and an aggregator $\bigoplus$. $M$ and $U$ are arbitrary
neural networks. The high-level idea is

  1. 1.

each node computes a message for its neighbours using $M$;

  2. 2.

then each node aggregates the received messages using $\bigoplus$;

  3. 3.

finally, each node updates its embedding using $U$.

The message function in this paper takes as input the sending and receiving
nodes’ representation as well as an encoding of the edge feature along which
the message is sent. The aggregator chosen is the $\max$ aggregator applied
element-wise as it was determined to work best by Veličković et al. [1] and
provides algorithmic alignment [15] between the architecture and the tasks.
The update function takes as input the node’s previous embedding and
aggregated messages.

###  3.3 Problem definition

We study learning graph algorithms that take in a graph $G$, a weight function
$w:E\to\mathbb{R}$ that assigns a weight to each edge in the graph, and node
features $X:V\to\mathbb{R}^{k}$. Algorithms compute an output $Y:V\to F^{k}$
and a predecessor $P:V\to V$ at each time step. This encompasses a large class
of graph algorithms solving tasks such as reachability or shortest-path.

For instance, for a sequential algorithm the $i$th node’s features $X_{t}[i]$
would be the key value and the state variable. Given $X_{t}$, the graph $G$,
and the edge weights, the graph algorithm at each iteration returns the node
features $Y_{t}$ and the predecessor for each $P_{t}$ (pred variable in
pseudocode § 3.1). $Y_{T}$ and $P_{T}$ at the final step are considered the
output of the algorithm. The intermediate steps refers to
$X_{t},Y_{t},P_{t}\;\forall t\in\\{1,\ldots,T-1\\}$ after each iteration.

##  4 Methods

In this section, we first briefly present two architectures we will use for
training and then discuss how existing algorithmic knowledge can be used to
solve tasks when no execution trace is given.

###  4.1 Architecture

As our starting point we choose the encoder-processor-decoder architecture
proposed in Veličković et al. [1]. The high-level idea is that the network
encodes the current node state into a hidden embedding, on which a graph
neural network unit, called the processor, is applied using the graph
structure. The results are then decoded by the decoder, which does the
prediction of the node features at the next time step (§ 3.1). The point of
this architecture is to allow several algorithms to use the same processor
architecture. A more detailed summary of the architecture is given below:

####  4.1.1 NeuralExecutor

The NeuralExecutor (NE) [1] uses an encoder-processor-decoder architecture.
Let $X\in\mathbb{R}^{n\times k}$ be node states, where $n,k$ are the number of
nodes and features, respectively. Each edge $(u,v)$ has a weight
$w(u,v)\in\mathbb{R}$. The architecture keeps a hidden state for each node
$H\in\mathbb{R}^{n\times l}$ with $l$ features, which is initialised to all
zeros. The encoder $\mathcal{E}$ consists of a linear layer and computes a
hidden embedding $\mathcal{E}(X_{i},H_{i})=Z_{i}$, where $i$ indicates the
$i$th step in the computation. The processor $\mathcal{P}$ is message passing
neural network (MPNN) with a $\max$ aggregator with linear message and update
functions. The processor computes the new hidden state for each node
$\mathcal{P}(H_{i},A,w)=H_{i+1}$. Then, we have the decoder
$\mathcal{D}(Z_{i},H_{i+1})=Y_{i+1}$ and predecessor predictor
$\mathcal{S}(Z_{i},H_{i+1})=S_{i}$. Finally, a termination network
$\sigma(\mathcal{T}(H_{i+1}))$ decides whether we should terminate or not.

We make minor changes to allow for better algorithmic alignment: we remove the
ReLU activations from the processor and replace the termination layer with a
processor and linear module333We remove the ReLU because it limits the ability
of the max aggregator to minimise values by using negative inputs. The
termination condition depends on whether the remaining nodes are still
reachable hence an MPNN is a more appropriate than a linear layer..

####  4.1.2 NeuralExecutor++

Veličković et al. [1] showed positive transfer when learning algorithms in a
multi-task setup with intermediate steps. They did so by concatenating
together the node features and encoding them together into the same $h$
embedding (see Fig. 1). This has the advantage of giving strong guidance to
the secondary algorithm learned in this multi-task set-up. However, ideally we
are able to only use the base algorithm during training without having to use
it at inference time introducing another failure mode. Thus, we propose to
change the architecture as follows:

Since the node encoder is unable to learn the individual subroutines operating
on edges, we replace it with a latent encoder for each task that operates on
edges and for an edge $(i,j)$ takes in
$[h^{(i)},x^{(i)},e^{(ij)},h^{(j)},x^{(j)}]$ (Fig. 1). The important
difference is that each has task has its own encoder rather than all tasks
sharing one encoder. The goal is to force the model to learn the shared
subroutines in the processor only and the specialised subroutines in the
latent encoder only (see Fig. 1).

Further, we change the latent encoder to consist of a linear and non-linear
encoder in parallel that are added together. This should allow for algorithmic
alignment with a much larger array of tasks (specifically Widest path), but
comes at the cost that overfitting is more likely, which may hurt
generalisation to larger graphs. This last problem has been avoided in prior
work [1, 15] by having the neural network only learn linear components, which
will not be able to overfit easily.444See the Supplementary for a more formal
description.

Figure 1: $x_{0},x_{1}$ are the node states of two algorithms respectively.
$w$ are the edge weights. $p_{0},p_{1}$ are the predecessor predictions for
the two algorithms respectively and $y_{0},y_{1}$ are the next node state
predictions. $h_{i}$s are the previous hidden state kept by the network and
$e^{(ij)}$ is the computed edge weight embedding. Superscript indices indicate
a particular node. (a) Shows the original Neural Executor architecture when
doing multi-task learning. (b) Shows the more expressive Neural Executor++
when doing multi-task learning. The key difference is that (b) forces a common
way to operate on a hidden embedding space, while (a) focuses on achieving
both at the same time.

###  4.2 Training and Loss functions

Sequential algorithms (Seq): We used softmax for the prediction of the next
node to be removed from the queue and softmax for the predecessor prediction,
where we masked out all nodes except the neighbours and the node itself. We
used a smooth $l_{1}$ loss with $\beta=0.001$ for the prediction of the key of
the selected node. Finally, we used binary cross entropy for termination
prediction. We only update the node state of the chosen node, this helps with
drift of the node state at test time.

Parallel algorithms (Par): We used a smooth $l_{1}$ loss with $\beta=0.001$
for the prediction of the key except for BFS where we used binary cross-
entropy as the node state is either $0$ or $1$. In this setting, during
teacher-forcing, we masked out nodes that are unreachable at a given time
step.

Teacher forcing (TF): We train the network to predict the next step given the
ground truth inputs. At test time the networks prediction are used instead of
the ground truth.

No algorithm (NA): We train the network using only the loss on the final
outputs, this means we change the softmax for predicting the next node to a
binary cross entropy for sequential algorithms. The next inputs are those
predicted by the network using gumbel softmax to predict the next node at each
stage. The number of steps are given to the network in this scenario. Inspired
by [27], we sample 10 trajectories using the best one for back-propagation,
when using a gumbel softmax. The idea is that only the best loss is of
interest at evaluation time and not the average loss. We show in the
supplementary that this helps stabilise and improve training compared to
taking the mean of the trajectories.

###  4.3 Standard transfer methods

We try three main approaches:

Freeze weights: This is a standard transfer technique, where we use the
learned weights of the processor unit on a base algorithm $B$ for learning a
target algorithm $T$. In this set-up we freeze the weights of the processor
and only the encoder-decoder part of the architecture can be learned. We
assume that the algorithm $B$ was learned with teacher forcing, while $T$ is
learned with no-algorithm. We note that encoder-decoder weights cannot be
reused because in general the input/output dimensions may differ from
algorithm to algorithm.

Fine-tune weights: This is the same as the previous technique except that we
do not freeze the processor weights and instead let them be changed by the
gradient descent algorithm.

2-Processors: Again we assume we have access to the processor weights learned
on a base algorithm $B$. This setting uses two processors in parallel whose
outputs we sum together. One of the processor uses the learned processor
weights and is frozen, while the other processor is free to learn the
necessary changes and is randomly initialised. We suspect this will be the
best transfer method as it does not forget the information given by the domain
algorithm, but retains the flexibility to adapt the processor.

###  4.4 Transfer via multi-task learning

A stronger inductive bias is to train the base algorithm $B$, for which we
have access to intermediate steps, together with the target algorithm $T$, for
which we do not. This multi-task set-up highlights the difference between the
original Neural Executor architecture proposed in Veličković et al. [1] and
Neural Executor++ (see Fig. 1). The former simply concatenates the node
features of $B$ and $T$ and forces them to share the hidden embedding. The
latter allows different encoder-decoders and only shares the weights of the
processor, i.e. each algorithm has its own hidden embedding. This second
approach encourages the network to execute the shared subroutine in the
processor and the individual subroutines in the encoder-decoder. The overall
idea is that the base algorithm $B$ serves as an inductive bias as to how to
structure the latent space and teach the processor how to evolve $T$.

###  4.5 Graphs

We study three kinds of graphs:

i) Erdos-Renyi $p=\min\left(\frac{\log_{2}|V|}{|V|},0.5\right)$,  ii)
Barabasi-Albert,  iii) 2d-grid graphs.

Erdos-Renyi graphs are random graphs where each possible edge has probability
$p$ of being added to the graph. Barabasi-Albert graphs are power-law graphs
with a few highly connected nodes and many dangling nodes. 2d-grid graphs are
very regular graphs in an arbitrary 2d-grid shape. We chose these 3 classes of
graphs because they represent some of the major possible differences between
graphs. 2d-grid graphs are very regular and Veličković et al. [1] notes that
very regular graphs tend to transfer poorly from or to random graphs. Erdos-
Renyi graphs tend to be sparse, but highly likely to be connected. Barabasi-
Albert graphs tend to be quite dense graphs with shorter average path-length
than random graphs. As such these graph classes differ significantly from each
other.

For all graphs, we generate edge weights that are uniformly between
$[0.2,1.0]$, this range prevents key values such as shortest path from
becoming too extreme555All code to generate data and train models will be
released upon acceptance with an MIT license..

##  5 Experiments

For all experiments we use 5,000 graphs of each type (Erdos-Renyi (ER),
Barabasi-Albert (BA), 2d-Grids (2d-G)) with 20 nodes each. We train using Adam
[28] with a learning rate of $0.0005$, a batch size of $64$, and use early
stopping with a patience of $10$ to prevent overfitting. We test on graphs
size 20, 50, and 100 nodes. The hidden embedding size is set to $32$ except
for NE++ for multi-task experiments, where it is 16 to account for the
additional expressivity of having several encoders. Each experiment was
executed on a V100 GPU in less than 5 hours for the longest experiment.

We measure the average performance over all 3 graph types at evaluation
separately and present the average with standard deviation in the main paper.
Large standard deviation may arise due to the extreme difference between
random graphs of type ER or BA versus 2d-G graphs.666See the Supplementary for
a more detailed explanation.

###  5.1 Metrics

Sequential algorithms: _Predecessor (Pred.)_ error rate is the most important
measure as to whether a task has been successfully completed as it gives us
the path predicted by the network. _Next node (Next)_ error rate measures
whether the next node is the correct one to pick. _Key_ accuracy measures
whether the key of the picked node is correct, measured in mean squared error.
Next node are indicative of whether the correct algorithm is being executed,
while Pred. and Key primarily serves to indicate the correctness of the
solutions found. Lower is always better.

Parallel algorithms: _Key_ accuracy measures the node features mean squared
error for all algorithms except BFS, where it is measured in accuracy as the
node feature is a binary choice between 0 and 1. _Predecessor (Pred.)_
accuracy measures the accuracy of predicting the predecessor node.

Table 1: Teacher forcing (seq.). NE++ worse performance on Dijkstra showing the downside of higher model capacity. | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Next node | Key | Predecessor | Next node | Key | Predecessor
NE | 20 | $0.018\pm 0.004$ | $0.0367\pm 0.01$ | $0.005\pm 0.002$ | $0.238\pm 0.05$ | $0.0358\pm 0.02$ | $0.053\pm 0.01$
50 | $0.089\pm 0.009$ | $0.569\pm 0.7$ | $0.02\pm 0.02$ | $0.557\pm 0.08$ | $0.0697\pm 0.05$ | $0.099\pm 0.01$
100 | $0.341\pm 0.02$ | $4.79\pm 6$ | $0.064\pm 0.04$ | $0.763\pm 0.07$ | $0.0924\pm 0.06$ | $0.167\pm 0.007$
NE ++ | 20 | $0.008\pm 0.003$ | $0.0108\pm 0.004$ | $0.003\pm 0.0008$ | $0.174\pm 0.07$ | $0.0264\pm 0.02$ | $0.047\pm 0.03$
50 | $0.35\pm 0.03$ | $445\pm 600$ | $0.211\pm 0.02$ | $0.492\pm 0.2$ | $0.0676\pm 0.05$ | $0.112\pm 0.05$
100 | $0.729\pm 0.01$ | $1.62e10\pm 2e10$ | $0.522\pm 0.07$ | $0.699\pm 0.2$ | $0.0906\pm 0.06$ | $0.171\pm 0.06$
Table 2: No algorithm (seq.). Size-generalisation is lacking without intermediate steps, especially on the more difficult Most reliable. | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Predecessor | Key | Predecessor
NE | 20 | $0.000104\pm 7e\text{-}05$ | $0.023\pm 0.01$ | $0.00829\pm 0.001$ | $0.187\pm 0.06$
50 | $9.71e5\pm 1e06$ | $0.121\pm 0.1$ | $20\pm 7$ | $0.897\pm 0.08$
100 | $3.34e16\pm 5e16$ | $0.194\pm 0.2$ | $1.32e6\pm 4e5$ | $0.768\pm 0.05$
NE ++ | 20 | $6.4e\text{-}06\pm 3e\text{-}06$ | $0.005\pm 0.003$ | $0.000465\pm 6e\text{-}05$ | $0.126\pm 0.06$
50 | $1.81\pm 2$ | $0.149\pm 0.06$ | $125\pm 70$ | $0.566\pm 0.06$
100 | $8.54e3\pm 1e4$ | $0.388\pm 0.05$ | $2.8e13\pm 4e13$ | $0.76\pm 0.05$
Table 3: Transfer to no algorithm (seq.). Pre-trained on Prim and Widest, respectively. Classic transfer learning fails to provide size-generalisation and often performs worse than no transfer. | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Predecessor | Key | Predecessor
NE Freeze | 20 | $0.014\pm 0.005$ | $0.081\pm 0.03$ | $0.0235\pm 0.003$ | $0.248\pm 0.06$
50 | $122\pm 200$ | $0.597\pm 0.09$ | $3.91e5\pm 3e4$ | $0.864\pm 0.009$
100 | $3.18e6\pm 4e6$ | $0.607\pm 0.1$ | $5.06e15\pm 7e14$ | $0.761\pm 0.04$
NE Fine-tune | 20 | $0.0021\pm 0.0009$ | $0.05\pm 0.02$ | $0.036\pm 0.005$ | $0.227\pm 0.07$
50 | $1.11e3\pm 1e3$ | $0.241\pm 0.09$ | $2e3\pm 200$ | $0.636\pm 0.1$
100 | $5.93e7\pm 8e7$ | $0.388\pm 0.1$ | $1.06e9\pm 1e8$ | $0.709\pm 0.02$
NE 2-Processor | 20 | $0.00136\pm 0.0005$ | $0.06\pm 0.03$ | $0.0163\pm 0.003$ | $0.231\pm 0.08$
50 | $14.2\pm 20$ | $0.162\pm 0.06$ | $205\pm 30$ | $0.749\pm 0.04$
100 | $1.04e4\pm 1e4$ | $0.305\pm 0.07$ | $1.22e10\pm 4e9$ | $0.815\pm 0.03$
NE++ Freeze | 20 | $0.00136\pm 0.001$ | $0.063\pm 0.02$ | $0.00687\pm 0.0008$ | $0.199\pm 0.09$
50 | $42.6\pm 50$ | $0.841\pm 0.04$ | $465\pm 100$ | $0.58\pm 0.1$
100 | $262\pm 400$ | $0.895\pm 0.07$ | $8.06e7\pm 3e7$ | $0.672\pm 0.08$
NE++ Fine-tune | 20 | $0.000414\pm 0.0003$ | $0.034\pm 0.02$ | $0.00669\pm 0.002$ | $0.191\pm 0.07$
50 | $13.5\pm 20$ | $0.962\pm 0.03$ | $1.79e5\pm 2e5$ | $0.757\pm 0.05$
100 | $2.51e4\pm 4e4$ | $0.962\pm 0.04$ | $8.17e14\pm 5e14$ | $0.774\pm 0.05$
NE++ 2-Processor | 20 | $0.00443\pm 0.002$ | $0.06\pm 0.04$ | $0.0022\pm 0.0003$ | $0.154\pm 0.05$
50 | $16.6\pm 20$ | $0.356\pm 0.1$ | $306\pm 70$ | $0.644\pm 0.03$
100 | $4.66e3\pm 6e3$ | $0.779\pm 0.02$ | $3.58e6\pm 9e5$ | $0.791\pm 0.02$
Table 4: Multi-task (seq.): Using Prim and Widest as inductive bias, respectively. Multi-task learning shows good generalisation, especially on the Key metric for Dijkstra and on Predecessor for Most reliable. | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Predecessor | Key | Predecessor
NE | 20 | $0.00362\pm 0.0005$ | $0.042\pm 0.01$ | $0.207\pm 0.03$ | $0.452\pm 0.09$
50 | $11.5\pm 2$ | $0.134\pm 0.1$ | $1.85\pm 0.5$ | $0.501\pm 0.06$
100 | $126\pm 30$ | $0.303\pm 0.3$ | $6.47\pm 3$ | $0.597\pm 0.01$
NE ++ | 20 | $0.000178\pm 8e\text{-}05$ | $0.019\pm 0.009$ | $0.00279\pm 0.0004$ | $0.166\pm 0.07$
50 | $0.413\pm 0.4$ | $0.161\pm 0.1$ | $0.199\pm 0.3$ | $0.185\pm 0.009$
100 | $2.91\pm 3$ | $0.282\pm 0.2$ | $0.843\pm 1$ | $0.267\pm 0.1$
Table 5: 2-Proc. transfer pre-trained on Prim, Dijkstra, & DFS for sequential and BFS & Bellman-Ford for parallel. Pre-training on several tasks does not improve classic transfer. | Most reliable (seq) | Most reliable (par)
---|---|---
Model | #Nodes | Key | Predecessor | Key | Predecessor
NE ++ 2-Proc. | 20 | $0.00237\pm 0.0003$ | $0.163\pm 0.06$ | $0.0408\pm 0.009$ | $0.227\pm 0.07$
50 | $62.9\pm 20$ | $0.606\pm 0.05$ | $0.161\pm 0.1$ | $0.363\pm 0.04$
100 | $1.76e6\pm 4e5$ | $0.758\pm 0.07$ | $2.68\pm 4$ | $0.448\pm 0.08$
Table 6: No algorithm (par.): For transfer we report the results of the best method (§ 4.3). Pre-trained on BFS and Widest respectively. Reliance on intermediate steps is lower for this class of problems, but multi-task transfer of knowledge is still beneficial in terms of size-generalisation. | Bellman-Ford | Most reliable path
---|---|---
Model | #Nodes | Key | Predecessor | Key | Predecessor
NE (NA) | 20 | $0.0182\pm 0.02$ | $0.057\pm 0.02$ | $0.018\pm 0.002$ | $0.226\pm 0.06$
50 | $59\pm 80$ | $0.164\pm 0.1$ | $0.147\pm 0.2$ | $0.327\pm 0.02$
100 | $1.98e6\pm 3e6$ | $0.261\pm 0.2$ | $10.4\pm 10$ | $0.435\pm 0.05$
NE++ (NA) | 20 | $0.00253\pm 0.002$ | $0.028\pm 0.01$ | $0.00957\pm 0.004$ | $0.145\pm 0.06$
50 | $0.226\pm 0.3$ | $0.057\pm 0.01$ | $0.0367\pm 0.04$ | $0.171\pm 0.03$
100 | $196\pm 300$ | $0.095\pm 0.04$ | $120\pm 200$ | $0.217\pm 0.02$
NE (Transfer Fine-tune) | 20 | $0.0386\pm 0.02$ | $0.072\pm 0.03$ | $0.0221\pm 0.006$ | $0.237\pm 0.06$
50 | $25\pm 40$ | $0.162\pm 0.05$ | $0.332\pm 0.4$ | $0.331\pm 0.02$
100 | $1.72e5\pm 2e5$ | $0.242\pm 0.1$ | $230\pm 300$ | $0.402\pm 0.03$
NE++ (Transfer 2-Proc.) | 20 | $0.0223\pm 0.02$ | $0.062\pm 0.03$ | $0.0131\pm 0.003$ | $0.196\pm 0.07$
50 | $0.666\pm 0.7$ | $0.105\pm 0.005$ | $3.04\pm 4$ | $0.313\pm 0.05$
100 | $10.8\pm 10$ | $0.168\pm 0.05$ | $579\pm 800$ | $0.411\pm 0.1$
NE (Multi-task) | 20 | $0.0154\pm 0.02$ | $0.034\pm 0.01$ | $0.173\pm 0.1$ | $0.346\pm 0.02$
50 | $6.22\pm 9$ | $0.051\pm 0.004$ | $0.407\pm 0.4$ | $0.362\pm 0.03$
100 | $1.53e3\pm 1e3$ | $0.096\pm 0.02$ | $0.615\pm 0.6$ | $0.376\pm 0.05$
NE++ (Multi-task) | 20 | $0.00353\pm 0.004$ | $0.023\pm 0.01$ | $0.00672\pm 0.0005$ | $0.153\pm 0.06$
50 | $0.0141\pm 0.02$ | $0.03\pm 0.006$ | $0.00805\pm 0.002$ | $0.182\pm 0.01$
100 | $8.84\pm 10$ | $0.13\pm 0.1$ | $0.00971\pm 0.002$ | $0.212\pm 0.02$

##  6 Results and Discussion

For the sequential algorithms we study transfer from Prim to Dijkstra and from
Widest path to Most reliable path, for parallel Algorithms we study transfer
from BFS to Bellman-Ford and from Widest path to Most reliable path.

###  6.1 Sequential

The first experiments establish baselines in terms of achievable performance
given the intermediate steps and trained with teacher-forcing (Tab. 1). We run
each algorithm separately. Next we establish the performance in the no-
algorithm setting (Tab. 2), i.e. what is achievable without intermediate
supervision.

Expressivity can harm systematic generalisation: Firstly, we note that the
additional expressivity of the NE++ (§ 4.1.2) seems to hurt systematic
generalisation even with the large amount of data available (Tab. 1) as we can
see on Dijkstra. On Most reliable both do equally well on Key and Pred., but
looking at Next node we can see that NE++ does better in simulating the
algorithm. Most reliable is a non-linear task so a non-linear encoder is
expected to help. We also note that as the graphs grow in size, the number of
reachable nodes in the priority queue increases, making it more likely we pick
the wrong node without affecting the correctness of prediction.

Secondly, we note that in the NA setting (Tab. 2) the NE is able to solve the
Pred. prediction quite well up to 100 nodes, but clearly found an alternative
way of reasoning as the key prediction is hugely wrong for larger graphs. Note
that the largest shortest distances will be found in 2-grid graphs, where it
will be upper bounded by 51. Also for Most reliable the performance on Pred.
drop at 50 nodes is significantly more severe with less representation power.

Transfer yields little improvement: The two key experiments are the transfer
setting (§ 4.3) and the multi-task setting (§ 4.4). We hypothesised that the
standard transfer experiments (fine-tune and freeze) would not help systematic
generalisation. None of the transfer methods (Tab. 3) help generalise either
task significantly. In fact, they harm systematic generalisation in terms of
Pred. prediction in all cases. The only benefit that can be observed is better
generalisation on Key accuracy indicating that the network outputs are less
extreme. The best transfer method is 2-Processor as we hypothesised in § 4.3,
which improves Key prediction at the cost of harming Pred. accuracy.

Multi-task helps systematic generalisation: In the multi-task set-up (Tab. 4),
several things occur: the Key prediction generalises even better and is
predicting in a reasonable range given the longest shortest path in graphs of
size 100. Further, NE in this setting has similar Pred. accuracy on Dijkstra
compared to NA, NE++ benefitted from the inductive bias in terms of its Pred.
accuracy on graphs of size 100 for Dijkstra. The results on Most reliable are
significantly improved and NE++ achieves good levels of systematic
generalisation in solving the task. NE interestingly worsens in its
performance on 20 nodes, but maintains a stable Pred. accuracy on larger
graphs. Demonstrating that the inductive bias from Widest prevents overfitting
in distribution and improves the performance on larger graphs. Overall, the
results validate our initial hypothesis that multi-task learning is the
correct approach to transfer knowledge.

Trying to extract shared subroutines does not help transfer: Finally, we study
to what extent the models are able to separate the common shared subroutines
and the subroutines individual to each algorithm by training multiple
algorithms with TF in a multi-task set-up together (Tab. 5). If the processor
successfully captures only the shared subroutines, then we might expect the
transfer results to be improve. We can see in Tab. 5 that multi-task pre-
training does not significantly improve results and that multi-task learning
with the target algorithm is still the best approach. However, one alternative
explanation is that given a good processor, the encoder struggles to learn the
expected encoding by the processor and thus performs poorly.

###  6.2 Parallel

Parallel algorithms are significantly easier than sequential ones due to their
much shorter length and the lack of a central data-structure that needs to be
learned to execute. This can be observed in the much higher performance in the
NA setting (Tab. 17). Interestingly, it seems that in this setting
expressivity was helpful for systematic generalisation, even in the Bellman-
Ford setting.

Transfer harms performance: In Tab. 17 we show only the best transfer result,
but as we can see this actually harms Pred. accuracy for NE++ for both
algorithms, while producing roughly the same result for NE. In both cases, the
results suggest that random initialisations are better than transfer ones. We
think this may because the shared algorithmic knowledge of parallel algorithms
is already inherently captured by GNNs as they apply message functions in
parallel to each edge, which then only need to learn the relax_edge function.
Pre-training on several algorithms did not help (Tab. 5).

Multi-task only helps Key accuracy: Similarly to sequential reasoning multi-
task vastly outperforms transfer techniques and significantly improves Key
prediction compared to NA, while keeping Pred. similar. Contrary to sequential
reasoning the Pred. prediction is comparable between NA and multi-task. We
think this is due to the shorter execution length providing less of an
inductive bias for the target algorithm and the strong inductive bias of GNN
architectures towards parallel algorithms. However, the access to more stable
gradients due to the multi-task learning approach seems to help learning to
some extent due to the improved Key predictions. Further, we observe that when
the model has less capacity (NE on Most reliable path) multi-task is still
able to improve systematic generalisation on Pred. at the cost of slightly
worse in-distribution (20 nodes) performance.

###  6.3 Why transfer learning fails?

Transfer via freezing and/or fine-tuning clearly does not work as demonstrated
by the results in Tab. 3. The fact that having two processors, one frozen and
one to fine-tune, also does not help transfer is telling, because neither the
fine-tuning process losing information, nor the rigidity of the network can be
at fault. In other words, fine-tuning has the disadvantage that we lose the
original weights and hence potentially lose information. Freezing weights
significantly limits the weights that can be changed and thus making it harder
to fit the data. However, the 2-processor approach suffers from neither
problem and yet still does not work.777Experiment 1 (in the Supplementary
material) shows that the information from a processor can be used and
recovered. Thus, we hypothesis that the reason why transfer fails to work is
that the initial weights of a similar algorithm are not near a good (as in
generalising) minimum for the target algorithm, in fact the minimum is often
worse than the minimum found from randomly initialised weights (see Tab. 2).

###  6.4 Why multi-task fairs better?

Multi-task on the other hand does not rely on the weights being near a good
minimum, but instead enforces them to be the same for the processor. This is a
very different way to use the base algorithm as an inductive bias. This
inductive bias is successful because the final weights are from a minimum that
systematically generalises (on at least one of the algorithms) with the
additional constraint that it performs well on the second target algorithm.
For transfer the initial weights might systematically generalise on the
original task there is no guarantee that the final weights stem from a minima
that systematically generalises.

##  7 Conclusion

We set out to investigate how systematic generalisation could be improved on
algorithmic tasks when the intermediate steps of the algorithm are not
available. Inspired by the success of transfer learning in domains such as CV
and NLP, we investigated it’s applicability to learning graph algorithms in
this setting. We showed that standard transfer learning is inadequate to
leverage algorithmic knowledge learned from intermediate steps to new
algorithmic tasks. Further, we showed how multi-task learning can enable the
successful transfer of inductive biases learned from other algorithms when
intermediate steps are available, significantly improving systematic
generalisation. The results are especially strong in the more difficult
sequential reasoning domain. Moreover, we conclude that expressivity can hurt
systematic generalisation if the task is too easy and intermediate supervision
is available. This should be taken into account when choosing the model. These
disadvantages disappeared when trying to learn algorithmic reasoning without
intermediate steps in our multi-task set-up, in this setting NE++ always
outperforms the simpler architecture. Both architectures can achieve
systematic generalisation. _Limitations_ of our work are that the results are
specific to algorithms on static graphs. Furthermore, as the number of
execution steps increases faster than linear in the number of nodes results
are likely to worsen significantly.

This paper’s contributions are fundamental in nature and thus, the societal
impact of this paper is low and there are no associated ethical risks. Any
benefits or risks stem from further advances in reasoning systems that may be
in some form be based on this work.

## Acknowledgments and Disclosure of Funding

We would like to thank Meng Qu, Zhaocheng Zhu, and Zuobai Zhang for proof
reading the manuscript prior to submission.

This project is supported by the Natural Sciences and Engineering Research
Council (NSERC) Discovery Grant, the Canada CIFAR AI Chair Program,
collaboration grants between Microsoft Research and Mila, Samsung Electronics
Co., Ltd., Amazon Faculty Research Award, Tencent AI Lab Rhino-Bird Gift Fund
and a NRC Collaborative R&D Project (AI4D-CORE-06). This project was also
partially funded by IVADO Fundamental Research Project grant
PRF-2019-3583139727.

Petar Veličković is a Research Scientist at DeepMind.

## References

  * Veličković et al. [2019] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell.  Neural execution of graph algorithms.  _arXiv preprint arXiv:1910.10593_ , 2019.
  * Erhan et al. [2010] Dumitru Erhan, Aaron Courville, Yoshua Bengio, and Pascal Vincent.  Why does unsupervised pre-training help deep learning?  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , pages 201–208. JMLR Workshop and Conference Proceedings, 2010.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Brown et al. [2020] TB Brown, B Mann, N Ryder, M Subbiah, J Kaplan, P Dhariwal, A Neelakantan, P Shyam, G Sastry, A Askell, et al.  Language models are few-shot learners. arxiv 2020.  _arXiv preprint arXiv:2005.14165_ , 4, 2020.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale, 2020.
  * Veličković et al. [2020] Petar Veličković, Lars Buesing, Matthew C Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell.  Pointer graph networks.  _arXiv preprint arXiv:2006.06380_ , 2020.
  * Jarník [1930] Vojtěch Jarník.  On a certain problem of minimization.  _Práce moravskè přírodovědecké společnosti 6, fasc. 4_ , pages 57–63, 1930.  URL http://hdl.handle.net/10338.dmlcz/500726.
  * Prim [1957] R.C. Prim.  Shortest connection networks and some generalizations.  _Bell System Technical Journal_ , pages 1389–1401, 1957.  URL https://archive.org/details/bstj36-6-1389.
  * Dijkstra [1959] E.W. Dijkstra.  A note on two problems in connexion with graphs.  _Numerische Mathematik_ , pages 269–271, 1959.  URL https://doi.org/10.1007/BF01386390.
  * Deac et al. [2020] Andreea Deac, Petar Veličković, Ognjen Milinković, Pierre-Luc Bacon, Jian Tang, and Mladen Nikolić.  Xlvin: executed latent value iteration nets, 2020.
  * Li et al. [2015] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated graph sequence neural networks.  _arXiv preprint arXiv:1511.05493_ , 2015.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Gilmer et al. [2017] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In _International Conference on Machine Learning_ , pages 1263–1272. PMLR, 2017.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Xu et al. [2020] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka.  What can neural networks reason about?, 2020.
  * Zaremba and Sutskever [2015] Wojciech Zaremba and Ilya Sutskever.  Learning to execute, 2015.
  * Łukasz Kaiser and Sutskever [2016] Łukasz Kaiser and Ilya Sutskever.  Neural gpus learn algorithms, 2016.
  * Kurach et al. [2016] Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever.  Neural random-access machines, 2016.
  * Reed and de Freitas [2016] Scott Reed and Nando de Freitas.  Neural programmer-interpreters, 2016.
  * Santoro et al. [2018] Adam Santoro, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy Lillicrap.  Relational recurrent neural networks.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/e2eabaf96372e20a9e3d4b5f83723a61-Paper.pdf.
  * Bronstein et al. [2017] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: Going beyond euclidean data.  _IEEE Signal Processing Magazine_ , 34(4):18–42, Jul 2017.  ISSN 1558-0792.  doi: 10.1109/msp.2017.2693418.  URL http://dx.doi.org/10.1109/MSP.2017.2693418.
  * Hamilton et al. [2018] William L. Hamilton, Rex Ying, and Jure Leskovec.  Representation learning on graphs: Methods and applications, 2018.
  * Battaglia et al. [2018] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu.  Relational inductive biases, deep learning, and graph networks, 2018.
  * Yan et al. [2020] Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi.  Neural execution engines: Learning to execute subroutines, 2020.
  * Bozinovski and Fulgosi [1976] S Bozinovski and A Fulgosi.  The influence of pattern similarity and transfer learning upon training of a base perceptron b2.  In _Proceedings of Symposium Informatica_ , pages 3–121, 1976.
  * Bozinovski [1981] S Bozinovski.  Teaching space: A representation concept for adaptive pattern classification.  Technical report, COINS Technical Report, University of Massachusetts at Amherst, 1981.
  * Petersen et al. [2021] Brenden K Petersen, Mikel Landajuela Larma, Terrell N. Mundhenk, Claudio Prata Santiago, Soo Kyung Kim, and Joanne Taery Kim.  Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=m5Qsh0kBQG.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.

##  Appendix A Appendix

###  A.1 Pseudo-code

In this section we give the pseudo-code for the initialise_nodes and
relax_edge functions for all the algorithms. Parallel meaning they use the
framework in Alg. 1 and Sequential meaning they use the framework in Alg. 2.

Algorithm 3 BFS (Parallel)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow 1$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}=0\land u.\text{key}=1$ then

$v.\text{key}\leftarrow 1$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 4 Dijkstra (Sequential)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow\infty$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}>u.\text{key}+w(u,v)$ then

$v.\text{key}\leftarrow u.\text{key}+w(u,v)$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 5 Bellman-Ford (Parallel)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow\infty$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}>u.\text{key}+w(u,v)$ then

$v.\text{key}\leftarrow u.\text{key}+w(u,v)$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 6 Prim (Sequential)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow\infty$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{pred}==\bot\text{ and }v.\text{key}>w(u,v)$ then

$v.\text{key}\leftarrow w(u,v)$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 7 Widest path (Parallel)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow\infty$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}<\min(u.\text{key},w(u,v))$ then

$v.\text{key}\leftarrow\min(u.\text{key},w(u,v))$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 8 Widest path (Sequential)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow\infty$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}<\min(u.\text{key},w(u,v))$ then

$v.\text{key}\leftarrow\min(u.\text{key},w(u,v))$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 9 Most reliable path (Parallel)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow 1$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}<u.\text{key}\times w(u,v)$ then

$v.\text{key}\leftarrow u.\text{key}\times w(u,v)$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 10 Most reliable path (Sequential)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow 1$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow 0$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}<u.\text{key}\times w(u,v)$ then

$v.\text{key}\leftarrow u.\text{key}\times w(u,v)$

$v.\text{pred}\leftarrow u$

end if

end function

Algorithm 11 Depth-first search (DFS) (Sequential)

function initialise_nodes($G.\text{vertices}$, $i$)

for $v\in G.\text{vertices}$ do

if $v=i$ then

$v.\text{key}\leftarrow|G.\text{vertices}|$

$v.\text{pred}\leftarrow v$

else

$v.\text{key}\leftarrow\infty$

$v.\text{pred}\leftarrow\bot$

end if

end for

end function

function relax_edge($u$, $v$, $w$)

if $v.\text{key}=\infty$ then

$v.\text{key}\leftarrow u.\text{key}-1$

$v.\text{pred}\leftarrow u$

end if

end function

###  A.2 Mean of trajectories

In this section we verify that taking the maximum of several trajectories as
described in § 4.2, the results are in Tab. 7 and confirm our hypothesis.

Table 7: No algorithm (seq.). We take the mean of 10 trajectories instead of the $\max$.  | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Predecessor | Key | Predecessor
NE | 20 | $6.22e\text{-}5\pm 5e\text{-}5$ | $0.014\pm 0.01$ | $0.00279\pm 0.0004$ | $0.158\pm 0.06$
50 | $1.13e6\pm 2e6$ | $0.121\pm 0.08$ | $11\pm 5$ | $0.615\pm 0.1$
100 | $1.39e17\pm 2e17$ | $0.237\pm 0.2$ | $3.31e5\pm 2e5$ | $0.658\pm 0.03$
NE ++ | 20 | $0.00221\pm 0.002$ | $0.026\pm 0.01$ | $0.000879\pm 8e\text{-}5$ | $0.121\pm 0.05$
50 | $13.3\pm 20$ | $0.257\pm 0.06$ | $0.232\pm 0.1$ | $0.503\pm 0.01$
100 | $1.38e6\pm 1e6$ | $0.629\pm 0.1$ | $0.378\pm 0.2$ | $0.576\pm 0.02$

###  A.3 Sequential: Breakdown tables

In this section we give the results for each graph type separately for the
sequential setting as well as adding termination accuracy for the teacher
forcing setting.

Termination accuracy: We measure termination accuracy according the following
formula:

$\text{Term}=1-\frac{|T_{\text{pred}}-T_{\text{true}}|}{T_{\text{true}}},$ (1)

where $T_{\text{true}}$ is the correct integer last step and $T_{\text{pred}}$
the predicted last step. The theoretical possible range is $[1,-\infty]$,
where we reach $1$ only if predicting the correct step, as we go further away
from the correct last step we get smaller and possibly negative (this can only
happen by terminating much later than is correct). In practice, the range is
limited because we run the network for a maximum number of steps equal to the
number of nodes in the graph.

Table 8: Teacher forcing (seq.). | Dijkstra
---|---
Model | #Nodes | Next | Key | Pred. | Term.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.014$ | $0.016$ | $0.023$ | $0.0492$ | $0.0358$ | $0.0252$ | $0.003$ | $0.007$ | $0.004$ | $0.997$ | $0.993$ | $0.996$
50 | $0.101$ | $0.085$ | $0.079$ | $1.49$ | $0.127$ | $0.0903$ | $0.042$ | $0.008$ | $0.01$ | $0.962$ | $0.993$ | $0.994$
100 | $0.311$ | $0.367$ | $0.344$ | $13.4$ | $0.556$ | $0.373$ | $0.124$ | $0.041$ | $0.026$ | $0.921$ | $0.966$ | $0.984$
NE++ | 20 | $0.004$ | $0.01$ | $0.01$ | $0.00692$ | $0.0159$ | $0.00955$ | $0.002$ | $0.004$ | $0.003$ | $0.998$ | $0.996$ | $0.997$
50 | $0.311$ | $0.37$ | $0.369$ | $1.33e3$ | $0.919$ | $0.657$ | $0.238$ | $0.202$ | $0.194$ | $0.881$ | $0.937$ | $0.952$
100 | $0.75$ | $0.72$ | $0.718$ | $4.87e10$ | $3.61e4$ | $1.86e4$ | $0.621$ | $0.489$ | $0.456$ | $0.67$ | $0.922$ | $0.936$
|  | Most reliable
Model | #Nodes | Next | Key | Pred. | Term.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.079$ | $0.189$ | $0.253$ | $0.00376$ | $0.0252$ | $0.0502$ | $0.015$ | $0.049$ | $0.078$ | $0.985$ | $0.951$ | $0.922$
50 | $0.279$ | $0.561$ | $0.635$ | $0.00605$ | $0.0704$ | $0.126$ | $0.038$ | $0.133$ | $0.165$ | $0.964$ | $0.865$ | $0.833$
100 | $0.485$ | $0.786$ | $0.826$ | $0.00549$ | $0.111$ | $0.155$ | $0.083$ | $0.206$ | $0.225$ | $0.924$ | $0.789$ | $0.773$
NE++ | 20 | $0.173$ | $0.258$ | $0.284$ | $0.0116$ | $0.0337$ | $0.0621$ | $0.037$ | $0.058$ | $0.064$ | $0.963$ | $0.942$ | $0.936$
50 | $0.45$ | $0.612$ | $0.609$ | $0.0114$ | $0.0762$ | $0.122$ | $0.08$ | $0.107$ | $0.111$ | $0.926$ | $0.894$ | $0.889$
100 | $0.661$ | $0.817$ | $0.81$ | $0.0163$ | $0.109$ | $0.152$ | $0.177$ | $0.165$ | $0.16$ | $0.829$ | $0.833$ | $0.842$
Table 9: No algorithm (seq.). | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.000208$ | $5.14e\text{-}5$ | $5.29e\text{-}5$ | $0.01$ | $0.018$ | $0.04$ | $0.00923$ | $0.00912$ | $0.00651$ | $0.1$ | $0.209$ | $0.253$
50 | $2.91e6$ | $5.85$ | $6.33$ | $0.289$ | $0.03$ | $0.044$ | $12.3$ | $18.4$ | $29.4$ | $0.788$ | $0.948$ | $0.955$
100 | $1e17$ | $9700$ | $9360$ | $0.485$ | $0.039$ | $0.058$ | $1.24e6$ | $912000$ | $1.8e6$ | $0.694$ | $0.789$ | $0.82$
NE++ | 20 | $1.07e\text{-}5$ | $4.32e\text{-}6$ | $4.2e\text{-}6$ | $0.001$ | $0.004$ | $0.009$ | $0.000431$ | $0.000556$ | $0.000409$ | $0.042$ | $0.149$ | $0.188$
50 | $4.83$ | $0.369$ | $0.236$ | $0.094$ | $0.123$ | $0.229$ | $227$ | $75.2$ | $74.1$ | $0.495$ | $0.56$ | $0.643$
100 | $24900$ | $468$ | $221$ | $0.34$ | $0.365$ | $0.459$ | $8.28e13$ | $7.51e11$ | $4.5e11$ | $0.692$ | $0.806$ | $0.781$
Table 10: Multi-task (seq.) Trained with Prim and Widest respectively. | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.00436$ | $0.00319$ | $0.00332$ | $0.028$ | $0.038$ | $0.06$ | $0.254$ | $0.18$ | $0.188$ | $0.342$ | $0.444$ | $0.571$
50 | $14.4$ | $10.2$ | $10$ | $0.303$ | $0.045$ | $0.053$ | $1.19$ | $2.3$ | $2.05$ | $0.422$ | $0.528$ | $0.552$
100 | $88.6$ | $141$ | $147$ | $0.733$ | $0.102$ | $0.073$ | $2.24$ | $9.33$ | $7.83$ | $0.609$ | $0.598$ | $0.584$
NE++ | 20 | $0.000267$ | $0.000195$ | $7.37e\text{-}5$ | $0.01$ | $0.016$ | $0.031$ | $0.00255$ | $0.00246$ | $0.00337$ | $0.076$ | $0.178$ | $0.244$
50 | $0.372$ | $0.000154$ | $0.867$ | $0.294$ | $0.027$ | $0.163$ | $0.592$ | $0.00203$ | $0.00151$ | $0.177$ | $0.18$ | $0.198$
100 | $6.94$ | $0.301$ | $1.48$ | $0.493$ | $0.109$ | $0.245$ | $2.53$ | $0.00148$ | $0.00233$ | $0.432$ | $0.184$ | $0.184$
Table 11: No algorithm (par.) Pre-trained on Prim and Widest respectively. | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE Freeze | 20 | $0.0204$ | $0.0119$ | $0.00982$ | $0.048$ | $0.073$ | $0.122$ | $0.021$ | $0.0212$ | $0.0282$ | $0.171$ | $0.25$ | $0.322$
50 | $341$ | $16.8$ | $7.72$ | $0.466$ | $0.639$ | $0.687$ | $3.47e5$ | $4.07e5$ | $4.2e5$ | $0.876$ | $0.862$ | $0.856$
100 | $9.49e6$ | $4e4$ | $2.03e4$ | $0.793$ | $0.533$ | $0.494$ | $4.05e15$ | $5.36e15$ | $5.77e15$ | $0.82$ | $0.728$ | $0.734$
NE Fine-tune | 20 | $0.00341$ | $0.00159$ | $0.0013$ | $0.022$ | $0.049$ | $0.08$ | $0.0299$ | $0.0363$ | $0.0418$ | $0.143$ | $0.23$ | $0.307$
50 | $2.91e3$ | $245$ | $174$ | $0.366$ | $0.157$ | $0.2$ | $1.72e3$ | $2.11e3$ | $2.17e3$ | $0.47$ | $0.689$ | $0.749$
100 | $1.77e8$ | $6.98e5$ | $4.34e5$ | $0.557$ | $0.289$ | $0.317$ | $9.01e8$ | $1.15e9$ | $1.13e9$ | $0.716$ | $0.688$ | $0.724$
NE 2-Proc. | 20 | $0.00203$ | $0.00114$ | $0.000919$ | $0.023$ | $0.063$ | $0.093$ | $0.0124$ | $0.0157$ | $0.0207$ | $0.137$ | $0.226$ | $0.331$
50 | $36.2$ | $3.86$ | $2.51$ | $0.096$ | $0.156$ | $0.235$ | $175$ | $240$ | $198$ | $0.786$ | $0.698$ | $0.763$
100 | $3.07e4$ | $225$ | $339$ | $0.205$ | $0.356$ | $0.355$ | $7.27e9$ | $1.34e10$ | $1.59e10$ | $0.769$ | $0.824$ | $0.851$
NE++ Freeze | 20 | $0.00269$ | $0.000876$ | $0.000516$ | $0.035$ | $0.066$ | $0.089$ | $0.00641$ | $0.00619$ | $0.008$ | $0.091$ | $0.202$ | $0.303$
50 | $115$ | $6.53$ | $5.9$ | $0.802$ | $0.894$ | $0.828$ | $290$ | $549$ | $557$ | $0.415$ | $0.649$ | $0.676$
100 | $782$ | $2.87$ | $1.41$ | $0.8$ | $0.941$ | $0.946$ | $3.25e7$ | $1.03e8$ | $1.06e8$ | $0.562$ | $0.729$ | $0.725$
NE++ Fine-tune | 20 | $0.000788$ | $0.000284$ | $0.00017$ | $0.011$ | $0.034$ | $0.057$ | $0.00823$ | $0.0041$ | $0.00772$ | $0.103$ | $0.187$ | $0.284$
50 | $38$ | $1.42$ | $0.955$ | $0.927$ | $0.98$ | $0.98$ | $397000$ | $6.90e4$ | $7.12e4$ | $0.694$ | $0.773$ | $0.803$
100 | $7.54e4$ | $1.6$ | $1.26$ | $0.908$ | $0.99$ | $0.99$ | $1.49e15$ | $4.83e14$ | $4.76e14$ | $0.705$ | $0.824$ | $0.794$
NE++ 2-Proc. | 20 | $0.00694$ | $0.00375$ | $0.0026$ | $0.021$ | $0.05$ | $0.109$ | $0.00243$ | $0.00235$ | $0.00183$ | $0.088$ | $0.172$ | $0.201$
50 | $47.8$ | $0.546$ | $1.49$ | $0.508$ | $0.256$ | $0.306$ | $404$ | $290$ | $223$ | $0.61$ | $0.64$ | $0.681$
100 | $1.35e4$ | $119$ | $383$ | $0.764$ | $0.808$ | $0.764$ | $2.4e6$ | $4.44e6$ | $3.88e6$ | $0.771$ | $0.808$ | $0.795$

###  A.4 Parallel: Breakdown tables

In this section we give the results for each graph type separately for the
parallel setting as well as adding termination accuracy for the teacher
forcing setting.

Table 12: Teacher forcing (par.). | Bellman-Ford
---|---
Model | #Nodes | Key | Pred. | Term.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.194$ | $0.0416$ | $0.0131$ | $0.215$ | $0.175$ | $0.167$ | $0.551$ | $0.735$ | $0.733$
50 | $0.829$ | $0.0533$ | $0.0239$ | $0.212$ | $0.232$ | $0.235$ | $0.492$ | $0.708$ | $0.708$
100 | $1.75$ | $0.104$ | $0.0349$ | $0.22$ | $0.247$ | $0.291$ | $0.183$ | $0.644$ | $0.703$
NE++ | 20 | $0.478$ | $0.0883$ | $0.0324$ | $0.312$ | $0.244$ | $0.224$ | $0.603$ | $0.833$ | $0.854$
50 | $3.75$ | $0.111$ | $0.0602$ | $0.386$ | $0.348$ | $0.319$ | $0.373$ | $0.850$ | $0.850$
100 | $21.7$ | $0.201$ | $0.0841$ | $0.443$ | $0.391$ | $0.393$ | $0.202$ | $0.783$ | $0.876$
|  | Most reliable
Model | #Nodes | Key | Pred. | Term.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.123$ | $0.0533$ | $0.0251$ | $0.22$ | $0.243$ | $0.306$ | $0.766$ | $0.720$ | $0.781$
50 | $0.311$ | $0.0594$ | $0.034$ | $0.327$ | $0.287$ | $0.31$ | $0.122$ | $0.24$ | $0.818$
100 | $1.05$ | $0.0657$ | $0.0386$ | $0.38$ | $0.321$ | $0.312$ | $-1.68$ | $-1.61$ | $-0.0624$
NE++ | 20 | $0.0851$ | $0.0404$ | $0.0245$ | $0.269$ | $0.264$ | $0.315$ | $0.796$ | $0.721$ | $0.637$
50 | $0.185$ | $0.0423$ | $0.0325$ | $0.402$ | $0.308$ | $0.323$ | $0.460$ | $0.835$ | $0.828$
100 | $3.04$ | $0.0465$ | $0.0339$ | $0.477$ | $0.348$ | $0.327$ | $0.309$ | $0.851$ | $0.883$
Table 13: No algorithm (par.). | Dijkstra | Most reliable
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.0145$ | $0.0382$ | $0.00181$ | $0.03$ | $0.061$ | $0.079$ | $0.0204$ | $0.0187$ | $0.0147$ | $0.147$ | $0.233$ | $0.297$
50 | $177$ | $0.184$ | $0.00364$ | $0.304$ | $0.096$ | $0.091$ | $0.4$ | $0.0201$ | $0.0212$ | $0.298$ | $0.331$ | $0.352$
100 | $5.93e6$ | $1.21$ | $0.00474$ | $0.54$ | $0.126$ | $0.116$ | $31$ | $0.0262$ | $0.0295$ | $0.5$ | $0.403$ | $0.403$
NE++ | 20 | $0.00528$ | $0.00152$ | $0.000793$ | $0.012$ | $0.026$ | $0.046$ | $0.0147$ | $0.00904$ | $0.00498$ | $0.064$ | $0.157$ | $0.214$
50 | $0.671$ | $0.00489$ | $0.00155$ | $0.072$ | $0.045$ | $0.055$ | $0.0955$ | $0.00768$ | $0.00675$ | $0.133$ | $0.186$ | $0.193$
100 | $589$ | $0.0192$ | $0.00215$ | $0.148$ | $0.068$ | $0.068$ | $361$ | $0.0112$ | $0.0108$ | $0.24$ | $0.21$ | $0.202$
Table 14: No algorithm (par.) Pre-trained on BFS and Widest respectively. | Bellman-Ford | Most reliable
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE Freeze | 20 | $0.253$ | $0.246$ | $0.00821$ | $0.078$ | $0.103$ | $0.151$ | $0.577$ | $0.0559$ | $0.0599$ | $0.229$ | $0.305$ | $0.431$
50 | $8.28e5$ | $1.18$ | $0.0176$ | $0.319$ | $0.169$ | $0.187$ | $2.76e4$ | $0.294$ | $0.197$ | $0.378$ | $0.484$ | $0.547$
100 | $1.53e17$ | $5.36$ | $0.0272$ | $0.434$ | $0.221$ | $0.222$ | $6.73e10$ | $1.61$ | $1.15$ | $0.508$ | $0.573$ | $0.611$
NE Fine-tune | 20 | $0.0635$ | $0.0475$ | $0.00463$ | $0.038$ | $0.078$ | $0.101$ | $0.029$ | $0.0224$ | $0.0148$ | $0.164$ | $0.237$ | $0.311$
50 | $74.8$ | $0.271$ | $0.00829$ | $0.231$ | $0.124$ | $0.13$ | $0.95$ | $0.0206$ | $0.0262$ | $0.318$ | $0.318$ | $0.358$
100 | $515000$ | $0.931$ | $0.013$ | $0.413$ | $0.162$ | $0.151$ | $691$ | $0.034$ | $0.0364$ | $0.437$ | $0.374$ | $0.394$
NE 2-Proc. | 20 | $0.128$ | $0.226$ | $0.00439$ | $0.051$ | $0.097$ | $0.14$ | $0.0326$ | $0.0243$ | $0.0157$ | $0.138$ | $0.223$ | $0.317$
50 | $1.68e3$ | $1.02$ | $0.00731$ | $0.615$ | $0.143$ | $0.165$ | $11.2$ | $0.0195$ | $0.0231$ | $0.284$ | $0.327$ | $0.38$
100 | $4.99e6$ | $1.86$ | $0.00816$ | $0.878$ | $0.196$ | $0.194$ | $1.44e6$ | $0.0403$ | $0.0474$ | $0.43$ | $0.428$ | $0.435$
NE++ Freeze | 20 | $0.0281$ | $0.0573$ | $0.00251$ | $0.028$ | $0.082$ | $0.095$ | $0.0196$ | $0.0114$ | $0.00888$ | $0.15$ | $0.236$ | $0.362$
50 | $172$ | $0.181$ | $0.00515$ | $0.383$ | $0.123$ | $0.114$ | $1.87$ | $0.0139$ | $0.0153$ | $0.259$ | $0.315$ | $0.385$
100 | $1.45e7$ | $1.71$ | $0.00734$ | $0.609$ | $0.171$ | $0.141$ | $19800$ | $0.0282$ | $0.0233$ | $0.384$ | $0.394$ | $0.406$
NE++ Fine-tune | 20 | $0.258$ | $0.246$ | $0.00939$ | $0.078$ | $0.139$ | $0.203$ | $0.0216$ | $0.012$ | $0.00804$ | $0.132$ | $0.202$ | $0.265$
50 | $5.73e3$ | $1.24$ | $0.0223$ | $0.494$ | $0.198$ | $0.224$ | $8.49$ | $0.00868$ | $0.00788$ | $0.227$ | $0.248$ | $0.256$
100 | $3.86e9$ | $7.07$ | $0.0267$ | $0.724$ | $0.288$ | $0.269$ | $12500$ | $0.0115$ | $0.00801$ | $0.394$ | $0.283$ | $0.274$
NE++ 2-Proc. | 20 | $0.019$ | $0.0444$ | $0.00353$ | $0.028$ | $0.068$ | $0.09$ | $0.0168$ | $0.0138$ | $0.00868$ | $0.113$ | $0.194$ | $0.281$
50 | $1.69$ | $0.302$ | $0.00598$ | $0.11$ | $0.098$ | $0.106$ | $9.11$ | $0.0107$ | $0.0112$ | $0.374$ | $0.266$ | $0.299$
100 | $30$ | $2.46$ | $0.00767$ | $0.234$ | $0.14$ | $0.13$ | $1740$ | $0.0131$ | $0.0107$ | $0.564$ | $0.324$ | $0.344$
Table 15: Multi-task (par.) Trained with BFS and Widest respectively. | Bellman-Ford | Most reliable
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE | 20 | $0.037$ | $0.00771$ | $0.00163$ | $0.017$ | $0.036$ | $0.05$ | $0.324$ | $0.121$ | $0.0748$ | $0.331$ | $0.327$ | $0.38$
50 | $18.6$ | $0.036$ | $0.0028$ | $0.045$ | $0.054$ | $0.053$ | $0.976$ | $0.15$ | $0.0948$ | $0.402$ | $0.334$ | $0.349$
100 | $3270$ | $1320$ | $0.0043$ | $0.114$ | $0.106$ | $0.067$ | $1.53$ | $0.199$ | $0.114$ | $0.443$ | $0.344$ | $0.34$
NE++ | 20 | $0.00868$ | $0.0015$ | $0.000407$ | $0.012$ | $0.019$ | $0.038$ | $0.00741$ | $0.00632$ | $0.00643$ | $0.067$ | $0.177$ | $0.216$
50 | $0.0382$ | $0.00339$ | $0.000544$ | $0.023$ | $0.031$ | $0.036$ | $0.0095$ | $0.00537$ | $0.00927$ | $0.165$ | $0.184$ | $0.197$
100 | $26.5$ | $0.00565$ | $0.000693$ | $0.287$ | $0.053$ | $0.049$ | $0.00929$ | $0.00739$ | $0.0124$ | $0.24$ | $0.199$ | $0.197$

###  A.5 Parallel TF & transfer results

In the main paper we did not give the results for all the transfer methods
(only the best one). In this section we give the transfer results in the same
style as the main paper as well as the teacher forcing results.

Table 16: Teacher forcing (par.). | Bellman-Ford | Most reliable path
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
NE | 20 | $0.0828\pm 0.08$ | $0.186\pm 0.02$ | $0.067\pm 0.04$ | $0.256\pm 0.04$
50 | $0.302\pm 0.4$ | $0.226\pm 0.01$ | $0.135\pm 0.1$ | $0.308\pm 0.02$
100 | $0.629\pm 0.8$ | $0.253\pm 0.03$ | $0.383\pm 0.5$ | $0.337\pm 0.03$
NE++ | 20 | $0.199\pm 0.2$ | $0.26\pm 0.04$ | $0.05\pm 0.03$ | $0.283\pm 0.02$
50 | $1.31\pm 2$ | $0.351\pm 0.03$ | $0.0866\pm 0.07$ | $0.344\pm 0.04$
100 | $7.33\pm 10$ | $0.409\pm 0.02$ | $1.04\pm 1$ | $0.384\pm 0.07$
Table 17: No algorithm (par.) Pre-trained on BFS and Widest respectively. | Bellman-Ford | Most reliable path
---|---|---
Model | #Nodes | Key | Predecessor | Key | Predecessor
NE Freeze | 20 | $0.169\pm 0.1$ | $0.111\pm 0.03$ | $0.231\pm 0.2$ | $0.322\pm 0.08$
50 | $2.76e5\pm 4e5$ | $0.225\pm 0.07$ | $9.18e3\pm 1e4$ | $0.47\pm 0.07$
100 | $5.1e16\pm 7e16$ | $0.292\pm 0.1$ | $2.24e10\pm 3e10$ | $0.564\pm 0.04$
NE Fine-tune | 20 | $0.0386\pm 0.02$ | $0.072\pm 0.03$ | $0.0221\pm 0.006$ | $0.237\pm 0.06$
50 | $25\pm 40$ | $0.162\pm 0.05$ | $0.332\pm 0.4$ | $0.331\pm 0.02$
100 | $1.72e5\pm 2e5$ | $0.242\pm 0.1$ | $230\pm 300$ | $0.402\pm 0.03$
NE 2-Proc. | 20 | $0.119\pm 0.09$ | $0.096\pm 0.04$ | $0.0242\pm 0.007$ | $0.226\pm 0.07$
50 | $562\pm 800$ | $0.308\pm 0.2$ | $3.73\pm 5$ | $0.33\pm 0.04$
100 | $1.66e6\pm 2e6$ | $0.423\pm 0.3$ | $4.8e5\pm 7e5$ | $0.431\pm 0.003$
NE++ Freeze | 20 | $0.0293\pm 0.02$ | $0.068\pm 0.03$ | $0.0133\pm 0.005$ | $0.249\pm 0.09$
50 | $57.5\pm 80$ | $0.207\pm 0.1$ | $0.633\pm 0.9$ | $0.32\pm 0.05$
100 | $4.85e6\pm 7e6$ | $0.307\pm 0.2$ | $6.59e3\pm 9e3$ | $0.395\pm 0.009$
NE++ Fine-tune | 20 | $0.171\pm 0.1$ | $0.14\pm 0.05$ | $0.0139\pm 0.006$ | $0.2\pm 0.05$
50 | $1.91e3\pm 3e3$ | $0.305\pm 0.1$ | $2.83\pm 4$ | $0.244\pm 0.01$
100 | $1.29e9\pm 2e9$ | $0.427\pm 0.2$ | $4.16e3\pm 6e3$ | $0.317\pm 0.05$
NE++ 2-Proc. | 20 | $0.0223\pm 0.02$ | $0.062\pm 0.03$ | $0.0131\pm 0.003$ | $0.196\pm 0.07$
50 | $0.666\pm 0.7$ | $0.105\pm 0.005$ | $3.04\pm 4$ | $0.313\pm 0.05$
100 | $10.8\pm 10$ | $0.168\pm 0.05$ | $579\pm 800$ | $0.411\pm 0.1$

###  A.6 Multi-task pre-training: Full breakdown

Table 18: 2-Processor transfer pre-trained on Prim, Dijkstra, & DFS for sequential and BFS & Bellman-Ford for parallel. | Most reliable (Seq.) | Most reliable (Par.)
---|---|---
Model | #Nodes | Key | Pred. | Key | Pred.
2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA | 2d-G | ER | BA
NE++ 2-Proc. | 20 | $0.00265$ | $0.00244$ | $0.002$ | $0.097$ | $0.161$ | $0.232$ | $0.0518$ | $0.0297$ | $0.041$ | $0.153$ | $0.214$ | $0.313$
50 | $29.4$ | $72.3$ | $86.9$ | $0.535$ | $0.629$ | $0.654$ | $0.341$ | $0.0611$ | $0.0821$ | $0.414$ | $0.311$ | $0.366$
100 | $1.13e6$ | $2.06e6$ | $2.08e6$ | $0.663$ | $0.8$ | $0.812$ | $7.81$ | $0.106$ | $0.105$ | $0.558$ | $0.383$ | $0.403$

###  A.7 Large standard deviations

The large standard deviation is to be expected given the widely different
graph types. Given that all edge weights have expected value 0.6 the max
expected shortest distance in a grid graph of size n is 0.6*(n/2+1), which is
orders of magnitude larger than for an Erdos-Renyi or Barabasi-Albert graph,
which will have a diameter of O(log(n)) and thus a max expected shortest
distance of 0.6*log(n). This large difference in the shortest path makes large
key errors when generalising much more likely on a grid-graph than on the
other types of graphs. Vice versa is true for predecessor prediction: on a
grid graph the degree of node is between 2 and 4 (constant no matter the size
of the graph), while for a Barabasi-Albert and Erdos-Renyi graph it will grow
with the size of the graph and be much larger, making errors much more likely.
Again yielding vastly different error percentages. See the breakdown across
graph types in the tables above.

###  A.8 Further experiments

####  A.8.1 Experiment 1

Table 19: Pre-train on Dijkstra with teacher forcing, transfer with a frozen processor to see to what extent the encoder/decoder can be recovered. | Dijkstra
---|---
Model | #Nodes | Next | Key | Predecessor
NE 2-Proc. | 20 | $0.114\pm 0.03$ | $0.226\pm 0.09$ | $0.023\pm 0.002$
50 | $0.457\pm 0.03$ | $3.51\pm 4$ | $0.083\pm 0.03$
100 | $0.759\pm 0.02$ | $132\pm 200$ | $0.226\pm 0.1$
NE++ 2-Proc. | 20 | $0.11\pm 0.01$ | $0.253\pm 0.1$ | $0.078\pm 0.03$
50 | $0.619\pm 0.06$ | $4.35\pm 4$ | $0.344\pm 0.02$
100 | $0.839\pm 0.03$ | $35.1\pm 40$ | $0.557\pm 0.09$

Conclusion from Table 20: The results are mostly quite similar to the original
results, but slightly worse, thus indicating that while the re-use of a pre-
trained processor is not trivial it is no the primary reason for transfer to
fail.

####  A.8.2 Experiment 2

Table 20: Pre-train on Dijkstra with teacher forcing, transfer with a frozen processor to see to what extent the encoder/decoder can be recovered. | Dijkstra
---|---
Model | #Nodes | Key | Predecessor
NE 2-Proc. | 20 | $0.00653\pm 0.005$ | $0.092\pm 0.04$
50 | $16900\pm 20000$ | $0.401\pm 0.05$
100 | $1.11e+12\pm 2e+12$ | $0.771\pm 0.2$
NE++ 2-Proc. | 20 | $0.000531\pm 0.0003$ | $0.05\pm 0.03$
50 | $12.1\pm 10$ | $0.249\pm 0.1$
100 | $74500\pm 100000$ | $0.502\pm 0.07$
NE Finetune | 20 | $0.00029\pm 0.0003$ | $0.026\pm 0.01$
50 | $794000\pm 1e+06$ | $0.441\pm 0.07$
100 | $8.32e+15\pm 1e+16$ | $0.627\pm 0.09$
NE++ Finetune | 20 | $0.000192\pm 0.0002$ | $0.027\pm 0.02$
50 | $20100\pm 30000$ | $0.67\pm 0.1$
100 | $1.25e+14\pm 2e+14$ | $0.716\pm 0.05$
NE Freeze | 20 | $0.000623\pm 0.0004$ | $0.041\pm 0.02$
50 | $79.2\pm 90$ | $0.37\pm 0.09$
100 | $1.23e+06\pm 2e+06$ | $0.862\pm 0.08$
NE++ Freeze | 20 | $0.0108\pm 0.007$ | $0.096\pm 0.05$
50 | $152\pm 200$ | $0.336\pm 0.01$
100 | $3.29e+09\pm 4e+09$ | $0.522\pm 0.09$
NE Multi-task | 20 | $0.0994\pm 0.1$ | $0.129\pm 0.08$
50 | $0.926\pm 1$ | $0.155\pm 0.1$
100 | $3.77\pm 4$ | $0.212\pm 0.1$
NE++ Multi-task | 20 | $1.47\pm 2$ | $0.363\pm 0.07$
50 | $5.2e+09\pm 5e+09$ | $0.769\pm 0.1$
100 | $3.14e+29\pm 3e+29$ | $0.752\pm 0.05$

###  A.9 NeuralExecutor++

Let $X\in\mathbb{R}^{n\times k}$ be node states, where $n,k$ are the number of
nodes and features, respectively. Each edge $(u,v)$ has a weight
$w(u,v)\in\mathbb{R}$. The architecture keeps a hidden state for each node
$H\in\mathbb{R}^{n\times l}$ with $l$ features, which is initialised to all
zeros at time step 0. The encoder $\mathcal{E}$ consists of a 2 layer MLP with
ReLU activation and is separate for each algorithm. The encoder is applied on
each edge a hidden embedding
$\mathcal{E}(X^{(t)}_{i},H^{(t)}_{i},X^{(t)}_{j},H^{(t)}_{j},W^{(t)}_{ij})=Z^{(t)}_{ij}$,
where $t$ indicates the $t$th time step in the computation and $i,j$ refer to
the nodes of the edge. This edge embedding is then passed to the message
function of the processor $\mathcal{P}$, which is message passing neural
network (MPNN) with a $\max$ aggregator with linear message and update
functions (these message and update functions are always shared between all
algorithms). The processor computes the new hidden state for each node
$\mathcal{P}(H_{i},A,W)=H_{t+1}$. Then, we have the decoder
$\mathcal{D}(Z_{t},H_{t+1})=Y_{t+1}$ and predecessor predictor
$\mathcal{S}(Z_{t},H_{t+1})=S_{t}$. Finally, a termination network
$\sigma(\mathcal{T}(H_{t+1}))$ decides whether we should terminate or not.