Learning Arborescence with An Efficient Inference Algorithm
Authors: Nan Jiang
Maxwell J Jacobson
Yexiang Xue
Venue: Submitted to ICLR 2023 (2023)
Keywords: minimum weight arborescence
arborescence Learning

Abstract: We consider a class of structured learning problems on arborescence (i.e., the directed spanning tree) from the input graph. The key step involved in this problem is predicting the minimal weight arborescence (MWA) from the learned model. In literature, there are two lines of research for predicting MWA: the Chu-Liu Edmonds (CLE) and the Lovasz methods.  The CLE method is easy to implement while it takes $\mathcal{O}(n)$ cycle contractions. Here $n$ is the graph size.  The Lovasz method reduces to the multi-pair shortest path (MPSP) problem and takes only $\mathcal{O}(\log n)$ contractions. Nevertheless, in the CPU setting, MPSP has the same time complexity as finding MWA. The Lovasz method only attains time efficiency under a sufficient GPU setting. Both the aforementioned methods are painfully slow for large-scale learning tasks.  In this research, we find the general MPSP problem can be simplified when working with machine learning models. This is because the learning model predicts edge weights for all pairs of vertices and the graph we process is always complete.  Therefore, we only need to handle those paths that directly enter every weakly connected component (WCC) while the classic Lovasz method needs to handle all possible paths. This allows us to propose LAzy LoVAz (Lava) method that enjoys $\mathcal{O}(\log n)$ contractions as well as efficient performance in both CPU and GPU settings. In experiments, we consider synthetic datasets and two real-world learning tasks, i.e., graph-based dependency parsing and unsupervised parsing on ListOps.  The empirical results exhibit important gains of our Lava method to the classic CLE and Lovasz methods, that Lava boosts the training time for arborescence learning tasks.

Under review as a conference paper at ICLR 2023
LEARNING ARBORESCENCE WITH AN EFFICIENT IN- FERENCE ALGORITHM
Anonymous authors Paper under double-blind review
ABSTRACT
We consider class of structured learning problems arborescence (i.e., the di- rected spanning tree) from the input graph. The key step involved this problem is predicting the minimal weight arborescence (MWA) from the learned model. In literature, there are two lines of research for predicting MWA: the Chu-Liu Edmonds (CLE) (Chu & Liu, 1965) and the Lovász (Lovász, 1985) methods. The CLE method is easy to implement while it takes (n) cycle contractions. Here n is the graph size. The Lovász method reduces to the multi-pair shortest path (MPSP) problem and takes only (log n.) contractions. Nevertheless, in the CPU setting, MPSP has the same time complexity as finding MWA. The Lovász method only attains time efficiency under a sufficient GPU setting. Both the aforementioned methods are painfully slow for large-scale learning tasks. this research, we find the general MPSP problem can be simplified when working with machine learning models. This is because the learning model predicts edge weights for all pairs vertices and the graph we process is always complete. Therefore, we only need handle those paths that directly enter every weakly connected component (WCC) while the classic Lovász method need handle all possible paths. This allows us to propose Lazy Loyáz (Lavá) method that enjoys Olog n.) contractions as well as efficient performance in both CPU and GPU settings. experiments, we consider synthetic datasets and two real-world learning tasks, i.c.. graph-based based dependency parsing and unsupervised parsing on ListOps. The empirical results exhibit important gains of our Lavá method to the classic CLE and Lovász meth- ods, that Lavá boosts the training time for arborescence learning tasks.
INTRODUCTION
This paper primarily focuses structured learning with the output structure being arborescence (i.e., directed spanning tree). Examples real-world arborescence learning problems include graph- based dependency parsing (Koo et al., 2007) and ListOps parsing (Nangia & Bowman, 2018). At every step of learning, the neural model needs to infer the minimum weight arborescence (MWA). This inference procedure is mainly resolved by the Chu-Liu Edmonds algorithm (CLE) (Chu & Liu, 1965; Edmonds, 1967) or the Lovász method (Lovász, 1985).
The CLE method is straightforward 2004). However, when dealing with larger-scale input graphs, CLE spends the majority of the time on cycle contractions. In fact, show the CLE takes O(n) rounds of contractions theoretically and empirically. Here is the size of vertices in the graph. Lovász (1985) transformed the original finding MWA problem into the multi-pair shortest path (MPSP) problem. The Lovász method only needs O(logn) contractions. Under sufficient GPU setting where the shortest path can be com- puted efficiently, Lovász algorithm attains faster running time over the CL.F method. Later works marginally improve the classic Lovász with less GPU resource (Amato, 1993) and generalize to distributed network (Fischer & Oshman, 2021).
its implementation (Gabow et al., 1986; Mendelson et al.,
Since the learning model predicts the edge weights for all pairs of vertices, the graph we process is always complete. After the edge pre-process step, all the edge weights are non-negative (in Remark 1) and the graph is partitioned into several weakly connected components (WCCs). The classic Lovász method asks for computing the shortest path for every outside vertex 2; into the cycle in the current WCC, which may travel around all the vertices and go inside and then outside

---

Under review as a conference paper at ICLR 2023
range of WCC
path may visit all outside vertices
paths visit only inside vertices
outside vertices
o
the cycle
(a) Graph after "edge pre-process" (b) Inefficient SSSP in Lovász
(c) Efficient SSSP in our Lavá
Figure 1: Our Lavá method is more efficient than the classic Lovász when computing the shortest path from outside to the cycle. (a) The pre-processed graph with circle denotes vertices and arrow (+) denotes edges. "WCC" stands for weakly connected component. (b) In Lovász method, the outside vertex may find a path that wanders around over several WCCs, that involves all the vertices in the graph. (c) Our Lavá method computes those paths that directly enter the WCC and never go outside. Our method limits the scope of the shortest path and thus attains time efficiency.
of the current WCC. We observe that this can be simplified by considering those paths that directly enter the current component and never go outside. Such paths always exist because the graph we process is densely connected. We thus save the computation workload by limiting the scope of the shortest path. This observation allows us to attain time efficiency and thus boosts the training time for large-scale learning problems. Fig. illustrates this idea with one potential graph.
In this research, we introduce, Lazy Lováz (Lavá), an unified algorithm for finding MWA. Except for the above observation, we also introduce bag of tricks for finding MWA on the large-scale and densely-comnected graph. To detect the cycle and compute the shortest path, we exploit the property of matrix power to replace matrix computation. Therefore, our method is not only convenient and efficient for implementation with Numpy or Pytorch but also transparent to the CPU or GPU devices.
algorithms. The whole method is described in the language of
In experiments, we show the advantage of our Lavá approach in synthesized graphs and two real- world applications. the synthetic experiment, we first show the empirical number of contractions by the CLE algorithm increases linearly with the graph size while our method takes much fewer contractions. Then we show that our Lavá method takes much less empirical running time to find large-scale setting. Furthermore, for the dependency parsing task
MWA than CLE approach datasets and unsupervised parsing over Listops task, we show the proposed Lavá method attain show better rumning time than the CLE method over real-world datasets. Our contributions are:
(1) We propose an efficient inference algorithm (i.e., Lavá) for finding MWA, which is more compat- ible with and efficient for large-scale arborescence learning problems. (2) Theoretically, show that our Lavá method takes O(log n) and CLE takes Oloog n) round of contractions. We further show the correctness of our Lavá after adopting our observation the shortest path. (3) We evalu- ate our method on synthetic data and two real-world applications. We show that Lavá is faster than CLE over all the datasets and tasks.
PRELIMINARIES
2.1 LEARNING ARBORESCENCE
Notations. Denote G(V, E) as weighted and directed graph with a given root r E V. Root r has incoming edges and the rest vertices strongly connected. The adjacency matrix A that represents the connectivity of the graph is: for 2i, Iz V,
Aij A(zi,z,) = (5)) If ef 2.) E E
(I)
If ef 2.) &
where (x);, : x VV R denotes the weight of edge (0,,0)) in the graph. We assume edge weights are all finite. All the incoming edges of vertex I; correspond to i-th column vector A, and all the outgoing edges can be found in i-th row vector A,.-
Min-plus Product. The min-plus product, is defined on the adjacency matrix for computing the shortest path in the graph (Williams & Xu, 2020). We denote "*" as the min-plus product. Let
2

---

Under review as a conference paper at ICLR 2023
matrix S contain all all-pair nwo-step shortest distances, with Siy be the shortest distance of two-step path 2; - 2%k + 2z. S and Sij are computed as:
A
Si
min As + Akd ISRS|VI
(2)
The min-plus product can be easily implemented as generalized matrix-matrix multiplication using current GPU-based software, like Pytorch and JAX. The high parallelism of GPU greatly boosts the empirical running time for the min-plus product.
r-arborescence. The r-arborescence is directed spanning tree with root r (Korte & Vygen, 2018). a subgraph T that covers all the vertices the graph G and there a unique directed path in T from to every other vertex I; E V. The weight of an arborescence T is the summation of its edge weights (Jaini et al., 2018): (TT) = - (x,,,,)) (e))eT" ((2,, zy). The Minimum Weight r-Arborescence (MWA) is an r-arborescence whose ((T) is minimum among all possible arborescences.
Learning r-Arborescence. The edge weight function Φa actually a neural network parameterized by 0. Given a set of vertices {-; J the network predicts the possible edge weight on (Zi for every pair of vertices T4, x. The arborescence represented as the binary matrix {0, 1 1)n8", where Tiş 1 denotes edge e(z,, zz)) is included. Similarly, the score of arborescence is given by de (T(z) = Σ (M.T))T dhe (T), The probability of arborescence is defined as:
1
Pa(T
exp(1ee (T
where Zz(x))
exp(Oo(T(xx) T'ET())
Σ
Z
Ze is the partition function and Txx) denotes all possible arborescences. In inference, given the trained parameters 0 for the network, we predict the arborescence with the maximum score:
arg
de (T(x) arg T'ET(2)
min T'ET(s)
Σ oo(Li,
(4)
We can construct the adjacency matrix Ag (in Eq. 1) using negative weight 6o (2a, myy) for all pairs of edge e(r;, n,). It exactly finding the MWA for Ag. We brief the inference procedure Sec. 2.2.
Given training set (a*h I* J where each T is labeled output for input a Learn- ing can be achieved via maximal likelihood estimation. In other words, we find the optimal param- eters 0* by minimizing the negative log-likelihood: (o(D)
Σm de (T* + log Zo (z*). Recently, Paulus et al. (2020); Struminsky et al. (2021) propose the recursive Gumbel-man trick, that we can estimate the term log (I( using the Gumbel distribution:
log Zo(x)= = Eg'
max (ET
Σ (ETT))ET
00(x,, + o/s
S Gumbel 1)
(5)
We use Eq. 4 to predict the set of edges on MWA with the perturbed adjacency matrix As + o' and compute the corresponding arborescence score. The parameters can be trained using gradient descent: g++1 6r v (D)) where 7) is the learning rate and (Dg(D) is the gradient of the negative log-likelihood function.
2.2 FINDING MIN-WEIGHT ARBORESCENCE
Chu-Liu Edmonds (CLE) (Chu & Liu, 1965; Tarjan, 1977) the most well-known method for find- ing MWA. Later, Lovász (1985); Amato (1993); Fischer & Oshman (2021) proposed a theoretically efficient variant by optimizing over the worst case CL.E. We brief CL.F and Lovász methods below.
Chu-Liu Edmonds. 1) For every non-root vertex (z; + r), find the incoming edge with minimum weight then subtract this minimum value from all the incoming edges of vertex z;, 2) Next extract all the vertices along with all the edges with weight being zero. They form new graph F. If there are multiple zero-weight edges, then randomly pick one incoming edge for every vertex. F has no cycle, it is clearly the minimum one. So the contraction terminates. 3) Otherwise, there exists at least one cycle. Every cycle is then contracted into a single super vertex. Those self-cconecttdd edges removed. The resulting graph is noted G'.
3

---

Under review as a conference paper at ICLR 2023
The above three steps are recursively applied over graph G' until the final contracted graph is an arborescence. On termination of the contraction, the expansion procedure is launched to recursively expand those super vertices (i.e., contracted cycles) and determine which edge on the cycle should be discarded. Finally, it outputs the set of edges of MWA in the original graph. Figure ((a) sketches the connection of our Lavá and CLE methods.
Lovász's Meta Algorithm. Lovász (1985) considered the worst case of CLE, noted as nested cy- cle contractions. The CLE method might spend many steps contracting nested cycles. The Lovász approach reduces to the multi-pair shortest path (MPSP) problem and only takes O (logn) contrac- tions in the worst case. Specifically, the Lovász approach finds the shortest entering path into a cycle. The algorithm not only contracts those vertices on the cycle but also those vertices relevant to the shortest entering path. The whole contraction process is detailed in Appendix A. For those follow-up works, Amato (1993) reducing the dependency on processors in the GPU setting and Fis- cher& & Oshman (2021) improved the running time in distributed CONGEST network. Figure (bbcc illustrates the major difference between our Lavá and Lovász methods.
METHODOLOGG
For the task of learning arborescence from training data, the neural network de takes in all vertices "i....., F' as input and outputs a set of edges 7 that form the arborescence with maximum score (as in Eq. 4) at every step of gradient computation. Specifically, the network predicts the edge score for every pair of vertices (1, zt) and constructs the adjacency matrix Ag. As mentioned in Sec. 2.2, CLE method takes this matrix Ag as input and outputs the set of edges that forms MWA by recursive contractions and expansions. The CLE method is insufficient because it spends most of the time shrinking to smaller and smaller graphs and later expanding to larger and larger graphs. In fact, we show in Sec. 3.2 that CLE requires (nn) contractions and expansions, under the mild assumption of the graph. Since large-scale inputs are the norm in real-world settings, this limits the scalability of those machine learning tasks that relies on the efficient inference of MWA.
As mentioned in Sec. 2.2, Lovász (1985) solved the nested cycle contractions problem, that re- duces from (n) contractions to Oloog n) contractions. Nevertheless, Lovász's meta-algorithm itself (Lovász, 1985) and its variants (Amato, 1993; Fischer & Oshman, 2021) need to compute the multi-pair shortest path (MPSP) problem to find the shortest entering path into the cycle. Specif- ically, every outside vertex needs to find the shortest path to the cycle, where the path could come inside the WCC that contains the cycle and go outside. In the worst case, the path may touch all the outside vertices. Solving the intermediate MPSP problem makes Lovász time-consuming.
In this research, we find the general MPSP problem can be simplified when working with neural networks. Since the graph constructed by the neural network is always complete, a path once enters the WCC should never go outside. By ruling out those paths that wander around several WCCs, outside vertex and directly enter the WCC. Our
only consider those paths that start from Lavá methods solve a much smaller scale problem and thus gain computational efficiency compared with the Lovász method. This allows us to propose Lazy Lováz (Lavá) method that enjoy Olog n) contractions with friendly and efficient implementation in CPU and GPU settings. For example, Figure 1(b.c) presents our Lavá method can better handle the shortest entering path problem than Lovász method. Figure ((a) presents our Lavá takes fewer contractions than CLE method.
3.1 FINDING WEIGHT ARBORESCENCE WITH LAZY LOvÁsZ ALGORITHM
Given the adjacency matrix A E Rax= (in Eq. I), the task is to output those edges that form the MWA. Assume root r has the largest index and the MWA is unique. Also given the neural network ée, there exists edge for every pair of vertices Iy (x, # r) with weight (0(2, We describe the whole contraction process in the language of matrix computation. The expansion step is omitted here since it is the same as all the classic methods.
Step 1: Edge Pre-process. This step finds the minimum incoming edge for each vertex. For vertex Iy (1 و < n), we go through the j-th column vectors of the matrix A. Denote ny as the index for the minimum incoming edge for vertex Zyz
T = arg min Aij, for S 15150
(6)
4

---

Under review as a conference paper at ICLR 2023
where e(Z,,, x;2)) is the corresponding edge for vertex 2,. Then need subtract the value of the minimum incoming edge from all the incoming edges of every vertex. This is computed as the j-th column vector A. subtracting Ar,
A Ang Anyii for 1 ssisi
(7)
We denote the resulting graph with edges determined by {e(Øx, I4) 1=1 as F. We also use F to denote the corresponding adjacency matrix F E (0m1 with F( bT) 1 for 1 S j < n. Remark 1. All the incoming and outgoing edge weight become non-negative after the first "Edge Pre-process" operation: A(z,, A(z,, 2,) ming, AZ,, 2 0, for all Di EV.
Step 2: Termination Criterion. The algorithm terminates when graph F is acyclic. We decide F is acyclic by counting the number of weakly connected components (WCCs) in F. Specifically, graph is said to be weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. One WCC implies F is connected and acyclic so that F an arborescence. Otherwise, graph F contains at least one cycle.
Specifically, we compute binary matrix power series to get WCCs, since binary computation is more efficient than arithmetic operators, like decimal multiplication. Consider k-th matrix power:
F FxExx..XX
where (F F)
V A for 1 sijj S 15k5n
(8)
& times multiplicaaions
Operator "x" denotes binary matrix multiplication. "V" and "A" means element- logical-OR and logical-AND operators correspondingly. F = 1 and only if vertex I; can reach vertex zj with exactly i steps using edges in graph F. The reachability matrix for all pairs of vertices within n steps is:
8= F- V V
k=1
We need Olog n) iterations to compute the matrix (IVF)a-1 using the idea of divide and conquer. See detailed illustration in Appendix C.2. We find S implies vertex is on the cycle, as there a path in F' that vertex x; can reach itself. Thus, the termination criterion is Di= S O.
This is not the only way to determine graph connectivity, prior works invoke matrix inverse or DFS to detect the connectivity of graph F. We give an in-depth discussion in Appendix C.3. Matrix inverse cannot scale to large matrix due to numerical precision. DFS is efficient in serial (i.e., CPU) setting but is undesirable under parallel (i.e., GPU) settings. Therefore, we consider this simple matrix computation-baser alternative to find WCCs and determine termination.
WCCs Extraction. This is an intermediate step for the following shortest entering path. We need to partition the vertices V using matrix S (in Eq. 9). For i-th WCC, extract 1) C,, the set of vertices on the cycle. If x, is on the cycle, we can locate the rest using the i-th column and row vector, i.c., Siy 1 Sy; 1. 2) Hi, the set of vertices that be reached from the cycle but not the cycle, i.e. C. n H, = 0. 3) K,, the set of vertices that are non-reachable from the cycle.
C, (xyISi 1Λ Sy; = 1, for S j < n),
H, = [2y[Sh = 0 S,. = 1, for S j < n)
(10)
K, {zy]S. O Sy: 0, for 1 Ejin]
We obtain a list of vertices (CC,, H,, K.) that partition the graph. See Example for illustration.
Step 3: Lazy Shortest Entering Path. Fix i-th WCC, we compute the shortest entering path from vertices in K; to vertices in C via edge relaxation. Briefly speaking, we consider æ - 2e for every I& E K4, E C₁, that corresponds to the one-step path. Then try to relax the distance with 23 + I' + Te for Fn E H,, that are those two-step paths. The above edge relaxation step terminates once the distance cannot be relaxed anymore.
Specifically, denote adjacency matrices AK,C, C, to represent the connectivity between the set of vertices in K2 and C₁ Matrices As.c, and AH.H, are defined similarly. To avoid recursive edge relaxation, we use the same matrix power trick to compute the all- alir shortest distance for Tn. 2/, e H,. Let matrix D be the resulting matrix, we have: D An. AH, * A An, A,, with at
5

---

Under review as a conference paper at ICLR 2023
Lavá progressive contraction
a two-step path X4 - Jj
12
X
123
CLE
CLE
CLE
1
r
conservative
X1234
contraction
(a) contraction in our Lavá are more progressive than in CLE
(b) example of entering path in Lavá
progressively than the CLE method. (b) The shortest entering path picks the minimum one (in Eq. 11). The outside vertex K = {r} can either directly enter eycle C { or by intermediate vertex in H { v. Lavá method find the shortest entering path (r + x4 + ø1) and directly contracts {z1, Z2, 23. 24 } as T1234-
Figure 2: (a) The Lavá method contracts vertices
most log [4 min-plus products. In comparison, the classic Lovász method would use the whole matrix A instead of Aи., computing D = * A with at most log min-plus products. The min-plus product * is defined in Eq. 2.
Let 8 E I. be the shortest entering distance from K2 to C.. B, could be picked from: 1) one-step paths, 2k - Tes TK E Ki; Hie E C.. 2) two-step paths, Ih' - In + Tiss Th E H, 3) more than two-step paths, Ie + + J/h - Te. Note that the intermediate vertices are only picked from H; The x//, E H4. It can be summarized as:
AKK,C. Ak.,H, AH,C. (AK.H, AB.C.
Case 1: one-step paths
B. min
Case 2: two-step paths
(11)
Case more than two-step paths
Example and Fig. 5(b) illustrate this procedure.
Step 4: Contraction. Given 3,, we contract vertices on cycle Cj and those relevant vertices in Hj Denote the set of vertices to be contracted U4.
U = C, {xul min A(x1, S Br, H,} a.EC,
(12)
Contraction done by picking an arbitrary vertex in u E U, as the representative and using a mask vector to filter out the rest vertices in U.. The weight of incoming edges of vertex u; in the contracted graph G' would be updated as follow:
A(x',x.) + A(Zu, xe) 3, min A(x', u4) zx =.EU,,
(13)
All the remaining edges stay the same. Afterward, we iteratively apply the above 4 steps over graph G' until there are no cycles. We use Example to show the detailed steps of our Lavá method.
Example 1. Take Fig. 2 as an example. In Fig. 2(a), Lavá contracts are more progressive than the classic CLE method. The vector (in equation 6) for the most left figure is: x [2 1 2 3 -1], where T3 = 2 means the minimum incoming edge of vertex 22 is e(23, 22). "-1" implies root has no incoming edge. Also this most left graph has two WCCs: {r} and (21, 43, x4). Figure 2(b) computes the shortest entering path. According to Eq. 10, we have C C= (x1, x2). H = {ugg and K = (r). We consider two possible cases for this example: 1) those one-step paths (in Case 1), which are recorded in matrix Ak,c. 2) those two steps paths (in Case 2), like r + Ø3 + F1, which can be computed as AK, AH,C.
To(33, 6123, x2)
Ak.C = (0(r 0(1,))),,
AK,H * AH,C = [o(1,x3)
((r)
x1)
o( x2)
The min-plus operator * can be: (AK,H * AH,ch.1 = min (ø(r, x') + 6(0', (()',r1)) The shortest entering path is r + 24 F1, then the set of vertices to be contracted is {I1, 21).
Our proposed method described in matrix computations can be easily implemented using Numpy on CPU or Pytorch GPU, The matrix computation offers transparent protocol to compute GPU in parallel, without exactly manipulating every parallel processor on GPU devices. Furthermore, the matrix-based approach allows to conveniently process the output from the neural network. The method may also be extended to parallel computing but would require remodeling each step, we leave this discussion in Appendix B.

---

Under review as a conference paper at ICLR 2023
3.2 THEORETICAL INSIGHTS ON LAVÁ METHOD
Analysis on Rounds of Contractions. The main impacting factor for the running time of the proposed method is the number of contractions. Let Tn be the number of contractions for the graph with n vertices. In the CLE method, we consider that the graph can be contracted into smaller graphs of sizes {2,.... ................................ ... n 2} with equal probability. This simplified assumption may be different from the real-world setting but it can help us to reveal the averaged case of the CLE algorithm. We leave the study with more rigorous assumptions
graph contraction as future work. We have the following recursion: T, + n-3 Ei Tr. We obtain Tn (n) by solving this recursion. This implies, other than the rarely-happer worst case, CLE method on average takes (()) contractions under the equal probability assumption. Furthermore, we show in Theorem that Lavá takes at most (log n) contractions, which more efficient than the CLE method.
Theorem (Rounds of Contractions). In Lavá method, every directed cycle in C, contains at least two super vertices from the previous round. Lavá takes at most Olog n) contractions.
Sketch of Proof. We show there exists at least one super vertex in the cycle and we prove by contrac- tion that there exist at least two super vertices. Finally, we do induction the contraction rounds that give at most Ollog n) round of contractions for the whole procedure. Details in Appendix D. L
According to Lemma 1, by induction on the contraction rounds, we conclude that the Lavá method finds the MWA for graph G.
Lemma (Correctness). T arg minrer T represents the MWA T in the original graph G with weight (TT*). and = arg mingre7: T represents the MWA T in the contracted graph G' with weight (TT")), Then we have: =(T*))((TT)) + 3r
4 RELATED WORK
Finding MWA. Historically, Chu-Liu Edmonds (CLF) algorithms (Chu & Liu, 1965; Edmonds, 1967; Bock, 1971; Tarjan, 1977) along with its efficient data structures (Gabow et al., 1986; Mendel- son et al., 2004) are proposed to find the min-weight arborescence in the directed graph. But those data structures, like heap, are left be developed for GPUs Most recently, Böther al. (2022) benchmark all the implementations. Meanwhile, Humblet (1983) first proposed distributed com- puting scheme for CLE approach. Lovász (1985) proposed to solve the nested cycle contraction problem, but it asks for ((VV')) many processors for solving the intermediate shortest path problem parallel. Later, Lucas & Sackrowitz (1992); Amato ( (1993) reduced to the dependency on proces- sors. Fischer & Oshman (2021) adopted recent advances in distributed shortest path (Elkin, 2020) and extend the Lovász algorithm to distributed CONGEST network. Another line of work is based on constrained linear programming (LP) (Fischetti & Vigo, 1997; Király et al., 2020). However, LP needs exponential many constraints to enforce the output is an arborescence.
Learning Arborescence. inference-based learning can be mainly divided into two categories: dis- criminate max-margin learning and probabilistic perturb-and-MAP learning. The first category, including structured SVM (Tsochantaridis et al., 2004) and max-margin Markov network (Taskar et al., 2003), learns to minimize the gap between the output in the dataset and the best-predicted out- put. The second category focuses on differentiable structured learning for arborescence. Based on the perturbed optimizer theory (Berthet et al., 2020), they utilize perturbed inference for estimating the partition function (Niculae et al., 2018; Paulus al., 2020; Struminsky et al., 2021).
There also exists a diverse category of applications that involve arborescence. In graph-based de- pendency parsing, MWA denotes the best grammar tree of input sentences (McDonald et al., 2005; Ma & Hovy, 2017; Zhang et al., 2019). In causality learning, MWA represents the optimal causal additive trees (Jakobsen et al., 2022). In multiple human tracking, MWA denotes the best tracking association for the objects (Henschel et al., 2014). MWA is applied for finding the optimal vessel tree reconstruction (Zhang et al., 10.1). MWA is adopted to decompose the Markov chain in game theory (Newton& & Sandholm, 2021).

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENTAL ANALYSIS
We mainly show Lavá method serves as an efficient alternative for CLE method in the arborescence learning applications and synthesised dataset. Furthermore, we show Lavá uses much less contrac- tions on real-world and synthesis dataset and use less time to detecting WCCs, compute shortest entering distance when comparing to its baselines.
5.1 SYNTHETIC DENSE GRAPH
Empirical Running Time. The experiment settings are mentioned in Appendix G.2. Fig. 3(a) shows our Lavá takes much less number of contractions empirically. We observe that larger graphs requires more contraction steps than smaller graph in the CLE approach, which is time-consuming for the learning problem in large-scale data. We also notice Lavá and the classic Lovász takes same amount of contractions for the same input graph. We then compare the empirical running time of the proposed approach with existing basclines over synthetic datasets (in Fig. 3(b)). Then the same input is feed into all the competing methods and we measure the time of every algorithm need to get an optimal spanning arborescence. We repeat 100 times and use the averaged running time as the running comparison metric. As
see from Fig. 3(b), when the size of graph is smaller than 29, both of the methods attain comparable results. When graph size is larger than 2 the proposed Lavá takes significant less time than the classic CLEE method. Since CLE needs to build up and then reset all the necessary data structures, like Heap and disjoint set, when reading every input. While Lavá only needs process the matrix and run the binary and min-plus matrix multiplication.
(4)
(b)
[4)
5000
Rai. Tiue for WCC (wec)
Round Contractonns
CLE Tonn & Teraoo
Thonfoo))
200-
Lova
CLE
3000
-dat. Layonae (cpu xaxa -BMM (opu & apr)
Taraa DFS (sps.
Mad. Trweeer (rges)
Mot. Levress (spu)
BMM (spo)
10
BMM (spa)
150
Torjun S(epa)
2000
Prror
50
1000
10
10
10
10
10
10
10
Graph Size
Graph Size
Graph Size
Graph Sizee
Figure 3: (a) The round of contractions taken by the CLE method grows linearly with graph size while our Lavá method takes much less rounds of contractions. (b) Empirical running time com- parison between Lavá and CLE methods on synthetic datasets. Lavá takes significant less time to process the graph with vertices 2 21 (c) Our proposed BMM (in Eq. 9) and Tarjan-DFS com- putes the exact matrix S and attain zero numerical error. Matrix inverse (Mat. Inverse) cannot be applied to detect WCCs as the number of mismatch in the computed matrix S accumulates linearly with the graph size. (d) BMM executed on GPU takes much less time for detecting WCCs than all the competing approaches. Here, "BMM" and "Mat. Inverse" is abbreviation for binary matrix multiplication and matrix inverse correspondingly.
WCC's Implementation Analysis. Here we compare with one baseline (Kepner et al., 2016) that propose to use matrix inverse for detecting WCCs. The detailed process of matrix inverse for com- puting WCCs is in Appendix C.3. The error is defined as the number of mismatches between the computed matrix S. In Fig. 3(c), we observe the error for detecting WCCs made by the matrix in- verse approach (Mat. Inverse) becomes obvious when the graph is large while our method computes WCCs with no errors (as in Eq. 9). That's one major reason that we use binary matrix multiplication (BMM) to detect WCCs. In Fig. 3(d), we observe that BMM deployed on GPU attain the fastest approach for detecting WCCs than Tarjan's DFS algrorithm as well as Matrix inverse methods.
5.2 GRAPH- GRAPH-BASED DEPENDENCY PARSING
Dependency parsing considers the syntactic structure of sentence, which describes the grammatical relations among words (Jurafsky& & Martin, 2009). Words in sentences are formulated as vertices in graph, that [æ1..... ... Fn r) represents an input sentence with t being the dummy root. Let T denotes the ground-truth dependency tree for sentence æ. The annotation tree T is composed of n 1 edges, where every (Nz,, Uzz) E T is directed dependency relation from head word s.;
8

---

Under review as a conference paper at ICLR 2023
Table 1: Lavá takes less contractions and time compare with baselines on three dependency parsing datasets. Both of them predict the same perturbed MWA when estimating log Z (in Eq. 5). "ApxErr" stands for the approximation error from the estimated value by perturbed inference the exact value of log Zg. "#contract." denotes the averaged number of contractions; "Infer." means the averaged time to inference the MWA by each algorithm.
English GWT
Dutch - Alpino
French - GSD
Methods
ApxErr
#contract.
Infer.
ApxErr
#contract.
Inf. time
ApxErr
#ccontract
Infer.
C.F
0.14
13.6104
0.09p.12
0.18
17.17.9
0.
0.22
25.2
0. 191.21
Lovász
0.14
3.412
0.080.0 os
0.18
4.0
0.110
0.22
6.5g.7
0.17p.1a
Lavá (ours)
0.14
3.412
0. 05
0.18
4.0p.
0.29p.34
0.22
6.5o.7
0. 0.43a.27
to modifier word zj. The learning task is to learn a neural model given annotated training data (zi, Ti Di inference, we need to predict a dependency tree with optimal score for given input x'. We leave the detailed experiment configurations in Appendix G.I.
Using the same deep neural network, we ask every baselines to predict the MWA over three multilingual datasets for the dependency parsing task. The results collected in Table 1. In terms of the number of contractions, our Lavá and the classic Lovász uses less contractions than the CLE method. In terms of the empirical running time for inference MWA, our Lavá attain much less time compare with Lovász because it handle much smaller SSSP problem while Lovász need handle all-pair shortest path problem. Furthermore, our Lavá takes less time compare with the classic CLE approach. The Finally, we use the same perturbed adjacency matrix to estimate the log Zo terms. task in described in Appendix G.I. All the three methods return the same correct MWA and attain the same approximation eπror.
Comparison.
5.3
UNSUPERVISED PARSING ON LISTOPS
The ListOps task contains sequences of prefix arith- metic expressions, e.g., [MAX 29 [MIN 47
Emp. Time @
0.4
1. The arithmetic syntax for the input sequence in- duces arborescence with the first token being the root. We follow the same graph neural network as described in Paulus al. (2020). We benchmark the time of inferencing the MWA with the adja- cency matrix induced by the deep network, the for- ward propagation of the neural network as well as the backward gradient pass for the neural network. The results are collected in Fig. 4, where we can see the classic CLE becomes one major tine-consuming component while our Lavá can serves as efficient alternative to boost the training speed the network.
0.3
0.2
0.1
0.0
forward
backward
CLE
Lava
Figure 4: Empirical running time ListOps task. Our Lavá method takes less time than CLE method, which can be a better alterna- tive for the arborescence learning problem.
CONCLUSION
In this research, we investigate the inference problem when learning arborescence. We observe that the inference module (i.c., CLE method) that invoked at every step of gradient computation becomes time-consuming on the large-scale dataset. Therefore, we propose Lazy Lovász for effi- cient inference of the optimal output of the learning model. Compared with CLE method, it needs Ollog n. rounds of contractions instead of (n)) by the CLE approach. Compared with the classic Lovász, reduces the computational workload for the shortest entering path problem. In experi- ments, we show the empirical running time analysis on synthesized data. Furthermore, experiments on two real-world tasks: graph- based depdnency parsing and latent tree learning on ListOps. All the experiment results suggest that Lavá can efficiently find MWA for the network's output. This study implies for learning over large-scale arborescence learning problems, one could potentially give our Lazy Lovász try.
conduct

---

Under review as a conference paper at ICLR 2023
REFERENCES
Nancy M. Amato. Improved processor bounds for parallel algorithms for weighted directed graphs. Inf. Process. Lett., 45(3):447-152, 1993.
Ariful Azad and Aydin Buluç. LACC: A linear-algebraic algorithm for finding connected compo- nents distributed memory. In IPDPS, pp. 2-12. IEEE, 2019.
Jiri Barnat, Petr Bauch, Lubos Brim, and Milan Ceska. Computing strongly connected components in parallel on CUDA. In IPDPS, pp. 544-555. IEEE, 2011.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean- Phan--Pillipp Vert, and Francis R. Bach. Learning with differentiable pertubed optimizers. In NeurlPS, 2020.
Frederick Bock. An algorithm to construct a minimum directed spanning tree in directed network. Developments in operations research, pp. 29 44, 1971.
Maximilian Böther, Otto Kißig, and Christopher Weyand. Efficiently computing directed minimum spanning trees. CoRR, abs/2208.025499 2022.
Yeong-Jin Chu and Tseng-Hong Liu. On the shortest arborescence of a directed graph. Science Sinica, 14: 14:1396-1400, 1965.
Carrie-Catherneee de Marneffe, Christopher D. MaMning, Joakim Nivre, and Daniel Zeman. Universal dependencies. Comput. Linguistics, 47(2):255-300 2021.
Timothy Dozat and Christopher D. Manning. Deep biaffine attention for neural dependency parsing. In ICLR, 2017.
David Durfee, Rasmus Kyng, John Peebles, Anup Rao, and Sushant Sachdeva, Sampling random spanning trees faster than matrix multiplication. In STOC, pp- 730-742. ACM, 2017.
Jack Edmonds. Optimum branchings. J. Res. Nat. Bur. Standards, pp. 233-240, 1967.
Michael Elkin. Distributed exact shortest paths in sublinear time. ACM, 67(3):15:1 2020.
Oгr Fischer and Rotem Oshman. A distributed algorithm for directed minimum-weight spanning tree. Distributed Computing, pp. 1-31, 2021. 2021.
Matteo Fischetti and Danicle Vigo. A branch-and-cut algorithm for the resource-constrained minimum-weet weight arborescence problem. Networks, 29(1):55-6, 1997.
Harold N. Gabow, Zvi Galil, Thomas H. Spencer, and Robert Endre Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Comb, 102):109- 1986.
Roberto Henschel. Laura Leal-Taixé, and Bodo Rosenhahn. Efficient multiple people tracking using minimum cost arborescences. In GCPR, volume 8753 of Lecture Notes in Computer Science, pp- 265-276. Springer, 2014.
Pierre A. Humblet. A distributed algorithm for minimum weight directed spanning trees. 1EEE Trans. Commun. 31(6))756-72, 1983.
Priyank Jaini, Amur Ghose, and Pascal Poupart. Prometheus Directly learning acyclic directed graph structures for sum-product networks. In PGM, volume 72 of Proceedings of Machine Learning Research, pp. 181-192. PMLR, 2018.
Martin Emil Jakobsen, Rajen Dinesh Shah, Peter Bühlmann, and Jonas Peters. Structure learning for directed trees. Journal of Machine Learning Research, 23(159):1-97, 2022.
Dan Jurafsky and James H. Martin. Speech and language processing: introduction natural language processing, computational linguistics, and speech recognition, 2nd Edition. Prentice Hall, Pearson Education International, 2009.
10

---

Under review as a conference paper at ICLR 2023
Jeremy Kepner, Peter Aaltonen, David A. Bader, Aydin Buluç, Franz Franchetti, John R. Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, Scott McMillan, Carl Yang, John D. Owens, Marcin Zalewski, Timothy G. Mattson, and José E. Moreira. Mathe- matical foundations of the graphblas. In HPEC, pp. 1-9. IEFF, 2016.
Csaba Király, Zoltán Szigeti, and Shin-ichi Tanigawa. Packing of arborescences with matroid con- straints via matroid intersection. Math. Program. 181()):5-117, 2020.
Terry Koo, Amir Globerson, Xavier Carreras, and Michael Collins. Structured prediction models via the matrix-tree theorem. In EMNLP-CONLLL pp. 141-150. ACL,, 2007.
Bernhard Korte and Jens Vygen. Spanning Trees and Arborescences, pp. 133-157. Berlin, Heidel- berg, 2018.
László Lovász. Computing ears and branchings in parallel. FOCS, pp. 464 467. IEEE Computer Society, 1985.
Joan M Lucas and Marian Gunsher Sackrowitz. Efficient parallel algorithms for path problems in directed graphs. Algorithmica, 7(1):631-644) 1992.
Xuezhe Ma and Eduard H. Hovy. Neural probabilistic model for non-projective MST parsing. In IJCNLP, pp. 59-69, 69. Asian Federation of Natural Language Processing, 2017.
Ryan McDonald and Joakim Nivre. Analyzing and integrating dependency parsers. Comput. Linguistics, 37(1):197-230, 2011.
Ryan T. McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajic. Non-projective dependency parsing using spanning tree algorithms. HLT/EMNLP, pp. 523-530. The Association for Com- putational Linguistics, 2005.
Ran Mendelson, Mikkel Thorup, and Uri Zwick. Meldable RAM priority queues and minimum directed spanning trees. In SODA, pp. 40-48. SIAM, 2004.
Nikita Nangia and Samuel Bowman. ListOps: diagnostic dataset for latent tree learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Com- putational Linguistics: Student Research Workshop, pp. 92-99, New Orleans, Louisiana, USA, June 2018. Association for Computational Linguistics.
Maxim Naumov, Alysson Vrielink, and Michael Garland. Parallel depth-first search for directed acyclic graphs. In IA3@ SC, pp. 4:1-4:8. ACM, 2017.
Jonathan Newton and William H Sandholm. Stochastic dynamies and edmonds' algorithm. Journal of Dynamics and Games, 2021.
Vlad Niculae, André F. T. Martins, Mathieu Blondel, and Claire Cardie. Sparsemap: Differentiable sparse structured inference. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 3796-3805, 2018.
Max B. Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris Maddison. Gradient estimation with stochastic softmax tricks. In NeurIPS, 2020.
Kirill Struminsky, Artyom Gadetsky, Denis Rakitin, Danil Karpushkin, and Dmitry P. Vetrov. Lever- aging recursive gumbel-max trick for approximate inference in combinatorial spaces. In NeurIPS, pp. 10999-11011, 2021.
Robert Endre Tarjan. Finding optimum branchings. Networks, 7(1):25-35, 1977.
Ben Taskar, Carlos Guestrin, and Daphne Koller. Max-margin markov networks. In S. Thrun, L. Saul, and B. Schölkopf (eds.), Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003.
Jesper Larsson Träff. A note on (parallel) depth- and breadth- first search by are elimination. CoRR, foss/335..122.. 2013.
11

---

Under review as a conference paper at ICLR 2023
1. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support vector machine learning for interdependent and structured output spaces. In International Conference on Machine Learning (ICML). pp. 104-112, 2004.
Virginia Vassilevska Williams and Yinzhan Xu. Truly subeubic min-plus product for less structured matrices, with applications. In SODA, pp. 12-29. SIAM, 2020.
Yongzhe Zhang, Ariful Azad, and Aydin Buluę. Parallel algorithms for finding connected compo- nents using linear algebra. Parallel Distributed Comput., 144:14-23 2020.
Zhisong Zhang, Xuezhe Ma, and Eduard H. Hovy. An empirical investigation of structured output modeling for graph-based neural dependency parsing. In ACL. pp. 5592-5598. Association for Computational Linguistics, 2019.
Zhongwen Zhang, Dmitrii Marin, Maria Drangova, and Yuri Boykov. Confluent vessel trees with accurate bifurcations. In CVPR, pp. 9573-9582. Computer Vision Foundation IEEE, 2021.
12


Reviews:
[{"review_id": "mUEjqAL4uu", "reviewer": "Reviewer_sBZy", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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 research considers structured learning problems on arborescence from input graphs. Prior algorithms are CLE, Lovasz algorithms, and their variants. The authors find the general MPSP problem(sub-problem of the original problem) can be simplified when working with machine learning models. This is because the learning model predicts edge weights for all pairs of vertices and the graph is always complete. Through this observation, they can restrict the scope of the original problem and thus decrease the computation burden. Some other tricks are also mentioned for large-scale learning tasks. ", "summary_of_the_review": "This research considers structured learning problems on arborescence from input graphs. The authors find the general MPSP problem(sub-problem of the original problem) can be simplified when working with machine learning models, they mention that their algorithms are suitable for large-scale data, but none of theoretical analysis and numeric experiments are provided for their algorithms.", "strength_and_weaknesses": "Strength:\n1. They cleverly use the observation that edge weights for all pairs of vertices and the graph always complete in learning model, they modify the prior algorithms by restricting the scope, which can decrease the computation burden.\n2. Consider the algorithm in GPU setting, they change the traditional operation to GPU-friendly operation.\n\nWeaknesses:\n1. I am not sure that the contribution part \"Theoretically, we show that our Lava method takes O(log n) and CLE takes O(log n) round of contractions.\" whether the CLE takes O(log n) is typo.\n2. In numeric experiment, the  proposed algorithms seems not better than Lovasz algorithms, in some cases even worse than CLE. They claim that their algorithm is suitable for large-scale, but they actually do not test large-scale real dataset.\n3. The idea of the paper needed to be explained more clearly.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "33wCGsY4-0", "reviewer": "Reviewer_kqon", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 presents a new algorithm, referred to as the LAVA method, for evaluating the minimal weight arborescence of a directed graph which each of the edges carries a weight. It was shown in the literature that this question can be reduced to the Multi-Pair Shortest Path (MPSP) problem. The present paper investigates this problem through deep learning methods: it introduces a new algorithm based on neural networks, states a result about its time-complexity, and shows numerical results and comparisons with existing methods of the literature.", "summary_of_the_review": "The proposed algorithm certainly deserves attention, but, in my opinion, both the presentation and the theoretical and numerical results do not allow the publication of this article in its current form.", "strength_and_weaknesses": "The main strength of this paper is that it is rather complete: it introduces a new algorithm for a difficult problem and analyses it both theoretically and numerically. However, it suffers from two important flaws:\n- First, the announced complexity in O(log n) contractions for the MPSP problem puts the proposed algorithm at the same level as the Lovasz algorithm developed in 1985. (The authors also announce that their algorithm benefits from \"friendly and efficient\" CPU and GPU implementation, but they should be more precise on this point. In particular, they should precisely compare their contribution and Lovasz algorithm on this aspect.)\n- Second, the experimental analysis is mainly dedicated to the comparison with the Chu-Liu Edmonds method, introduced in 1965, which is theoretically worse because it needs O(n) contractions.\nFor these two reasons, the contribution is poorly situated with respect to the state of the art, both theoretically and numerically. The authors mention themselves more recent references than the two mentioned above, which should serve as baselines.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-iAzGD2Shyp", "reviewer": "Reviewer_5U91", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "The authors propose an improvement to an existing algorithm for the minimum weight arboresence problem in a special class of directed graphs.  The proposed improvements are verified experimentally on both real and synthetic problems.", "summary_of_the_review": "While the paper seems interesting overall and appears to describe a practical improvement for a class of problems, the presentation makes it difficult to read/verify its central claims.", "strength_and_weaknesses": "Strengths:  The paper purports a practical improvement that makes the minimum weight arboresence solvable at larger scales, which may be of sufficient interest to certain ML subcommunities.\n\nWeaknesses:  The exposition and presentation lack considerably when compared against typically accepted papers at ICLR.", "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": {}}]

Author rebuttal:

Decision: Reject