Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a model which uses a learned weighted combination of spaces 
main_review: ### Overview

**Originality:** This work is (almost literally) a novel combination of well-known methods, and demonstrates sufficient originality.

**Quality:** The submission is technically sound, however:

- The one "statement" which appears (L145-L146) does not seem to have a corroborating proof in the appendix. (For completeness I would recommend this be included, even if it is relatively straightforward.)
- The authors propose a "universal signature", a name which seems to imply some level of sufficiency / representational capacity, however an explicit proof along these lines is not provided.

That said, the authors perform sufficient empirical analysis of their model, and are very honest about the strengths and weaknesses of their approach.

**Clarity:** The submission is clearly written and well organized, the model should be easily reproducible from their description.

**Significance:** The authors demonstrate improvement on various tasks as well as various aspects of training (see below) of interest to researchers.

---

### Specific Comments / Questions

**General:** The largest objection I could see to this work is that, despite sharing parameterization, these representations are not really "overlapping" in space from a geometric perspective. A critical reviewer could suggest that the performance improvement is simply the result of the model having access to a much richer set of transformations (a contention which is bolstered by the fact that dot product similarity is included, despite not being a metric) and demonstrate this fact by choosing arbitrary collections of otherwise nonsensical functions to include in the set of possible functions to calculate. If the resulting model was still able to perform well, this would point more to the amazing power of optimizers than any sort of combination of spaces with different curvature. Despite this, I think the work itself is interesting and provides many positive contributions to the field.

**L183-L190:** The fact that weights correspond both to changing curvature and different amounts of relative emphasis seems problematic. Does this mean, for example, that the model would struggle with data that, for example, ideally was embedded in mix of a low-curvature Hyperbolic space and high-curvature spherical space?

**L202-L209:** These observations and the proposed solution seem similar to [0], which may be worth citing. As an aside, [0] uses the squared Lorentzian distance, which is similar to the weighted inner product distance except in Hyperbolic space, and it may be of interest to use this in place of (or in addition to) distance on the hyperboloid.

**L239:** (minor) "better than for the best" → "better than the best"

**L250-L251:** (comment) The observation that distortion optimization weakly correlates with mAP optimization is an important one, I appreciate the authors bringing this to the community's attention.

**Section 5.3:** This experiment suggest that neural networks do not seem to easily adapt to overlapping spaces. This could either be a fundamental limitation or simply an area where additional machinery is needed. It seems likely to me, for example, that weight decay may not cooperate nicely with the overlapping spaces, and different forms of regularization may be necessary. In any event, I commend the authors for including this result in the paper itself.

**Section 5.4, 6:** These sections seem a bit rougher, grammatically, than the others.

**Questions / Extensions:**

- I was surprised that an analysis of the weights (eg. how they correlate to the performance of the product space networks and heuristics, how the weights of layer 0 differ when the model is allowed to go to layer 1) were not provided.
- I am also very curious about how the resulting embeddings compare to their single-space and/or product-space equivalents. For example, if we only considered the dot product distance of an OS-Mixed model is it similar to the scores from a trained c-d_dot model? What if we initialize an OS-Mixed model with embeddings from a trained c-d_dot model, and put most of the weight on the dot product portion? (In particular, this seems as though it may allow for better results from the DSSM experiment.) Another avenue for future exploration would be to consider an incremental approach, where (for example) model with t=0 is trained and then expanded to a t=1 model. (To be clear, these are not criticisms of the current paper, which I feel is sufficient, but suggestions for future work.)

[0] Law, Marc, Renjie Liao, Jake Snell, and Richard Zemel. "Lorentzian distance learning for hyperbolic representations." In International Conference on Machine Learning, pp. 3672-3681. PMLR, 2019.

limitations_and_societal_impact: I feel the authors adequately addressed all limitations of this work, which is of a theoretical nature without direct societal consequences.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper focuses on graph embedding task and propose the overlapping space that could combine several kinds of spaces in an efficient manner. The proposed method allows subsets of coordinates to be shared between different kinds of spaces. The empirical studies clearly show its promising performance.
main_review: Strengths:
+ The efficiency of combining different spaces is a crucial problem.
+ Experimental results of this paper are promising.

Concerns:
- The motivation of this paper should be discussed more clearly. The authors should explain why we use such complex spaces for learning graph embedding and what kind of data these methods are suitable for.
- The organization of this paper should be improved. The background and related work could be introduced in a more concise way.
- The meaning of Fig. 1 seems not clearly demonstrated. There are too much details in this figure, which hinders the expression of its core information.

limitations_and_societal_impact: The authors have adequately discussed these points.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Paper proposes overlapping spaces for embedding structured data. Those spaces combine Hyperbolic, Spherical and Euclidean spaces, that all can catch some different specificities of the data. In some sense, it extends the concept of product spaces, allowing some coordinates to be shared between the different spaces
main_review: The paper defines overlapping spaces, proposes an optimization scheme and gives an complete experimental evaluation.
The work is original, provides non trivial results and is supported by experimental evidence.

My main concerns are about the writing of the paper that may be improved and about some claims that should be provided with stronger evidence.
The paper is sometimes difficult to read; the paragraph dedicated on the description of paper [9] should be developed more clearly and more details should be provided as the proposed method strongly builds on it.
The description of the overlapping spaces is also quite hard to follow; Fig. 1 helps the reader to figure out the main steps of the method. The links between the curvature and the weights should be given with more details.
Again, in the optimization section, the procedure that is used instead than RSGD should be supported by stronger evidence.
The results provided in the experimental sections support the claims that the new space is definitely useful in a wide set of configurations ; the definition of the WLA6 is interesting. Nevertheless, it would be useful to recall all the notations that are used on the different tables.

That being said, I think that it is a good paper that extends in an appropriate way the product space, allowing to obtain better results.


Minor comments:
- l56: "mertic" should read metric
- the vectors are split in different halves (according to t): what happens if one shuffle the position of the dimensions? Would it be possible to take no adjacent dimensions? 
limitations_and_societal_impact: There is no discussion about the limitations and potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors propose to extend product space for embedding structured data. In doing so, the author poses to allow each dimension to possibly belong to multiple signatures t. To optimize, the authors propose to use universal signatures and a regular Adam optimizer. Extensive experiments have been conducted to demonstrate the effectiveness of new embedded space.
main_review: In this paper, the authors propose to extend product space for embedding structured data, after identifying its issue that finding the best combination of signatures (a signature is a group of dimension associates with a distance and scale coefficient) is labor and resource-intensive. In doing so, the author poses to allow each dimension to possibly belong to multiple signatures t. To optimize, the authors propose to use universal signatures that effectively serve as aggregations of signatures, and to use regular Adam optimizer. Extensive experiments have been conducted to demonstrate the effectiveness of new embedded space.

Generally speaking, this paper is a nice extension over product space [1] which itself already shows improvement over traditional, single spaces for embedding structured data. Product space divides dimensions into multiple disjoint signatures, thus suffering from the need to manually select configuration of these signatures. By allowing each dimension to possibly multiple signatures. This paper addresses its issue but extends its expressiveness.

Technically this paper is well written and easy to follow. Details look sounding, expect for some parts of the optimization and experiments, which I have concerns (or confusions) as fellows:


- Regarding the universal signature. If I understand correctly, it is similar to using divide and conquer to aggregate in order to reduce computation cost from exponential $O(2^d)$ to linear $O(d)$ This computational feasibility would be important as this allows scalability, but I'm not sure 
  - (a) why in the paper, only $t=0$ and $t=1$ is considered, instead of larger $t$. Note that $t \leq log_2 (n)$ are all valid choices.
  - (b) why the proposed universal signature can serve as a (possibly "approximated") replacement for a combination of all possible $2^d-1$ signatures. There seems to be no proof or experiments addressing  these issues.

- Regarding experiments: Only $d=10$, which is the same for [1] that this paper extends, is used for this work. What is the rationale behind such a choice? 

- Relation with [1]. As an extension, this paper naturally borrows concepts and notations from [1]. However, as this paper itself should be a self-contained work, It's better to add more discuss  --- currently the notations are sometimes left unexplained and readers may need to refer to [1] to get the whole picture.

To summarize, this paper focuses on an extension over [1]. The improvements may be somewhat incremental but show us the possibility of dimensions being used for multiple spaces/metrics in embedding structured data. I would recommend it more strongly if my concerns are resolved.

References:
- [1] Gu et al. Learning mixed-curvature representations in product spaces. ICLR 2019. https://openreview.net/forum?id=HJxeWnCcF7 



**After authors’ responses and discussion**: Some of my concerns are addressed and I increase my score from 6 to 7.

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper had quite a bit of high-quality discussion between reviewers and authors, and is approaching consensus. Multiple reviewers specifically champion the paper and ask for acceptance. The main argument against acceptance, from one of the reviewers is the lack of theoretical analysis. While this is something that would have been nice to have, most of the time, in embedding works, there is no tractable analysis that can be had, without specifying some much more limited version of the problem (e.g., studying distortion bounds for hyperbolic embeddings, but only for trees). So while going off in a theory direction would be interesting, the paper succeeds at its main task.

The paper’s core idea is clever; I can imagine a bunch of work that could take off from seeing this idea. Overall I lean towards acceptance. One thing the authors should work on is some additional clarity in the writing for the final version; this was noted by several reviewers, and I agree.

Decision: Accept (Poster)