Random Laplacian Features for Learning with Hyperbolic Space
Authors: Tao Yu
Christopher De Sa
Venue: ICLR 2023 poster (2023)
Keywords: hyperbolic space
random features
kernel approximation

Abstract: Due to its geometric properties, hyperbolic space can support high-fidelity embeddings of tree- and graph-structured data, upon which various hyperbolic networks have been developed. Existing hyperbolic networks encode geometric priors not only for the input, but also at every layer of the network. This approach involves repeatedly mapping to and from hyperbolic space, which makes these networks complicated to implement, computationally expensive to scale, and numerically unstable to train. In this paper, we propose a simpler approach: learn a hyperbolic embedding of the input, then map once from it to Euclidean space using a mapping that encodes geometric priors by respecting the isometries of hyperbolic space, and finish with a standard Euclidean network. The key insight is to use a random feature mapping via the eigenfunctions of the Laplace operator, which we show can approximate any isometry-invariant kernel on hyperbolic space. Our method can be used together with any graph neural networks: using even a linear graph model yields significant improvements in both efficiency and performance over other hyperbolic baselines in both transductive and inductive tasks. 

Under review as a conference paper at ICLR 2023
RANDOM LAPLACIAN FEATURES FOR LEARNING WITH HYPERBOLIC SPACE
Anonymous authors Paper under double-blind review
ABSTRACT
Due to its geometric properties, hyperbolic space can support high-fidelity embed- dings of tree- and graph-structune data, upon which various hyperbolic networks have been developed. Existing hyperbolic networks encode geometric priors not only for the input, but also at every layer of the network. This approach involves repeatedly mapping to and from hyperbolic space, which makes these networks complicated to implement, computationally expensive to scale, and numerically unstable to train. In this paper, propose simpler approach: learn hyper- bolic embedding of the input, then map once from it to Euclidean space using a mapping that encodes geometric priors by respecting the isometries of hyperbolic space, and finish with a standard Euclidean network. The key insight is to use random feature mapping via the eigenfunctions of the Laplace operator, which we show can approximate any isometry-invarian kernel on hyperbolic space. Our method can be used together with any graph neural networks: using even a linear graph model yields significant improvements in both efficiency and performance over other hyperbolic baselines in both transductive and inductive tasks.
INTRODUCTION
Real-world data contains various structures that resemble non-Euclidean spaces: for example, data with tree- or graph- Strph-struutue such as citation networks (Sen et al.) 2008). social networks (Hoff al.) 2002). biological networks (Rossi & Ahmed 2015). and natural language (e.g., taxonomies and lexical entailment) where latent hierarchies exist (Nickel & Kiela 2017). Graph-style data fea- tures in range of coablems-includingg node classification, link prediction, relation extraction, and text classification. It has been shown both theoretically and empirically (Bowditch) (0066] Nickel &
Kiela 2017: 2018; Chien et al., 2022) that hyperbolic space- the geometry with constant negative curvature naturally suited for representing (i.e. embedding) such data and capturing implicit hierarchies, outperforming Euclidean baselines. For example, [Sala et al. (2018) shows that hyper- bolic space embed trees without loss of information (arbitrarily low distortion), which cannot be achieved by Euclidean space of any dimension (Chen et 2013 Ravasz & Barabási 2003).
Presently, most well-known and -established deep neural networks built in Euclidean space. The standard approach is to pass the input to a Euclidean network and hope the model can learn the fea- tures and embeddings. But this flat-space approach can encode the wrong prior in tasks for which we know the underlying data has a different geometric structure, such as the hyperbolic-space structure implicit tree-like graphs. Motivated by this, there an active line of research on developing ML models in hyperbolic space HH, Starting from hyperbolic neural networks (HNN) by Ganea et al. (2018) a variety of hyperbolic networks were proposed for different applicationss including HNN+ Shimizu et al.] 2020). hyperbolic variational auto-encoders (HVAE, Mathieu et al. (2019), )) hyper- CLAAT,,Gulleere bolic attention networks (HATN, Guulcehre et al. (2088). ) hyperbolic graph convolutional networks
(HGCN, Chami et al. (2019)), hyperbolic graph neural networks (HGNN, Liu et al. (2019)) and hyperbolic graph attention networks (HGAT Zhang et al. (2021a)). The strong empirical results of HGCN and HGNN in particular on node classification, link prediction, and property prediction show the power of hyperbolic geometry for graph learning.
These hyperbolic networks adopt hyperbolic geometry at every layer of the model. Since hyperbolic space is not a vector space, operations such as addition and multiplication are not well-defined; nei- ther are matrix-vector multiplication and convolution, which are key components of deep model

---

