Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks
Authors: Sadegh Mahdavi
Kevin Swersky
Thomas Kipf
Milad Hashemi
Christos Thrampoulidis
Renjie Liao
Venue: Accepted by TMLR ()

Abstract: In this paper, we study the OOD generalization of neural algorithmic reasoning tasks, where the goal is to learn an algorithm (e.g., sorting, breadth-first search, and depth-first search) from input-output pairs using deep neural networks. First, we argue that OOD generalization in this setting is significantly different than common OOD settings. For example, some phenomena in OOD generalization of image classifications such as \emph{accuracy on the line} are not observed here, and techniques such as data augmentation methods do not help as assumptions underlying many augmentation techniques are often violated. Second, we analyze the main challenges (e.g., input distribution shift, non-representative data generation, and uninformative validation metrics) of the current leading benchmark, i.e.,  CLRS \citep{deepmind2021clrs}, which contains 30 algorithmic reasoning tasks. We propose several solutions, including a simple-yet-effective fix to the input distribution shift and improved data generation. Finally, we propose an attention-based 2WL-graph neural network (GNN) processor which complements message-passing GNNs so their combination outperforms the state-of-the-art model by a $3\%$ margin averaged over all algorithms. 

Published in Transactions on Machine Learning Research (03/2023)
Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks
Sadegh Mahdavi University of British Columbia
smahdari@ece.uber ubc.c
Kevin Swersky
ksuerskyy@gooolle.co
Google Research, Brain Team
Thomas Kipf
tkipf@ com
Google Research, Brain Team
Milad Hashemi
miladh @google.
Google Research, Brain Team
Christos Thrampoulidis
cthrampo@ece.ubc. ubc.c.
University of British Columbia
Renjie Liao
rjliaoBece. ubc.
University of British Columbia
Reviewed on OpenReview: https: // oppenreveee.... net/ formm? id= dd=krrtuflp33
Abstract
In this paper, study the OOD generalization of neural algorithmic reasoning tasks, where the goal is to learn algorithm (e.g., sorting, breadth-first search, and depth-first search) from input-output pairs using deep neural networks. First, argue that OOD generalization in this setting is significantly different than common OOD settings. For example, some phenomena in OOD generalization of image classifications such as accuracy on the line are not observed here, and techniques such as data augmentation methods do not help as assumptions underlying many augmentation techniques are often violated. Second, analyze the main challenges (e.g., input distribution shift, non-representaaive data generation, and uninformative validation metrics) of the current leading benchmark, i.e., CLRS (Veličković et al.) 2021), which contains 30 algorithmic reasoning tasks. We propose several solutions, including & simple-yet-effective fix to the input distribution shift and improved data generation. Finally, we propose an attention- based 2WL-graph neural network (GNN) processor which complements message-passing GNNs so their combination outperforms the stato-of-the-art model by a 3% margin averaged over all algorithms. Our code is available al: http:://ggtttb..coom/mllaa/////s smahdavi4/clrs
1 Introduction
Algorithms have been vital part of today's computing systems, solving tasks ranging from scheduling to finding the shortest path in real-world maps. Algorithms often come with benefits like performance guaranlees, provable correct ness, and generalization to various instances. Designing algorithms to solve tasks, however, can be quite hard in many situations. For instance, given any task, a computer scientist has to either follow some existing algorithm paradigms (e.g., divide and conquer) or come up with some new algorithm, which typically requires significant hand-design efforts. Morcover, some problems lie in the NP-hard class of which the solutions require exponential amount of time for execution, and designing efficient approximate

---

Existing works have shown that this problem is challenging, especially when the model is evaluated on Published in Transactions on Machine Learning Research (03/2023)
algorithms for such problems often requires several years of research. Finally, executing algorithm often requires preprocessing data into a predefined format before feeding the data into a computer program. On the other hand, deep learning has been successful in solving tasks of many domains without much task-specific adaptation. For instance, a Transformer (Vaswani et al. 2017 could solve image classification, machine translation, and language modeling with negligible changes to its architecture. Moreover, deep learning models are well known for their ability in solving tasks an end-to-end fashion, thus removing the necessity of data preprocessing and feature design. Neural networks, however, are not resilient to distribution shifts, and their symbolic manipulation and reasoning capabilities are limited (Zhang et al. 2021
Therefore, it is natural to ask whether one can leverage deep neural networks to mimic algorithms, i.e., neural networks execute the same computation as given algorithms. The hope is to combine the strength of both worlds, e.g., 1) performance guarantees, generalization to various instances, and transferability across tasks from algorithms, and 2) end-to-end training, universal approximation, and fast parallel computation from neural networks. Recently, researchers have been working on this problem and the area is dubbed as Neural Algorilhmic Reasoning (Veličković & Blundell 2021). Here, the goal is not only to enhance the symbolic manipulation and reasoning capabilities of neural networks but also to leverage them to find more efficient and faster algorithms.
test samples that are drawn from a different distribution than train samples (f.e., it is hard to generalize to out-of-distribution data) Veličković et al. (2021). For example, while deep neural networks could be trained to perform sorting on sequences of a given, fixed length, when faced with longer sequences, their performance drops substantially (Varis & Bojar 2021]. In this work, we analyze the out-of-distribution (OOD) generalization of neural networks algorithmic reasoning tasks. We first investigate several challenges with OOD generalization in our problem context and propose solutions to some of the issues that arise. In particular, our contributions are as follows:
In Section 3 based on the CLRS benchmark, we show how OOD settings of neural algorithmic reasoning tasks are different from common ones (Section 3.1 and identify several key challenges: input distribution shift (Section 3.2 unrepresentative dataset generation in both train and test. (Section 3.3). model selection difficulties due to near-perfect in-distribution validation metrics (Section 3.4. and a systematic investigation of OOD generalization under controlled distribution shift of graph sizes and node degrees (Section 3.5
In Soction 4 wC propose solutions to some of these challenges, including 1) cnlarging the in-distribution
training dataset. to push the limits of OOD performance (Section 4.1 2) simple-yet-effective fix
to input distribution shift (Section 4.2), 3) an attention-based 2-WT, graph neural network (GNN) (Morris et al.] 2019) processor that significantly outperforms the state-of-the-art when combined with message passing GNNs (Sections
4.3 and 4.4
2 Background
We follow the setup of the CLRS benchmark (Veličković et al. 2021). All algorithmic tasks are translated and represented as graphs (possibly empty or fully-connected) with task-specific hate///de//rrpppp feature inputs and mode/edge//ee sadge/graph--evel target outputs. Fach task also contains the ground truth values of all variables presented in intermediate steps of an algorithm, which are called hints and could be used as additional supervision to train the model. The aim of hints to help mimic individual steps of the underlying algorithm and finally predict the target output.
Each instance of a task contains a graph G = (V,E) with a set of n nodes V = (W1, u2,..., bn and m edges E = {a = (Mi V;z) Wi Vig E v, < < m) with an adjacency matrix A E Roxx, edge feature tensor X5 E xde and node feature matrix Xy E Raddy We eschew an explicit graph feature vector as it could be represented as a concatenation of features to the node feature matrix. For a node (column) vector 2,, we use capital from Z indicate a vertically stacked matrix (one row per node) of all node vectors across the graph. Moreover, we denote column-wise concatenation of two matrices rewtorss F. and F as E, F
2

---

Published in Transactions on Machine Learning Research (03/2023)
Node Embedding
GNN(xI)
Message Passing
Poanast
Decoder
Enc
Proc
Dec
Figure 1: Encode-processe process-decode visualization for the BFS task. The input is a graph with starting node index of two. The node representations are encoded into a latent space. Then T consecutive steps of processing are applied to the latent dimensions using a GNN. Finally, the output pointer for each node is decided by pairwise comparisons of node representations.
All models consider are GNNs with an algorithm with T iterative steps, consider recurrent GNN whole message passing steps correspond to algorithms steps. At each step (1 < t T) of processing, all input features are embedded into embedding vectors Zimp, E dh by their corresponding encoders, for each individual node E V. The processor then takes the embedding vectors and the hidden states at step and outputs the hidden representations of step + 1. Formally, a (simplified) formula for the processor is as follows:
framework (Battaglia et al. 2018). For an
H(++1) = GNN([ H(),, Zinp A),
(1)
where GNN(X, A) represents the one-step computation process of a GNN processor with input node features X and adjacency matrix A. Finally, outputs are decoded using simple MLP per node/edge, with shared parameters. The loss value is evaluated based on the outputs of decoders at itcration
better illustrate this framework, we explain how Breadth-first Search (BFS) is formulated in this framework. Given an input undirected graph and a starting node, the task is to predict for each node the pointer to its predocessor when applying BFS this graph. Namely, we have two-dimensional node features Xy R where the first dimension determines the index of node and the second dinension determines whether the node is the starting node. We also have the adjacency matrix A of the graph. The encoder is linear layer with a weight matrix Wene E _2xd, where d, is the latent embedding size. Then, for the processing step, T recurrent steps of GNN are applied to the latent space with adjacency matrix A to get the final latent node representations HT) E Raxds Finally, for each pair of nodes i.j (1 S ú, S n), a score 04, determines how likely i points to j the predecessor and 0 arg max, 0i is the predicted output pointer of node i. To compute 04, we can apply an MLP to [n(",, .n.] followed by a (row-wise) Softmax non-linearity. The loss for this task is a cross-entropy loss between predicted row scores og,; and the true (one-hot row-wise) pointer scores for each node i. This process is illustrated in Figure [ For additional examples, see Appendix A.3
As the processor considered the central part of this architecture, here we explain the three processor baselines used by the benchmark:
MPNN Gilmer el al. 2017): A message passing neural nelwork with a max-aggregation. On the benchmark, this processor assumes a fully connected graph regardless whether the downstream task contains any graph or not. We regard this fully-connected MPNN processor as MPNN-FC. We also consider the original MPNN which operates on given graphs (if graphs are uavailable for task, a fully connected graph used), and call it MPNN-G.
3

---

Published in Transactions on Machine Learning Research (03/2023)
Table 1: Test scores three processors (MPNN-FC, PGN, GAT) on the CLRS benchmark proposed by Veličković et al. (2021) on all 30 algorithms averaged over three random sceds. The performances with hints are lower on the majority of algorithms, for all processors. The mean is taken over all 30 algorithms, the wins are taken within each processor. For each algorithm, win is declared when the score for that algorithm is higher than the alternative (i.e., with vs. without hints).
Method
MPNN-FC
PGN
GAT
Use Hints
Yes
No
Yes
No
Yes
No
Mean
51.02
60.04
52.31
57.02
44.69
49.53
Wins
8/30
22/30
10/30
20/30
14/30
16/30
PGN (Veličković et al. 2020a):: Similar to MPNN, but PGN operates on a graph derived from both the input and hints. When no hints are available, and the lask does not contain any graph, it assumes an empty graph and hence behaves the same as DeepSets (Zaheer et al. 2017).
GAT (Veličković et al. 2018): Similar to PGN, but GAT replaces the max-aggreationn-baad message passing in MPNN with the attention based one.
To fairly benchmark these processors, the encoder and the decoder are controlled to be the same.
3 Current Challenges of OOD generalization of Neural Algorithmic Reasoning Tasks
In the CLRS, Veličković et al. 2021 measures both the in-distribution (TD) and the out-of-distribution (OOD) generalization of the aforementioned processors over 30 classical algorithms. For example, they generate validation graphs from the same distribution as training but generate testing graphs from different distributions, e.g., larger sizes in lerms of the number of nodes. Table contains the OOD test accuracies of the algorithms when using hints (i.e. intermediate steps). We also include the performance the different. models when disabling hints. As the table shows, in the current form of benchmark, hints do not bring any performance gain on the final output for the majority of algorithms. Moreover, to learn algorithms beyond those in the CLRS benchmark, hints might be unavailable infeasible to collect at all (e.g., NP-hard problems). Based on these considerations, end-to-end training with only the supervision of the final output. In the following, highlight the fundamental challenges in the OOD generalization of neural algorithmic reasoning in the CLRS.
deactivate hints for the rest of the paper and instead focus
3.1 Difference with Common OOD Settings
Several recent works have studied the problem of OOD generalization in both image and graph domains (Arjovsky et al., 2019 Anil et al. 2022 Ovadia et al. 2019 Chen et al. 2022). However, the nature of OOD generalization in neural algorithmic reasoning is fundamentally different from these works. To illustrate an example, consider the phenomena of accuracy on the line (Miller et al. 2021 for image classifications where some works have observed the OOD performance has a linear relationship with (and often is close to) ID performance in some image classification benchmarks. However, in our setting, we often observe perfect ID generalization with poor (sometimes even less than random guesses) OOD accuracy, and OOD generalization might keep improving after the ID validation performance completely saturates (see Bridges task in Figure 2a Moreover, popular data augmentation technique
effective remedy for OOD generalization (Gulrajani & Lopez- Paz 2021 Wenzel et al. 2022), are generally inapplicable to our setting, For instance, Mixup (Zhang ct al. 2018) assumes convex combinations of inputs have the same convex combination of outputs, but for many algorithms, a convex combination of inputs from two tasks creates a new task with output siguificantly different from the convex combination of outputs from two tasks (e.g., sorting the average of two sequences creates a whole new task, and the output is not a lincar function of outputs of two tasks), thus violating the assumptions of Mixup. Even graph-specific data augmentation methods are generally inapplicable. For instance, DropEdge (Rong et al. 2020 assumes by randomly dropping an edge in the graph, the target.
4

---

Published in Transactions on Machine Learning Research (03/2023)
Br1dgis
Liearf2
000 8200922
50
02
DrapEdge
20
120
20
63
60
100
0.00 ACUUICI
80
03
0.4
0.5
GG
Mixup
23
Q3
20
120
20
63
80
100
(b) Data augmentation failure modes
(a) ID vs OOD accuracy relation
Figure 2: (a) In-distribution (ID) accuracy (X-axis) vs OOD accuracy (y-axis) during different optimization steps for four different algorithms; in contrast to previous literature (Miller et al. 2021), either the linear correlation non-existent, or the slope of the line is far from being onc. (b) Failure of two widely-used data augmentation methods when applied to neural algorithmic reasoning tasks. Top: dropping a single edge (Rong al.) 20200) on DFS (starting from node 1) causes all of the output pointers in the graph (i.e. red arrows) to reverse direction. Bottom: using Mixup (Zhang et al. 2018) for sorting convex node-wise combination of two sequences leads to new sequence to sort, rather than the node-wise convex combination of labels of nodes of each sequence.
output stays the same. However, for many graph algorithms, altering any edge could change the output of the underlying task significantly. For example, performing DFS on a ring graph is an extreme failure example, since removing single edge changes the outputs (e.g., pointers of nodes to be visited next) of all nodes in the graph. See Figure 2b for illustration of the failure modes of such examples.
A recent line of work has particularly investigated OOD generalization in GNN settings. However, the assumptions they make about generalization across environments (in our case graph sizes) are invalid to the neural algorithmic reasoning. Yehudai et al. (2021) studied such generalization from local k-hop neighborhood perspective (where l the number of GNN layers) and connected failures generalization distribution shifts in the such local neighborhood. For algorithmic tasks, the numbers of reasoning steps are large (sometimes larger than the number of nodes) that such local neighborhood often contains the whole graph and the analysis would be vacuous. Some prior works have also analyzed the OOD generalization through the lens of graphons (Zhou et al.) 2022 Bevilacqua et al. 2021 Maskey et al. 2022) where graphs along with labels are drawn from some grahpon models. In these settings, the implicit assumption is that if we restrict the original graph to a subgraph induced by a subset of its nodes, the labels within the subgraph stay the same. However, this favorable property does not hold in neural algorithmic reasoning tasks. For instance, consider the DFS example in Figure 2b By removing node "2" and restricting the graph to the rest of the nodes, all the pointers turn into clockwise order; hence the outputs change when restricting graph to a smaller subset of its nodes. In algorithmic reasoning tasks, the relation between ID and OOD generalization is much more intricate than the above assumptions; the only connecting point between the larget label of each task across different graph sizes is they are generated using the same algorithm. This makes even formulating the OOD generalization and the desired invariance properties in such tasks nontrivial. Although some prior works have discovered some desirod invariance propertics of a model for stronger OOD generalization of some algorithmic tasks, such as homogeneity of the neural network (Tang al., 2020 finding sufficient conditions remains open question.
5

---

Published in Transactions on Machine Learning Research (03/2023)
3.2 Distribution Shift in Input Representations
Beyond improving models, finding suitable data representations to facilitate OOD generalization is also crucial. For instance, all algorithms in the CLRS benchmark receive the node indices as part of their input. For several tasks, this node index serves as a unique flag (e.g., Convex Hull, Bridges), for others, the ordering plays an important role in the algorithm behavior (e.g., DFS algorithm starts with a node with the lowest index, then, at each step, an unexplored neighbor with the lowest index gets expanded), As a result, the model must be able to compare node indices to be able to exccute the algorithm.
The current. node index implemented in the CLRS (Velickovié et al. 2021 appends scalar pos,, (i - to the feature vector of each node U with index i, (1 n). This kind of representation makes it harder for processor to generalize when such ordering is important in task. For instance, despite the model being able to reach perfect ID accuracy lo execute DFS on 16-node graphs; it fails to do so when we feed the induced subgraph of the first quarter nodes of a 64-node graph. This is while the graphs are still in-distribution, and the only difference is that the indices have shifted from 16 equispaced indices in the range [0, 1] to 16 equispaced indices in the range [0, 0.25]. In Section 4.2 we explore two different possible mitigations to such a distribution shift for node indices.
(1-1)/n 1)/n
3.3 Unrepresentative Dataset Generation
The graphs in the CLRS benchmark are sampled using Erdös Rényi (ER) model with a fixed probability p (where p = 0.5 in most cases) and pode/eedg//rrap-llee random (mostly from [0, 1)). In this strategy, sampling is uniform and all possible graphs (of the same size) have an equal probability of being present in the datasct. However, it takes many samples for this random graph model to sample diverse graphs (e.g., node-degree and the nunber of edges in ERs concentrate around (n - 1)p and n(n 1)p/2 respectively). This raises two issues, especially in the low-data regime (i.e., fewer training data).
scalar input features are generated uniformly at
First, the training data might not be enough to uniquely identify the underlying algorithm (e.g., BFS and DFS have the same output pointers on the class of tree graphs - all nodes point to their parents towards the root) and the OOD generalization should not be expected in this case.
Second, and perhaps more importantly, the test dataset may lurn into poor performance measure as it is not diverse enough and biased. This bias may allow cheating solutions to gain higher scores, especially when extrapolating (Angelini & tasks in the CLRS are Articulation Points and Bridges. In these tasks, the goal is to identify the modes/edger whose removal increases the number of connected components of the underlying graph. Here, if a graph is too sparse, trivial /ardige/artiiotliion points appear in the graph. On the other hand, a dense graph leads to no such nodes/ nodes/odges. /dges.. In Section 4.4. we report 98.69% OOD accuracy on the Bridges task using a hybrid combination of 2WL and MPNN-G processor. At first sight, the Bridges algorithm seems to be completely solved and the model can reliably find the bridges in graph. However, the test dataset is not rich enough for testing the model. The bridges in the dataset are mostly chain subgraphs branching out of a connected component (see Section 5 for more discussion).
2022). For instance, two of the most challenging algorithmic
3.4 Model Selection is Hard with Nearly Perfect ID Performances
Generally, model selection in OOD settings is not as straightforward as in the ID setting. This is because the validation data is not identically distributed as the test data. This problem is accentuated even more in algorithmic reasoning tasks. When training a model algorithmic tasks of the CLRS benchmark, it usually fits the ID validation data almost perfectly in terms of prediction accuracy. This leaves harder model sclection question than common OOD settings, i.e., "How to pick the best model among all these perfect models?". These perfect-ID models behave very differently on OOD data. For example, despite all the architectures achieving 100% ID accuracy on the Articulation Points task (Table 9 in the Appendix), the OOD accuracies widely differ across different architectures, ranging from 69% 88%. This issuc exists even when comparing models from the same architecture but in different optimization steps. For example, for some tasks, the OOD accuracy keeps improving even after perfectly fitting the ID data. An extreme case can
6

---

Published in Transactions on Machine Learning Research (03/2023)
53 0.
09
05
1.0
Intepolation
(a) Model B to A
(b) Model C to A
(c) Model C to B
Figure 3: Model interpolation on the Matrix Chain Order task. We train three models (named as A, B, C) and pairwise interpolate their weights to obtain ID and OOD accuracies. Each plot shows the interpolation of a pair (e.g., when the cocfficient set to and 1 in (a), we use model and A respectively; when it is in the middle, we linearly interpolate weights from and A). While models achieve similar ID accuracy, their interpolations show very different OOD performances.
seen in Figure 2a for the Bridges algorithm. Here, the OOD accuracy keeps improving from around 30% above 90% after an almost perfect TD performance achieved.
Furthermore, OOD performances in some algorithms have high variance across models, and sometimes even negatively correlate with ID performances. Inspired by recent works mode-connectivity and model weight interpolation (Wortsman et al. 2022 Entezari et al. 2022), we interpolate between the weights of models to better understand the loss landscape of such tasks. We pick the Matrix Chain Order task which shows a high variance even when the initialization point of the model fixed. Here, despite all models attaining 99.5% ID accuracy, some of them have an OOD accuracy of around 60%, and some have an OOD accuracy of around 80%. Figure shows pairwise interpolation of three models trained on this task. According the figure, there are barriers when connecting two sets of weights. Quite counter-intuitively; the ID barrier between two models with larger OOD gap is the smallest (Figure 3b Moreover, there are two barriers for the ID performance, and one barrier for the OOD in Figure 3c Finally, when interpolating from model C to model A, the ID and OOD do not show any positive correlation and even negative correlation in the first half of the plot (bb.. These all support the fact that the ID validation performance is not suitable measure for model selection, and ID and OOD data clearly have different loss landscapes. See Figure in the Appendix for additional interpolation plots.
3.5 Disentangling Different OOD Generalization Behaviors
The CLRS benchmark (Velččkoić et al. 2021 generates the underlying graphs using an Erdös Rényi model with a fixed probability p. This means that the node degree distribution increases as the graph size increases. While prior works have worked on proving OOD generalization guarantees when the local structure of graphs stays the same (Ychudai et al. 2021), ncural algorithmic rcasoning is different from standard graph benchmarks. Here, when the graph size increases, higher-depth reasoning needed. As result, fixed-depth local structure of the graph is no longer sufficient for node to decide the label. To disentangle these two types of gencralization, we create three dataset configurations of the CLRS benchmark to better understand such generalization bottlenecks.
We consider only graph algorithms since it is not possible to control the message- saassaggppssingggg locality of sequence/sel algorithms. There are distinct graph algorithms in the benchmark. We remove the Articulation Points camplingeevannation
and Bridges algorithms since they require complicated sampling/ /evaluation strategies for preventing cheating solutions from succeeding. We create the following datasets:
7

---

Published in Transactions on Machine Learning Research (03/2023)
Table 2: Test scores of MPNN-G processor on controlled datasets of 9 graph algorithms, L.e, L-CLRS-Len, L-CLRS-Deg, and L-CLRS-Len-DEE
Accuracy Metric Method
Node Level
Graph Level CL.RS-Ten
CLRS-Len-
CL.RS-Ten
CLRS-Deg
CT.RS-Len-Deg
CT.RS-Deg
Bellman Ford
99.48: 0.07
99.57= 0.06
99.40=
0.09
84.93+ 2.24
87.53= 1.69
82.974: 2.11
Bis
100.001 0.00
99.92 L 0.04
100.00 0.00
100.00.1 0.00
97.77 1.23
100.001 0.00
Dag Shortest Paths
99.84 0.04
99.94= 0.00
99.81+ 0.02
95.10+ 1.18
98.17= 0.12
94.37+ 0.66
Dis
74.63+ 3.91
81.76+ 3.66
98.91+ 0.23
0.13+ 0.12
3.67+ 1.68
81.57+ 2.82
Floyd Warshall
63.841 1.07
64.51= 0.34
51,981 2,88
0,001 0.00
0.001 0.00
0,001 0,00
Mst. Kruskal
49.80+ 1.54
61.66+ 1.56
51.69+ 1.53
0.00+ 0.00
0.00+ 0.00
0.00+ 0.00
Mst. Prim
87.02:1 0.90
95.33 0.42
85.72:1 1.56
6.67 1.87
53.20 3.03
4.47 2.15
Strongly Connected Components
94.45= 0.39
94.18= 0.04
96.19 0.09
65.57 0.75
64.40= 0.96
75.63: 1.76
Topological Sort
94.30.1 0.27
93.76.L 0.01
98.56.1 0.09
54.12.1 0.78
52.02 0.25
80.97.L 0.67
Mean
84.82
87.85
86.92
45.17
50.75
57.77
L-CI.RS-Len: We control the degree distribution of nodes between training and testing to be the same via sampling random K-regular graphs. Only the size (i.e., number of nodes) of testing graphs is larger than those in training. This is an ideal setting for studying size generalization.
L-CLLR-Dee:: We control the number of nodes between training and testing to be the same. Only the degree distribution of nodes changes, which is achieved by changing the K value in K K-regular graphs. This is ideal for studying how the degree distribution shift affects the generalization.
L-CLRS-Len-Deg
We allow both the size and the degree distribution to be changed between training and testing, which is a setting closest to the original CL.SS. It is useful to study both size and degree generalization. Here, in the test set, we not only increase the number of nodes but also increase the K value of K-regular graphs.
The details of these datasets are summarized in Table 3 Note that the motivation behind choosing K-regular graphs that degree shift can be completely controlled and no shift in the variance of degroe. Morcover, dataset leakage is avoided as we generate more training graphs (í.e., graphs in the test dataset have zero probability of appearing in the training set). In addition to the CLRS's own metric (f.e., node-level metrics), we include graph-level metric that is stricter than the node-level onc. In particular, a graph is considered as correct if all of its nodes are classified correctly (in contrast to the node-level metric which measures the accuracy of the node classification). This way, we can better distinguish performances among models.
We observe that while some algorithms struggle more on size generalization (e.g., DFS), others struggle on degree generalization (e.g., MST algorithms, Floyd Warshall). This suggests that, even if we control all the distribution shifts caused by size generalization, distribution shift in degree is still challenging for some algorithms and vice versa. Moreover, the graph-level metric shows very poor performance in some tasks, despite a high node-level performance (e.g., Floyd Warshall, and MST algorithms). This shows that in tasks with low graph-level accuracies, all graphs contain challenging parts. Finally, lower graph-level and node-level accuracies of CLRS-Len-Deg compared to the other two datasets confirms that when two distribution shifts are combined, the prediction problem becomes more challenging.
4 Improving OOD Generalization of Neural Algorithmic Reasoning
In this section, we introduce our solutions to some of the above challenges that improve the performance of end-to-end (i.e., without hints) neural algorithmic reasoning. Since hints are disabled in our casc, we make two changes to our model. First, algorithms with the same input/oulput (e.g., Dijkstra and Bellman-Ford) only differ in the number of processing steps. Since we discard these intermediate steps, the number of steps becomes mcaningless and we use a number of steps independent of the underlying algorithm. Morcover, the number of tasks shrinks from 30 to 24 tasks (e.g., Dijkstra and Bellman- Ford become Shortest Path, Quick Quick/Insertion/MER Mergee/ Mewgeeerrreeeeeeeeeeeee Bubble/Heap Sort become Sort, elc.). In order to facilitate the comparison, we do
8

---

Published in Transactions on Machine Learning Research (03/2023)
Table 3: Summary dataset configurations used in this paper.
Lengths Train/ Srain/Val Val
Dataset Size
Dataset
Dataset Generation
Test
Train
Val/Test
CLRS Velickovvv
2021
16
61
1000
32
Erdös Rényi graphs with fixed
L-CLRS
16
64
100
32
Erdös Erdös-Rényi graphs with fixed p
L-CLRS-Len
16
32
100000
1000
K-Regular graphs with K =
L-CLRS-Deg
32
32
100000
1000
K-Regular graphs with K = 4 for train/val, and K = 8 for test K-Regular graphs with K 4 for train/ /val, and K 8 for test
L-CLRS-Len-Deg
16
32
100000
1000
not change the names of tasks and keep their original names from the CLRS benchmark. Second, use MPNN-G as the message-passingg processor.
4.1 Increase Dataset Size and Representativeness
First, we propose to increase the dataset size. The purpose of this change is to truly measure the extrapolation properties of cach model and avoid some in-distribution training issucs like overfitting. We change the CLRS dataset configuration and increase the amount of ID training samples from 1000 to 100K (and keep the ID validation and OOD test sets as they are). This way, it is possible to observe a much more diverse set of ID graphs. We note this strategy as a remedy to the low-data regime and not a solution. This strategy especially becomes problematic and even more data-hungry as the size of training graphs grows, and sampling diverse graphs becomes harder since the graph statistics become even more concentrated (e.g., as the size of the graph grows, the number of samples to generate disconnected graph increases). While this strategy is not strong solution to OOD generalization, it helps mitigate any side factors contributing to low benchmark numbers but not directly related to size generalization; hence, providing better test bed for testing size generalization. Table 3 summarizes the different datasets we use in this paper and their comparisons.
4.2 Improving Representation Distribution Shift
The position index of each node is vital part of the inputs, especially since several algorithms depend on the ordering of such positions. Here, we explore few possibilities of generalization to larger sizes. A suitable representation must be naturally extendable to any size of graph. For instance, one-hot encoding of indices is not generalizable as it contains a fixed imput length and the input dimension is not fixed across different sizes.
As baselines, we consider the default index encoding used in the CLRS benchmark (i.e., a scalar feature for each node i as (i-1) (i-1)/n where n is the number of nodes). We also add positional encoding used by Transformers /Vaswani et al. 2017)
bascline. We propose the following stratogy mitigation to the distribution shift of the scalar index:
Random Scalar Index. Although the Scalar Index representation is naturally extendable to any graph size and node orderings are preserved, the model might rely on spurious correlations between such numbers (e.g., the distribution shift due to moving to larger sizes makes generalization harder). For instance, the model might rely on the fact that consecutive indices always have a difference of 1/n where is the training datasot size, hence struggling to generalize as the size of graph grows and the difference between two consecutive indices becomes smaller. To mitigate the distribution shift, propose to randomly sample scalars from 1] and use its sorted sequence during training, and use the same Scalar Index for validation and testing as mentioned before. This way, the model observes variety of position embeddings and learns to better preserve the ordering of positions. In our experiments, we find that using random scalar makes training harder (e.g., convergence is slower). As a remedy, we use a mix of both random and deterministic scalar index in a mini-batch as a training stratogy to case the training and achieve a faster convergence (i.e., each mini-batch with the probability of 0.5 for each graph, we replace the position index of the whole graph with random scalar index).
9

---

Published in Transactions on Machine Learning Research (03/2023)
Table 4: Performance of different positional encoding strategies on positions-order aware algorithms using
MPNN-G processor on L-CLRS dataset.
Method
Scalar
Random Scalar
Position Enc.
Dfs
25.36 0.17
31.71# 1.13
11.90 0.89
Find Maximum Subarray Kadane
26.60+ 5.95
47.85 5.32
12.97 3.96
Dag Shortest Paths
99.82# 0.06
99.79 0.02
31.45= 2.69
Naive String Matcher
8.24 2.33
7.67 3.94
1.32+ 0.35
Matrix Chain Order
80.69 1.33
92.07 0.11
30.96 3.16
Topological Sort
82.62:: 0.63
84.17# 1.67
33.28 0.84
Bis
100.00=: 0.00
100.00 0.00
49.40 4.83
Mean
60.47
66.18
24.47
In Appendix A.4
we also propose a more invariant (to shift and scale) way representation, however, due to the superiority of the Random Scalar Index, we choose Random Scalar for all remaining experiments.
4.3 An Attention-Bant Based Processor Competitive with MPNN-G
Inspired by recent works on higher-order message passing beyond node-level message passing, we explore this approach as a processor (Bodnar et al. 2021b Kim et al. 2022 Morris et al., 2019 Morris & Mutzel 2019)) We treat each edge of the input graph a node, construct new graph (I.e., line graph in graph theory) and run GNN top of that. Namely, the set of nodes, edges, and features ,' X will be as follows:
V {u/ (Vi, U12) Ui v/s EV,I iissisi m]
E' {E/ (i2) Eigy Gig share common node 11 S m'}
X' {xr [ =I., They" xT, 1T : v/2 E E7,,,,,15
m).
In other words, nodes of the new graph are the edges of the original graph, edges are between every two original edges that share a node, and node features are concatenations of cach endpoint of cach edge. We use transformer with edge masks of E' the GNN. Such GNN archilecture has similar computation mechanism 2- Weeisfeller-Lhmaarl (2WL) test, and hence we call this processor "2WL". We, however, note that while the processors are limited by the expressivity of K- WL test (Morris & Mutzel 2019), our model as whole does not have such limitation since in our setting node features are equipped with a unique identifier (Fereydounian et al. (022). The result of using this processor is present in Table 5 As the results suggest, this processor shows competitive results with MPNN-G, and outperforms MPNN-CC in some algorithms, while under-pont under-perming MPNN-G in others. For instance, the 2WL processor shows 20% higher performance on the String Matching problem, while the MPNN-G shows 20% higher performance on the Articulation Points finding algorithm.
4.4 Hybrid Processor
As saw above, different processors exhibit different generalization behaviors. Here, show hybrid processor brings performance gains over individual ones. To this end, we take MPNN-G and 2WL processors as they show competitive results, and are quite complementary in nature (e.g., max aggregation vs. attention, edge-wise message passing vs. node-wise message- message-passing. We consider the following processor combination stratogics:
Average: At each individual step of processing, two processors process the hidden representation, and the representation of each node/edge /edge is computed using an average of two processors. Namely,
(P.)
(Pa) hot
(P.)
he: (Pa)
(P)
and (PP)
2
where P1, P2, P are two processors and the hybrid hidden representations.
10

---

Published in Transactions on Machine Learning Research (03/2023)
Table 5: Mean test scores different processors averaged over all 24 distinct algorithms on the L-CLRS dataset (performances of individual algorithms are averaged over three random sceds). The two rows correspond using the scalar index and the random scalar index for input representation respectively. The hybrid models are a combination of MPNN-G and 2WL with the same parameter budget individual processors (Table 13
and 14 contain the complete test scores of individual algorithms).
Method
MPNN-G
2WL
Hybrid-
Hybrid-Sigmokd
Scalar Index
69.23
67.96
70.92
71.98
Random Scalar Index
71.11
71.52
74.33
74.31
Table 6: Summary of sequentially applying the improvements proposed in this paper. Test scores are averaged over all 24 distinct algorithms.
Method
Mean Test Score
Improvement (%)
Baseline
60.93
Increase ID Dataset Size
69.23
8.30
Improve Input Representation Shift
71.11
1.88
Add Hybrid Processor
74.33
3.22
Similar to average, but sigmoid is applied to the previous hidden dimension to assign weighted combination of processor hidden representation values. That is,
Sigmoid:
h (n ((P1) (1 (n(p"))) (P2) ((P) ( ((P.)) [1 (h(Bn) W) (Px),
where W is d x weight matrix.
This processor trained from scratch. Table 5 shows the results of experiments with these processors. As the results suggest, a hybrid processor does bring an average accuracy gain on performance. Furthermore, to show that the boost in the results indeed originates from the complementariness of processors, also report the results of hybrid model of two processors of the same lype (e.g., hybrid of two separate 2WL processors) in Table 12 in the Appendix. Next, we combine the proposed random scalar index representation and the 2WL processor in Section 4.3 and report the average score on the OOD testing dataset in the bottom row of Table 5 The hybrid models already outperform individual processors, and by adding the proposed input representation change, all processors gain 2% 3% improvement on the average accuracy. The hybrid processors achieve an average score of above 74% on the benchmark. A unified summary table of improvements proposed in our work shown in Table
5 Discussion on OOD Performances
So far, have made series of improvements to the models and training data and improved the OOD accuracy of several tasks. Indeed, have even achieved OOD accuracy above 98% some tasks. Here, we ask "Is a task solved given our model achieves high score on the benchmark for that particular task?". As discussed in Section 3.3 the test. dataset might be biased and all graphs in the test. set might have common property and the model might take advantage of that property to output solutions. Following this issue, we pick the Bridges task on which the hybrid of MPNN-G and 2WL achieves high OOD performance as shown in Table [4] As we show in Figure 4a the bridges are all chain subgraphs branching out of connected component.
11

---

Published in Transactions on Machine Learning Research (03/2023)
(a) Erdös-Rényí dataset
(b) Two- Ivv-Coomunity dataset
Figure 4: Illustration of two datasets generated for measuring the performance of model on Bridges task. (a) The dataset generated by the CLRS benchmark. (b) We generate two-community dataset for stricter mcasurement of the Bridges task. The dashed edge is present in one graph and absent in the other graph of the pair. Red edges show the target bridges. Green ovals show connected components. A model with 98% OOD F1 score on the dataset (a) fails to detect the bridge wetw the two communities of the dataset (b).
To better evaluate models in this task, we create pairs of two-community graphs. Each pair of the community graph has two Erdös-Rad Rényi generated and inter-comnected subgraphs. Then, we connect the two communities using a randomly chosen edge. We also connect the two communities of the second graph in the pair using another random edge (sce Figure 4bj. This way, the first edge is a bridge in one graph and not bridge in the second graph due to the existence of another edge connecting the communities. Ideally, a model capable of reasoning on bridges task must be able to identify the existence of the mentioned bridge in one graph, and the absence the bridge in the sccond graph of the pair. Although there might be more bridges among the pairs of graphs (i.e., inside individual communities), we do not consider them in our metrie since most of them might be trivial. Therefore, random guess gives 25% accuracy in such evaluation. We evaluate the model on 1000 randomly generated pairs of graphs, we find out that in only seven pairs of graphs, the model detects the existence of the mentioned bridge in both graphs correctly. This 0.70% accuracy is much lower than the 25% chance accuracy. This suggests that despite the remarkable improvement on the benchmark (originally from 72% to 98%), there is still a lot of room for improvement, and OOD generalization in the Bridges task is not even close to being solved. Therefore, as the models get stronger, test datasets must also be refined to not only better evaluate the reasoning capabilities of model, but also prevent heuristies from achieving high scores.
6 Related Works
In addition to the related works discussed in Section 3.1 there are some lines of research close to this area that explain below.
Neural Algorithm Execution. A recent line of work has focused on the execution of algorithmic tasks
using neural networks (De'etang et al.) 2022 Joshi et al. 2022 Abbe et al. 2022). Some works consider
NP-Hard problems over graphs and propose problem-speeifie solutions (Karalias & Loukas 2020 Bresson &
Laurent 2021 , however, perfect extrapolation is infeasible for such problems (Yehuda et al.) 2020). Some
works consider executing algorithmic tasks, however, they are either limited to simple arithmetic tasks Kaiser
& SSutskever 2016) or are general purpose but hard-to-train and struggle to even fit in-distribution data for
complex tasks (Graves et al. 2014 Yan et al. (2020) proposed general neural executor to mimic elementary subroutines of any algorithm, but requires low-level design and assembly of subroutine engines for each specific task. More recent works have proposed gencral-purpose GNN pipelines for executing (graph) algorithms [Veličković et al.) 2020b Several benchmarks have been proposed to measure the reasoning capabilit of neural networks Zhang et al.) 2022 2021 Veličković et al., 2021). Perhaps the CLRS benchmark (Veličkovid 2021) the most comprehensive benchmark to date, as contains 30 highly complex and challenging algorithmic reasoning tasks. In a concurrent work, Tbarz al. (2022) proposed series of improvements for improving OOD generalization when hints used.
ct al.
12

---

Published in Transactions on Machine Learning Research (03/2023)
Expressivity of GNNS. Previous works have studied the expressiveness of GNNs from WL-test point of view (Weisfeiler & Leman 1968 Xu et al. 2019 Morris et al. 2019 2021 These works show negative results by proving message passing GNNs are unable to distinguish two graphs if the WL test fails in distinguishing them. There cxists a considcrable body of literature for lifting such a limitation and improving the expressivity
of GNNs by proposing novel architectures and providing analysis (Qian et al. 2022 Bevilacqua el al. 2022 Bodnar et al.) 2021bb @ Maron et al., 2019). Some prior works have also addressed the limitations of GNNs by investigating their power in solving algorithmic tasks such as substructure counting in graphs (Bouritsas et al. 2022 Chen et al. 2020). All these limitations on the expressivity of GNNs, however, can be resolved by augmenting node features (Dasoulas et al.) 2020: Fereydounian et al. 2022). at the cost of losing guaranteed equivariance. Since all tasks in our setting contain unique identifiers, none of the above limitations are applicable to our setting. This can also be verified by looking al validation scores. Here, the challenge is to extrapolate to larger graphs, rather than the possibility of learning to solve an in-distribution task.
Reasoning Capabilities of Language Modcls. With the success of Large Language Models (LLMs) in natural language understanding (asks, a series of recent studies have focused on exlending the reasoning capability of LLMs even further. The core of these models is a Transformer architecture, which makes such tasks in nature very close to neural algorithmic reasoning tasks. Recent works improve the performance of
LLMs using fine-tuning, chain-of-thought prompting (Kojima et al. 2022 Wei et al., 2022b Amil et al. 2022 sampling multiple solutions (Lewkowycz et al.) 2022 Wang et al. 2022 and scaling Weei et al. 2022a). The
most relevant idea to our setting is chain-of thought prompting, which forces the model to do multi-step reasoning and is close in nature to the purpose of hints, but, in contrast to LLMs, hints do not bring any noticeable accuracy gain in neural algorithmic reasoning. Scaling the models might also be relevant, however, in our sctting, the depth of the transformer must also increase with the size of the diameter of training graphs, which makes training large models on large graphs highly challenging,
7 Conclusion
In this work, we investigate the OOD generalization of neural algorithmic rcasoning tasks from end- to-end training perspective. We identify and analyze several challenges of OOD generalization under the current framework. Then, we propose solutions to some of these challenges by making the dataset larger, designing fixes to input representation distribution shift, and proposing an attention-based processor. These improvements, lead to a final 74.33% accuracy averaged over all algorithms. Finally, we shed light on the limitation of our model in executing one of the benchmark tasks and conclude that despite our model gains a high OOD test accuracy, there still exists much room for improvement. Our analysis opens up several interesting directions for future work. Designing better hints with guaranteed invariance properties potentially facilitate the step-by-step execution of algorithms and help improve OOD generalization. Sampling training graphs from diverse set of distributions could help boost the generalization. Improving the model selection strategy and finding an alternative to the validation set could help pick the best-performing models. Finally, it would be interesting to develop a meta-learning framework for inductive learning across graph sizes, in order for the model to learn the invariance properties of an algorithm across different sizes and generalize to larger graphs.
Acknowledgments
This work was funded, in part, by NSERC DG Grants (No. RGPIN-2022-046636 and No. RGPIN-2021-03677)) Google Cloud credits, and Oracle Cloud credits. Resources used in preparing this research were provided, in part, by Google, Advanced Research Computing at the University of British Columbia, the Oracle for Research program, and the Digital Research Alliance of Canada (alliancecan.cal
References
Emmanuel Abbe, Samy Bengio, Elisabetta Cornacchia, Jon M. Kleinberg, Aryo Lotfi, Maithra Raghu, and Chiyuan Zhang. Learning to reason with neural networks: Generalization, unseen data and boolean measures. ArXio, abs/2205.13647, 2022.
13

---

Published in Transactions on Machine Learning Research (03/2023)
Maria Chiara Angelini and Federico Ricci-Tersenght Cracking muts with sledgehammer: when modern graph neural networks do worse than classical greedy algorithms. ArXiv, abs/2206. 13211, 2022.
Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowyez, Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. ArXiv, abs/2207.04901 2022.
Martín Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. ArXio, abs/1197,02899,, 02893, 2019.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchelti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint orXiv:1806. 01261, 2018.
Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating propagating gradients through stochastic neurons for conditional computation. ArXiv, abs/1308.3432, 2013.
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In ICML, 2021.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramanian Srinivasan, Chen Cai, G. Balamuru- gan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. ArXie, abs/2110.02910, 2022.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Lio', Guido Montúfar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: Cw networks. In NewrIPS, 2021a.
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Lio', and Michael M. Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. ArXis, abs/2103.03222, 2021b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE transactions pattern analysis and machine intelligence, PP, 2022.
Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. ArXio, abs/2103.03012, 2021.
Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant reprosentations for out-of-distribution generalization on graphs. In Advances in Neural Information Processing Systems, 2022.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? ArXie, 00s/2002.04005,, 2020.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In IJCAI, 2020.
Gr'egoire Del'etang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Kevin Wenliang, Elliot Catt, Marcus Hutter, Shane Logg, and Pedro A. Ortega. Neural networks and the chomsky hierarchy. ArXio, aabs/2207.02099 2022.
Rahim Entezari, Hanic Sedghi, Olga Saukh, and Behnam Neyshabur. The role of permutation invariance in linear mode connectivity of neural networks. ArXiv, abs/2110.06296, 2022.
Mohammad Fereydounian, Hamed Hassani, and Amin Karbasi. What functions can graph neural networks generate? 2022.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. ArXiv, abs/1704.01212, 2017.
14

---

Published in Transactions on Machine Learning Research (03/2023)
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. ArXiu, abs/1410.5400 2014.
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. ArXio, abs/ Nlbs/2007.014333 2021.
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mchdi Abbana Bennani, R. Csordás, Andrew Dudzik, Matko Bovsnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličkovié. A generalist neural algorithmic learner. ArXiv, abs/2209. 11142, 2022.
Eric Jang, Shixiang Shane Gu, and Ben Poolc. Categorical reparamctcrization with gumbel-softmax. ArXio, abs/1611.0114,, 2017.
Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints An Int. J., 27:70-90 98, 2022.
Lukasz Kaiser and Tyy Sutskever. Neural gpus learn algorithms. arxi Learning, 2016.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combina- torial optimization on graphs. ArXiv, abs/2006.10643, 2020.
Jinwoo Kim, Tien Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontac Lee, Honglak Lee, and Scunghoon Hong. Pure transformers are powerful graph learners. ArXiv, hes/2207.002500 2022.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yulaka Matsuo, and Yusuke wwssaw.. Large language models are zero-shot reasoners. ArXiv, abs//220..1130 2022.
Aitor Lewkowycz, Anders Johan Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Venkatesh Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with 2022.
language models. ArXie,
Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals. Strong generalization and efficiency in neural programs. ArXau, abs abs/2007.03629) 2020.
Haggai Maron, Heli Ham-H Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks.
ArXio, hbss/1905.11133 2019.
Sohir Maskey, Ron Levie, Yunscok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. 2022.
John Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution genoralization. ArXiv, abs/ abs/2107.04669, 2021.
Christopher Morris and Petra Mutzel. Towards a practical k-dimensional weisfeiler-leman algorithm. ArXio, abs/1904.01143,, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, (310))44602 4609, Jul. 2019, doi: 10.1609/aaae http://aa...331.333..33333 33060... URL https://ojs aaai, org/ wtogg/iddx.... www.k/.ppppaaa AAAI/ att/aaarcieeeeeeeeeeeeeeeeeeeeee /384
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt. Weisfeiler and leman machine learning: The story so far. ArXie, abs/2112 abs/2111.09999, 2021.
Yaniv Ovadia, Emily Fortig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshma Dillon, Balaji Lakshminarayanan, and Jasper Snock. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
15

---

Published in Transactions on Machine Learning Research (03/2023)
Chen Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Ordered subgraph aggregation networks. Ariiu, abs/ 2os/2206.11168,, 2022.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR, 2020.
Hao Tang, Zhiao Huang, Jia- Yuan Gu, Bao-Liang Lu, and Hao Su. Towards scale-invariant graph-related problem solving by iterative homogeneous graph neural networks. ArXit, abs/2010.13547, 2020.
Aäron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learning. In NIPS, 2017.
Dusan Varis and Ondrej Bojar. Sequence length is a domain: Length-based overfitting in transformer models. In EMNLP, 2021.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Usækoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. ArXiv, abs/ abs/1706.03362 2017.
Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio', and Yoshua Bengio. Graph attention networks. ArXiu, abs/1710.1090: 2018.
Petar Veličković, Lars Buesing, Matthew Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. ArXiv, abs/2006.06322 06380, 2020a.
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. ArXiv, abs/1910.105555 2020b.
Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning benchmark. 2021.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. ArXiv, abs/2203.1101 11171, 2022.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosmn,, Denny Zhou, Donald Metzler, Ed Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. ArXiv, abs/ abss/220600662) 2022a.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. ArXiv, abs Abs/2220.11903 2022b.
B. Weisfeiler and A. Leman. The reduction of a graph to canonical form and the algebra which appears therein. Nauchno- Technicheskaya Informatsia, 2(9):12-16, 1968.
Florian Wenzel, Andrea Dittadi, Peter Vincent Gehler, Carl-Johann Simon-Gabriel, Max Horn, Dominik Zietlow, David Kernert, Chris Russell, Thomas Brox, Bernt Schiele, Bernhard Schölkopf, and Francesco Locatello. Assaying out-of-distribution generalization in transfer learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. ottp:etteeeoommmmmm5777/
URL
Mitchell Wortsman, Gabriel Iharco,, Samir Yitxhak Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes, Ari S. Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, and Ludwig Schmidt. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. ArXiv, abs//203.ams /2//222202222222 2022.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks?
ArXée, abs/1810.00826, 2019.
Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning to execute subroutines. ArXiv, abs/2006.08084, 2020.
16

---

Published in Transactions on Machine Learning Research (03/2023)
Gal Yehuda, Moshe Gabel, and Assaf Schuster. It's not what machines can learn, it's what we cannot teach. In TCML, 2020.
Gilad Yehudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In ICML, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alex Smola, Deep sets. In NIPS, 2017.
Chiyuan Zhang, Maithra Raghu, Jon M. Kleinberg, and Samy Bengio. Pointer value retrieval: A new benchmark for undorstanding the limits neural network generalization. ArXiu, abs/2107.12580, 2021.
Hongyi Zhang, Moustapha Cissé, Yann Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. ArXie, abs/ hbss/170.00941,, 2018
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasckar, and Tal Wagner. Unveiling transformers with lego: a synthetic reasoning task. ArXiv, (bss/220600430)) 2022.
Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. Ood link prediction generalization capabilities of message- passing gnns in larger test graphs. ArXiu, abs/2205.15117 2022.
A Appendix
A.1 Experiment Details
For Table we take the (with-hint hint versions) numbers from Veličković et al. (2021) and run the no-hint version of the table with the same configuration except for disabling hints.
For the rest of the experiments, we use a batch size of 32 for message-passing processors and 16 for high-order processors, gradient clipping to a norm 1.0, a learning rate of 0.0001, 20 000 optimization steps, and cosine annealing scheduler. Moreover, as the number of processing steps is meaningless in the no-hint version, we set this number to 32 (f.e. 32 recurrent steps of message passing). Unless otherwise specified, experiments are run using the MPNN-G processor on the I-CLRS dataset. Finally, as the ID accuracy and OOD accuracy are not highly correlated, we do not do any early-stopping and among the models with the highest validation accuracy, keep the last model.
The number of distinct algorithms shrinks from 30 to 24 when doing such changes. In particular, the following algorithms merge together:
Sorting: All variants of sorting. That is, Quick sort, Insertion sort, Bubble sort, Heap sort are merged together. We Keep the "Quick sort" name to represent sorting and refrain from creating new names.
Single source shortest path: Dijkstra and Bellman- Ford are merged together. We keep the "Bellman Ford" name to represent the shortest path.
String Matching: Naive String Matcher and KMP algorithms are merged together as they contain the same input/output. We keep the "Naive String Matcher" name to represent the string matching task.
Convex Hull computation: Jarvis March and Graham Scan are combined and represented as "Graham Scan".
Note that some other algorithms might also seem have the same computation (e.g., MST Prim and MST Kruskal both compute minimum spanning tree), however, they are implemented differently in the CLRS benchmark and keep them different as well.
17

---

Published in Transactions on Machine Learning Research (03/2023)
A.2 Leveraging Intermediate Steps of Algorithms
The CLRS benchmark contains intermediate steps of algorithms (i.e., hints) as optional supervision in addition to the supervision of the final output of the algorithm. Namely, for applying an algorithm to a particular graph, two additional supervision signals are provided: (1) number T' representing the number of recurrent processing steps to perform (í.e., the processor is called T times), (2) depending on the algorithm, several hints are provided. Fach hint is a T-dimensional tensor, representing the intermediate output of an algorithm for each intermediate step. For instance, for the Dijkstra algorithm, one hint is the computed distance for each node at each individual step (i.e., Xhint R where Xnint, represents the distance of node to the source node at step t). Hints also follow the encode encode-process- prrocess-dcodde framework and have separate encoders and decoders (while sharing the same processor with the inputs and outputs). When leveraging hints, Eq- | should be modified to the following formula:
H(++1) = GNN([ H Zippy
(t) hint,
], A),
(2)
where Lint, is the encoded hints at step & (1 S ( L T). The hints for the successor step are also decoded and evaluated in the final loss function along with the final output of the algorithm.
Table 8 contains the full OOD test accuracies of the algorithms when using hints and when disabling them. As shown by the results, enabling hints mostly degrade the final OOD accuracy. While (Veličković et al., 2021) employed a complex model selection on the validation numbers for the with-hint version of processors, running a no-hint version of the simplest form of a processor and no hyperparameter tuning yields superior OOD results.
A.3 Encode- Ponode-Process-ee Decode Framework
Here, we explain how three algorithms are put into a simplified encode- prodee-process-eeoode framework.
Sorting. Given a sequence 41, ......,.. an of scalars, the task is to find the successor of each clement when the sequence is sorted. So, the input is again a two-dimensional node feature matrix Xy E Raxx where the first dimension denotes the index of each element and the second dimension is the value a of that dimension. Here, do not have underlying graph and one could consider fully-connected graph where all nodes are connected to each other. The encoding, processing, and decoding steps are similar to the case of BFS since the final output is again pointer prediction for each node.
Minimum Spanning Tree (MST) Prim. Given a weighted graph, the goal is to find the minimum spanning tree of the imput graph. A spanning tree is a subset of edges with the lowest sum of weights, which preserve the connectivity of the graph. The input to this task a two-dimensional node feature matrix Xy gmx2 where the first dimension is the node index, and the second dimension indicated the starting node of the MST Prim algorithm. Additionally, the input contains edges features/weightt, Xx gnxax1, Again, the procedure is similar to that of BFS, but with the following differences: during the encoding part, we also need an edge encoder (c.g., WE E Ri to encode edge features and incorporate them in the processing step. Finally, the decoder needs to predict a binary output for each edge (ú.e., whether the edge is in MST or not). So, for each edge eÚ with two endpoint nodes i, respectively, we directly apply a sigmoid function the output of the decoder aij; and compute the binary cross entropy loss with the ground truth edge label.
adjacency matrix A R= and
A.4 Alternative Representation for Input Index Representation Shift
The advantage of the Random Scalar Index is that it is a simple exlension of the position index into node embeddings. However, it requires a large number of training steps for the neural network to learn the ordering of numbers the range [0, 1). Idcally, representation mothod for ordering of nodes must be invariant under shifting and scaling of the index (i.e., if we shift the index of nodes by some constant factor, the function must not change).
18

---

Published in Transactions on Machine Learning Research (03/2023)
Table 7: Performance of different positional encoding strategies on positions-order aware algorithms for
MPNN-FC on L-CLRS dataset.
Method
Scalar
Random Scalar
Edge Pos.
Dfs
15.07# 0.92
25.29= 1.25
28.19 1.20
Find Maximum Subarray Kadane
23.81 2.12
48.99= 2.78
46.27 5.29
Dag Shortest Paths
99.67 0.12
99.72= 0.06
99.71# 0.04
Naive String Matcher
11.51 4.26
7.13+ 3.35
6.484 3.43
Matrix Chain Order
65.19 3.05
91.50= 0.59
80.92 1.71
Topological Sort
68.77 2.61
70.06= 0.53
67.25 0.90
Bfs
99.90 0.08
100.00 0.00
99.82 0.10
Mean
54.85
63.24
61.23
Edge Position. A more natural alternative way of enforcing such an embedding is to encode orderings edge features [Li et al. 2020). Namely, we create edge feature from node vs node vy as follows:
pos = [ Vi,j E (1,2.....,
This way, the ordering of nodes can be determined by performing topological sort using two steps of message passing a fully connected graph. The advanlage of using such method is that nodes do not undergo any distribution shift as the graph grows; hence any subgraph of the larger graph stays in distribution. Moreover, the method is invariant to any shift or scaling of indices j. On the other hand, using this method roquires a processor with global message passing steps and requires an implicit extrapolation of the Topological Sort. itself (which is itself challenging, according the Topological Sort task in the benchmark).
In order to keep the exprossiveness of the models and preserve the uniqueness of positions cach node, we append vector of random features to inpul features of each node for all representation strategies (Kim et al. 2022). Since this method requires a fully-connected MPNN, we run this method on the MPNN-FC processor and report the results in Table 7 The results show that this method is indeed superior to Scalar Index, although it is outperformed by Random Scalar by a narrow margin.
A.5 Additional Approaches that Failed
Furthermore, we also tried the following ideas (mostly on the DFS a algorithm, and mostly towards making hints work better than no-hints), however, they seem to not work:
One key factor in failure in OOD generalization is large number of roll-outs mostly present in sequential algorithms). One scenario where hints might come be useful is to consider Markovian assumption algorithm is independent of previous steps given its previous state. This then allows for step-wise training and makes training casier and less memory/compinn hungry. However, this strategy (on algorithms that satisfy markovian property) did not bring any performance gain over non-markovian assumption.
Markovian Assumption hints:
steps of the algorithm, meaning that each step of the
Choosing a subset of hints: Each algorithm might contain up to 22 different hints with different types. However, not all of them have a positive effect on a GNN for a better prediction of output and might distract the GNN more than they can help. We tried using only a subset of such hints to see any boost output happens or not. For the DFS algorithm, we observed that the fewer hints we use, the higher the accuracy becomes, however, it never surpasses the no-hint version.
Using hints only as masks: Since an algorithm can contain several hints and not all of them are useful to the GNN, we hypothesizod that perhaps a GNN should have fewer restrictions. We used the change in hints again it did not bring any performance gain over the no-h counterpart and the GNN (on the DFS
mask to supervise the GNN for a sparser hidden-ropresentation update. However,
19

---

Published in Transactions on Machine Learning Research (03/2023)
Table 8: Full test results of Table
Method
MPNN-FC
PGN
GAT
Hints
No
No
No
Articulation Points
50.91= 2.18
30.36+ 3.02
49.53+
2.09
47.85+
2.59
37.76= 1.62
49.24 1.30
Activity Sclector
80.66_ 3.16
91.49.1
1.29
66.80.1 1.62
64.591
1.26
73.23 1.37
66.1411 0.63
Bellman Ford
92.01= 0.28
90.141 1.17
92.99.1 0.34
91.591
1.99
87.91 1.19
78.12.1
Bis
99.80 0.05
99.531 0.20
99.63.1 0.29
99.791
0.20
99.04 0.21
99.141 0.68
Binary Search
36.83- 0.26
7.06+ 6.87
76.95+ 0.13
29.13+
19.12
23.50- 3.12
3.58+ 0.78
Bridges
72.69 4.78
30.36+ 0.73
51.42+ 7.82
32.90+ 0.99
25.64- 6.60
31.52+ 0.49
Bubble Sort
5.27= 0.60
50.13: 3.33
6.014 1.95
54.561 4.23
9.91 1.77
57.284 1.55
Dag Shortest Paths
96.24= 0.56
97.23: 0.17
96.944 0.16
97.464 0.35
81.14= 1.37
80.60
Dis
6.54+ 0.51
15.27+ 5.29
8.71 0.24
22.644::00 3.12
11.78 2.04
11.13t 1.31
Dijkstra
91.50= 0.50
93.51 0.46
83.45-t: 1.75
93.80+ 0.22
58.01= 0.79
83.27 0.17
Find Maximum Subarray Kadane
20.30= 0.49
21.65# 0.58
65.23 2.56
16.45+ 0.31
24.43= 0.43
14.88# 0.52
Floyd Warshall
26.74= 1.77
39.47# 4.43
28.76 0.51
35.19 1.20
16.66= 3.14
14.78= 3.85
Graham Scan
91.04= 0.31
96.271 0.27
56.871 1.61
57.05 0.29
77.80 2.70
57.62.1 0.33
Heapsort
10.94 0.84
63.72.1 6.41
5.2711 0.18
55.181 2.05
10.35 1.83
59.55.1 1.64
Insertion Sort
19.81= 2.08
38.41+ 18.19
44.37 2.43
68.77+ 2.56
29.52- 1.87
40.93+ 18.49
Jarvis March
34.86+: 12.39
95.46+ 1.01
49.19+ 1.07
56.64+: 0.55
51.51 10.25
57.63+ 0.33
Kmp Matcher
2.49+ 0.86
9.08+ 2.39
2.00+ 0.12
2.18+ 0.53
3.03+ 0.36
2.28+ 0.27
Length
53.23= 0.36
56.931 2.87
56.821 0.21
60.274 0.35
57.88= 1.02
59.70:1 0.68
Matrix Chain Order
79.84= 1.40
78.13: 6.56
83.91 0.49
82.011 0.59
78.19= 3.31
75.13 5.57
Minimum
85.34- 0.88
99.53+ 0.06
87.71+ 0.52
98.01+ 1.13
84.20 2.95
93.52+ 4.88
Mst. Kruskal
70.97 1.50
73.22+ 0.39
66.96 1.36
71.25+ 1.48
65.72 0.99
71.57+ 2.81
Mst Prim
69.08= 7.56
74.63+ 3.19
63.33 0.98
73.164 1.08
38.20= 4.34
45.46: 4.03
Naive String Matcher
3.92+ 0.30
4.43+ 0.84
2.08: 0.20
1.942 0.27
3.01 1.20
1.30+ 0.20
Optimal Bst
62.23 0.44
56.02.1: 13.13
71.011 1.82
30.25
30.03
65.49 1.75
30.42.1 2.85
Quickselect
1.431 0.69
8.501 3.29
3.6611 0.42
9.10 1.07
4.3611 0.95
8.691 0.99
Quicksort
11.30= 0.10
58.30# 4.20
6.17+ 0.15
63.874 3.06
7.60= 0.98
59.29+ 0.92
Segments Intersect
93.44= 0.10
93.94 0.29
77.51 0.75
77.67+ 0.92
90.41= 0.04
76.16 0.73
Strongly Connected Components
24.37= 4.88
53.65+ 3.52
20.80- 0.64
57.65+ 3.95
12.70= 3.12
39.86+ 2.19
Task Scheduling
84.11= 0.32
82.8611 0.32
84.8011 0.91
81.881 0.11
84.60= 2.09
81.9311 0.14
Topological Sort
52.60 6.24
72.03 0.74
60.45:1 2.69
78.761 2.69
27.03 6.92
35.3011 19.58
Mean
61.0240.60
60.04:10.93
52.3110.35
57.0241.22
44.69-20.58
49.53:10.97
Wins
8/30
22/30
10/30
20/30
14/30
16/30
Validation Score Mean
96.63
93.83
89.47
83.79
95.66
78.83
algorithm) violated the mask quite often (in favor of always updating hidden representations). Even increasing the mask loss to prevent such violations, reduces learning accuracy.
Caaretizze/Qunllii hidden representations: Due to the long roll-out of many algorithms, small errors might accumulate throughout the processing steps and lead to wrong outputs. We tried quantization techniques such as Straight Through (Bengio et al. 2013), Gumbel-Softmax (Jang et al. 2017), Vector Quantization (van den Oord et al. 2017 on the hidden representation of each processing step. However, training deep quantized networks in an end-to-end fashion hurts the in-distribution training accuracy and even in cases where it did not, OOD accuracy was no better than the continuous counterpart. Even when using hints and trying Markovian assumption, quantization did not offer any accuracy gain.
20

---

Published in Transactions on Machine Learning Research (03/2023)
Table 9: Validation scores of Table
Method
MPNN-G
2WL
Average Hybrid
Sigmoid Hybrid
Articulation Points
100.00 0.00
100.00:: 0.00
100.00 0.00
100.00 0.00
Activity Selector
99.491 0.18
99.4911 0.48
99.231 0.31
99.101: 0.18
Bellman Ford
100.00= 0.00
100.00 0.00
100.00 0.00
100.00= 0.00
Bis
100.00 0.00
100.00: 0.00
100.00 0.00
100.00 0.00
Binary Search
99.101 0.08
99.41 0.11
99.451 0.15
99.091 0.22
Bridges
99.081 0.08
100.00 0.00
100.00 0.00
100.00= 0.00
Dag Shortest Paths
100.00 0.00
99.80 0.28
100.00 0.00
100.00 0.00
Dfs
99.93# 0.09
99.67= 0.18
99.22# 0.55
99.80 0.16
Find Maximum Subarray Kadane
97.51# 0.21
97.46= 0.67
97.46# 0.18
97.48 0.05
Floyd Warshall
88.77 0.90
87.37= 0.59
88.46+ 0.63
87.46+ 0.42
Graham Scan
100.00= 0.00
100.00 0.00
100.00 0.00
100.00= 0.00
Les Length
75.00 0.35
100.00 0.00
99.981 0.02
100.00 0.00
Matrix Chain Order
99.52+ 0.03
99.33 0.06
99.49 0.12
99.45 0.10
Minimum
99.97 0.02
99.97 0.05
99.98 0.02
99.97 0.05
Mst. Kruskal
92.90+ 0.08
99.19 0.33
99.77 0.17
99.88+ 0.17
Mst Prim
99.35 0.18
99.35= 0.09
99.61 0.16
98.96 0.18
Naive String Matcher
80.89 14.72
78.45 10.80
83.15# 4.53
92.01 4.73
Optimal Bst
96.23+ 0.13
95.77+ 0.17
96.30+ 0.08
95.71 0.51
Quicksclect
89.19 5.67
99.82 0.02
99.80 0.07
99.67 0.13
Quicksort
100.00 0.00
100.00 0.00
100.00 0.00
100.00 0.00
Segments Intersect
98.49 0.10
96.42 0.53
97.23 0.47
96.86 0.67
Strongly Connected Components
100.00 0.00
99.28= 0.49
100.00 0.00
100.00 0.00
Task Scheduling
99.50 0.07
99.90 0.14
99.95 0.07
99.85 0.12
Topological Sort
100.00 0.00
100.00+ 0.00
100.00 0.00
99.97 0.05
Mean
96.46
97.95
98.30
98.55
Table 10: Validation scores of Table 2
Method
CL.RS-Ten-Deg
CLRS--ee
CLRSS-eg
Bellman Ford
99.81 0.02
99.82+ 0.02
99.82+ 0.02
Bis
100.00 0.00
100.004: 0.00
100.00 0.00
Dag Shortest Paths
99.981 0.01
99.98 0.01
99.98 0.01
Dfs
100.00 0.00
100.004: 0.00
99.631 0.06
Floyd Warshall
87.03+ 0.52
86.58 0.40
78.40 0.98
Mst. Kruskal
62.46-t 1.09
62.22+ 0.92
63.41 0.87
Mst Prim
98.561 0.07
98.431 0.21
97.36+ 0.44
Strongly Connected Components
99.86 0.05
99.83 0.01
99.66+t 0.07
Topological Sort
99.94 0.03
99.931 0.03
99.69 0.06
Mean
94.18
94.09
93.11
21

---

Published in Transactions on Machine Learning Research (03/2023)
Table 11: Test scores of proposed processors 12 representative algorithms on (low-data regime) CLRS dataset. While the 2WL processor shows some level of robustness to the low-data regime, MPNN outperforms 2WL in phortest-path-relatee
tasks since max aggregation inductive bias is baked into the architecture, while the 2WL architecture requires a higher amount of data to learn such inductive biases. However, the hybrid processor still generalizes better compared to both processors.
Method
MPNN-G
2WL
Average Hybrid
Articulation Points
49.78 0.64
48.66 6.92
51.74 3.83
Bellman Ford
96.164 0.88
92.55 1.50
91.024 3.16
Bfs
100.00 0.00
99.67 0.17
100.00 0.00
Dag Shortest Paths
98.45+ 0.20
88.64 4.73
96.22+ 1.61
Dfs
26.19 1.20
25.29 9.87
27.08 1.54
Floyd Warshall
25.92 2.37
21.744 6.25
28.941 1.23
Graham Scan
96.81 0.79
73.80 3.69
96.88 0.35
Les Length
56.60 1.71
86.58 0.43
87.54 0.39
Matrix Chain Order
94.81 0.76
83.66 5.27
95.241 1.29
Mst. Prim
64.34+ 6.82
53.47+ 0.60
59.70+ 2.69
Quicksort
48.73 8.64
42.77 15.35
50.99 28.89
Task Scheduling
83.10 0.21
82.47 0.41
83. 13. 0.21
Mean
70.07
66.61
72.37
Table 12: Test scores of different hybrid models for combinations of MPNN-G and 2WL on L-CLRS dataset. A hybrid model of two different processors brings accuracy gain over each individual processor.
Method
Average (MP-MP) Avergae (2WL-2WL) Avergae (MP-2WL) Sigmoid (MP-2WL)
Mean
68.77:0.61
69.57-0064
70.92:10.69
71.98
22

---

Published in Transactions on Machine Learning Research (03/2023)
Table 13: Full test scores of Table for Scalar Index.
Method
MPNN-G
2WL
Average Hybrid
Sigmoid Hybrid
Articulation Points
88.92 3.39
69.59 5.05
78.58 1.48
80.70+ 2.11
Activity Selector
95.811 0.67
90.15 1.03
90.431 2.65
89.37 2.31
Bellman Ford
98.831 0.18
98.54 0.60
98.19. 0.14
98.03 0.68
Bis
100.00 0.00
100.00 0.00
100.00 0.00
100.00 0.00
Binary Search
93.201 2.07
90.301 1.32
86.171 11.38
89.701 2.80
Bridges
89.17 2.13
85.22.1 11.89
98.69 0.51
82.574 17.44
Dag Shortest Paths
99.721 0.06
95.91 1.54
99.10# 0.14
99.67 0.06
Dfs
25.031 1.62
21.11 4.18
19.041 1.79
22.561 1.08
Find Maximum Subarray Kadane
26.484 1.50
44.03:1 0.53
46.01 2.10
43.68 4.64
Floyd Warshall
35.394 2.05
30.75= 0.27
34.384 0.98
33.591 1.36
Graham Scan
98.881 0.25
82.691: 9.57
95.261 1.30
92.931 1.87
Les Length
58.85# 0.80
87.06= 0.71
86.97 0.54
88.56 0.32
Matrix Chain Order
73.65 9.55
76.291 3.82
73.47 5.28
68.70 3.11
Minimum
99.561 0.04
99.15.1 0.22
99.461 0.11
99.58 0.20
Mst Kruskal
72.07 1.03
84.77= 2.24
90.64# 0.79
88.01 2.31
Mst Prim
83.84 1.47
75.05 2.91
78.37 1.04
78.03 2.18
Naive String Matcher
7.36 1.64
8.48+ 1.29
9.54+ 2.72
12.83# 1.30
Optimal Bst
61.43 11.78
75.94= 0.82
74.96 1.87
76.12 2.06
Quickselect
3.741 5.29
0.20+ 0.21
0.234 0.18
29.361 41.52
Quicksort
10.06 3.49
17.25 12.53
10.86 5.96
14.45 7.63
Segments Intersect
98.16 0.20
96.58= 0.64
97.51 0.45
96.37+ 0.49
Strongly Connected Components
75.15 0.33
55.99 1.79
72.15 1.42
73.83 3.12
Task Scheduling
83.64 0.14
83.85= 0.55
84.21 0.72
83.82+ 0.24
Topological Sort.
82.61 1.50
62.09 8.14
77.86 3.26
85.00 2.53
Mean
69.2310.97
67.9610.64
70.92=0.73
71.9811.94
23

---

Published in Transactions on Machine Learning Research (03/2023)
Table 14: Full test scores of Table for Random Scalar Index. The Weighted Mean average over all algorithms when considering repeated algorithms with higher weight.
Method
MPNN-G
2WL
Average Hybrid
Sigmoid Hybrid
Articulation Points
89.86 1.79
72.46 2.51
79.07 0.88
81.97# 2.99
Activity Selector
94.024 1.96
89.94 1.02
92.31 1.40
91.07# 1.26
Bellman Ford
98.84 0.25
98.58 0.38
98.16+ 0.15
96.74 2.57
Bis
100.00 0.00
100.00 0.00
100.001: 0.00
100.00 0.00
Binary Search
95.41+ 1.35
94.94 0.96
94.45 0.90
96.70+ 2.15
Bridges
77.95 8.57
77.96 9.75
97.05 2.08
96.43 0.82
Dag Shortest Paths
99.761 0.07
96.6011 1.52
99.401 0.14
99.581 0.20
Dis
30.55 1.85
37.50 2.25
26.11 1.71
25.42+ 0.78
Find Maximum Subarray Kadane
49.251 3.93
74.30= 3.57
75.701 1.99
69.291 5.46
Floyd Warshall
35.041 1.26
30.321 0.42
33.751 0.90
32.66 1.80
Graham Scan
98.41 0.20
92.27+ 2.40
95.80+ 0.77
93.00 1.80
Les Length
58.961: 0.53
88.40= 1.03
87.531 0.76
88.99 0.60
Matrix Chain Order
92.34 0.53
91.591 1.08
92.541 2.17
92.121 1.05
Minimum
99.59 0.19
99.43 0.12
99.461 0.16
99.50 0.08
Mitt Kruskal
72.781 0.50
87.561 2.75
90.421 1.75
86.69 2.59
Mst Prim
81.791 1.24
76.641 2.94
78.221 1.97
78.521 1.50
Naive String Matcher
5.62+ 1.71
14.08 5.14
16.24 6.82
14.88 7.65
Optimal Bst
76.961: 1.19
72.491 2.43
77.681 1.15
76.82+ 2.83
Quickselect
3.344 4.72
0.15+ 0.08
0.63+ 0.69
0.05 0.04
Quicksort
6.411 1.98
7,41 1.56
15.331 8.84
26.241 19.85
Segments Intersoct
07.74# 0.23
96.17= 0.32
97.55+ 0.78
97.34 0.55
Strongly Connected Components
75.21 1.48
50.65# 1.37
71.47# 1.33
72.14 2.07
Task Scheduling
84.04 0.81
83.92 0.58
84.121 0.66
83.69 0.28
Topological Sort
82.80 0.96
83.18 1.36
80.84 1.84
83.65 1.26
Mean
71.11
71.52-1..53
74.33:10.49
74.97
Weighted Mean
64.29
64.79
68.00
68.89
24

---

Published in Transactions on Machine Learning Research (03/2023)
081
0.3
0.5
66-
6.-
000
000
03
(a) Task Scheduling
1.5
0.3
9.0
000
0.
00
03
04
65
26 0J CoNTESNE
62
23 04 15
65 1.2
03
01
05
67
O8 03
(b) Optimal BST
0.4
04
6.4
622
(c) MST Kruskal
Figure Model interpolation charts on three additional tasks. For each task, we train three models and pairwise interpolate their weights and plot ID and OOD accuracies. Each plot shows the interpolation of pair for each task. As suggested by the plots, ID and OOD accuracies have very different landscapes and ID accuracy is suboptimal model selector. In (a), the right plot shows the highest OOD accuracy corresponds with the lowest ID accuracy. In (b), the middle plot achieves its highest OOD accuracy when ID accuracy is not at its peak. (c), the right plot shows different rates of change for ID and OOD accuracies, OOD accuracy at its peak when ID not, and for coefficient 0.5, the OOD accuracy higher than that of ID.
25


Reviews:
[{"review_id": "JpnFKGNmZG", "reviewer": "Reviewer_ie3r", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strength:\n\n- The paper identifies a series of contributing factors that makes the OOD generalization of NAR challenging.\n- The paper proposes a set of expanded CLRS datasets to aid the study of the OOD issue.\n- The paper proposes a set of improvements to boost the OOD generalization performance. Specifically, the use of randomized node indexing (random scalar) and the proposed hybridization of 2WL and MPNN-G message-passing processors both exhibit visible improvement gains.\n\nweakness:\n\n- The method for enlarging the dataset seems tailored for some specific predefined OOD scenarios, which might harm the coverage of the empirical analysis and evaluation on top of it.\n- While the analysis part of the paper points out that model selection is problematic on CLRS due to near-perfect ID validation accuracy, the validation accuracy on L-CRLS also seems to be near-perfect for most cases (Table 9). I could be missing something, so perhaps the author can clarify.\n\nfurther comments & questions:\n\n1. In the Background section, when discussing CLRS, I feel the clarity could be further improved without much change. Currently, without going through the original CLRS paper, it is not clear to the reader which component of the program a node/edge represents. Perhaps adding an illustrative example would be sufficient.\n2. In table 2, why is the graph level accuracy for Floyd Warshall and Mst Kruskal 0 for all dataset variants?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies Out-Of-Distribution (OOD) generalization problem of Neural Algorithmic Reasoning (NAR). The paper argues that OOD generalization for NAR requires special treatment compared with OOD in other domains such as image, as NAR’s taskonomy prevents the use of standard regularizations technique such as data augmentation.\n\nThe author points out several contributing factors that makes OOD in NAR challenging, including suboptimal node indexing causing unnecessary distribution shift, dataset generation not covering all modes of the true distribution, model selection under near perfect ID validation scores, and two entangling factors (degree distribution and graph size) in CLRS benchmark.\n\nTo alleviate these issues, the paper proposes three major changes to the pipeline, including 1). a set of enlarged CLRS dataset (L-CLRS) that disentangles degree distribution and graph size, 2). randomized node indexing (random scalar) to avoid overfitting, and 3). A new hybrid message-passing method that combines MPNN-G and 2WL processors.\n\nExperimental results in conducted on the proposed variants of CLRS dataset, where the proposed random node indexing and hybrid processor outperforms prior art (MPNN-G).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "[minor] Adding an illustrative example in the Background section to link the graph representation (node/edge/graph) to their respective components of a program.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Pe8XgBAr0f", "reviewer": "Reviewer_2gZT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper lays out its contributions very clearly and was easy to follow from this perspective.\n- The paper points out a few concrete differences between typical OOD generalization settings and OOD in neural algorithmic reasoning.\n- The suggested improvements do seem to generally improve OOD performance.\n\n\nWeaknesses:\n- The exposition could be improved. For example, for those inexperienced with neural algorithmic reasoning (such as myself), Section 2 does little to explain how tasks such as sorting are actually put into graph form.\n- The claim that \"model selection is hard\" is not presented convincingly, since good model selection only requires monotonicity and not linearity in Figure 1---is it true that picking the best ID model performs very poorly on OOD data?\n- The solution in 4.1 (increasing dataset size) seems more like changing the problem than an actual solution---it's not really surprising that more data improves performance. The authors seem to acknowledge this and don't highlight it too much in writing, but it would be interesting to know whether the other suggested improvements (like the new processor, increased representativeness, etc.) depend on this increased dataset size, or whether they also improve things in the low-data regime.\n- It is often hard to line up the claims in captions/text with the quantitative results in the corresponding figures. For example, the caption of Figure 2 says \"While models achieve similar ID accuracy, their interpolations show very different OOD performances.\" I agree that the variation in the OOD accuracy does seem to be slightly bigger on average, but I think the conclusion that ID is constant while OOD varies is not true. Similarly, the accuracies in 1b and 1d do seem to fall on the line (and so does 1a prior to the x axis saturating at 100%) but this is not discussed in the caption or surrounding text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies out-of-distribution generalization in the context of so-called \"Algorithmic Reasoning Tasks,\" which are tasks where one uses a modern machine learning method (e.g., deep neural networks) to implement algorithms for known problems such as shortest-path, sorting, etc. The paper makes note of a few differences between OOD generalization in algorithmic reasoning and OOD generalization in computer vision, and proposes a few changes that improve OOD performance across tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to answering the questions raised above:\n\n- Improve clarity of writing, and fix various typos throughout the paper (e.g., \"underperming -> underperforming\", \"performances -> performance\", etc) \n- Add error bars for both tables and graphs (Table 1, Table 5, Figure 2)\n- Include in-distribution accuracies in Table 1\n- More thorough ablation of the improvements, rather than just showing that they are effective sequentially\n- In general, improve the presentation of the results: this includes showing both ID and OOD accuracy for the original algorithms considered in Table 1, then for each suggested improvement, showing a Table in the same format as Table 1 that has the accuracies before and after the proposed improvement. As it stands each paper is formatted totally differently and it's hard to tell where the actual improvements are.\n- The mode connectivity study could be more convincing---ways to make it more convincing include studying more tasks, using more models, and providing analogous results for vision.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "A54ruFGHx1", "reviewer": "Reviewer_t7tV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is reasonably well written, with extensive discussion and thorough reasoning of various design choices made. While it's not totally clear to me how robust the claimed improvements are, I think the authors adequately address the general difficulty of testing this and take pains to evaluate in a variety of settings.\n\nFurthermore, independent of the \"improving OOD performance\" contribution, I think the general argument made in this paper---that OOD generalization is a fundamentally different task for neural algorithmic reasoning and requires separate consideration/solutions/evaluation---is a useful one that stands on its own. **In fact, I think this constitutes by far the more interesting contribution**, with the proposed methods at the end of the paper feeling a bit like an afterthought and not as essential to the main story of the paper.\n\nI don't have any major complaints, just some general writing suggestions:\n\n* The introduction and earlier discussion is verbose. Lots of parentheses, repeating points several times when once or twice would suffice, etc. I think it would be more effective (and more approachable to casual readers) to state the main points very explicitly *much* sooner, and delay some of the more detailed discussion for a later section so that readers can get the gist of the paper and skip over the more detailed justification if they so choose. **For example, is it absolutely necessary to introduce \"hints\" so early in the main body and give experiments showing that they're not very helpful, just to say \"we won't be using them for the rest of the paper\"?** I think this discussion is lengthy and misplaced; I would suggest a brief sentence explaining why they're not being used, with discussion and experiments pushed to the appendix.\n\n* It is disorienting to reference figures in this discussion which are so far removed from when they are first mentioned. I imagine this could be fixed by shortening discussion as described above, but if you *have* to make a certain point so much earlier than the relevant experiments, I would prefer either moving the figure up, or simply referencing general \"supporting evidence\" in the relevant *section*, and then only referencing the specific figure once you get to that section. It's a bit unpleasant to click on a reference to a figure and then have to scroll all the way back up, and the need to do this generally indicates to me poor planning in the writing structure.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The majority of this paper is arguing that OOD generalization in neural algorithmic reasoning tasks requires fundamentally different considerations that more \"traditional\" OOD problems such as supervised classification or language processing. They point out several cases where existing approaches for improved generalization (understandably/expectedly) fail for algorithmic reasoning, and give convincing evidence for why many evaluation metrics can also be misleading.\n\nThe work also proposes some methods for improving OOD generalization of Transformer GNNs on these tasks, with reasonable results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Suggested writing changes aside, I don't see any glaring issues to be fixed before publication. I think the main body of the paper is currently quite a bit longer than it needs to be, and that the writers and their intended audience would be much better served with more aggressive editing and pushing more fine-grained details to the appendix.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: See Claims and Evidence above.
Decision: Accept (poster)