Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new framework for embedding first-order logic (FOL) queries over knowledge bases using region-based embeddings. The embedding space is a Cartesian product of 2D cones. Entities are embedded in the same space with 0-aperture cones (ray starting at origin).

- Authors provide the relevant foundation to cones in 2D space, the final Cartesian product space, and suggest parameterizations of projection, intersection, union, and complement operations.
- The choice of using cones facilitates complement operation.
- Authors demonstrate empirical improvements over past work in FOL query embedding.
- While the proposed cone-based region embeddings allow for clear descriptions for intersection, union, and complement, the implementation does not strictly enforce these geometric concepts.
main_review: ### Originality

- The work builds on past work on FOL query embedding and suggests new parameterization using cones. Set complements of cones are also cones and lie in the same embedding space. This was a limitation of past work that relied on geometrical embeddings (e.g. complement of box embeddings is no longer a box). This choice allows the representation to model all FOL operations.
- It has appropriately cited past related work and placed itself with respect to it.

### Quality

- The representation capacity of the proposed method is demonstrated with empirical results. The baselines are fairly compared. The ability to tackle set complement is also compared with relevant baselines.
- **(1) Minor clarification**: ConE embeddings are trained with *d*=800. Is this space the Cartesian product of 800 cones (so a total of 1600 parameters) or 400 cones (800 parameters)? If is it the former, then shouldn't the baselines also have 1600 dimensional embeddings?
- **(2) Strong claim**: Line 297 claims that cone embeddings are better geometric representations than box embeddings. I believe this is a very strong claim since it only compares against specific parameterizations of box embeddings. In particular, the notion of intersection and union of box embeddings is still an active area of research and there isn't a universally accepted parameterization.

### Clarity

- The paper provides the necessary mathematical background to understand the proposed approach of conical embeddings.
- Hyperparameters are reported in sufficient detail to recreate the experimental results.

### Significance

- The work improves the state of the art in a demonstrable way.
- There is scope to experiment with other parameterizations of the same underlying conical embeddings space for marginal improvements.
- There is also scope to view the apertures in a probabilistic framework (the fraction of the entire space covered by a cone can be interpreted as likelihood similar to probabilistic box embeddings)
limitations_and_societal_impact: ### Limitations

(1)

The set of sector cones (used to represent the query) is not closed under union and intersection.

(2)

The proposed parameterization of the intersection operation does not correspond exactly to set intersection.

As a concrete example, consider a space of a single 2D cone (i.e. *d*=1). The intersection of two sector cones with $C_1$ = ($\theta_{ax} = 0$, $\theta_{ap} = \pi / 2$) and $C_2$ = ($\theta_{ax} = \pi / 4$, $\theta_{ap} = \pi / 2$), have an intersection of $C_I$ = ($\theta_{ax} = \pi / 8$, $\theta_{ap} = \pi / 4$). This is not guaranteed by the parameterization i.e. an entity can belong to $C_1$ and $C_2$ but not to $I(C_1, C_2)$ as defined in sec 4.2.

(3)

The definition of an entity belonging to the answer set is not clear. This is especially confusing when using $d > 1$. The use of both *inside* and *outside* distance in the scoring seems to convey that an entity can belong to the answer set as long as it intersects any of the *d* cones in the query embedding. In this case, an entity can have some overlapping components with both the query and the complement of the query.

Alternatively, we can define that an entity belongs to the answer set only if it intersects all of the *d* cones in the query embedding. Under this definition, the proposed complement operation is too restrictive since an entity with just one mismatched cone dimension should belong to the complement.

- - -

The geometric embeddings help build intuitions/mental pictures when *d*=1 but the geometry isn't strictly imposed always. It would be useful to explicitly discuss this along with barriers to implementing fully geometric operations. 

### Societal Impact

The work does not pose issues in terms of negative societal impacts besides concerns noted in the supplementary materials.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a novel geometric embeddings called cone embeddings for solving query answering. Query answering requires embeddings of queries that are represented using first order logic. This includes conjunction, disjunction, negation but excluding Universal Quantification. Given this as basis, the related work until now has focused on two different types of embeddings (1) Geometric; and (2) probabilistic query based model. The progression from Geometric based embeddings to probabilistic models was primarily due to the fact that geometric embeddings cannot handle negation.
main_review: The work differentiates itself from the other related works in the geometric query embeddings space by handling negation in first order logic queries for knowledge graphs. They propose cone embeddings (in comparison to Box Embeddings). Cone embeddings can handle negation because complement of a cone is also a cone, whereas this is the primary limitation for box embeddings. The approach also proposes four operators (a) Projection, (b) Intersection, (c) Union, and (d) Complement. The experiments on three different datasets and 9 different patterns of queries shows that Cone embeddings outperform the other approaches including BetaE, Query2Box, and GQE. This also includes its performance gain in predicting the cardinality of the answers. 

The paper is written well and the overall evaluation shows significant performance gain in comparison to other approaches. 

My main concerns with the paper are as follows:
1. Comparison to faithful embeddings: The primary drawbacks of query embeddings approach is that they focus on incomplete knowledge bases. In pursuit of this -- they lose significant performance on complete knowledge bases. This is an important feature that is required for all embeddings. This work does not compare itself on the setting and also does not provide any reasons why they did not attempt comparing. 
2. Qualitative analysis between Box Embeddings and Cone Embeddings: While Cone Embeddings makes sense for negation, it is unclear why they perform significantly better than Box Embeddings. This is also the case in comparison to BetaE for negation. The authors primarily drive the work as having a geometric embeddings for negation but do not motivate/justify why Cone embeddings performs better than Box Embeddings for this work. Particularly, seems like Box Embeddings can handle most of the conjunctive queries without negation and is probably more easily interpretable than cone embeddings. 

Overall -- its hard for me to understand why ConeEmbeddings performs well on all aspects since it is not clearly explained in the paper. Further, it is important to have the time taken for training both ConeEmbeddings, BetA, and BoxEmbeddings. This is primarily because of the effect of multiple operators including the negation in Cone embeddings. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: A recent line of knowledge graph (KG) query systems "compiles" the query into an embedded representation, which is interpreted as a geometric region and then used to find response entities whose embedding representations are contained within the region.  Query2box is an early example, where the regions are multidimensional boxes or rectangles.  To be useful, the regions have to be simple, closed under query operators, and capable of being characterized using a few parameters.  Union (disjunction) and negation have therefore created problem for boxes.  This paper replaces boxes with a Cartesian space of cones in 2d.  By restricting the family of permitted cones and disjunction to the last step of any query, the authors argue that their cone family is closed under query operators.  Experiments with benchmarks that have a good diversity of query graph structures show promising results.

main_review: Motivation and novelty of problem statement:

The problem statement was established in Query2box.
It is well-motivated, although the claimed "exponential" complexity of discrete graph alignments vs. efficiency of query embedding methods is somewhat debatable.  Plenty of SPARQL implementations do fine on these query classes by clever indexing and pruning.

Moreover, even from the ML perspective, generating a region of embedding space with various assumptions about the compactness of and distances in the region seems more fraught with difficulties than testing a candidate entity against a query, in a discriminative manner.  This also depends on the fanout of a query operator.  See further discussion on table 1 later.  However, the current authors do not really own that debate.


Clarity of presentation:

The paper is quite well written. However, there is one high level issue.  It could well be a limitation in my understanding.

To discuss it, we first need a mild definition.  Let's say a cone in 2d is simple if it has only one contiguous region, i.e., is defined by exactly two rays from the origin.  A simple cone may be convex (if the aperture is at most $\pi$) or non-convex.  A convex cone is always simple.  The complement of a simple cone is also simple.

There is a 1-1 mapping between the Cartesian space of $K$ simple cones and $K$-dimensional boxes.  So, in principle, ConE goes beyond query2box only because they allow a larger family of cones.

The authors define "sector-cones" (definition 3).  A sector-cone or its closure-complement is convex.  If a sector-cone is convex, it is simple.  Otherwise its complement is simple and therefore so is it.  So it seems a sector-cone is always simple.

Now even if there is a bijection between $K$ simple cones and $K$-dimensional boxes, non-convex loss optimization can behave  differently, but it seems to be important to understand the core reason behind the superiority of ConE over Query2box.

Quality and depth of technical proposal/
Detailed comments:

L81 Careful about terminology here: relation instance from $\mathcal{E}$ vs. relation type from $\mathcal{R}$.

L85 triples -> triple

L124 near Defn 3 --- give more examples to clarify the expressiveness boundaries of sector-cones, particularly concerning the discussion about simple cones above.

L150 "should have similar embeddings" --- this is actually quite questionable, and there is some anecdotal evidence (sorry, word of mouth) that even entity sets belonging to what look like coherent types to humans do not occupy tight or compact regions in typical embedding spaces.

L159 remove the two occurrences of "embeddings"

L190 After staying with the paper reasonably well up to this point, and noting the visual definition of intersection in Fig 2(b), SemanticAverage and CardMin come as surprises.  Why should we define the intersection axis as any kind of average?  Aren't the bounding rays of the intersection cone defined in terms of a bunch of min and max operators?

L213 ... and if you are using DeepSets to define the intersection aperture, small wonder about the numbers in Table 3; section 5.3.  I was hoping this would arise naturally out of ConE magic.

L223 "is also a cone" ... but is it a sector-cone?

Table 1 is intuitive.  The trend 1p > 2p > 3p is generally sustained from prior work.  3i gets a large boost, but that is the case even for Q2B --- basically, chaining out is progressively harder with chain length, but intersections are easy (which has been the experience with indexed/combinatorial graph traversal approaches as well).

On negation queries the gains are modest, again raising the question about fundamental model capacity over boxes.

limitations_and_societal_impact: Societal impact: N/A

Limitations: Please provide clarification for the questions raised in the main review field.

To a first order, the appeal of this paper is in improved accuracy, not a new modeling or representation insight.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new embedding model for multi-hop reasoning over knowledge graphs. The idea is to embed a complex query as n arc segments each on a 1-sphere. The paper designs several neural logic operators including the intersection, projection and complement operators. For union, the model uses the DNF technique to reorder the operators so that the union operators always appear in the last step. The authors evaluate the model on standard benchmarks and achieve better results than prior methods. 

Overall the paper is clean and easy to follow. A general question I have is that the current modeling is to embed the query into several independent arc segments. Have you tried to embed the query into the surface (sphere cap) of a n-sphere? 

main_review: Here are some additional questions.
1. line 46-47, it seems a little inaccurate. The beta QE model uses the KL divergence to determine whether an entity is an answer to the query. Can you clarify this point?
2. For the SemanticAverage operation, what if the weighted sum of the points is a whole-zero vector? E.g., what is the intersection between $\theta$ and $\theta+\pi$?
3. Can you also report the performance of converting union queries into queries with only intersection and complement operations? How does it compare with the DNF modeling?

limitations_and_societal_impact: Please check the questions in the section above. I do not see any potential negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper represents a novel approach to learning embeddings for entities and relations from a knowledge base that are capable of directly encoding *reasoning* (i.e. FOL). The principal representation proposed for this representation is a *cone* (i.e. a set which is closed under multiplication by a positive scalar) which is motivated by the fact that cones are closed under intersection and complements. In practice, the authors use *sector cones*, which leads to some incongruity between the original motivation and the model in practice (eg. sector cones are not closed under intersection or union). Even so, the authors apply this embedding method to several standard logic embedding tasks and demonstrate significant performance improvements.
main_review: ### Update after Rebuttal
The authors have performed extensive experiments to aid in understanding how the neural operators approximate their geometric analogs as well as various potential logical discrepancies that exist between the interaction of negation and union / intersection. I appreciate the time and effort which went into these additional experiments, and feel they add significant value to the paper. I would strongly encourage the authors to include this level of detailed analysis in a polished way in the final submission.