Under review as a conference paper at ICLR 2023
that uses hyperbolic geometry at every layer. A common solution is treat hyperbolic space gyro-vector space by equipping it with a non-commutative, non aonaassci addition and multiplica- tion, allowing hyperbolic points to be processed as features in a neural network forward. However, this complicates the use of hyperbolic geometry in neural networks because the imposition of an extra structure on hyperholic space beyond its manifold properties- non-geometric. A second problem with using hyperbolic points as intermediate features is that these points can stray far from the origin (just as Euclidean DNNs require high dynamic range Kalamkar et al. (2019)), especially for deeper networks. This can cause significant numerical issues when the space is represented with ordinary floating-poits and grows exponentially with the distance from the origin. Much careful hyperparameter tuning is
the approach somehow
numbers: the representation error is unbounded
required to avoid this "NaN problem" [Sala et al. (2018); : Yu De Sa (2019 (02T). These issues call for simpler and more principled way of using hyperbolic geometry in DNNs.
In this paper, we propose such a simple approach for learning with hyperbolic space. The insight is to (I) encode the hyperbolic geometric priors only at the input via an embedding into hyperbolic space, which is then (2) mapped once into Euclidean space by a random feature mapping & IHI,, + I that (3) respects the geometry of hyperbolic space in that its induced kernel k(2,, y) [o(())), <(v)) is isometry-invarian
i.e. k(x, y) depends only on the hyperbolic distance between æ and y. fol- lowed by (4) passing these Euclidean features through some downstream Euclidean network. This approach both avoids the numerical issues common in previous approaches (since hyperbolic space only used once early in the network, numerical errors will not compound) and eschews the need for augmenting hyperbolic space with any additional non- con-geometric structure (since we base the mapping only on geometric distances in hyperbolic space). Our contributions are as follows:
In Section we propose a random feature extraction called HyLa which can be sampled to be an unbiased estimator of any isometry-invarian kernel on hyperbolic space. This generalizes the classic method of random Fourier features proposed for Euclidean space by |Rahmii et al. (2007). In Section 5 we show how to adopt HyLa La in an end-to-end graph learning architecture that si- multancously learns the embedding of the initial objects and the Euclidean graph learning model.
In Section 6 we evaluate our approach empirically. Our HyLa- demonstrate better per- formance, scalability and computation speed than existing hyperbolic networks: networks consistently outperform HGCN, even on tree dataset, with 12.3% improvement while being x,4x faster. Meanwhile, we argue that our method is an important hyperbolic baseline to com- pare against due to its simple implementation and compatibility with any graph learning model.
2 RELATED WORK
Hyperbolic space. n-dimensional hyperbolic space H. is usually defined and used via model, a representation of H. within Euclidean space. Common choices include the Poincaré ball (Nickel) & Kiela| 2017) and Lorentz hyperboloid model (Nickel & Kiela, 2018). We develop our approach using the Poincaré ball model, but our methodology is independent of the model and can be applied to other models. The Poincaré ball model is the Riemannian manifold (B",,p)) with 8" = {x e
R" ||>||| < 1) being the open unit ball and the Riemannian metric Ip and metric distance dp being
(x) = 4(1 - ||==||)-~2 -2g. and dz(x, y) = arcosh (1+ 2 1-11-
y1l
where ge is the Euclidean metric. To encode geometric priors into neural networks, many versions of hyperbolic neural networks have been proposed. But while (matrix-) addition and multiplication are essential to develop a DNN, hyperbolic space is not a vector space with well-defined addition and multiplication. To handle this issue, several approaches were proposed in the literature.
Gyrovector space. Many hyperbolic networks, including HNN (Ganea et al., 2018). HNN++ (Shimizu al. 2020). HVAE (Mathieu et al.) (201)), HGAT (Zhang et al.) (202 la), and GIL Zhu (et al. (2020). adopt the framework of gyrovector space as an algebraic formalism for hyperbolic geometry, by equipping hyperbolic space with non-associative addition and multiplication: Möbius addition @ and Möbius scalar multiplication @, which is defined for æ, E B" and a scalar r e R
+ = (1+2(z.9)-11)) (1/ 1+2( |>|>>>|>
r X x == tanh(r tanh ([1x |
However, Möbius addition and multiplication are complicated with a high computation cost; high level operations such Möbius matrix-vector multiplication are even more complicated and numer-
2

---

Under review as a conference paper at ICLR 2023
ically unstable (Yu & De Sa 2021 Yu et al. 2022). due to the use of ill-conditioned functions like tanh- Also problematic is the way hyperbolic space is treated as gyrovector space rather than a manifold, meaning this approach can not be generalized to other manifolds that lack this structure. Push-forward & Pull-backward. Since many operations are well-defined in Euclidean space but not in hyperbolic space, a natural idea is to map Hi, to R via some mappings. apply well-defined operations in Rd, then map the results back to hyperbolic space, Many works, including HATN (Gulcehre et al.) 2018), HGCN (Chami et al. 2019), HGNN (Liu et al. 2019), HGAT (Zhang et al.)
2021a), Lorentzian GCN (Zhagg et al. 2021b). and GIL Zhu et al. (2020). adopt this method:
pull the hyperbolic points to Euclidean space with "pull-backward" mapping:
apply operations such as multiplication and convolution in Euclidean space; and then
push the resulting Euclidean points to hyperbolic space with a "push-forward" mapping.
Since hyperbolic space and Euclidean space are different spaces, no isomorphic maps exist between them. A common choice of the mappings (Chami et al. [019 Liu et al. 2019) is the exponential map expx (.) and logarithm map log (-), where usually chosen be the origin O. The exponential and logarithm maps are mappings between the hyperbolic space and its tangent space T H.,, which an Euclidean space contains gradients. The exponential map maps a vector v E HH æ to another point exp,, (v) in HI, (intuitively, exP,, (v) is the point reached by starting at æ and moving in the direction of v a distance ||æ||| along the manifold), while the logarithm map inverts this.
This approach is more straightforward and natural in the sense that hyperbolic space is only treated as a manifold object with no more structures added, so can be generalized to general manifolds (although it does privilege the origin). However, (-) and (-) are still complicated and numerically unstable. Both push-forward and pull-backward mappings are used at every hyperbolic layer, which incurs high computational cost in both the model forward and backward loop. As result, this prevents hyperbolic networks from scaling to large graphs. Moreover, the Push-forward & Pull-backward mappings act more like nonlinearities instead of producing meaningful features.
Kernel Methods and Horocycle Features. Cho et al. (2019) proposed hyperbolic kernel SVM for nonlinear classification without resorting to ill-fitting tools developed for Euclidean space. Their hyper- bolic feature space, rather than an Euclidean feature space. They also constructed feature mappings only for the Minkowski inner product kernel: it's unknown how to construct feature mappings of their type for general kernels. Another work by Fang et al. (2021) develops several valid positive definite kernels in hyperbolic spaces and investigates their usages; they do not provide any sampling- based features to approximate these kernels. [aang] (2020) constructed hyperbolic neuron models
approach differs from ours in that they map hyperbolic points to another (higher-dimensionn)
using a forh-forward mapping along with the hyperbolic Poisson kernel P, (z., w) 11 [c]| )a-
|-=-
for x E 8", w E dB" as the backbone of an even more complicated feature function. Sonoda et al.) 2022) theoretically proposes a continuous version of shallow fully-connected networks compact symmetric space (including hyperbolic space) using Aagason--Furiie transform, where some network functions coincidentally share some similarities to features proposed in this paper.
3 BACKGROUND
Laplace operator (Euclidean). The Laplace operator A on Euclidean space IR" is defined as the di- vergence of the gradient of scalar function i... Af = V V Ei= 0² of A are the solutions of the Helmholiz equation - As = AS R, and can form an orthonormal basis for the Hilbert space (22 when Q E FT compact Giilbarg & Trudinger 2015). i.c.. a linear combination of them can represent any function/model that is L'-integrable. A notable pa- rameterization for these eigenfunctions are the plane waves, given by f(x) exp(i(w,, x.). where w E T and (:--) -) is the Euclidean inner product. A standard result given in Helgason (2022) states that any cigenfunction of A can be written as a linear combination of these plane waves (Theo- rem A.I. The famous result of Rahimi et al. (2007) used these eigenfunctions to construct feature maps, called random Fourier features, for arbitrary shift-invariant kernels in Euclidean space.
The eigenfunctions
Theorem 3.1 (Bochner's 's theorem, Rudin (2017). For any shift-invariant continuous kernel k(x, y) k(x y) on RR", let p(w) be its Fourier transform and Ew (x)) = cxp(i(ue,x)) x.)). Then is positive defiiite if and only if p 2 O, in which case if we draw w proportionally to p.
k(xc - y) = Sax p(w) exp(i(us, x y)) du- k(()) Ba LEw (2) Ew (g)*).
3

---

Under review as a conference paper at ICLR 2023
Since both the probability distribution p(w) and the kernel k( - y) are real, the integral is un- changed when we replace the exponential with a cosine. Rahimi et al. (2007) leveraged this to produce real-valued features by setting = mapping that satisfies the condition IH Bew-ppbb-Uuiffo... 2nr (a d ( = k(x - y)- |Rahimi et al. (007)) approximated functions such as Gaussian, Laplacian and Cauchy kernels with this technique.
v2 (w, .) + b), arriving at a real-valued
Laplace-Beltra Beltrami operator (Hyperbolic). The Laplace- of the Laplace operator to Riemannian manifolds, defined as the divergence of the gradient for any wiicediifferentialle real-valee vellev function f. i.e., Lf = ff. In the n-dimensional Poincaré disk model 6 the Laplace- Laplace-Beltrami operator takes the form (Agmon 1987)
operator L is the generalization
8 L= [1 | E 1=1 Bay 2
0 || E T. Oz."
(w.x)
Just in the Euclidean case, the cigenfunctions of L in hyper- bolic space can be derived by solving the Helmholtz equation. We might hope find analogs of the "plane waves" in hyper- bolic space that are eigenfunctions of L. One way to approach this is via geometric interpretation of plane waves.
5(w.x)
Figure 1: Euclidean hyperplane.
In the Euclidean case, for unit vector w and scalar X, f(x) exp(iX(w, (ws, (w)) is called "plane wave" because it is constant each hyperplane perpendicular to w. We can interpret (w, x) as the signed distance from the origin O to the hyperplane (ww x) which contains x and is perpendicular to w (Figure
In the Poincaré ball model of hyperbolic space, the geometric analog of the hyperplane is the horocycle. For any z E 8 and unit vector w (i.e., w aB"), the horocycle E(w, z) is the Euclidean circle that passes through w. and is tangent to the boundary Og at w, as indicated in Figure 2 We let (w, =) denote the signed hyperbolic distance from the origin O to the the horocycle ((w.z). In the Poincaré ball model, this takes the form (w, z)H ). If we define the "hyperbolic plane waves" exp(u((,, z) where 1 C. Unsurprisingly, they are indeed eigenfunctions of the hyperbolic Laplacian (Agmon 1987).
(w.
5(w, z)
Figure 2: Hyperbolic horocycle.
Lexp(u(w, x)H) = مlب n + 1)e(p(w, z)H).
Since we are interested in finding real eigenfunctions (via the same exp-to-cosine trick used in Rahimi et al. (207)) ), we restrict our attention to μ that yield a real eigenvalue. This happens when
1 + i for real X, in which case the eigenvalue is p n + 1) - - (n 1)²/4. Just as the Euclidean plane waves exp(i(w, x)) span the eigenspaces of the Euclidean Laplacian, the same result holds for these "hyperbolic plane waves" (Theorem A.2
2
4 HYLA: EUCLIDEAN FEATURES FROM HYPERBOLIC EMBEDDINGS
In this section, we present HyLa, a feature mapping that can approximate an isometry-invarian kernel over hyperbolic space IH,, in the same way that the random Fourier features of Rahimi et al. (2077) approximate any inift-invariant kernel over R". In place of the Euclidean plain waves, which are the eigenfunctions of the Euclidean Laplacian, here we derive our feature extraction using the hyperbolic plain waves, which are eigenfunctions of the hyperbolic Laplacian. Since the hyperbolic plane wave exp(( _ - ((w, a) n1) is an eigenfunction of the real operator L with real eigenvalue, so will this function multiplied by any phase exp(- -ib). as will its real part. Call the result of this HyLax,o, (z) = exp ( 2 (w, z) cos (X(w, z) + b).
(1)
This parameterization, which we call HyLa (for Hyperbolic Laplacian features), yields real-valued eigenfunctions of the Sopllac--Beltrnti operator with eigenvalue - (1n-(nn112 1)2/4 /4. HyLa eigenfune- tons have the nice property that they are bounded in almost every direction, as (w, z) approaches 0 as x approaches any point on the boundary of B" except w. Note that HyLa eigenfunctions are invariant to isometries of the space: any isometric transformation of HyLa yields another HyLa eigenfunction with the same À but a transformed w (depending on how the isometry acts on the boundary ) It is easy to compute, parameterized by continuous instead of discrete parameters,
4

---

Under review as a conference paper at ICLR 2023
y?
Kernel value
Heat Kernel
0.6
0.4
0.0
1
dix.9) V2
Figure 3: Visualization of the kernel k(x,, y) when p()) (.0. (left) Distributions of k(æ,, y) and the heat kernel (at temperature = 6) in 3D hyperbolic space: (middle) k(x; O) in 2D Poincaré disk model; (right) (uy)) for HyLa features based on D 1000 samples.
and are analogous to random Fourier features. Moreover, HyLa can be extended to eigenfunctions on other manifolds (e.g. symmetric spaces) since only manifold properties of H.,
We show that for any X E R. under uniform sampling of w and the product HyLay, (z) HyLax,b,w is unbiased estimate of isometry- invariatt kernel k(x, y). Theorem 4.1. Let w be sampled uniformly (under the Euclidean metric) from the boundary 88" and let b be sampled uniformly from (0, 2T). Then E. [HyLax, b, (a)) HyLa,,, [y)) (x(2,)) for any x E R and x; y E H where the function k2 is an isomelry-invaree
kernel given by 1x(2,, y) = = F1 ( - id, n=1 id; 2; 1 (1 cosh(dæ(z,, y))))
2
where 2F is the hypergeometric function, defined via analytic continuation by the power series
2F1 (a, by c2
n= (c).
(a),. g" 1+ ab
i!
+ 1[a+1)b((+1) 2²
c(c+1) 2T +...
(x) < 1).
Note that despite the presence of an i in the formula, this kernel clearly real because the hyper- geometric function satisfies the properties 2Fi (a, by 2)
Fi, 2) and 2Fi (a, by 2)
(a", b"; =====")), =*). In practice, as with random Fourier features, instead of choosing one single X, we select them at random from some distribution p(A). The resulting kernel will be an isometry-
invariant kernel that depends on the distribution of X, as follows:
2: cooshhdaaa( y))) p(A) dA (2) k(x, y) = - 2F1 n--1 + n-1 iA; n,
This formula gives way to derive the isometry-invan interested in finding feature map for some particular kernel, we can invert this mapping to get distribution for which will produce the desired kernel.
kernel from a distribution p()); if we are
Theorem 4.2. Suppose that k(æ:, y) k(da(a (æ, v)) is isometry invariant positive semidefinite kernel. Assume the existence of an associated density p(X) with the kernel, then
p(A) = > tanh ((E) S. Sa k(da(z, O)) exp (!==) ix)(w, z) dw dz.
i.e., p(A) is the spherical transform of the kernel, and if we draw À proportional to p. uniformly on OB", and uniformly on [0, 2T)) then
k:)) EE [HyLax, v. (x) HyLax,e, (v)] kx y) k(x,
Although Theorem 4.2 lets us find HyLa distribution for any isometric kernel, for simplicity in this paper, because the closed-forms of many kernels in HH, are not available, rather than arriving at distribution via this inverse, we will instead focus on the case where & is a Gaussian. This corresponds closely to a heat kernel (Grigor' yan Noguchi 1998), as illustrated in (left.
We will use HyLa eigenfunctions to produce Euclidean features from hyperbolic embeddings, using the same andom-features approach as Rahimi et al. (2007). Concretely, to map from H, to R.D. we draw D independent samples λ A1...., An from p. 1> independent samples w WD uniform from O and D independent samples bi..... ........ bp uniform from 2T). and then output a feature map o the kth coordinate of which is (x(x) /D Hy Hy, dr (x). It is easy to that this will yield feature vectors with E [(((x), d(y)) k( y) as given in Eq. 2
We visualize the kernel k(x, O) for p(A) _N 0.25) in the 2-dimensional Poincarè disk in Figure 3 evaluating the integral in Eq. 2 using Gauss-Hermite quadrature. Figure 3 (right), we sample random HyLa features with D 1000 and plot (Ø(x). o (O)). Visibly, the HyLa features approximate the kernel well. A discussion of the estimation error is provided in Apppnddix B
Connection to Euclidean Activation. There is close connection between the HyLa eigenfunction and the Euclidean activations used in Euclidean fully connected networks. Given data point x e R", weight R., bias b R and nonlinearity a, Fuclidean DNN activation can be
5

---

Under review as a conference paper at ICLR 2023
written as ((we, x) + b) = a[|lo| (T),)) + b). In hyperbolic space, for B", E OB", E RR, b E I and a = cos, we can reformulate the HyLa eigenfunction as HyLaxxa,(z) (AWw, 2) + b) exp ("a² (w) z) HyLa generalizes Euclidean activations to hyperbolic space, with an extra factor exp ("2 (w, z)H) from the curvature of ,
From a functional perspective, any f E (HH,) can be expanded as an infinite linear combination (integral form) of Hyl.a (Theorem 4.3 in [Sonoda et al. (2022)). This statement holds whenever the non-linearity a is a tempered distribution on R, i.c., the topological dual of the Schwartz test functions, including ReLU and cos. Though the features will not approximate a kernel on hyperbolic space if a + cos, this suggests variants of HyLa with other nonlinearities may be interesting to study.
HYLA FOR GRAPH LEARNING
In this section, we show how to use HyLa to encode geometric priors for end-to-end graph learning.
Background on Graph Learning. A graph is defined formally as G = A). where V represents the vertex set consisting of nodes and A E R=** represents the symmetric adjacency matrix. Be- sides the graph structure, each node in the graph has a corresponding d-dimensional feature vector: we let X E Raxd denote the entire feature matrix for all nodes. A fraction of nodes are associated with a label indicating one (or multiple) categories it belongs to. The node classification task is to predict the labels of nodes without labels or even of nodes newly added to the graph.
An important class of Euclidean graph learning model the graph convolutional neural network (GCN) (Kipf & Welling 2016; Defferrard et al. 2016).. The GCN is widely used in graph tasks including semi-supervised learning for node classification, supervised learning for graph-level clas- sification, and unsupervised learning for graph embedding. Many complex graph networks and GCN variants have been developed, such as the graph attention networks (GAT, Veličković et al. (2117). FasIGCN (Chen et al. 2018). GraphSage (Hamilton al.) 2017), and others (Velickovic et al. 2019 Xu et al. 2018). An interesting work to understand GCN is simplifying GCN (SGC, Wu et al. (019)): linear model derived by removing the non-linearities in K-layer GCN as: f(A,X) softmax(S (S* XW), where S is the "normalized" adjacency matrix with added self- loops and W is the trainable weight. Note that the pre-processed features S X can be computed before training, which enables large graph learning and greatly saves memory and computation cost.
End-to-End Learning with HyLa. We propose feature-extracted architecture via the following recipe: embed the data objects (graph nodes or features, detailed below) into some space (e.g., Euclidean or hyperbolic), map the embedding to Euclidean features X via the kernel transformation RFF or Hyla),, and finally apply an Fuclidean graph learning model f(A,X) This recipe only manipulates the input of the graph learning model and hence, this architecture can be used with any graph learning model. The graph model and the hyperbolic embedding are learned simultancously with backpropagation. In theory, the embedding space can be any desired space, just use the same Laplacian recipe to construct features. Below we only show the pipeline for hyperbolic space, while we also include Euclidean space (with random Fourier features) as a baseline in our experiments.
RF.
Directly Embed Graph Nodes. We em- bed each node into low dimensional hy- perbolic space 18 as hyperbolic embed- ding Z E x for all nodes in the graph, which can be either pretrained fixed em- bedding or as parameters learnt together with the subsequent graph learning model during training time. To compute with the HyLa eigenfunctions, first sample d, points uniformly from the boundary 00d to get 52 E xdo, then sample d1 eigenvalues and biases separately from (0, s²) and Uniform([0, 2x]) to get A, B Rdd where is scale constant. matrix (X E "x computation follows; please refer to Algorithm [ for detailed breakdown. The mapped features X are then fed into the chosen graph learning model f(A, X) for prediction.
Algorithm 1 End-to-End HyLa
input: n objects, Poincaré disk Bdo HyLa feature dimension d1, adjacency matrix A, node feature ma- trix X, graph neural network f initialize Z E x (hyperbolic embeddings} sample boundary pts matrix S E IRd eigenval- ues A E Rndd and biases B E =
compute P= Z)
== { distance}
compute X exexp a=1 P) cos(A (A P + B) (HyLa}
if embedding features: X = XX Baxd return Y = (A, {e.g., SGC)
The resulting feature

---

Under review as a conference paper at ICLR 2023
Embed Features. One can also embed the given features into hyperbolic space as derive the node features implicitly. Specifically, when a node feature matrix X E Rn is given, we initialize hyperbolic embedding for each of the d dimensions to derive hyperbolic embeddings Z E R The Euclidean features X can be computed in the same manner following Algorithm | However, to get the new node feature matrix, an extra aggregation step X = XX E Raxd1 is required before fedding into a graph learning model.
Embedding graph nodes is better-suited for tasks where no feature matrix is available or meaning- ful features are hard to derive. However, the size of the embedding Z will be proportional to the graph size, hence it may not scale to very large graphs due to memory and computation constraints. Furthermore, this method can only be used in a transductive setting, where nodes in the test set are seen during training. In comparison, embedding features can be used even for large graphs since the dimension of the original feature matrix is usually fixed and much lower than the number of nodes n. Note that the hyperbolic embeddings are built for each feature dimension, they can be used in both transductive and inductive settings, as long as the test data shares the same set of features as the training data. One limitation is that its performance depends on the existence of feature matrix X that contains sufficient information for learning.
Any graph learning model can be used in the proposed feature-extracted architecture. In our ex- periments, we focus primarily on the simple linear graph network SGC, which takes the form fA, = softmax A K (W) with a trainable weight matrix W. Note that just as the vanilla SGC case, A A X can be pre-computed in the same way before training and inference. For the purpose of end-to-end learning, we jointly learn the embedding parameter Z and weight W in SGC during the training time. It's also possible to adopt two-step approach, i.c., first pretrain hy- perbolic embedding following (Nickel & Kiela, 2017 2018 Sala et al., (018:/Snthhlin & Gilbert, 2020 Chami et al. (2019), then fix the embedding and train the graph learning model only. We defer this discussion to Appendix D due to page limit.
6 EXPERIMENTS
6.1 NODE CLASSIFICATION
Task and Datasets. The goal of this task is to classify each node into a correct category. We use transductive datasets: Cora, Citeseer and Pubmed (Sen al.] 2008), which are standard citation net- works benchmarks, following the standard splits adopted in Kipf & Welling (2016). We also include datasets adopted in HGCN (Chami et al. 2019) for comparison: disease propagation tree and Air- port. Yhe former contains tree networks simulating the SIR disease spreading model (Anderson & May 1992). while the latter contains airline routes between airports from OpenFlights. To measure scalability, we supplement our experiment by predicting community structure on large inductive dataset Reddit following Wu et al. 2019). More experimental details are provided in Appendix E
Experiment Setup. Since all datasets contain node features, we choose to embed features most of the time, since it applics to both small and large graphs, and transductive and inductive tasks. The only exception is the Airport dataset, which contains only 4 dimensional features-hers we HyLa/RFF after embedding the graph nodes to produce better features X. We then use SGC model as softmax A XW), where both W and Z are jointly learned.
Baselines. On Disease. Airport, Pubmed, Citeseer and Cora dataset, we compare our HyLa/RFF- SGC model against both Fuclidean models (GCN, SGC and GAT) and Hypeholic models (HGCN, LGCN and HNN) using their publicly released version in Table [ where all hyperbolic models adopt 16-dimensional hyperbolic space for consistency and fair comparison. For the largest Reddit dataset, a 50-dimensional hyperbolic space is used, We also compare against the reported performance of supervised and unsupervised variants of GraphSAGE and FastGCN in Table Note that GCN based models (e.g.. HGCN, LGCN) could not be trained on Reddit because its adjacency matrix is too large to fit in memory, unless a sampling way is used for training. Worthy to mention, despite of the fact that standard Euclidean GCN literature (Kipf & Welling 2016 Wu et al. 2019) train the model for 100 epochs on the node classification task, most hyperbolic (graph) networks in- cluding HGCN, LGCN, GIL.Treport results of training for (5-)thousand epochs with early stopping.
We cannot replicate results of GIL. from their public code.
7

---

Under review as a conference paper at ICLR 2023
Table 1:
Test accuracy/Micro Fl Score (%) averaged 10 Performance of some baselines are taken from their original papers. OOM: Out of memory.
node classification task.
Model
Test F1
Datasct
Discase
Airport
Pubmed
Citesoer 5.0
Cora 11
llyperbolicity 6
1.0
3.5
GCN
OOM
GCN
69.7 + 0.4
81.4
78.1
0.2
70.5 + 0.8
81.3 + 0.3
HGCN
OOM
SGC
69.5 = 0.2
80.6
+
71.9 0.1
0.0
LGCN
OOM
GAT
70.4 1 0.4
0.3
79.0 0.3
83.0 1.7
SAGE-mean
95.0
HGCN
74.5 0.9
9.2
0.3
0.6
0.2
SAGE-GON
93.0
LGON
81.3 + 4.0
0.7
7.88
0.8
7..0
FasIGCN
93.7
HNN
41.0
0.55
69.8 0.4
1.0
54.6
SGC
94.9
RFF-SGC
83.4
94.8
77.6
0.6
8166
RFF-SGC
93.9
HyLa-SGC
86.8 2.1
95.2 0.5
80.3
0.9
72.6
0.5
HyLa-SGC
94.5
2nd Princpal Direction
23
1-SNE-
40
-40
-20 20
-40
-23
-20
20
80
C-NEE-
E-SE-X
1st Principal Direction
Figure 4: Visualization of node HyLa features on Cora, Airport and Disease datasets, where nodes of different classes are indicated by different colors. (left) t-SNE on Cora; (middle) t-SNE on Airport; (right) PCA on Disease.
For a fair comparison, we train all models for a maximum 100 epochs with early stopping, except from HGCN whose results were taken from the original paper trained for 5,000 epochs.
Analysis. Our ctature-extracted architecture is particularly strong and expressive to encode geomet- ric priors for graph learning from Table ! Together with SGC, HyLa-SGC outperforms state-of- the-art hyperbolic models on nearly all datasets. In particular, HyLa-SGC beats not only Euclidean SGC/GCN, but also attention model GAT, except the Cora dataset with comparable perfor- mance. For the tree network disease with lowest hyperbolicity (more hyperbolic), the improvements HyLa-SGC over HGCN is about 12.3%! The results suggest that the more hyperbolic the graph is, the more improvements will be gained with HyLa. On Reddit, HyLa-SGC outperforms sampling- based GCN variants, SAGE- GCNN and FastGCN by more than 1%. However, the performance close to SGC, which may indicate that the extra weights and nonlinearities are unnecessary for this particular dataset. Notably, RFF-SGC, embedding into Euclidean space and using RFF, sometimes can be better than GCN/SGC, while Hyl is consistently bettter than RFF-SGC.
Visualization. In Figure 4 we visualize the learned node Euclidean features using HyLa on Cora, Airport and Discase datasets with t-SNE (Van der Maaten & Hinton 2008 and PCA projection. This shows that HyLa achieves great label class separation (indicated by different colors).
6.2 TEXT CLASSITCATION
Task and Datsets. We further evaluate HyLa on transductive and inductive text classification task assign documents labels. We conducted experiments on standard benchmarks including R52
and R8 of Reuters 21578 dataset, Ohsumed and Movie Review (MR) follows the same data split as Yao al. (2019): Wu et (2019). Detailed dataset statisties are provided in Table
Experiment Setup. In the transductive case, previous work Yao et al. (2019) and Wu et al. (2019) apply GCN and SGC by creating corpus-level graph where both documents and words are treated as nodes in the graph. For weights and connections in the graph, word-word edge weights are calculated as pointwise mutual information (PMI) and word-document edge weights as normalized TF-IDF scores. The weights of documenn-documenn edges unknown and left 0. We follows the same data processing setup for the transductive setting, and embed the whole graph since only the adjacent matrix is available. In the inductive setting, we take the sub-matrix of the large matrix in
'HGCN requires pretraining embeddings from link prediction task to achieve reported results node classification task for Pubmed and Cora.
8

---

Under review as a conference paper at ICLR 2023
Table 2: Test accuracy (%) averaged over 10 runs transductive and inductive text classification task except from the LR mode. Bold numbers: best in both transductive and inductive setting; Underlined numbers: best in inductive setting.
Setting
Methods
R8
R52
Ohsumed
MR
TexIGNN
97.1 +
93.5 + 0.2
68.4 0.6
76.7 0.2
Trans-
TextSGC
97.2 0.1
94.0
75.9 0.3
0.3
ductive
RFF-SGC
96.5
91.0 0.5
6.42
13.1:0.1
HyLa-SGC
9.4
94.1 0.3
76.2 0.3 0.5
TextGCN
88.2+ 9.3 0.3
57.7
74.8+00 0.3
Inductive
I.R
93.3
85.6
56.6
73.0
HyLa-LR
97.4
93.5 + 0.2
64.9
75.5 1: 0.3
RFF-LR
9..0
92.2 0.2
0.3
76.0 + 0.3
the transductive setting, including only the document- word edges the node representation feature matrix X, then follow the procedure in Section 5 to embed features and apply HyLa/RFF to get X. Since the adjacency matrix of documents is unknown, we replace SGC with a logistic regression (LR) formalized as Y softmax X XW). We train all models for maximum of 200 epochs and compare it against TextSGC and TexIGCN in T
Performance Analysis. In the transductive setting. HyLa-based models can match the performance of TexIGNN and TextGGC The corpus-level graph may contain sufficient information to learn the task, and hence HyLa-SGC does not seem to outperform baselines, but still has a comparable per- formance. HyLaa shows extraordinary performance in the inductive setting, where less information used compared to the (transductive) node level case, i.c. a submatrix of corpus-level graph. With a linear regression model, it can already outperform inductive TexIGNN, sometimes even better than the performance of a transductive TexIGCN model, which indicates that there is indeed redundant information in the corpus-level graph. From the results the inductive text classification task, argue that HyLa (with features embedding) is particularly useful in the following three ways. First, solve the OOM problem of classic GCN model in large graphs, and requires less memory during training, since there are limited number of lower level features (also X is usually sparse), and there is no need to build corpus-level graph anymore. Second, it naturally inductive as HyLa is built at feature level (for each word in this task), it generalizes to any unseen new nodes (documents) that uses the same set words. Third, the model is simple: HyLa follows by a linear regression model, which computes faster than classical GCN models.
Efficiency. Following Wu et al.. (2019). we measure the training time of HyLa- mod- els on the Pubmed dataset, and we compare against both Euclidean models (SGC, GCN, GAT) and Hyperbolic models (HGCN, HNN). In Figure S we plot the timing performance of various models, taking into account the pre- computation time of the models into train- ing time. We measure the training time on NVIDIA GeForce RTX 2080 Ti GPU and show the specific timing statistics in Appendix. HyLa-based models achieve the best perfor- mance while incurring a minor computational slowdown, which is 4.4x faster than HGCN.
test Securda (%6
SGC
10.5
GAT
41,7 X
33.
LG:04 20.5
20
relative training
Figure 5: Performance over training time on Pubmed. HyLa-SGC achieves best performance with minor computation slowdown.
CONCLUSION
We propose simple and efficient approach to using hyperbolic space in neural networks, by deriv- ing HyLa as an expressive feature using the Laplacian eigenfunctions. Empirical results on graph learning tasks show that HyLa can outperform SOTA hyperbolic networks. HyLa sheds light principled approach to utilizing hyperbolic geometry in an entirely different way to previous work. Possible future directions include (1) using HyLa with non-linear graph networks such as GCN to derive even more expressive models; and (2) adopting more numerically stable representations of the hyperbolic embeddings avoid potential "NaN problems" when learning with HyLa

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shmuel Agmon. On the spectral theory of the laplacian on noncompact hyperbolic manifolds.
Journées Equations aux dérivées partielles, pp. 1-16, 1987.
Roy M Anderson and Robert M May. Infectious diseases of humans: dynamics and control. Oxford university press, 1992.
Silvere Bonnabel. Stochastic gradient descent riemannian manifolds. IEEE Transactions Automatic Control, 58(9))2217722222, 2013.
Brian H Bowditch. A course on geometric group theory. 2006.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in neural information processing systems, 32:4868 4879, 2019.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling, arXiv preprint arXiv: 10247.01177,,,.. 2018.
Wei Chen, Wenjie Fang. Guangda Hu, and Michael W Mahoney. On the hyperbolicity of small- world and treelike random graphs. Internet Mathematics, 944):434-491 2013.
Eli Chien, Puoya Tabaghi, and Olgica Milenkovic. Hyperaid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering. arXiv preprint arXiv:2205.0972), 2022.
Hyunghoon Cho. Benjamin DeMeo, Jian Peng, and Bonnie Berger. Large-margin classification in hyperbolic space. The 22nd international conference on artificial intelligence and statistics, pp. 1832-1840. PMLR, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844-3852. 2016.
Pengfei Fang, Mchrtash Harandi, and Lars Petersson. Kernel methods in hyperbolic spaces. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 10665-10674, 2021.
Octavian-Fugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. arXiv preprint arXhv:1805.09112. 2018.
David Gilbarg and Neil Trudinger. Elliptic partial differential equations of second order, volume 224. springer, 2015.
Alexander Grigor' yan and Masakazu Noguchi. The heat kernel on hyperbolic space. Bulletin of the London Mathematical Society, 30(6))643-633 1998.
Caglar Gulcehre, Misha Denil, Mateusz Malinowski. Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, et al. Hyperbolic attention networks. arXiv preprint arXiv: 097866 2018.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Sigurdur Helgason. Groups and geometric analysis: integral geometry, invariant differential oper- ators, and spherical functions, volume 83, American Mathematical Society, 2022.
Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches social network analysis. Journal of the american Statistical association, 97(460); 1090-1990, 2002.
Dhiraj Kalamkar, Dheevatsa Mudigere, Naveen Mellempudi, Dipankar Das, Kunal Banerjee, Sasikanth Avancha, Dharma Teja Vooturi, Nataraj Jammalamadaka, Jianyu Huang, Hector Yuen, et al. A study of bfloat16 6 for deep learning training. arXiv preprint arXiv: /2322, 2019.
10

---

Under review as a conference paper at ICLR 2023
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988) 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609. 0290,0 2016.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. arXiv preprint arXiv: 12892, 2019.
Emile Mathieu, Charline Le Lan, Chris Maddison, Ryota Tomioka, and Yee Whye Teh. Con- tinuous hierarchical representations with poincaré variational auto-encoders. Advances in neural information processing systems, 32, 2019.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representa- tions. Advances in neural information processing systems, 30:6338-6341 6347, 2017.
Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International Conference Machine Learning, pp. 3779-3788, PMLR, 2018.
Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS, volume 3, pp. 5. Citeseer, 2007.
Erzsébet Ravasz and Albert-Lászi Barabúsi. Hierarchical organization in complex networks. Phys- ical review E. 67(2):0261 12,6 2003.
Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoffs for hyperbolic embeddings. In International conference on machine learning, pp. 4460-4460 PMLR, 2018.
Prithviraj Sen, Galileo Mark Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):33-006 2008.
Ryohei Shimizu, Yusuke Mukuta, and Tatsuya Harada. Hyperbolic neural networks++. arXiv preprint arXiv:2006.082 082 10, 2020.
Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda. Fully-connected network on noncompact symmetric space and ridgelet transform based on helgason-fourier analysis. arXiv preprint arXiv:2203.01631, 2022.
Rishi Sonthalia and Anna Gilbert. Tree! i am no tree! am a low dimensional hyperbolic embedding. Advances in Neural Information Processing Systems, 33:845-855 8566, 2020.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Ming-Xi Xi Wang. Laplacian cigenspaces, horocycles and neuron models on hyperbolic spaces. 2020.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- 6861-6871. PMLR, 2019.
Keyulu Xu, Weihua Hu. Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.000 2018.

---

Under review as a conference paper at ICLR 2023
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 7370-7377, 2019.
Tao Yu and Chris De Sa. Numerically accurate hyperbolic embeddings using tiling-based models. Advances in neural information processing systems, 2019.
Tao Yu and Christopher M De Sa. Representing hyperbolic space accurately using multi-component floats. Advances in Neural Information Processing Systems, 34, 2021.
Tao Yu. Went Guo, Jianan Canal Li, Tiancheng Yuan, and Christopher De Sa. Mctensor: A high-precision deep learning library with multi-component Moating-point. arXiv preprint arXiv:2207.08867. 2022.
Steve Zelditch. Eigenfunctions of the Laplacian Riemannian manifold, volume 125. American Mathematical Soc., 2017.
Yiding Zhang, Xiao Wang, Chuan Shi, Xunqiang Jiang, and Yanfang Fanny Ye. Hyperbolic graph attention network. IEEE Transactions on Big Data, 2021a
Yiding Zhang, Xiao Wang, Chuan Shi, Nian Liu, and Guojie Song. Lorentzian graph convolutional networks. In Proceedings of the Web Conference 2021, pp. 1249-1261 1261, 2021b.
Shichao Zhu, Shirui Pan, Chuan Zhou, Jia Wu, Yanan Cao, and Bin Wang. Graph geometry inter- action learning, Advances in Neural Information Processing Systems, 33:7548-7558, 2020.
12

---

Under review as a conference paper at ICLR 2023
A
THEOREMS
Theorem A.1 (Helgason (002); Zelditch (2017)). All smooth eigenfunctions of the Euclidean
Laplacian A on I² are
= = S ( dT dT(),,
where À E C - {0) and T is analytic functionaa (or hyperfinnciion), i.e., an element of the dual space of the space of analytic functions on 5
Theorem A.2 (Helgason
) Zelditch 2017)
All smooth eigenfunctions of the Hyperbolic
Laplacian on 3" are
f(z) Jog= exp((i> + (w z) dT(w),
where À C and T is analytic functional (or hyperfunction).
Lemma A.3 (Expression of k(æ, O)). Denote (x,((z) - exp (1= + i>)(w, z)H then the cor-
responding kernel kx (x, O) for a particular value of defined
ka(2; O) E [HyT (Hyyaaxbb. m (a)) HyL (1))
E (aw
2 B (x)) (3)
takes the form
n1
id, iA; n 1 2' cosh(daa O)))
n2 n-1
(x 0) 0-= - 2F
2
where the expectation in Equation taken over w drawn uniformly from the n-dimensional unit sphere.
Proof. Recall that for æ in the n-dimennional Poincare ball 8 and w E 0B"
(wo x) и = log
w
Let a-1 + id, expanding Equation
out,
|
(x O)
E
exp
7 log
|
w
1
||a=||
1 + ||2:1 11
2
exp
ylog
1
||==||
2
E
exp
? log
|| wlll 2
1
||=|||
|
[
w||
2
exp
7 7og
||a||| 2
E
||>||| |
[ 2 2w x + ||001| -7)
||
2 cxp
7 log
1
||=|| 2
E
1 + xx|
and if we let
||>|||
1
| 2'
and let & denote the unit vector in the direction of ær then this becomes
||=
(1 ud w)
1 [x. O 2
exp
log
E
+ x
Expanding this out using the Binomial Formula (which is valid here because
/u||
< 1), we get
bx(2: O) =
exp
y yoo
1
[
(eTw))
1
|
k
exp
Y log
1
|
2
*
E
T
w
1
+
|
k=0
13

---

Under review as a conference paper at ICLR 2023
Since this expected value is for odd k, this becomes
1 (v, 0) 2
exp
7log
2 x
Σ k=0
2k
R
@n: w
2k
But a² w has the same the distribution as the inner product of two uniform random unit vectors in n dimensions. The square of this is well known to be Beta-distributed with parameters (2) m=1 ). So we can write this as
1
- | 1 + x
A O)
exp y log
2k
E
100
2k
k=0
where w Beta 2z1). Of course, the moments of the Beta distribution are well-known to
E
w
(R)
where (x)) denotes the Pochhammer symbol representing the rising factorial. On the other hand,
(-7)
2k
(2k)!
where T(kk) denotes the Pochhammer symbol representing the falling factorial. Since x(())
(-1))(-z)(() write this in terms of rising factorials
(>>
(>) (2))
2k
(2k)
So substituting everything in, we have
1
(7 7
1 - || 1
(7))
(2) (k)
(2x 0)
2
exp
1 1 | 12
(2k:)!
2k
; (16
==
Next, observe that
1
(2k)
+
2 d
(2m +
-
2
2
k!
m=
m=0
So this becomes
1
1 - || 1|2
(2k)
(2x 0)
exp
7 log
+ || 11
k!
4 4-k
m (N)
Next, we leverage the famous identity that
(2h) 46
? (R)
+ 2
1
(R)
to get
kx [x, O) =
2 exp
7 7og
2
8
(K)
7
(8)
u 2h
k=0
|00
+
7 72
2 exp
y log
[=]|]
2
F2
2
2
Since
4 ||||||
1 +
||
+ |
14

---

Under review as a conference paper at ICLR 2023
it follows that
2
||=|| 2
+
1
u²
1 + || 1| + +|211]
and
vI u² -1
x
2v1 u2
x:
Recall
the
classic
formula
ttttss// wo com/
that
v1
-
2 a, aa+ + 2:0² = - -) 2
2a, 2c 2a
1;;;
2
Substituting u² and マタZ yields
||0||²
7/ 7 - 1; n2
(ar 0) = 0)=
F1
2'
| 1|
1
n1 n-1
n1
ii; n
- -1|2=||
F2
+ +1,,
2
2
2
2
|
Therefore,
[ | tanh tanh2(D/2) -tanh?(D/2) (D/2) sinh?(D/22) = -1-con cosh (D)),
tanh
| 1 1 - tanh (D/2) sech² Scch²(DD2) (D/2)
2
where = dæ( O). So we get final expression
1
n n
+ + n - - iA; n 1
(1 (d 0
(x 0)
2Fi
2
2
2 2
The proof is done here. We further make remark here. Recall that for the Poincaré ball model,
| + 1
d(x, 0) 2 log
||00| || \
[1|20
||
+ 1) 2
log
1 ax 11
1 +
[
||
log
||>||
2 aaraan
Therefore,
|
tanli
log
log
1+
[
+ tanh 2 (D/2)
sech² (D/2)
log
1 + tanh Faanh2(D//)) PDD/2)
log
(inhh?(D/2) + cosh?(DD2))
log
(inhh((D/2)) cosh? (D/22
log (cosh(D)).
And on the other hand,
tanh (D/2)
=
tanh(D).
1 + tanh (D/2))
15

---

Under review as a conference paper at ICLR 2023
then also write the kernel as
(x O) 2
1
exp
1
+ +1x log (cosh(D)) 2f
11 ++
+
A n2 -1
+ + tDnh
2
2
where D = da O).
Lemma A.4 inoometr--nvariancee
The kernel defined by
(x y) -EE (x)'
- E exp
( (--1
(1) W)
+
nn- + + (y) ]
is isomelry-invariant.
Proof.
Let g be any isometry of the space, then observe the geometric identity (Helgason
2022 :
(g o g. w) (z, w) +
(4)
Take = g- in Equation
4 follows that
(g w) = (.. 9 w) + w,
Take = g O in Equation
4 follows that
= 0 = (0 = (00
+
i...
-- = -go
replace g with g. then
(g0.w = 69 00
By definition,
n-1
(2) + 1-1
iA) -a))).w)))
(x 3) 2 E
exp
(5)
2
Now assume, g y O, then consider
kx x. 0) E
(
(A,
2 . (go x)
1
n- 1
E
exp
i
(gox,w) w)
E
exp
n - 1
i
((2,g ow) + + (go
2
1
E
exp
n - 1
i
((2,g- )w) - 69 0 (w))
2
E
cxp
n -
1
((z,g (w) (y.g ww)
2
1
n 11-1
i (1x. (g.g - o wi)) pi pi(w)dw.
exp
gg--
where (I(w) is uniform distribution over the sphere, use w g then
change of variable.
kx 2, x, 0) =
exp
2 (
n 1 - -id) (1x,g-towl - o w)) PI (w))d
ga-1
n (n-1 - -i ((x, ()) (y. ()) pi (g ()
exp
ga
2
We claim that the mapping g acts on the boundary with the Jacobian given by
1 1 0 2 n-1
d(gow) = 2 exp((n - 1). 19-99-91 10.100,000 -0,0)) =
(6)
d(o))
||
16

---

Under review as a conference paper at ICLR 2023
then
1
11-1 1
-100-yy,,,1 ((x, - (y, (0)) ) i (
kx x. 0)
exp
i1
2
g--1
2
1
11 1
exp
i
((x,, (0) (v. (1, pn (x)00))) 1) 0,
2
9n-1
2
1
exp
11 1
ii
((xr, (3)
(y, x)) + (n 1) (v. (v. p pi
(
2
1g-1
2
1
11-1
1
exp
it
(a,, (0) +
1
+ i1
(y. (0) Pi (((o
2
@n-1
2
2
1
11 1
11 - 1
exp
i
(c,, ()) (x),00) +
2 + +id) (v,
pi pi
1g-1
2
Since P1 is a uniform distribution, this is
exp (m²21 - (x, (3) +
12 n-1
(y), mo:
kx o x, 0) = 2
E 2
12
(
+ id
2
compared with Equation 5 follows that 1x (gox, 0) = (x. y) Since k (gox O) only depends
on dur (goz, O) dz (zz, 100)= = dz y) from Lemma A.3 then lix (xe, y) is distance-invariant, and hence isonetry-invariant
It suffices to prove Equation 6 i.e.,
d(g (W) d(w)
1
1 | - w 1
1
n-1
clearly it holds when 9 is an rotation, it suffices to show this for translation isometry. Denote Inv(x)=
x then in the Poincarè Ball model, all translation isometry takes the form |
(x) a + (1 -[aal)))) Inv (lnv(z) - -a), where both x, a in the Poincarè Ball model and Ta (a)= = O = a. Thus,
w a (w( -a a (1-1laa))) (nv(Inv(w)-o) -a - - (1-1aaaaaaalaalllla 122 Inv(w-a) = -1(1|al)))))) || lww-|l*
where the fact ||س|| 1. Since the integral is taken over the unit sphere with ||||| 1, I (w)]l = 1, we consider only the mapping of Ta restricted to the first n 1 (free) dimensions, dimensional vector. Then the Jacobian of To (w)
with an abuse of notation, regard w as an with respect to w is
dTa (w) = (1 - [|al))dt )dl
w a
||W - all
can calculate that
|ا - all dw - (w a) 2((w dww
d( w a
[ all
|| w - all 4
|| a|| 2(w a) (w -a) dw
w - all
||ا - a|l ?
dw
-n- 2(w a) (w (w- - a)
|| all 2
||ا - all
then
dTa(w)
1 - ||a|2
I I 2(w - a) (w- a)T
dw
|| - all
|| - all
note the relation that
det(I + Tyy*) + xTy.
17

---

Under review as a conference paper at ICLR 2023
then
1 2(w - a) (w - a
2(w - a)T (w a
1 - 2 = -1,
|ا - a
|| - -al
then the absolute value of determinant of the Jacobian is
|det( ((Ta(w))
|a|
|
2(w a) -
det
dw
||
|| all
1 ||
|
|| - all |
1 ||g
012 n-1
|| g- Ol |
with which change of variable would give
d(g w) d(ww)
1 - | 9 0 1g w 12
n-1
which finishes the proof.
Proof of Theorem 4.7 follows:
As a result of Lemma
A.3 and Lemma A.4 the expression for (x, y)
(x, y)
2 2f n1
+ + n iA;
n
(1 cosh(da (()(=.))))))
2
2 2
where 2 is the hypergeometrii function, we can also apply the Euler transformation to get
(x v) = 2 _ (1 cosh(d((z,,))) 1-#
[
FF
1
1
+
12
1
i2: 5 (1 cosh(dn(2;, v)))
If we let
2 == 2
(1 (o (x)()))) B)))
then this is written more succinctly as
1 2 (1- 1 =F
xx 3)
+ id,
id; 2
2
2
2
We can also write this as a Legendre function,
(x y) = (1 (1-z) -1-
72
z 1
2-n
(1-z)
n=3
11-3
1+2 (1 - 22)
2
2
1
(=(1 - -2)) =)) سية
r
11
p2- 3
p
(1 2z)
2
++
Observe that
1 (dsinh?(da(zz) 8))
2(1 2) (1 cosh (dn B)))
4
and similarly
1- 1-2z cosh(dn(zzg)) ()).
This is manifestly real because
20
+ + i2) (~ +m -i)
1
kx 3)
2 (1 (dx B)))
2 k= m=
+ m) (1 + m)
1
[-1
+ +m)² 2 + X2
1
2
(1 cosh(da (œ, y)))
2
+ m) (1+ m)
2
A=U m=0
18

---

Under review as a conference paper at ICLR 2023
If we draw HyLa features using distribution p over X, then the resulting approximated kernel will be
k( y)
(x, y) p(()) dA
-00
30
n
n c--oos(dd((; vi))) p(2) ds
=
F
+
12,
id;
2'2 (1
2
2
2
Proof of Theorem 4.2
Denote
xx = Lown (x = - exp (M=)) + iA)ww, //111)/11// dw,
which are basic spherical functions. For any 2, y B", assume By is isometry that maps y to
the origin, i.c. By O, denote & By then hy (x, y) = (x i O) for any X, note that
(
n-
k (á, 0) - 2 ga-1
exp
+
(w, 2) (w)
2
/
n-
2
Area(Sn-1)
exp
2
+ (w) 23 dw
1
1
Area (Sea(Sn-1) (1(2),
where we use the fact that p1 (w) is uniform distribution over the sphere. Assume the existence of an associated density p()) with the kernel, then
k(x,, y) :-daa v)) k(da(E (o)
kx y) p(A) yd
(x 0) p(A) da
1
(x())) p(A) da
Area p
(1 p(A) dd
Area(S
((A)
IA (x |c(A)] da
AArea (5-1))
tanh
?
where lc(A)] = xd tanh a1 2
when X E R. Note that the last integral is exactly the inverse hence can be derived in the reverse direction
spherical transform (Helgason 2022 of À tann 2
p())
by taking the spherical transtorm of (dd O)). ie..
p())
/ k(da(a (
A tanh
mA 2
Hence p()) can be derived as
Tr
/
P(A) = À tanh
A(da(i, (
2
Bm
T
/ J98"
n1 ( - x) dwdz. (
= A
k(du (z, 0)) exp
2
Bm
Therefore, given an isometry-invann invariant positive semidefinite kernel k(x,, y) k(dn( B)), we can compute p()) following the above expression if it exists, then the rest of the theorem follows. 17
19

---

Under review as a conference paper at ICLR 2023
0.09
Averaged Estimation Error
0.08
0.07
0.06
0.05
0.04
0.03
0.02
0
200
400
600
800
1000
Sampling Number
Figure Averaged estimation error HyLa to the kernel
B CONCENTRATION OF THE KERNEL ESTIMATION
The readers may wonder whether there is concentration behavior using the random variable (ő(z), (ty) to approximate k( y). Unfortunately, the eigenfunction <(x) itself is not sub- Gaussian so as to derive a concentration bound a straightforward way, but we do provide a nu- merical experiment measure the estimation behavior. For the estimation in FFiuurr 3) sampled 1, 000 different eigenfunctions.
We first fix of 1, 000 points x; by uniformly sampling 2-dimensional hyperbolic space, then approximate the kernel k(o, x;)) using (Φ(x;;; ((o)) by sampling with an increasing number of eigenfunctions, ranging from 50 1, 000. At last, we compute the mean absolute error of the estimation (Ø(æ;), 6(o)) to the true kernel value k(o, æz). We plot the mean estimation error in Figure which seems to be an exponentially decay, it's an interesting future work investigate this estimation error.
C NODE EMBEDDING VS FEATURE EMBEDDING
When HyLa is adopted node level, i.e., each vertex/node v; in the graph is associated with hyperbolic embedding parameter z, Bdo, Then the inner product of HyLa features (Φ(zz), o(2,) of vertex Us, vy approximates some kernel k(2,, 2,) The optimization of z; encourages learning of the kernel on the hyperbolic space to solve the task.
When HyLa is adopted feature level, i.e., each column dimension of the node feature E gaxd is associated with hyperbolic embedding parameter z; E Bd, The HyLa feature associated to each vertex/node is then computed as Ed= X,o(zz),, where Σd= X 1 if a row-normalization applied on the original node features.
Therefore, the inner product of two node HyLa features is
X
(z)()))
Σ
x ((((z))
Σ
XxxX (
1=1
k,1=1
20

---

Under review as a conference paper at ICLR 2023
Table 3:
Node classification Dataset statistics.
Setting
Dataset
Nodes
Edges
Classes
Features
Table 4: Text classification Dataset statistics.
Cora
2,708
5,429
1,433
Dataset
Docs
# Words
Average Length Classes
Trans- ductive
Pubmed
Citeseer
19,717
3,327
44,338
4,732
3,703
500
R8
7,
7688
65.72
R52
9, 9,100
8892
69.82
52
Disease
1,044
1,043
1,000
Ohsumed
7400
14157
135.82
23
Airpott
3,188
18,631
MR
10662
18764
20.39
2
Inductive
Reddit
233K
11.6M
41
6U2
which in expectation equals a linear combination of kernels, i.e., Σi.=n fore, it captures much more complicated kernel relation on the hyperbolic space than directly embedding nodes.
Ektt=1 X.a XaKkki zt). There-
D TWO-STEP APPROACH
For the purpose of end-to-end learning, in our experiments, we jointly learn the embedding param- eter Z and weight W in SGC during the training time, detailed in subsectiio E.2 It's possible
to adopt a two-step approach, i.e., first pretrain a hyperbolic embedding, then fix the embedding and train the graph learning model only. In the first step, for example, optimization-base
methods
(Nickel & Kiela 2017 2018) and combinatorial construction methods (Sala et al.) 2018 SSonthaia be adopted by supervising the graph connectivity. However, these methods only utilize the graph structure information, but ignore the node feature information X, which leads natural performance degradation. In comparison, as shown in experiments and analyzed in AA- pendix C our end-to-end learning of HyLa can be used to embed features and enables learning complex kernel representation to avoid this shortcoming. Intuitively, the graph connectivity infor- mation can be too general for downstreaming tasks which rely more on semantic information. It's not clear to us how to encode the semantic information (node features) into embedding following e.g., Nickel & Kiela 2017 2018).
Gilbert 2020
Another way (Chami et al., 2019) of deriving pretrained hyperbolic embedding that might take semantic information into consideration is to train link prediction model, however, this method is not efficient as HGCN, shown in Figure
E EXPERIMENT DETAILS
E. TASK AND DATASET
We provide a detailed description/table of used datasets in Table and Table
1. Citation Networks. Cora, Citeseer and Pubmed Sen et al. (2008) are standard citation network benchmarks, where nodes represent papers, connected to each other via citations. We follow the standard splits Kipf & Welling (2016) with 20 nodes per class for training. 500 nodes for validation and 1000 nodes for test.
2. Disease propagation tree Chami et al.] (2019). This is tree networks simulating the SIR disease spreading model Anderson & May (1992), where the label is whether node was infected or not and the node features indicate the susceptibility to the disease. We use dataset splits of 20/10/600 660% for train/val/test set.
3. Airport. We take this dataset from Chami al. (2019). This is transductive dataset where nodes represent airports and edges represent the airline routes as from OpenFlights. Air- port contains 38188 nodes, each node has a 4 dimensional feature representing geographic information (longitude, latitude and altitude), and GDP of the country where the airport belongs to. For node classification, labels are chosen to be the population of the country where the airport belongs to. We use dataset splits of 524/524 nodes for val/test set.
4. Reddit. This is a much larger graph dataset built from Reddit posts, where the label the community, "subreddit", that post belongs to. Two nodes connected if the same user comments on both. We use a dataset split of /52K/24K/ /55K follows Hamilton et al. (2077) Chen et al. (2018), similarly, we evaluate HyLa inductively by following Wu al.
21

---

Under review as a conference paper at ICLR 2023
Table 5: Hyper-parameters for node classification.
Dataset
do
d1
K
Iri
lrz
# Epochs
Disease
16
100
1.0
0.05
0.0001
100
Airport
16
1000
0.01
0.5
0.1
100
Pubmed
16
100
0.1
0.5
0.001
200
Citeseer
16
500
1.0
0.1
0.001
100
Cora
16
100
1.0
0.1
0.01
100
Reddit
50
1000
2
0.5
0.1
0.001
100
Table 6: Hyper-parameters for text classification.
Transductive Setting
Inductive Setting
Dataset
dg
d1
lr
lr2
do
di
8
Ir
Ir2
R8
50
500
0.5
0.01
0.0001
50
500
0.5
0.001
0.0001
R52
50
500
0.5
0.1
0.0001
50
1000
0.5
0.008
0.0001
Ohsumed
50
500
0.5
0.01
0.0001
50
1000
0.1
0.001
0.0001
MR
30
500
0.5
0.1
0.0001
500
0.5
0.01
0.0001
(2019): we train on subgraph comprising only training nodes and test with the original graph.
E.2 TRAINING DETAILS.
We use HyLa together with SGC model softmax(A AXW), where the HyLa feature matrix X Raxds is derived from the hyperbolic embedding Z R.xxdo using Algorithm 1 Specifically, randomly sample constants of HyLa features X by sampling the boundary points uniformly from the boundary OB", eigenvalue constants from a zero-mean dekandard-deviattee Gaussian and biases b uniformly from [0, 2x). These constants remain fixed throughout training.
We use cross-entropy as the loss function and jointly optimize the low dimensional hyperbolic em- bedding Z and linear weight W simultaneously during training. Specifically, Riemannian SGD optimizer Bonnabel (2013) (of learning rate Iri) for Z and Adam Kingma & Ba (2014) optimizer (of learning rate Ir2) for W. RSGD naturally scales very large graph because the graph con- nectivity pattern is sufficiently sparse. We adopt carly-stopping
regularization. We tune the hyper-parameter via grid search over the parameter space. Each hyperbolic embedding initialized around the origin, by sampling each coordinate at random from [-10-3 100
E.3
We provide the detailed values of in Table 5 and Table respectivel. Particularly, fix K 2 for the text classification task and train the model for a maximum of 200 epochs without using any regularization (e.g. early stopping). Also note that in the transductive text classification setting, HyLa is used node level, hence the size of parameters will be proportional to the size of graph, in which case, do and dj can not be too large so as avoid OOM. In the inductive text classification setting, there is no such constraint as the dimension of lower level features is not very large itself. Please check the code for more details.
for node classification and text classification
F TIMING
We show the specific training timing statistics of different models on Pubmed dataset in Table 7 Particularly for HGCN model, in order to achieve the report performances. we follow the same training procedure using public code, which is divided into two stages: (1) a link prediction task on the dataset learn hyperbolic embeddings, and (2) use the pretrained embeddings train a ML.P classifier. Hence, we add the timing of both stages as the timing for HGCN.
22

---

Under review as a conference paper at ICLR 2023
Table 7: Training time on Pubmed.
Model
Timing (seconds)
SGC
0.37
GCN
1.25
GAT
12.52
HNN
2.41
HGCN
15.41
LGCN
10.93
SGL
3.51
23


Reviews:
[{"review_id": "ufU4TcljAtG", "reviewer": "Reviewer_Ue38", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a new method for utilizing hyperbolic geometry that avoids many of the issues with current models. \n\nMy understanding of it is as follows. Suppose we have $x_1, \\ldots, x_n$ embedded into some hyperbolic space and some kernel map $k(x_i,x_j)$ that **only** depends on the hyperbolic distance between the data, then we can define a random features type map (using the eigenfunctions of the Laplace Beltrami Operator on the manifold) to get features $\\phi(x_i) \\in \\mathbb{R}^d$ such that $\\mathbb{E}[\\phi(x_i)^T \\phi(x_j)] = k(x_i,x_j)$. \n\nThe idea then is to use this features with traditional neural networks (instead of hyperbolic neural networks). The paper proves that any such kernel can be estimated in an unbiased banner and implements one such kernel to show improvements in many cases over both purely hyperbolic and purely euclidean methods. ", "summary_of_the_review": "In summary I think the paper presents a fundamental extension of the random features model of hyperbolic space. It then presents a very interesting way in which this can be used. \n\nI think the paper is novel, and interesting. ", "strength_and_weaknesses": "**Strengths**\n---\n\n1) The Random Features Model is very important model for Euclidean data and the extension to the Hyperbolic version seems fundamental and interesting. \n2) The idea to then get Euclidean features that represent hyperbolic geometry (in some way) in this manner is very novel. \n3) The theory results are compelling and general to show that this can be used in a wide variety of settings. \n\n**Weaknesses**\n---\n\n1) Since the method for embedding the data into hyperbolic space is crucial to the method, the paper is missing a discussion on how to obtain this embedding. On page 6 it says ``A low dimensional hyperbolic embedding $z \\in \\mathcal{B}^{d_0}$ is initialized for each node to derive hyperbolic embeddings $Z \\in \\mathbb{R}^{n\\times d_0}$ for all nodes in the graph''. However, this does not tell us how the embeddings was obtained. I think this is a crucial detail. Further, it is not clear, whether $Z$ is now a parameter is that learned during the neural network training. Based on the motivation of the paper to avoid hyperbolic gradient based learning, I do not think this is the case. \n\nHence I think some discussion of how the method learns the embeddings and a discussion (such as Nickel and Kiela NeurIPS 2017, Nickel and Kiela ICML 2018, Sala, De Sa, Gu and Re ICML 2018, Sonthalia and Gilbert NeurIPS 2020) about embedding data into hyperbolic space would help. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RxKrbk-6bS", "reviewer": "Reviewer_iAHJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors suggest a simpler method: learn a hyperbolic embedding of the input, map it once to Euclidean space using a mapping that encodes geometric priors by respecting the isometries of hyperbolic space, and end with a standard Euclidean network.", "summary_of_the_review": "In this paper, the authors propose a straightforward approach, learn a hyperbolic embedding of the input, then map it once to Euclidean space using a mapping that preserves the isometries of hyperbolic space while encoding geometric priors, and finally, finish with a standard Euclidean network. However, I am a little concerned about the experimental results.", "strength_and_weaknesses": "The idea is quite interesting, but the experimental results are strange, especially for the baselines in table 1 which are much lower than their real performance. \nFor scalability, the author only experiments on some small datasets.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FB2vI7UqMv", "reviewer": "Reviewer_BVuW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper outline a method to use hyperbolic spaces in a graph neural network. The approach mainly relies on the computation of Laplacian Eigenfunctions: after embedding the graph nodes in some space, they are mapped via a kernel transformation to their hyperbolic features (i.e., Hyperbolic Laplacian eigenfunctions), and lastly, a standard euclidean network can be used. The method shows comparable results with the SoTA and a performance gain over previous hyperbolic networks.", "summary_of_the_review": "I find the proposed methodology interesting and in line with recent research directions. As a non-expert, I would prefer better insights and explanations to fully appreciate the impact of this work, but I think the highlighted weaknesses can be addressed before the submission. Looking forward to the rebuttal to clarify my doubts.", "strength_and_weaknesses": "STRENGTH\n=======\n1) SIMPLICITY: While I do not fully understand some parts of the method, the overall principles seem straightforward. I expect that with some better details about the implementation, the method can be easily reproducible. Adopting Laplacian features as input of a network is a well-known approach to inject non-euclidean knowledge inside the network, but I am not aware of other works that compute such features in hyperbolic spaces.\n\n2) EXPERIMENTS: The method is tested on different kinds of graphs from different families and structures. The results suggest that in the worst case, the method can be applied without harm, while in many cases, it improves.\n\nWEAKNESSES\n=======\n1) PRESENTATION: as a non-expert in hyperbolic spaces, I had a hard time understanding exactly some parts of the method. For example, it is not clear to me how \"a low dimensional hyperbolic embedding is initialized for each node\". I think a plain explaination might help the reader and increase the usability of the paper methodology\n\n2) APPLICABILITY AND LIMITATIONS: It is not completely clear to me if the method can have an impact in different applications from node classification since all the experiments are performed in this context. Exploiting isometric invariance has been widely popular in contexts like 3D meshes to compute correspondence between two objects. I wonder if the same holds here. Also, while the method indeed improves from euclidean networks, it comes with non-trivial computational costs (i.e., from Figure 5, SGC is 10x times faster). Finally, in Conclusions Section, it is mentioned that in future, a direction is to adopt \"more numerically stable representations of the hyperbolic embeddings to avoid potential 'NaN problems'\". I would like to know more about these issues and where they arise.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster