Dual Algorithmic Reasoning
Authors: Danilo Numeroso
Davide Bacciu
Petar Veličković
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Algorithmic Reasoning
Deep Learning for Graphs

Abstract: Neural Algorithmic Reasoning is an emerging area of machine learning which seeks to infuse algorithmic computation in neural networks, typically by training neural models to approximate steps of classical algorithms. In this context, much of the current work has focused on learning reachability and shortest path graph algorithms, showing that joint learning on similar algorithms is beneficial for generalisation. However, when targeting more complex problems, such "similar" algorithms become more difficult to find. Here, we propose to learn algorithms by exploiting duality of the underlying algorithmic problem. Many algorithms solve optimisation problems. We demonstrate that simultaneously learning the dual definition of these optimisation problems in algorithmic learning allows for better learning and qualitatively better solutions. Specifically, we exploit the max-flow min-cut theorem to simultaneously learn these two algorithms over synthetically generated graphs, demonstrating the effectiveness of the proposed approach. We then validate the real-world utility of our dual algorithmic reasoner by deploying it on a challenging brain vessel classification task, which likely depends on the vessels’ flow properties. We demonstrate a clear performance gain when using our model within such a context, and empirically show that learning the max-flow and min-cut algorithms together is critical for achieving such a result.

Published as a conference paper at ICLR 2023
DUAL ALGORITHMIC REASONING
Danilo Numeroso
Davide Bacciu
University of Pisa
University of Pisa
danilo.. www.nooo@eph.....moooooo.. unipi. it
davide davide.bacccuuunge www.ciuuniipiii.....cc... it
Petar Veličković
DeepMind
petarv@deeepmiddccom
ABSTRACT
Neural Algorithmic Reasoning is an emerging area of machine learning which seeks to infuse algorithmic computation in neural networks, typically by training neural models to approximate steps of classical algorithms. In this context, much the current work has focused on learning reachability and shortest path graph algorithms, showing that joint learning similar algorithms is beneficial for gen- cralisation. However, when targeting more complex problems, such "similar" al- gorithms become more difficult to find. Here, propose learn algorithms by exploiting duality of the underlying algorithmic problem. Many algorithms solve optimisation problems. We demonstrate that simultancously learning the dual def- inition of these optimisation problems in algorithmic learning allows for better learning and qualitatively better solutions. Specifically, we exploit the max- max-flow min-cut theorem to simultaneously learn these two algorithms over synthetically generated graphs, demonstrating the effectiveness of the proposed approach. We then validate the real-world utility of our dual algorithmic reasoner by deploying it on a challenging brain vessel classification task, which likely depends on the vessels' flow properties. We demonstrate clear performance gain when using our model within such a context, and empirically show that learning the max-flow and min-cut algorithms together is critical for achieving such result.
INTRODUCTION
Learning to perform algorithmic-like computation is a core problem in machine learning that has been widely studied from different perspectives, such learning to reason (Khardon & Roth, 1997), program interpreters (Reed De Freitas, 2015) and automated theorem proving (Rocktäschel & Riedel, 2017). As matter of fact, enabling reasoning capabilities of neural networks might drasti- cally increase generalisation. i.c. the ability of neural networks to generalise beyond the support of the training data, which is usually difficult challenge with current neural models (Neyshabur al., 2017). Neural Algorithmic Reasoning (Velickovic & Blundell, 2021) is a recent response to this long-standing question, attempting train neural networks exhibit some degrees of algorithmic reasoning by learning to execute classical algorithms. Arguably, algorithms are designed to be gen- eral, being able be executed and return "optimal" answers for any inputs that meet set of strict pre-conditions. On the other hand, neural networks are more flexible, i.e. can adapt to virtually any input. Hence, the fundamental question is whether neural models may inherit some of the positive algorithmic properties and use them to solve potentially challenging real-world problems.
Historically, learning algorithms has been tackled as simple supervised learning problem (Graves et al., 2014; Vinyals et al., 2015), i.e. by learning an input-output mapping, through the lens of reinforcement learning (Kool et al., 2019). However, more recent works build upon the notion of algorithmic alignment (Xu et al., 2020) stating that there must be an "alignment" between the learning model structure and the target algorithm in order to ease optimisation. Much focus has been placed Graph Neural Networks (GNNs) (Bacciu et al., 2020) learning graph algorithms, ie Bellman- -Frd (Bellman, 1958). Velickovic et al. (2020b) show that is indeed possible to train GNNs to execute classical graph algorithms. Furthermore, they show that optimisation must oceur

---

Published as a conference paper at ICLR 2023
on all the intermediate steps of a graph algorithm, letting the network learn to replicate step-wiss transformations of the input rather than learning a map from graphs to desired outputs. Since then, algorithmic reasoning has been applied with success in reinforcement learning (Deac et al., 2021), physics simulation (Velickovic et al., 2021) and bipartite matching (Georgiev & Lió, 2020).
Moreover, Xhonneux et al. (2021) verify the importance of training on multiple "similar" algorithms at once (multi-task learning). The rationale is that many classical algorithms share sub-routines, i.e. Bellman-Ford and Breadth-FFrst Search (BFS), which help the network learn more effectively and be able to transfer knowledge among the target algorithms. Ibarz et al. (2022) expand on this concept by building generalist neural algorithmic learner that can effectively learn to execute even a set of unrelated algorithms. However, learning some specific algorithmss might require learning of very specific properties of the input data, for which multi-task learning may not help. For instance, algorithm (Ford & Fulkerson, 1956) for maximum flow entails learning to identify the set of critical (bottleneck) edges of the flow network, i.e. edges for which a decrease in the edge capacity would decrease the maximum flow. Furthermore, in the single-task regime, ie. when we are interested in learning only one single algorithm, relying on multi-task learning can unnecessarily increase the computational burden the training phase.
learning the Ford-Fulkerne
Motivated by these requirements, we seek alternative learning setups to alleviate the need for training on multiple algorithms and enable better reasoning abilities of our algorithmic reasoners. We find potentially good candidate in the duality information of the target algorithmic problem. The concept of duality fundamentally enables an algorithmic problem, e.g. linear program, be viewed from two perspectives, that of a primal and a dual problem. These two problems are usually complemen- tary, i.c. i.c. the solution of one might lead the solution of the other. Hence, we propose to incorporate duality information directly in the learning model both as an additional supervision signal and input feature (by letting the network reuse its dual prediction in subsequent steps of the algorithm), an approach we refer to as Dual Algorithmic Reasoning (DAR). To the best of our knowledge, there exists no prior work targeting the usage of duality in algorithmic reasoning. We show that by train- ing an algorithmic reasoner on both learning of an algorithm and optimisation of the dual problem we can relax the assumption of having multiple algorithms to train on while retaining all the bene- fits of multi-task learning. We demonstrate clear performance gain in both synthetically generated algorithmic tasks and real-world predictive graph learning problems.
PROBLEM STATEMENT
We study the problem of neural algorithmic reasoning graphs. Specifically, we target learning of graph algorithms A : G + Y that take in graph-structured inputs G = (V, E, x; Ciy). with V being the set of nodes and E the set of edges with node features æ; and edge features Cij. and compute a desired output y E Y. Usually, the output space of an algorithm A depends on its scope. In the most general cases, it can either be RIVI (node-level output), |/V|X (edge-level output) or IR (graph-level output). We mainly consider the class of algorithms outputting node-level and edge-level outputs, which includes many of the most well-known graph problems, e.g. reachability, shortest path and maximum flow. From neural algorithmic reasoning perspective, we are par- ticularly interested in learning a sequence of transformations (steps of the algorithm). Hence, we where each element represents the intermediate state of the target algorithm we aim to learn. At each step t we have access to intermediate node (t)
consider a sequence of graphs {G (...) G(T-1)}
and edge features, i.c. x!" eij called hints as well as intermediate targets (!)), As is com- mon in classical algorithms, some of the intermediate targets may be used node/edge features in the subsequent step of the algorithm. Such hints are thus incorporated in training as additional features/learning targets, effectively learning the whole sequence of steps (algorithm trajectory).
In particular, we focus on learning maximum flow via the neural execution of the Ford-Fulkerson algorithm. Differently from Georgiev & Lió (2020), who learn Ford-Fulkerson find the indepen- dent set of edges in bipartite graphs, we aim to learn Ford-Fulkerson for general graphs. We report the pseudo-code of Ford-Fulkerson in the appendix. Ford-Fulkerson poses two key challenges: (i) it comprises two sub-routines, i.e. finding augmenting paths from to t, and updating the flow assignment F(t) E V VV at each step t; (ii) F must obey a set of strict constraints, namely the edge-capacity constraint and conservation of flows. The former states that scalar value Gif
2

---

Published as a conference paper at ICLR 2023
(capacity) is assigned to every (i,5) E and F must satisfy:
v(i.j) E Fij S Cij:
i.e. flow assignment an edge must not exceed its capacity. The latter states that the assignment
needs to satisfy:
WEVIS (8,1):
Σ Fi, (WEE
Σ D F A Σ F.j = UiEE
Σ FSe (1,)
(2)
(SJ)EE
iee. the flow sent out from the source is not lost nor created by intermediate nodes. This also leads to F =-F", i.e. antisymmetry. An optimal solution F to the max flow problem is the one maximising the total flow in the network, i.c. D(.j)er Fej. We show how we address both challenge (i) and (ii) directly in the model architecture, through the concept of algorithmic alignment and by carefully adjusting and rescaling the model predictions.
3 METHODOLOGY
3.1 LEVERAGING DUALITY IN ALGORITHMIC REASONING
We leverage the concept of duality when learning to neurally execute classical graph algorithms. In particular, most of the problems solved by classical algorithms (including maximum flow) can be expressed in the form of constrained optimisation problems such as linear programminy or integer linear programming. In mathematical optimisation, the duality principle ensures that any optimisa- tion problem may be viewed from two perspectives: the "direct" interpretation (called the primal problem) and the dual problem, which is usually derived from the Lagrangian of the primal problem. The duality principle ensures that the solutions of the two problems are either linked by an upper- bound/lower-boutt bound relation (weak duality) or equal (strong duality) (Boyd al., 2004). Hence, the two problems are interconnected.
In the context of neural algorithmic reasoning, we identify several reasons why primal-dual informa- tion might be useful to consider. First, by incorporating primal- objectives, we let the network reason on the task from two different and complementary perspectives. This can substantially sim- plify learning of algorithms which require identifying and reasoning properties which are not explicitly encoded in input data. For instance, to effectively solve max-flow problems, the network needs the ability to identify and reason critical edges. By the max-flow min-cut theorem (Ford Jr & Fulkerson, 2015), this set of edges corresponds to the minimum cut, i.e. dual problem, that sep- arates the source node from the sink t. Hence, correctly identifying the minimum cut is highly relevant for producing relevant max-flow solution.
Second, heing able output better step-wise solution means that there is less chance for error propagation throughout the trajectory of the neurally executed algorithm. This is especially true for more complex algorithms, such as Ford-Fulkerson consisting of multiple interlocked sub-routines. There, an imprecise approximation of one sub-routine can negatively cascade on the results of the following ones. Finally, learning jointly on the primal-dual can be seen an instance of multi-task learning, but relaxing the assumption of having multiple algorithms to train on.
In the following, we study dual algorithmic reasoning on the max-flow primal complemented with min-cut dual information. Note that graph neural networks have been formally proven to be able to learn minimum cut, even under uninformative input features (Fereydounian et al., 2022). This also implies that solving min-cut can be useful "milestone" for a network learning to solve max-flow.
3.2 ARCHITECTURE
We rely the neural algorithmic reasoning blueprint (Velickovic & Blundell, 2021), building on the ancode-process-decode framework (Hamrick et al., 2018). The abstract architecture of the Dual Algorithmic Reasoner (DAR) is depicted in Figure I for the Ford-Fulkerson algorithm. Since the latter is composed of two sub-routines, we introduce two processors to align neural execution with the dynamics of the algorithm. The first processor PBF learns to retrieve augmenting paths, while Pr learns to perform flow-update operations F()), Both Par and Pr implemented graph
3

---

Published as a conference paper at ICLR 2023
Node encoder
2
PDF
p
Znj
Edge encoder
Residual Graph Cy
Figure 1: High-level architecture of the Dual Algorithmic Reasoner (DAR) for the Ford-Fulkerson algorithm. Refer to the text for comprchensive explanation.
networks with Passsage-Passing Neural Network (MPNN) convolution (Gilmer al., 2017):
(++1) h h(th1)
v0 h
(8)
(J,))E
where the and dh are neural networks with ReLU activations and + permutation-innarian function, i.e. summation, mean or max.
Intuitively, the encode- poaaee-proces--ecoee architecture allows decoupling learning of the algorithmic steps from the use of specific input features. Through the learned processor, the algorithm can be neurally executed on latent-space which Iearnt representation of the input features required by the original algorithm. We will show how we can exploit this property to perform steps of the Ford-Fulkerson algorithm even with missing input features.
More in detail, the DAR computational flow comprises two linear encoders, fo and fe, which are applied respectively node features x; and edge features eij produce encoded node-level and edge-level features:
(t)
- (2ا - These encoded representations are used as inputs for the processor network PBF which computes the latent node representations (t) as:
1 (z (a V)
= Sa(e v(i,j) E E}.
H (t) PBF (6) 2 (((1)))
with (0)) (0 Vi E V). our DAR instance, this processor performs Bellman-Ford steps to retrieve the shortest augmenting path from s to 1, following Georgiev Lió (2020). ())) is then passed to a decoder network producing the augmenting path (!):
(4) The augmenting path is represented as vector of predecessors for all nodes in the graph, i.e. each entry Pt (t) is pointer to another node j in the graph. This way, we are able to reconstruct a path from any node (included !) back to the source node s. The augmenting path (t is then passed to Pr as an input feature. The target quantities of the algorithm, i.e. flow assignment F and minimum cut c, are finally predicted as:
P
(z) (())).
(F(() c) - gF (Pr (Pr (t) 20 ()).
W.L.o.g. choose to represent the minimum s-f cut node-level features, where c; indicates that is the cluster of nodes of s, and c; = 1 otherwise. Note that the minimum s-f cut includes all edges (i,j) for which e; and ej 1. Furthermore, F()) is reused input feature in the next step of the algorithm (F 0).
We pay additional attention the prediction of the flow assignment matrix F(t), in order to be compliant with the maximum flow problem constraints described in subsection 3.1. In particular, transform F to ensure compliance with anti-symmetry, i.e. F' F FT. To satisfy edge- capacity constraints we further rescale the matrix according to the hyperbolic tangent and the actual value of the capacity Gy for each (i.j) E E, such:
F tanh F) ④ C,
(5)

---

Published as a conference paper at ICLR 2023
Ford-Fullesson
Ford-Fulkemon meonsstructinn
13
PGN max (arimal)
meNn (prmal)
PGN-max (dual)
PGN-maan (dual)
PGN-max (pipe)
PGN-menn (pips)
01
08
07
14
PGN (primal)
maxN-max
05
8000
20L8
12
50.0
0.20
10-00
Train stops
Train stops
(a) Ford-Fulkerson validation loss
(b) Fuld-Fulkerson reconstruction loss
Figure 2: (a) Ford-Fulkerson validation loss on synthetic data for PGNs, (b) normalised loss curve of reconstructing Ford-Fulkeree with encoders for 4aj. diy Pij. with both the primal and dual PGN-max. It applies to BVG data.
where C,2 Ciy for all edges in the graph. We note that this only satisfies the box constraint on the edge capacities, however the conservation of flows might still be violated, i.e. nodes in the path from the source to the target may either retain some amount of in-flow (sending out less than what is received) vice versa. To address this last constraint, we simulate the entire neural algorithm until termination and apply a corrective procedure order to correct all the flow conservation error. We report the pseudocode of this procedure in the Appendix, along with additional details and results.
4 EXPERIMENTS
To assess the benefits the dual algorithmic reasoning approach, we test the learning model in two specific scenarios. First, train and test the DAR pipeline synthetic-generate' graphs, to evaluate the benefits in the key task of algorithmic learning (section 4.1). Then, to evaluate the generality of the model test it a real-world graph learning task. Specifically, compare our model with several graph learning baselines on a biologically relevant vessel classification task (Pactzold al., 2021), comprehending large-scale vessel graphs (section 4.2). We stress that our neural reasoners are not further re-trained on real-world data, thus forcing the model to use the algorithmic knowledge attained on synthetic data to solve the new task.
4.1 SYNTHETIC GRAPHS
Data generation We consider two different families of graphs: (i) 2-community graphs, in which communities are sampled from the Erdös-Rényi distributions with probability 0.75 and their nodes are interconnected with probability 0.05; (ii) bipartite graphs. To thoroughly assess the general- isation capabilities of our algorithmic reasoners, we exclusively trained all models on small 2- community graphs and tested on 4x larger 2-community graphs partite graphs family. We highlight that bipartite graphs are solely used for testing purposes and no further training occurs on them. To generate train, validation and test sets we follow the stan- sample 1000 2-community
and 4x larger bi-
dard CLRS benchmark (Veličković et al., 2022) setup. Specifically, in-distribution performance, training graphs with 16 nodes each. The validation set is used to assess thus comprising 128 2-community graphs with still 16 nodes. To assess out-of-distributin and out- of of-family generalisation we consider respectively 128 test 2-community samples and 128 bipartite samples, both of size of 64 nodes. Furthermore, we generate data of all intermediate steps of the Ford-Fulkerson algorithm to be used as hints and additional training targets, in order to train the net- work all intermediate data manipulations. Algorithm features once again generated following the CLRS-30 standard and they comprise: (i) inputs: source node s, sink node t, edge-capacity ma- trix C. E x and additional weights W E [o, ||]V for the Bellman-Fort processor; (ii) hints (algorithm steps): augmenting paths " and intermediate flow assignments F((;; (iii) outputs (learning targets): final flow matrix F and minimum cut Lastly, capacities sampled as integers
5

---

Published as a conference paper at ICLR 2023
Table 1: Mean Absolute Error (MAE) and accuracy of predicting the final F and intermediate flow F(1), and min-cut (if applicable) 2-community and bipartite graphs. (primal) corresponds to training on max-flow only. (dual) corresponds to training with both primal-dual heads. (pipeline) corresponds to learning min-cut first. (no-algo) corresponds optimising directly max-flow, with- out learning Ford-Fulkerson.
2- 2-Comuunity (out-of-distribution)
Bipartite (out-of-family)
Model
F
F(O)
F
F(()
PGN-max (primal)
0.266
0.29440.002
0.56-0.23
0.82.a.17
PGN-mean (primal)
0.27410.001
0.311
1.09
1.13=0.18
MPNN-max (primal)
0.263
0.289 +0.00
0.75-0.47
0.78+u.11
MPNN-mean (primal)
0.278
0.313:10003
0.75
0.92.0.22
PGN-max (dual)
0. 0.002
0.269
100%.4..
0.49
0.78
100%
PGN-mean --ean (dual)
0.240 400004
0.285+u..044
100%
1.10-a.30
1.05+0.12
99%6+u.7
MPNN- -mx (dual)
0.206
0,288 0.00
100%
0.71=0.32
0.98
100%
MPNN-mean (dual)
0.258g00008
0. 0.268
100%
0.81=0.08
1.06g0.35
100%==0.
PGN-max (pipeline)
0.256:20.001
0.293 003
61 11.1
0.45
0.77 26
90.
PG PGN-mean (pipeline)
0.244.10.001
0.304 0.001
100%=10.0
0.98
1.03
99%
MPNN-max (pipeline)
0.261 +:0.002
0.31 3312+0.00
61%40.3
0.47
0.95
90%
MPNN mean (pipeline)
0.255
+0.92
100%
0.64=0.35
0.92 20
100%
Random
0.7440
50%+0.0
1.00=a.00
50%++..
PGN-mas -ax (no-algo)
0.31440.013
0. 0.78=u.u2
from (O, 10) and then rescaled via a min-max normalisation for 2-community graphs, while they are sampled as either 0 or 1 for bipartite graphs.
Ablation& neural architectures We performed an ablation study to assess the contribution from the dual, by training the same DAR architecture without the additional min-cut head (consequently the dual information does not flow back in Pr in Figure 1). To deepen our analysis, we also consider neural architecture where the minimum cut is learnt prior the Ford- Sord-Fulkerson algorithm. Specif- ically, we introduce a third processor that is trained solely on minimum cut, whose output is then compare
used additional feature for the architecture presented in Figure 1. Furthermore, two different types of processors: (i) fully-connected Message-Passing Neural Network (MPNN) (Gilmer et al., 2017), which implements equation 3 and exchanges messages between all pairs of nodes; (ii) Pointer-Graph Network (PGN) (Velickovic et al., 2020a), which instead exchanges mes- sages only between node and its neighbours defined by the imputs and hints of the algorithm. For all processors, we try different aggregation operators in equation 3, namely θ {max, mcan, sum). We train all models for 20,000 epochs with the SGD optimiser and we average the results across runs. We also use teucher forcing with decaying factor of 0.999. This has the effect of provid- ing the network with ground-truth kints for the early stage of the training phase, while letting the network predictions flow in for the majority of training. To choose optimal hyperparameters, e.g. learning rate, hidden dimension, we employ a bi-level random search scheme, where the first level samples values of hyperparameters in large range of values, while the second one "refines" the search based on the first level results. We choose the best hyperparameters based on the validation error F. Aggregated validation loss curves shown in Figure 2(a). For further details on the model selection, refer to the appendix.
Results analysis We report results on Ford-Fulkere Fuld-Fulersonn simulation in Table 1. Specifically, we use the Mean Absolute Error (MAE) as metric for assessing the predictions of the final flow assignment F. obtained as in equation 5. Similarly, we measure average performance on all the intermediate flow assignment P()) in order to show how well the algorithm is imitated across all steps, which is referred to as F(1) in Table 1. Where applicable, we report accuracy on the minimum cut as well, i.e for dual and pipeline models. To better evaluate all models, we include random baseline which samples at random and rescales it following equation 5 and GNN trained to directly output the flow matrix F without learning Ford-Fulkerson (marked as no-algo). First, Table shows clear performance advantage with respect to the two baselines, indicating that learning max-flow with the support of algorithmic reasoning, i.e. learning of Ford-Fulle Ford-Fulkerson, is more effective. More importantly, we notice how models incorporating the prediction of the dual problem consistently outperform the primal baselines on both 2-community and bipartite graphs. Dual architectures also
6