### Overview

**Originality:** The approach of using this form of cones is significantly novel, and the approaches to representing relations, intersections, and unions combine well-known techniques in a reasonable way.

**Quality:** The most concerning aspect from the perspective of quality is the distinction between motivation and practice, as mentioned in the summary. Not only is the set of sector cones not closed under intersection or union, the actual operations used for projection, intersection, and union are not necessarily self-consistent (see below). That being said, the empirical evidence in support of the resulting model, regardless of it's departure from the initial motivations, is quite strong.

**Clarity:** The submission is reasonably clear, and gives enough mathematical detail to reproduce the results.

**Significance:** The authors report strong results on the task of logic embeddings, which is of significant interest to the community.

---

### Specific Comments / Concerns

The fundamental question which remains in my mind is whether the original motivation of using *cones* is responsible for the improved performance, particularly when considering the fact that many of the original motivating principles to suggest their use are not applicable to the model which was employed in practice. For example:

1. The authors claim that the aperture of a cone should represent the number of entities it contains, however this aperture must also somehow depend on the variety of answers. For example, consider a query that represents a very specific set of things that (from the KB's perspective) are all very similar vs. a very general query with a wide variety of answers. Here is an approach to test this: pick an arbitrary entity $x$ from the KB, and artificially augment the training data by creating many new entities $\{\tilde x_i\}$ which have identical relations to $x$. Then, any query which contains $x$ suddenly contains many more entities, but this does not actually require that it have a larger aperture - indeed, the exact same model should work if the $\tilde x_i$ entities simply have the same embedding as $x$.
2. As mentioned in the summary, the use of cones is motivated by their closure under intersection and union, however the actual model uses sector cones which are not closed under intersection and union. Still, it seems the model performs very well. The authors mention that they have resubmitted this paper to NeurIPS with additional motivation and evaluation along these lines, however I actually feel it is simply less emphasized in the beginning and has not been fully explored. For example, the representations could be assessed as to how well they approximate the actual intersection and union operator - if it is close, then perhaps the original motivation is justified; if it is not, then the next question on my mind would be to explore the actual model and try to identify which properties are contributing to the increased performance.
3. Apart from the difference between cones and sector cones, the operations themselves are all learned and do not necessarily obey reasonable compositional semantics. For example, if cone A is inside cone B (indicating that it contains elements which are, themselves, a subset of those in B) then the projection of A should be inside the projection of B, but this is not guaranteed by the current model. Composing operations lead to additional issues, for example, the complement of intersections may be far from the union of their complements. This can be assessed in much the same way as proposed above - compare the learned operators with geometrically accurate versions; if it is close, then perhaps it is learning to approximate the geometric idealized model, if it is not close then I would argue that it is not, fundamentally, embedding the logical operations it claims to.
limitations_and_societal_impact: The questions I raised above could be viewed as a limitation of the work, particularly if it turns out that the proposed operators are not actually learning the intersection / union / complement operations they claim to represent.
review_title: null

Meta-review: The paper attempts to improve reasoning over knowledge bases. In this regard, the authors introduces a novel query representation using cones. As the set of cones is closed under intersection, union, and complement, it is claimed that such representation can be very expressive. Empirical performance of the proposed method is very good. We thank the reviewers and authors for engaging in an active discussion, which resulted in clearing a lot of the concerns (e.g. mismatch between motivation and method) and a lot of constructive feedback were provided to improve the paper. The authors provided extensive empirical results as part of the discussion, please include them in the final version of the paper as they add great value and understanding to the model as a whole.
Decision: Accept (Poster)