Node-Specific Space Selection via Localized Geometric Hyperbolicity in
  Graph Neural Networks
Many graph neural networks have been developed to learn graph representations
in either Euclidean or hyperbolic space, with all nodes' representations
embedded in a single space. However, a graph can have hyperbolic and Euclidean
geometries at different regions of the graph. Thus, it is sub-optimal to
indifferently embed an entire graph into a single space. In this paper, we
explore and analyze two notions of local hyperbolicity, describing the
underlying local geometry: geometric (Gromov) and model-based, to determine the
preferred space of embedding for each node. The two hyperbolicities'
distributions are aligned using the Wasserstein metric such that the calculated
geometric hyperbolicity guides the choice of the learned model hyperbolicity.
As such our model Joint Space Graph Neural Network (JSGNN) can leverage both
Euclidean and hyperbolic spaces during learning by allowing node-specific
geometry space selection. We evaluate our model on both node classification and
link prediction tasks and observe promising performance compared to baseline
models.
See Hian Lee, Feng Ji, Wee Peng Tay
# Node-Specific Space Selection via Localized Geometric Hyperbolicity in Graph Neural Networks

###### Abstract

Many graph neural networks have been developed to learn graph representations in either Euclidean or hyperbolic space, with all nodes' representations embedded in a single space. However, a graph can have hyperbolic and Euclidean geometries at different regions of the graph. Thus, it is sub-optimal to indifferently embed an entire graph into a single space. In this paper, we explore and analyze two notions of local hyperbolicity, describing the underlying local geometry: geometric (Gromov) and model-based, to determine the preferred space of embedding for each node. The two hyperbolicities' distributions are aligned using the Wasserstein metric such that the calculated geometric hyperbolicity guides the choice of the learned model hyperbolicity. As such our model Joint Space Graph Neural Network (JSGNN) can leverage both Euclidean and hyperbolic spaces during learning by allowing node-specific geometry space selection. We evaluate our model on both node classification and link prediction tasks and observe promising performance compared to baseline models.

 Graph neural networks, hyperbolic embedding, graph representation learning, joint space learning.

## I Introduction

Graph neural networks (GNNs) are neural networks that learn from graph-structured data. Many works such as Graph Convolutional Network (GCN) [1], Graph Attention Network (GAT) [2], GraphSAGE [3] and their variants operate on the Euclidean space and have been applied in many areas such as recommender systems [4, 5], chemistry [6] and financial systems [7]. Despite their remarkable accomplishments, their performances are still limited by the representation ability of Euclidean space. They are unable to achieve the best performance in situations when the data exhibit non-Euclidean characteristics such as scale-free, tree-like, or hierarchical structures [8].

As such, hyperbolic spaces have gained traction in research as they have been proven to better embed tree-like, hierarchical structures compared to the Euclidean geometry [9, 10]. Intuitively, encoding non-Euclidean structures such as trees in the Euclidean space would result in more considerable distortion since the number of nodes in a tree increases exponentially with the depth of the tree while the Euclidean space only grows polynomially [11]. In such cases, the hyperbolic geometry serves as an alternative to learning those structures with comparably smaller distortion as the hyperbolic space has the exponential growth property [8]. As such, hyperbolic versions of GNNs such as HGCN [12], HGNN [13], HGAT [14] and LGCN [15] have been proposed.

Nevertheless, real-world graphs are often complex. They are neither solely made up of Euclidean nor non-Euclidean structures alone but a mixture of geometrical structures. Consider a localized version of geometric hyperbolicity, a concept from geometry group theory measuring how tree-like the underlying space is for each node in the graph (refer to Section III-A for more details). We observe a mixture of local geometric hyperbolicity values in most of the benchmark datasets we employ for our experiments as seen in Fig. 2. This implies that the graphs contain a mixture of geometries and thus, it is not ideal to embed the graphs into a single geometry space, regardless of Euclidean or hyperbolic as it inevitably leads to undesired structural inductive biases and distortions [8].

Taking a graph containing both lattice-like and tree-like structures as an example, Fig. 1c and Fig. 1f shows that 15 of the blue-colored nodes in the tree structure are calculated to have 2-hop local geometric hyperbolicity value of zero, while 12 of the purple nodes have a value of one and the other 3 purple nodes (at the center of the lattice) have a value of two (the smaller the hyperbolicity value, the more hyperbolic). This localized metric can therefore serve as an indication during learning on which of the two spaces is more suitable to embed the respective nodes.

Here we address this mixture of geometry in a graph and propose Joint Space Graph Neural Network (JSGNN) that performs learning on a joint space consisting of both Euclidean and hyperbolic geometries. To achieve this, we first update all the node features in both Euclidean and hyperbolic spaces independently, giving rise to two sets of updated node features. Then, we employ exponential and logarithmic maps to bridge the two spaces and an attention mechanism is used as a form of model hyperbolicity, taking into account the underlying structure around each node and the corresponding node features. The learned model hyperbolicity is guided by geometric hyperbolicity and is used to "softly decide" the most suitable embedding space for each node and to reduce the two sets of updated features into only one set. Ideally, a node should be either hyperbolic or Euclidean and not both simultaneously, thus, we also introduce an additional loss term to achieve this non-uniform characteristic.

To the best of our knowledge, the closest work to ours is Geometry Interaction Learning (GIL) [11] which exploits Euclidean and hyperbolic spaces through a dual feature interaction learning mechanism and a probability assembling module. GIL has two branches where a message-passing procedure is performed in Euclidean and hyperbolic spaces simultaneously. Dual feature interaction learning is where the node features
in each of the spaces are enhanced based upon the updated features on the other space and their distance similarity. The larger the distance between the different spatial embeddings, the larger the portion of features from the other space is summed to itself as seen in Fig. 3. Meanwhile, probability assembling refers to learning node-level weights to determine which of the learned geometric embeddings is more critical. A weighted sum of the classification probabilities from the two spaces yields the final result.

Our approach differs from [11] in some key aspects. Firstly, we leverage the distribution of geometric hyperbolicity to guide our model to learn to decide for each node to be either better embedded in a Euclidean or hyperbolic space instead of performing feature interaction learning. This is done by aligning the distribution of the learned model hyperbolicity and geometric hyperbolicity using the Wasserstein distance. Our motivation is that if a node can be best embedded in one of the two spaces and encoding it in another space other than the optimal one would result in comparably larger distortion. Minimal information would be present in the sub-optimal space to help "enhance" the representation in the better space. Hence, promoting feature interaction could possibly introduce more noise to the branches. The ideal situation is then to learn normalized selection weights that are non-uniform for each node so that we select for each node a single, comparably better space's output embedding. To achieve this, we introduce an additional loss term that promotes non-uniformity. Lastly, we do not require probability assembling since we only have one set of output features at the end of the selection process.

## II Background

In this section, we give a brief overview of hyperbolic geometry that will be used in the paper. Readers are referred to [16] for further details. Moreover, we review GAT and its hyperbolic version.

### _Hyperbolic geometry_

A hyperbolic space is a non-Euclidean space with constant negative curvature. There are different but equivalent models to describe the same hyperbolic geometry. In this paper, we work with the Poincare ball model, in which all points are inside a ball. The hyperbolic space with constant negative curvature \(c\) is denoted by \((\mathbb{D}_{c}^{n},g_{\mathbf{x}}^{c})\). It consists of the \(n\)-dimensional hyperbolic manifold \(\mathbb{D}_{c}^{n}=\{\mathbf{x}\in\mathbb{R}^{n}:c\|\mathbf{x}\|<1\}\) with the Riemannian metric \(g_{\mathbf{x}}^{c}=(\lambda_{\mathbf{x}}^{c})^{2}g^{E}\), where \(\lambda_{\mathbf{x}}^{c}=2/(1-c\|\mathbf{x}\|^{2})\) and \(g^{E}=\mathbf{I}_{n}\) is the Euclidean metric.

At each \(\mathbf{x}\in\mathbb{D}_{c}^{n}\), there is a tangent space \(\mathcal{T}_{\mathbf{x}}\mathbb{D}_{c}^{n}\), which can be viewed as the first-order approximation of the hyperbolic manifold at \(\mathbf{x}\)[9]. The tangent space is then useful to perform Euclidean operations that we are familiar with but are undefined in hyperbolic spaces. A hyperbolic space and the tangent space at a point are connected through the exponential map \(\exp_{\mathbf{x}}^{c}:\mathcal{T}_{\mathbf{x}}\mathbb{D}_{c}^{n}\to\mathbb{D}_ {c}^{n}\) and logarithmic map \(\log_{\mathbf{x}}^{c}:\mathbb{D}_{c}^{n}\to\mathcal{T}_{\mathbf{x}}\mathbb{D} _{c}^{n}\), specifically defined as follows:

\[\exp_{\mathbf{x}}^{c}(\mathbf{v}) =\mathbf{x}\oplus_{c}\Big{(}\tanh\!\left(\sqrt{c}\frac{\lambda_{ \mathbf{x}}^{c}\|\mathbf{v}\|}{2}\right)\!\frac{\mathbf{v}}{\sqrt{c}\|\mathbf{ v}\|}\Big{)}, \tag{1}\] \[\log_{\mathbf{x}}^{c}(\mathbf{y}) =\frac{2}{\sqrt{c}\lambda_{\mathbf{x}}^{c}}\tanh^{-1}(\sqrt{c} \|-\mathbf{x}\oplus_{c}\mathbf{y}\|)\frac{-\mathbf{x}\oplus_{c}\mathbf{y}\,}{ \|-\mathbf{x}\oplus_{c}\mathbf{y}\|}, \tag{2}\]

where \(\mathbf{x},\mathbf{y}\in\mathbb{D}_{c}^{n},\mathbf{v}\in\mathcal{T}_{\mathbf{ x}}\mathbb{D}_{c}^{n}\) and \(\oplus_{c}\) is the Mobius addition. For convenience, we write \(\mathbb{D}\) for \(\mathbb{D}_{c}^{n}\) if no confusion arises.

A salient feature of hyperbolic geometry is that it is "thinner" than Euclidean geometry. Visually, more points can be squeezed in a hyperbolic subspace having the same shape as its Euclidean counterpart, due to the different metrics in the two spaces. We discuss the graph version in Section III-A below.

### _Graph attention and message passing_

Consider a graph \(G=(V,E)\), where \(V\) is the set of vertices, \(E\) is the set of edges, and each node in \(V\) is associated with

Fig. 1: Example graphs. (a) Lattice-like graph. (b) A tree. (c) A combined graph containing both lattice and tree structure. (d-f) The histograms reflect the geometric hyperbolicity in the respective graphs.
a node feature \(h_{v}\). Recall that GAT is a GNN that updates node representations using message passing by updating edge weights concurrently. Specifically, for one layer of GAT [2], the node features are updated as follows:

\[h_{v}^{{}^{\prime}} =\sigma\Big{(}\sum_{j\in N(v)}\alpha_{vj}\textbf{W}h_{j}\Big{)}, \tag{3}\] \[\alpha_{vj} =\frac{\exp(e_{vj})}{\sum_{k\in N(v)}\exp(e_{rk})},\] (4) \[e_{vj} =\mathrm{LeakyReLU}(\textbf{a}^{\prime}[\textbf{W}h_{v}\parallel \textbf{W}h_{j}]), \tag{5}\]

where \(\parallel\) denotes the concatenation operation, \(\sigma\) denotes an activation function, **a** represents the learnable attention vector, **W** is the weight matrix for a linear transformation and \(\alpha\) denotes the normalized attention scores.

This model has been proven to be successful in many graph-related machine learning tasks.

### _Hyperbolic attention model_

To derive a hyperbolic version of GAT, we adopt the following strategy. We perform feature aggregation in the tangent spaces of points in the hyperbolic space. Features are mapped between hyperbolic space and tangent spaces using the pair of exponential and logarithmic functions: \(\exp_{\textbf{x}}^{c}\) and \(\log_{\textbf{x}}^{c}\).

With this, we denote Euclidean features as \(h_{\mathbb{R}}\) and hyperbolic features as \(h_{\mathbb{D}}\). Then one layer of message propagation in the hyperbolic GAT is as follows [11]:

\[h_{v,\mathbb{D}}^{{}^{\prime}}=\sigma\Big{(}\sum_{j\in N(v)} \alpha_{vj}\log_{\textbf{o}}^{c}(\textbf{W}\otimes_{c}h_{j,\mathbb{D}}\oplus_ {c}\textbf{b})\Big{)}, \tag{6}\] \[e_{vj}=\mathrm{LeakyReLU}\Big{(}\textbf{a}^{\prime}\Big{[}\hat {h}_{v}\parallel\hat{h}_{j}\Big{]}\times d_{\mathbb{D}}(h_{v,\mathbb{D}},h_{j, \mathbb{D}})\Big{)},\] (7) \[d_{\mathbb{D}}(h_{v,\mathbb{D}},h_{j,\mathbb{D}})=\frac{2}{\sqrt {c}}\tanh^{-1}(\sqrt{c}\|-h_{v,\mathbb{D}}\oplus_{c}h_{j,\mathbb{D}}\|),\] (8) \[\alpha_{vj}=\mathrm{softmax}_{j}(e_{vj}), \tag{9}\]

where \(d_{\mathbb{D}}\) is the normalized hyperbolic distance, \(\hat{h}_{j}=\log_{\textbf{o}}^{c}(\textbf{W}\otimes_{c}h_{j,\mathbb{D}})\), while \(\otimes_{c}\) and \(\oplus_{c}\) represent the Mobius matrix multiplication and addition, respectively.

## III Joint Space Learning

In this section, we propose our joint space learning model. The model relies on comparing two different notions of hyperbolicity: geometric hyperbolicity and model hyperbolicity. We start by introducing the former, which also serves as the motivation for the design of our GNN model.

### _Local geometry and geometric hyperbolicity_

Gromov's \(\delta\)-hyperbolicity is a mathematical notion from geometry group theory to measure how tree-like a metric space is in terms of metric or distance structure [17, 12]. The precise definition is given as follows.