---

Published as a conference paper at ICLR 2023
Table 2: Qualitative analysis on the prediction of F. Mean Absolute Error (MAE) used as the regression error from the ground truth maximum flow value. For simplicity, we only report results of the pest-performing models (PGNs).
primal
dual
pipeline
Metrie
PGN-max
PGN-mean
PGN-max
PGN-mean
PGN-max
PGN-mean
F F
7.86 0.47 8.68 1 0.21
0.34 + 0.04
0.41 + 0.01
7.58 + 0.10 0.38 + 0.08
better imitate the algorithm across all intermediate steps compared to primal, as testified by lower F(1). This suggests that the dual min-cut information, despite being easy to learn (Fereydounian et al., 2022), helps the model achieve a lower prediction error. This finding is also strengthened by the observation that whenever the min-cut prediction is imprecise, e.g. (PGN, MPNN)-ma pipeline for 2-community, the prediction of F and F(() become consequently worse. From our experiments, the dual PGN architecture with max aggregator emerges as the best-performing model, at least for what concerns 2-community graphs, being able to perfectly predict also the minimum cuts of all the graphs in the test set. Contrastingly, learning min-cut first is less stable (while still outperforming the primal baseline) confirming prior work findings on the effectiveness of multi-task learning.
The performance gap also increases when testing out-of-family on bipartite graphs, where dual and pipeline with max aggregator are both very competitive. We note that for bipartite graphs we record higher mean and standard deviations. While this behaviour is emphasised by the fact that capacities are sampled as either 0 or I, i.e. leaving more chances for prediction errors, this testifies that generalisation to arbitrary graph distributions is still a challenging task.
To further evaluate the performance of DAR, we perform qualitative study, whose results are presented in Table 2. For 2-community graphs we assess how close the pre- dicted flow matrix F is to the optimal max-flow solution without considering errors for intermediate nodes. This gives a measure of how well the network can predict the maximal flow value in the graphs and use in the predicted solution. To achieve that, we ignore intermediate errors and only measures flow signal exiting the source node s and entering the sink node t, i.e. [(aj)e Faj and EGDEEE Fzt. Thus, we take the maximum (absolute value) between the two and compare this value to the ground truth maximum flow value F*. From Table 2 observe that all the dual architectures exhibit a solution which reflects the true maximum flow quantity in the input graphs, i.e. F 0.30 of MAE from the optimum on average. This analysis further solidifies our claim that DAR model can positively transfer knowledge from the dual to the primal problem resulting in more accurate and qualitatively superior solutions. This claim is also supported by the fact that both primal architec- tures and dual architectures for which min-cut results are worse miss the optimal solution by large margin (compare PGN-max -mxx pipeline min-cut results in Table and higher MAE in Table 2).
Qualitative analysis
4.2 REAL-WORLLD GRAPHS
Benchmark description We assess generality and potential impact of the DAR pipeline by con- sidering real-world edge classification task, for which prior knowledge of the concept of max-flow might be helpful. We test both the primal and the DAR architectures on the Brain Vessel Graphs (BVG) benchmark (Pactzold et al., 2021). This benchmark contains 9 large-scale real-world graphs, where edges represent vessels and nodes represent bifurcation of the vessel branches in brain net- work. The task is to classify each edge in three categories: capillaries, veins and arteries based on the following features: vessel length ley; shortest distance between bifurcation points dej; and curva- ture Pij. Note that the three classes can be distinguished by the radius of the vessel, or equivalently, by the amount of blood flow that can traverse the vessel. Hence, being able to simulate the blood flow in the entire brain network is likely to be advantageous to effectively solve the task. As an additional challenge, note that the classification task is highly imbalanced, i.e. 95% of samples are capillaries, 4% veins and only 1% arteries.
We test the models three BVG graphs, namely CD1-E-1 (the largest, with 5,791,309 edges), CDI-E-2 12,150.326 edges) and CDI-E-3 (3,130,655 edges). BVG data also include a synthetic brain vessel graph for validation purposes, comprising 3159 nodes and 3234 edges.
7

---

Published as a conference paper at ICLR 2023
Algorithm reconstruction The main difference with our synthetic tasks is that here we need to estimate the vessel diameter/radius which is a quantity that can be related with the vessel capacity, Le. how much blood (flow) can traverse the edge. Therefore, the capacity is a learning target rather than one of the features to feed our algorithmic reasoner with. Here, we exploit the generality of the prooode-rrccss-eecodee architecture and learn to reconstruct the Ford-Fulkerson neural execution. Specifically, we reuse PGN-max networks pre-trained on 2- 2-community graphs (section 4.1).
As the capacity is no longer an input feature, we drop the capacity encoder from fu and introduce three new encoder layers in fv. one for each feature of the vessel graph benchmark, i.e. lij, dej. Pij- Thus, we freeze all the parameters in the pre-trained models apart from the introduced encoder layers. Hence, we only train the weights of Lyg, dij. Pig to learn ford-Fulkerson steps in absence of input information about capacity. In other words, the model learns to use lig, dij; Pij to estimate the edge flows in the network, which act as proxy information for edge capacities, i.e. our primary objective in the BVG task. We perform these learning steps of algorithm reconstruction on the synthetic vessel graph provided by the BVG benchmark. Source and sink nodes s, are chosen as two random nodes whose shortest distance is equal to the diameter of the graph. We train to reconstruct the algorithm for 15000 epochs, with Adam optimiser (Kingma & Ba, 2015) and learning rate le-5. Figure 2(b) compares the loss curves for the primal and DAR models, on the task.
Thus, we simulate one single step of Ford-Fulkerson on CDI-E-X through PGN-max primal and dual models and extract hidden learnt representations for each node, which are then summed to- gether get edge embeddings. These edge embeddings will be used additional input features for the graph neural networks (described below) which we train to solve brain vessel classification. Fi- nally, we highlight how this approach allows to easily dump the embeddings, as the reconstructed encoders and processors will not be training further on real-data.
Neural architectures We consider graph neural networks from the BVG benchmark paper as our baselines, namely Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017). GraphSAGE (Hamilton et al., 2017) and ClusterGCN (Chiang et al., 2019) with GraphSAGE convolution (C- SAGE). The general architecture consists of several graph convolutional layers with ReLU acti- vations followed by a linear module. Additionally, we use the embeddings extracted by PGN-max (primal) and PGN-max (dual) to train a simple linear classifier (LC) to assess how much information these embedding add with respect to the original 4g. dij, Pij features. We also use those representa- tions in combination with GraphSAGE AGE and C-SAGE. Specifically, our embeddings are concatenated together with the GraphSAGE's and C-SAGE's learnt embeddings prior the final lincar layer. As an additional sanity check, we also train Node2Vec (Grover & Leskovee, 2016) on each of the three datasets and concatenate its learnt embeddings the same way. All models are trained with early stopping of 300 epochs and optimal hyperparameters taken from the BVG paper, which we report in the appendix for completeness. Finally, we average the results across 3 trials.
Results analysis Results on the BVG benchmark reported in Table 3. As the learning problem is highly imbalanced, we use the balanced accuracy score (average of recall for each class) and the area under the ROC curve as metrics to evaluate the performance.
Looking at LC performance, we see that the algorithmic reasoner embeddings (both primal and dual) are informative, resulting in an average 16.6% increase in balanced accuracy and 10.5% in ROC across the three datasets when compared to simple features. Dual embeddings also show superior performance compared to primal embeddings, as testified by consistent increments in both metrics. Figure 2(b) hints that this might be due to a better algorithm reconstruction in the dual, which results in more informative representations. LC performance also gives clear indication of how well the algorithmic reasoner is able to positively transfer knowledge acquired on synthetic algorithmic tasks to unseen real-world predictive graph learning ones.
When considering the use of learnt embedding in combination with GNN architecture, we note significant performance improvements over vanilla (i.e. non algorithmically enhanced) GNNs, C- SAGE with dual embeddings achieves the best performance on all three datasets with a consistent performance gap for CDI-E-3 and CD1-E-2. Interestingly, dual embeddings consistently outper- form Node2Vec embeddings. This is remarkable, considering that Vece2 is trained directly on the CDI-E-X data, whereas DAR only performs inference on them. A reason to this performance gap might be that Vec essentially widens the local perceptive field of graph neural networks
8

---

Published as a conference paper at ICLR 2023
Table 3: Balanced accuracy (Bal. Acc.) and area under the ROC curve (ROC) performance metrics on large-scale brain vessel graphs. LC refers to a linear classifier. In addition to the standard archi- tectures, we consider variants where the final linear classification layer takes in additional Node2Vec (Grover & Leskovec, 2016) learnt embeddings and embeddings extracted from PGN-max primal and dual architectures.
CDI-E-3
CDI-E-2
CDI-E-1
Model
Bal. Ace.
ROC
Bal. Acc.
ROC
Bal. Aec.
ROC
LC
39.3%-o.2
52.3%
36.9%
55.9%+4.1
45.5%.+..
61.7%=o.0
LC (N2V)
13.9%
55.5%+b.
71.9%+0.
62. 62.6%.4..o
46. 16.1%+o.
60.0%
LC (primal)
48.6%-oo4
59.4%
58.7%
63.8%.4..2
45.3%
59.9%=a.1
LC (dual)
53.8%_o.3
66.2%o10.
67.3%
71.8%.0.0
48.1 18..5
62. 62.1%=o..
GCN
58.1%=o..
67.9 67.9%
74.6%
78.7%+4..
59.0%
67.9%-oo.
SAGE
63.5%-o.2
70.9%+0.3
73.9%++o.
82.5%+0.2
64.7%.o.7
74.2%=o.2
SAGE (N2V)
65.0%_o.1
71.9%.0.
84.1%+1.9
82.5%.4.4
65.9%.1o.
74.8%=0..
SAGE (primal)
61.5%
72.0%11.2
83.8%
83.7%610.
66.2%.1.5
74.8%
SAGE (dual)
66.7%-o.4
75.0%.4..
85.2%
85.5%64.2
66.4%.o.3
74.8%
C-SAGE
68.6%-u.s
74.2%
81.8%
85.6%+4.2
59.3%
68.3%-u.6
SAGE (N2V)
68.6%-oo.
74.1%+0.1
84,8%.+0.2
84.8%%44.5
67.4%
75.9%++o2
C-SAGE (primal)
67.3%_
73.6%.+19
82.5%++1.
84.0%++..
67. 67.7%+o.1
75.8 75.8%=o.2
C-SAGE (dual)
70.2%61..
76.3%.10.
85.6%10.2
86.7% 86.7%=20.
68.1%10.
75.8% 75.8%.10.1
with random walks an attempt capture global graph features. On the contrary, DAR utilises more principled approach based on the simulation of graph flow. This means that the learnt latent space encodes the information necessary to reconstruct the flow assignment and consequently edge capacities, these being more informative for the specific task. DAR models also exhibit very good generalisation capabilities. In fact, we recall that the networks are only trained on graphs with 16 nodes and extract meaningful representations for graphs with millions of nodes, being able to pro- vide clear performance advantage over baselines. This might also indicate a way worth pursuing to realise sustainable data-efficienl learning models for graphs.
CONCLUSION
We have presented dual algorithmic reasoning (DAR), neural algorithmic reasoning approach that leverages duality information when learning classical algorithms. Unlike other approaches, we relax the assumption of having multiple algorithms to be learnt jointly and show that incorporating the dual of the problem targeted by algorithms represents a valuable source of information for learnt algorithmic reasoners. We showed that learning together the primal-dual max- max-flow-in fow-min-cut problem can substantially improve the quality of the predictions, as testified by the quantitative and qualitative evaluations of the models. Furthermore, dual algorithmic reasoners have demonstrated to generalise better, showing positive knowledge transfer across different families of graph distributions and ex- tracting informative representations for large-scale graphs while only being trained on toy-synthetic graphs. In this context, we also demonstrated for the first time how more classical graph learning tasks can be tackled through exploitation of algorithmic reasoning, via algorithm reconstruction. On final note, we identify several problems and algorithms that may benefit from dual reasoning ap- proach. First, max-flow and min-cut may be representative for a wide class of primal/dual pairs, for which strong duality holds. There, the dual solution can be used recover the primal optimum (and vice versa), equivalently to max-flow and min-cut. Examples of such problems are shortest path and min-cost flow problems. More interestingly, we may generalise this approach to target also weak primal-dual problems, in which the dual objective is an approximation of the primal objective. Even in the case of weak duality, dual information is valuable, as testified by the numerous algorithms exploiting primal-dual relations (Balinski, 1986; Pourhassan et al., 2017). Particularly interesting problems to target may be the Travelling Salesman Problem (Cormen et al., 2009), for which a dual formulation includes learning to output I-tree (Bazaraa & Goode, 1977). and the Weighted Vertex Cover problem, for which the dual can effectively be used to develop 2- 2-approximation heuristics (Pourhassan et al., 2017). We believe that results showed in this manuscript should strongly mo- tivate further work in this direction, extending the analysis to other pairs of primal-dus dual problems, such the ones suggested in this section.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.
REFERENCES
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs. Neural Networks, 129:203-221, 2020.
Michel L Balinski. competitive (dual) simplex method for the assignment problem. Mathematical Programming, 34(2):125-1411 1986.
Mokhtar S Bazaraa and Jamie J Goode. The traveling salesman problem: A duality approach. Mathematical Programming, 13(1):221-231 1977.
Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In KDD, pp- 257-266. ACM, 2019.
Thomas H Cormen, Charles E Leiserson, Ronald Rivest, and Clifford Stein. algorithmss, 3rd edition, pp. 1111-1117. MIT press, 2009.
Introduction to
Andreea Deac, Petar Velickovie, Ognjen Milinkovic, Pierre-Luc Bacon, Jian Tang, and Mladen Nikolic. Neural algorithmic reasoners are implicit planners. NeurlPS, pp. 15529-15542, 2021.
Mohammad Fereydounian, Hamed Hassani, Javid Dadashkarimi, and Amin Karbasi. The exact class of graph functions generated by graph neural networks. CoRR, abs/2202.08833. 2022.
Lester Randolph Ford and Delbert Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399-404 1956.
Lester Randolph Ford Jr and Delbert Ray Fulkerson. Flows in networks. Princeton university press, 2015.
Dobrik Georgiev and Pictro Lió. Neural bipartite matching. Graph Representation learning and Beyond Workshop. ICML., 2020.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neu- ral message passing for quantum chemistry. In ICML, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pp- 855-864. ACM, 2016.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
Jessica B. Hamrick, Kelsey R. Allen, Victor Bapst, Tina Zhu, Kevin R. McKee, Josh Tenenbaum, and Peter W. Battaglia. Relational inductive bias for physical construction in humans and ma- chines. In CogSci. cognitivesiencessciity.ggg 2018
10

---

Published as a conference paper at ICLR 2023
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličković. A generalist neural algorithmic learner. In Bastian Rieck and Razvan Pascanu (eds.), Proceedings of the First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, pp- URL https: http:///ooceeedeegeeoo wwt.......//ws.....
2:1-2:23, PMLR, 09-12 Dec 2022. ibarz22a. html.
Roni Khardon and Dan Roth. Learning to reason. Journal of the ACM (JACM), 44(5):697-725, 1997.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR (Poster). OeenRevi 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In ICLR (Poster). OpenReview.net, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. Advances in neural information processing systems, 30, 2017.
Johannes C. Paetzold, Julian McGinnis, Suprosanna Shit, Ivan Ezhov, Paul Büschl, Chinmay Prab- hakar, Anjany Sekuboyina, Mihail I. Todorov, Georgios Kaissis, Ali Ertürk, Stephan Günnemann, and Bjoern H. Menze. Whole brain vessel graphs: A dataset and benchmark for graph learning and neuroscience. In NeurIPS Datasets and Benchmarks, 2021.
Mojgan Pourhassan, Tobias Friedrich, and Frank Neumann. On the use of the dual formulation for minimum weighted vertex cover in evolutionary algorithms. In Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, pp. 37-44, 2017.
Scott Reed and Nando De Freitas. arXiv: 2015.
Neural programmer-interprette
arXiv preprint
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. Advances neural
information processing systems, 30, 2017.
Petar Velickovic and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7): 2021.
Petar Velickovie, Lars Buesing, Matthew C. Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. In NeurIPS, 2020a.
Petar Velickovic, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execu- tion of graph algorithms. In ICLR. OpenReview.net, 2020b.
Petar Velickovic, Matko Bosnjak, Thomas Kipf. Alexander Lerchner, Raia Hadsell, Razvan Pascanu, and Charles Blundell. Reasoning-modulltted modulated representations. CoRR, abs/2107.08882 2021.
Petar Veličković, Adrià Puigdomenech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning bench- 2022.
mark. arXiv preprint
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NIPS, pp. 2692-2700, 2015.
Louis-Pascas A. C. Xhonneux, Andreea Deac, Petar Velickovic, and Jian Tang. How to transfer algorithmic reasoning knowledge to learn new algorithms? In NewrIPS, pp. 19500-19512, 2021.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In ICLR. OpenReview.net. 2020.

---

