Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work provides an empirical and theoretical foundation for the analysis of geometric representations of directed graphs. The paper introduces a novel box embedding model, extending the recent Gumbel-box process to learn a parametric model representing a continuous relaxation of box intersections. The model can trade-off between smoother, vector-like settings and more discrete, region-like settings, and provides better performance across a range of dimensionalities.

Directed graphs have received considerably less attention in the representation learning community than undirected graphs, making this paper particularly appealing. 
main_review: (1) Extensive and meaningful experiments with new observations can inform the design of future algorithms. Insightful empirical analyses are a strong plus of the proposed work. Include error bars in Figure 2. 

(2) Description of the novel box embedding method in section 3 lacks some information. Please describe the complete algorithm using the algorithmic environment. What are the critical hyperparameters of the approach? How does the new approach scale with graph size? I couldn't find this information in the Appendix.

(3) The authors treat the prediction of a directed edge from node i to j as a binary classification problem (in section 5). How are reverse edges predicted? Are those treated independently? The appropriate edge scoring function depends on the type of geometric model (e.g., Nickel and Kiela's [35] scoring function was designed for hyperbolic vectors). Would you mind clarifying and providing details for each method included in the benchmarking study? 

(4) The authors carry out a suite of experiments on synthetic and real-world graphs, comparing various vector, hyperbolic, cone, and box representations over a range of dimensions. That is great, but it also means that some aspects of the new model are not thoroughly evaluated (i.e., see point 2). 
limitations_and_societal_impact: Limitations of the work are described. This work does not seem to introduce any new potential for negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: # A solid work on Geometric Embeddings

This paper discusses the properties of recent geometric embeddings for representing graphs and extends a new continuous relaxation of the probabilistic box embeddings. This paper is written is a clear way: the motivation and contribution are clear, and backed up by extensive experiments. Theoretical contributions, especially the precision bound for box embeddings, are presented in parallel with its methodological contribution. Based on these strengths, although there are some issues (discussed below), I give a clear accept of this paper. 

main_review: This paper discusses the properties of recent geometric embeddings for representing graphs and extends a new continuous relaxation of the probabilistic box embeddings. I think this is a solid work what worth a clear acceptance. Yet I do want to point out certain issues and suggest further improvements: 
* Discussions on hyperbolic embeddings are just scratching the surface. Theoretical results are centered on box embeddings. I would suggest the authors to either give a more detailed discussion on hyperbolic embeddings, or shorten them. 
* The mechanism why axis-wise temperature gives better performance in high-dimensional scenarios is not discussed at all, which would be important to understand the source of performance gain (although all models are tuned with Bayesian hyperparameter search).
* Given this paper is more about box embeddings, I would suggest to shorten discussions on complex and hyperbolic vectors (put them in the appendix) and make room for the experiments. In the experiments, more studies about why axis-wise temperature improves performance in high-dimensional scenarios should be conducted (Possibly to show more stable optimization / numerics, as these are the major challenges for the hyperbolic case). 

Other Minor Points:

- For important theoretical results, their proofs should be sketched briefly (e.g.,  Thm 2)
- I would encourage using simple language to explain what the theorem says intuitively. For example, for proposition 3, the authors may say box embeddings can represent graphs with exponentially large number of nodes (because of the log V term), but the connections should not be too dense (because of the linear $\Delta$ term)
- The math behind why POE always yield a DAG but OE does not should be briefly explained, my understanding is that the composition of $max(\cdot)$ and L1 norm allows separation of variables while L2 norm does not
- Important concepts in the theorems should be explained briefly (e.g., what does bits per box mean?)
limitations_and_societal_impact: The underlying mechanism why axis-wise temperature helps in the high-dimensional case is not studied. I would recommend the authors to at least give an intuitive explanation.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyses models for node embeddings of directed acyclic graphs (DAGs). It has 3 contributions: 

i) it proposes a relatively straightforward extension of probabilistic box embeddings P-BOX [56], called t-BOX which is similar to the previous GumbleBox model [14], but has per-dimension and per-node intersection and volume temperature parameters (learnable) as opposed to just global parameters (as in GumbleBox). This extension is natural and the motivation is clear, but comes with the cost of doubling the number of parameters of the P-Box and GumbleBox models.

ii) theoretically, it extends the prior theory of [41] and [13] (which was analysing only undirected graphs) to work with DAGs and prove  that their t-Box model can represent any DAG (theorem 2, proof is an extension of [41]), giving an upper bound on number of dimensions and bits per box (proposition 3, proof is an extension of the result in [13]). Moreover, corollaries 1 and 2  are also the authors' contributions, being simple extensions of the result  in [56]. These theoretical results are important for understanding the representational capacity of existing DAG embedding models and I find this section nice and well written.

iii) Empirically, the authors evaluate the representational capacity (not generalization, just the "overfitting" ability) of several popular DAG embedding models on a variety of synthetic and real datasets. The choice of datasets is diverse and the empirical evaluation (e.g. removing the hyperparameters as confounding factors) is compelling, however, there are a few downsides that I will discuss below.
main_review: ======= Update after rebuttal ====

I am increasing my score to 7. See discussion.

=============================


First, I will touch the main required parts of this section, but my detailed comments will be given afterwards.

1) Originality:  I largely discussed this in the previous section. The t-BOX method is a straightforward extension of P-BOX. In its own is an incremental contribution, but given the other contributions of the paper, it is fair. Related work is missing important citations which would also be needed in the evaluation section (see below). 

2) Quality: largely discussed in the previous section.

3) Clarity: paper is well written, with nice and detailed descriptions of methods, theory, experimental setups, etc.

4) Significance: largely discussed in the previous section, but there are important points that I will add below.


Important drawbacks of this work:

- empirical results (figure 1) do not show a clear advantage of the t-BOX models over previous BOX or other models. In the best case, it is comparable, but not clearly better. Fig 2 is showing more clear gains, but that is of course at the cost of doubling the number of parameters.

- important prior work is missing both to be cited and to be compared empirically against: for example, it is mentioned that hyperbolic models struggle with transitivity and use an heuristic choice of the scoring function (eq 6). These issues were addressed by the work of hyperbolic entailment cones ([1,2,3]) which also address capacity difficulties of order embeddings.

- looking at representational capacity (i.e. overfitting ability) is one facet of the problem, but for the community it is arguably equally or more important to understand the generalization capability of these models. Evaluating tasks like link-prediction was done in most of the prior work on DAG embeddings, and the lack of it in this paper is a weakness. This is especially important since the proposed t-BOX model does not seem to show clear cases where it clearly outperforms the BOX or the other models.

- Many of the real datasets are relatively small (what are the stastistics of KNN and Imagenet-hac datasets?) and by "small" I mean that many of the models are already almost perfect with 32 parameters. As a consequence, it is quite hard to see how good these models really are in high dimensions as it is claimed in the abstract of the paper. Why not use larger datasets where the effect could be more visible, such as the full WordNet?

All in all, I would be happy to increase my score if: i) the authors would include at least one generalization experiment on a real dataset, ii) the authors would compare against hyperbolic entailment cones. Also, I would be glad to see at least one large real dataset where all the baseline models (excl. t-BOX but inc. P-BOX) are far from perfect in the 32 parameters case.


[1] Hyperbolic Entailment Cones for Learning Hierarchical Embeddings, Ganea et al, 20`18

[2] Inferring Concept Hierarchies from Text Corpora via Hyperbolic Embeddings, Le et al 2019

[3] Hierarchical Image Classification using Entailment Cone Embeddings, Dhall et al, 2020

limitations_and_societal_impact: yes, they did
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study geometric embeddings for directed graphs and propose a continuous relaxation of probabilistic box embeddings. They also analyze geometric embedding methods for modeling directed graphs by theoretical analysis and experiments.
main_review: Update After Rebuttal
---
I have carefully read the authors' responses. The explanation of why the trainable temperatures can help box embeddings avoid performance saturation in higher dimensions is reasonable. However, I still feel that there is a gap between the theoretical analysis and empirical implementations. In the further response, the authors provide a graph depicting the value of temperatures across all boxes as they are observed during training. It seems to me that many of the temperatures are far from zero, which violates the assumption in Theorem 2. In all, I recommend a weak accept for this paper.

---
Originality
---
The proposed box embedding model is a simple extension of that in [1], while the model in this paper allows learnable temperature parameters in the approximation of max operators. However, learning adaptive temperature parameters is not a new idea and it has been used in other scenarios, e.g., the computation of attention [2]. The authors may want to cite these papers and discuss the relationship between them and this work.

[1] Shib Sankar Dasgupta, Michael Boratko, Dongxu Zhang, Luke Vilnis, Xiang Lorraine Li, and Andrew McCallum. Improving local identiﬁability in probabilistic box embeddings. NeurIPS, 2020.

[2] Junyang Lin, Xu Sun, Xuancheng Ren, Muyu Li, and Qi Su. Learning When to Concentrate or Divert Attention: Self-Adaptive Attention Temperature for Neural Machine Translation. EMNLP 2018.


Quality
---
My major concerns about this paper are as follows.
1. Why the proposed model can outperform existing box embedding models is unclear. The authors claim that their method avoids performance saturation common to other geometric models in high dimensions, but why?
2. The authors claim that the learned temperatures capture uncertainty related to min and max coordinates for the box representing nodes. However, they did not clearly describe the exact meaning of uncertainty. Moreover, the authors may want to provide theoretical or experimental analysis to support the aforementioned claim.
2. It seems that the theoretical analysis in Section 4 has no strong connection with the proposed model. Does the analysis provide any guidance in model designing, or provide theoretical explanations for the effectiveness of the model?

Clarity
---
Overall, this paper is well-written. However, some important details are missing, which may confuse the readers.
1. What do capacity and bias mean? Though these two items appear frequently in the title, abstract, and introduction, the authors did not provide formal definitions for them.
2. The authors may want to include all the related work in the main text instead of the appendix.
3. I suggest the authors detail the objectives in Section 5, since it is critical for reproducing the results.

Significance
---
This work outperforms the state-of-the-art geometric embedding models in some experimental settings. The authors perform standard theoretical and empirical analyses. 

Other Comments
---
1. Box embeddings are also applicable in tasks involved with multi-relational graphs, e.g., knowledge base completion [3], which is also mentioned in the abstract of this paper. The authors should discuss these works and conduct experiments on multi-relational data, if possible.

[3] Ralph Abboud, İsmail İlkan Ceylan, Thomas Lukasiewicz, Tommaso Salvatori. BoxE: A Box Embedding Model for Knowledge Base Completion. NeurIPS 2020.
limitations_and_societal_impact: Yes. The authors addressed the limitations and potential negative societal impact of their work in the checklist.
review_title: null

Meta-review: This paper has reached a consensus in that the authors are offering several useful items to the study of embeddings, including a new method that balances between the flavors of two popular classes of existing embedding methods. This is a relatively practical area with many different proposed methods, so the authors approach—to bridge known gaps and provide useful theoretical and empirical insights—is welcome. The reviewers have very little variance between them; post clarifications by authors almost all the scores are identical. I also largely agree with the paper’s strengths. I’m positive about the contributions offered here.

Perhaps the main argument against acceptance, as also noted by several reviewers, is that the paper is a bit of a grab-bag in a sense, in that there’s some theoretical analysis of existing methods, the introduction of a new method, along with a large empirical study (not necessarily focused on just evaluating the proposed method). This is not a major problem, since all of these parts are useful, provide interesting insights that are likely to be helpful to practitioners, and the authors’ writing quality in weaving together these concepts is pretty good. The additional discussion period helped clarify a number of things here as well. 

I think the authors made a wise choice to study the basics and paint a fairly complete picture (e.g., the focus on representation quality rather than generalization, attempting to control all the factors involved in quality in the empirical results). This is a more well-grounded and scientific approach than is typically found in papers in this area.
Decision: Accept (Poster)