Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
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. 


- Showed both theoretically and empirically the advantage of the binary code models being able to model directed cyclic graphs. 


- 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. 
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.

- 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.   


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?
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.

The 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.

Although 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?

Typos:
L. 36 $o_k$ -> $t_k$
L. 90 it’s -> its

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?

In 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?

I 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?

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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Pros

1. An interesting extension of box embeddings for modeling cyclicity 
2. Strong empirical results

Cons

1. 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. 
2. 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.
3. 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.
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?

[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.
review_title: null

Meta-review: metareview: This paper extends box embeddings to allow for them to represent directed graphs. In particular, the proposed binary box embeddings can represent cycles in graphs, which was not previously possible. The reviewers appreciated the introduction of binary box embeddings and felt the contribution was novel and elegant. During the discussion, the reviewers felt that the rebuttal generally answered their questions and felt that the contribution would be of interest to the NeurIPS community. 

A number of clarity issues brought up in the initial reviews should be addressed for the final version of the work, for instance, the motivation of the binary code embeddings and the discussions with 3KMQ on transitivity holding. Please revise the paper to address the remaining comments from the reviewers and carefully incorporate the additional results presented during the author response discussion phase.
confidence: Less certain
Decision: Accept