Published as a conference paper at ICLR 2023
A
PSEUDO-CODE
A.1 FORD-FULKERSON PSEUDO-CODE
We consider a standard Ford- Fulkerson implementation, shown in Algorithm 1.
Algorithm Ford-Fulkersoo
Input: G = (V, (,
fue v(u,v) E E
while augmenting path p s,..., ., Gy do;
df = mmin(Cue (u, v) E PP:
for each (u, 8) p
fue fuv df
fa - Ju + df
end for end while return f
A.2 CORRECTIVE FLOW PROCEDURE PSEUDO-CODE
The corrective procedure is shown in Algorithm 2. We discriminate between negative nodes i if (E Flg E Fj+) < 0, i.c. the node keeps some of the flow, and positive nodes it if the sum of in-flow and out-flow is instead positive. Thus, we enforce the flow conservation constraint two simple steps. First, all negative nodes i sends back the source an amount of flow equal to the magnitude of the constraint violation without considering edge-capacities. All positive nodes instead, lower the amount of out-flow towards the sink l. After this step, the conservation of flows is satisfied but we have introduced capacity violations in the graph. Hence, in the second step we impose back capacity constraints. Starting from the source s, we find paths with capacity violations and clamp the flow value to the maximum capacity. Thus, we readjust the flow sent from until all capacities violations are corrected and no flow conservation error occurs.
Algorithm Flow correction algorithm
Input: G E), F: flow matrix, C: capacity matrix, source, sink
V = {u u V E (LW)EE Fi + -(Cii) Fu < 0}
V+ v Σ (1.))E Fiv + E(mier Fai 0}
for each #- V- do
(n.eeR Fud find a path from e to and send back amount of flow end for for each 2+ E V+ do == =-E Fiv + (ODDER Fod
==1> F...
find a path from wt to and reduce the out-flow by
end for E. E(SDEE Fs: -EENEE Carl while E, > 0 do
find a path from t and reduce the fut-flow by enforcing capacity constraints recompute E,
end while return F
12

---

Published as a conference paper at ICLR 2023
Table 4: First-level and second-level random searches details.
Level
Hyperparameter
Min. value
Max. value
Distribution
Learning rate
le-5
le-1
log-uni log-uniform
Level
Weight decay
le-5
le-1
log-uniform
Hidden dimension
512
uniform
Learning rate
le-3
le-2
log-uniform
Level 2
Weight decay
le-3
4e-3
log-uniform
Hidden dimension
60
100
uniform
B HYPERPARAMETER OPTIMISATION
B.I SYNTIETIC GRAPIIS
We sample n = 50 configurations for each level of the bi-level random search. In Table we report details for the first and second level random searches, where the second refines the first based on validation results of the primal model. Winner hyperparameters for primal model are: hidden dimension 68, learning rate 0.009341, weight decay 0.003420. Winner hyperparameters for dual model are: hidden dimension 65, learning rate 0.009868, weight decay 0.001734. Pipeline shares hyperpameters with dual.
B.2 BRAIN VESSEL BENCHMARK
Optimal hyperparameters for BVG data are presented in Table 5. We perform minimal hyperparam- eters optimisation for C-SAGE for CDI-E-I, as the optimal hyperparameters reported in Pactzold al. (2021) did perform well. Specifically, we optimised number of layers and number of hiddens by grid-searching over {2, 3, 4] and (64, 128), respectively.
Table 5: Optimal hyperparameters used for the BVG benchmark. Note that C-SAGE needs more epochs for CD1-E-3.
Dataset
GCN
SAGE
C-SAGE
Node2Vec
Ir=3 10-3
Ir=3 10-3
Ir=3 10-3
Ir=1 10
layers=3
no. layers=4
layers=4
walk length=40
CDI-E-3
no. hiddens=256
no. hiddens=123 128
no. hiddens=128
walks per node= 10
dropout=0.4
dropout=0..4
dropout=0.2
no. hiddens= 128
epochs=1500
epochs=1500
epochs=5000
epochs=5
1r=3 10-3
no. layers=4
CD1-E-2
above
above
hiddens=128 above
dropout=0.2 epochs=1500
Ir=3 10-3
no. layers=3
CDI-E-1
as above
as above
no. hiddens=64
as above
dropout=0.2 epochs=1500
C ADDITIONAL RESULTS
Qualitative study Here, present additional qualitative study for all models in Table on synthetic graphs, both 2-community and bipartite. To further strengthen qualitative findings of Ta- ble 2, aim to measure what extent the optimal max-flow value can be linearly decodable from
13

---

Published as a conference paper at ICLR 2023
Table 6: R² score of predicting the maximum flow value from learnt graph representations hg. R metric emits score in (-30, 1], with 1 being the best possible score.
primal
dual
pipeline
Graphs
PGN-max
PGN-mean
PGN-max
PGN-mean
PGN-max
PGN-mean
2-community
0.69 0.12
-0.59 + 0.33
1.00 0.00
0.93 + 0.01
0.80 + 0.05 -0.13 1 0.29
bipartite
-0.79 0.81
-115.6 = 64
0.98 0.01
-115.2 + 64
-0.69 = 0.33
0.98 0.01
the learnt node representations. Specifically, we compute ground truth optimal max-flow value f for all graphs in the test sets. Thus, for all models we neurally execute Ford-Fulkerson, collect learnt node embeddings h; and obtain graph representations hg through MAX-POOL operation. Thus, we fit linear models on {hg} and compute the R2 score to evaluate the quality the predictions. Table shows that from dual embeddings we are able to linearly decode the optimal max-flow value almost perfectly, i.c. 2 0.99 on average across the two graph distributions, confirming once again that learning min-cut and max-flow together is beneficial and yields more informative representations.
Enforcing flow conservation As explained in section 3.2 of the main paper, the max-flow output of the algorithmic reasoner (equation 5) is a noisy version (F) of a real correct solution F, as it may not satisfy the conservation of flows constraint (equation 2). We can enforce the flow conservation through Algorithm 2. Figure 3 provides visual example of how the flow conservation is corrected by the corrective procedure of Algorithm 2, showing that is possible to extract correct solution from the neural output. In the figure, we represent negative nodes i (see subsection A.2) with blue and positive nodes it with red. Sources should always be "positive" nodes (flow always sent out) while sinks should be "negative" (flow is always received). White nodes in Figure 3(b) represent nodes for which equation holds.
2.0
200
20
20-
030
450
40
40
0.5
035
60
0.0
60
0.00
50
50
-0
100
200
-075
-075
120
220
(a) Flows pre-correction
(b) Flows post-correction
Figure 3: This figure shows the (normalised) flow conservation error for all nodes axis) of each test graph (y axis). (a) shows the predicted F conservation error prior Algorithm 2. (b) shows the corrected conservation error. Through Algorithm 2 we are able to correct all the inner error (white represents zero error), with and being the only nodes which respectively send and receive flow.
Putting together Node2Vec and dual embeddings Table 3, Node2Vec and dual embeddings arose as the most informative node embeddings for solving the brain vessel classification task. Therefore, we run an additional experiment by concatenating together these two embeddings and learning neural networks to solve the BVG task the same way it was done in subsection 4.2 for primal/dual/N2V embeddings separately. We report these results in Table 7. We record higher results for these combined embeddings compared to using the two embeddings separately. hinting that Node2Vec and dual representations encode two different kinds of information that might be effectively combined, i.e. structural (the former) and blood flow (the latter).
14

---

Published as a conference paper at ICLR 2023
Table 7: Additional BVG results for concatenation of Vode2Vec and dual embeddings. To be com- pared to Table in the main paper.
CD1-E-3
CDI-E-2
CDI-E-1
Model
Bal. Ace.
ROC
Bal. Acc.
ROC
Bal. Acc.
ROC
LC (dual-N2V)
53.9%
66.3%+4.1
77.8%=o.1
74.3%.o.1
48 2..22
62.1%
SAGE (dual-N2V)
70.1 10.1
76.5%.1.11
89. 89.2%=20.
86. 86.3%
67 67.5%
76.0% 67.0%:10.
C-SAGE (du)l-N2V)
70.4%60.1
76.7%.10.1
88.3%
85.0%
75.8%
Table 8: Validation results 2-commmaitt graphs for all models.
Model
F
(t)
RGN-max (primal)
0,218 + 0.002
0.272 + 0.006
PGN-mean (primal)
0,199 = 0.001
0.281 + 0.004
MPNN-max (primal)
0.215 + 0.003
0.271 0.003
MPNN-mean (primal)
0.235 + 0.008
0.304 + 0.005
PGN-max (dual)
0.183 0.001
0,250 0.002
100% = 0.0
PGN-mean (dual)
0.184 + 0.001
0.266 + 0.004
100% + 0.0
MPNN-max (dual)
0.185 + 0.001
0.246 + 0.002
100% 0.0
MPNN-mcan (dual)
0.184 + 0.001
0.246 = 0.002
100% 0.0
PGN-max (pipeline)
0.189 = 0.002
0.262 + 0.003
98.2% + 0.1
PGN-mean (pipeline)
0.193 = 0.001
0.264 = 0.002
100% 0.0
MPNN-max (pipeline)
0.188 + 0.003
0.257 0.003
98.3% 0.1
MPNN-mean (pipeline)
0.204 + 0.001
0.278 + 0.002
100% + 0.0
Random PGN-max (no-algo)
0,553 0.003
50% 0.0
0.256 + 0.002
D VALIDATION RESULTS
To better evaluate the algorithmic generalisation of our models, we report validation results on syn- thetic data in Table 8. Additionally, Figure 4, similarly to Figure 2(a) for PGNs. Lastly, we also report validation performance for all variants of C-SAGE models, i.e. vanilla, primal, dual and pipeline, brain vessel classification (see Figure 5).
report additional plots showing loss of MPNN. * models in
Ford-Fulkorson validation loss
MrNN-mmx (primal)
MPNN-mean (pnmel))
MPNN-max (dual)
MPNN-mean (dual)
MPNN-max (pipe)
MPNN-mean (pips)
17
0.
Train
Figure 4: Ford-Fulkerson validation loss for MPNN processors.
15

---

Published as a conference paper at ICLR 2023
OGBN CD1 E validation
OGBN CD1 E validation
34
ClusterGCN
ClusterGCN (primal)
ClusterGON
ClusterGCN (prima))
(N2V)
ClusterGCN (dual)
CusterGON (N2V)
ClusterGON (dual)
Eval
steps
OGBN-CD1-E-1 validation
08
115
03
ClusterGCN
ClusterGCN (arimal)
ClusterGON (N2V)
ClusterGCN (dual)
700
DOK 85
300
20
ot
Eval stops
Figure 5: Validation performance of C-SAGE variants CDI-E-X in terms of balanced accuracy. Truncated lines in CDI-E-3 plot represent early stopping.
16


