Shedding Light on Problems with Hyperbolic Graph Learning
Authors: Isay Katsman
Anna Gilbert
Venue: Accepted by TMLR ()

Abstract: Recent papers in the graph machine learning literature have introduced a number of approaches for hyperbolic representation learning. The asserted benefits are improved performance on a variety of graph tasks, node classification and link prediction included. Claims have also been made about the geometric suitability of particular hierarchical graph datasets to representation in hyperbolic space. Despite these claims, our work makes a surprising discovery: when simple Euclidean models with comparable numbers of parameters are properly trained in the same environment, in most cases, they perform as well, if not better, than all introduced hyperbolic graph representation learning models, even on graph datasets previously claimed to be the most hyperbolic as measured by Gromov $\delta$-hyperbolicity (i.e., perfect trees). This observation gives rise to a simple question: how can this be? We answer this question by taking a careful look at the field of hyperbolic graph representation learning as it stands today, and find that a number of results do not diligently present baselines, make faulty modelling assumptions when constructing algorithms, and use misleading metrics to quantify geometry of graph datasets. We take a closer look at each of these three problems, elucidate the issues, perform an analysis of methods, and introduce a parametric family of benchmark datasets to ascertain the applicability of (hyperbolic) graph neural networks.

Published in Transactions on Machine Learning Research (03/2025)
Shedding Light on Problems with Hyperbolic Graph Learning
Isay Katsman
isey.katsmaan@@yae.cco eduu
Deportment of Applied Mathematics
Yale University
Anna Gilbert
anna.gibert@@ol... edu
Department of Applied Mathematics
Department of Statistics Data Science
Department of Electricol Engineering
Yale University
Reviewed on OpenReview: openreviee. net/ forum? id= 3K33
Abstract
Recent papers in the graph machine learning literature have introduced number of ap- proaches for hyperbolic representation learning. The asserted benefits are improved perfor- mance on a variely of graph lasks, node classification and link prediction included. Claims have also been made about the geometric suitability of particular hierarchical graph datasets to representation hyperbolic space. Despite these claims, our work makes surprising discovery: when simple Euclidean models with comparable nunbers of parameters are properly trained in the same environment, in most cases, they perform well, if not better, than all introduced hyperbolic graph representation learning models, even graph datasets previously claimed to be the most hyperbolic (Chami et al., [019)] as measured by Gromov 6-hyperbolicity (i.e., perfect trees). This observation gives rise to a simple question: how can this be? We answer this question by taking a careful look at the field of hyperbolic graph representation learning as it stands today, and find that a number of results do not diligently present baselines, make faulty modelling assumptions when constructing algorithms, and use misleading metrics to quantify geometry of graph datasets. We take closer look at each of these three problems, elucidate the issues, perform analysis of methods, and introduce parametric family of benchmark datasets to ascertain the applicability of (hyperbolic) graph neural networks.
1 Introduction
Graph machine learning has undergone metcoric rise in popularity over the course of the last several years. Given the ubiquity of graphs, and the demonstrated capabilities of machine learning in modern large-scale data contexts, it has been unsurprising to see widespread interest in designing machine learning models that can do predictive inference over these fundamental structures. Relevant graph tasks that researchers have focused on include link prediction (when a model must predict whether two nodes are connected or not) as well as node classification (when a model must predict one of discrete set of classes for a given graph node).
Simultaneously, recent research from Bronstein et al. (017)) and others has brought altention to the fact that several kinds of complex data benefit from manifold considerations. In particular, Nickel & Kiela (0177) has shown that troc-like graphs (that is, graphs with hierarchical structure) benefit from representation through hyperbolic node embeddings, in that such embeddings frequently yield lower distortion than their Euclidean analogs. This line of work is well motivated by Sarkar (2011), which first showed that trees can be embedded with arbitrarily low distortion in hyperbolic space something that does not hold for Euclidean space.
In an attempt capitalize on these improved con-Euclidean representations for tree-like graphs, a number of graph machine learning papers began to incorporate non-Fuclidean representations into their pipelines. This

---

Published in Transactions on Machine Learning Research (03/2025)
resulted in number of highly infiuential papers, namely Ganea et al. (2018) and Chami et al. (019 ),
both
of which later inspired even more related geometric graph machine learning work (Shimizu et al.
2020 Chen
et al. 2021 Zhang et al. 2019: 2021). These papers had both novel and interesting aspects that attempted
to maximize hyperbolicity of the model in an effort to make the best use of the data.
f2
fi
0.6
fa
1.3
4.2
0.3
-1.7
-111
0.2
2.2
x2
R²
33
H
22
1
X
1
1
3
μ
0.8
3
-2.1
0.3
V
T3
d(u, x3)
d(z;, 2, for i #
d (1e, xii) =
dH:(H, 2ii =
dæ (2;, = V3, for +
d = 2, for i +
Figure 1: Above is example where give the best Euclidean embedding of tripodal graph, associated with a toy graph dataset (comprised of the tripodal tree and associated node features, fi), in R2, i.e. the embedding that has lowest average distortion. We see that the largest amount of separation we can get between the leaf nodes while maintaining the distances between the root and leaf nodes v3 z 1.7, falling short of 2. In contrast, we give the best hyperbolic embedding of the same tree in HP. Note that the embedding has high gcometric fidelity, i.c., all distances can be preserved. We compute this embedding explicitly in Appendix
That being said, in the process of expanding and generalizing models, several papers strayed from the original theoretical and primarily geometric motivations behind non-Fuclidean embeddings for trees, frequently pursuing the design of more general models without thoroughly considering the models' appropriateness for the data on which they were being used. We posit this one of the reasons for the following main discovery of paper: prior benchmark lasks, when simple Euclidean models with a comparable number of parameters are trained in the same environment these state-of-the-art hyperbolic models, the Euclidean models match or outperform the hyperbolic models on the "most hyperbolic" datasets, as measured by Gromov 8- h-hperbblicity. We demonstrate this specifically for the link prediction and node classification tasks presented originally in Chami et al. (2019), and used in a number of papers thereafter (Chen et al. 2021 Zhang et al. 2019 2021). Investigating this further, we find there are three fundamental problems that led. to this unfortunade state of afTairs:
(i) The Euclidean baselines used in these papers were either buggy, or insufficiently trained, thereby yielding misleading representation of inferiority.
On a more fundamental level, this led us to the observation that the original test tasks were selected incorrectly. Explicitly, we observed that the test tasks were too easy. They were easy enough to not yield statistically significant scparation between the performance of Euclidean basclines and state- of of-the-art hyperbolic models, they were even too weak to separate the performance of a Euclidean baseline that. uses only features from the performance of Fuclidean baseline that incorporates graph
2

---

Published in Transactions on Machine Learning Research (03/2025)
information. Most of the hyperbolic test tasks in Chami al. 2019 are in fact trivially solvable with simple Euclidean multi-layer perceptron that does not utilize any graph information. This suggests the need for much harder test tasks, if we are to make any conclusions about the effectiveness of incorporating graph information, let alone the effectiveness of hyperbolic methods in these contexts.
(ii) Graph machine learning models began using hyperbolic representations for Euclidean features without any justification for the hyperbolic nature of said features (in contrast to the extant hyperbolic nature of nodes in tree-like graphs). Additionally, modelling assumptions were frequently made that sacrificed geometric fidelity for the sake of convenience.
(iii) Using Gromov 6-hyperbolicity (Gromov 1987 as a proxy for graph datasct suitability to learning in hyperbolic space is flawed. Notably, d-hyperbolicity is a characteristic of the graph alone, yet a graph dataset includes node features and frequently node labels. Moreover, Gromov &-hyperbolicity is too coarse metric for the purpose of understanding graph geometry at a finer level.
We expound on each of these three points in our paper, conducting rigorous experiments that give ample evidence to demonstrate each point, while resolving a subset of key issues and laying the grounds for a more comprehensive study. Our contributions are as follows:
1. On several of the original most hyperbolic test tasks, we demonstrate that simple Euclidean model outperforms or matches a variety of state-of-the-al. hyperbolic (and non-trivial Euclidean) models.
2. We explain the underlying causes of this phenomenon, expounding upon each of the problems (i), (ii), and (iii) above, providing relevant evidence and resolving a core subset of issues.
3. We perform an analysis of existing methods, and introduce parametric family of benchmark datasets that help establish the applicability of (hyperbolic) graph neural networks.
2 Related Work
Our work addresses and is related a specific subset of the hyperbolic machine learning [Bronstein et al., 2017] literature that deals with graphs in the context of intragraph prediction. Specifically, we deal with tasks such as link prediction, in which one must predict whether two nodes are connected (Kipf & Welling 2017), and node classification, in which one must predict one of a set of classes for individual nodes in a graph (Kipf & Welling 2017). That being said, we believe several problems we point out about the way hyperbolic graph learning is being done currently may hold more generally.
Distortion Distortion is fundamental to the discussion of geometric representation learning but is not used in number of the aforementioned papers. One must. recall the original theoretical motivation from /aakar (2011) was provide natural embedding for trees (undirected, connected, acyclie graphs) in which distortion of graph distances could be made arbitrarily small. That is, seek embedding of the graph into metric space (M,dM) in which the distance metric dM captures the original graph distances as well as possible. Typically, the continuous nature of M yields considerable benefits over the original discrete graph structure.
For a given dimension, it may be impossible to obtain a Euclidean embedding with high geometric fidelity but this may be possible in a hyperbolic space. Take for example the task of two-dimensional embedding of the tripodal tree, with one root and three children, shown Figure ] The optimal embedding in R² does not have high geometric fidelity as it does not preserve the graph distances faithfully. In contrast, we see in the same figure that when the same graph is embedded in H2, we can recover distances of 2 between the children (see Appendix A for full details), staying faithful to the original graph. This example provides some intuition for the suitability of hyperbolic space for tree embeddings.
Graph neural networks Graph neural networks, and perhaps more broadly, the application of mod- ern machine learning to graph tasks, begins with the paper Kipf & Welling (2017). which introduced Graph Convolutional Networks (GCNs). The ubiquity of graphs and the power of large scale modern machine learning quickly transformed graph machine learning into an incredibly large and diverse field
3

---

Published in Transactions on Machine Learning Research (03/2025)
Veelickvii et al. 2018). That being said, these methods were not without their problems. Wu et al. (0019 pointed out that many of the modifications being made to graph neural networks (GNNs) were at their core, superficial, and presented a way to considerably simplify GNNs. Additionally, Huang et al. (2020)
showed that a very simple graph neural network construction with few parameters could outperform most slate-of-the-art models with an order of magnitude more parameters. Such papers proved very useful at
forcing the field to step back and think about what methodological changes were truly useful. In similar sense, our paper aims to push current hyperbolic machine learning papers, particularly in graph contexts, for more rigorous research and careful methodological proposals.
Hyperbolic graph machine learning Hyperbolic graph machine learning can be viewed either as subfield of geometric machine learning (Broustein et al. 2017] or as a subfield of graph machine learning. Either way, it has enjoyed increasing popularity over the course of the last several years. The original line of work from Nickel & Kiela (017)) was principled in that wanted to generate better embeddings for trees (WordNet. Fellbaum 2000) hicrarchics, to be procise) via hyperbolic embedding. Concurrently, Ganea et al. (2018) began to extend classical Euclidean neural networks to hyperbolic space. Issues in the principled nakure of the work began to arise when researchers began to push hyperbolic neural networks to do intragraph prodiction. A prominent carly paper exemplifying this is Chami et al. 2019 While mentioning distortion several times for motivation, it loses sight of what it actually means to minimize distortion (i.e., distortion is with respect to a graph embedding). In this work, features are mapped into hyperbolic space despite the fact that there is no direct evidence for their hyperbolicity, in contrast to the nodes themselves that are best suited to hyperbolic space assuming the graph a tree. Further papers that build upon Chami et al. (219
such as Zhang et al. (2019), Zhang al.] [2021], and Chen et al. (2021) follow the framework of initially mapping the features into hyperbolic space. Their innovations are primarily architectural: Zhang et al. 2019 introduces Hyperbolic Graph Attention Networks (HATs), Zhhang et al.
(2021) introduces Lorentzian Graph Convolutional Networks (LGCNs), and [Chnn et al. (2021) introduces a hyperbolic neural network capable of
expressively capturing Lorentz boosts, in contrast to Ganca et al. (2018) Katsman et al. (023) introduces a
general manifold version of residual neural network and uses hyperbolic space as a use case, comparing against the above methods.
Graph curvature One of the claims we put forth is that geometric graph measures previously used are insufficient to capture the geometry of the graph, let alone the graph dataset (comprised of the graph, features, and frequently node labels). Notably, Gromov 5-hyperbolicity has been previously used in Chami et al. 2019)) Chen et al. (2021); 3 in particular, the same number, 0, is assigned to all trees despite considerable potential differences in geometry (e.g. branch factor). Graph curvature measurcs, such as Ollivicr Ricci curvature (Lin et al. 2011), have been previously studied as a way to more granularly characterize graphs, but are seldom used this context. Please see Appendix for further details.
3 Background
We give the primary background necessary to understand the key results of this paper. In particular, we introduce some essential definitions from Riemannian geometry, give necessary background on hyperbolic space, and demonstrate explicitly how [Chmmi et al. (2019): Liu et al. (2019) : Zhang et al. (2019 2021 map features from Euclidean to hyperbolic space; also define Gromov 8 o-hyperbolicity.
3.1 Riemannian Geometry
We establish relevant definitions from Riemannian geometry Lee 1997).
Manifold An n-dimensional manifold M is topological space that is locally homeomorphicjit. R".
Tangent space The tangent space T.M at x of a manifold M is defined as the vector space of all tangent vectors at x and is isomorphic to I.".
Riemannian manifold A Riemannian manifold is a manifold M equipped with a Riemannian metric,
p == (Px)zeM: a smooth collection of inner products Pa : T.M x T.M + R for every x E M.
IA homeomorphism is contimuou bijection with continuous inverse.
4

---

Published in Transactions on Machine Learning Research (03/2025)
Geodesics and induced distance function Given a Riemannian manifold (M. p) and curve [a, M, we define the length of y to L(7) = Ja (lb' dt. For æ, E M, the distance d(z, y) = inf L(n), where y is any curve such that 7(a) 2; ((b) = y- A geodesic Tay from to y should be thought of as curve that minimizes this length.
Riemannian exponential map For each point E M and vector v T&M, there exists unique geodesic y [0, + M, where 7()) = 70) The exponential map exp, T2M M is defined by (x),(v) (1).
3.2
Hyperbolic Space
We give necessary definitions regarding hyperbolic space. A more detailed treatment be found in
Lee
1997)
Hyperbolic space Hyperbolic space is the Riemannian manifold of constant negative sectional curvature
K < 0. Here we deal with the hyperboloid model of hyperbolic space: where 2) is the hyperbolic inner product:
His = {o E 1 (r,x) x) K )
(z, v). = Zoo0 + ø1 + 221/ + +...... In0l
for x, y H... It is equipped with the pullback metric from 1=+1 Lee 1997p.
Hyperbolic exponential map The Riemannian exponential map for the hyperboloid model has closed form given by:
+ sinh(
/ [|]]|]|)
exp." K (v) cosh / K [
[ [K]]oolcc
where x e Hy and v E T,H
3.3 Mapping Features from Euclidean to Hyperbolic Space
Hyperbolic graph machine learning models are usually trained on graph datasets that have Euclidean features. In order for the models to process these fcatures, they map them to the hyperboloid via the exponential map. This the procedure followed by Chami et al. (2019); Liu al. (2019); Zhang al. (2019: 2021 Chen et al. (2021). Explicitly, the procedure as follows. Let xh E R denote the input Euclidean features. Let [VK 0,O..... ......... 0} E Hi denote the north pole (origin) in Hi,, which is the reference point used to perform tangent space operations. They interpret (0, ²)) as point in T& and use the exponential map map it to :
x" = expo ((0,x
||r VK
| ll
x
VK coch cosh
VK sinh
K
Notice how the origin for exponentiation is chosen arbitrarily. Moreover, observe that this use of hyperbolic space to represent the features is separate from any notion of improved distortion of graph embedding, discussed at length in Section 2 To give a concrete example, this would map the features from Figure [ into hyperbolic space, instcad of producing embeddings of the graph nodes. One can perhaps posit that the features are in some way representative of the original hierarchical relationship between the nodes, but this need not be the case. In other words, this ad hoc exponentiation is not well-motivated.
3.4 Gromov j-Hyperbolicity
Let G (V, E) be a connected graph with distance function defined as the number of edges on a shortest. path between a pair of vertices. Formally, the Gromov 5-hyperbolicity can be defined using the following four-point condition (Gromov] 1987).
5

---

Published in Transactions on Machine Learning Research (03/2025)
Given a graph G (V, and four vertices x. y, u, V with:
d(r,y) ) + d(u, 1) 2 d(z, u) + d(y,v) 2 d(x,v) + d(y, u)
the hyperbolicity of the quadruple n, y, u, denoted as ó(x, y, u, v) is defined as:
V,, y, u, u) = (d(x, v) + d(u, u) (d(x,, u) + d(y, e)))/2
and the d-hyperbolicity of the graph is 5(G) wwv 0(r V, u, v). Note that Gromov 8-hyperbolicity is nonnegative and can be thought of as measuring how "tree-like" a graph is The closer it is to 0, the closer a graph is to being a perfect tree. We reference the interested reader to Appendix B for additional intuition.
4
Elucidating Problems
In this section, revisit the problems mentioned in Section and provide relevant evidence for our claims.
4.1 Misleading Presentation of Strength of Hyperbolic Graph Models
Properly-tuned Euclidean models outperform hyperbolic models A somewhat persistent issue across a number of prominent geometric graph machine learning papers is either buggy or poor implementation of Euclidean baselines. Such an issue does indeed arise in the publicly available code for Chami et al. (2019). We discuss the details of the bug and the fix in Appendix F In short, the central issue is that two lines in the implementation of the MLP normalize all Euclidean features to lie within the unit ball; commenting these two lines alleviates this issue. Although this introduces some numerical instability to the Permi-Dirat decoder, there is also a simple one line fix for this that we also give in Appondix [ The removal of this bug allows for the Euclidean representation space to be fully utilized, i.e., the features are no longer constrained to unit ball.
If we fix bugs in a Euclidean baseline of Chami et al. (2019) said model outperforms or matches all hyperbolic models on nearly all of the most hyperbolic datasets of that paper. The results for the non-buggy version of the multi-layer perceptron Euclidean model in Chami et al. (2019) are given in the "MLP (debugged)" row of Table D All results are given by mean and standard deviation over 5 trials. As is evident, the debugged Euclidean model trivially solves nearly all of the most hyperbolic lasks. The Euclidean MLP presented in the original GitHub repository" attains 98.7 + 0.2 test ROC AUC for link prediction (vs. 72.6 + 0.6 for the original) on Discase (Chami al. 2019 and 80.3 = 0.7 test F1 score for node classification (vs. 28.8 + 2.5 for the original) on the same dataset (as shown in Table [ above). These are increases of 43.5 and 20.6 standard deviations, by the standards of the originally presented link prediction and node classification results for this model, respectively. The link prediction result for Disease-M is 99.1 + 0.3 test ROC AUC (vs. 55.3 + 0.5 for the original) after the correction, up 87.6 standard deviations from the original result. The one exception is Disease NC, for which the difference between the debugged and original version is staggering (80.3+ + 0.7 versus 28.8 + 2.5), though the result is not state-of-thh--te It is also worth noting that the Euclidean MLP attains these results without the graph, since it uses features alonc! The graph neural network basclincs on the table (under subheading "GNN") are standard near state-of- of-the-art baselines used in the graph neural network literature. The "Hyp N models are all various different hyperbolic neural network models, with either HyboNet (Chen et al. 2021 or G-RResNet Horo (Katsman et al. 2023) being the current state-of-the-art on these test tasks.
It should be noted that a number of papers (c.g. HyboNet Chen et al. 2021 make dircct use of the experimental setup provided originally in Chami et al. 20019) hence we effectively have that the original issues with baselines cascade and affect the experimental setup for many papers at once. To the best of our knowledge, none of these papers noticed the issues with the Euclidean MLP baseline. The experimental
details for Table are given in Appendix
Pllease find the original GitHub repository for Chami 2019) at httpp:///tthuu..cmm Haaaaamm//aaaaaaaaaa TrlazyRReeercchheee hngnn TThe authors were unahle provide the datasel to oblain this result.

---

Published in Transactions on Machine Learning Research (03/2025)
Dataset Hyperbolicity
Disease
Disease-M
Airport
8 =0
0
8 I
Task
LP
NC
LP
NC
LP
NC
Euc (Chami et al.
2019
59.8+2.
32.5+1.1
=2.0=0.0
60.9
Shallow
Hyp Nickel & Kiela, 2017
63.5
45.5+s.3
94.5
70.2
Euc-Mixed
49.6#11
35.2+s.4
91.5 91.5+0.1
68. 68.3
Hyp-Mixed
55.1+1a
56.9+1.5
93.3+o.0
69.6+o.1
MLP (original)
72.6=o
28. 28.8
55.3=0.b
55.9 [
89.8
68.6.0.6
NN
MLP (debugged)
98. to.2
80.3
99. 99.1
96.4
95.9
GCN (Kipf & Welling
2017
64.7
19.7
66.0
59.41a.
89.3
81.410.6
GNN
GAT
Velickovic et al.
2018
69.8
70.4
69.5=a.4
62.5
90.5
81.5+0.a
SAGE
Mamilton et al.
2017
=
69.
67. 67.4
61.3
90.4
82. 20.5
SGC
Wu et al. 2019
65.1+
69.5+a.2
66.2 06.2#n.
60.5+o.s
89.8+0.a
80.6+0.1
HNN
Ganea et al. 2018
15.1+
41.0+1.s
60.9+n.4
56.2+o.s
90.8+0.2
80.5+o.s
HGCN Chami et a..
2019
90.8+0.a
74.5+0.9
78.1+
72.2-o.5
96.4+0.1
90.6 +0.2
Hyp NN
HAT
Zhang et al.
2019
91.810s
83.610.9
LGCN [Zhang at al.. 2021
96.6.u.
84.4
96.0
90.9 11.7
IlyboNet (Chen et x..
2021
96.8
96.0=1.
97.3
90.9
G-RResNet Horo Katsman et al. 2023
08.410.3
95.421.
25.2
97.4
Table 1: Above we give graph task results for a debugged version of the Euclidean model from Chami et al.
(219)) compared other models, including the current state-of-the-an models from Chen et al. (2021) ) and Katsman et al. 2023). The metrics reported are test ROC AUC for link prediction and test F1 score for node classification. Means and standard deviations are given over trials. After the bug fix, the Euclidean "MLP (debugged)" entry above allains or nearly matches stale-ofthhe-rrl results on most of the hyperbolic test tasks in the paper. We highlight the best result only if the result gives a p-value less than 0.01 after running a paired significance t-test against the next best result.
Baselines for hyperbolic knowledge graph tasks It should be noted that Euclidean baselines in other papers can frequently be made stronger. We show a more typical scenario via a subset of the knowledge graph lasks in Chami et al. (2020), specifically those that "exhibit hierarchical structures." " In particular, we note that carefully tuned Euclidean models considerably decrease the gap between the baseline Euclidean models in that paper and the introduced hyperbolic models. Results are given in Appendix D (Table 3).
4.2 How Did this Happen?
Poor dataset selection The results in Table ! suggest that the graph structure, and perhaps geometric fidelity more broadly, is irrelevant solving node classification and link prediction on the "most hyperbolic" tasks presented in the cited subset of hyperbolic machine learning papers. Please note that both Disease and Disease-M are the most hyperbolic datasets presented, as measured by Gromov d-hyperbolicity (the d-hyperbolicity is O, meaning the graphs from both datasets are perfect trees). The fact that a Euclidean model with no graph information (i.c. a model that only uses features) effectively solves the most hyperbolic tasks led us recognize what is perhaps an even more fundamental problem of the original work: the graph tasks selected were quite poor, in that they could not serve their purpose of distinguishing the hyperbolic models from baseline Euclidean models, simply because the multi-layer perceptron Euclidean model already solved the tasks with no graph information. To avoid this, we claim one must first ensure that the graph tasks benefit from geometry, i.c., that usage of the graph markedly improves performance. We elaborate on this further in Section 5
Poorly motivated model design model design feature that has persisted in hyperbolic graph neural networks due to very carly adoption from Kipf & Welling (2017) is the failure to distinguish between nodes and node features. Graph convolution convolves the node features as de facto substitutes for the nodes themselves. However, when deal with these graphs in a geometric context, it is important to recall that.
7

---

0.8 Published in Transactions on Machine Learning Research (03/2025)
the benefit we obtain from Sarkar 2011 in terms of embedding trees in hyperbolic space only holds if we explicitly embed the nodes in hyperbolic space with respect to the original graph distances. Simply mapping the node features to hyperbolic space, as discussed in Section 3.3 does not necessarily capture the original graph geometry. One may perhaps make the argument that the features should by proxy capture some of the original hyperbolicity of the graph, but there are myriad counterexmmple for this and hyperbolicity of features has never been defined, let alone demonstrated. The failure recognize and/or to explicitly address this is what makes the decision to exponentiate features in Chami al. (2019); Zhang et al. (2019) 2021); Liu et al. (2119) and derivative work not methodologicallyy principled. The construction and the theoretical motivation presented originally by Sarkar (2011) diverge.
Poor geometric characterization of graph datasets Another problem is that the metric used to quantify the "hyperbolicity" of the so-called "most hyperbolic" graph datasets characterizes only the graph, and moreover, does so in rather a coarse way. As we saw above, characterizing graph datasets via the graph alone can be extremely misleading, simply because the features alone are often enough to solve the relevant lasks. A proper characterization should take into account both the graph and associated node features. Additionally, using Gromov 8 d-hyperbolicty is quite coarse characterization of the graph, since 8 = 0 for all trees, regardless of considerable differences in geometry (e.g. differing branch factor). One must use more granular graph curvature metrics, for example Ollivier-Rict curvature, to more precisely characterize graph geometry. We refer the interested reader to Appendix B for a definition of Ollivier-Ricci curvature together with intuition. That being said, Ollivier-Ricci still a graph-level characterization and does not incorporate analysis of node features, which in some sense is a more central and pressing issue. One would need to develop more fundamental set of tools to properly characterize node feature geometry together with the geometry of the graph; we believe this is very fruitful and important avenue for future work.
Introducing Parental Dependence in Features
100
90
Test ROC AUC
80
70
HyboNet (y-0)
Dataset
Tree1111 (y = 0)
60
GCN (y-0)
MLP (debugged)
54.4+a.8
50
MIP (debugged) (y-0)
Model
GCN Kipf & Welling 2017)
55.52a.s
0.0
0.2
0.4
0.6
1.0
Parent Feature Coefficient (y)
HyboNet [Chen et al. 2021
48.4
Figure 2: Introducing parental dependence in node features very quickly leads the MLP to solve link prediction. Each data point is obtained by luning the MLP on the relevant synthetic dataset. The average of 5 trials is reported and the error region specifies one standard deviation.
Table 2: Link prediction results (test ROC AUC) for our synthesized Tree1111 dataset, mcant to illustrate context in which Euclidean models fail.
5 Initial Solutions
In response to the above presented problems, our solutions are test a well-tuned graph-less Euclidean MLP baseline on given graph dataset before making of graph machine learning method, using synthetic datasets to benchmark graph methods (or selecting tasks where graph structure is actually important for the task at hand, i.c., where using the features alone is not sufficient to solve the task), designing models well, based on theory (Sarkar 2011 (which implies usefulness of graph positional embeddings), and lastly, using
*Take for cxample datasct of airports for which scparate nodes, say major airports New York City and Shanghai, may be very different and far apart the graph while being very close in feature space (e.g. similar land area, occupancy, etc.). The point more generally that there is guarantee that the feature space structure will mimic the graph structure.
8

---

Published in Transactions on Machine Learning Research (03/2025)
quantitative graph dataset characterizations that capture both the graph and associated graph features to determine suitability of graph dataset to geometric machine learning method.
Euclidean MLP baseline Crucially, we recommend a well-tuned Euclidean MLP be applied first to a graph dataset (i.e. the features alone); if this method is insufficient, one should seek to use a graph neural network that makes use of the graph information together with the features. Even in this case, one should still be careful, since more recently Spehhle--Spiccher et al. (2024) points out different graph neural networks can perform quite differently on various benchmarks and it may be the case that the graph is not necessary (perhaps even detrimental) for given task using certain graph neural network.
Synthetic graph benchmark datasets The results in Table I show that these tasks make for quite a poor proxy to measure the benefit of using the graph, let alone the geometric benefit of the proposed hyperbolic approach. For proper benchmarking, one must attempt to select tasks that necessitate graph information.
Defining Tree(b, E, 7, 6, D) For the purpose of illustration, and to introduce an important set of synthetic graph machine learning benchmark lasks, we describe designing better alternative datasels to Disease and Disease-M M (Chami et al.) 2019). We do this by introducing a parametric family of dataset distributions that we denote by Trce(b, E, 7, ö, D): drawing a sample from given datasct distribution implics generating graph dataset whose graph is an é-level tree with branch factor b and whose features are generated procedurally, level-by-level, in the following way:
(0) ~ D
x (n) t r. p(x(()) + + +.2
v, where D
where .0(0) is the root node's feature vector and ((x(")) is the feature vector of the parent node of x(()), For the sake of concreteness, we will fix D = No, /100)) (i.c. the multivariate normal distribution over IR 1000 with mean 0 and identity covariance matrix) and ō = 1. Now note that y controls the level of parental dependence, which in effect controls the extent to which the features carry the graph structure (i.e. the extent to which the relationships of the Euclidean distances between features mimic the relationships of the graph distances between the corresponding nodes). If = 0, the features are entirely i.i.d. and carry no graph structure. To perform link prediction well on such a dataset, a graph machine learning method must make explicit use of the graph.
Treel111 dataset For illustration (and as an initial starting point), we sample from Tree 3, 0, (0, and call this sampled dataset Tree1111. That is, we take graph with high branch factor and synthesize fcatures simply by drawing them i...d from the specified Gaussian; the graph and these features logether comprise the dataset, which is suitable for link prediction. Note that the features contain no graph information, thereby forcing use of the graph for nontrivial performance, Moreover, the larger branch factor (10) relative to Discase (Chami et al. 2019) makes this dataset a far worse fit for Euclidean graph machine learning models. We summarize the performance for three key models on this dataset in Table 2 In particular, the Fuclidean multi-layer perceptron that trivially solves Disease in Table D only obtaïns 54.4+33 test ROC AUC for Treelll1 link prediction after thorough tuning. Moreover, adding graph information via the traditional Euclidean GCN also does not help, yielding result of 55.5 + 3.5 test ROC AUC. Finally, we note that the stale-of-the-art hyperbolic model HyboNet (Chen et al.] 2021 obtains 68.4 + 4.6 test ROC AUC, a considerable improvement over both Euclidean models. This Treel111 result is significant, in that it demonstrates a situation where graph information is not only relevant, but the straightforward Euclidean GCN treatment fails, and a hyperbolic treatment (of the graph) truly helps yield better results.
A Analysis of existing methods Morcover, we note that when the features are completely uninformative, a number of standard Euclidean graph models do not use graph information in a more complex way than simple GCN (when performing a per-layer analysis at initialization); the full details of this analysis are given in Appendix E. This highlights the overreliance of existing graph machine learning methods on the adjacency matrix alone, and indicates that more explicit usage of the graph information via embeddings can yield considerable benefit. in situations where the graph is important.
Tree1111, datasets To further illustrate this, as well as how when graph information lcaked into the features, graph machine learning can quickly becomes entirely unnecessary, we vary y from 0 to 1 in increments of 0.2, sampling a graph dataset from each parametric distribution. This produces six datasets, that call
9

---

Published in Transactions on Machine Learning Research (03/2025)
[Tree11l1,/ k0.2k [3]))}} We tune Euclidean MLP these datasets and give the results in Figure 2. As is clearly visible, as soon as 7 2 0.4, the MLP trivially solves the link prediction task with uras alone. To produce more challenging benchmark datasets, we also generate Treellllo.ag Treellllop freellllo.c as can be seen from Figure 2 these datasets are not as trivially solved by the MLP and thus are reasonable additional benchmarks for hyperbolic graph machine learning models.
Note that the feature synthesis process for 7 > can be viewed as sampling a positional embedding for the nodes of the graph, which see here, produces considerable benefit and is a potential solution (yielding complementary benefit) to the fact that many graph methods do not make use of graph information in a more nuanced manner.
6 Conclusion
In this work, we have demonstrated that state-of-the-art geometric graph learning results are misleading, in that, for most of the hyperbolic tasks in Chami et al. (2019), simple Euclidean model can outperform match state-of-the-art models while using the feal alone. We explain the problems that led to this state of affairs. Namely, that hyperbolic graph machine lcarning papers (i) suffer from buggy or weak Euclidean baselines, (ii) select test tasks that can be solved with the features alone, (iii) stray from the theoretical motivation behind hyperbolic embedding for trees, and (iv) use a graph measure (6- (6-hyperbolicity) to characterize an entire graph dataset, as opposed to characterizing the features jointly with the graph (moreover, the graph measure used is coarse).
Limitations We present initial solutions in Section aforementioned problems, but recognize that we fall short of a complete understanding of all aspects.
a substantial first step towards resolving the
Future work We resolve the first three of these four problems above. Additional work on the third problem would consist of finding real world benchmarks to match the synthetic benchmarks we introduced in this paper. The largest remaining amount of work is to be done on the fourth problem, that introducing a metric characterize graph datasets (that is, the graph and the associated node features). For this, one will have to characterize the interaction of the node features and the graph jointly, and may have to use more granular metrics than Gromov 8- d-hyperbolicity (e.g. Ollivier -icci curvature) to gain better geometric understanding of the underlying structure.
Impact statement. This paper, among other things, demonstrates the need for greater care when dealing with bascline evaluation in the context of hyperbolic machine learning. We do not have many concerns about negative societal impact, and hope our results will improve the quality of evaluation in the geometric graph machine learning literature, thereby improving the overall quality of work in the field. It should be noted that do make of synthetic dataset to demonstrate some of our core claims and note that we do not want to push the field entirely to the extreme of only synthetic benchmarks; ideally, we would use relevant practical real-world datasets for evaluation and finding such test tasks should be priority for the field.
References
Asuman Güven Aksoy and Sixian Jin. The apple doesn't fall far from the (metric) tree: Equivalence of definitions. orXiv: Metric Geometry, 2013. URL, hattss://api: http:/ppp...mmaiiccccooollarrrra org/ argg/CorpuIID>
14720409
Maya Bechler-Speicherr Ido Amos, Ran Gilad-Bachrach, and Amir Globerson. Graph neural networks use graphs when they shouldn't, 2024.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL httpp://www.wandbb.cm com/ Software available from wandb.com.
Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Neural Information Processing Systems, 2013. URL
14941970
M. Bronstein, Joan Bruna, Y. LeCun, Arthur D. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEFE Signal Processing Magazine, 34:18-49 428, 2017.
10

---

Published in Transactions on Machine Learning Research (03/2025)
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In Advances in neural information processing systems, pp. 4868-888 4879, 2019.
Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. In Annual Meeting of the Association for Compulational Linguistics, 2020.
Weize Chen, Xu Han, Yankai Lin, Hexu Zhao, Zhiyuan Liu, Peng Li, Maosong Sun, and Jie Zhou. Fully hyperbolic neural networks. ArXiu, 0os/2105.14686, 2021. URL https://api https://api.semanniiccc www.ssssscacccccar..ooommm CorpusID:2352547322
Christiane Fellbaum. Wordnet an electronic lexical database. Language, 76:706, 2000. URL https:
//api. htt.:/accci.aaa.ooorroooroosoaap ort//oorrssSD..55556331
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Advances in newral information processing systems, pp. 5345-5355, 2018.
M. Gromov. Hyperbolic Groups, pp. 263. Springer New York, New York, NY, 1987. ISBN 978-1-4611--958-77 doi: 1L1007977--10 1-1------19998-7--11 3_3. URL https://doii
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Tn NIPS, 2017.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson. Combining label propagation and simple models out-performs graph neural networks. ArXie, abs/2010.13390 2020.
Isay Katsman, Eric Chen, Sidhanth Holalkere, Anna Asch, Aaron Lou, Ser-Nam Lim, and Christopher De Sa. Riemannian residual neural networks. ArXiv, abs/2310.10013, 2023. URL https://api semanticscholar
Crg/CorpusID 264 145900
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, abs/1669.02907, 2017.
John M. Lee. Riemannian Manifolds: An Introduction to Curvature. 1997.
Yong Lin, Linyuan Lu, and Shing-Tung, Yau. Ricci curvature of graphs. Tohoku Mathematical Journal, 63: 605 627, 2011.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In Advances in Neural Information Processing Systems, pp. 8230 8241, 2019.
Aaron Lou, Isay Katsman, Qingxuan Jiang, Serge Belongie, Ser-Nam Lim, and Christopher De Sa. Differenti- ating through the fréchet mean. In International Conference on Machine Learning, 2020.
Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Tn Advances in neural information processing systems, pp. 6338 6347, 2017.
Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, pp. 355 366. Springer, 2011.
Ryohci Shimizu, Yusuke Mukuta, and Tatsuya Harada. Hyperbolic neural networks++, 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio', and Yoshua Bengio. Graph attention networks. ArXiu, abs/1710.10000, 2018.
Felix Wu, Tianyi Zhang, Amauri H. de Souza, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. ArXiu, abs/ Abs/1192.07153, 2019.
Yiding Zhang, Xiao Wang, Xunqiang Jiang, Chuan Shi, and Yanfang Ye. Hyperbolic graph attention network.
IEEE Transactions on Big Dota, 8:1690-1701, 2019. URL ://api. semanticscholar .rg. CorpuuIr 208857525
11

---

Published in Transactions on Machine Learning Research (03/2025)
Yiding Zhang, Xiao Wang, Chuan Shi, Nian Liu, and Guojie Song. Lorentzian graph convolutional networks.
Proceedings of the Web Conference 2021, 2021. URL hntpss//app semanticscholar.... ooomaa/ttcccooll....oo/oooopop
288241168
12

---

Published in Transactions on Machine Learning Research (03/2025)
Appendix
A Hyperbolic Embedding Example Computation
In this section we specify some fundamental Riemannian constructs the context of the hyperboloid model of hyperbolic space (Lee 1997), use them to compute an H² embedding of the tripodal graph in Figure I and show that the distances can be preserved with arbitrarily low distortion in hyperbolic space. We will deal with the hyperboloid model of hyperbolic space with curvature K < O; the relevant point set is H = {x Ra+1, (I, k where x) is the hyperbolic inner product:
(z,8) 1) =000 + 21y1 221/2
Inllr
for z, E Hg. Referencing Lou et al. (2000) we note that the hyperbolic distance in this model is given by:
(1,y) VíK
cosh -1 -K
and the Riemannian exponential map has closed form given by:
K (v) cosh( v K [[lllc) + sinh( / [K]] [[lllc) expx
K ||oll|c
where x Hi and v Tgl Recall we seek a low distortion embedding for the tripodal graph shown with distances d;),,;) and x(,,, = 2 for i i j. It will be convenient to give explicit coordinates vectors for the æ1, 22, 2s. l embeddings. Hence, for reference, begin by labeling xf x x p the Euclidean embeddings given in Figure ! for the sake of disambiguation:
in Figure D
22
2
We will now embed these points into H& using the Riemannian exponential map the origin of the hyperboloid, n which has coordinate form:
K 0
0
We must prepend 0 to the Euclidean vectors prior using them with the above exponential map formulation in order to properly treat them as tangent vectors (vectors lying in the tangent space of H3 with point of tangency )*). We abuse notation slightly and treat the original Euclidean vectors equivalently to those with this augmentation. Computing the embedding, we see:
exp (fe cosh( V [ 0)H²" 0 n1
cosbl VIKD VKK
0 O
cosh V 1 sinh / [
1uT0
# = exp K (Ift) xx "
sinht
/ V(AT)
v [
V
coshi K))
0
22
11 = exp (x = /x
= cosh(
sinh( ( K
sinll V [])
2/1K
sinh( [()
2/[R
13

---

Published in Transactions on Machine Learning Research (03/2025)
coshi (KK)
0
VIKI
5 exp f (xz) exp
cosh(v/K))
sinh( [
sinh (
|
3
2 2
V3
2
3 sinht y /KK)
2
Notice that because the Riemannian exp is a local isometry, have di (1ot wxth preserving the original Euclidean distances to the origin in the tangent space. Indeed, we confirm for 4 and x:::
coshi V(k ViKi sinb( / ViKi 0
| 0
cosh( v [
du x
cosh -1
K
=1
K
K
0
Thus we preserve the distances from to the children with no distortion. Now for the leaf node distortion analysis, we select of and ayd without loss of generality (by symmetry). Note:
cochi (KD
cosh vi VIK sinb(y/KK) vIKI
VIKI
(
siuh( v K
2V(K
3ainh (K)
2V(K]
1
K cosh? (alhh(vVK)) [
K sinhi (V[K)
cosh
V|K|
K
2|
1
cash
(asni((//)) (v [ + sinh (v(K()
v |
Now observe:
cossli + sinh"(v kT) =V3
lim
de (
lim K +
K
and
K (xf x² KK|
lim
lim cosh Dosh2((V/r []) + sinhh((/(K)) (V[K)
K
Thus we see when the curvature is O, we obtain the distorted Euclidean distance v3, as anticipated. Yet as the curvature bocomes more and more negative, d (af xxf' approaches which is the original graph distance between any two leaf nodes. Thus have manifested hyperbolic embedding and have demonstrated that. it is suitable to preserve the original graph distances in Figure with arbitrarily low distortion.
B Hyperbolic Geometry: Gromov 5-Hyperbolicity Intuition
In this scction, we follow up on the algebraic definition of Gromov 8-hyperbolicity given in Soction 3.4 and aim give more intuitive way of reasoning about this commonly used graph characterization metric. In service of attaining this end, we give less algebraic and more geometrically intuitive definition of Gromov
14

---

Published in Transactions on Machine Learning Research (03/2025)
2
B8 (1x, y))
B8 (1z, æ²))
6
y
6
2
Bs (sy, x1)
Figure 3: An illustration of the 8-slim triangle condition for the metric space (X.d). Recall Bx(S) == (pl ins d(s.p) < <.}.
8- h-hpeerbllycity in what follows Let (X, be geodesic metric space (a space in which any two points be connected via a geodesic, not necossarily unique). Let x, y. 2 E X. A geodesic triangle with verticos 2 is the union of the three geodesic segments [a, u], =I, [z, x]] (where [p; g] denotes a geodesic segment with endpoints and q). If for any point m E y] there is a point in [y, 2] U [z, x at distance less than 8 of m, and similarly for points on the other edges, and 8 2 0, then the triangle said to be 8-slim. Please see Figure for an illustration of this condition. We can then define a 8-hyperbolic space as geodesic metric space in which all geodesic triangles are 8-slim. Notably, if 8 0, we the triangles collapse to tripods, implying the space is isomorphic to tree.
c Graph Characterization via Ollivier-Ricci Curvature
Though Gromov d-hyperbolicity is commonly used to characterize the geomelry of graphs, we note that it assigns a single integer to an entire graph, and fails to distinguish finer graph geometry that may be relevant in a machine learning context. In particular, two trees with very different structure (e.g. very different branch factor) will both be assigned Gromov 5-hyperbolicity value 0. Thus, one may desire finer way to characterize graph geometry in this context. One such way to obtain more fine characterization is via Ollivier-Rieci curvature (Lin et al. 2011. Riccii curvature is discretization of Ricci curvature, and can be used to locally characterize graph edges. The definition is given below.
Definition (Ollivier-Ricci Curvature). Let (X, d) be a separable, completely metrizable, metric space. Let (mz)rex be a family of probability measures on X such that (i) the measure m, depends measurably on X and (ii) for every x E X, the first moment f d(a,, y) dm is finite. Let a, y E X, x + y. The Ollivier-Riae Ricci curvature s(x, y) of (X, d, (m²)) along (zy) defined by:
<(x,y) y) = Ti (m, my) d(x, y)
where Ti (m, my) is the I transportation distance from m. to my.
In the context of graphs, we measure the Ollivier Ricci curvature of an edge (z, y) by taking m, and my to be discrete uniform distributions over the neighbor sets Ng, respectively. The metric d is induced by the graph (i.c. shortest path). Computing the curvature boils down to computing the L transport distance between these distributions, which boils down to solving a linear program (and can be automated with simple linear program solver). Computing the Allivie-RRicd curvature for all edges can give a nuanced view of graph geometry that is not offered by Gromov d-hyperbolicity. In particular, note that while the graphs from Discase (Chami et al.) 2019) and Tree1111 (a dataset we introduce) are both trees, ie. Gromov 8-hyperbolicity is 0 for both, the Ollivier-Rieci curvature profiles given in Figure 4 differ considerably. As such, Ollivier-Rieci curvature provides a more granular approach to graph characterization that would benefit
3This definition of 6-hyperholicity is equivalent to the prior definition up to constant factor Aksoy Jin 2013
15

---

Published in Transactions on Machine Learning Research (03/2025)
Figure 4: Ollivier-Ricii curvature (Lin et al.) 2011 for two graphs. The left graph is the Discase Chami
et al. 2019 dataset and the right graph is tree with branch factor of 10 from the synthetic graph dataset. Treel 111 we introduce.
the hyperbolic graph machine learning community in particular (this community currently largely relics on Gromov 6-hyperbolicity).
Tuning Euclidean Baselines
In cases where Euclidean baselines are not well presented, most the time Euclidean baselines are not severely buggy, but rather, are not tuned to maximally present the extent their performance. In this section, we invostigate basclines in the application geometric machine lcarning the knowledge graph lasks in Chami al. (2020). In particular, we note that further Luning the Euclidean models for of the datasets that "exhibits hierarchical structures" (Chami et all 2020) considerably bridges the gap between the bascline Euclidean models and the introduced hyperbolic models. Results are given in Table 3 (best of 5 trials is given; only the best result is reported, following conventions set by prior work for these tasks).
Dataset
WNISRR [Bordes
2013
Space
Model
MRR
H@1
H@3
H@10
RefE
0.455
0.419
0.470
0.521
Rd
RotE
0.463
0.426
0.477
0.529
RefE (tuned)
0.457
0.425
0.469
0.512
Rd
RotE (tuned)
0.466
0.429
0.481
0.534
RefH
0.447
0.408
0.464
0.518
H
RotH
0.472
0.428
0.490
0.553
Table 3: Above we give link prodiction results for WN18RR [Bordes et al. 2013 a dataset that "cxhibits hierarchical structures" (Chami et al. 2020). We deal with low-dimensional. embeddings (d = 32) in the filtered setting, as was the case in the original paper (Chami al. 2020). The properly tuned Euclidean models considerably close the gap between the baseline Euclidean results and the hyperbolic results. While tuning, focus MRR, but most other metrics also exhibit concomitant increase.
E Analysis of Graph Methods when Features are Uninformative
In this section, under some assumptions, we analyze a varioty of graph machine learning methods in a context. where the features are uninformative of the graph structure. We do this better understand how the graph is being used when the features offer distinction between nodes for the task at hand.
16

---

Published in Transactions on Machine Learning Research (03/2025)
Per-layer Analysis
We analyze variely of common graph machine learning baselines graph dataset. where the features are ii.d. this is a very strong setting, in that when this is the case, graph methods must use the graph to obtain nontrivial performance. Note that our introduced synthetic Tree1111 (y = 0) datasct falls under this sctting. Recall that graph dataset is given by the graph structure G (V, E), whence the adjacency matrix is derived, together with the associated feature vectors X E IR. Vix"; that is, feature vector in I given for each of the vertices. We will make the simplifying assumption that the input features are drawn i.i.d. from Ia).
Multi-layer Perceptron (MLP) Recall that a layer of the MLP is simply:
x(") = o(x(a=)))
where W the learned weights, (n-1) is the matrix of imput features, and is a non-linearity. This is one of the simplest models used in this context and is baseline that uses graph information (only the features).
Graph Convolutional Network (GCN) A layer of the GCN (Kipf & Welling 2017 is given by: x(") (AX("=))))
where W and ((--1) are given above, and is the normalized adjacency matrix of the underlying graph. We have:
À A-1
A T[v
where D is the degree matrix of A. The GCN is the simplest modern graph machine learning method that uses graph information by way of normalized adjacency malrix multiplication.
Graph Attention Network (GAT) A layer of GAT (Velickovic et al. 2018 is given by:
x
Ois W N. ( JEN.
Σ
where M₁ represents the graph neighbors node and:
W (1-)) a
LeakyReLU
exp
W [ x(())11
Oij
W W (n-1) 1) W (x(1=1) (n1)
ΣLEN. exp
LeakyReLLU aT
W (n-))
are the attention weights. Note that if all node features X; are i.id. Gaussian, the vectors
W W Wx("-1) are
all equal in distribution for any i.j. By properties of softmax, this implies oi concentrates on [T and hence
(n) concentrates on a (EjeN, (AG] Wx(n--)), and since W is constant, the features over which learning happens approximately follow (N00, J. Ia). Ia).
That is to say, the attention scores are spread evenly across all neighbors, and use of the graph structure reduces simply to scaling down covariance by degree.
Simple Graph Convolution Network (SGC) K-layer SGC (Wu et al. 2019 is given by:
(²) softmax AK xW)
17

---

Published in Transactions on Machine Learning Research (03/2025)
where À is the normalized adjacency matrix. On per-layer basis (K = 1) it reduces to:
X softmax (AXW)
that is, the graph is used no more complicated of a way than how is used for the GCN,
Graph Sample and Aggregation (SAGE) A layer of SAGE (Hamilton et al. 2017 is given by:
x
X(1) = a W
x!n)
NWO
where:
x NO = Agg (1X Vj ((()
The aggregation function Agg is selected to be either mcan or max pool operator. For the sake of simplicity, let us assune the aggregation operator is the mean. Note if the aggregation is the mean function, we have:
x( N(O
NO,
W. 1a)
That is to say, x!") learned from the previous feature vector and feature drawn from distribution with covariance scaled down by the degree. In other words, mercly the degree is used from the graph and the model uses graph structure in more sophisticated manner than the GCN.
A summary of this analysis is provided in Table highlighting how each method does (or does not) use the graph. As we can clearly see, when dealing with a dataset where the features are not informative, most graph learning methods do not actually use the graph information in a more sophisticated way than the GCN. This may perhaps be surprising and showcases the overreliance on features of most graph methods. Tf graph information is truly necessary to solve the task hand, this analysis indicates that coming up with positional embeddings may prove be highly beneficial (and this is confirmed in Figure 2 of the main paper).
Table 4: Summary Analysis of Various Graph Machine Learning Methods on a Dataset with Independent, Identically Distributed Gaussian Features
Method
Layer Structure
Graph Dependence Reduction (first layer at initialization)
MLP
X (WW
None
GCN
X oxi
-x
W x (1-
LoakyBaae
wxf--11
x =o (Era a wxfe-))) where ou
N/ pd.
[
Liey cop
LookyRat
WX
SGC
wottmar 1 xix-11
Ax
17 X
SAGE
x =a w
where x(1)) Ags ((x)))-)) e NO)
(o 4d), if Ang!") is mean
F HGCN (Chami et al., 2019) Euclidean Multi-layer Perceptron Bug
A fairly prominent, and motivating, discovery in our paper is that in Chami et al. (2019), there was a bug present for Euclidean baselines, most, prominently for the Euclidean MLP. This bug is manifested by a single line of code in the publicly released implementation; this line constrained Euclidean model representations to lie within the unit ball, perhaps a vestigial feature from the Poincaré ball implementation. For reference, the line, together with the relevant conditional statement, is given below (lines 104-105 of 'models/ base models.py" of the original repository, accessible at https:://github.com/ Hazy Research/hearr
18

---

Published in Transactions on Machine Learning Research (03/2025)
if self mwa.ionnnndo... name == 'Buclidean's h self manifold normalize (h)
If you simply comment these lines, as we did above for Table ! and slightly modify the Fermi- Dirac decoder in 'layers/ llarrrssyyyesspp by replacing line 86:
exprcheexpc probs = 1. / (torch. exp ((diit - self r) / self.t)) 1.0)
with:
probs 1. / etorch.exp[ (((dist - self.r) .x) / self. t) cwwmppmmaaaammmmpc (_pp_maxx(00)) + 1.0)
for better numerical stability, the very Euclidean MLP presented in the original GitHub repository attains 98.7% test ROC AUC for link prediction on Disease (up from 72.6% for the original version) and 80.3% test. F1 score for node classification on Disease (up from 28.8% for the original version). The Euclidean MLP also attains 99.1% test ROC AUC for link prediction on Disease-M (up from 55.3%). Note that Discase and Discase-M (Chami al.) 2019) are the most hyperbolic datasets presented, as measured by Gromov d-hyperbolicity (the o-hyperbolicity is 0, meaning the graphs from both datasets are trees). This is a considerable issue, since the HGCN GitHub repository has been used in number of hyperbolic machine learning papers (Chen et al. models.
2021
Lou et al. 2020 Katsman et al. 2023 that introduce their own hyperbolic
G Experimental Details
Our runs for Table 1 specifically the "MLP (debugged)" row, were performed on single NVIDIA GeForce RTX 3090 GPU. All reported results in Table D give mean and standard deviation over trials; trials differ only in terms of the seed used. The same procedure is followed for the three rows of Table 2 and each data point of Figure 2 Data for other rows in Table ! was taken from existing results reported in Chami et al. 2021).
(2019) and Chen
A complete repository with code (and bug-free version of the Fuclidean multi-layer perceptron model from Chami et al. (2019)) ) is available at the following Github link) There, README gives explicit line-by-ln line-by-line commands to reproduce our results. The hyperparameters for our best runs were found with
tuning via the Weights and Biases Biewald 2020) framework and we include the YAML configuration file we
used for tuning the repository as well.
6 find the original Hub repository for Chami 2019) Inttpe:/ htipe://github.com Reseaaar
Research hggen
19


Reviews:
[{"review_id": "3ZSlQqn9Pq", "reviewer": "Reviewer_ybg8", "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 points out a very interesting phenomenon in the literature and explains it at a conceptual level, in addition to showing it with experiments.\n\n2.) The paper provides a dataset whose construction is well-motivated by the conceptual explanation of the flaws of previous work.\n\n3.) The paper lists its main limitations -- one of which is that it does not solve the problem of finding real datasets for which hyperbolic graph learning methods outperform properly implemented Euclidean methods.\n\nWeaknesses:\n\n1.) The paper suggests the use of Ollivier-Ricci curvature profiles in place of $\\delta$-hyperbolicity to characterize graph geometry.  I see that this profile can differ between two graphs that are both trees and thus have equal (zero) $\\delta$-hyperbolicity.  However, I am not certain of the details regarding the concrete use of the Ollivier-Ricci curvature profile to determine the suitability of a given dataset for analysis via hyperbolic embeddings.  Furthermore, I do not see that this solves the problem of measuring hyperbolicity when node features are involved.", "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 empirically studies results from prior literature on hyperbolic graph representation learning -- that is, embedding of nodes of featurized graphs in hyperbolic spaces.  The paper shows that Euclidean multilayer perceptron implementations as baselines for various recent works are buggy and that, when the bugs are fixed, performance on these baselines improves dramatically, even beyond the performance of state of the art hyperbolic models.  \n\nIt posits a multi-point explanation for how this state of affairs came about:\n\n1.) Datasets selected for evaluation of hyperbolic GCNs are poorly chosen, in the sense that even methods that ignore graph structure completely perform well on the selected tasks.  This holds even for datasets that perfect $\\delta$-hyperbolicity.\n\n2.) The motivation for hyperbolic embedding in the first place is poor -- even if graphs can be embedded in a hyperbolic space with low metric distortion, this is not a justification for assuming that node feature vectors should be as well.\n\n3.) Gromov $\\delta$-hyperbolicity is a measure of hyperbolicity that considers only graph structure and not node features.  Thus, this is only a partial measure of appropriateness of hyperbolic embeddings for a given dataset.\n\nThe paper then proposes a more rigorous way of benchmarking datasets for analysis of hyperbolic graph learning methods.  It includes the construction of a parametrized family of synthetic datasets, where the parameters control the dependence of node features on graph (in fact, tree) structure.  They show empirically that on this dataset, when parameters are chosen so that graph information is relevant, state-of-the-art hyperbolic GCNs outperform Euclidean GCNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.) Can the authors provide more intuition regarding the Ollivier-Ricci curvature and how it ought to be interpreted?\n\n2.) Can the authors clarify whether or not the Ollivier-Ricci curvature accounts for node features?\n\nNeither of these are crucial for securing my recommendation for acceptance, but I think that they would improve the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mVaYvtvrkd", "reviewer": "Reviewer_krJo", "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\nThe work is very relevant for the graph and geometric representation learning communities. Some of the work's strengths are:\n\n* **Identifying Systematic Issues**: The paper properly identifies widespread problematic hyperbolic graph learning practices and systemic issues and proposes first steps to mitigate the situation.\n* **Novel Benchmark**: The paper proposes a novel, controlled, synthetic benchmark to evaluate hierarchical graph learning models.\n* **Impactful and Practical Recommendations**: The work emphasizes the importance of reproducibility, proper task design, and theoretical grounding, which are essential for advancing geometric machine learning.\n\n## Weaknesses\n\nThe work makes a valuable contribution by identifying systematic issues in hyperbolic graph representation learning and providing important and actionable insights. However, to emphasize the broader applicability of its findings, a few gaps in analysis and presentation need to be addressed. These will be straightforward to address and would significantly enhance the impact of the work.\n* **(W1) Limited Real-World Evaluation**: Table 1 considers only three of the six datasets from Chami et al. (2019). Expanding the evaluation to at least all six would provide a more comprehensive evaluation\n* **(W2) Unclear Explanation of the Identified Bug**: The discussion of the bug in Euclidean baselines lacks detail. The authors do not fully explain the possible original intent of the buggy line (i.e., why it was possibly present) or how its removal changes the behavior of the model. It is not clear what researchers need to be careful about when implementing Euclidean baselines or how such bugs could be systematically identified and avoided in future work.\n* **(W3) Synthetic Dataset Simplifications**:\n  * **(W3a)** The Tree dataset assumes linear dependencies between adjacent node features, which may not adequately reflect the characteristics of real-world data.\n  * **(W3b)** The dataset focuses exclusively on tree dependencies, and does not provide any insights for non-tree graph topologies (e.g., grids or random graphs).\n  * **(W3c)** The dataset focuses exclusively on the link prediction task.\n  * **(W3d)** The authors do not compare/contrast the design and rationale of their Tree model against the SIR disease propagation model from Chami et al. (2019)\n* **(W4) Ollivier-Ricci Curvature**: While the authors discuss its potential as a finer metric for characterizing graph data that would benefit from hyperbolic representation learning, they do not integrate it into their experiments or benchmarks, leaving its practical utility unexplored.", "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 identifies systematic issues in hyperbolic graph learning, including poorly tuned Euclidean baselines, flawed task designs, and misuse of Gromov $\\delta$-hyperbolicity. The authors demonstrate that well-tuned Euclidean models often outperform or compete with hyperbolic ones on benchmarks previously used to demonstrate the superiority of hyperbolic models. They also propose synthetic benchmarks to evaluate hierarchical structures, and suggest Ollivier-Ricci curvature as a better alternative to $\\delta$-hyperbolicity. The work challenges key assumptions and offers actionable insights for improving evaluation practices in the field.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* **(R1) Expand Real-World Benchmark Analysis**: Include results for all six datasets from Chami et al. (2019) or explain why certain datasets were excluded.\n* **(R2) Clarify the Bug**: Provide more details about the buggy code in the Euclidean baselines, including its possible original purpose (i.e., why was it possibly introduced) and the specific changes that occur when it is removed.\n* **(R3) Synthetic Dataset Design**:\n  * **(R3a)** Consider introducing nonlinear dependencies between the features (e.g., transform the parent features with sigmoid or ReLU, perhaps before/after applying a non-diagonal linear transformation) to better simulate characteristics of real-world data.\n  * **(R3b)** Consider exploring additional graph topologies beyond trees, such as grids or random graphs, to further explore the impact of graph topology/geometry across Euclidean and hyperbolic graph representation learning models.\n   * **(R3c)** Expand the dataset to appropriate tasks beyond link prediction, such as node classification or graph regression.\n  * **(R3d)** Compare/contrast the underlying model against the SIR model for disease propagation from Chami et al. (2019).\n* **(R4) Ollivier-Ricci Curvature**: Better contextualize ORC in the work.\n* **(R5) Experimental Details**: Expand Section G in the Appendix with more details on the datasets, baselines, hyperparameters, etc.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DYz9bZiIQt", "reviewer": "Reviewer_iz4Q", "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- The authors very convincingly demonstrate their first point, i.e., that Euclidean baselines were not fairly represented previously.\n- The authors do a good job of arguing the shortcomings of previous work.\n- The authors focus on fair evaluations given this particular state of affairs.\n- The authors also attempt to explain how these issues might have arisen.\n\nWeaknesses:\n- Large parts of this work are antithetical to currently held beliefs on model evaluation, which is not an issue per se. The authors try to defuse their, for lack of a better word, aggressive language towards some of the related works. However, some parts of this work could still be considered personal attacks. In particular, there is a large focus on Chami et al. (2019) (and then Chami et al. (2020)). I would suggest that the authors, wherever possible, always include all related works that made these mistakes to, at the very least, diffuse the blame among all of these. Namely, Chen et al. (2021), Zhang et al. (2019), and Zhang et al. (2021), and others.\n- (in relation to the previous weakness) I would also suggest. However, I will not make my score dependent on this that the authors add a paragraph to their introduction, putting Chami et al. (2019) and the other works into context, in the sense that the authors are not attempting to attack these other authors but are only criticizing some aspects of their work. If possible, this could also include a recognition of work well done in these related works, highlighting that there are only some issues in evaluation and model design, as mentioned.\n- In section 4.2, \"Poor geometric characterization of graph datasets,\" the authors claim that Gromov \\delta-hyperbolicity is a poor characterization, especially due to its coarseness in treating trees. While I acknowledge that this might be the case, one mentioned issue, i.e., that node features are not taken into account, is a fundamental issue in many areas of graph learning and, to the best of my knowledge, has no current solution. By this, I mean that this cannot be used as an argument that Gromov \\delta-hyperbolicity is a poor measure. By this standard, almost every measure is a poor measure. I suggest that the authors tone down their language in this paragraph and put into context that this is an important area of study for which we currently do not have a solution.\n- (in relation to the previous weakness) Along the same lines, the authors claim that Ollivier-Ricci curvature is a better measure since it is more fine-grained. The authors do not demonstrate that coarseness/fine-grainedness is particularly relevant or beneficial; however, they do not demonstrate that Ollivier-Ricci curvature is a better measure. I suggest that the authors either add further arguments, carefully reconsider the strength and tone of their statements, or remove this paragraph (which would necessitate other changes).\n- In section 5, \"Euclidean MLP baseline,\" The authors claim that after a Euclidean MLP fails to perform well, a GNN should act as an additional baseline. This in and of itself makes sense, of course. However, the authors should more clearly articulate that no author can guarantee that this GNN baseline benchmark will be a fair comparison since it has been demonstrated repeatedly that different GNNs perform vastly differently depending on the benchmarking dataset in question. Perhaps the most striking recent publication to this effect would be Bechler-Speicher et al. (2024).\n- In section 5, \"Defining Tree(...)\" and \"Tree1111 dataset,\" the authors claim that their notably strongly synthetic dataset is a better benchmark for hyperbolic graph learning than Disease and Disease-M, which are also synthetic but strongly motivated, representing real processes. This is a poor argument as the authors compare their purely academically relevant synthetic dataset to datasets that might have practical relevance. I suggest that the authors either provide a better-suited practical dataset (even some dataset that is already in use) or make it clear that they do not have a better-suited practical dataset and that they thus propose a synthetic replacement that is at least better suited in the sense that graph structure becomes relevant. To be more specific, I propose that the authors tone down their language and make it clear to any prospective reader that their proposal is also not perfect when it is being proposed.\n- The authors do not provide an experimental setup or details on their experimental setup regarding their tuning on the Euclidean MLP models. I am assuming that this tuning includes the tuning of model hyperparameters, in which case the authors should clearly state how these hyperparameters are being tuned.\n- The authors criticize previous work for not achieving statistically significant results but don't clarify whether their tables (notably Table 1) include significance tests. While I believe it is quite apparent that all presented results are statistically significant, these tests should be explicitly conducted and included in this work. Specifically, the author should test whether each second-best method (the best being the bold entry) performs statistically significantly worse than the best method and mark each second (third and so on) method that does not perform significantly worse by underlining it or making this clear in some other way. This also necessitates an additional explanation in the table's caption.\n- There is a small mistake in Appendix A \"d(\\mu, x_i) = 1 and d(x_i, x_i)=2 for ...\". It should be \"d(x_i, x_j)=2\".\n\nMaya Bechler-Speicher et al., \"Graph Neural Networks Use Graphs When They Shouldn't\", ICML (2024)", "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 demonstrate a clear issue in, at the very least, some related work on hyperbolic graph learning. Specifically, they argue and show that (1) euclidean baselines were not fairly represented, resulting in misleading conclusions (2) some architectural design choices in hyperbolic graph learning models are not supported by the underlying theory (3) a standard measure of hybolic relevance, the Gromov \\delta-hyperbolicity, is not a good measure for suitedness of a dataset for evaluation of hyperbolic graph learning models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Each weakness above is essentially also a requested change:\n- weaken the aggressive language in particular directed towards Chami et al. (2019) (critical)\n- Include a paragraph in the introduction explaining criticism of Chami et al. (2019) and other works. (non-critical)\n- Weaken their strong language regarding Gromov \\delta-hyperbolocity. (critical)\n- Put Ollivier-Ricci curvature and its comparison to Gromov \\delta-hyperbolicity into proper context. (critical)\n- Clarify the proposal of GNN baselines as a solution to the mentioned problems (critical)\n- Clarify the proposal of synthetic tree datasets like Tree111 as a solution to the mentioned problems (critical)\n- Add an experimental setup for hyperparameter tuning of Euclidean baselines. (critical)\n- Add statistical significance evaluations (non-critical)\n- Fix minor typo in appendix (non-critical)", "broader_impact_concerns": "Since the authors propose synthetic tree datasets to replace more practically relevant datasets currently in use, the authors could clarify that this proposal could lead to a different form of spurious evaluation of only synthetic benchmarks, and practically relevant datasets are sorely needed. While the authors include this to some extent in their \"Future Work\" paragraph, assuming this shortcoming is not resolved, they should include this more explicitly in their \"Impact statement\" paragraph.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three reviewers. The reviewers agreed that the paper's main finding, i.e., that simple Euclidean models outperform or are competitive with hyperbolic models in hyperbolic graph tasks, is surprising and very interesting. They also appreciated the synthetic dataset introduced in the paper on which Euclidean MLP models fail. However, the reviewers also raised concerns mainly about the design of the synthetic dataset, the limited number of real-world datasets, and the strong criticism towards some prior works. The reviewers also asked for more details on the Ollivier-Ricci curvature. The authors comprehensively responded to the reviewers' comments and revised the manuscript accordingly, and all reviewers recommended acceptance of the paper. I believe that the submission now meets the TMLR acceptance criteria, and thus, I am recommending acceptance. I request that the final version of the manuscript implements any remaining items promised in the author feedback.
Decision: Accept (poster)