Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings
Authors: Dongxu Zhang
Michael Boratko
Cameron N Musco
Andrew McCallum
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph representation learning
geometric representation learning
directed graphs
cyclic graphs
transitivity

Abstract: Modeling directed graphs with differentiable representations is a fundamental requirement for performing machine learning on graph-structured data. Geometric embedding models (e.g. hyperbolic, cone, and box embeddings) excel at this task, exhibiting useful inductive biases for directed graphs. However, modeling directed graphs that both contain cycles and some element of transitivity, two properties common in real-world settings, is challenging. Box embeddings, which can be thought of as representing the graph as an intersection over some learned super-graphs, have a natural inductive bias toward modeling transitivity, but (as we prove) cannot model cycles. To this end, we propose binary code box embeddings, where a learned binary code selects a subset of graphs for intersection. We explore several variants, including global binary codes (amounting to a union over intersections) and per-vertex binary codes (allowing greater flexibility) as well as methods of regularization. Theoretical and empirical results show that the proposed models not only preserve a useful inductive bias of transitivity but also have sufficient representational capacity to model arbitrary graphs, including graphs with cycles.

Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings
Dongxu Zhang, Michael Boratko, Cameron Musco, Andrew McCallum University of Massachusetts Amherst (dongxuzhang, mboratko, cmusco, mccallum)@cs @cs. umass. edu
Abstract
Modeling directed graphs with differentiable representations fundamental requirement for performing machine learning on graph-structured data. Geometric embedding models (e.g. hyperbolic, cone, and box embeddings) excel at this task, exhibiting useful inductive biases for directed graphs. However, modeling directed graphs that both contain cycles and some element of transitivity, two properties common in real-world settings, is challenging. Box embeddings, which be thought of as representing the graph as an intersection over some learned super- graphs, have natural inductive bias toward modeling transitivity, but (as prove) cannot model cycles. To this end, we propose binary code box embeddings, where learned binary code selects subset of graphs for intersection. We explore several variants, including global binary codes (amounting to a union over intersections) and per-vertex binary codes (allowing greater flexibility) well methods of regularization. Theoretical and empirical results show that the proposed models not only preserve a useful inductive bias of transitivity but also have sufficient representational capacity to model arbitrary graphs, including graphs with cycles.
1 Introduction
Many real-world networks, such as social media interactions, paper citations, web links, and ontolo- gies, naturally represented directed graphs [14] (). Two common properties of these graphs are transitivity and cyclicity. A cycle in a directed graph is directed path starting from a vertex and traversing back itself. For example, "organic matter" "worm" - "fish" - "cat" - "organic matter" is a food cycle. Transitivity in a directed graph is the property that if there exists directed path from v, then edge (u, v) also exists. For example, if "cat is mammal" and "mammal is animal" are true, "cat is animal" is true.
In the age of deep learning, it is necessary to determine way to capture the salient information from a graph via some differentiable parameterization. To this end, various graph embedding methods have been proposed. Some work, such as Deep Walk [17] and Node2vec [8] maps each vertex to a vector in Euclidean space. These methods perform a low-rank factorization of the adjacency matrix or the graph Laplacian (18) and are designed to model undirected graphs. These can be extended to capture edge asymmetry in directed graphs by using two separate representations one for source, and one for target- either unconstrained or related with one another via some function. It has been proven that using a dot product or distance-based energy function, separate source and target vectors can encode any graph (given sufficient dimension) M. including graphs with cycles. When the source and target representations live in separate spaces, however, relationships which result from following directed paths (c.g.. transitivity) are harder encode. For example, given edge (i,j) and (j. k), vector model can learn to make - t, 2 and |s, - tul2 zu O, where Sy are source vectors and
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