Reviews:
[{"review_id": "X8odGuWTDQ9", "reviewer": "Reviewer_4SGE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel method for learning algorithms with neural networks. Specifically, the authors design a new architecture for processing graph data and a new training routine that considers both primal and dual formulations of optimization problems. Using min cut max flow problems, they compare their method to existing neural algorithmic reasoning tools. They show that their method beats the existing methods.\n", "summary_of_the_review": "The technique is interesting and novel, but the empirical results are lacking. ", "strength_and_weaknesses": "Strengths: \n  - Interesting and novel approach to leaning algorithmic reasoning using primal/dual.\n  - Timely: the algorithmic reasoning community is growing.\n  - Clear writing and good exposition.\n\nWeaknesses: \n  - There is only one algorithmic problem considered. In related work, more than one algorithm is used to show performance. This is a major weakness of the paper since the main claims are not entirely supported. The abstract states, \"We demonstrate that simultaneously learning the dual definition of these optimisation problems in algorithmic learning allows for better learning and qualitatively better solutions.\" and In the conclusion, the authors write:  \"We showed that learning together the primal-dual problem can substantially\nimprove the quality of the predictions, as testified by the quantitative and qualitative evaluations\nof the models. Furthermore, dual algorithmic reasoners have demonstrated to generalise better,\nshowing positive knowledge transfer across different families of graph distributions and extracting\ninformative representations for large-scale graphs while only being trained on toy-synthetic graphs.\" But I find the claims much more general than the empirical findings which relate to only one problem on graph data and only two different families of graphs. \n\nMinor issues not affecting score:\n    - The citations and figure references are not linked. \n\n___\n\n\nAfter reading the author response, I have changed my score. The authors have addressed my concerns.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UTdQ2kPy2b", "reviewer": "Reviewer_vEcN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes DAR, an approach of Neural Algorithmic Reasoning following the FordFulkerson algorithm for calculating maximum flow. The key idea is to simultaneously learn the primal and the dual problem which is max-flow and min-cut in this case. This should produce a similar advantage to multi-task training. Experiments on synthetic graphs demonstrate that the proposed method performs better than learning to predict max-flow only. Experiments on real-world Brain Vessel Graphs demonstrate that DAR retains useful knowledge for extracting edge features that advance the performance of edge classification.", "summary_of_the_review": "This is an interesting paper on neural algorithmic reasoning. The proposed approach is reasonable and achieves decent improvements compared with baselines. I lean toward accepting. ", "strength_and_weaknesses": "Strength\n1 The idea of using duality for neural algorithmic reasoning is intuitive and interesting. \n2 The implementation of DAR for max-flow and min-cut is technically sound.\n3 Experiments on both synthetic data and real-world data are solid and demonstrate the advantage of neural algorithmic reasoning and dual algorithmic reasoning.\n\nWeakness\nThe main concern is that this paper proposes only the idea of DAR and one demonstration of how to implement this idea for max-flow but lacks a general implementation method. It is unclear how difficult it is to set up a DAR model for other algorithms and tasks. Maybe proposing a general implementation is too difficult, more experiments on how to use duality for other algorithms are also welcome and helpful.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "29dRBzUEb0b", "reviewer": "Reviewer_vSCg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper follows a line of work on learning to mimic algorithms with neural networks to allow for better out-of-distribution generalization. Following recent advancement, the authors aim to train a GNN to simulate the intermediate steps of graph algorithms, using intermediate states of the true algorithm as supervision targets.\n\nThe authors expand on recent findings that training such an architecture benefits from multi-task learning, i.e. simultaneously learning to execute multiple related algorithms. They propose to leverage duality by simultaneously learning the primal and the dual version of an optimization algorithm. This gives the benefits of multi-task learning, reduces the chance for error propagation, and allows to leverage the learnt dual problem as a subroutine of the primal algorithm.\nSpecifically, this paper considers learning to execute the Ford-Fulkerson algorithm for the max-flow problem along with its dual min-cut problem.\n\nThe method follows the encode-process-decode framework, and consists of two iteratively executed GNN processors operating on the latent space. The first processor retrieves augmenting paths, while the second one learns to perform flow-update operations and predicts min-s-t-cuts. Some of the constraints on the max-flow are enforced by appropriate transformations, others are corrected for after termination of the neural algorithm.\n\nThe method is empirically tested on both synthetic and real-world data. \nThe neural algorithm is trained on small synthetic 2-community graphs.\nIn the synthetic experiment,  it is then evaluated on synthetic graphs that are out-of-distribution and out-of-family. The results show a clear benefit of incorporating the dual information both in terms of final performance and in terms of algorithmic alignment. They also demonstrate the benefit of using the dual solution as a subroutine of the primal neural algorithm, thereby extending beyond the setting of simple multi-task learning.\n\nIn the real-world experiment, the task is to classify the edges of a large-scale brain vessel graph from edge-level features. The goal is to improve existing classification pipelines by extracting additional features that capture the flow-capacity, using the neural algorithm that was trained on synthetic data. After retraining the encoder to adapt for the new inputs, the neural algorithm is executed for a single step on the large-scale graph, and the latent representation of the neural algorithm is aggregated to extract the edge features. Running existing classification pipelines with the additional features shows a clear performance improvement, demonstrating that the neural algorithm captures useful information even when executed on graphs much larger than the training data.", "summary_of_the_review": "This paper proposes a novel idea, translates it into a well-designed method and empirically validates the effectiveness on both synthetic and real-world data. This is a strong paper in my opinion that is highly relevant for the ICLR community, and I therefore recommend acceptance.", "strength_and_weaknesses": "Overall, I liked this paper a lot. It is very well written and the idea of using duality information for learning to execute optimization algorithms with neural networks is exciting. \nThe empirical evaluation is also very strong in my opinion, clearly showing the benefit of the proposed method even when going beyond an evaluation on purely synthetic data. \n\nOne critique point is that the paper only covers one specific primal/dual pair of algorithms (max-flow/min-cut), and the architecture is heavily engineered towards this problem. It would be great to see how the presented ideas of using dual information as a subroutine of the primal algorithm translate to other primal/dual pairs of algorithms, a short exposition of potential candidates would be very useful.\nAdditionally I have some remaining questions on the details of the method and the experiments. \n- What is the architecture used for the two decoders? \n- Is there an interpretation for the big differences in performance from max and mean pooling? Could they be used in conjunction to improve performance or at least to remove the need to optimize over it?\n- Regarding re-training for the real-world experiment: What exactly is the training setup for training the new encoder? Is the true radius of the vessel used to produce ground truth capacities that the target algorithm is executed on? Have the authors tried to directly predict the capacity from the three available features as a baseline?\n\n\nSidenote: In Figure 1 the second processor also accesses the inputs of the algorithm, but the arrows are not drawn.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%