**Definition 1** (Gromov 4-point \(\delta\)-hyperbolicity [18] p.410).: _For a metric space \(X\) with metric \(d(\cdot,\cdot)\), it is \(\delta\)-hyperbolic, where \(\delta\geq 0\) if the four-point condition holds:_

\[d(x,y)+d(z,t)\leq \tag{10}\] \[\max\{d(x,z)+d(y,t),d(z,y)+d(x,t)\}+2\delta,\]

_for any \(x,y,z,t\in X\). \(X\) is hyperbolic if it is \(\delta\)-hyperbolic for some \(\delta\geq 0\)._

This condition of \(\delta\)-hyperbolicity is equivalent to the Gromov thin triangle condition. For example, any tree is (0-)hyperbolic, and \(\mathbb{R}^{n}\), where \(n\geq 2\) is not hyperbolic. However, if \(X\) is a compact metric space, then \(X\) is always \(\delta\)-hyperbolic for some \(\delta\) large enough such as \(\delta=\mathrm{diameter}(X)\). Therefore, it is insufficient to just label \(X\) as hyperbolic or not. We want to quantify hyperbolicity such that a space with smaller hyperbolicity resembles more of a tree.

Inspired by the four-point condition, we define the \(\infty\)-version and the \(1\)-version of hyperbolicity as follows.

Fig. 2: Distributions of geometric hyperbolicity for all datasets, obtained by computing \(\delta_{G_{\alpha},\infty}\) on each nodes’ 2-hop subgraph.
**Definition 2**.: _For a compact metric space \(X\) and \(x,y,z,t\in X\), denote \(\inf_{\delta\geq 0}\{(10)\) holds for \(x,y,z,t\}\) by \(\tau_{X}(x,y,z,t)\). Define_

\[\delta_{X,\infty}=\sup_{x,y,z,t\in X}\tau_{X}(x,y,z,t),\] \[\delta_{X,1}=\mathbb{E}_{x,y,z,t\sim\mathrm{Unif}(X^{4})}[\tau_{ X}(x,y,z,t)],\]

_where \(\mathrm{Unif}\) represents the uniform distribution._

In order for these invariants to be useful for graphs, we require them to be almost identical for graphs with similar structures. We shall see that this is indeed the case. Before stating the result, we need a few more concepts.

Let \(\mathcal{G}\) be the space of weighted, undirected simple graphs. Though for most experiments, the given graphs are unweighted. However, aggregation mechanisms such as attention essentially generate weights for the edges. Therefore, for both theoretical and practical reasons, it makes sense to expand the graph domain to include weighted graphs.

For each \(G=(V,E)\in\mathcal{G}\), it has a canonical path metric \(d_{G}\), and \(d_{G}\) makes \(G\) into a metric space including non-vertex points on the edges. For \(\epsilon>0\), there is the subspace \(\mathcal{G}_{\epsilon}\) of \(\mathcal{G}\) consisting of graphs whose edge weights are greater than \(\epsilon\).

On the other hand, there is a metric on the space \(\mathcal{G}\) and \(\mathcal{G}_{\epsilon}\), called the Gromov-Hausdorff metric ([18] p.72). To define it, we first introduce the Hausdorff distance. Let \(X\) and \(Y\) be two subsets of a metric space \((M,d)\). Then the Hausdorff distance \(d_{H}(X,Y)\) between \(X\) and \(Y\) is

\[d_{H}(X,Y)=\max\{\sup_{x\in X}d(x,Y),\sup_{y\in Y}d(X,y)\},\]

where \(d(x,Y)=\inf_{y\in Y}d(x,y)\), \(d(X,y)=\inf_{x\in X}d(x,y)\). The Hausdorff distance measures in the worst case, how far away a point in \(X\) is away from \(Y\) and vice versa.

In general, we want to also compare spaces that do not a priori belong to a common ambient space. For this, if \(X,Y\) are two compact metric spaces, then their Gromov-Hausdorff distance \(d_{GH}(X,Y)\) is defined as the infimum of all numbers \(d_{H}(f(X),g(Y))\) for all metric spaces \(M\) and all isometric embeddings \(f:X\to M,g:Y\to M\). Intuitively, the Gromov-Hausdorff distance measures how far \(X\) and \(Y\) are from being isometric. The following is proved in the Appendix.

**Proposition 1**.: _Suppose \(\mathcal{G}\) and its subspaces have the Gromov-Hausdorff metric. Then \(\delta_{G,\infty}\) is Lipschitz continuous w.r.t. \(G\in\mathcal{G}\) and \(\delta_{G,1}\) is continuous w.r.t. \(G\in\mathcal{G}_{\epsilon}\) for any \(\epsilon>0\)._

Consider a graph \(G\). We fix either \(\delta_{G,\infty}\) or \(\delta_{G,1}\) as a measure of hyperbolicity, and apply to each local neighborhood of \(G\). To be more precise, it is studied [19, 20] that many popular GNN models have a shallow structure. It is customary to have a \(2\)-layer network possibly due to oversmoothing [21, 22, 23] and oversquashing [24] phenomena. In such models, each node only aggregates information in a small neighborhood.

Therefore, if we fix a small \(k\) and let \(G_{v}\) be the subgraph of the \(k\)-hop neighborhood of \(v\in V\), then it is more appropriate to study the hyperbolicity \(\delta_{v}\), either \(\delta_{G_{v},\infty}\) or \(\delta_{G_{v},1}\), of \(G_{v}\). For our experiments, the former is utilized. We call \(\delta_{v}\) the _geometric hyperbolicity_ at node \(v\). The collection \(\Delta_{V}=\{\delta_{v}:v\in V\}\) allows us to obtain an empirical distribution \(\mu_{G}\) of geometric hyperbolicity on the sample space \(\mathbb{R}_{\geq 0}\).

For instance, we can build histograms to acquire the distributions as observed in Fig. 2. We see, for example, for Cora, a substantial number of nodes have small (local) hyperbolicity, in contrast with many works that claim Cora to be relatively Euclidean due to its high global hyperbolicity value [12, 25]. On the other hand, Airport is argued to be globally hyperbolic, but a large proportion of nodes has large local hyperbolicity. However, this is not a contradiction as we are considering the local structures of the graph. We call \(\mu_{G}\) the _distribution of geometric hyperbolicity_. It depends only on \(G\) and \(k\).

### _Space selection and model hyperbolicity_

In this section, we describe the backbone of our model and introduce the notion of model hyperbolicity. Our model consists of two branches, one using Euclidean geometry and the other using hyperbolic geometry. For the Euclidean part, we use GAT for message propagation, while for the hyperbolic part, we employ HGAT in Section II-C.

After the respective message propagation, we would have two sets of updated node embeddings, the Euclidean embedding \(Z_{\mathbb{R}}\) and the hyperbolic embedding \(Z_{\mathbb{D}}\). The two sets of embeddings are combined into a single embedding \(Z=\{z_{v},v\in V\}\) through an attention mechanism that serves as a space selection procedure. The attention mechanism is performed in a Euclidean space. Thus, the hyperbolic embeddings are first mapped into the tangent space using the logarithmic map. Mathematically, the normalized attention score indicating whether a node should be embedded in the hyperbolic space \(\beta_{v,\mathbb{D}}\) or Euclidean space \(\beta_{v,\mathbb{R}}\) is as follows:

\[w_{v,\mathbb{R}} =\mathbf{q}^{\intercal}\tanh(\mathbf{M}z_{v,\mathbb{R}}+\mathbf{ b}), \tag{11}\] \[w_{v,\mathbb{D}} =\mathbf{q}^{\intercal}\tanh(\mathbf{M}\log_{\mathbf{v}}^{ \mathrm{c}}(z_{v,\mathbb{D}})+\mathbf{b}),\] (12) \[\beta_{v,\mathbb{R}} =\frac{\exp(w_{v,\mathbb{R}})}{\exp(w_{v,\mathbb{R}})+\exp(w_{v, \mathbb{D}})},\] (13) \[\beta_{v,\mathbb{D}} =\frac{\exp(w_{v,\mathbb{D}})}{\exp(w_{v,\mathbb{R}})+\exp(w_{v, \mathbb{D}})}, \tag{14}\]

where \(\mathbf{q}\) refers to the learnable space selection attention vector, \(\mathbf{M}\) is a learnable weight matrix, \(\mathbf{b}\) denotes a learnable bias and \(\beta_{v,\mathbb{D}}+\beta_{v,\mathbb{R}}=1\), for all \(v\in V\). The two sets of space-specific node embeddings can then be combined via a convex combination using the learned weights as follows:

\[z_{v}=\beta_{v,\mathbb{R}}z_{v,\mathbb{R}}+\beta_{v,\mathbb{D}}\log_{\mathbf{v }}^{\mathrm{c}}(z_{v,\mathbb{D}}),\forall\,v\in V. \tag{15}\]

This gives one layer of the model architecture of JSGNN, as illustrated in Fig. 3.

The parameter \(\beta_{v,\mathbb{R}},v\in V\) controls whether the combined output, consisting of both hyperbolic and Euclidean components, should rely more on the hyperbolic components or not. We call \(\beta_{v,\mathbb{R}}\) the _model hyperbolicity_ at the node \(v\). The notion of model hyperbolicity depends on node features as well as the explicit GNN model. Similar to geometric hyperbolicity, the collection \(\Gamma_{G}=\{\beta_{v,\mathbb{R}}:\,v\in V\}\) gives rise to an empirical distribution \(\nu_{G}\) on \([0,1]\). We call \(\nu_{G}\) the _distribution of model hyperbolicity_.
To motivate the next subsection, from (15), we notice that the output depends smoothly on \(\beta_{v,\mathbb{R}}\). If we wish to have a similar output for nodes with similar neighborhood structures and features, we want their selection weights to have similar values. On the other hand, we have seen (cf. Proposition 1) that geometric hyperbolicities, which can be computed given \(G\), are similar for nodes with similar neighborhoods. It suggests that we may use geometric hyperbolicities to "guide" the choice of model hyperbolicities.

### _Model hyperbolicity vs. geometric hyperbolicity_

We have introduced geometric and model hyperbolicities in the previous subsections. In this subsection, we explore the interconnections between these two notions.

Let \(\Theta\) be the parameters of a proposed GNN model. We assume that the model has the pipeline shown in Fig. 4. Given node features \(\{h_{v},v\in V\}\) and model parameters \(\Theta\), the model generates (embedding) features \(\{z_{v},v\in V\}\) and selection weights or model hyperbolicity \(\{\beta_{v,\mathbb{R}},v\in V\}\) in the intermediate stage. For each \(v\in V\), there is a combination function \(\phi_{v}\) such that the final output \(\{\hat{y}_{v},v\in V\}\) satisfies \(\hat{y}_{v}=\phi_{v}(z_{v},\beta_{v})\).

In principle, we want to compare \(\{\beta_{v,\mathbb{R}},v\in V\}\) and \(\{\delta_{v},v\in V\}\) so that the geometric hyperbolicity guides the choice of model hyperbolicity. However, comparing pairwise \(\beta_{v}\) and \(\delta_{v}\) for each \(v\in V\) may lead to overfitting. An alternative is to compare their respective distributions \(\nu_{G}\) and \(\mu_{G}\), or even coarser statistics (e.g., mean) of \(\nu_{G}\) and \(\mu_{G}\) (cf. Fig. 5). The latter may lead to underfitting. We perform an ablation study on the different comparison methods in Section IV-E.

We advocate choosing the middle ground by comparing the distributions \(\mu_{G}\) and \(\nu_{G}\). The former can be computed readily as long as the ambient graph \(G\) is given, while the latter is a part of the model that plays a crucial role in feature aggregation at each node. Therefore, \(\mu_{G}\) can be pre-determined but not \(\nu_{G}\). We propose to use the known \(\mu_{G}\) to constrain \(\nu_{G}\) and thus the model parameters \(\Theta\). A widely used comparison tool is the Wasserstein metric.

**Definition 3** (Wasserstein distance).: _Given \(p\geq 1\), the \(p\)-Wasserstein distance metric [26] measures the difference between two different probability distributions [27]. Let

Fig. 4: The model pipeline is shown in the (blue) dashed box, while the geometric hyperbolicity can be computed independently of the model.

Fig. 5: Different ways of comparing geometric and model hyperbolicities.

Fig. 3: Comparison between JSGNN and GIL [11] in leveraging Euclidean and hyperbolic spaces. (a) Soft space selection mechanism of JSGNN where trainable selection weights \(\beta_{v,\mathbb{R}},\beta_{v,\mathbb{D}}\) are non-uniform, effectively selecting the better of the two spaces considered. (b) Feature interaction mechanism of GIL where \(\zeta,\zeta^{\prime}\in\mathbb{R}\) are trainable weights and \(d_{\mathbb{D}},d_{\mathbb{R}}\) are the hyperbolic distance (cf. (8)) and Euclidean distance respectively. The node embeddings of both spaces in GIL are adjusted based on distance, potentially introducing more noise to the branches as there is minimal information in the sub-optimal space to “enhance” the representation in the better space.
\(\Pi(\nu_{G},\mu_{G})\) be the set of all joint distributions for random variables \(x\) and \(y\) where \(x\thicksim\nu_{G}\) and \(y\thicksim\mu_{G}\). Then the \(p\)-Wasserstein distance between \(\mu_{G}\) and \(\nu_{G}\) is as follows:_

\[W_{p}(\nu_{G},\mu_{G})=\left\{\inf_{\gamma\in\Pi(\nu_{G},\mu_{G})}\mathbb{E}_{( x,y)\thicksim\gamma}\|x-y\|^{p}\right\}^{1/p}. \tag{16}\]

To compute the Wasserstein distance exactly is costly given that the solution of an optimal transport problem is required [28, 29]. However, for one-dimensional distributions, the \(p\)-Wasserstein distance can be computed by ordering the _samples_ from the two distributions and then computing the average \(p\)-distance between the ordered samples [28, 30].

In ideal circumstances, considering the distributions do not lose much information. We first notice that for both \(\beta_{v,\mathbb{R}}\) and \(\delta_{v}\), a smaller value means more hyperbolic in an appropriate sense. Suppose \(\beta_{v,\mathbb{R}}\) is increasing w.r.t. \(\delta_{v}\), i.e., \(\delta_{v}\leq\delta_{u}\) implies that \(\beta_{v,\mathbb{R}}\leq\beta_{u,\mathbb{R}}\). Then, \(W_{2}(\mu_{G},\nu_{G})=\sqrt{\frac{1}{|\mathcal{V}|}\sum_{v\in V}|\beta_{v, \mathbb{R}}-\delta_{v}|^{2}}\).

### _Non-uniformity of selection weights_

A node is considered to be more suitable to be embedded in the hyperbolic space when \(\beta_{v,\mathbb{D}}>\beta_{v,\mathbb{R}}\). Meanwhile when \(\beta_{v,\mathbb{D}}\leq\beta_{v,\mathbb{R}}\), the node is considered to be Euclidean. Nevertheless, to align with our motivation that each node can be better embedded in one of the two spaces and the less suitable space would result in distortion in representation, we require JSGNN to learn non-uniform attention weights, meaning that each pair of attention weights \((\beta_{v,\mathbb{D}},\beta_{v,\mathbb{R}})\) should significantly deviate from the uniform distribution. This is because soft selection without a non-uniformity constraint may result in the assignment of nodes to be partially Euclidean and partially hyperbolic with \(\beta_{v,\mathbb{R}}\approx\beta_{v,\mathbb{D}}\approx 0.5\). Hence, we include an additional component to the standard loss function encouraging non-uniform learned weights as follows:

\[L_{\text{nu}}=-\frac{1}{|V|}\sum_{v\in V}\bigl{(}\beta_{v,\mathbb{R}}^{2}+ \beta_{v,\mathbb{D}}^{2}\bigr{)}. \tag{17}\]

Since \(-1\leq-(\beta_{v,\mathbb{R}}^{2}+\beta_{v,\mathbb{D}}^{2})\leq-0.5\) and \(\beta_{v,\mathbb{R}}+\beta_{v,\mathbb{D}}=1\), minimizing the term would favor non-uniform attention weights for each node.

In summary, we may combine hyperbolicity matching discussed in Section III-C and the non-uniformity loss to form the loss function to optimize JSGNN.

\[L_{\text{overall}}=L_{\text{task}}+\omega_{\text{nu}}L_{\text{nu}}+\omega_{ \text{was}}W_{2}(\nu_{G},\mu_{G}), \tag{18}\]

where \(L_{\text{task}}\) is the task-specific loss, while \(\omega_{\text{nu}}\) and \(\omega_{\text{was}}\) are balancing factors. For the node classification task, \(L_{\text{task}}\) refers to the cross-entropy loss over all labeled nodes while for link prediction, it refers to the cross-entropy loss with negative sampling. This completes the description of the JSGNN model.

We speculate that the non-uniform component \(L_{\text{nu}}\) should push the model hyperboliciities towards the two extremes \(0\) and \(1\). On the other hand, as we have seen in Section III-C, to compute \(W_{2}(\nu_{G},\mu_{G})\), we need to order \((\delta_{v})_{v\in V}\), \((\beta_{v,\mathbb{R}})_{v\in V}\) respectively, and compute their pairwise differences. Therefore, \(W_{2}(\nu_{G},\mu_{G})\) aligns the shapes of \(\nu_{G}\) and \(\mu_{G}\).

## IV Experiments

In this section, we evaluate JSGNN on node classification (NC) and link prediction (LP) tasks against seven baselines.

### _Datasets_

A total of seven benchmark datasets are employed for both NC and LP. Specifically, three citation datasets: Cora, Citeseer, Pubmed; a flight network: Airport; a disease propagation tree: Disease; an Amazon co-purchase graph dataset: Photo; and a coauthor dataset: CS. The statistics of the datasets are as shown in Table I.

### _Baselines and settings_

We compare against three Euclidean methods GCN [1], GraphSAGE [3] and GAT [2] and four hyperbolic models HGCN [12], HGNN [13], HGAT [14] and LGCN [15]. We also consider GIL [11], which similar to JSGNN, leverages both hyperbolic and Euclidean spaces.

For all models, the hidden units are set to 16. We set the early stopping patience to 100 epochs with a maximum limit of 1000 epochs. The hyperparameter settings for the baselines are the same as [11] if given. The only difference is that the hyperparameter _h-drop_ for GIL in [11] (which determines the dropout to the weight associated with the hyperbolic space embedding) is set to 0 for all datasets as setting a large value essentially explicitly chooses one single space. Else, the hyperparameters are chosen to yield the best performance. For JSGNN, we perform a grid search on the following search spaces: Learning rate: [0.01, 0.005]; Dropout probability: [0.0, 0.1, 0.5, 0.6]; Number of layers: [1, 2, 3]; \(\omega_{\text{nu}}\) and \(\omega_{\text{was}}\): [1.0, 0.5, 0.2, 0.1, 0.01, 0.005]; **q** (cf. (11)): [16, 32, 64]. The Wasserstein-\(2\) distance is employed in all variants of JSGNN.

### _Node classification_

For the node classification task, each of the nodes in a dataset belongs to one of the \(C\) classes in the dataset. With the final set of node representations, we aim to predict the labels of nodes that are in the testing set.

To test the performance of each model under both semi-supervised and fully-supervised settings, two data splits are used in the node classification task for the Cora, Citeseer and Pubmed datasets. In the first split, we followed the standard split for semi-supervised settings used in [1, 2, 3, 11, 22,
[31, 32, 33, 34]. The train set consists of 20 train examples per class while the validation set and test set consist of 500 samples and 1,000 samples, respectively.1 Meanwhile, in the second split, all labels are utilized and the percentages of training, validation, and test sets are set as 60/20/20%. For the Photo and CS datasets, the labeled nodes are also split into three sets where 60% of the nodes made up the training set, and the rest of the nodes were divided equally to form the validation and test sets. Airport and Disease datasets were split in similar settings as [11].

Footnote 1: Note that the top results on [https://paperswithcode.com/sota/node-classification-on-cora](https://paperswithcode.com/sota/node-classification-on-cora) used different data splits (either semi-supervised settings with a larger number of training samples or fully-supervised settings such as the 60/20/20% split) which give much higher accuracies

In Table II and Table III, the mean accuracy with standard deviation is reported for node classification, except for the case of Airport and Disease datasets where the mean F1 score is reported. Our empirical results demonstrate that JSGNN frequently outperforms the baselines, especially HGAT and GAT which are the building blocks of JSGNN. This shows the superiority of using both Euclidean and hyperbolic spaces. Results also show that JGNN frequently performs better than GIL, indicating that our method of incorporating two spaces for graph learning is potentially more effective.

We also observe that Euclidean models such as GCN, GAT, and GraphSAGE perform better than hyperbolic models in general on the Cora, Citeseer, and Pubmed datasets for both splits. Meanwhile, hyperbolic models achieve better results on the CS, Photo, Airport, and Disease datasets. This means that Euclidean features are more significant for representing Cora, Citeseer and Pubmed datasets while hyperbolic features are more significant for the others. Nevertheless, JSGNN is able to perform relatively well across all datasets. We note that JSGNN exceeds the performance of single-space baselines on all datasets except for Disease. This can be explained by the fact that Disease consists of a perfect tree and thus, does not exhibit different hyperbolicities in the graph.

We also particularly note that the difference in results between single-space models using only the Euclidean embedding space and hyperbolic models is not significant. This means that many of the node labels can be potentially predicted even without the best representation from the right space. This might be the reason why the gain in performance for the node classification task is not exceptional from embedding nodes in the better space. Nevertheless, we still see improvements in predictions for cases where there is a mixture of local hyperbolicities. Moreover, embedding nodes in a more suitable space can benefit other tasks that require more accurate representations such as link prediction.

### _Link prediction_

We employ the Fermi-Dirac decoder with a distance function to model the probability of an edge based on our final output
embedding, similar to [11, 12, 35]. The probability that an edge exists is given by \(\mathbb{P}(e_{vj}\in E\,|\,\Theta)=(e^{(d(x_{i},x_{j})-r)/t}+1)^{-1}\) where \(r,t>0\) are hyperparameters and \(d\) is the distance function. The edges of the datasets are randomly split into 85/5/10% for training, validation, and testing. The average ROC AUC for link prediction is recorded in Table IV. We observe that JSGNN performs better than the baselines in most cases. For the link prediction task, we notice that hyperbolic models consistently outperform Euclidean models by a significant margin. In such a situation, predicting the existence of edges seems to benefit from dual space models, i.e., GIL and JSGNN, potentially benefiting from better representations with reduced distortions.

### _Ablation study_

We conduct an ablation study on the node classification task by introducing three variants of JSGNN to validate the effectiveness of the different components introduced:

* Without the non-uniformity constraint (w/o NU): This does not enforce the model to learn non-uniform selection weights.
* Without the Wasserstein metric (w/o \(W_{2}\)): The learning of model hyperbolicity is not guided by geometric hyperbolicity.
* Without the non-uniformity loss and Wasserstein distance (w/o NU & \(W_{2}\)): Only guided by the cross entropy loss, i.e., \(\omega_{\text{nn}}=0,\omega_{\text{wns}}=0\) (cf. (18)).

Table V summarizes the results of our study, from which we observe that all variants of JSGNN with some components discarded perform worse than the full model. Moreover, JSGNN without \(W_{2}\) always achieves better results than JSGNN without NU and \(W_{2}\), signifying the importance of selecting the better of the two spaces instead of combining the features with relatively uniform weights. Similarly, JSGNN without NU performs better than JSGNN without NU and \(W_{2}\) in most cases, suggesting that incorporating geometric hyperbolicity through distribution alignment does help to improve the model.

To further analyze our model, we present a study regarding our method of incorporating the guidance of geometric hyperbolicity through distribution alignment. The result is as seen in Table VI. We test and analyze empirically different variants of our model based on the different comparisons shown in Fig. 5. Pairwise match indicates minimizing the mean squared error between elements of \(\Gamma_{G}\) and \(\Delta_{V}\) (without sorting) while mean match minimizes the squared loss between the means of \(\Gamma_{G}\) and \(\Delta_{V}\). We observe that comparing the distributions of \(\nu_{G}\) and \(\mu_{G}\) consistently outperforms comparing their mean, demonstrating the insufficiency of utilising coarse statistics for supervision. Secondly, pairwise matching gave better results than mean matching, though still lower than distribution matching, suggesting the importance of fine-scale information yet, a need to avoid potential overfitting.

### _Analysis of hyperbolicities_

We have speculated the effects of different components of our proposed model at the end of Section III-D. To verify that our model can learn model hyperbolicity that is non-uniform and similar in distribution as geometric hyperbolicity, we analyze the learned model hyperboliciities \((\beta_{v,\mathbb{R}})_{v\in V}\) of JSGNN and JSGNN w/o NU & \(W_{2}\) for the node classification task. Specifically, we extract the learned values from the first two layers of JSGNN and its variant for ten separate runs. The learned values from the first two layers were then averaged before determining \(W_{2}(\nu_{G},\mathrm{Unif})\) and \(W_{2}(\nu_{G},\mu_{G})\).

In Fig. 6, it can be inferred that JSGNN's learned model hyperbolicity is always less uniform than that of JSGNN w/o NU & \(W_{2}\) given JSGNN's larger \(W_{2}(\nu_{G},\mathrm{Unif})\) score, demonstrating a divergence from uniform distribution. Meanwhile, for most cases, JSGNN's \(W_{2}(\nu_{G},\mu_{G})\) is smaller than that of JSGNN w/o NU & \(W_{2}\), suggesting that the shape between \(\nu_{G}\) and \(\mu_{G}\) of JSGNN is relatively more similar. At times, JSGNN's \(W_{2}(\nu_{G},\mu_{G})\) is larger than JSGNN w/o NU & \(W_{2}\), suggesting a tradeoff between NU and \(W_{2}\) as we choose the optimal combination for the model's best performance.

## V Conclusion

In this paper, we have explored the learning of GNNs in a joint space setting given that different regions of a graph can have different geometrical characteristics. In these situations, it would be beneficial to embed different regions of the graph in different spaces that are better suited for their underlying structures, to reduce the distortions incurred while learning node representations. Our method JSGNN utilizes a soft attention mechanism with non-uniformity constraint
and distribution alignment between model and geometric hyperboliciities to select the best space-specific feature for each node. This indirectly finds the space that is best suited for each node. Experimental results of node classification and link prediction demonstrate the effectiveness of JSGNN against various baselines. In future work, we aim to further improve our model with an adaptive mechanism to determine the appropriate, node-level specific neighborhood to account for each node's hyperbolicity.

## Acknowledgments

The first author is supported by Shopee Singapore Private Limited under the Economic Development Board Industrial Postgraduate Programme (EDB IPP). The programme is a collaboration between Shopee and Nanyang Technological University, Singapore. The last two authors are supported by the Singapore Ministry of Education Academic Research Fund Tier 2 grant MOE-T2EP20220-0002, and the National Research Foundation, Singapore and Infocomm Media Development Authority under its Future Communications Research and Development Programme.

## Proof of Proposition 1

Proof.: We first consider \(\delta_{G,\infty}\). For two graphs \(G_{1}=(V_{1},E_{1})\) and \(G_{2}=(V_{2},E_{2})\), let \(f_{1}:G_{1}\to M\), \(f_{2}:G_{2}\to M\) be isometric embeddings into a metric space \((M,d)\) such that \(d_{GH}(G_{1},G_{2})=d_{H}(f_{1}(G_{1}),f_{2}(G_{2}))\). Denote \(d_{GH}(G_{1},G_{2})\) by \(\eta\). For \(x,y,z,t\) in \(G_{1}\), there are \(x^{\prime},y^{\prime},z^{\prime},t^{\prime}\in G_{2}\) such that \(d(f_{1}(x),f_{2}(x^{\prime}))\), \(d(f_{1}(y),f_{2}(y^{\prime}))\), \(d(f_{1}(z),f_{2}(z^{\prime}))\), \(d(f_{1}(t),f_{2}(t^{\prime}))\) are all bounded by \(\eta\). We now estimate:

\[\begin{split}& d_{G_{1}}(x,y)+d_{G_{1}}(z,t)=d(f_{1}(x),f_{1}(y))+d(f_ {1}(z),f_{1}(t))\\ &\leq d(f_{2}(x^{\prime}),f_{2}(y^{\prime}))+d(f_{2}(z^{\prime} ),f_{2}(t^{\prime}))+4\eta\\ &=d_{G_{2}}(x^{\prime},y^{\prime})+d_{G_{1}}(z^{\prime},t^{ \prime})+4\eta\\ &\leq\max\{d_{G_{2}}(x^{\prime},z^{\prime})+d_{G_{2}}(y^{\prime},t^{\prime}),d_{G_{2}}(z^{\prime},y^{\prime})+d_{G_{2}}(x^{\prime},t^{\prime} )\}\\ &\qquad+2\delta_{G_{2},\infty}+4\eta\\ &\leq\max\{d(f_{1}(x),f_{1}(z))+d(f_{1}(y),f_{1}(t)),\\ & d(f_{1}(z),f_{1}(y))+d(f_{1}(x),f_{1}(t))\}\\ &\qquad+2\delta_{G_{2},\infty}+8\eta\\ &=\max\{d_{G_{1}}(x,z)+d_{G_{1}}(y,t),d_{G_{1}}(z,y)+d_{G_{1}}(x,t)\}\\ &\qquad+2\delta_{G_{2},\infty}+8\eta.\end{split} \tag{19}\]

Therefore, \(\delta_{G_{1},\infty}\leq\delta_{G_{2},\infty}+4\eta\). By the same argument swapping the role of \(G_{1}\) and \(G_{2}\), we have \(\delta_{G_{2},\infty}\leq\delta_{G_{1},\infty}+4\eta\). Therefore \(|\delta_{G_{1},\infty}-\delta_{G_{2},\infty}|\leq 4\eta\) and \(\delta_{G,\infty}\) is Lipschitz continuous w.r.t. \(G\).

The proof of the continuity of \(\delta_{G,1}\) is more involved. Consider \(G_{1}\) and \(G_{2}\) in \(\mathcal{G}_{\epsilon}\). Let \(f_{1},f_{2},(M,d),\eta\) be as earlier and assume \(\eta\ll\epsilon\), for example, \(\eta=\alpha\epsilon\) for \(\alpha\) is smaller than all the numerical constants in the rest of the proof.

We adopt the following convention: for any non-vertex point of a graph, its degree is \(2\). By subdividing the edges of \(G_{1}\) and \(G_{2}\) if necessary, we may assume that the length of each edge \(e\) in \(E_{1}\) or \(E_{2}\) satisfies \(\epsilon/2\leq e<\epsilon\). As a consequence, for \((u,v)\) in \(E_{1}\) (resp. \(E_{2}\)), \(d_{G_{1}}(u,v)\) (resp. \(d_{G_{2}}(u,v)\)) is the same as the

Fig. 6: Analysis of hyperbolicities on different datasets. (a) \(W_{2}(\nu_{G},\mathrm{Unif})\). (b) \(W_{2}(\nu_{G},\mu_{G})\).
length of \((u,v)\). We define a map \(\phi:G_{1}\to G_{2}\) as follows. For \(v\in G_{1}\), there is a \(v^{\prime}\) in \(G_{2}\) such that \(d_{GH}(f_{1}(v),f_{2}(v^{\prime}))\leq\eta\). Then we set \(\phi(v)=v^{\prime}\). The map \(\phi\) is injective on the vertex set \(V_{1}\). Indeed, for \(u\neq v\in V_{1}\), \(d_{G_{1}}(u,.,v)\geq\epsilon/2\) and hence \(d_{G_{2}}(\phi(u),\phi(v))\geq\epsilon/2-2\eta>0\). The strategy is to modify \(\phi\) by a small perturbation such that the resulting function \(\psi:G_{1}\to G_{2}\) is a homeomorphism that is almost an isometry.

For \(v\in V_{1}\), let \(N_{v}\) be the \(5\eta\) neighborhood of \(v\). It is a star graph and its number of branches is the same as the degree of \(v\), say \(k\). Let \(v_{1},\ldots,v_{k}\) be the endpoints of \(N_{v}\). The convex hull (of shortest paths) \(C_{v}\) of \(\{\phi(v_{1}),\ldots,\phi(v_{k})\}\) in \(G_{2}\) is also a star graph. This is because \(C_{v}\) is contained in the \(7\eta\) neighborhood of \(\phi(v)\) and it contains at most \(1\) vertex in \(V_{2}\).

We claim that \(C_{v}\) has the same number of branches as \(N_{v}\). First of all, \(C_{v}\) cannot have fewer branches. For otherwise, there is a \(\phi(v_{i})\) in the path connecting \(\phi(v)\) and \(\phi(v_{j})\) for some \(j\neq i\). Hence,

\[d_{G_{2}}(\phi(v_{i}),\phi(v_{j}))\leq d_{G_{2}}(\phi(v_{i}), \phi(v))\leq 7\eta\] \[<10\eta-2\eta=d_{G_{1}}(v_{i},v_{j})-2\eta.\]

This is a contradiction with the property of \(\phi\). It cannot have more branches than \(k\) as it is the convex hull of at most \(k\) points.

We next consider different cases for \(k\). For \(k\neq 2\), as \(C_{v}\) is a star graph, it has a unique node \(v^{\prime}\) with degree \(k\) (in \(C_{v}\)), and \(d_{G_{1}}(v^{\prime},\phi(v_{j}))>0,1\leq j\leq j\). We claim that \(v^{\prime}\) has degree exact \(k\) in \(G_{2}\). Suppose on the contrary, its degree in \(G_{2}\) is larger than \(k\). Then there is a branch not contained in \(C_{v}\). Let \(w^{\prime}\) be a node on the new branch such that \(6\eta\leq d_{G_{2}}(w^{\prime},\phi(v))\leq 7\eta\). Moreover, there is a node \(w\) in \(N_{v}\) such that \(4\eta\leq d_{G_{1}}(w,v)\leq 9\eta\) and \(w^{\prime}=\phi(w)\). Moreover, \(w\) is on the branch containing \(v_{j}\) for some \(j\), and hence \(d_{G_{1}}(w,v_{j})\leq 4\eta\). Therefore,

\[d_{G_{1}}(w,v_{j})\leq 6\eta-2\eta\] \[<d_{G_{2}}(v^{\prime},\phi(v_{j}))+d_{G_{2}}(w^{\prime},v^{\prime })-2\eta\] \[=d_{G_{2}}(\phi(w),\phi(v_{j}))-2\eta,\]

which is a contradiction. In this case, we define \(\psi(v)=v^{\prime}\in G_{2}\). If \(k=2\) when \(N_{v}\) is a path, by a similar argument, we have that \(C_{v}\) is a path. We set \(\psi(v)=\phi(v)\). An illustration is given in Fig. 7.

For each \(v\in V_{1}\), we now enlarge the neighborhood and consider its \(\epsilon/6\)-neighborhood \(N_{v}^{\prime}\). It does not contain another vertex and hence is also a star graph. Moreover, if \(v\neq u\in V_{1}\), then \(N_{v}^{\prime}\cap N_{u}^{\prime}=\emptyset\) for otherwise \(d_{G_{1}}(u,v)\leq\epsilon/3\), which is impossible. We may similarly consider the \(\epsilon/6\)-neighborhoods \(C_{u}^{\prime},C_{v}^{\prime}\) of \(\psi(u)\) and \(\psi(v)\). Both \(C_{u}^{\prime}\) and \(C_{v}^{\prime}\) do not contain any vertex in \(V_{2}\) with degree \(\neq 2\).

As \(N_{v}^{\prime}\) and \(C_{v}^{\prime}\) are star graphs with the same number of branches, there is an isometry (also denoted by \(\psi:N_{v}^{\prime}\to C_{v}^{\prime}\) such that \(d_{G_{2}}(\psi(w),\phi(w))\leq 2\eta\). By disjointedness of \(\epsilon/6\) neighborhoods, we may combine all the maps above together to obtain \(\psi:\cup_{v\in V_{1}}N_{v}^{\prime}\to\cup_{v\in V_{1}}C_{v}^{\prime}\).

For the rest of \(G_{1}\), consider any edge \((u,v)\in E_{1}\). Without loss of generality, let \(u_{1}\) and \(v_{1}\) be the leaves of \(N_{u}^{\prime}\) and \(N_{v}^{\prime}\) contained in \((u,v)\). We claim that the shortest open path connecting \(\psi(u_{1})\) and \(\psi(v_{1})\) is disjoint from \(\cup_{v\in V_{1}}C_{v}^{\prime}\). For otherwise, \(d_{G_{1}}(u_{1},v_{1})\geq 2\epsilon/3\), while \(d_{G_{2}}(\phi(u_{1}),\phi(u_{2}))\leq d_{G_{2}}(\psi(u_{1}),\psi(u_{2}))-4\eta \geq\epsilon/2+2\epsilon/6-4\eta\). Therefore, \(2\epsilon/3-2\eta\geq 5\epsilon/6-4\eta\), which is impossible as \(\eta\ll\epsilon\).

Let \(P_{u,v}\) and \(Q_{u,v}\) be the shortest paths connecting \(u_{1},v_{1}\) and \(\psi(u_{1}),\psi(v_{1})\) respectively (illustrated in Fig. 8). Then the length of \(P_{u,v}\) and \(Q_{u,v}\) differ at most by \(4\eta\). We may further extend \(\psi:P_{u,v}\to Q_{u,v}\) by a linear scaling such that \(d_{G_{2}}(\psi(w),\phi(w))\leq 3\eta\) for \(w\in P_{u,v}\). For different edges \((u,v),(u^{\prime},v^{\prime})\), it is apparent \(Q_{u,v}\cap Q_{u^{\prime},v^{\prime}}\) are disjoint, as the minimal distance between points on \(P_{u,v}\) and \(P_{u^{\prime},v^{\prime}}\) is at least \(\epsilon/3\). Therefore, we obtain a continuous injection \(\psi:G_{1}\to G_{2}\), which maps homeomorphically onto its image.

We claim that \(\psi\) is onto. If not, there is a vertex \(v^{\prime}\in V_{2}\) that is not in \(\psi(V_{1})\) but it has a neighboring vertex \(u^{\prime}=\psi(u)\). However, this implies that the degree of \(u^{\prime}\) is strictly larger than that of \(u\), which is impossible as we have shown.

In summary, \(\psi:G_{1}\to G_{2}\) is a homeomorphism such that \(|d_{G_{1}}(u,v)-d_{G_{2}}(u,v)|\leq 6\eta\) for any \(u,v\in G_{1}\). Moreover, \(\psi\) is piecewise linear whose gradient \(\psi^{\prime}\) is \(1\) in the interior of \(N_{v}^{\prime},v\in V_{1}\) and satisfies

\[\frac{\frac{\epsilon}{6}-6\eta}{\frac{\epsilon}{6}}\leq\psi^{ \prime}(w)\leq\frac{\frac{\epsilon}{6}+6\eta}{\frac{\epsilon}{6}}, \tag{20}\]

for \(w\) contained in the interior of some \(P_{u,v},(u,v)\in E_{1}\).

We are ready to estimate \(|\delta_{G_{1},1}-\delta_{G_{2},1}|\). Let \(|G_{i}|\) be the total edge weights of \(G_{i},i=1,2\). For convenience, we denote a typical tuple \((u,v,w,t)\in G_{1}^{4}\) as a vector \(\mathbf{v}\), and \((\psi(u),\psi(v),\psi(w),\psi(t))\) by \(\boldsymbol{\psi}(\mathbf{v})\). The map \(\boldsymbol{\psi}:G_{1}^{4}\to G_{2}^{4},\mathbf{v}\mapsto\boldsymbol{\psi} (\mathbf{v})\) inherits the properties of its counterpart \(\psi\), which is a piecewise linear homeomorphism. In particular, its Jacobian \(J(\mathbf{v})\) is defined almost everywhere. Using Definition 2,

Fig. 7: Illustration of \(\psi\).
we have:

\[\begin{split}&|\delta_{G_{1},1}-\delta_{G_{2},1}|\\ &=\Bigg{|}\int_{\mathbf{v}\in G_{1}^{4}}|G_{1}|^{-4}\tau_{G_{1}}( \mathbf{v})\,\mathrm{d}\mathbf{v}\\ &\qquad-\int_{\mathbf{v}\in G_{1}^{4}}|G_{2}|^{-4}J(\mathbf{v}) \tau_{G_{2}}(\mathbf{\psi}(\mathbf{v}))\,\mathrm{d}\mathbf{v}|\\ &\leq\sup_{\mathbf{v}\in G_{1}^{4}}|\tau_{G_{1}}(\mathbf{v})- \frac{|G_{1}|^{4}}{|G_{2}|^{4}}J(\mathbf{v})\tau_{G_{2}}\big{(}\mathbf{\psi}( \mathbf{v})\big{)}\Bigg{|}.\end{split} \tag{21}\]

Similar to (19), we estimate

\[\sup_{\mathbf{v}\in G_{1}^{4}}|\tau_{G_{1}}(\mathbf{v})-\tau_{G_{2}}\big{(}\bm {\psi}(\mathbf{v})\big{)}|\leq 24\eta. \tag{22}\]

Moreover, we have seen in the proof that \(\psi\) can only have distortion when restricted to \(P_{u,v}\) for \((u,v)\in E_{1}\). As

\[\frac{\frac{2e}{3}-6\eta}{\frac{2e}{3}}\leq|P_{u,v}|/|Q_{u,v}|\leq\frac{\frac{2 e}{3}+6\eta}{\frac{2e}{3}},\]

the same bounds holds for \(|G_{1}|/|G_{2}|\). Both upper and lower bounds can be arbitrarily close to \(1\) if \(\eta\) is small enough. Similarly, by (20), \(J(\mathbf{v})\) as a fourth power of \(\psi^{\prime}\) can also be made arbitrarily close to \(1\). In conjunction with (21) and (22), \(|\delta_{G_{1},1}-\delta_{G_{2},1}|\) can be arbitrarily small if \(\eta\) is chosen to be small enough. This proves that \(\delta_{G,1}\) is continuous in \(G\). 