Input
Graph Decomposition
B
B
C
B
Interval Representations
Binary Codes
E
B
A
Box Subspaces
GBC-Box
Output
Figure 1: Demonstration of using GBC-Bot represent a directed graph. Firstly, the model learns d(= 3) interval embeddings, each representing directed graph. Then, there are k(= 2) binary code vectors, each of which selects a subset of the interval embeddings combine into a box embedding (in this case, 2-D and 1-D) subspace. In each subspace, box embeddings can represent DAG as shown in the bottom the diagram. Finally, the target graph can be reconstructed as a union over DAGs from all subspaces.
Lys la are target vectors. However, the condition |s; - 1x/2 Ri 0 which would represent the transitive edge (i, k) has no encouragement to hold, the source and target spaces are entirely disconnected.
Transitivity cannot be trivially injected via symbolic rules, e.g., adding all transitive edges a directed graph. This is because most real world edges are not strictly transitive: the degree of transitivity is "soft", and may hold locally but not globally,
vary for different edge types sets of nodes in the
graph. Some work, such as HOPE [[5] and APP 29 attempts to capture transitivity by factorizing high-order proximity signals instead of the graph Laplacian. This branch of work is limited by the imperfection of high-order proximity scores (for example, these scores do not model cycles well). ATP resolves this by breaking cycles in the graph, accepting loss of graph information.
An alternative approach to represent nodes in an embedding space with additional geometric structure. For example, hyperbolic embeddings leverage the negative curvature of hyperbolic space to provably model trees with less distortion [22] Region- based embeddings such as box embeddings [28]
m and hyperbolic entailment cones
have natural bias toward modeling transitivity. These region-based embeddings can capture the transitivity in a directed graph without relying on high-order proximity scores, using only the original adjacency matrix as supervision. Previous work 2 proved that box embeddings can model any directed acyelic graph (DAG). A natural question, therefore, whether box embeddings can capture graphs with cycles. we will show in Section 2 this is not the case.
In this work, propose binary code box embeddings a generalization of box embeddings to represent arbitrary directed graphs. The model motivated by the intuition that a given directed graph can be regarded union of multiple sub-graphs, where each sub-graph is acyclic, and therefore can be represented using boxes. We introduce the concept of a "binary code" which selects these sub-gra nub-graphs.
Our contributions lie in three folds:
We propose global (GBC-BoX) and per-vertex (VBC-BoX) binary code box models, generalization of box embeddings capable of representing arbitrary directed graphs.
OOu code is available at htthtttps//gtthii httpps///ggtub..oo/////////////e htt.g/twwwwoo..eeeee/eeeeee/etta

---

We analyze theoretically the limitations of existing box embedding models when represent- ing cycles. We also prove that, given sufficient dimensions, both binary code box models can model any directed graph. This establishes that, in theory, the representational capacity of these models is not limited.
We evaluate our model on graph reconstruction and link prediction tasks with various synthetic graphs and real world graphs, and observe that our proposed methods perform the best in almost all scenarios, especially when graph has strong cyclicity and transitivity.
2 Background
Given a simple directed graph G with vertices and edges (V, E), we seek represent the vertices using some mapping Φ V + Rd, and energy function F: V x V IR+ providing score (based on o and, perhaps, some hyperparameters A) which is interpreted as the negative log probability of weighted
edge existence, E(u,, v; Φ, A) - log P((u, v) E). We can view these probabilities graph, however in practice is often necessary to make hard decision on edge existence, which is done by choosing a (global) threshold T and binarizing the output. We denote the energy function for a particular model M with a subscript, i.e. EM. and say that M is capable of modeling graph G (V,E) if there is some é, X, and 7 such that & {u, v) (u, iz A) < T).
2.1 Boxicity
Let be the set of closed and bounded intervals in R. An interval graph is an undirected graph G = E) such that there exists mapping V > I for which
{u, v) E E = ((u) n n *
More generally, we can consider Bd, the set of d-dimensional "boxes", which are Cartesian products of intervals,
II [ = [oT.2:]] 1mo
( xt] CR²
where x; and 2t are min and max coordinates in dimension i. As defined by Roberts 200. the boxicity of an undirected graph G' is the smallest dimension d such that there exists a mapping p V 8d for which {u, v} E & if and only if (uu) p(e) # 0. Equivalently, the boxicity the minimal number of interval graphs whose intersection is G.
2.2 Box Embeddings
28 provide way of using boxes to represent directed graphs by defining asymmetric energy function based on box volumes, and subsequent work has introduced various improvements and extensions of this idea Dasgupta et al. [. Boratko et al. [2]. In this section we will define the energy function of box embedding models under a common framework, in preparation to motivate extension to binary code box embeddings.
Vilnis et al.
The energy function for all box embedding variants has the form
d
E(u, un Φ A) - log II F (((())
where ((u) are the parameters associated with node u in dimension i and F(c(u), o(v);; A) E [0. 1] is a per-dimension score representing the probability of edge existence. The model originally defined Vilnis al. [X represented each node using box, as in Q The per-dimension parameters are the endpoints of an interval, Φ(u); (Ø(u), . (l and the score function is defined as || +1 n ,l
,y+) - max(x= ,,)))))))))
TBoxc[2= x Iy 1)
max(y + y 0)
'A simple directed graph is one without multiple edges self-loops. i.. the adjacency matrix contains only Os and 1s, with Os the diagonal. We also synthetically remove self- from the graph modeled by the learned representations.
As in boxicity, we can interpret these box embedding models as representing graph as intersection of interval graphs, one for each dimension.
3

---

This encourages the box for given vertex to contain (or overlap highly with) the boxes for it's children. Boxes which are disjoint or contained one another can present problems for training. however. Dasgupta et al. 3 addressed this by modeling the endpoints of intervals using Gumbel random variables. The per-dimension score can be written as
Fa-Box((2 ,,),,,,),,00 (v ,U));(T LSE, (- L.S. (-xt, -t) (x , ,V)),0)
(3)
Ly 00
where LSE, denotes the following continuous extension of LogSumExp with temperature 2 0:
LSEx = (llo Σ max x
if f 0, if t= 0.
(4)
In practice, the temperatures т and v are tuned separately as global hyperparameters, however when they are equal the parameters x y (resp, x y be interpreted as the mean of the GumbelMax (resp. GumbelMin) random variables with scale V/ = T, and FG-Box approximates a ratio of expected box volumes. Note that for any (x x xt)), (y v IR² FG Box is continuous with respect to т, V E Rz0, and Fu-Box ((x xxxx)) (y );0,0) = FBOX ",,11,11 (y, ,1+)).
Boratko et al. 2 takes this one step further, using mapping which learns 4 parameters per dimension: ((u), = (d(u), ((u)+ (())..r (.))..)) The per-dimension score function is then defined as
Fr Box ((x o Tr, To), (y ,yt Ur: vv)) = FG (oxBox(( ,xx) (y (=
t.
tu Wh. )). (5)
2
3. Existing Representational Capacity and Limitations
3.1 Representational Capacity
We would like know each model's representational capacity (the set of graphs capable of being modeled) as well as how this may change depending on hyperparameter settings. It was proven model any DAG, and of course since T-Box is equivalent to in Boratko et al. that Box (()),,= = 0 this also holds for T- T-Box. As defined in Section we can also
Box when ((u);,r say that G-Box is capable of modeling any DAG, since it is equivalent Box when we set the temperature hyperparameters to zero (i.e. r = V = 0), however this practically quite different - the temperatures are trainable in T-Box, and would never be
in order to avoid the training difficulties of Box. Hence, the existing proof of representational capacity in 2 says very little about the practical representational capacity of G-Box Thankfully, more can be proven.
Theorem 1. Given a threshold T, temperature hyperparameters T, U, there exists and bijection v on the set of parumeterizations (V R2d] such that for all u, V,
EG- u (0)), (T, v)) <T
EBOx v; <T
In other words, for any temperature hyperparameters, G-BOX can represent any graph representable by Box. For the proof, see Appendix Proposition 3 in Boratko et al. 2 states that any DAG can be modeled by Box in O(A + 2) log [I) dimensions with O(D(A 2) log" (V]) bits of precision per box, where D S [V] is the depth of G and A the maximum degree. Combining this with Theorem we have the following:
Corollary 2. Let G be any DAG, Given any T, R2o. there exists a mapping Φ - 2d and threshold T > 0 such that Eg-Box (u, u; S. (T, < T if and only if (u, u) E E, where ((A + 2) log [V]), and A the maximum degree in
In other words, for any setting of temperature hyperparamters, G-Box can model any DAG.
'In Dasgupta et al. 4 they interpret ofu)² the "location" parameters of the distribution, resulting in slightly different form of the score function, however show in Appendix our 3 leads an equivalent model.
'This limitation was acknowledged in Boratko et al. just before Section 4.3 as part of the motivation for the trainable temperatures of T- T-Bo..

---

3.2 Limitation on Modeling Cycles
In this section, we point out that G-Box cannot model any graph containing a (directed) chordless cycle, which is a cycle such that no two vertices are connected by an edge which does not belong to the cycle.
Theorem 3. If E is such that E(u, v) - E(v, u) g(u) - glv) for some function V - IR then it cannot model any graph containing a chordless cycle with more than 2 nodes.
Proof. Suppose the vertices 1,2, .... comprise chordless cycle, the edges of which are D {(1, 2), (2, (2.3).... (N N),, (N, 1)). Suppose further that we can model the graph containing this cycle using energy E and threshold T. In particular, we have E(u, < 'I' and E(v, u) 2 T for
(u, v) E D. This implies that g(u) g(v) = E(u, v) - E(u, u) < O, and thus g(u) < g(v) for each
(u, D. Hence 9()) < g(2) < g(N) 9(1), which is contradiction.
Corollary 4. G-Box cannot model any graph containing a chordless cycle on more than nodes.
Proof. Theorem 3 applies to EG-Box with g(u) = - log II= (&E - <(u), 0).
is possible to avoid the contradiction in Theorem 3 by the introduction one reverse edge, and in this case we observe that it is theoretically possible for G-Box represent graph.
Proposition 1. IfG is graph which is the union of a chordless cycle and one reverse edge, G-Box can model G in 2 dimensions.
The proof of this statement is contained Appendix C
Method
In this section, we will introduce the binary code box embedding concept, which includes family of models whose shared feature is the use of learned binary codes to select subsets of dimensions. Two we will focus in particular include GBC-BoX, which uses "global" binary code vectors, and VBC-BoX, which uses ver-vertex binary code vectors. The following topics will be covered: the motivation for binary codes, the definition of GBC-Bos Box and VBC- their representational capacity to model arbitrary directed graphs, our learning objectives and regularization, the models' inductive biases and strengths, and some discussion about their limitations and alternative variants.
4.1 Motivation
The idea of binary code boxes is allow more flexibility than simply taking an intersection over interval graphs, as captured by boxicity (see Section 2.J). Recall, in the undirected case, the boxicity of a graph G = (V,E) was equivalent to the smallest number such that for some set of interval graphs S {G, (V, we have & =
Eu = VF:(U,F) eu.
There are various ways to increase the flexibility of this representation. For example, we could consider allowing a union over intersections by specifying & subsets of S, {S.) for which E O(V.FIEs F.i.e
[u E
Ei :FVF (V,F) S;,
(u E.F
(6)
To allow for even greater flexibility, we could allow each vertex select a subset of graphs to intersect. Formally, we allow the specification of a function db V + 2 which assigns a subset of interval graphs each vertex, for which
{u, E -
(F:FV.F) E (l)) (u.
(7)
For the undirected case the advantage is minimal. Increasing the flexibility in these ways may allow us to represent an undirected graph in smaller dimension (or, equivalently, using a smaller number of interval graphs), however as mentioned previously we know any undirected graph can be represented as an intersection of interval graphs. For directed graphs, however, this not the case, and (as we prove in Section this generalization allows for any directed graph to be represented.
5

---

4.2 Definition
In order capture the idea of "union of intersections" specified in we consider learning "binary code" vectors by [0, 1] Each binary vector corresponds to a selection of which dimensions to include if the hthh component is 0 the scores for edges in this dimension should be ignored, and if it is 1 they should be included. For convenience, we will represent these as the columns of d matrix B E [0, _ The energy function in this case is
BoBC-Box (u, is (T, = min
log II Fa-Box (()) i=1
(8)
[E(2....kk
In order capture the notion of per-vertex subset selection in we learn parameters per dimension, which we denote as ((u); = (Ø(u), (()),
x R x [0, 1]. The binary code { indicates whether this dimension should be taken into account when calculating the probability of edge existence for edges involving this node - if is O, the dimension should be ignored, and if it is 1 may be included. We incorporate this the level of the per-dimension score function as follows:
E
FVBC Box "0=,,ttx))0
vt )) v)) FG Box (a=x(((" a0 (y bbt): (T,"))=²0*
Using the product in the exponent is a relaxation of the intersection (b)) n (b()) from When computing the probability of edge (u, v),, the binary codes can learn to ignore certain dimensions by making p or o(v); equal to O.
In the following, we point two perspectives which provide further intuition behind these models:
Generalization: Both GBC-BoX and VBC-BoS Box are a generalization of G-Box, as the energy function is equivalent when all binary codes are in which case all dimensions are used for volume calculation. As we will show in Section 4.3 these models are strictly more expressive, as when some binary codes are less than 1 these models can represent more complex graphs
Projection: For GBC-BoX, if Br, E 10 we can think of this defining set of projections {P where P3 projects the boxes parameterized by ó into the Σ Br, dimensional subspace where B. = 1. Similarly, for VBC-BoX, if o(u); E {0, } we can think of this determining the dimensions D. == {i : Φ(u); t} which the box will be projected in. Given an edge (u, v), we project into dimensions D, n D. before determining the edge existence.
4.3 Representational Capacity
The energy functions for GBC-Box and VBC-Box were constructed such that Theorem 3 would not apply, thus making it possible that they may be capable of representing some graphs with cycles. In this section, we prove that both can model any directed graph.
Theorem 5. Given a directed graph G = E) and any 2 O and k 2 2, there exists a threshold T > O, parameters & : V + 2d, and binary codes B E [0, 1]axk for which
EGRC-BOX (u, vz (Ø) B), (T, <T
(u,u) E
Proof. Given a directed graph G E), let ( (<, V) be an arbitrary strict total order on the vertices. Then define subgraphs D1 = EV) and D2 (V, E2) where &, [u, v) v} & and E, {u, v) > w} NE Observe that Dj and D2 are directed acyclic graphs, and thus Corollary implies that for j E (1,2) 2} there exists a threshold T,, dimension d, O(A 2) log (1), and mapping dj + 2ddd such that
Eg-Box o, (T, < T)
(u, E Eg.
Let = di + d2. T = min(Ti, T2). and define Φ : - 2d and B E [0, 1j k as follows:
E (1, (1.....ddd d ((u)= = (1) B = T
T
B = 0,
Vi (d, + 1, .......... dl + d2), ((u); oz(u)
B 0, B T.
Then we have EGBC-Box (u, v; (Ø. B), (T, v)) = minze(1.2) Σ BoG-BoX v; Hi (T, v)) which com- pletes the proof with k 2. and therefore implies the result for all A > 2.

---

While motivated by similar idea, note that VBC-BoX is not generalization of GBC-BoX, and thus an independent proof of representational capacity is required.
Theorem Given a directed graph G (V,&) and any T, V 2 0, there exists threshold T > 0 and parameters Ø V 2d [0, 10 for which EvEC-Box (u, Ø, (T, I if and only if (u, v) E E.
Proof. Given graph G = (V.E) let H = (fu, o} V. v). We will construct a VBC- Box model in d H| dimensions. For convenience, index the dimensions using h H. Then let d(u) = 1 if u E h, and O otherwise. This means when evaluating the edge (u, v) or (u, u) we simply need to compare in the 1-d space obtained by projecting the boxes dimension h = (u, and furthermore that this dimension will not be used when considering any other edges. Any directed graph nodes be embedded using boxes in 1-dimension (observable by direct construction), which completes the proof.
While Theorem and Theorem are helpful in establishing that, unlike all prior box embedding models and many other geometric embeddings, GBC-BoX and VBC-BoX are capable of modeling any directed graph, the implied dimensionality bounds are far from optimal. general, both models tend to require fewer dimensions than alternatives, which we analyze theoretically in Appendix D and observe empirically in Section
4.4 Learning
We fit geometric embeddings by optimizing a binary cross entropy objective. Given some edges in training set T, the loss defined as
LBCE(d;A)
E (W,)ET
E(u,,; (W",H"))N((.))))
Σ
log e
(10)
where Nu,, v) is the set of negative samples for each positive edge (u, v) within one batch. We sample minibatches of positive edges in T, and for each positive edge we sample 32 edges not in T by randomly corrupting either the source target node. We also use a adversaverallal negative weight, as described [26].
Limitations and Regularization
There are few limitations of Binary Code Box Embeddings: 1) Transitivity and Flexibility In order to model cycles with separate sub-spaces, the inductive bias of asymmetric transitivity might be weakened. 2) Inefficiency of Parameterization For VBC-BoX, the number of parameters is increased by 50% compared with G-Box model equal dimension. In addition, during inference, large portion of box co-ordinates are "dead" when binary codes near zero. Here, introduce regularization method and a tunable binary code size to resolve these concerns.
Regularization We can regularize the sparsity of binary codes to penalize dimension drop-off using the lasso with a regularization weight wr, leading to a loss function I. I.BCE + w/|l1 Bllet.
Restricted Binary Code Size We can constrain the number of trainable binary codes to the last dhin dimensions, setting the first - dhin dimensions 1.
Both w, and dhin can provide a handle on mitigating issues mentioned above. One can increase w, or decrease dain to preserve more transitivity and make full use of the model's parameters.
5
Experiments
5.1 Graph Reconstruction
While GBC-Box and VBC-BOX provably model any directed graph, the extent to which they can be trained to do so via gradient descent is another matter. In this section, we compare the reconstruction performance of various geometric embedding methods number of synthetic graphs, including simple directed cycles, trees and scale-free networks.
Baselines. We compare our model with different basclines:
7

---

We implement a vector baseline where each node is parameterized by a source and target vector, and the energy function is measured by E(u, v) = log a (((2) source ((v) (arges) * indicates it uses source and target vectors.
Vector*:
Lorentzian: has been shown that hyperbolic space can embed undirected trees with arbitrarily low distortion [22] therefore we also compare with the baseline of squared Lorentzian distance on the hyperboloid [10 21.
Hyperbolic Entailment Cones: Ganea et al. 7 model vertices cones in hyperbolic space, combining the bias of hyperbolic space to represent tree-like graphs with the transitivity bias of region-bacee based representations.
Box Models: We also compare with G-Box and T-Box as defined in Section 2.2
We use Bayesian hyperparameter tuning based on the optimal Fl score for reconstruction.
Capacity over Cycles. We evaluate each model's capacity to represent cycles, where simple directed cycles are generated with an increasing number of vertices (VV = 2 21, 2 21 In addition, we analyze the effect of adding one reverse edge to the cycle, which conventional box embedding models can represent. Results are shown in Table T For fair comparison, all methods use 12 parameters per vertex 6 VBC-BOX shows the best reconstruction performance. Most other geometric baselines cannot model cycles. Surprisingly, VBC-BoX even outperforms the Vector baseline when [V] = =/2, indicating our model's high expressivity and surprising case of training. Results also show that, in concordance with Proposition [ G-Box can model a cycle containing a reverse edge when [V] is small, though it may struggle to do so. We also see that T-BOX can model certain cycles when [V] is small, which is not contradiction of Theorem as the energy function for T-BOX does not satisfy the premise.
Table I: Reconstruction performance (Fl score) on directed cycles. All embeddings use 12 parameters per vertex. Different columns show the results as we increase the number of vertices in the cycle. Methods
Simple cycle
One bidirectional
edge
|
2
2
2
2
2
24
2
2
Vector*
1.0
1.0
1.0
0.676
1.0
1.0
1.0
0.666
Lorentzian
0.857
0.75
0.679
0.671
1.0
0.839
0.693
0.665
Hyperbolic Entailment Cones
0.75
0.667
0.662
0.635
0.75
0.692
0.654
0.645
G-Box
0.857
0.762
0.695
0.648
1.0
0.914
0.689
0.630
T-BoX
1.0
1.0
0.996
0,685
1.0
1.0
0.992
0.659
GBC-BOX
1.0
1.0
0.992
0.957
1.0
1.0
0.993
0.967
VBC-BOX (doin
1.0
1.0
1.0
0.973
1.0
1.0
1.0
0.978
Capacity over Trees. It is known that box models have inductive bias which makes them more suited to capturing asymmetric transitivity, whereas hyperbolic space is particularly suitable for undirected trees. In this experiment, we evaluate whether binary code models maintain the inductive bias of box embeddings. We generated four balanced (out-)trees, each with 2 vertices and branching factor of [2, 3. 5, 10). We also generated another four graphs with full transitive closures. We compare each method with 12, 24 and 48 parameters per vertex. For each setting, we average the results over the four trees, and present the results in Table 2 As expected, G-Box performs the best on transitively closed trees, while the Lorentzian model performs well on balanced trees. It is shown that GBC-BoT BBx performs equally well as G-BoX on transitively closed trees, while the performance of VBC-BoX is slightly lower. In contrast, the latter performs similarly or better than the former on the transitive reduction of trees. This suggests that more transitive bias is preserved GBC-BoX, while per vertex binary codes provide more representational flexibility. In addition, these results confirm trend observed in [2], where binary code models and and T- T-Box outperform the Lorentzian model on balanced trees when dimension size is increased, and the performance of other geometric-based embeddings are not capable overfitting even as dimension increases.
Capacity over Random Graphs. Finally, we conduct experiments on scale-free networks, simulation to real-world graphs, where the edge distribution follows preferential attachment. order to analyze how the cyclicity of graphs affects each model's performance, we randomly sampled
$12 is the least common multiple of 2, 3, 4 which are the minimum number of parameters per node for G- Box. B-BoX and VBC-Bo- Box
8

---

Table 2: Average reconstruction performance (Fl score) on balanced trees with [V] 213 and branching factors of 2, 5, 10 using 12, 24, and 48 parameters per vertex.
Methods
Balanced tree
w. transitive closures
Parameters / vertex
24
48
12
24
48
Vector
0,453
0.992
1.0
0.863
0.999
1.0
Lorentzian
0.929
0.935
0.951
0.975
0.979
0.995
Hyperbolic Entailment Cones
0.828
0,834
0.838
0,977
0.982
0.987
G-Box
0.832
0.830
0.842
1.0
1.0
1.0
T-Box
0.800
0.957
1.0
0.952
0.997
1.0
GBC- BOX
0,901
0.961
0.983
1.0
1.0
1.0
VBC-BoX BOx (dhen = d)
0.866
0.994
1.0
0.987
0.999
1.0
nearly three-thousand graphs using wide range of parameters used for graph generation. Then we split the generated graphs into five bins by our proposed measure cyclicity: The proportion of vertices in given graph involved in least one cycle. In order to analyze models' effectiveness of modeling cycles instead of the density of graphs, we randomly sample 5 graphs from each bin where the average degree is in the range between and 4. Results are shown in Figure Z From the chart, we can see that our proposed model outperforms standard G-Box in all scenarios. Moreover, the gap in performance more significant when eyclicity high. Figure 2 also clearly shows that VBC-Bot Box provides more representational capacity overall, while GBC- Box is less expressive in modeling cyclic graphs.
24 Parameters/ Vertex
48 Parameters / Vertex
96 Parameters / Vertex
1.0
1.0
1.0
0.8
0.2
0.8
0.6-
0.6
0.6
0.4
Box
GBC--oo
VBC Box
(00.0.02) (0.2.0.4)
(0.6.0.3) (6.8.1.0) Qyclicty
200.002 (0.2.044 (0.4.66) (0.8..0)
(00.322) 202.0.44 Cydliity
6.3.8) (0.8.1.0)
Figure 2: Reconstruction performance on Scale-free networks with |V| = 223 We plot the Fl scores for G-Box, GBC-Box and VBC-BoX using 24, 48, 96 parameters per vertex.
5.2 Link Prediction
Finally, we apply our binary code box models on link prediction tasks to evaluate the models' generalization ability. We evaluate on the following real world graphs: Google hyperlink network, Epinions trust network, CORA citation network, Twitter network, and DREAM5 gene regulatory networks. For more data statistics, see Appendix E During training, all hyperparameters are tuned via 10% cross-validation and the test set results are averaged over 10 models of different random seeds, which were trained on the full training set with the best prper-parameters found during cross- validation. We also tune the weight of the sparsity regularization w, for all BC-Box models (see Section
In Table we follow 30 and compare with several baselines including vector-based baselines such as DeepWalk 17 LINE 27 node2vec [. HOPE (5),, APP 29 DGGAN KC and our model with separate source and target parameters, as well
own implementation of a vector- reaion-based baselines such G-Box 3 and T-Box 2. Models
evaluated using the Area Under ROC Curve (AUC). For fair comparison, we follow B0 and use 128 parameters per vertex for all our models. Results show that our binary code box models out-perform other baselines in most cases. Furthermore, there is an clear trend that VBC-BoX performs the best when graphs are highly cyclic (on the left side of the table), whereas VBC-Box with fewer binary code dimensions and GBC- B-o model start to perform better when graphs are less cyclic. In the case where a graph mostly acyclic (on the right side of the table), G-Box performs equally well.
We also observe that box geometry is superior than vector-based models in all scenarios, even graphs are less transitive, or have lot of cycles, showing the strength of box geometry in modeling

---

directed graphs. In addition, we also compare with another recent work from Sim et al. 23 over DREAM5 datasets. where observe that box embedding models out-performs their baselines significantly in most cases. (On In Silico dataset, our model has an average precision of 68.8%, out-performs their best result 61.0%.) Detailed results are in Appendix
Table 3: Link prediction real-world graphs We use AUC evaluation metric. Vector-based methods (upper), and box embedding variants (bottom). Most vector baseline results are provided by 30 We evaluated over two negative sampling strategies for testing, unif.: uniformly sampled negatives; corr: randomly corrupting source or target node in each positive edge the test set. All methods use 128 parameters per vertex. Bold numbers perform the best, and underscored numbers perform the best in all non-box models
Methods
Google
Epinions
CORA
Twitter
Cyclicity =
0.96
0.88
0.23
0.01
Transitivity
0.40
0.09
0.22
0.01
unif.
unif.
corr.
unif.
unif.
Walk
30
83.6
76.6
84.9
50.4
LINE-1
R0
89.7
78.8
84.7
53.1
node2vee
R0
84.3
89.7
85.3
50.6
HOPE*
30
87.5
79.6
77.6
98.0
APP* 30
92.1
70.5
76.6
71.6
DGGAN 30
92.3
96.1
85.1
99.7
Vector(Ours)
94.0
94.2
93.0
88.9
78.9
76.7
99.8
84.1
G-BoX
99.2
98.2
95.1
90.0
93.9
89.6
99.8
86.3
T-BoX
95.8
96.4
89.6
87.3
79.6
84.4
GBC- BOX
99.0
98.3
96.8
92.7
92.7
90.3
99.9
86.2
VBC-BoT Box (0 < dein < d)
99.3
98.3
97.6
92.2
94.1
89.7
99.9
86.1
VBC-Bo Box (doin d)
99.5
98.6
98.0
92.4
93.2
88.8
99.8
85.7
6 Conclusion
In this paper, we introduced binary code box embeddings, a generalized box embedding method to model directed graphs. We provide both theoretical and empirical results showing the capacity of our model for modeling directed graphs. We demonstrated that this model can maintain useful bias of transitivity while also modeling graphs with cycles.
Acknowledgements
This work supported in part by the Center for Data Science and the Center for Intelligent Information Retrieval, and in part by the National Science Foundation under Grants No. 2106391 and No. 1763618, and in part by IBM Research Al through AI Horizons Network, and in part by the Chan Zuckerberg Initiative under the project "Scientific K Knowledge Base Construction", and the Office of Naval Research (ONR) via Contract No. N66001 1924032 under Subaward No. 123875727 from the University of Southern California. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Some of the work reported here was performed using high performance computing equipment obtained under grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor.
References
[1] Robi Bhattacharjee and Sanjoy Dasgupta. What relations are reliably embeddable in euclidean space? Conference Algorithmic Learning Theory (ALT), 2020.
10

---

[2] Michael Boratko, Dongxu Zhang, Nicholas Monath, Luke Vilnis, Kenneth Clarkson, and Andrew McCallum. Capacity and bias of learned geometric embeddings for directed graphs. Advances in Neural Information Processing Systems, 34, 2021.
[3] Shib Sankar Dasgupta, Michael Boratko, Dongxu Zhang, Luke Vilnis, Xiang Lorraine Li, and Andrew McCallum. Improving local identifiability in probabilistic box embeddings. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[4] Shib Sankar Dasgupta, Xiang Lorraine Li, Michael Boratko, Dongxu Zhang, and Andrew McCallum. Box-to-box transformations for modeling joint hierarchies. In Proceedings of the 6th Workshop on Representation Learning for NLP (RepLANLP-20211 pages 277-288, 2021.
[5] Munmun De Choudhury. Yu-Ru Lin, Hari Sundaram, Kasim Selcuk Candan, Lexing Xie, and Aisling Kelliher. How does the data sampling strategy impact the discovery of information diffusion in social media? In Fourth international AAAI conference on weblogs and social media, 2010.
[6] Leo Egghe and Ronald Rousseau. Introduction to informetrics: Quantitative methods in library, documentation and information science. Elsevier Science Publishers, 1990.
[7] Setavian-Euggnt Ganea, Gary Bécigneul, and Thomas Hofmann, Hyperbolic entailment cones for learning hierarchical embeddings. arXiv preprint
2018
[8] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 355-864, 2016.
[9] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning curved-curvature repre- sentations in product spaces. International Conference Learning Representations (ICLR), 2019.
[10] Mare Law, Renjie Liao, Jake Snell, and Richard Zemel. Lorentzian distance learning for hyperbolic representations. International Conference on Machine Learning (ICML), 2019.
[1]] Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smooth- ing the geometry of probabilistic box embeddings. International Conference on Learning Representations (ICLR), 2019.
[12] Daniel Marbach, James C Costello, Robert Küfffnrr, Nicole M Vega, Robert J Prill, Diogo M Camacho, Kyle R Allison, Manolis Kellis, James J Collins, and Gustavo Stolovitzky. Wisdom of crowds for robust gene network inference. Nature methods, 9(8):996 804, 2012.
[13] Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies the lorentz model of hyperbolic geometry. International Conference on Machine Learning (ICML), 2018.
[14] Evelien Otte and Ronald Rousseau. Social network analysis: powerful strategy, also for the information sciences. Journal of information Science, 28(6):441-455 2002.
(15) Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity pre- serving graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1105-1114, 2016.
[16] Gergely Palla, Illés Farkas, Péter Pollner, Imre Derényi, and Tamás Viesck. Directed network modules. New journal of physics, 966):166 2007.
[17] Bryan Perozzi, Rami Al-Rfon and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[18] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Fleventh ACM International Conference on Web Search and Data Mining, pages 459-467, 2018.
11

---

[19] Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. Trust management for the semantic web. In International semantic Web conference, pages 351-368. Springer. 2003.
[20] Fred S Roberts. On the boxicity and cubicity graph. Recent progress in combinatorics, 1969.
[21] Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoffs for hyperbolic embeddings. International Conference on Machine Learning (ICML), 2018.
[22] Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. International Symposium on Graph Drawing, pages 355-366, 2011.
[23] Aaron Sim, Maciej L Wiatrak, Angus Brayne, Páidí Creed, and Sace Paliwal. Directed graph embeddings in pseudo-riemannian manifolds. In International Conference on Machine Learning. pages 9681-9690. PMLR, 2021.
[24] Lovro Šubelj and Marko Bajec. Model of complex networks based on citation dynamics. In Proceedings of the 22nd international conference on World Wide Web, pages 527-530, 2013.
[25] Jiankai Sun, Bortik Bandyopadhyay, Armin Bashizade, Jiongqian Liang, Sadayappan, and Srinivasan Parthasarathy. Atp: Directed graph embedding with asymmetric transitivity preser- vation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 265 265- 2019.
[26] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embed- ding by relational rotation in complex space. International Conference on Learning Representa- lions (ICLR), 2019.
[27] Jian Tang. Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067-1077, 2015.
[28] Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. Association for Computational Linguistics (ACL), 2018.
(29) Chang Zhou, Yuqiong Liu, Xiaofei Liu, Zhongyi Liu, and Jun Gao. Scalable graph embedding for asymmetric proximity. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
[30] Shijie Zhu, Jianxin Li. Hao Peng, Senzhang Wang, and Lifang He. Adversarial directed graph embedding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4741-4748, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work does introduce any particular new potential for negative societal impacts, but provides inductive biases (transitivity ccclicitt) that could have negative downstream use cases as features for models, search (for example). However, we provide handles to control and trade-off such bias, therefore downstream users should be aware and control the bias as necessary.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We include complete proofs in Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [No] We obtained code and data for real world graphs that was publicly available.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] The data we use does not have any personally identifiable information offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "XOaUE1H_zIL", "reviewer": "Reviewer_99se", "summary": "Introduces the concept of binary code box embeddings and theoretically shows that the proposed models have the expressive power to model arbitrary directed cyclic graphs. Empirical result suggests that the proposed models perform better on 4 link prediction datasets compared to vector based baselines. ", "questions": "- The paper does a good job analysing the expressive power of the model. However, as the author(s) mention, whether or not the model can be trained via gradient descent is not yet clear. The paper does not currently have details on the optimization challenges/ease of the proposed models vs the other baselines. It is often possible that the expressive power is sufficient, but the optimization difficulty is high.\n\n- While the intuition of binary code box embedding bases off box embeddings, and has a nice theoretical picture, it is hard to intuitively see how much of the geometry structures are still learned by the models, since binary codes break transitivity. It would be interesting to see a visual comparison of the learned boxes in 2D with and without binary codes.   \n\n", "limitations": "How are the binary code represented during training/inference? Are they represented as a probability since the model is trained using gradient descent, or are they pushed to 0 and 1s? ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Binary code box embeddings is a novel concept with nice theoretical intuitions. It relieves some of the constraints of box embeddings at the expense of weakening transitivity. \n\n\n- Showed both theoretically and empirically the advantage of the binary code models being able to model directed cyclic graphs. \n\n\n- Provided nice intuition for proposed concepts using interval graphs, including box embeddings can be thought of representing a graph as an intersection over some learned subgraphs. Binary codes can be thought of redefining “intersection”, such that two non-overlapping boxes can be seen as overlapping by selecting which dimensions to ignore using the binary codes. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CuvSFweJ72k", "reviewer": "Reviewer_f6GD", "summary": "This paper proposed an extension of box embedding on dealing with directed graphs with cycles. The idea is called binary code box embedding, which learns to project the box embeddings into a subspace of the box space. The authors prove the theoretical expressivity of the proposed model. Empirical results on two tasks further show that the model provides useful inductive biases for preserving transitivity and cyclicity.", "questions": "The author in [1] proved that box embedding has some theoretical limitations on embedding some directed graphs (e.g., a counterexample is given in section 7.3 of [1]). How does the proposed model encode such a counterexample?\n\n[1] Vilnis, L., 2021. Geometric Representation Learning.", "limitations": "The authors discussed the limitations of the proposed Binary Code Box Embeddings and proposed a regularization term to alleviate but not fully address such problem.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\n\n1. An interesting extension of box embeddings for modeling cyclicity \n2. Strong empirical results\n\nCons\n\n1. Theoretical results in Sec 3.1 are taken from [2]. The author should cite it right after the title like “Theorem 1 [2]” to avoid misunderstanding. \n2. Theoretical results in Sec 3.2 are a bit trivial. It seems very clear that the box embedding cannot model any cycles in any dimension.\n3. The motivation for using binary code embedding is not very clear. Could you give an example of how the projection models cycles? For instance, how binary code box embedding can embed a pure cycle with 4 nodes with minimal dimension? that would be a nice picture that gives readers an intuition of the idea.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8pTK7n-R3o", "reviewer": "Reviewer_3KMQ", "summary": "The authors consider the problem of modeling directed graphs for semi-supervised link prediction. They propose a new model based on an extension of box embeddings which enables greater representational capacity, particularly in the presence of cycles. This extension may be viewed as a decomposition of a graph into a finite union of graphs, each of which modeled using (modified) box embeddings. The authors show that, with sufficiently high-dimensional embeddings, this model may represent an arbitrary directed acyclic graph. The authors demonstrate the effectiveness of their model through some experiments on synthetic graph models, and some applications on real data.", "questions": "It is unclear to me how the baseline vector model differs from existing pairwise latent embedding models such as node2vec. Indeed, it seems to me that the edge likelihood is exactly the same in either case (modulo directedness, which can be dealt with in such representations by separating the source and target embedding) - the crucial difference being the way edges are sampled and the effective induced weighting through the sampling procedure. Would the authors be able to describe in more detail what the exact loss for the vector model is?\n\nIn the paragraph preceding table 3, the authors mention that they evaluate t-Box, but this does not seem to appear in the table. Could the authors share these numbers and add them to the table?\n\nI was confused by the accounting of the number of parameters in the binarycode models in the provided code in the supplementary. My reading of the current code (`model.py:375-378`) indicates that the total number of parameters is $3 dim$. However, in `main.py:33` the computation of `dim` as a function of `num_parameters` and `shared_dim` gives, e.g. when `shared_dim = num_parameters / 2` that `dim = num_parameters / 2`, leading to a total of 50% more parameters than claimed. Running the code and inspecting the generated embedding tensors seems to support that claim. Would the authors be able to comment on how the parameters are counted for the binary box models?\n", "limitations": "I did not find any particular limitation except as described in the weaknesses. I do not believe this work has any particular societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I found the proposed method interesting and with good empirical performance. The authors propose an elegant solution to address issues with existing geometric embedding models. However, I also found this work to be fairly incremental (especially with respect to [2]), both from a theoretical and an empirical perspective, and had some doubts on the general motivation of the paper. Finally, I have some concerns in the empirical evaluations in the paper as it currently stands (see questions). On the balance, I do not feel that this work is currently a substantial enough contribution to warrant publication, although I am willing to revisit this judgment should my questions be addressed.\n\nThe modification proposed by the authors is elegant and addresses a potential issue in the representational power of box embeddings for graphs, namely the ability to model directed cycles. However, it is not clear to me how this relates to the claims around transitivity. Indeed, it seems to me that in the setting considered by the authors, transitivity is viewed not as a symbolic requirement, but rather a feature of the data (“soft transitivity”). In that setting, the argument given by the authors on ll. 34-35, that there is no encouragement for transitivity to hold seems suspicious: given that such edges are present in the data, it is unclear why a purely data-based approach is not able to recover them.\n\nAlthough the proposal of the authors is well-motivated theoretically, I found the empirical results to be unconvincing. Indeed, in table 3, the authors show that the G-box model achieves the same performance for 3 of the 4 benchmarks, and is only slightly behind on the 4th one. In practice, it thus seems that the cycle representation is not an issue, and the model is able to disambiguate cycles based on additional context. Especially given the additional flexibility in the *BC-box models, would the authors be able to provide additional empirical evidence that the difference, when it exists, is due to the inability to model cycles?\n\nTypos:\nL. 36 $o_k$ -> $t_k$\nL. 90 it’s -> its\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept