Overlapping Spaces for Compact Graph Representations
Authors: Kirill Sergeevich Shevkunov
Liudmila Prokhorenkova
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph embedding
hyperbolic space
product space
overlapping space

Abstract: Various non-trivial spaces are becoming popular for embedding structured data such as graphs, texts, or images. Following spherical and hyperbolic spaces, more general product spaces have been proposed. However, searching for the best configuration of a product space is a resource-intensive procedure, which reduces the practical applicability of the idea. We generalize the concept of product space and introduce an overlapping space that does not have the configuration search problem. The main idea is to allow subsets of coordinates to be shared between spaces of different types (Euclidean, hyperbolic, spherical). As a result, we often need fewer coordinates to store the objects. Additionally, we propose an optimization algorithm that automatically learns the optimal configuration. Our experiments confirm that overlapping spaces outperform the competitors in graph embedding tasks with different evaluation metrics. We also perform an empirical analysis in a realistic information retrieval setup, where we compare all spaces by incorporating them into DSSM. In this case, the proposed overlapping space consistently achieves nearly optimal results without any configuration tuning. This allows for reducing training time, which can be essential in large-scale applications.

Overlapping Spaces for Compact Graph Representations
Kirill Shevkunov Yandex, MIPT Moscow, Russia
Liudmila Prokhorenkova
Yandex Research, MIPT, HSE University
Moscow, Russia
shevkunov. wwwpkkstehhhhhheeeeeoeo edu
ostroumovv--l@yyadeex.u
Abstract
Various non-trivial spaces are becoming popular for embedding structured data such as graphs, texts, or images. Following spherical and hyperbolic spaces, more general product spaces have been proposed. However, searching for the best con- figuration of product space is resource-intensive procedure, which reduces the practical applicability of the idea. We generalize the concept of product space and introduce an overlapping space that does not have the configuration search problem. The main idea is to allow subsets of coordinates be shared between spaces of different types (Euclidean, hyperbolic, spherical). As a result, we often need fewer coordinates store the objects. Additionally, we propose optimization algo- rithm that automatically learns the optimal configuration. Our experiments confirm that overlapping spaces outperform the competitors in graph embedding tasks with different evaluation metries. We also perform an empirical analysis in a realistic information retrieval setup, where we compare all spaces by incorporating them into DSSM. In this case, the proposed overlapping space consistently achieves nearly optimal results without any configuration tuning. This allows for reducing training time, which can be essential in large-scale applications.
Introduction
Building vector representations of various objects is one of the central tasks of machine learning.
Word embeddings such as Glove [22 and Word2Vec [19 are widely used in natural language processing; a similar Prod2Vec 7 approach is used in recommendation systems. There are many algorithms proposed for graph embeddings, e.g., Node2Vec and DeepWalk [23]. Recommendation systems often construct embeddings of a bipartite graph that describes interactions between users and items [10].
For long time, embeddings were considered exclusively in R" However, the hyperbolic space was shown to be more suitable for graph, word, and image representations due to the underlying hierarchical structure [12] 20) proposed product spaces, which combine several copies of Euclidean, spherical, and hyperbolic spaces. While these spaces demonstrate promising results, the optimal signature (types of combined spaces and their dimensions) has to be chosen via brute force, which may not be acceptable in large-scale applications.
21 21,22]] Going beyond spaces of constant curvature, a recent study [9]
In this paper, we propose more general metric space called overlapping space (OS) together with an optimization algorithm that trains signature simultaneously with embedding allowing us to avoid brute-forcing. The main idea is allow coordinates to be shared between different spaces, which significantly reduces the number of coordinates needed.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Importantly the proposed overlapping space can further be enhanced by adding non non-metric approaches such weighted inner product [T3] additional similarity measures complementing metric ones. Thus, we obtain a flexible hybrid measure OS-Mixed that is no longer metric space. Our experiments show that in some cases, non-metric measures outperform metric ones. The proposed OS-Mixed has advantages of both worlds and thus achieves superior performance.
To validate the usefulness of the proposed overlapping space, we provide an extensive empirical evaluation for the task of graph embedding, where we consider both distortion-based (i.e., preserving distances) and ranking- based (i.e., preserving neighbors) objectives. In both cases, the proposed measure outperforms the competitors. We also compare the spaces in information retrieval and recommendation tasks, for which we apply them to train embeddings via DSSM (M]. Our method works comparable to the best product spaces tested in these cases, while it does not require brute- forcing for the best signature. Thus, using the overlapping space may significantly reduce the training time, which can be crucial in large-scale applications.
2 Background and related work
2.1 Embeddings and loss functions
For graph G =VV, F)) an embedding is mapping f : V + U, where U is a metric space equipped with a distance du
x - R P On the graph, one can consider a shortest path distance de V V + R4. In the graph reconstruction task, it is expected that good embedding preserves the original graph distances: do u) du (f((),), f(u)). The most commonly used evaluation metric is distortion, which averages relative errors of distance reconstruction over all pairs of nodes:
(do()()), - da(v, w)
Davg [
Σ
(1)
dc(v,u)
(V. jogf
While commonly used in graph reconstruction, distortion is natural choice for many practical applications. For example, in recommendation tasks, one usually deals with a partially observed graph (some positive and negative element pairs), huge graph distance between two nodes in the observed part does not necessarily mean that the nodes are not connected by a short path in the full graph. Also, often only the order of the nearest elements essential while predicting distances to faraway objects is not critical. In such cases, it is more reasonable to consider a local ranking metric, e.g., the mean average precision (mAP) that measures the relative closeness of the relevant (adjacent) nodes compared to the others
mAP
1 - V Σ AP(c)
Σ deg(c) NEV
Σ WEN,
N.v (.)
V
[R)(
VEV
(2)
(u) tw (f(v),
du f(u)), =
= {w
VI(o, E}.
Mean average precision cannot be directly optimized since it is not differentiable. our experiments, we use the following probabilistic loss function proxy 3
exp(-da:[(ww,
I Tproxy =
Σ E
log P((u, u) E E) =
Σ log
Σ exp(- (f()
(,
WEV
Note that when substituting (x. = c- fy) (assuming that f(x) R", so the dot product is defined), Lprozy becomes the standard word2vec loss function.
2.2 Spaces, distances, and similarities
In the previous section, we assumed that du U U -> R2 is arbitrary distance. In this section, we discuss particular choices often considered in the literature.
Note that any discrete metric space corresponds to weighted graph, so graph terminology is not restrictive. Foor mAP, the relevance labels are assumed be binary (unweighted graphs). a graph is weighted, then we say that. N, consists of the closest element to e (or several closest elements if distances them are equal). See Table 10 in Appendix for the comparison of other ways of converting distance to probability.

---

For many years, Euclidean space was the primary choice for structured data embeddings [6] For two 1/2
points 2; y E IRd, Euclidean distance defined as de(r, y)
Σ (t y2)²
Spherical spaces also found to be suitable for some applications T8
24 30
Indeed, in practice,
vector representations are often normalized, so cosine similarity between vectors is a natural way to measure their similarity. This naturally corresponds to spherical space Sa {i E Rd+1, +|>||| If equipped with a distance (z( .) arccos y).
In recent years, hyperbolic spaces also started to gain popularity. Hyperbolic embeddings have shown their superiority over Euclidean ones in a number of tasks, such as graph reconstruction and word embedding [20] 20 (5 26).. To represent the points, early approaches used the Poincaré model of the hyperbolic space (0)]. but later it has been shown that the hyperboloid (Lorentz) model may lead to more stable results [1]. In this work, also adopt the hyperboloid model Ha = {o E IR++
Kr, x) = 1, > 0} equipped with a distance dæ = arccosh( (a, v) where d+1
(r, = 11
Σ Jal.
Going even further, a recent paper ( proposed more complex product spaces that combine several copies of Euclidean, spherical, and hyperbolic spaces. Namely, the overall dimension is split
k into l parts (smaller dimensions): d = Σ d. di > 0. Each part is associated with a space
D; E {Ea,: Sa,, Ha,} and scale coefficient w; E R+. Varying scale coefficients corresponds to changing curvature of hyperbolic and spherical spaces, while in Euclidean space this coefficient is not used (w, = 1). Then, the distance in the product space D1 X ... x D₁ is defined as:
dp(x.y) v)
w; do, (xlt-11+ + t.). 1/4-1 1: :t))),,
where tu = 0. 14-1 + d; and æ/s el is a subvector (z....., ) E Re-s+1 If = 1, we get a standard Euclidean, spherical, hyperbolic space.
In [9) it is proposed to learn an embedding and scale coefficients w, simultaneously. However, choosing the optimal signature (how to split d into d, and which types of spaces to choose) is challenging. A heuristies proposed [9] allows to guess types of spaces if d,'s are given. d = d2 = 5. this heuristics agrees well with the experiments on three considered datasets. The generalizability of this idea to other datasets and configurations is unclear. In addition, it cannot be applied if dataset is partially observed and graph distances cannot be computed (e.g., when there are several known positive and negative pairs). Hence, in practice, it is more reliable to choose a signature via the brute-force, which can be infeasible on large datasets.
Another way measure objects' similarity, which is rarely compared with metric methods but is frequently used in practical applications, is via the dot product of vectors x² y or its weighted version x Wy with a diagonal matrix W. which also known as a weighted inner product [13]. Such measures cannot be converted to a metric distance via a monotone transformation. However, they can be used predict similarity or dissimilarity between objects, which often sufficient practice, especially when ranking metrics are used.
In this paper, we stress that when comparing different methods, both metric and non-metric variants should be used because different methods are better for different tasks. In particular, the dot product similarity allows one to easily differentiate between more popular and less popular items (the vector norm can be considered a measure of popularity). This feature is also attributed to hyperbolic spaces, where more popular items are placed closer the origin.
2.3 Optimization
Gradient optimization in Euclidean space is straightforward, while for spherical or hyperbolic embeddings, we also have to control that the points belong to surface. In previous works, Riemann- SGD was used to solve this problem 2 In short, projects Fuclidean gradients on the tangent space at point and then uses so-called exponential map to move the point along the surface according
3

---

to the gradient projection. For product spaces, a generalization of the exponential map has been proposed [ 27
In [29], the authors compare RSGD with the retraction technique, where points are moved along the gradients in the ambient space and are projected onto the surface after each update. From their
experiment, the retraction technique requires from 2% to 46% more iterations, depending on the learning rate. However, the exponential update step takes longer. Hence, the advantage of RSGD in terms of computation time depends on the specific implementation.
Overlapping spaces
3.1 Overlapping metric spaces
In this section, we propose a new concept of overlapping spaces This approach generalizes product spaces and allows us make the signature (types and dimensions of combined spaces) trainable. Our main idea to divide the embedding vector into several overlapping (unlike product spaces) segments, each segment corresponding its own space. Then, instead of discrete signature brute-forcing, optimize the weights the signature elements.
Importantly, allow the same coordinates of an embedding vector to be included in distances computations for spaces of different geometry. For this purpose, we first need to map a vector x IRd (for any d 1) point in Euclidean, hyperbolic, and spherical space. Let us denote this mapping by M. Obviously, for Euclidean space, we may take (x z. We may use the vector normalization for the spherical spaces, and for Ha we use projection from hyperplane hyperboloid:
(V
I E S4-1, (x)
Ms(x)=
1
22. 21
dd
E H
(4)
x
Note that for such parametrization a d-dimensional vector ir is mapped into Euclidean and hyperbolic spaces of dimension d and into a spherical space of dimension d - 1. Hence, in standard implementa- tions of product spaces, a sphere S₂ is parametrized by a (d + 1)-dimensional vector (9] However, this requires more coordinates to be stored for each spherical space. Hence, to make a fair comparison of all spaces, we use the hyperspherical coordinates for Sz:
cos 21 COS Ø2
COS Zd-1 COS Id
Cos 008
04-1 sim
Ms(x)=
CO8 #1 008 02
sin F2-1
E Sa.
(5)
sin 11
Now ready define overlapping space. Consider two vectors I, E Rd Let Pi...., denote some subsets of coordinates, i.c., pj C "h....,d), We assume that together these subsets cover all coordinates, i.e., - P = f1.....df d). By x z(pd we denote subvector of æ induced by p:. Let D; {E. S, H). We define dz 3) == dp, (MD, (x(p.)), Mp, (v.(p)))) and aggregate these distances with arbitrary positive weights wi
R4:
dg
w;d((x, v).
(6)
1/2
(3(z,))
Σ wirk (z. (z.1)
Definition 1. Oa = fx E Rd) equipped with a distance d' or dB defined in (6) is called an overlapping space. This space is defined by Ps, D,, and w...
Note that is sufficient to assume that spherical and hyperbolic spaces have curvatures and -1, respectively, since changing the curvature is equivalent to changing scale, which is captured by wi- The following statement follows from the definition above and the fact that dg, ds, and du are distances (see Appendix for the proof).
We refer Appendix D for additional simple illustrations of the proposed idea.

---

wi E R4, then do d' are distances on R x R2, Statement 1. If Jf = = (l..... and ui.... i.e, they satisfy the metric axioms.
It is easy to see that overlapping spaces generalize product spaces. Indeed, if we assume Ps Op 0
for all * j. then an overlapping space reduces to product space. However, the fact that we allow P. a Py * 0 gives significantly larger expressive power for the same dimension d.
3.2 Generalization with WIPS: OS-Mixed measure
known that for ranking loss functions, methods based on weighted and standard dot products can have good performance [13] Let note that such similarity measures cannot be converted to a distance via a monotone transformation. In our experiments, we notice that in some cases, such non-metric methods can successfully be used for graph embeddings even with the distortion loss, when the model approximates metric distances.
To close the gap between metric and non-metric methods, we propose generalization of the overlapping spaces that also includes the weighted inner product similarity (WIPS).
First, let us motivate our choice of WIPS. One may extend the list of base distance functions {dE, ds, d with dissimilarity measure dao c x² y that is not a metric distance. By using such "distance" for all possible subsets pt E 2 and applying (1-aggregation (6), we get WIPS
measure dw ē ii
warii where é and W; are trainable values.
Thus, instead of using an extended set of base distances {dg, ds, du daa) together, as shown in equation (6), we suggest simply use dos-Mized y) do (xr y) dw (x.y) where do is metric overlapping space. We show that this design gives excellent results for both distortion and ranking objectives in the graph reconstruction task. We further refer to this approach as OS-Mixed.
Optimization in overlapping spaces
4.1 Binary tree signature
Overlapping spaces defined in Section are flexible and allow capturing various geometries. However, similarly to product spaces, they need signature (p; and D,) be chosen in advance. This section describes a particular signature, which is still flexible, does not suffer from the brute-force problem, and shows promising empirical results the datasets experimented with.
Let t 2 denote the depth (complexity) of the signature for a d-dimensional embedding. Each layer I, 0 < 1 t, of the signature consists of 2 subsets of coordinates: p - 10/2- 1,...., [di/2"]]
isiss 2'. Each p is associated with Euclidean, spherical, and hyperbolic spaces simultancously. The corresponding weights are denoted by w. wo w.! Then, the distance is computed according to (6) See Figure I for an illustration of the procedure for d= 10 and
Informally, assume that we have two vectors y E Rdd. To compute the distance between them in the proposed overlapping space, we first compute Euclidean, spherical, and hyperbolic distances between and y. Then, we split the coordinates into two halves, and for each half, we also compute all three distances, and so on. Finally, all the obtained distances are averaged with the weight coefficient according to (6). Note that we have 3(2++1 1) different weights in our structure in general, but with 12-aggregation this value may be reduced to 2(2 - 1) +)+2 2' since for the Euclidean space, the distances between subvectors at the upper layers be split into terms corresponding smaller subvectors, so we essentially need only the last layer with 2' terms.
Recall that in a product space, the weights correspond to curvatures of the combined hyperbolic and spherical spaces. our case, they also play another important role: the weights allow us balance between different spaces. Indeed, for each subset of coordinates, we simultaneously compute the distance between the points assuming each the combined spaces. Varying the weights, we can increase or decrease the contribution of particular space to the distance. As result, our signature allows us to learn the optimal combination, which does not have to be a product space since all weights can be non-zero. Interestingly, when we analyzed the optimized weights, observed that
5

---

E R 10
do (a,
(x, y)
widh
E R 10
(x(x(p)))
d1,F.
Ms(viefl)
layer
Ms(x(p]1)
d2,s
Ms(v(p())
Mn(x(p[1)
d3
Me (x(pf))
d,
Me(v(ptl)
Mæ (p)1)
ds,F
MR Mx(v(p2))
Ms(x(p]])
do,s
Ms(v(e())
layer
Ms (z)p))
d7,s
Ms(ulpg))
My (x
ds
Mx(vlp())
ds
Mn((ppp))
Mr pb))
=[p"]
2 z[p|] (21...
y/p
(ve... yio)
Figure 1: Overlapping space with d = 10, / = 1, and /1 (sum) aggregation
often of them close zero. Thus, unnecessary weights be detected and removed after the training. See Appendix [35 for more details.
Note that the procedure described in this section naturally extends OS-Mixed by adding the corresponding 'distance' to Euclidean, hyperbolic, and spherical as described in Scction 3.2
4.2 Optimization
In this section, we describe how we embed into the overlapping space. Although Riemann- SGD (see Section 2.3) is good solution from the theoretical point of view, practice, due errors in storing and processing real numbers, it may cause some problems. Indeed, point that we assume lie on surface (sphere or hyperboloid) does not numerically lie it usually. Due to the accumulation of numerical errors, with each iteration of RSGD, point may move away from the surface. Therefore, in practice, after each step, all embeddings are explicitly projected onto the surface, which may slow down the algorithm. Moreover, RSGD is not applicable if one needs to process the output of a neural network, which cannot required to belong to given surface (e.g.. + E H2). As result, before finding the hyperbolic distance between two
to satisfy (ar, a) outputs of a neural network in the Siamese [3] setup, one first needs to map them to hyperboloid.
Instead of RSGD, we store the embedding vectors in Euclidean space and calculate distances between them using the mappings (4) to the corresponding surfaces. Thus, we can evaluate the distances between the outputs of neural networks and also use conventional optimizers. To optimize embeddings, we first map Euclidean vectors into the corresponding spaces, calculate distances and loss function, and then backpropagate through the projection functions. To improve the convergence, we use Adam [14 instead of the standard SGD. Similar technique using SGD with momentum is used in [5 Applying this to product spaces, we achieve the results similar to the original paper [ (see Table in Appendix), where RSGD was used with the learning rate brute-forcing, custom learning rate for curvature coefficients, and other tricks.

---

Table Datasets for graph reconstruction
USCA31
CS PhDs
Power
Facebook
WLA6
EuCore
Nodes Edges
312
1025
4941
4039
3227
986
48516 (weighted)
1043
6594
88234
3604
16687
Table 2: Distortion graph reconstruction, top results are highlighted, top metric results are underlined
Signature
USCA312
CS PhDs
Power
Facebook
WLA6
EuCore
F10
0.00318
0.0475
0.0408
0.0487
0.0530
0.1242
H10
0.01104
0.0443
0.0348
0,0483
0.0279
0.1144
Sig
0.01065
0.0519
0.0453
0.0561
0.0608
0.1260
H3 H5 x Hs
0,00573
0.0345
0.0255
0,0372
0.0279
0.1106
S5 Ss Ss
0.00700
0.0501
0.0438
0.0552
0.0584
0.1251
H5 X Ss
0.00541
0.0341
0.0254
0.0346
0.0310
0.1195
H
0.00592
0.0344
0.0273
0.0439
0.0356
0.1163
ST
0,00604
0.0464
0.0416
0.0512
0.0543
0.1244
H3 x 1/2 x $
0,00537
0.0344
0.0302
0.0406
0,0437
0.1193
ou, =
0.00324
0.0368
0.0281
0.0458
0.0286
0.1141
on,
0.00325
0.0300
0.0231
0.0371
0.0272
0.1117
Op,t=
0.00530
0.0328
0.0246
0.0324
0.0278
0.1127
dot
0.04005
0.0412
0.0461
0.0236
0.0296
0.1085
C wips
0.06468
0.0358
0.0442
0.0161
0.0238
0.1016
dut
0.08142
0.0424
0.0505
0.0192
0.0270
0.1048
mix-11,
0.00277
0.0243
0.0235
0.0172
0.0187
0.1026
min--12
0.00464
0.0220
0.0258
0.0163
0.0198
0.1028
5
Experiments
5.1 Compared spaces
In this section, we provide a thorough analysis to compare all metric spaces discussed in the paper, including product spaces with all signatures from [9] and the proposed overlapping space. For the non-metric dissimilarity functions, we consider d(x,, y) = c x² y, d(I, y) = c - Σ war.y; (WIPS), d(2; y) cexp(-x' y) with trainable parameters c, w2 E I, and the proposed OS-Mixed measure. We add non- measures even to the distortion setup to see whether they are able to approximate graph distances. Similarly to [9]. we fix the dimension d 10. However, for a fair comparison, fix the number of stored values for each embedding and use the hypersperical parametrization (5) instead of storing d+1 1 coordinates The training details are given in Appendix A The code of experiments is available
5.2 Graph reconstruction
Graph datasets We use the following graph datasets: the USCA312 dataset of distances between North American cities 4 (weighted complete graph). graph of computer science Ph.D. advisor- advisee relationships 11, a power grid distribution network with backbone structure (28]. a dense social network from Facebook [17). and EuCore dataset generated using email data from large European research institution [16]. We also collected a new dataset by launching the breadth-fire search on the Wikipedia category graph, starting from the "Linear Algebra" category with search depth limited to 6. Further, we refer to this dataset as WLA6; more details are given in Appendix A.2 This graph is very close being tree, although it has some cycles. We expect the hyperbolic space to give significant profit for this graph, and we observe that product spaces give almost no additional advantage. The purpose of using this additional dataset is to evaluate overlapping spaces on a dataset where product spaces do not provide quality gains. Table I lists the properties of all considered datasets.
'In Appendix R.2 we evaluate spherical spaces without this modification to compare with 9 httpp///giiib..ccom//eee/woo/o/p spaps:elllpppppisssssssssee for www.rooowommttttuuuppprereeeeeee
7

---

Table mAP graph reconstruction, top results are highlighted, top metric results are underlined
Signature
USCA312
CS PhDs
Power
Faccbook
WLA6
EuCore
E
0.9290
0.9487
0.9380
0.7876
0.7199
0.6108
110
0.9173
0.9399
0.9385
0.7997
0.9617
0.6670
S10
0.9183
0,9519
0.9445
0.7768
0.7289
0.6037
Ha
0.9247
0.9481
0,9415
0,8084
0.9682
0.6783
S
0.9316
0.9600
0.9482
0.7790
0.7307
0.6116
H5 Ss
0.9397
0.9538
0.9505
0.7947
0.9751
0.6847
HE
0.9364
0.9671
0.9508
0.7979
0.8597
0.661 1
S
0,9439
0.9656
0.9511
0.7800
0.7358
0.6169
H3 x E2 x $
0.9519
0.9638
0.9507
0,7873
0.7794
0.6492
On, 0
0.9538
0,9879
0.9728
0,8093
0,6759
0,6580
Ou, =
0.9522
0.9904
0.9762
0,8185
0,9598
0.6691
O12,t
0.9522
0.9938
0.9907
0.8326
0.9694
0.7078
dot wips mix mix- = miia- 12, ==
1
0.9983
0,8745
0.9990
0.7409
1
0.8704
0.7742
0.9994
0.8806
0.9997
0.7860
1
1
0,9021
0.8405
Distortion loss We start with the standard graph reconstruction task with distortion loss ( The goal is to embed all nodes given graph into a d-dimennsionl space approximating the pairwise graph distances between them. In this setup, all models are trained to minimize distortion ( the results are shown in Table [ It can be seen that the overlapping spaces outperform other metric spaces, and the best overlapping space (among considered) is the one with /1 aggregation and complexity = 1 Interestingl, the performance of such overlapping space is often better than the best considered product space.
We note that standard non-metric distance functions show highly unstable results for this task: for the USCA312 dataset, the obtained distortion is orders of magnitude worse than the best one. However, on some datasets (Facebook and WLA6), the performance is quite good, and for Facebook, these simple non-metric similarities have much better performance than all metric solutions. Thus, conclude that such functions are worth trying for graph reconstruction with the distortion loss, but their performance is unstable. In contrast, the overlapping spaces show good and stable results all datasets, and the proposed OS-Mixed modification (see Section 3.2) outperforms all other approaches.
Ranking loss As discussed in Section 2.1 in many practical applications, only the order of the nearest neighbors matters. In this case, it more reasonable to mAP (2). In previous work [9], mAP was also reported, but the models were trained to minimize distortion. In our experiments, we observe that distortion optimization weakly correlates with mAP optimization. Hence,
minimize B The results are shown in Table 3, and the obtained values for mAP are indeed much better than the obtained with distortion optimization [9,, i.e., it is essential to use an appropriate loss function. According to Table 3 among the metric spaces, the best results achieved with the overlapping spaces (especially for f2-aggregation with / 1). Importantly, in contrast to distortion loss, ranking based on the dot-product outperforms all metric spaces. However, using the OS-Mixed measure allows improve these results even further.
the proxy-loss defined in equation
5.3 Information retrieval
From a practical perspective, it is also important to analyze whether an embedding can generalize to unseen examples. For instance, embedding can be made via neural network based on objects' characteristics, such as text descriptions or images. This section analyzes whether it is reasonable to use complex geometries, including product spaces and overlapping spaces, in such scenario.
II Appendix B.4 also analyze > and show that performance improves as increases.
TTee gap between E2so and H258 may suspicious, but in Table 5 of g similar pattern is observed.

---

Table 4: DSSM embeddings, top three results are highlighted
Signature
Test mAP
Signature
Test mAP
F10
0.4459
H10
0.4047
E25a
0.717
S
0.4364
H25a
0.412 M
Ha
0,4492
S255
0,588
S
0.4573
Hf28
0.547
Hs x Ss
0.3295
S127
0.662
H
0.3681
H128 x S127
0.501
S
0.4616
His x Hs2
0.621
H2 E2 x $
0.3526
Sg X Sa
0.701
dot
0.4194
dot
0.738
Ou1 f
0.4562
On
0,677
Ou,
0.4498
Ou,t=
0.662
O f
0.4456
O m
0.663
O Omio
0.4447
m2iz-12,
0.655
mir 12,
0.4483
For this purpose, we trained a classic DSSM model" on private Wikipedia search dataset consisting of 491044 pairs (search query, relevant page), examples are given in Table IT in Appendix. All queries are divided into train, validation, and test sets, and for each signature, the optimal iteration was selected on the validation set. Table cobbarc all models for two embedding sizes. For short embeddings, we see that product space based on spherical geometry useful, and overlapping spaces have comparable quality. However, for large "industrial size" dimensions, the best results are achieved with the standard dot product, questioning the utility complex geometries the case of large dimensions.
Note that in DSSM-like models, the most coneeminnnnnggg task is model training. Hence, training multiple models for choosing the best configuration can be infeasible. Therefore, for small dimensions, overlapping spaces can be preferable over product spaces since they are universal and do require parameter tuning. Moreover, calculating element embeddings is usually more time-consuming than calculating distances. Hence, even though calculating distances in the overlapping space has larger complexity than in simpler spaces, it does not have noticeable effect in real applications.
5.4 Synthetic bipartite graph reconstruction
Let us additionally illustrate that some graph structures are hard embed into (considered) metric spaces. Our intuition is that the dot product is suitable for modelling popularity of items since it can be naturally reflected using vector norms. Thus, we consider a situation when there are few objects that are more popular than the other ones. To model this, we consider synthetic bipartite graph with two sets of sizes 20 and 700 with 5% edge probability (isolated nodes were removed, and remaining graph is connected). Clearly. in the obtained graph, there are a few popular nodes and many nodes of small degrees. Figure visuaaiziss the obtained graph. Table compares the performance of the best metric space with the dot-product performance. As intuition that some specific graphs are hard to embed into metric spaces, even with distortion loss. We also that our OS-Mixed approach gives the best result with margin. Thus, this experiment additionally confirms the universality of the proposed approach. We also observe that the optimization of WIPS is highly unstable this dataset, see Table 6 for details.
see, this experiment confirms
WW changed dense layers sizes in order to achieve the required embedding length and used more complex text tokenization with char bigrams, trigrams, and words, instead of just char trigrams.

---

Table 6: WIPS distortion (5 restarts; best learning rate)
avg.
worst
best
std
wips
0.092
0.100
0.078
0.0078
Omiz 02iz-12. f
0.071
0.074
0.069
0.0018
Table Bipartite graph reconstruction
mAP
distortion
E
0.777
0.094
Hio
0.794
0.095
Sin
0.796
0.096
H
0.799
0.090
S
0.796
0.094
Hs x Ss
0.798
0.090
H
0.761
0.086
S
0.773
0.092
H3 x Eg x S2
0.796
0.089
Ou, 00
0.824
0.094
On
0.803
0.082
O12,
0.814
0.092
best metric space
0.824
0.082
C dot
0.863
0.079
C wips
1
0.091
Figure Graph visualization. Red (big) nodes belong to the smaller part.
O Thi
0.986
0.083
Omia Pain--12,-- 12,
1
0.070
6
Conclusion
This paper proposed the new concept of overlapping spaces that do not require signature brute- forcing and have better comparable performance relative the best product space in the graph reconstruction task. Improvements are observed for both global distortion and local mAP loss functions. An important advantage of method is that it allows to easily incorporate distances or similarities as building blocks. The obtained overlapping-mixxe non-metric measure achieves the best results for both distortion and mAP. We also evaluated the proposed overlapping spaces in the DSSM setup, and in the case of short embeddings, product space gives better result than standard spaces, and the OS comparable In the case of long embeddings, no profit from complex spaces was found.
Acknowledgments and Disclosure of Funding
The authors would like to thank Egor Samosvat for fruitful discussions.
The work of Liudmila Prokhorenkova is partially supported by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant 075-15-2019-1996 and by the Russian President grant supporting leading scientific schools of the Russian Federation NSh2540.200 2020.. Besides that, the funding was provided exclusively by the companies listed in the authors' affiliation.
10

---

References
[1] Phillip Bonacich. 2008. Book Review: W. de Nooy, A. Mrvar, and Batagelj Exploratory
Social Network Analysis With Pajek. (2004). Sociological Methods & Research SOCIOL METHOD RES (05 2008), 563-564. https://doi. org/10. 11w71 1177/0049124107366677
[2] Silvere Bonnabel. 2013. Stochastic Gradient Descent on Riemannian Manifolds. IEEE Trans. Automat. Control 58 (2013), 2217-2229.
[3] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. 1994. Signature verification using siamese" time delay neural network. In Advances neural information processing systems. 737-744.
[4] John Burkardt. 2011. Cities City Distance Datasets. saurkaardt/datasstss//eee cittes///iiiis/esssee ci hhtml
https://people..st fsu. fdu
[5] Frederick Arthur Ficken. 1939. The Riemannian and affine differential geometry of product- spaces. (1939), 892-913.
[6] Palash Goyal and Emilio Ferrara. 2018. Graph embedding techniques, applications, and performance: A survey. Knowledge-Batt Based Systems 151 (2018), 78 94. htttp:://oi..rgg 10. 10160116j...o ..nos//..noyss....
wwwsys.sss...................... 2018.0111.000 03.03.3... 022
[7] Mihajlo Grbovic, Vladan Radosavijevic, Nemanja Djuric, Narayan Bhamidipati, Jaikit Savla, Varun Bhagwan, and Doug Sharp. 2015. E-commerce your inbox: Product recommendations at scale. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 1819-1818.
[8] Aditya Grover and Jure Leskovee. 2016. node2vec: Scalable Feature Learning for Networks. CoRR abs/1607.000e .00653 (2016).
http://arxiv/ wwwpsiii.orrg.eooooo httg//bb/16007 1atps//667000653 00653
[9] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. 2019. Learning mixed-curvature representations in product spaces. International Conference Learning Representations
(CCL))
[10] Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative Filtering for Implicit Feedback Datasets. In IEEE International Conference Data Mining (ICDM 2008). 263-272. wwwptettttteeeeeeeeeeeeeeeeeee cf.
[11] Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. 2013. Learning Deep Structured Semantic Models for Web Search using Clickthrough Data. ACM International Conference on Information and Knowledge Management (CIKM).
[12] Valentin Khrulkov, Leyla Mirvakhabova, Evgeniya Ustinova, Ivan Oseledets, and Victor Lem- pitsky. 2020. Hyperbolic image embeddings. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition. 6418-6428.
[13] Geewook Kim, Akifumi Okuno, Kazuki Fukui, and Hidetoshi Shimodaira. 2019. Representation learning with weighted inner product for universal approximation of general similarities. arXiv preprint arXiv: /902. 10409 (2019).
[14] Diederik Kingma and Jimmy Ba. 2014. Adam: A Method for Stochastic Optimization. Interna- tional Conference Learning Representations (12 2014).
[15] Marc Teva Law, Renjie Liao, Jake Snell, and Richard S. Zemel. 2019. Lorentzian Distance Learning for Hyperbolic Representations. In ICML.
[16] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM transactions Knowledge Discovery from Data (TKDD) 1, (2007), 2-cs.
[17] Jure Leskovec and Julian J. Mcauley, 2012. Learning to Discover Social Circles in Ego Networks. In Advances in Newrul Information Processing Systems 25, F. Pereira, J. C. Burges. I. Bottou, and Q. Weinberger (Eds.). Curran Associates, Inc., 539-547. http:: htttp://paper.. niw...ciiccc.......... cc/
haper/4532. learning- to wwwcoooor-sociaa
in- ego newworks.we.... pdf

---

[18] Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. 2017. Sphereface: Deep hypersphere embedding for face recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. 212-220.
[19] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.
Efficient Estimation of Word Representations Vector Space. CoRR abs/ 1 301,3781 (2013). http://dblp... .nt.puniiin uni-triee
de/db/ htb/joounals/conee caaprr//orr10 cttr//orrr111 hwbs 1301 3781
[20]
Maximillian Nickel and Douwe Kiela. 2017.
Poincaré embeddings Advances in neural informa-
for learning hierarchical representations. lion
In
processing systems. 6338-6347.
http://papers. nips. wttp:///..ppp..ppppppppppepppppe pdf
7213
[21]
Maximillian Nickel and Douwe Kiela. 2018. Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry. In International Conference on Machine Learning. 3776-3785
https://arxin: org/ abs/ 03417
[22] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe:
Global Vectors for Word Representation. In Empirical Methods in Natural Language Processing (EMNLP).
1532-1543.
http://www. www.ww.wwwbbb...... org/ httg//anooooog//1-11111
[23] Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. 2014. DeepWalk: Online Learning of Social Representations. CoRR abs/140 1403.6652 (2014). arXiv:1403.cm http://arxiv.orrg /bs/
[24] Gang Qian, Shamik Sural, Yuelong Gu. and Sakti Pramanik. 2004. Similarity between Euclidean and Cosine Angle Distance for Nearest Neighbor Queries. In Proceedings of the 2004 ACM Symposium on Applied Computing (SAC '04). Association for Computing Machinery, New York, NY, USA, 1232-1237, https://doo org. 10. /141//1799000 968151
[25] Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. 2018. Representation Tradeoffs for Hyperbolic Embeddings. In International Conference on Machine Learning. 4457-4466.
[26] Alexandru Tifrea, Gary Bécigneul, and Octavian-Eugee Ganea. 2018. Poincar' 'e GloVe:
Hyperbolic Word Embeddings. arXiv preprint arXiv:1810.06546 (2018).
[27] Pavan K Turaga and Anuj Srivastava. 2016. Springer.
Riemannian Computing in Computer Vision.
[28] Steven H Watts, Duncan J./Strogatz. 1998. Collective Dynamics of Small- World Networks.
Nature. 393:440- 442. https://doi. 10/ 1007/008----665 21742-6_130
[29] Benjamin Wilson and Matthias Leimeister. 2018. Gradient descent hyperholic space. arXiv preprint arXiv: /805.080000000 (2018).
[30] Richard C Wilson, Edwin R Hancock, Elžbieta Pekalska, and Robert PW Duin. 2014. Spherical and hyperbolic embeddings of data. IEEE transactions on pattern analysis and machine intelligence 36, 11 (2014), 2255-2269.
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 describe the limitations of your work? [Yes] See sections 5 and
(c) Did you discuss any potential negative societal impacts of your work? [No] Any possible impact depends on the usage, not the approach itself.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Yes, the paper conforms General Ethical Conduct: for example, we do not provide users' data from Section 5.3
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] The link to the code is provided and the description is given in Appendix. Users' requests for the experiment in Section[3.3 are not provided due to privacy rules; public graph datasets sufficient to reproduce the main results.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] Both in Appendix and code.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [No] In the experiments with graph reconstruction, stability is ensured by using different datasets, in the experiments with DSSM, restarting does not change the final results in any significant way.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] Technical requirements for implementation are provided with code, small experiments can be reproduced on regular computer.
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See section 5.2
(b) Did you mention the license of the assets? [No] No, although the data is available now, this may change for reasons beyond our control.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] See the WLA6 dataset.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] Indirectly, it is widely known that Wikipedia uses the Creative Commons license.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] We only collect the Wikipedia category graph.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "tLjRP8ru735", "reviewer": "Reviewer_VsLk", "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", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper defines overlapping spaces, proposes an optimization scheme and gives an complete experimental evaluation.\nThe work is original, provides non trivial results and is supported by experimental evidence.\n\nMy main concerns are about the writing of the paper that may be improved and about some claims that should be provided with stronger evidence.\nThe 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.\nThe 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.\nAgain, in the optimization section, the procedure that is used instead than RSGD should be supported by stronger evidence.\nThe 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.\n\nThat being said, I think that it is a good paper that extends in an appropriate way the product space, allowing to obtain better results.\n\n\nMinor comments:\n- l56: \"mertic\" should read metric\n- 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? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion about the limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "MS1rKxIbCm", "reviewer": "Reviewer_ndZi", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nGenerally 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.\n\nTechnically 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:\n\n\n- 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 \n  - (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.\n  - (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.\n\n- 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? \n\n- 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.\n\nTo 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.\n\nReferences:\n- [1] Gu et al. Learning mixed-curvature representations in product spaces. ICLR 2019. https://openreview.net/forum?id=HJxeWnCcF7 \n\n\n\n**After authors’ responses and discussion**: Some of my concerns are addressed and I increase my score from 6 to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "8KrJ6THkZYn", "reviewer": "Reviewer_P7eR", "summary": "This paper introduces a model which uses a learned weighted combination of spaces ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "### Overview\n\n**Originality:** This work is (almost literally) a novel combination of well-known methods, and demonstrates sufficient originality.\n\n**Quality:** The submission is technically sound, however:\n\n- 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.)\n- 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.\n\nThat said, the authors perform sufficient empirical analysis of their model, and are very honest about the strengths and weaknesses of their approach.\n\n**Clarity:** The submission is clearly written and well organized, the model should be easily reproducible from their description.\n\n**Significance:** The authors demonstrate improvement on various tasks as well as various aspects of training (see below) of interest to researchers.\n\n---\n\n### Specific Comments / Questions\n\n**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.\n\n**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?\n\n**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.\n\n**L239:** (minor) \"better than for the best\" → \"better than the best\"\n\n**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.\n\n**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.\n\n**Section 5.4, 6:** These sections seem a bit rougher, grammatically, than the others.\n\n**Questions / Extensions:**\n\n- 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.\n- 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.)\n\n[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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "2elMcPe-CKW", "reviewer": "Reviewer_oDDg", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\n+ The efficiency of combining different spaces is a crucial problem.\n+ Experimental results of this paper are promising.\n\nConcerns:\n- 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.\n- The organization of this paper should be improved. The background and related work could be introduced in a more concise way.\n- 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately discussed these points.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)