Normed Spaces for Graph Embedding
Authors: Diaaeldin Taha
Wei Zhao
J. Maxwell Riestenberg
Michael Strube
Venue: Accepted by TMLR ()

Abstract: Theoretical results from discrete geometry suggest that normed spaces can abstractly embed finite metric spaces with surprisingly low theoretical bounds on distortion in low dimensions. Inspired by this theoretical insight, we highlight in this paper normed spaces as a more flexible and computationally efficient alternative to several popular Riemannian manifolds for learning graph embeddings. Normed space embeddings significantly outperform several popular manifolds on a large range of synthetic and real-world graph reconstruction benchmark datasets while requiring significantly fewer computational resources. We also empirically verify the superiority of normed space embeddings on growing families of graphs associated with negative, zero, and positive curvature, further reinforcing the flexibility of normed spaces in capturing diverse graph structures as graph sizes increase. Lastly, we demonstrate the utility of normed space embeddings on two applied graph embedding tasks, namely, link prediction and recommender systems. Our work highlights the potential of normed spaces for geometric graph representation learning, raises new research questions, and offers a valuable tool for experimental mathematics in the field of finite metric space embeddings. We make our code and data publically available \footnote{\url{https://github.com/andyweizhao/graphs-normed-spaces}}.

Published in Transactions on Machine Learning Research (05/2024)
Normed Spaces for Graph Embedding
Diaacldin Taha"
diaackdin. taka Brris. mmp.dd de
Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany
Wei Zhao"
wei.zhao@abdn.ccc
University of Aberdeen, Aberdeen, United Kingdom
J. Maxwell Riestenberg
maz.riestenbery Emiss
Maa Planck Institute for Mathematics in the Sciences, Leipzig, Germany
Michael Strube
michael, stabbveellttuuehh--la.e
Heidelberg Institule for Theoretical Studies, Heidelberg, Germany
Reviewed on OpenReview: https: // optpr//veeer..ee....mmme net/ forum? id= 4E2XLydJiv
Abstract
Theoretical results from discrete geometry suggest that normed spaces can abstractly embed finite metric spaces with surprisingly low theoretical bounds on distortion in low dimensions. Inspired by this theoretical insight, we highlight in this paper normed spaces as a more flexible and computationally efficient alternative to several popular Riemannian manifolds for learning graph emboddings. Normed space emboddings significantly outperform several popular manifolds on large range of synthetic and real-world graph reconstruction benchmark datasets while requiring significantly fewer computational resources. We also empirically verify the superiority of normed space embeddings growing families of graphs associated with negative, zero, and positive curvature, further reinforcing the flexibility of normed spaces in capturing diverse graph structures as graph sizes increase. Lastly, we demonstrate the utility of normed space embeddings on two applied graph embedding tasks, namely, link prediction and recommender systems, Our work highlights the potential of normed spaces for geometric graph representation learning, raises new research questions, and offers valuable tool for experimental mathematics in the field of finite metric space embeddings. We make our code and data publically available !
1 Introduction
Graph representation learning aims to embed real-world graph data into ambient spaces while sufficiently preserving the geometric and statistical graph structures for subsequent downstream tasks and analysis. Graph data many domains exhibit non-Fuclidean features, making Euclidean embedding spaces an unfit. choice. Motivated by the manifold hypothesis (see, e.g., Bengio et al. (2013)), recent research work has proposed embedding graphs into Riemannian manifolds Chamberlain al. 2017 Defferrard et al. 2020 Grattarola et al. 2020 Gu et al.) 2019 Tilrea et al. 2019). These manilolds introduce inductive biases, such as symmeery and curvature, that can match the underlying graph properties, thereby enhancing the quality of the embeddings. For instance, Chamberlain et al. (2017) and Defferrard et al. (2020) proposed embedding graphs into hyperbolic and spherical spaces, with the choice determined by the graph structures.
https://github. htwpscuuu.co//ndyeeeeeeeee www//nddweizzao/ggreeee http///gaaaaaaaeeeee spaces These contributed equally work.

---

Published in Transactions on Machine Learning Research (05/2024)
More recently, López et al. (López et al. 2021 López et al. 2021) proposed Riemannian symmetric spaces framework that unifies many Riemannian manifolds previously considered for representation learning. They also highlighted the Siegel and SPD symmetric spaces, whose geometries combine the sought-for inductive biases of many manifolds. However, operations in these non- non-Enclidean spaces are computationally demanding and lechnically challenging, making them impractical for embedding large graphs.
In this work, we highlight normed spaces, particularly & and t as a more flexible, more computationally efficient, and less technically challenging alternative to several popular Riemannian manifolds for learning graph embeddings. In particular, normed spaces are empirically observed to be easier to train and to perform better in general graph embedding settings that leverage gradient descent. Our proposal is motivated by theoretical results from discrete geometry, which suggest that normed spaces can abstractly embed finite metric spaces with surrrsingly low theoretical bounds on distortion in low dimensions, This is evident in the work of Bourgain 1985);; Johnson & Lindenstrauss) (1884) and Johnson et al. (1987).
We evaluate the representational capacity of normed spaces on synthetic and real-world benchmark graph datasets through graph reconstruction task. Our empirical results corroborate the theoretical motivation; observed in our experiments, diverse classes of graphs with varying structures can be embedded in low-dimensional normed spaces with low average distortion. Second, we find that normed spaces consistently outperform Euclidean spaces, hyperbolic spaces, Cartesian products of these spaces, Siegel spaces, and spaces of SPD matrices across test setups. Further empirical analysis shows that the embedding capacity of normed spaces remains robust across varying graph curvatures and with increasing graph sizes. Moreover, the computational resource requirements for normed spaces grow much slower than other Riemannian manifold alternatives the graph size increases. Lastly, we showcase the versatility of normed spaces in two applied graph embedding tasks, namely, link prediction and recommender systems, with the & normed space surpassing the baseline spaces.
As the field increasingly shifts towards tochnically challenging geometric methods, our work underscores the untapped potential of simpler geometric techniques. As demonstrated by our experiments, normed spaces set a compelling baseline for future work geometric representation learning.
2 Related Work
Graph embeddings are mappings of discrete graphs into continuous spaces, commonly used as substitutes for the graphs in machine learning pipelines. There are numerous approaches for producing graph embeddings, and we highlight some representative examples: (1) Matrix factorization methods (Belkin & Niyogi 2001
Cai et al., 2010; Tang & Liu 2011) which decompose adjacency or Laplacian matrices into smaller matrices,
providing robust mathematical vector representations of nodes; (2) Graph neural networks (GNNs) (Kipf & Welling 2017
Velicković et al. 2018: Chami et al. 2019a) which use saassagg-pssinng to aggregate node
information, eleectively capluring local and global statistical graph structures; (3) Autoencoder approaches
Kiipf & Welling, 2016; (Salha et al. 20199) which involve a two-step process of encoding and decoding to generate graph embeddings; (4) Random walk approaches (Perozzi et al. 2014 Grover & Leskovee, 2016
Kriege 2022 which simulate random walks the graph, capturing node proximity in the embedding space
through co-occurrence probabilities; and (5) Geometric approaches (Gu et al. 2019 Tópez et al.) 2021
which leverage the geometric inductive bias of embedding spaces to align with the inherent graph structures, typically aiming to learn approximate isometric embeddings of the graphs in the embedding spaces. We note that these categories are not mutually exclusive. For instance, matrix factorization can be seen as a linear autocncoder approach, and geometric approaches can be combined with graph neural networks. Here we follow previous work (Gu et al., 2019: López et al. 2022 López al., 2021 Giovanni et al. 2022 and use a geometric approach to produce graph embeddings in normed spaces.
Recently, there has been a growing interest in geometric deep learning, especially in the use of Riemannian manifolds for graph embeddings. Those manifolds include hyperbolic spaces (Chamberlain et al. 2017
Ganea et al. 2018 Nickel & Kiela 2018 López et al. 2019), spherical spaces (Meng et al. 2019 Defferrard
ct al.) 2020), combinations thereof (Bachmann et al. 2020 Grattarola et al. 2020 Law Stam 2020),
Cartesian products of spaces (Gu et al.) 2019 Tifrea et 2019). Grassmannian manifolds (Huang ct al.
2018), spaces of symmetric positive definite matrices (SPD) (Huang & Gool 2017 Cruceru et al. 2020
2

---

Published in Transactions on Machine Learning Research (05/2024)
and Siegel spaces (López al.,
2021 All these spaces are special cases of Riemannian symmetric spaces, also known as homogeneous spaces. Non-homogeneous spaces, such as Giovanni et al. (2022). have been explored for embedding heterogeneous graphs. Other examples of mathematical spaces include Hilbert spaces (Sriperumbudur ct al., 2010 Herath et al. 2017) Lic groups (Falorsi et al. 2018) (such as the torus (Ebisu & Ichise 2018)), non-abeliag groups (Yan el al. 2020 and useudo-Riemaunin manifolds of constant nonzero
curvature [Law & Stam 2020). These spaces introduce inductive biases that align with critical graph features.
For instance, hyperbolic spaces, known for embedding infinite trees with arbitrarily low distortion (Sarkar) 2012 are particularly suitable for hierarchical data. Though the computations involved in working with these spaces are tractable, they incur non-trivial computational costs and often pose technical challenges. In contrast, normed spaces, which we focus on in this work, avoid these complications.
3 Theoretical Inspiration
In discrete geometry, abstract embeddings finite metric spaces into normed spaces, which are characterized by low thcorctical distortion bounds, have long been studiod. Here we review some of the existence results that motivated our work. These results provide a ralionale for using normed spaces embed various graph types, much like hyperbolic spaces are often matched with hierarchical graph structures. While these results offer strong motivation for our experiments, we emphasize that these theoretical insights do not immediately translate to or predict our empirical results. Theoretical results and embedding spaces investigated in this work are summarized in Tables and Appendix).
It a well-known fact that any n-pointed metric space can theoretically be isometrically embedded into & For many classes of graphs, the theoretical bound on dimension can be substantially lowered: the complete graph Kn can thcorctically be isometrically embeded in 1| ([1=8,(m)] every tree T with n vertices can theoretically be isometrically embedded in Ex (Olggg) and every tree T with leaves can theoretically be isometrically embedded in e (llog)) (Linial et al. 1995
Bourgain showed that similar dimension bounds can be obtained for finite metric spaces in general by relaxing the requirement that the embodding isometric. A map f X -> Y between two metric spaces xX,dx) and dy) is called D-embedding for a real number D 2 1 if there exists number 0 such that for all 21, x2 X,
T dx x2) S (y)((()), s D (x1,)
The infirnum of the numbers D such that f is a D-embedding is called the distortion of f. Every n-point metric space (X,d) can be embedded in an O(log -)dimennsionnal Euclidean space with an O(logn) distortion
Bourgain 1985
Johnson and Lindenstrauss obtained stronger control on the distortion at the cost of increasing the embodding dimension. Any set of points in Euclidean space can be mapped to R where = O (lgg) with distortion
most 1 + e in the distances. Such mapping may be found in random polynomial time (Johnson & Lindenstrauss 1984).
Similar embedding theorems were obtained by Linial et al. in other fp-spacss In random polynomial-time (X,d) d) may be embedded in Ep (logg) (for any S p S 2), with distortion Ologn) LLnial al. 1995 or into Ooloo" n) (for any p >>> 2), with distortion O(logn) (Linial et al. 1995).
When the class of graphs is restricted, stronger embedding theorems are known. Krauthgamer et al. obtain embeddings with bounded distortion for graphs when certain minors are excluded; we mention the special case of planar graphs. Let X be an n-point edge-weighted planar graph, equipped with the shortest path metric. Then X embeds into e (logn) with ((1) distortion (Krauthgamer et al. 2004).
Furthermore, there are results on the limitations of embedding graphs into ly-spaces For example, Linial et al. show that their embedding result for 1 S p I 2 is sharp by considering expander graphs. Every embedding of an n-vertex constant-degroo expander into an l, space, 2 2 p 2 1, of any dimension, has distortion Q(log n). The metric space of such a graph cannot be embedded with constant distortion in any normed space of dimension O(logn) n) (Linial al. 1995).
3

---

Published in Transactions on Machine Learning Research (05/2024)
4 Normed Space
4 Enclidean Space
2 Normed Space
H Poincare Hyperbolic Space
H x H Product Poincare Spaces
SPD Symmetric Space
Embedding distortion across spaces on a small synthetic graph, with color indicating distortion levels (the absolute difference between graph edge and norm distances). The graph embeds well in the L and loc normed spaces but endures distortion in other spaces.
Figure 1:
These theoretical results illustrate the principle that large classes of finite metric spaces can in theory be abstractly embedded with low theoretical bounds on distortion in low dimensional normed spaces. Furthermore, the distortion and dimension can be substantially improved when the class of metric spaces restricted. This leaves open many practical questions about the embeddability of real-world data into normed spaces and translating these theoretical results into predictions about the empirical results from experiments.
4 Experiments
We evaluate the graph embedding capacity of normed spaces alongside other popular Riemannian manifolds in the graph reconstruction task on various synthetic and real-world graphs ($4.1).
We analyze further (a) the space capacity and computational costs for varying graph sizes and curvatures; (b) space dimension; and in Appendix E. we extend our analysis to (c) expander graphs and (d) the asymmetry of the loss function. Additionally, recommender systems ($4.3). For link prediction, we investigate the impact of normed spaces four popular graph neural networks.
evaluate normed spaces in two tasks: link prediction ($4.2) and
4.1 Benchmark: Graph Reconstruction
Shortest Path Metric Embeddings. A metric embedding mapping f Y between two metric spaces (X,dx) and dy, Ideally, would desire metric embeddings to be distance preserving. In be practice, accepting some distortion be necessary. In this case, the overall quality of an embedding evaluated by fidelity measures such as the average distortion Davg and the mean average precision mAP (cf. Appendix D.I for the definitions). A special case metric embedding is the shorlest path metric embedding, also known as Now-distortion or approzimate isometric embedding, where X the node set V a graph G (V,E) and dg corresponds to the shortest path distance within g. These embeddings represent or reconstruct the original graph G in the chosen embedding space Y, idcally preserving the desirable geometric features of the graph.
4

---

Published in Transactions on Machine Learning Research (05/2024)
Learning Framework. To compute these embeddings, we optimize a distance-based loss function inspired
by generalized MDS (Bronstein et al., 2006) and which was used earlier in, e.g., Gu et al. (2019) López et al. (2021); Giovanni et al. (2022). Given graph distances dg(u, between all pairs u, E V of nodes connected by a path in 9, which we denote u ~ v, the loss is defined as:
{(f) - (1)
2 -1. -1.
(1)
dg(u,
where (I)),, is the distance between the corresponding node embeddings in the target embedding space. In this context, the model parameters are finite collection of points f(u) in Y, each indexed by a specific node u of G. These parameters, i.e, the coordinates of the points, are optimized by minimizing the loss function through gradient descent. This loss function treats the distortion of different path lengths uniformly during training. We provide more context for the loss function in Appendix B We also empirically evaluate
embeddings learned by the distance-based loss function from eq. (1) against another popular distance-based loss function, namely mean squared error loss, in Appendix D.1
Motivation. In geometric machine learning, graph reconstruction tasks have achieved "de facto" bench- mark status for empirically quantifying the representational capacity of geometric spaces for preserving graph structures given through their local close neighborhood information, global all-node interactions, or an intermediate of both (Nickel & Kiela 2017 2018: Gu et al., 2019 Cruceru et. al. 2020 López et al. 2021 López et al.] 2021). This fidelity to structure is crucial for downstream tasks such as link prediction and recommender systems, where knowing the relationships between nodes or users is key. Other applications
include embedding large laxonomies. For instance, Nickel & Kiela (2017) and Nickel & &Kiela (2018) proposed embedding WordNet while maintaining its local graph structure (semantic relationships between words), and applied these embeddings to downstream NLP tasks. Additionally, low-distortion metric embeddings have applications in approximation algorithms (Linial et al. 1995|, online algorithms (Bansal et al.] 2015),
and distributed algorithms (Khan et al. 2008). We note that though we employ a global loss function, the resulting normed space embeddings preserve both local and global structure notably well.
Experimental Setup. Following the work of Gu et al. (2019), we train graph embeddings by minimizing the previously mentioned distance-based loss function. We follow López et al. (2021), and we do not apply any scaling to cither the input graph distances or the distances calculated in the space, unlike carlier work (Gu el al. 2019 Cruceru el al. 2020). We report the average results across five runs in terms of (a) average distortion Daog and (b) mean average precision (mAP). We provide the training details and the data statistics in Appendix D.I
Baseline Comparison. We compare the performance of normed metric spaces with many other spaces for graph embedding. These spaces fall under three classes: (a) Normed spaces: R200 R220 and 2 (b)
Riemannian symmetric spaces (Cruceru et al. 2020 López et al.
2021 López et al. 2021), incl. the space
of SPD matrices: SPDg. Siegel upper half spaces: Sh. S S bounded symmetric spaces: B1_ B1.
B4 hyperbolic spaces (Nickel & Kiela 2017):
: 1H
(Poincaré model), and product spaces (Gu et al. 2019
H x H (c) Cartesian product spaces involving normed spaces: R. x Lx I x H R: lTto
H R and
RI x HH (d) pscudo-Eaclidean space (Goldfarb) 1985 Vishwakarma & Sala 2022 R19t. The notation
for all metrics follows standardized format: the superscript scales with the space dimension, and the subscript denotes the specific distance metric used (e.g. R for Riemannian and for Finsler). Following López et al. 2021). we ensure uniformity across metric spaces by using the same number of free parameters, specifically a dimension of 20; and more importantly, we are concerned with the capacity of normed space at such low dimensions where non-Euclidean spaces have demonstrated success for embedding graphs (Chami et al. 2019b] Gu et al. 2019). We also investigate the capacities of spaces with growing dimensions, observing that other spaces necessitate much higher dimensions to match the capacity of the foo normed space (see Tab. 4p. Note that S and 8.t have n(n + 1) dimensions, and SPD" has a dimension of n(n + 1)/2. We elaborate on these metric spaces in Appendix A.
Synthetic Graphs. Following the work of López et al. (022)) ), we compare the representational capacity of various geometric spaces on several synthetic graphs, including grids, trees, and their Cartesian and rooted
5

---

Published in Transactions on Machine Learning Research (05/2024)
4D GRID
TREE
TREE TREE
TREE GRID
GRID TREE
(IVI: (E)
(625, 2000)
(364, 363)
(225, 420)
(775, 1270)
(775, 790)
Davg
mAP
Dang
mAP
Daug
mAP
Davg
mAP
Davg
mAP
R22
1.08 +:000
100.00
1.62::0.02
73.56
1.22:40001
100.00
1.22::0011
71.91
0.75:40.02
60.13
R2
11.24:0.00 00
100.00
3.92:10.04
42.30
9.78:10.00
96.03
3.8620.02
31.21
4.28 0.
27.50
R7
0.13+0000
100.00
0.15#0.01
100,00
0.58+0.01
100.00
0.09=0.01
100.00
0.23=0.02
99.39
25.23:1.005
63.74
0.54::0.02
100.00
20.59=0.11
75.67
14.56:0.27
44.14
14.6240.11
30.28
SPD
11.24:1:.00 00
100.00
1.79:10.02
53.92
8.83:10.01
98.49
1.36:0.02
62.31
1.83-0.00 00
72.17
Sk
11:27:10.0
100.00
1.35++0.02
78.53
8.68:0.002
98.03
1.45=+0.09
72.49
1.54
76.66
S
5.92:10.06
99.61
1.23:10.28
99.56
3.31:10.06
99.95
10.88$0.19
63.52
10.48:0.21
72.53
ST.
0.01=0.00
100.00
0.70:20.02
91.57
1.0
100.00
1.03=0000
78.71
0.84+0.00
80.52
BR
11.28:#0.01
100.00
1.27:+0.05
74.77
8.74=0.09
98.12
2.88+0.32
72.55
2.76+ 11
96.29
7.32::0.16
97.92
1.51:0..13
99.73
4.26:10.26
99.70
1.77
73.80
0.15+0.885
90.51
15
0.391:0.02
100.00
0.77:10.02
94.64
1.28:10.16
100.00
1.09=0.03
76.55
0.99:10.01
81.82
B x R
0.16++0.00
100.00
0.63++0.02
99.73
0.62:#0.00
100.00
0.34+0.01
99.84
0.60++0.01
94.81
R Hg
0.55++0.00
100.00
1.13+0001
99.73
0.62:+0.01
100.00
1.76+00.2
50.74
1.65+
89.47
B H
11.24 00
100.00
1.19:0.04
100.00
9.30+10.04
98.03
2.15#0.05
58.23
0.03:0000
97.88
B
x H/
0.14+0.000 00
100.00
0.22:10.0
96.96
1.91:0.01
99.13
0.15=00.11
99.96
0,57+00.01
90.31
H H
18.74+00.01
78.47
0.65++0.02
100.00
8.60
97.63
1.08+0.06
77.20
2.80++0.65
84.88
1,11.
5.65++0.02
99.87
4.91++0.08
33.38
3.46++0.04
99.70
0.32++0.03
40.09
4.933+00.03
27.53
Table 1: Results on the five synthetic graphs. Lower Dong is better. Higher mAP is better. Metrics are given as percentages.
products. Further, we extend our analysis to three expander graphs, which can be considered theoretical worst-case scenarios for normed spaces embedding theorems (Linial al.) 1995), and thus are challenging sctups for graph reconstruction. Tab. and report the results on synthetic graphs and expanders.
Overall, the foe normed space largely outperforms all other metric spaces considered on the graph configurations we examine. Notably, it excels over manifolds typically paired with specific graph topologies. For instance, the fxo space siguificantly outperforms hyperbolic spaces, and surpasses Cartesian products of hyperbolic spaces and pseudo-Euule Euclidean space on embedding tree graphs. Further, the foe space outperforms sophisticated symmotric spaces such as S/ and B3, on the graphs with mixed Euclidcan and hyperbolic structures (TREE GRIDS and GRIDS o TREE), although these symmetric spaces have compound geometries that combine Euclidean and hyperbolic subspaces. We also observe competitive performance from the l space, which outperforms the l2, hyperbolic, and symmetric spaces equipped with Riemannian and Finsler infinity metrics. Interestingly, combining lx and hyperbolic spaces using the Cartesian product does not bring added benefits and is less effective than using the 6x space alone. Further, combining & and Eo spaces yields intermediate performance between the individual & and loo spaces, due to the substantial performance gap between these two spaces. These findings underline the high capacity of the &, and foo spaces, aligning with our theoretical motivations,
In Tab. we report graph reconstruction results for three expander graphs, namely Vargulis-Gabber-GCC Paley, and Chordal-Cycle graphs (Bollobás & Bollobés 1998 Lubotzky 1994 Vadhan et al. 2012). We note that expanders are considered representative of complex structures due to their high degree of sparsity and connectivity. As observed in our results, none of the metric spaces investigated align well with these intricate structures, leading to substantial distortion of graph structures across all spaces. Overall, graph structures the ε and lo spaces endure much lower distortion in terms of Dang compared to the other spaces. Importantly, even with considerable distortion, the & and fxo spaces yield favorable mAP scores, particularly CHORDAL. This suggests that the CHORDAL graph, while not isomctrically embodded, is nearly isomorphic in these spaces, indicative of high-quality embeddings.
In sum, these results affirm that the & and loo spaces are well-suited for embedding graphs, showing robust performance when their geometry closely, or even poorly, aligns with the graph structures.
World Graph Networks. We evaluate the representational capacity of metric spaces on five popular real-world graph networks. These include (a) USCA312 (Hahsler & Hornik 2007) and EUROROAD (Subelj
6

---

Published in Transactions on Machine Learning Research (05/2024)
MARGULIS
PALEY
CHORDAL
[ LE))
(625, 2500)
(101, 5050)
(523, 1569)
Davg
mAP
Davg
mAP
Dang
mAP
R1
13.1=0.00
87.97
22.7+0.00
65.84
10.7=0.01
99.66
R
14.040.01
83.99
23.6+0.02
60.80
12.8=0.01
87.79
R20
14.240.01
82.73
16.1
66.88
10.520.01
98.39
16.8:00011
69.47
23.810.02
60.76
22.820002
59.19
SPD
14.110.01
84.98
23.610.01
61.76
12.810.01
77.59
St
24.2+0002
2.24
26.0+0.01
51.94
38.1 10000
1.40
By,
24.1110.01
2.17
26.510001
52.97
37.210.01
1.43
B x R
13.8:0000
87.25
20.400.01
60.09
10.6 10.620.01
99.17
R F
14.2::0.00
83.63
23.3100000
62.77
11.7=0.00
82.95
2 E
14.4:0000
79.12
28.710.01
60.72
12.820.00
81.93
R 1 Hg
14.610.01
86.26
20.810.00
60.57
12.120.01
88.98
BLD BR
15.4+0.01
75.77
23.740.01
60.33
17.2=0.00
58.25
B 110+-10- PSR
15.740.02
45.25
24.740.01
56.78
9.140.02
76.48
Table 2: Results on the three expander graphs. Metrics are given as percentages.
USCA312 (312, 48516)
BIO-DISASSOME (516, 1188)
CSPHD
EUROROAD
FACEBOOK
(VIEE)
(1025, 1043)
(1039, 1305)
(4039, 8823-)
Davy
Davy
mAP
Davg
mAP
Daop
mAP
Davg
mAP
B7
0.29:10.01
1.6220.01
89.14
1.59:0.02
52.34
1.73:0.011
93.61
2.38
31.22
R2
0.18=0.01
3.83:20001
76.31
4.0410.01
47.37
4.50:10.00
87.70
3.16#0.01
32.21
0.95++0.2
0.53:10.01
98.24
0.42=0001
99.28
100::0.01
99.48
0.71:10.02
42.21
HR
2.30++0.02
6.83+0.08
91.26
22.42-+0.23
60.24
43.56:10.44
54.25
3.7240
44.85
SPD
0.21
2.54+0.00
82.66
2.92+t0.11
37.88
19.54:1:.99
92.38
2.92=0.05
33.73
Sh
0.28
0.40
87.01
4.30::0.18
59.95
29.21110.91
84,92
3.07=0004
30.98
St
0,57
2.78#0.49
93.95
27.27=1.00
59.45
16.82+1.00 002
72.03
1.90=0.11
45.58
Sh
0.18
1.55#0.04
90.42
1.50++0.03
64.11
3.79:+0.07
94.63
2.37=#0.07
35.23
By
0.24+0.07
2.69+0.10
28.65++3.99
62.66
53.45:1-2.65
3.58
30.35
0.2110004
4.5820.63
90.36
26.32466166
34.91
62.69:12.28
48.75
2.18#0.15
39.15
0.18:0.07
1.5120022
90.41
2.96:10.91
67.55 67.58
21.98:10.22
91.63
5.05 03
39.87
R R
0.47:10.01
1.560.011
98.22
1.38+00.2
89.18
L.65100022
98.34
2.1620.02
39.90
RE H
0.72+0001
1.9940.01
93.78
1.83+0.02
78.10
2.26:10.02
2.77=0.02
33.79
R/ x H
0.18:0.00
2.52+0.02
91.99
3.06:20.02
73.25
4.24:10.02
89.93
2.8020.01
34.26
2 x H
0.42:40.02
1.42:0.02
96.51
1.16::0.01
76.91
1.77:00.01
97.38
1.41:20.02
35.03
H HIR
0.47:#0.18
2.57=20.05
95.00
7.02+1107
79.22
23.30:1:.62
75.07
2.51=00.0
36.39
B 30
0.41++0.01
3.87:10.02
3.17::0.02
2.49:10.01
90.33
5.10=0.08
20.36
Table 3: Results on the five real-world graphs. Metrics are given as percentages.
& Bajec 2011 representing North American city networks and European road systems respectively; (b) BIO-DISE SE-DDIEAASOME Goh et al. 2007), biological graph representing the relationships between human disorder and diseases and their genetic origins; (c) CSPHD (Nooy et. al. 2011 graph of Ph.D. advisor-ad visee visee relationships in computer science and (d) FACEBOOK (McAuley & Leskovec 2012), a dense social network from Facebook.
In Tab. 3 the and lox spaces generally outperform all other metric spaces on real-world graphs, consistent. with the synthetic graph results. However, for USCA312 a weighted graph of North American cities where edge lengths match actual spherical distances the inherent spherical geometry limits effective embedding into the E and foo spaces at lower dimensions.
Graph Representational Capacity. We assess the capacity of the metric spaces for embedding graphs of increasing size, focusing on trees (negative curvature), grids (zero curvature), and fullerenes (positive curvature). See the illustrations of these graphs in Appendix F For trees, we fix the valency and vary the tree height from to 7; for 4D grids, we vary the grid dimension from number of carbon atoms from 20 to 240. We report the average results across three runs.
for fullerencs, we vary the
7

---

Published in Transactions on Machine Learning Research (05/2024)
Toee
God
Filleeenex
R1
R0
Theeeten
Tosteting
M52 x 635
00-
R11 x9]
R12 B1
SPDg
100
150
200
Time Birght
Brdd Stce
Carhon Stne
Figure 2: Metric space capacities with growing graph size and unnoticeable distortion variance.
Fig. (left) reports the results on Irees. Within the range of computationally feasible graphs, we see that as graph size grows, the capacity of all metric spaces, barring the fo space and its product with hyperbolic space, improves significantly before platcauing. In hyperbolic spaces, which are not scale-invariant embodding trees with high fidelity to all path leugths could require scaling (see, e-g., [Sarkar] (2012). [alaa al. (2018) This be seen in the high embedding distortion of small trees, specifically those with height less than 4. Further empirical analysis demonstrates that the optimization goal localizes unavoidable distortion to some paths of short combinatorial lengths and their contribution to the average loss becomes smaller with increased size since there are relatively fewer of them. In contrast, the for space consistently exhibits a high capacity, largely unaffected by graph size, and significantly outperforms the hyperbolic space within the observed range.
Fig. (center) reports the results on 4D grids with zero curvature. We find that the metric spaces whose geometry aligns poorly with grid structures, such the & space, the hyperbolic space and their products, exhibit weak representational capacity. In contrast, the & and foo spaces preserve grid structures consistently well as the graph size increases. Fig. 2 (right) reports the results on fullerenes with positive curvature, Given that none of the spaces considered feature a positively curved geometry, they are generally ill-suited for embedding fullerenes. However, we see that the l and fx spaces and the product spaces accommodating either of these two spaces consistently outperform others even as the number of carbon atoms increases.
Overall, these results show that the & and foc spaces consistently surpass other metric spaces in terms of representation capacity. They exhibit small performance fluctuation across various curvatures and maintain robust performance within graph configurations and size ranges consider.
Training Efficiency. Fig. 3 compares the training time for different metric spaces grids and trees with growing size. The training time grows as C(space) x O(number of paths), where C(space) is constant that depends on the embedding space. Among these spaces, SPD demands the highest amount of training efforts, even when dealing with small grids and trees. For other spaces, the training time differences become more noticeable with increasing graph size. The largest difference appears at a grid size of 7 and a tree height of 6: The L,, l,, and foo normed spaces exhibit the highest efficiency, outperforming product, hyperbolic and SPD spaces in training time.
These results expected given that transcendental functions and sigendecompositionnn computationally costly operations. Overall, normed spaces show high scalability with increasing graph size. Their training time grows much slower than product spaces and Riemannian alternatives.
Space Dimension. Tab. 4 compares the results of different spaces across dimensions the BIo-DISEASOME dataset. The surveyed theoretical results suggest that in sufficiently high dimensions, space capacities appear to approach theoretical limits, leading to the possibility that the performance of different spaces can become similar. However, we find that other spaces necessitate very high dimensions to match the capacity of the txo normed space. For instance, even after tripling space dimension, H and SPD) still perform much worse than R220 R&C rivals 1R only in mAP. R-33 R233 surpasses 1R mAP but lags behind in Daug- López ct al. (2021) similarly evaluated Euclidean, hyperbolic and spherical spaces, their products, and Siegel space at 306. Their best results BIO- Bio-DISRASOME were Davg = 0.73 and mAP 99.09 for S In contrast,
8

---

Published in Transactions on Machine Learning Research (05/2024)
4D Grid
Tree
3000
1200
Training (Secorids)
Toatning Time (Seonadi)
1000
2000
600
R 19
1000
400
RE x 19
200
# H
SPD2
Grid Size
Tree Height
Figure 3: Training time scales up as the graph size increases.
fo and f x el achieved Davg = 0.5 + 0.01 and mAP 99.4, respectively. These results show that normed spaces efficiently yield low-distortion emboddings much lower dimensions than other spaces.
36
66
Dava
MAP
Davg
mAP
Daca
mAP
R
1.6+0.01
89.1
1.6:0.011
94.3
1.7=0.01
98.1
R
3.840.01
76.3
3.840.01
85.9
3.9:0.01
86.2
RY
0.5100011
98.2
0.510.01
98.3
0.610.01
99.2
6.810.08
5.8110.66
5.9.1.05
93.2
2.3:0.00
82.6
2.4:0.02
2.320.022
1.540.011
98.2
1.2::0.01
99.4
1.4.1.011
99.8
B
1.9:0.01
93.7
18800.01
95.8
1.7#0.01
98.4
R
2.511.022
91.9
2.6.10.02
92.3
2.5.1.011
94.6
1.440.02
96.5
1.140.02
0.8:0.01
98.8
2.3+0.05
95.0
2.540.04
97.1
2.640.05
97.6
Table 4: Results BIO-DISFASOME. When takes 20, 36, 66, l in SPD takes 6, 8, 11. Metries are
given percentages.
4.2 Application 1: Link Prediction
Experimental Setup. We comparably evaluate the impact of normed spaces on four popular architectures
of graph neural networks (GNNs), namely GCN (Kipf & Welling, 2017). GAT (Velččković et al. 2018). SGC
(Wu ot al. 2019) and GIN (Xu et al. 2019). Following Kipf Welling (2016); Chami et al. (2019a) we evaluate GNNs the link prediction lask on two cilation network dalasels: Cora and Citeseer (Sen et al., 2008). This task aims to predict the presence of edges (links) between nodes that are not seen during training. We split each dataset into train, development and test sets corrosponding 70%, 10%, 20% of citation links that sample at random. We report the average performance in AUC across five runs. We provide the training details in Appendix D.2
Results. Tab. 5 reports the results of GNNs across different spaces for link prediction. While previous works showed the superiority of hyperbolic over Euclidean space for GNNs at lower dimensions on these datasets (Chami et al.) 2019a 9a. Zhao el al. 2023), our findings indicate the opposite (see the results from Hy and Ry,)) This is attributed to the vanishing impact of hyperbolic space when operating GNNs in a larger dimensional space (with up to 128 dimension to achieve optimal performance on development sets). The L normed space consistently outperforms other spaces (including the loc and product spaces), demonstrating its superiority for link prediction.

---

Published in Transactions on Machine Learning Research (05/2024)
CORA
CITUSEER
GCN
GAT
SGC
GIN
GCN
GAT
SGC
GIN
98.4=0.3
93.7=0.5
91.640.5
93.1=0.3
93.1+0.4
93.840.4
92.1=0.33
02.1+:.5
91.720.5
91.1
90.2=0.5
91.410.5
91.120.4
93.840.4
92.020.3
89.5.00.4
88.2.0.55
88.810.3
08.4
90.310.4
89.51005
91.710.3
90.5.0..3
86.110..5
92.11.066
80.9100.
87.7
92.5.10.2
91.110.3
91.0.0.3
91.710..4
2
98.0+0.5
92.3#0.3
93.5+0.3
90.9=004
92.9+0.5
92.8=0.6
94.6=0.5
92.1=0.4
R x
89.540.3
90.7#0.4
88.740.4
89.0=0.6
91.5+0.4
90.320.3
90.640.4
90.3+0.5
R
x HI
90.2110.4
90.6.10.5
88.310.6
87.810.4
90.8100.5
91.210.3
91.010.5
90.410.3
2 1
89.7+0.5
90.7#0.3
89.2#0.3
87.7=0.1
90.5+0.3
90.2#0.1
90.840.4
90.1=0.3
Hg
85.2+0.3
88.0#0.4
88.720.4
87.6=0.3
90.4+0.3
87.220.5
89.2+0.3
91.3#0.5
Table 5: Results of GNNs in different spaces for link prediction, where n is a hyperparameter of space dimension that we tune on the development sets. Results are reported in AUC.
ML-100K
LASTPM
MEETUP
HR@10
nDG
HR&10
nDG
HR@10
nDG
54.5:1 1.2
28.2
69.3::0.4
48.9
82.110..4
63.3
14.6:110
28.7
05.4:
24.6
0..8::0.2
59.5
R
10.1
25.5
54.940.55
31.7
70.2:+0.2
45.3
ER
53.4+1.0
28.2
54.8+0.55
24.9
79.1
58.8
SPD R
1..
28.0
55.4.10.2
25.3
78.5.10.5
58.6
St
55.6+1.3
29.4
61.1+112
80. 00.55
R10 x IR10
52.0:11.1
27.1
68.2:10.4
47.3
79.6:10.3
60.1
2 Rg
1b
53.1
27.6
69.2::0.5
49.9
80.6#0.3
61.2
REg R
1.3
27.9
45.5:10.4
18.9
79.3:0.22
58.9
3 16
1..9
28.4
66.2+0.55
77.8
57.2
55.0100.6
79.5.1.22
Table 6: Results on the three recommendation bipartite graphs. Higher HR@10 and nDG are better.
4.3 Application 2: Recommender Systems
Experimental Setup. Following López el al. 2021 1 we conduct a comparative examination of the impact of the choice of metric spaces on recommendation task. This task can be seen as binary classification problem bipartitc graph, in which users and items treated two distinct subsets of nodes, and recommendation systems are tasked with predicting the interactions between user-item pairs. We adopt the approach of prior research (Vinh Tran et al. 2020 López et al., [2021) and base recommendation systems on graph embeddings in metric spaces. Our experiments include three popular datasets: (a) MI-100K (Harper & Konstan 2015) from MovieLens for movie recommendatio; (b) LAST.FM (Cantador et al. 2011] for music recommendation, and (c) MEETUP (Pham et al. 2015) from Meetup.com in NYC for event recommendation. We use the train/dev/test sets of these datascts from the work of López et al. (2021), and report the average results across five runs in terms of two evaluation metries: hit ratio (HR) and normalized discounted cumulative gain (nDG), both at 10. We provide the training details and the statistics of the graphs in Appendix D.3
Results. Tab. reports the results three bipartite graphs. We find that the performance gaps between metric spaces small on MI- 10-1.0.. Therefore, the choice of metric spaces does not influence much the performance on this graph. In contrast, the gaps are quite noticcable on the other two graphs. For instance, we see that the é space largely outperforms all the other spaces, particularly on LAST.FM. This showcases the importance of choosing a suitable metric space for downstream tasks. is noteworthy that the 4 norm outperforms the loo norm on the recommender systems task, while the opposite true for the graph reconstruction task. This raises intriguing questions about how normed space embeddings leverage the geometries of the underlying normed spaces.
10

---

Published in Transactions on Machine Learning Research (05/2024)
5 Conclusions
Classical discrete geometry results suggest that normed spaces can abstractly embed a wide range of finite metric spaces, including graphs, with surprisingly low theoretical bounds on distortion. Motivated by these theoretical insights, we highlight normed spaces as a valuable complement to popular manifolds for graph representation learning. Our empirical findings show that normed spaces consistently outperform other manifolds across several real-world and synthotic graph roconstruction benchmark datascts. Notably, normod spaces demonstrate an euhanced capacity to embed graphs of varying curvatures, an increasingly evident. advantage as graph sizes get bigger. We further illustrate the practical utility of normed spaces on two applied graph embedding tasks, namely link prediction and recommender systems, underscoring their potential for applications. Moreover, while delivering superior performance, normed spaces require significantly fewer compulational resources and pose fewer technical challenges than competing solutions, further enhancing their appeal. Our work not only emphasizes the importance of normed spaces for graph representation learning but also naturally raiscs several questions and motivates further rescarch directions:
Modern and Classical AI/ML Applications. The potential of normed space embeddings can be tested across a wide range of AI applications. In many machine learning applications, normed spaces provide a promising alternative existing Riemannian manifolds, such as hyperbolic spaces (Nickel & Kiela 2017 2018 Chami ct al. 2020a b) and other symmetric spaces, as embedding spaces. Classical non-diffcrentiable discrete methods for embedding graphs into normed spaces have found applications in various areas (Livingston &
Stout 1988 Linial et al.) 1995 Deza & Shtogrin 2000: [Mhammedl] 2005). Our work demonstrates the efficient computation of graph embeddings into normed spaces using a modern differentiable programming paradigm. Integrating normed spaces into deep learning frameworks holds the potential to advance graph representation learning and its applications, bridging modern and classical AT research.
Discrete Geometry. Further analysis is needed to describe how normed space embeddings leverage the geometry of normed spaces. It is also important to investigate which emergent geometric properties of the embeddings can be used for analyzing graph structures, such hicrarchies. Lastly, we anticipate our work will provide a valuable experimental mathematics tool.
Our work and others in the geometric machine literature, such as Nickel & Kiela (2017 2018); Chami et al. (2019a); Cruceru et al. (2020); López et al. (2021): Giovanni et al. 2022), lack theoretical guarantees. It is crucial to connect the theoretical bounds on distortion for abstract embeddings and the empirical results, especially for real-world graphs. In particular, is possible that hyperparameter tuning or different spaces and training techniques than normed spaces and gradient. descent can achieve better performance in general settings, in addition the restricted cases where some geometric spaces perform exceptionally well on particular graphs, such hyperbolic geometry and trees. It would also be valuable to analyze more growing families of graphs, such as expanders and mixed-curvature graphs. Furthermore, embedding larger real-world networks would provide insights into scalability in practical settings, and how the benefits would translate to graphs of larger scale. Lastly, future work should expand this study to dynamic graphs with evolving structures and investigating the transferability of embeddings learned on one task, e.g., link predictions with GNNs, to other tasks.
Limitations and Future Research.
Acknowledgments
We would like to extend our thanks to Anna Wienhard, Maria Beatrice Pozetti, Ullrich Koethe, Federico López, and Steve Trettel for many interesting conversations and valuable insights. We extend our sincere gratitude to the reviewers for their insightful comments and suggestions, which have significantly enhanced the quality of this paper. J.M. Riestenberg was supported by the RTG 2229 "Asymptotic Invariants and Limits of Groups and Spaces" and by the DFG under Project-ID 338644254 SPP2026. Wei Zhao was supported by the Klaus Tschira Foundation and Young Marsilius Fellowship at Heidelberg University.
11

---

Published in Transactions on Machine Learning Research (05/2024)
References
G. Bachmann, G. Bécigneul, and O.-E. Ganea. Constant curvature graph convolutional networks. In 37th International Conference on Machine Learning (ICML), 2020.
Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A poylogarihmmiccompetiiee algorit for the k-server problem. Journal of the ACM (JACM), 62(5):1 49, 2015.
Gary Bécigneul and Setavian-Euggan Ganea, Riemannian adaptive optimization methods. In 7th International Conference on Learning Representations, ICLR, New Orleans, LA, USA, May 2019. URL https:// openreview. www.viiwwnetffore.o hett/foruriddrrrriiliaoo..
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani (eds.), Advances in Neurol Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 9-8, 2001, Vancouver, British Columbia, Canadaj, pp. 585-591. MIT Press, 2001. URI,https Abstract cosstrccthtm]
//proceedings.neuree nww..nnuiipp.... wwtpccce/p/.../////// /ttp:///////./110001022222200000
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798 1828, 2013.
Béla Bollobés and Béla Bollobás. Random graphs. Springer, 1998.
Silvère Bonnabel. Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Aulomatic Control, 58, 11 2011. doi: (0000//TAA.:211.22545444
J. Bourgain. On Lipschitz embodding of finite metric spaces in Hilbert space. Ismael J. Math., 52(1-2))46-52, 1985. ISSN 0021-2172. doi: 10.1007 10.1000/BBF227700000 BF02776678. URL https: /tttps://do.... wtt.///o.......//////.....
Alexander M Bronstein, Michael M Bronstein, and Ron Kimmel. Generalized multidimensionall scaling: a framework for isomelry-invariant partial surface matching. Proceedings of the National Academy of Sciences, 103(5):1168 1172, 2006.
Deng Cai, Xiaofei He, Jiawei Han, and Thomas S Huang. Graph regularizod nonnegative matrix factorization for data representation. IEFF transactions on pollern analysis and machine intelligence, 33(8)11548 1-0-1-608--6 2010.
1560,
Iván Cantador, Peter Brusilovsky, and Tsvi Kuftik. 2nd Workshop on Information Heterogeneity and Fusion in Recommender Systems ReetRec 2011). In Proceedings of the 5th ACM Conference on Recommender Systems, RecSys 2011, New York, NY, USA, 2011. ACM.
Ben Chamberlain, Mare Deisenroth, and James Clough. Neural embeddings of graphs in hyperbolic space. In Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG), 2017.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolu- tional neural networks In Advances in Newral Information Processing Systems 32, pp. 4869- 4880. Curran Associates, Inc., 2019a. URL https://prroceeding wtw.:ggs..uurrssreoeo pttpppp/..cc/appe///////lee
0415700aa4GGeebosa0011SSSEEGG Paper. pdf
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference Newral Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 4869-4880, 2019b.
Incs Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From trees to continuous em- beddings and back: Hyperbolic hierarchical clustering. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Aisuan-Tien Lin (eds.), Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Newral Information Processing Systems 2020, NewrIPS 2020, December 6- 12, 2020, virtual, 2020a. URL httpps://proceedings hatrrips..ccppape//2000 hhash// cec10ccc.ae5112227773877774422.9 Abstaa/r html
12

---

Published in Transactions on Machine Learning Research (05/2024)
Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. In Proceedings of the 58th Annual Meeting of the Associalion for Computational Linguistics, pp. 6901 6914, Online, July 2020b. Association for Computational Linguistics.
doi: 10. 10.18653/v1, 000/53/v12220..0// /0.18653/v1/2020..c 2al/2220..cllmiin. main.61a.. URL https://www.ccliii aclweb. www.e//eb.rrg/nniiii arggantholoogy/2200.. acl acl- 617
C. Cruceru, G. Bécigneul, and O.-E. Ganea. Computationally tractable Riemannian manifolds for graph embeddings. In 37th International Conference on Machine Learning (ICML), 2020.
Michaël Defferrard, Martino Milani, Frédérick Gusset, and Nathanaël Perraudin. DeepSphere: A graph- based spherical CNN. In International Conference on Learning Representations, 2020. URL https: //openreview met./foruuriddi111011115.
M Deza and Mikhail Ivanovich Shtogrin. Embeddings of chemical graphs in hypercubes. Mathemalicaa Notes, 68:295-300 305, 2000.
Takuma Ebisu and Ryutaro Ichise. Toruse: Knowledge graph embedding on a Lie group. In Sheila A. McIlraith and Kilian Q. Weinberger (eds.), Proceedings of the Chirty-Secome AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th Innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 1819 1826. AAAT Press, 2018. URL https: www. aaai. orrg//org//ogoo ocs/ index php/AAAT/AAAII8/ppaa wttp://///ppppeeee//eeeeee/e//// 16227
Luea Falorsi, Pim de Haan, Tim R. Davidson, Nicola De Cao, Maurice Weiler, Patrick Forré, and Taco S. Cohen. Explorations in homcomorphic variational auto-encoding, 2018.
Octavian-Euge Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1646 1655, Stockholmsmässmn, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:///proceeenngg// mlr / v80/ 2000/anea188..o html
Francesco Di Giovanni, Giulia Luise, and Michael M. Bronstein. Helerogeneous manifolds for curvalure-awan graph embedding. CoRR, abs/2202.01133 2022. URL https://arxiv.. http://wwww...rrra//////////...0
Kwang-II Goh, Michael E Cusick, David Valle, Barton Childs, Mare Vidal, and Albert-László Barabási. The human disease network. Proceedings of the National Academy of Sciences, 104(21):8685- 8690, 2007.
Lev Goldfarb. A new approach to pattern recognition. Progress in pallern recognition, 2:241 402, 1985.
Daniele Grattarola, Daniele Zambon, Lorenzo Livi, and Cesare Alippi. Change detection in graph streams by learning graph embeddings constant-curvature manifolds. IEEE Trans. Neural Networks Learn Syst., 31 (6):1856-1869, 2020. doi: TNN.:/NNNN......1.. 2927301
URL https: org/ 1109/TNNSS...... 2019
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Son Francisco, CA, USA, August 17, 2016, pp. 855-864. ACM, 2016. doi: 10. /25///999672229977535 URL https://doi.org 10. 1011/ 2937777
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvatioo representations in product spaces. In International Conference on Learning Representations, 2019. URL URL httpps://pperreviee
net/foorumiid::DxeeWncrr
Michael Hahsler and Kurt Hornik. Tsp-infrastructure for the traveling salesperson problem. Journal of Statistical Software, 23(2):1 21, 2007.
F. Maxwell Harper and Joseph A. Konstan. The MovicLens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), December 2015. ISSN 2160-6455. doi: 10.1145/2827872. URL https
7/doi. owa.laorg/11.. 21g/10.1145//827877
13

---

Published in Transactions on Machine Learning Research (05/2024)
Sigurdur Helgason. Differential geometry, Lie groups, and symmetric spaces. Academic Press New York, 1978. ISBN 0123384605.
Samitha Herath, Mchrtash Tafazzoli Harandi, and Fatih Porikli. Learning an invariant Hilbert space for domain adaptation ion. In 2017 TEFE Conference on Computer Vision and Patlern Recognilion, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, 7, pp. 3956 3965. LEEE Computer Society, 2017. doi: 10.1109 10.1109/CVPR.200 /CVPR.2017.22) URL https: pettps:/ddo..rgee 10. 1109/CVPR. 20017.421
Zhiwu Huang and Luc Van Gool. A Riemannian network for SPD matrix learning. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI17, pp. 2036 2042. AAAI Press, 2017.
Zhiwu Huang, Jiqing Wu, and Luc Van Gool. Building deep networks on Grassmann manifolds. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Thirlly-Scood AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th Innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAT Symposium on Educational Advances in Artificial Intelligence (EAAT-18), New Orleans, Louisiana, index
USA, February 2-7, 2018, pp. 3279 3286. AAAI Press, 2018. URL https: /www. aaai. fesi.or 16846
William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probabilily (New Haven, Conn., 1982), volume 26 of Contemp. Math., pp. 189 206. Amer. Math. Soc., Providence, RI, 1984. doi: 10.1090/ 10.1090/comm//0n https: //doi. org/10. wtt00/////////////////0//
URL
William B. Johnson, Joram Lindenstrauss, and Gideon Schechtman. On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pp. 177-184. Springer, Berlin, 1987. doi: 10.1007/BFb0079145, URL https://dol org/ 10. 10070007//BBB 1077/0F600781455
Mahmut Kaya and Hasan Sakir Bilge. Deep metric learning: A survey. Symmetry, 11(9):1066, 2019.
Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar. Efficient distributed approximation algorithms via probabilistic tree embeddings. In Proceedings of the twenby-seventh ACM symposium on Principles of distributed computing, pp. 263-272 2008.
Thomas N. Kipf and Max Welling. Variational graph aulo-encoders. CoRR, abs/ als/1661.00730 2016. URL
http://arxiv wwtexivv.ogg/// abs http//111..000
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. CRL https::/opeerrviiet wtt.:///wweeettoooooo/oo//ss///
Max Kochurov, Rasul Karimov, and Sergei Kozlukov. Geoopt: Riemannian optimization in PoTorh.. ArXie, //////005..2211 2020.
Robert Krauthgamer, James R Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. In 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 434-443. IEEE, 2004.
Nils M. Kriege. Weisfeiler and leman go walking: Random walk kernels revisited. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Newral Information Processing Systems, volume 35, pp. 20119 20132. Curran Associates, Inc., 2022. URL htttps://pooceeeeee htw.eeeeeiiinnnnnnnnnise.. neurips. cc/ paper_ httpe//ppppepoooo//////////aaaaa
Papera---aaee-----feeeeeene Paper- Conferenceeeeeeeeee pdf
Brian Kulis et al. Metric learning: A survey. Foundations and Trends& in Machine Learning, 5(4):287-366 2013.
Mare T. Law and Jos Stam. Ultrahyperbolic representation learning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tin Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatooiio, 15(2):215-24) 2452 1995. ISSN 0209-9683. doi: 10.1007/BF01200757 URL
Marilynn Livingston and Quentin F Stout. Embeddings in hypercubes. Mathematical and Computer Modelling, 11:222-221 1988.
Federico López, Benjamin Heinzerling, and Michael Strube. Fine-grained entity lyping in hyperbolic space. In Proceedings of the 4th Workshop on Representation Learning for NLP (RepL/NLP-2019), pp. 169-180, 180, Florence, Italy, August 2019. Association for Computational Linguistics. doi: 10.18663/v1/W1994411 URL
https://wwis www.ab. wttpg//anntolloo/1199-990
Federico López, Beatrice Pozzctti, Steve Trettel, Michael Strube, and Anna Wienhard. Symmetric spaces for graph embeddings: A finsler-rimmannian approach. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event,
volume 139 of Proceedings of Machine Learning Research, pp. 7090 7101. PMLR, 2021. URL http: //proceedings. mlm. wttp:sssw........seeeeeeeeeeesee httpss//vvv91oooee1111 1opp/21.......... html
mmr.
Federico López, Beatrice Pozzetti, Steve Trettel, Michael Strube, and Anna Wienhard. Vector-valued distance and gyrocalculus on the space of symmetric positive definite matrices. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
Alex Lubolzky. Discrele groups, expanding graphs and invariant measures, volume 125. Springer Science & Business Media, 1994.
Julian McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In Proceedings of the 25th International Conference on Neural Information Processing Systems Volume 1, NIPS'12, 12, pp. 547, Red Hook, NY, USA, 2012. Curran Associates Inc.
Yu Meng, Jiaxin Huang, Guangyuan Wang, Chao Zhang, Honglei Zhuang, Lance Kaplan, and Jiawei Han. Spherical text embedding. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buus Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32, pp. 8208-8217. Curran Associates, Inc., 2019. URL https://pproceedings http://gww....aa.cc/////p/////// Papero-pppppppppp
Qatawneh Mohammed. Embedding linear array network into the tree-hypercube work European Journal of Scientific Research, 10(2):72-70) 76, 2005.
Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6341-6350. Curran Associates, Inc., 2017. URL https; : .dd
Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the Lorentz model of hyperbolic geom- ctry. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3779 -7888, Stockholnsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URI htt.:ttt:///rcceediinee
mlr. press/ v80/nickeell html
Wouter De Nooy, Andrej Mrvar, and Vladimir Batagelj. Esploralory Social Network Analysis with Pajek. Cambridge University Press, USA, 2011. ISBN 0521174805.
OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2023. Published electronically at http://oeis.org
Bryan Perozzi, Rami Al-Rfou, and Sleven Skiena. Deepwalk: online learning of social representations. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani (eds.), The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY, USA August 24- 27, 2014, pp. 701-710. ACM, 2014. doi: 221144//6233302222222 https:///oi... org/ 10. wttg//...14///2230...ooo 2623333
URL
15

---

Published in Transactions on Machine Learning Research (05/2024)
T. N. Pham, X. Li, G. Cong, and Z. Zhang. A general graph- model for recommendation in event-based social networks. In 2015 IEFE 31st International Conference on Dala Engineering, pp. 567-578, 2015. doi: 10.1109/ICDE..215.7777 7.13315.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoffs for hyperbolic embeddings. In Jennifer Dy and Andreas Krausc (cds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Mochine Learning Research, pp. 1460-4460 Stockholmsmässan Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:://rroceedings.. mlr press//80/saalllaa http:///.ccaaaaii...././/////a/a html
Guillaume Salha, Romain Hennequin, Viet Anh Tran, and Michalis Vazirgiannis. A degeneracy framework for scalable graph autoencoders. In 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019.
Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In Mare van Kreveld and Bettina Speckmann (eds.), Graph Drawing, pp. 355-366, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-25878-7
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Carl Ludwig Siegel. Symplectic geometry. American Journal of Mathematics, 65(1):1 86, 1943. ISSN 00029327, 10806377. URL http://wwx. http:///wwwwjsstrr.oo.ooooooooo. wttp:/jstoooror/ttatboioes wrtp//taaaee////77//44/
Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert R.G. Lanckriet Hilbert space embeddings and metrics on probability measures. J. Mach. Learn, Res., 11:1517-1561, August 2010. ISSN 1532-4435.
Lovro Subelj and Marko Bajec Robust network community detection using balanced propagation. The European Physical Journal B, 81:353-362 2011.
Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery, 23:447 478, 2011.
The Sage Developers. SageMath, the Suge Mathematics Software https: //ww:. wagemath.
System (Version 2.y.2), 2023.
Alexandru Tifrea, Gary Béeigneul, and Octavian-Eugen Ganea. Poincare GloVe: Hyperbolic word embeddings. In 7th International Conference Learning Representations, ICLR, New Orleans, LA, USA, May 2019.
URL
Salil P Vadhan et al. Pseudorandomness, volume 7. Now Publishers, Inc., 2012.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL https
//openreview. wttp::/oommiidddrri.........
Lueas Vinh Tran, Yi Tay, Shuai Zhang, Gao Cong, and Xiaoli Li. HyperML: A boosting metric learning approach in hyperbolic space for recommender systems. In Proceedings of the 13th International Conference on Web Search and Data Mining, WSDM '20, pp. 609-617, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450368223. doi: 10.1145/33361911 333619113371850 URL
1144/3336199.33719850 3371850
Harit Vishwakarma and Frederic Sala. Lifting weak supervision to structured prediction. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Newral Information Processing Systems, volume 35, pp. 37563-3337777 37574. Curran Associates, Inc., 2022. URL
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. PMLR, 2019.
16

---

Published in Transactions on Machine Learning Research (05/2024)
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representalions, TCLR 2019, New Orleans, L.,, USA, May 6-9, 2019. OpenReview.net, 2019. URL http:://pppaneeess..rrr/ooooooos
Tong Yang, Long Sha, and Pengyu Hong. NagE: Non-Abelian Group Emmeedingg for Knowledge Graphs, pp. 1735-1742. Association for Computing Machinery, New York, NY, USA, 2020. ISBN 9781450368599. URL
3411887
Wei Zhao, Federico Lopez, Maxwell Riestenberg, Michael Strube, Diaacldin Taha, and Steve Trettel. Modeling graphs beyond hyperbolic: Graph neural networks in symmetric positive definite matrices. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2023.
17

---

Published in Transactions on Machine Learning Research (05/2024)
A Embedding Spaces
Metric Spaces. Let X be non-empty set. A metric space is ordered pair (X,d), where d: X x X - R is function, called the metric or dislance, function, that satisfies the following properties for all 2, 2 E X: (i) d(z, v) 2 0, (ii) d(z, y) = O if and only if I = (iii) d(z, y) d(y,z), and (iv) d(x,2) < d(z, y) + d(y. A map f: X + Y between two metric spaces (X, dx) and dy) is an isometric embedding if it preserves distances, i.e, dy (f(()) = dx (I1, I2), A 21, 22 E X.
Riemannian Manifolds. Let M be a smooth manifold, E M be a point, and T.M. be the tangent space at the point A Riemannian manifold (M,g) is a smooth manifold M equipped with a Riemannian metric 9 given by a smooth inner product 9p: TpM x TyM + IR at each point p E M. Euclidean space is the simplest example of a Riemannian manifold. Let V be any n-dimensional real vector space endowed with the Euclidean metric g given by g(v, w) = (v, (), for any p E V and any v, w T,V = V.
Normed Spaces. A normed space is a vector space V over the real numbers R or complex numbers C equipped with a norm. A norm is a function ||-I|: V + [0, +20) satisfying the following properties for all vectors 2, y E V and scalars F: (i) ||>|||| 2 0, with equality if and only if x = 0, (ii) ||x]|| = |a|||=||, and (iii) || + yl ||=||| + lyyl- Normed spaces induce metric spaces via the induced distance function, defined d(r, = | yll- The p-norms are among the most important examples of norms. For real number p 2 1, the p-norm of a vector x E Rd given by |жж| == (|=y|² + lay|? +.... + [xa)P) The definition is exlended for p = oc as ||>]|>> = ma The space Rdd equipped with p-norm denoted as ed Here we focus on the cases p= 1,2, and co.
"p-
Pseudo-Euclidean Spaces. Denote the product IRd x Rd where dt and d' are non-negative integers, pd' by RpSE and write any element E EpsE the pseudo-Euche Euclidean space EEsE (f v) = | y -|= - y Il, where || ||3 is the square of the & norm on the respective space.
= (xt,x"), where x+ E Rd and x- R² Then B d' is the set Rdt x Rd with the squared distance function defined by
Hyperbolic Space. Hyperbolic space is Riemannian manifold with constant negative curvature. There are several models of hyperbolic space, such as the Poincaré ball model and Lorentz model. The models are essentially the same in a mathematical sense (they are pairwise isometric), but one model can have computational advantages over another.
Definition 1 (Poincaré Ball Model). Let ||- be the Euclidean norm. Given negative curvature c, the Poincaré boll model is a Ršemannian manifold (82.92) where B: = {x E R" ||x||² < <1/cc} is an open ball with radius 1/ Vld and ox = (Id) where X 21 e||x|1B) and Id is the identity matriz.
Product Manifold. Let M1, M, ..., .....,, M&& be a sequence of smooth manifolds. The product manifold is given by the Cartesian product M = M1 x M2 x Mg. Each point p M has the coordinates p ,P).....P,,, with ps E M2 for all i. Similarly, tangent vector v T,M can be written as (#1...., Uk), with each 0s E TT,MM If each Mj is equipped with Riemannian metric Ii, then the product manifold M can be given the product metric where g(,,w) Σ (i
Riemannian Symmetric Spaces. Riemannian symmetric spaces are connected Riemannian manifolds such that the geodesic symmetry at each point defines global isometry of the space. For simply connected manifolds this condition equivalent to having covariantly constant curvature tensor. key consequence of the definition is that symmetric spaces are homogeneous manifolds. Intuitively, this means that the manifold "looks the same" at every point. Furthermore, simply connected symmetric spaces decompose into products of irreducible symmetric spaces and Euclidean space. Irroducible symmetric spaces can be described in terms of semisimple Lie groups. Basic examples of Riemannian symmetric spaces include Euclidean spaces, hyperbolic
FFor any point p in any Ricmannian manifold, there exists sufficently small 0 such that the map Sp: B(p,c) B(p, c) defined by Sp(c(t)) = c(-t) is well-defined for any unit-speed geodesic et (-r,e) + B(p.e) with c(0) p. Such map Sp is called the geodesic symmetry at p-
18

---

Published in Transactions on Machine Learning Research (05/2024)
Sywee
Undarlying
Distanoo
R2
Dormed space
R
d(x.v) Ia -1l
hyperbolic apace
(R.
Bille S
d(r,)) areuch +
11
<(x.v) [ "iit whore Ac(e (y) the eigenvalue 2
SPD
Leigue al.
symmnttii posilive dedinite undeiios
Siogel aperss Lelprer et al. A021
upper
X+ Symin, <y 0]
Algorithm Algorithm
upper half model
[Z X Symix, 1Y>>>>>>>>>>>
upper holf model
-2-X+ YY
Algorithm
bounded symmattdi domain model bounded symmetric domain model
[2 8ym(u. Id-2'>>>> 0)
see Algocithas
[2 Sym(n,
144-2-220 0)
Algostthm
0
bounded
model
Sym(e, =d=2">>>
Algocithmm
d(x,u) vlxr yth 1. (whem clefmee)
pecodloEuuciden Euclidean space
Visiwakarma Sala. 2022
R x
where (x (x7) and y (0".8")
Mg product apriss
d(x,)) (1a, d2 where (21) and (81.39)
Table 7: summary of the embedding spaces.
spaces and spheres. In the following we will describe two further special cases: Siegel space and the space of symmetric positive definite (SPD) matrices.
Siegel spaces, HypSPDa, hyperbolic planes and the copies of SPD as submanifolds. These spaces support Finsler metrics that induce the & and the &oo metric on the Euclidean subspaces. HypSPD, has the two following models with n(n + 1) dimensions, both of which are open subsets of the space Sym(n, () over C. These two models generalize the Poincaré disk and the upper half plane model of the hyperbolic space.
matrix versions of the hyperbolic plane, accommodating many products of
Definition 2 (Bounded Symmetrie Domain Model). The bounded symmelric domain model for HypSPD, generalizes the Poincaré disk. It is given by Bn (Z E Sym(n, C) ld - Z >> 0}.
Definition 3 (Siegel Upper Half Space Model). The Siegel upper half space model for HypSPD, generalizes the upper half plane model of the hyperbolic plane by Sn = (Z x e Sym(n, C) Y >> 0}.
There exists an isomorphism from B, to Sn given by the Cayley transform, which is a matrix analogue of the familiar map from the Poincare disk to upper half space model of the hyperbolic plane:
Z + Id) Idd)
We refer readers to Siegel (1943) and López (202)) for an in-depth overview of Siegel spaces and their applications in graph embeddings.
matrices, given by SPD(n, R) = {X E Sym(n, R)I X >> 0}. It has the structure of Riemannnin manifold of non-positive cureature of nnn++ + 1)/2 dimensions. The Riemannian metric on SPD,, is defined as follows: if U.V E S, are tangent vectors based at P SPD,, their inner product is given by (U, V)P = TPPP--UP-V)
Definition 4 (SPD Space). SPD, is the space of positice definite real symmetric
The tangent space to any point of SPD, can be identified with the vector space S, of all real symmetric matrices. SPD, is more flexible than Euclidean or hyperbolic geometries, or products thereof. In particular, it contains n--dimensional Euclidean subspaces, (n - -)ddimensional hyperbolic subspaces, products of Lä] hyperbolic planes, and many other interesting spaces as totally geodesic submanifokds, see the reference Helgason 1978 for an in-depth introduction.
B Graph Reconstruction Loss Function
The graph reconstruction task aims to empirically quantify the capacity of a space for embedding graph structure given through its node-to-node shortest paths. Recent work has generally employed local, global, or hybrid loss functions, focusing on close neighborhood information, all-node interactions, intermediate of
19

---

Published in Transactions on Machine Learning Research (05/2024)
Finite Metric Spaces
Embedding Space
Distortion Bound
Reference
Complete graph (Kn)
[ogg(1)]
O(1)
Linial et al.
1995
Tree (Tx)
Oloo n)
O(1)
Linial et
1995
Planar graph with vertices
2o (log n)
O(1)
Krauthgamer et al.
2004
Expander with n vertices
8p of any dimension (22 1)
((log
Linial et al. 1995
Metric space (X,d) with points
p (logg) (for any 1 2)
(loggn)
Linial et al.
1995
Metric space (X,d) with points
colioe m) (for any p Ep
(log
Linial et al.
1995
Table A summary of thcorctical results.
both. Local loss functions emphasize preserving neighborhoods, exemplified by the loss function
exp (=dy(f(u),f()))
C(J)
Σ
log
E EmEN(()) exp dy ((),
(a
from Nickel & Kiela [2017 2018 where M(u) = (w (u, & E} U {A} is the set of negative examples for u
(including v). The resulting embeddings are typically favored by rank- based evaluation metrics such as mean average precision mAP. On the other hand, global functions emphasize proserving distances directly via loss functions motivated by generalized MDS (Bronstein et al. 2006)), exemplified by the loss function
dy dr((f(w) 2 -1.
C(f)= = Σ
(
dg(u,v)
from Gu et al. (2019) and which we use in this work. The resulting embeddings are typically favored by average distortion Davg- Lastly, hybrid loss functions, such as the Riemannian Stochastic Neighbor Embedding (RSNE) from Cruceru et al. (2020), aim to balance the emphasis on local and global, sometimes with a tunable parameter for controlling the optimization goal.
We note that though employ global loss function, the resulting normed space embeddings notably perform well on both D Dang and mAP.
C Metric Learning
Metric learning is a machine learning approach concerned with learning distance metrics in an embedding space, with the aim of using the distances between data points as features for tasks such as classification, regression, clustering, and image retrieval. In connection with our work, metric learning pipelines broadly consist of a learnable embedding function f X Y that maps data from an input space X into a target embedding space Y equipped with distance metric dy, machine learning component that takes the values of the distance dy(:-) ; dy (f()), f(-) input features for task, and appropriate optimization algorithms for learning the parameters in the pipeline. The embedding function and the parameters of the machine learning components (if any) could be jointly learned in a supervised manner or otherwise hand-crafted or leveraged from embeddings trained on another task. In deep metric learning, typically, the embedding function and the machine learning component are differentiable, and parameter optimization takes place by minimizing or maximizing an appropriatc loss function with gradient descent. For reference, we recommend the following excellent surveys on metric learning: Kulis al. (2013); Kaya & Bilge (2019). We note that many geometric machine learning pipelines, including ours, align with the metric learning paradigm, where the metric space has Riemannian manifold structure. Check, for example, Nickel & Kiela 2011 2018
Chami et al. (019a)); Cruceru et al. 20000 López et al. (2021; Giovanni et al. 2022).
shallow embedding is a function that simply assigns each entity a point in the target embedding space, with these points serving as the learnable parameters. On the other hand, a graph neural network maps the features of node and its neighbors to a point in the target space, with the network weights being the learnable parameters.
We summarize the metric learning pipelines used in this work in Table
20

---

Published in Transactions on Machine Learning Research (05/2024)
Task
Embedding Function
ML Component
Loss Function
Craph Reconstruction
shallow embedding
distance- based loss (eq.
$4.1
D.1
Link Prediction
graph neural network
Fermi-Dirac decoder (eq.
binary cross-entropy (eq. 5
4.2
D.2
Recommender System
hinge loss (eq.
shallow embedding
similarity score (eq.
($43
D.3
binary cross-entropy (eq.
Table 9: Summary of metric learning pipelines.
Grid Layout
Tree Valency
Tree Height
Graph
Nodes
Edges
Triples
4D GRID
625
2000
195,000
(5)*
TREE
364
363
66,066
3
TREE x TREE
225
420
25,200
2
3
TREE GRIDS
775
1,270
299,925
2
4
GRID TREES
775
790
299,925
5
2
4
Table 10: Characteristics of synthetic graphs.
Experiments
Hardware and Code Release. All experiments were executed on an Intel(R) (R) CPU E5-2650 computer, equipped with 48 CPUs operating at 2.2 GHz and a single Tesla P40 GPU with a 24GB of memory running CUDA 11.2.
D.1 Graph Reconstruction
Implementation Details. In all setups, we use the RADAM optimizer (Bécigneul & Ganea 2019) and run the same grid search to to train graph embeddings. The implementation of all baselines are taken from Geoopt (Kochurov et al. 2020) and López et al. (2021). We train for 3000 epochs, and stop training when the average distortion has decreased for 200 epochs. We experiment with three hyperparameters: (a) learning rate E {0.1, 0.01, 0.001); ); (b) batch size (512, 1024, 2048, -1} with -1 the node count within graph and (c) maximum gradient norm E {10, 50, 250). Table 10 and 11 report the stats of all the synthetic and real-world graphs.
Evaluation Metrics. We evaluate the quality of the learned embeddings using distortion and precision metrics. Consider a graph G, target metric space Y, and a metric embedding f G + Y. The distortion of the embedding of a pair of nodes u, is given by:
ldy f(v)) do v)
distortion(u, v)
do (u, v)
Graph
Nodes
Edges
Triples
USCA312
312
48,516
48,516
BIO-DISAASOME
516
1,188
132,870
CSPHD
1,025
1,043
524,800
ROAD-BUROROAD
1,039
1,305
539,241
PACEBOOK
4,039
88,234
8,154,741
MARGULIS
625
2,500
195,000
PALEY
101
5,050
5,050
CHORDAL
G23
1,569
136,503
Table 11: Characteristies of real-world and expander graphs.
21

---

Published in Transactions on Machine Learning Research (05/2024)
DIO-DISEASOME (316, 1188)
CSPHD
(V)) (ED)
(1025, 1943)
Davg
mAP
Davg
mAP
Strees Loss
2.79110.01
87.09
2.16
45.55
200
1.41#0.02
76.71
1.31=0.01
39.05
27
1.8820.01
88.86
1.54#0.01
69.00
11.344:0.05
66.55
30.88=0.06
19.62
Distortion Loss
1:20
1.62:10.01
89.14
0.39
52.34
3.83#0.01
76.31
4.01=0.01
47.37
87
0.53=2.01
98.21
0.12:0.011
99.28
6.83:10.08
91.26
0.24
60.24
Table 12: Comparison of distortion and stress loss functions.
We denote the average of distortion over pairs of nodes by Dawg.
The other metric that we consider the mean average precision (mAP). It is ranking- ranking-based measure for local neighborhoods that does not track explicit distances. For the mean average precision (mAP) metric, consider G (V, E) graph and Na the neighborhood of the node V. Let Ra,d, be the smallest neighborhood of f(a in the space Y that contains f(b;), with f: G + P as a metric embedding. Then, mAP can be defined as follows:
W.l
W. n Ra.d
mAP()) V
Σ Σ aEV deg(a)
Ra,b.
mAP quantifies how well the embedding approximates graph isomorphism, applicable only to unweighted graphs. mAP measures the average discrepancy between the neighborhood each node u E and the neighborhood of f()) Y. It's important to note that an embedding with zero average distortion guarantees perfect mean average precision score (i.e., 100.00), but the inverse is not always true: an embedding that effectively preserves the adjacency structure might not be isometry.
Distortion Loss Stress Loss. We note that distance-based loss functions inspired by generalized MDS (Bronstein et al.) 2006) include distortion and stress loss functions. Distortion loss, which is the main loss function we use for learning embeddings in this work, is given by:
Ldistortion (f) = Σ dd (d) -1
dg(u,
(Compare eq. given by:
2 with eq. (I.) On the other hand, strain loss, also known as mean squared error loss, is
Catrees (f) (dolu,)) -y (f((u.)))
compare the impacts of distortion loss and mean squared error loss functions graph embeddings for graph roconstruction. Our results show that with respect to the Davy and mAP evaluation metries, loo embeddings trained with both loss functions consistently outperform the other embeddings, and for each space, the embeddings trained with the distortion loss outperform the embeddings trained with mean squared error. This justifies our choice for learning embeddings with distortion loss.
In Table 12
Space Dimension.
13 we vary the dimension size on datasets with varying curvatures. Our results show that for & and fxc: performance generally improves dimension grows bigger.
In Table 15
16 and
22

---

Published in Transactions on Machine Learning Research (05/2024)
We also observe that increasing the dimension does not seem to help much when there is mismatch between the geometry of a space and graph, such as is the case with Ry and IHE on Grid, and H on Fullerenes. Lastly, we highlight that López et al. (2021) similarly evaluated embeddings on the BIO-DISEASOME dataset in Euclidean, hyperbolic and spherical spaces, their products, and Siegel space at dimension n = 306; our low-dimensional normed spaced embeddings outperformed their high-dimensional embeddings.
Choice of Norm. The choice of the norm could be considered hyperparameter to be tuned. In our experiments, foo performs best in the graph reconstruction task on 10/13 datasets, whereas for downstrcam lasks (link prediction and recommender systems), f performs consistently best in almost all cases on five datasets. So, we recommend using lo for graph reconstruction and & for downstream tasks. Alternatively, we recommend the product of and lo in all setups, as that product performs consistently the second best option behind l and fx..
Link Prediction. We evaluate the performance of task-agnostic shortest-path metric embeddings in a link prediction task. Here, task-agnostic and tosk-specific refer to the technique used for training the embeddings. We first embed the nodes of the CORA and CITESEER datasets by minimizing the distance-based distortion loss defined in eq. (1) using training set of existing edges. We note that no node features are used in this process. Subsequently, we train logistic regression classifier the Hadamard product of source and target node embeddings to predict whether link exists between the nodes for training set that includes existing and non-existing edges. Lastly, we evaluate the classifier We follow the same experimental setup for link prediction from Appendix D.2 and tune hyperparameters (including dimension size and lcarning rate) on the development set.
test set of existing and non-existing edges.
Table 17 compares the results for link prediction using the Lask-agnostic and lask-specific embeddings on the CORA and CITESEER datasets. (The results for the task-specific embeddings are taken from Table 5) We observe that ε space performs best among task-agnostic embeddings on these link prediction datasets, but overall, task-agnostic embeddings underperform task-specific counterparts in our setup. Even though shortest-path metric embeddings capture enough information to enable non-trivial accuracy in link prediction, they fall short of capturing the more nuanced information present in node features and higher-order proximity, resulting in performance that lags behind task-specific embeddings that do capture the aforementioned information. Thus, among the embeddings considered for link prediction this work, we recommend task-spocific & GNN emboddings for practitioners.
20
7
36
66
Davg
mAP
Davg
mAP
Daug
m.P
E
1.50+0.02
52.34
1.32-10.01
08.35
1.1110.01
82.40
4.04110.01
47.37
3.84110.01
62.35
3.7710.02
68.86
R
0.12+00.01
0.50=#0.01
99.16
0.47#0.01
99.37
ER
22. 22.12::0.23
60.24
21.8120.20
74.62
21.54:0.15
75.45
Table 13: Results on CSPHD.
20
7 36
66
Dang
Dang
Davg
RF
1.08:00.00
100.00
0.36:0.00
100.00
0.21+0.00
100.00
R
11.24:1.00
100.00
11.23-10.00
100.00
11.22:10.00
0.13::0.00
100.00
0.02=#0.00
0.02:40.00
R
25.23:10.05
63.74
25.30:10.05
68.69
25.25:10.05
68.78
Table 14: Results on GRID (zero curvature).
23

---

Published in Transactions on Machine Learning Research (05/2024)
20
36
66
Davs
mAP
Dang
mAP
Daug
mAP
Ry,
1.6240.02
73.56
0.90 02
90.61
0.08 02
97.8
3.92.10.04
42:30
3.13100.2
55.19
2.77100.02
55.39
0.15:t0001
100.00
0.0240.01
100.00
0.02+:.01
100.00
BR
0.54:0.02
0.4310.02
0.511:002
Table 15: Results on TREE (negative curvature).
20
36
66
Daug
mAP
Davg
Davy
mAP
Ry R
3.32:1.02
100.00
3.06=1.03
100.00
2.97:40.03
8.5310.03
100.00
8.45:10.03
100.00
8.25:10.03
2.95110.02
100.00
1.96:10.01
100.00
1.59110.01
R
25.18110.05
84.13
25.34=10:04
84.51
25.22:10.05
84.89
Table 16: Results on FULLERENES- 140 (positive curvature).
D.2 Link Prediction
Implementation Details. For each dataset, we use grid search to tune hyperparameters on the development set. Our hyperparameters include (a) dimension E {32, 64, 128} and (b) learning rate E {0.1, 0.01, 0.001 We set batch size to the number of nodes present in each graph dataset. We train for 1000 epochs and stop training when the loss on the development set has not been decreased for 200 epochs. We report the average performance in AUC across five runs. Following Chami al. (2019a), we use the Fermi-Dirac docoder compute the likelihood of link between node pairs, and generale negative sets by randomly selecting links from non-connected node pairs. All graph neural networks are trained by optimizing the eross-entropy loss function. We extend the implementation of Poincaré GCN (Chami et al. 2019a) to support the other three architectures, enabling them to operate in both hyperbolic space and product spaces. We reduce the lcarning rate by a factor of 5 if GNNs cannot improve the performanu after 50 epochs for hyperbolic and product. spaces.
Model. Given a graph 9 = (V,E) with vertex set V and edge set E, node features x, R.d for each node E V, and a target metric space (Z, dz), GNN used map each node u an embedding zu Z. The Fermi-Dirac decoder is used to compute probability scores for edges:
Pa = (1+exp] ( [Byleus 2nd (B(())))--)))) -n)==-))
(4)
where P,,v is the probability of edge existing between nodes and v, dz(zn, 2,) is the distance between the embeddings of the nodes, r is a learnable parameter that adjusts the decision boundary, and t learnable temperature parameter that controls the sharpness of the decision boundary.
Loss Function. Given training set Etriin := Epos U Eneg consists of existing edges Epes and non-existing edges Eneg, the binary cross-entropy loss used to train the model is given by:
C -
Σ
log(o + Σ
log(1 o (Pw.o)))
(5)
(v,
where Pu,v is the output of the model and o(x) T is the sigmoid function.
Space Dimension. In Table 18 we vary the dimension size on the Cora datasct for link prediction. Our results show that, & performs consistently best across GNNs and dimensions from 32 128, and overall, the results show improvement with increased dimension.
24

---

Published in Transactions on Machine Learning Research (05/2024)
Embedding
CORA
CIreSEER
Low- DistDiittonion
Embeddings (task-agnostic)
R7 81.310.3
76.3
R2
79.5#0.4
73.8=0.3
77.0:1.33
76.3=0.5
GCN Embeddings
(task-specific)
GCN in R2
93.410.33
03.1
GCN in R2
92.1
91.4=0.5
GON R%
89.5+0.4
90.3+0.4
Table 17: Results for link prediction on CORA and CITESEER using different embeddings.
129
8GC
GCN
SGC
GCN
GAT
32
93.410.3
01.210.3
92.5.003
00.2.10.4
02.1100.3
02:210.3
93.7.10.5
91.610.5
02.510.3
92.8
93.0.10.3
91:010.3
R7
91.320033
91.120.2
90.720.1
90.2:0.5
90.920.5
90.820.3
80.5:0.5
92.120.5
91.1=0.5
91.120.8
80.210.5
R230
89.01.0.4
66.2100.
67.81.0.3
87.410.4
89.11.0.4
87.2.0.55
88.8 88.33
68.410.5
89.5.0..4
88.2.0.3
87.8.0.3
87.210.5
84.820.3
84.320.2
67.720.3
86.610.3
86.12:0.3
69.020..5
88.720.3
85.920.3
86.1
92.1=0.6
89.910.4
87.7:0.3
Table 18: Results on CORA for link prediction.
D.3 Recommender Systems
Implementation Details. We follow a metric learning approach Vinh Tran et al. (2020), with the implementation of all baselines taken from López et al. (2021). We minimize the hinge loss function for ML-100K and LAST.FM, while minimizing the binary cross-entropy (BCE) function for MEETUP. We use the RsGD optimizer (Bonnabel] 2011) to tune graph node embeddings. In all setups, we run the same grid scarch to train recommender systems. We train for 500 epochs, reduce the learning rate by factor of if the model does not improve the performance after 50 epochs. We stop training when the loss on the dev set has not been decreased for 50 epochs. We use the burn-in strategy (Nickel & Kiela 2017 Cruceru et al 2020) that trains recommender systems with a 10 times smaller learning rate for the first 10 epochs. Wc experiment with three hyperparameters: (a) learning rate E (0.1, 0.01, 0.001); ) (b) batch size E (512, 1024, 2048) and (c) maximum gradient norm E (5, 10, 50). Table 19 reports the stats of all the bipartite graphs in the recommendation task.
Model. Given set of entities and target metric space (X,dx), associate with each entity e e an embedding f(e) X and bias terms be: rhs E R, where f - X is learnable embedding function. Given a pair of entities e2 E E, the model computes a similarity score o(e,,e)) as follows
(e1,,(ee,, = ,hs + beg (f(e)),
(6)
Subtracting the square distance ensures that the entities whose embeddings are closer in the metric space have a higher score, making it suitable representation of similarity. The model we use is shallow: It learns collection of points f(e) E M indexed by the entities e E E. In our setting, E = UUV, where U is the space of users and V is the space of items.
Hinge Loss Function. Given set T= is given by:
= ()), of observed user-item interactions, the hinge loss function
L= Σ Σ Im + (5,,x(u, - x1,.x(u, w))+
(u,o)TT (u,w)TT
where w is an item the user has not interacted with, m is the hinge margin, and [z]+ maz(0, 2). For each user u, we generate a negative set by randomly selecting 100 items that the user has not interacted with.
Binary Cross-Entropy Loss Function. Let T and Tz be a set of observed user-item interactions and a sot of non-interactions, respectively. Consider T= Ti UT2 as the collection of all interactions and non-interacttons. For each pair (u, v) E T, let Vu.r (0, 1} denote the true label: If the pair belongs to Ti, then ya,s 1,
25

---

Published in Transactions on Machine Learning Research (05/2024)
Dataset
Users
Items
Interactions
Density (%)
ML- 100K
943
1,682
100,000
6.30
LAST.FM
1,892
17,632
92,834
0.28
NRCTUP-NYC
46,895
16,612
277,863
0.04
Table 19: Recommender system dataset stats
Normed Space
E Enelidesn Space
68 Normed Space
1.0
0.0
0.5
0.0
0.5
Bg Pincare Syace
SPD Symnmetric Space
Eij H.] Producc of Poincare and Nortee Spaces
0.0
Figure 4: Embodding distortion shown in various spaces small expandor-chordal graph. Color range indicates distortion levels.
otherwise Va,e = 0. The BCE loss function is given by:
== Σ Yu,v log(o((),axxu.)))) v))) - (1 ya.o) log(1 ((,),,,(u,)))),
(8)
(T.
where [(x) I+c is the sigmoid function. For each user u, generate negative set by randomly selecting one item that the user has not interacted with.
E Supplementary Graph Reconstruction Analysis
Results of Expander Graphs. For readability, choose to embed small expander graph into various spaces and visually compare embedding distortion in these spaces, displayed in Figure 4 We find that both normed spaces perform much better than other spaces. Further, we see that the graph undergoes small distortion in the & space and unnoticeable distortion in the foo space when dealing with a small expander, although embedding expanders into normed spaces well-known challenge (Linial et al. 1995 Proposition 4.2).
F Trees, Grids, and Fullerenes
In our Large Graph Representational Capacity experiments (Section we used trees, grids, and fullerenes as discrotizations of manifolds with negative, zero, and positive curvatures, respectively. Refer Figure for a visual illustration of these discretizations. In chemistry, a fullerene any molecule composed entirely of carbon in the form of hollow spherical, ellipsoidal, cylindrical mesh. In experiments, used combinatorial
26

---

Published in Transactions on Machine Learning Research (05/2024)
Top: surfaces of negative, zero, and positive curvature (from left. to right). Bottom: graphs of negative, zero, and positive curvature (from left to right).
Figure 5:
graphs representing spherical fullerenes. We generated the fullerene graphs using the graphs. fullerenes function from SageMath (The Sage Developers) 2023). The number of possible fullerenes grows fast. function in the number of nodes (OEIS Foundation Inc. 2023 A007894), and used the first fullerenc graph generated by graphs. fullerenes () for each node count. The graph data for the specific fullerenes used in our experiments can be found in our code repository, ensuring reproducibility and facilitating further analysis. Trees and grids are well-known and require no further description.
27


Reviews:
[{"review_id": "EBhG3ZUUKJ", "reviewer": "Reviewer_oocY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper offers a novel approach by underscoring normed spaces as a more flexible, computationally efficient, and technically less challenging alternative to popular methods for learning graph embeddings.\n\n2. The proposal is grounded in theoretical results from discrete geometry, providing a solid foundation for using normed spaces in embedding finite metric spaces with low distortion bounds in low dimensions.\n\n3. Empirical evaluation on synthetic and real-world benchmark graph datasets demonstrates the superior representational capacity of normed spaces, outperforming various Riemannian manifold alternatives across diverse graph structures and curvatures.\n\n\nWeaknesses:\nI do not see any major weaknesses. The requested changes section lists my concerns, questions, and suggestions below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores the normed spaces to embed finite metric spaces with low distortion bounds in low dimensions. Drawing inspiration from the theoretical foundations in prior works (Johnson & Lindenstrauss, 1984; Bourgain, 1985; Linial et al., 1995;  Krauthgamer et al., 2004 ), the authors advocate for normed spaces as a flexible and computationally efficient alternative to popular Riemannian manifolds for learning graph embeddings. Through extensive experimentation on synthetic and real-world graph reconstruction benchmarks, normed space embeddings demonstrate superior performance compared to traditional manifolds while requiring significantly fewer computational resources. Additionally, empirical validation across graph families associated with various curvatures underscores the adaptability of normed spaces in capturing diverse graph structures as graph sizes increase. Furthermore, the paper showcases the practical utility of normed space embeddings in tasks such as link prediction and recommender systems, offering a valuable tool for geometric graph representation learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is generally well written, however, from the point of view of a general reader in ML it would be helpful to make these changes.\n\n1. Section 3 would be much better with some more background on normed spaces and other embedding spaces. I can see it in the Appendix, it would be helpful to have abridged version of it in the main paper. \n\n2. In Section 3. the main point being made is \"large classes of finite metric spaces can in theory be abstractly embedded with low theoretical bounds on distortion in low dimensional normed spaces\". It would be better to clearly state this at the start the section  and then give the evidence by discussing the prior works as it is done in the middle paragraphs. If possible add some more details about the the kind of metric spaces for which the results apply. It would be great if these results can be discussed in depth in the Appendix and have a table summarizing the results in the main paper. \n\n3. The authors did not discuss pseudoEuclidean embeddings (PSE). These are also a great choice for embedding discrete metric spaces since any discrete metric space is isometrically embeddable in PSE spaces and they also contain normed vector spaces. See figure 2.1 in [1].  I am curious to see how these embeddings will perform for the settings considered in the paper. Please see the references below for PSE. \n\n4. Have a table (maybe in the appendix) summarizing various embedding spaces used in the experimental results. \n\n[1] Goldfarb 1985, A new approach to Pattern Recognition,  Progress in Pattern Recognition.\n\n[2] Vishwakarma & Sala, 2022, Lifting Weak Supervision to Structured Prediction, NeurIPS 2022.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lzHRwLRNQu", "reviewer": "Reviewer_o9MM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThe paper is very well written, includes the relevant background and cites prior work appropriately. The authors support their claims in both synthetic settings as well as real-world tasks, and the results look significant. The author's proposed embedding space is also computationally more efficient than the baselines, and more straightforward to implement.\n\n### Weaknesses\nNo theoretical justification for the observed results are presented. The author's claims rest entirely on empirical observation, and since all methods under consideration are trained via gradient descent this leaves open the possibility that hyperparameter tuning or different training techniques could allow opposite results to be achieved. The size of the graphs under consideration are relatively small, it is unclear if these benefits would translate to graphs of larger scale.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose using normed spaces, with particular emphasis on $\\mathbb R^n_{\\ell^1}, \\mathbb R^n_{\\ell^\\infty}$, to represent nodes in a graph. They contrast this with metric spaces such as hyperbolic or spherical embeddings which have been motivated by the fact that their metric may more naturally align to capturing distances in certain graphs, and have provable bounds on the distortion. The authors of this work show empirically that embeddings in $\\mathbb R^n_{\\ell^1}$ and $\\mathbb R^n_{\\ell^\\infty}$ can be effectively trained via gradient descent to outperform a variety of alternative geometries, including hyperbolic and spherical, on graph reconstruction, link prediction, and recommendation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Asymmetric Loss Function:** In the discussion here the authors claim that Figure 4 (b) and (c) shows that the asymmetry in the loss function has a bigger impact on the small tree. This is not clear to me from the figures. The asymmetry in the loss function would have suggested that nodes which are closer than they should be get less of a penalty than nodes which are farther apart, but the graphs show the opposite (namely, that smaller trees have a larger number of nodes which are farther apart than they should be). In addition, I think more graphs should be inspected if one wants to make a more general statement in this regard. For example, trying a variety of graph sizes and calculating, for each one, the number of pairs which over vs. under-estimate the distance, and then plotting the average of this for each graph size. To be fair, however, I think the asymmetry is not much of an issue - after all, the loss function directly targets the distortion, so it is minimizing exactly the metric it will be evaluated on.\n\n**Link Prediction:** In Section 4.1 \"baseline experiments\", the authors state that their focus was on settings with small dimensions, where it was known that geometric embeddings tended to outperform Euclidean. The results in Table 3 suggested $\\mathbb R_{\\ell^2}$ and $\\mathbb R_{\\ell^\\infty}$ achieved lower distortion even when $n$ was small. When evaluating link prediction in Section 4.2, however, the authors switch to using a larger embedding dimension. Are larger embeddings required to see a benefit here? Do the results of Section 4.1, where $\\mathbb R^n_{\\ell^2}$ and $\\mathbb R_{\\ell^\\infty}^n$ outperformed alternative geometric embeddings in low dimensions, not transfer to this setting?\n\n**Training vs. Representational Capacity:** Some of the proposed baselines have very strong theoretical bounds on distortion for certain graphs - for example, the fact that hyperbolic space can embed any tree with arbitrarily low distortion - whereas the results for normed spaces are less impressive. Thus, it seems to me that an implication of the author's claims is that normed spaces can be *trained* more effectively than more complicated geometric counterparts. On the other hand, for $\\mathbb R_{\\ell^\\infty}$ gradient descent would essentially be operating as coordinate descent, since only one dimension would appear at a time. Have I correctly inferred the implication of the author's claims, and if so how is this explained in light of the sparse gradient in the $\\mathbb R_{\\ell^\\infty}$ setting?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9Kq5EoPVsX", "reviewer": "Reviewer_rchM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The proposed method is simple and can be integrated into different techniques. Evaluating the loss function is computationally efficient in case the shortest paths are pre-computed. Thus, the proposed method can be applied to very large graphs.\n\n- The presented empirical results are strong. Normed space embeddings lead to low distortions and can thus tackle the graph reconstruction problem better than other types of embeddings.\n\n- The paper is well-written and easy to read. All details are clearly explained.\n\nWeaknesses:\n\n- It is not clear to me how Section 3 is connected to the rest of the paper. In my understanding, the theoretical statements presented in this Section do not apply to the proposed embeddings and the authors should explain why.\n\n- There is a lack of explanations or insights about the employed loss function. What are the advantages of such an asymmetric loss function over standard loss functions such as the mean squared error or the mean absolute error?\n\n- The learned embeddings are not directly compatible with standard machine learning algorithms that operate in Euclidean spaces. Embeddings serve as general representations of objects that can be used in different downstream tasks. Could the learned embeddings be combined with a standard classification algorithm such as logistic regression or an MLP?\n\n- In the reported results, the embedding dimension is always set to 20. Typically, the embedding dimension is treated as a hyperparameter since different values might lead to very different results.\n\n- No intuition is given on why a specific norm ($\\ell_\\infty$) works better than the rest of the norms in most cases. It would be useful to a practitioner to know which norm to use in a specific application.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes to embed nodes of a graph in normed spaces. The authors use a very simple algorithm which randomly initializes the embeddings of the nodes and uses gradient descent to minimize an asymmetric loss function which compares norm distances against shortest path distances. The proposed embedding method is evaluated in the task of graph reconstruction, but also in the task of link prediction and in a recommendation task. In most cases, the normed space embeddings outperform other baseline embeddings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The requested changes listed below are related to the weaknesses of the paper presented above.\n\n- From Section 3: every tree $T$ with $n$ vertices can be embedded isometrically in $\\ell_\\infty^{\\mathcal{O}(\\log n)}$. Will the proposed learning algorithm embed isometrically a tree $T$ with $n$ vertices in $\\ell_\\infty^{\\mathcal{O}(\\log n)}$? If the answer is no, please explain why.\n\n- Give a justification why the proposed loss function is chosen over standard loss functions such as the mean squared error. I would suggest the authors provide some empirical results where the proposed function is replaced by the mean squared error.\n\n- I would suggest the authors investigate whether the proposed embeddings could be used along with standard learning algorithms. For example, the authors could evaluate the learned embeddings + logistic regression in a node classification task (such as Cora, etc.). \n\n- The authors should experiment with different embedding dimension sizes. Ideally, the embedding dimension size could be treated as a hyperparameter and thus be tuned.\n\n- Please, provide some intuition on how a practitioner can choose which norm to employ in a specific application.", "broader_impact_concerns": "no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies network embeddings into normed spaces. This builds on earlier work embedding graphs into Riemannian manifolds, which showed that Euclidean embeddings can be outperformed (i.e., lower distortion at the same number of dimensions). The authors propose an even simpler approach. The work presents empirical results showing very strong results.

All reviewers suggest accepting. I agree with their assessment. This is strong empirical work showing how a simple idea works very well. Such work is very useful, especially for a field where the trend is to look for more and more exotic manifolds to embed into.
Decision: Accept (poster)