Modeling Graphs Beyond Hyperbolic: Graph Neural Networks in Symmetric
  Positive Definite Matrices
Recent research has shown that alignment between the structure of graph data
and the geometry of an embedding space is crucial for learning high-quality
representations of the data. The uniform geometry of Euclidean and hyperbolic
spaces allows for representing graphs with uniform geometric and topological
features, such as grids and hierarchies, with minimal distortion. However,
real-world graph data is characterized by multiple types of geometric and
topological features, necessitating more sophisticated geometric embedding
spaces. In this work, we utilize the Riemannian symmetric space of symmetric
positive definite matrices (SPD) to construct graph neural networks that can
robustly handle complex graphs. To do this, we develop an innovative library
that leverages the SPD gyrocalculus tools \cite{lopez2021gyroSPD} to implement
the building blocks of five popular graph neural networks in SPD. Experimental
results demonstrate that our graph neural networks in SPD substantially
outperform their counterparts in Euclidean and hyperbolic spaces, as well as
the Cartesian product thereof, on complex graphs for node and graph
classification tasks. We release the library and datasets at
\url{https://github.com/andyweizhao/SPD4GNNs}.
Wei Zhao, Federico Lopez, J. Maxwell Riestenberg, Michael Strube, Diaaeldin Taha, Steve Trettel
# Modeling Graphs Beyond Hyperbolic:

###### Abstract

Recent research has shown that alignment between the structure of graph data and the geometry of an embedding space is crucial for learning high-quality representations of the data. The uniform geometry of Euclidean and hyperbolic spaces allows for representing graphs with uniform geometric and topological features, such as grids and hierarchies, with minimal distortion. However, real-world graph data is characterized by multiple types of geometric and topological features, necessitating more sophisticated geometric embedding spaces. In this work, we utilize the Riemannian symmetric space of symmetric positive definite matrices (SPD) to construct graph neural networks that can robustly handle complex graphs. To do this, we develop an innovative library that leverages the SPD gyrocalculus tools [28] to implement the building blocks of five popular graph neural networks in SPD. Experimental results demonstrate that our graph neural networks in SPD substantially outperform their counterparts in Euclidean and hyperbolic spaces, as well as the Cartesian product thereof, on complex graphs for node and graph classification tasks. We release the library and datasets at [https://github.com/andyweizhao/SPD4GNNs](https://github.com/andyweizhao/SPD4GNNs).

Keywords:Graph Neural Networks Riemannian Geometry Symmetric Space of Symmetric Positive Definite Matrices

## 1 Introduction

Complex structures are a common feature in real-world graph data, where the graphs often contain a large number of connected subgraphs of varying topologies (including grids, trees, and combinations thereof). While accommodating the diversity of such graphs is necessary for robust representation learning, neither Euclidean nor hyperbolic geometry alone has been sufficient [25].
This inefficiency stems from geometric reasons. Properties of the embedding space strongly control which graph topologies embed with low distortion, with simple geometries selecting only narrow classes of graphs. Euclidean geometry provides the foundational example, where its abundant families of equidistant lines allow for efficient representation of grid-like structures, but its polynomial volume growth is too slow to accommodate tree-like data. This is somewhat ameliorated by moving to higher dimensions (with faster polynomial volume growth), though with a serious trade-off in efficiency [4]. An alternative is to move to hyperbolic geometry, where volume growth is exponential, providing plenty of room for branches to spread out for the isometric embedding of trees [7, 37]. However, hyperbolic geometry has a complementary trade-off: it does not contain equidistant lines, which makes it unfit for embedding the grid-like structures Euclidean space excelled at [8].

Many proposed graph neural networks utilize representations of graph data to perform machine learning tasks in various graph domains, such as social networks, biology and molecules [24, 39, 11, 13, 34, 33, 14, 2]. A subset of these networks take seriously the constraints of geometry on representation capability, and work to match various non-Euclidean geometries to common structures seen in graph data. For instance, Chami et al. [11] and Defferrard et al. [13] show that constructing graph neural networks in hyperbolic and spherical spaces have been successful in embedding graphs with hierarchical and cyclical structures, respectively. However, the relative geometric simplicity of these spaces poses serious limitations including (a) the need to know the graph structure prior to choosing the embedding space, and (b) the inability to perform effectively with graphs built of geometrically distinct sub-structures, a common feature of real-world data.

Avoiding these limitations may necessitate resorting to more complex geometric spaces. For example, Gu et al. [18] employed Cartesian products of various geometric spaces to represent graphs with mixed geometric structures. But any such choice must be carefully considered: isometries play an essential role in the construction of the above architectures, and any increase in complexity accompa

Figure 1: Propagation schema for utilizing SPD geometry while performing calculations in the tangent (Euclidean) space: starting from an SPD embedding, map a node and its neighbors to the tangent space via the logarithm, and perform a modified Euclidean aggregation (Table 1) before returning to SPD via the Riemannian exponential map.
nied by too great a decrease in symmetry may render a space computationally intractable.

Riemannian symmetric spaces, which have a rich geometry encompassing all the aforementioned spaces, strike an effective balance between geometric generality and ample symmetry. Lopez et al. [27] proposed particular symmetric spaces, namely Siegel spaces, for graph embedding tasks, and demonstrated that many different classes of graphs embed in these spaces with low distortion. Lopez et al. [28] suggested utilizing the symmetric space SPD of symmetric positive definite matrices that is less computationally expensive than Siegel spaces. Furthermore, they developed gyrocalculus tools that enable "vector space operations" on SPD.

Here we extend the idea of Lopez et al. [28] to construct graph neural networks in SPD, particularly by utilizing their gyrocalculus tools to implement the building blocks of graph neural networks in SPD. The building blocks include (a) feature transformation via isometry maps, (b) propagation via graph convolution in the tangent space of SPD (the space of symmetric matrices \(S_{n}\)), (c) bias addition via gyrocalculus, (d) non-linearity acting on eigenspace, and (e) three classification layers. We develop _SPD4GNNs_, an innovative library that showcases training five popular graph neural networks in SPD\({}_{n}\), alongside the functionality for training them in Euclidean and hyperbolic spaces.

We perform experiments to compare four ambient geometries (Euclidean, hyperbolic, products thereof, and SPD) across popular graph neural networks, evaluated on the node and graph classification tasks on nine datasets with varying complexities. Results show that constructing graph neural networks in SPD space leads to big improvements in accuracy over Euclidean and hyperbolic spaces on complex graphs, at the cost of doubling (resp. quadrupling) the training time of graph neural networks compared to hyperbolic space (resp. Euclidean space).

Finally, we provide a summary of the numerical issues we encountered and the solutions to addressing them (see Appendix 0.F).

## 2 Related Work

Graph Neural Networks.Graph neural networks (GNNs) have been profiled as the de facto solutions for learning graph embeddings [24, 39, 40, 33, 14, 2]. These networks can be differentiated into two dimensions: (a) how they propagate information over graph nodes and (b) which geometric space they use to embed the nodes. In **Euclidean space**, a class of GNNs has been proposed that represents graph nodes in a flat space and propagates information via graph convolution in various forms, such as using Chebyshev polynomial filters [12, 24], high-order filters [40], importance sampling [20], attention mechanisms [39], graph-isomorphism designs [41, 34, 2], and differential equations [16, 33, 14]. In contrast, **non-Euclidean spaces** have a richer structure for representing geometric graph structures in curved spaces. Recently, there has been a line of GNNs developed in these spaces that performs graph convolution on different Riemannian manifolds in order to accommodate various graph structures, such as hyperbolic space on
tree-like graphs [11, 26, 42], spherical space on spherical graphs [13], and Cartesian products of thereof [19].

SPD _Space._ Representing data with SPD matrices has been researched for many years, with the representations being primarily in the form of covariance matrices [15, 22, 44, 17, 9]. These matrices capture the statistical dependencies between Euclidean features. Recent research focused on designing the building blocks of neural networks in the space of covariance matrices. This includes feature transformation that maps Euclidean features to covariance matrices via geodesic Gaussian kernels [15, 6], nonlinearity on the eigenvalues of covariance matrices [22], convolution through SPD filters [44] and Frechet mean [9], Riemannian recurrent networks [10], and Riemannian batch normalization [5].

Nguyen et al. [31] recently approached hand gesture classification by embedding graphs into SPD via a neural network. The architectures we consider here are different. While we alternate between SPD and its tangent space using the exponential and logarithm maps, Nguyen et al. [31] do so via an aggregation operation and the log map. Further, we couple this alternation with our building blocks to operate graph neural networks in SPD.

## 3 Background

### The Space SPD

We let \(\mathrm{SPD}_{n}\) denote the space of positive definite real symmetric \(n\times n\) matrices. This space has the structure of a Riemannian manifold of non-positive curvature of \(n(n+1)/2\) dimensions. The tangent space to any point of \(\mathrm{SPD}_{n}\) can be identified with the vector space \(S_{n}\) of all real symmetric \(n\times n\) matrices. \(\mathrm{SPD}_{n}\) is more flexible than Euclidean or hyperbolic geometries, or products thereof. In particular, it contains \(n\)-dimensional Euclidean subspaces, \((n-1)\)-dimensional hyperbolic subspaces, products of \(\lfloor\frac{n}{2}\rfloor\) hyperbolic planes, and many other interesting spaces as totally geodesic submanifolds; see the reference [21] for an in-depth introduction to these well-known facts. While it is not yet fully understood how our proposed models leverage the Euclidean and hyperbolic subspaces in \(\mathrm{SPD}_{n}\), we hypothesize that the presence of these subspaces is an important factor in the superior performance of \(\mathrm{SPD}_{n}\) graph neural networks. Refer to Figure 2 for a demonstration of how this hypothesis may manifest.

Riemannian Exponential and Logarithmic Maps.For \(\mathrm{SPD}_{n}\), the Riemannian exponential map at the basepoint \(I_{n}\) agrees with the standard matrix exponential \(\exp\colon S_{n}\to\mathrm{SPD}_{n}\). This map is a diffeomorphism with inverse the matrix logarithm \(\log\colon\mathrm{SPD}_{n}\to S_{n}\). These maps allow us to pass from \(\mathrm{SPD}_{n}\) to \(S_{n}\) and back again. Given any two points \(X,Y\in\mathrm{SPD}_{n}\), there exists an isometry (i.e., a distance-preserving transformation) that maps \(X\) to \(Y\). As such, the choice of a basepoint for the exponential and logarithm maps is arbitrary since any other point can be mapped to the basepoint by an isometry. In particular, there is no loss of generality with fixing the basepoint \(I_{n}\) as we do.
Non-linear Activation Functions in \(\mathrm{SPD}_{n}\).We use two non-linear functions on SPD matrices, namely (i) ReEig [22]: factorizing a point \(P\in\mathrm{SPD}_{n}\) and then employing the ReLU-like non-linear activation function \(\varphi_{a}\) to suppress the positive eigenvalues that are bigger than \(0.5\)2:

Footnote 2: TgReEig equals ReEig in the case of \(\varphi_{a}(x)=\max(x,1)\).

\[\varphi^{\mathrm{SPD}}(P)=U\varphi_{a}(\varSigma)U^{T}\hskip 28.452756ptP=U \varSigma U^{T} \tag{1}\]

(ii) TgReEig: projecting \(P\in\mathrm{SPD}_{n}\) into the tangent space and then suppressing the negative eigenvalues of the projected point \(\in S_{n}\) with the ReLU non-linear activation function \(\varphi_{b}\), i.e. \(\varphi^{\mathrm{SPD}}(P)=U\exp(\varphi_{b}(\log(\varSigma)))U^{T}\).

### Gyrocalculus on SPD

Addition and Subtraction.Gyro-calculus is a way of expressing natural analogues of vector space operations in Riemannian manifolds. Following Lopez et al. [28], given two points \(P,Q\in\mathrm{SPD}_{n}\), we denote gyro-addition and gyro-inversion by:

\[P\oplus Q=\sqrt{P}Q\sqrt{P}\hskip 28.452756pt\ominus P=P^{-1} \tag{2}\]

For \(P,Q\in\mathrm{SPD}_{n}\), the value \(P\oplus Q\in\mathrm{SPD}_{n}\) is the result of applying the \(\mathrm{SPD}_{n}\)-translation moving the basepoint \(I_{n}\) to \(P\), evaluated on \(Q\).

Isometry Maps.Any invertible \(n\times n\) real matrix \(M\in\mathrm{GL}(n,\mathbb{R})\) defines an isometry of \(\mathrm{SPD}_{n}\) by

\[M\mathbin{\raisebox{-1.0pt}{\mbox{\tiny$\circ$}}}P=MPM^{T} \tag{3}\]

where \(P\in\mathrm{SPD}_{n}\).

Lopez et al. [28] proposed defining \(M\) in two forms, namely a rotation element in \(SO(n)\) and a reflection element in \(O(n)\). In this case, the choice of rotation and reflection becomes a hyperparameter for \(M\), and that needs to be selected before training. In contrast, the form of \(M\) we considered is more flexible and can be automatically adjusted by training data. To do so, we first let \(M\) denote the

Figure 2: Graphs exhibiting both euclidean/grid-like and hyperbolic/tree-like features (left) cannot embed well in either euclidean or hyperbolic spaces due to the impossibility of isometrically embedding trees in Euclidean spaces and grids in hyperbolic spaces (center). However, \(\mathrm{SPD}_{n}\) (right) contains both euclidean and hyperbolic subspaces, which allows embedding a broad class of graphs, including the example in the figure.
orthogonal basis of a learnable square matrix, and then tune the square matrix from training data. Thus, \(M\), as an orthogonal matrix that extends rotations and reflections, is better suited to fit the complexity of graph data.

## 4 Graph Neural Networks

In this section, we introduce the notation and building blocks of graph neural networks using graph convolutional network (GCN) [24] as an example, and present modifications for operating these building blocks in SPD. Table 1 establishes parallels between five popular graph neural networks in Euclidean, hyperbolic and SPD spaces.

### GCN in Euclidean Space

Given a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) with a vertex set \(\mathcal{V}\) and an edge set \(\mathcal{E}\), we define \(d\)-dimensional input node features \((x_{i}^{0})_{i\in\mathcal{V}}\), where the superscript \(0\) indicates the first layer. The goal of a graph neural network is to learn a mapping denoted by:

\[f:(\mathcal{V},\mathcal{E},(x_{i}^{0})_{i\in\mathcal{V}})\rightarrow\mathcal{Z }\in\mathbb{R}^{|\mathcal{V}|\times d}\]

where \(\mathcal{Z}\) is the space of node embeddings obtained from the final layer of GCN, which we take as the input of classification layer to perform downstream tasks.

Let \(\mathcal{N}(i)=\{j:(i,j)\in\mathcal{E}\}\cup\{i\}\) be the set of neighbors of \(i\in\mathcal{V}\) with self-loops, and \((W^{l},b^{l})\) be a matrix of weights and a vector of bias parameters at layer \(l\), and \(\varphi(\cdot)\) be a non-linear activation function. We now introduce **message passing**, which consists of the following three components for exchanging information between the node \(i\) and its neighbors at layer \(l\):

\[h_{i}^{l} =W^{l}x_{i}^{l-1}\] Feature transform (4) \[p_{i}^{l} =\sum_{j\in\mathcal{N}(i)}k_{i,j}h_{j}^{l}\] Propagation (5) \[x_{i}^{l} =\varphi(p_{i}^{l}+b^{l})\] Bias & Nonlinearity (6)

where \(k_{i,j}=c_{i}^{-\frac{1}{2}}c_{j}^{-\frac{1}{2}}\) with \(c_{i}\) as the cardinality of \(\mathcal{N}(i)\). \(k_{i,j}\) represents the relative importance of the node \(j\) to the node \(i\).

\begin{table}
\begin{tabular}{l|l|l|l} \hline Operations & GNNs & Euclidean Space & Hyperbolic and SPD Space \\ \hline \multirow{2}{*}{Feature Trans} & All & \(h_{i}^{l}=W^{l}x_{i}^{l-1}\) & \(Q_{i}^{l}=M^{l}\odot Z_{i}^{l-1}\) \\ \hline \multirow{2}{*}{Propagation} & GCN & \(p_{i}^{l}=\sum_{j\in\mathcal{N}(i)}k_{i,j}h_{j}^{l}\) & \(P_{i}^{l}=\exp(\sum_{j\in\mathcal{N}(i)}k_{i,j}\log(Q_{j}^{l}))\) \\  & GAT & \(p_{i}^{l}=\alpha_{i,i}h_{i}^{l}+\sum_{j\in\mathcal{N}(i)}\alpha_{i,j}h_{j}^{l}\) & \(P_{i}^{l}=\exp(\alpha_{i,i}\log(Q_{i})+\sum_{j\in\mathcal{N}(i)}\alpha_{i,j} \log(Q_{j}^{l}))\) \\  & Cheb & \(p_{i}^{l}=h_{i}^{l}+W^{l}\sum_{j\in\mathcal{N}(i)}k_{i,j}h_{j}^{l}\) & \(P_{i}^{l}=Q_{i}^{l}\oplus(M^{l}\odot\exp(\sum_{j\in\mathcal{N}(i)}k_{i,j}\log Z _{j}^{l-1}))\) \\ \hline Bias\&Nonlin & All & \(x_{i}^{l}=\varphi(p_{i}^{l}+b^{l})\) & \(Z_{i}^{l}=\varphi(P_{i}^{l}\oplus B^{l})\) \\ \hline \end{tabular}
\end{table}
Table 1: Comparison of operations in different spaces across three graph neural networks, i.e., GCN [24], GAT [39] and 1-order Cheb [12]. SGC [40] and GIN [41] are presented in Appendix B, which indeed apply propagation before feature transformation.
### GCN in SPD

Mapping from Euclidean to SPD space.Oftentimes, input node features are not given in SPD, but in Euclidean space \((x_{i}^{0})_{i\in\mathcal{V}}\in\mathbb{R}^{d}\). Therefore, we design a transformation that maps Euclidean features to a point in SPD. To do so, we first learn a linear map that transforms the \(d\)-dimensional input features into a vector of dimension \(n(n+1)/2\), that we arrange as the upper triangle of an initially zero matrix \(A\in\mathbb{R}^{n\times n}\). We then define a symmetric matrix \(U\in S_{n}\) such that \(U=A+A^{T}\). We now apply the exponential map such that \(Z=\exp(U)\), which moves the coordinates from the tangent space \(S_{n}\) to the original manifold \(\mathrm{SPD}_{n}\). Thus, the resulting node embeddings \((Z_{i}^{0})_{i\in\mathcal{V}}\) are in \(\mathrm{SPD}_{n}\). By performing this mapping only once, we enable GNNs to operate in \(\mathrm{SPD}_{n}\).

Feature Transform.We apply isometry maps to transform points in SPD at different layers, denoted by: \(Q_{i}^{l}=M^{l}\odot Z_{i}^{l-1}\), where \(Q_{i}^{l},Z_{i}^{l-1}\in\mathrm{SPD}_{n}\) and \(M^{l}\) is a isometry map (see SS3.2) at layer \(l\) of the GNN.

Propagation.This step aggregates information from all the neighbors \(\mathcal{N}(i)\) of a given node \(i\), with the information weighted by the importance of a neighbor to the node \(i\) (see Eq. 5). We note that propagation involves addition and scaling operators. This results in two alternative approaches for computing propagation: (a) employing gyro-addition to aggregate information over the neighbors for each node; (b) computing the Riemannian Frechet mean in \(\mathrm{SPD}_{n}\)--which requires hundreds of iterations to find a geometric center. Therefore, these approaches are costly to compute and also involve the use of cumbersome Riemannian optimization algorithms (see Appendix 0.A for optimization). Here we perform aggregation via graph convolution in the space of symmetric matrices \(S_{n}\) denoted by: \(P_{i}^{l}=\exp(\sum_{j\in\mathcal{N}(i)}k_{i,j}\log(Q_{j}^{l}))\), where \(P_{i}^{l}\in\mathrm{SPD}_{n}\) and \(k_{i,j}=c_{i}^{-\frac{1}{2}}c_{j}^{-\frac{1}{2}}\) (as in the Euclidean case). This is similar to the approach of Chami et al. [11] by performing propagation in the tangent pace and the posterior projection through the exponential map.

Bias Addition and Non-linearity.Finally, we add the bias \(B^{l}\) at layer \(l\) to the result of propagation through gyro-addition followed by applying a non-linear function, denoted by: \(Z_{i}^{l}=\varphi^{\mathrm{SPD}}(P_{i}^{l}\oplus B^{l})\), with \(Z_{i}^{l}\in\mathrm{SPD}_{n}\) as the new embedding for the node \(i\) at layer \(l\) and \(B^{l}\in\mathrm{SPD}_{n}\).

Message Passing in \(\mathrm{SPD}\).We establish a one-to-one correspondence between the Euclidean and SPD versions of GCN at layer \(l\) for node \(i\):

\[Q_{i}^{l} =M^{l}\odot Z_{i}^{l-1}\] Feature transform (7) \[P_{i}^{l} =\exp(\sum_{j\in\mathcal{N}(i)}k_{i,j}\log(Q_{j}^{l}))\] Propagation (8) \[Z_{i}^{l} =\varphi^{\mathrm{SPD}}(P_{i}^{l}\oplus B^{l})\] Bias & non-lin (9)
Classification.In node classification setups3, we are given \(\{Z_{i},y_{i}\}_{i=1}^{N}\) on a dataset, with \(N\) as the number of instances, \(Z_{i}\in\text{SPD}_{n}\) as the \(i\)-th node embedding obtained from the final layer of a graph neural network, and \(y_{i}\in\{1,\ldots,K\}\) as the true class of \(i\)-th node. Let \(h:\text{SPD}\mapsto\{1,\ldots,K\}\) be a classifier that best predicts the label \(y_{i}\) of a given input \(Z_{i}\). Indeed, the input space of \(h\) can be in various forms, not limited to \(\text{SPD}_{n}\). Here we introduce three classifiers in two alternative input spaces: (a) \(\mathbb{R}^{d(d+1)/2}\) and (b) \(S_{n}\)4. To do so, we first take Riemannian logarithm \(\log\colon\text{SPD}_{n}\to S_{n}\) of each \(Z_{i}\) at the identity. For (a), we vectorize the upper triangle elements of \(X\) as \(\mathbf{x}=(X_{1,1}\cdots X_{1,d},X_{2,2},\cdots,X_{d,d})\in\mathbb{R}^{d(d+1) /2}\), and then design two classifiers, i.e., Linear-XE (Linear Classifier coupled with Cross-Entropy loss) and NC-MM (Nearest Centroid Classifier with Multi-Margin loss). For (b), we design a SVM-like classifier SVM-MM acting in \(S_{n}\), a similar approach to the proposal of Nguyen et al. [31]. We present the details of these classifiers in Appendix 0.C.

Footnote 3: For graph classification, \(Z_{i}\) and \(y_{i}\) denote the ‘center’ of the graph \(i\) and its true class. We take the arithmetic mean of node embeddings in \(\text{SPD}_{n}\) to produce \(Z_{i}\in\text{SPD}_{n}\).

Footnote 4: We also design several classifiers with the input space in \(\text{SPD}_{n}\), but these do not yield better results than those in \(S_{n}\).

## 5 Experiments

In this section, we first perform experiments for node and graph classification, and then analyze the ability of three geometric spaces in arranging and separating nodes with different classes. Further, we compare the training efficiency of different spaces and the usefulness of three classifiers. Lastly, we discuss **product space** (the Cartesian product of Euclidean and hyperbolic spaces) and compare it with SPD in Appendix 0.H.

Baselines.To investigate the usefulness of different geometric spaces on graph neural networks, we choose five well-known graph architectures as representatives: GCN [24], GAT [39], Cheb [12], SGC [40] and GIN [41], and evaluate these architectures in Euclidean, hyperbolic and SPD spaces. For the hyperbolic versions of these architectures, we use Poincare models and extend the implementation of Poincare GCN [11] to other four architectures.

### Node Classification

Datasets.We evaluate graph neural networks in the three spaces on 5 popular datasets for node classification: Disease [1], Airport [43], Pubmed [30], Citeseer and Cora [36]. Overall, each dataset has a single graph that contains up to thousands of labeled nodes. We use the public train, validation and test splits of each dataset, and provide dataset statistics in Appendix 0.C. Unlike previous works [11, 42], we only use original node features to ensure a fair and transparent comparison.
Setup.We compare three geometries, namely Euclidean, hyperbolic and SPD, in two low-dimensional spaces: (i) 6 dimensions: \(\mathbb{R}^{6}\), \(\mathbb{H}^{6}\) and \(\text{SPD}_{3}\), and (ii) 15 dimensions: \(\mathbb{R}^{15}\), \(\mathbb{H}^{15}\) and \(\text{SPD}_{5}\), a common choice of dimensions in previous work [11, 42]. The reason we considered for low-dimensional space is the following: If the structure of data matches the geometry of embedding space, a low-dimensional space can be leveraged efficiently for producing high-quality embeddings. If they do not match, a large dimension is needed to compensate for the wrong use of unsuitable geometric spaces. Here we investigate the efficiencies of different geometries in space use when given a small dimension. We report mean accuracy and standard deviation of binary/multi-label classification results under 10 runs, and provide training details in Appendix 0.A.

Results.Figure 3 shows the accuracy results of a node classification task in the three 6-dimensional geometries across five datasets on five GNNs, see also Table 6. For graphs with \(\delta\)-hyperbolicity \(>1\), \(\text{SPD}_{3}\) achieves the best accuracy in all cases except the Cheb architecture on the Citeseer dataset. We also observe that the accuracy of SPD is similar to hyperbolic space on the Airport dataset \(\delta=1\)

Figure 3: Evaluation of five graph neural networks coupled with Linear-XE on five node classification datasets in the three 6-dimensional spaces: \(\mathbb{R}^{6}\), \(\mathbb{H}^{6}\) and \(\text{SPD}_{3}\). Each radar chart shows classification accuracy (on a varying scale, as noted by the gridlines with circular shapes) from the five GNN architectures on a dataset. Each dataset has only one graph. \(\delta\)-hyperbolicity shows the degree to which the dataset graph is a hyperbolic tree. A smaller \(\delta\) indicates a more tree-like dataset.
The Disease graph is a tree (\(\delta=0\)) and has optimal performance in hyperbolic space. The accuracy is much lower for these two tree-like datasets in Euclidean geometry for all GNNs except Cheb.

In the case of tree-like datasets, hyperbolic space provides not only accuracy for these tasks but also efficiency. Figure 4 compares 6-dimensional hyperbolic space to \(\mathbb{R}^{15}\) and \(\text{SPD}_{5}\) (also 15-dimensional), showing that even a much smaller dimensional hyperbolic space achieves the best performance on Disease. Notably, the poor performance of Cheb across all spaces might be attributed to the low representational capacity of the first-order Chebyshev polynomial used in the graph neural network for embedding the tree structure of Disease. Results comparing the 6d and 15d geometries are reported in Table 7 (appendix).

### Graph Classification

Datasets.We evaluate graph neural networks in three spaces on the popular TUDataset benchmark [29]. Here we focus on datasets with node features, and choose a sample of 4 popular datasets in two domains, namely (a) Biology: ENZYMES [35] and PROTEINS [3]; (b) Molecules: COX2 [38] and AIDS [32]. Overall, each dataset instance has one labeled graph with dozens of nodes. We use the first split of train and test sets in the 10-fold cross-validation setup5, and select 10% of the training set uniformly at random as the development set. We provide data statistics in Appendix C.

Footnote 5: Morris et al. [29] proposed to run 10-fold cross-validation by generating ten splits of train and test sets, and repeat this ten times to reduce model initialization. This requires 100 runs for one setup, but it is impractical in our large-scale study.

Setup.Following Morris et al. [29], we predict the class of an unlabeled graph by classifying its center. In particular, we produce the graph center by using mean pooling to take the arithmetic mean of node embeddings in a graph. To compare efficiency in space use, we conduct experiments in three spaces with the same dimension size of 36, namely \(\mathbb{R}^{36}\), \(\mathbb{H}^{36}\) and \(\text{SPD}_{8}\), the smallest dimension

Figure 4: Comparison of 6d and 15d spaces on Disease. \(\text{SPD}_{5}\) has 15 dimensions.
size in the grid search from Morris et al. [29]. We report the mean accuracy and standard deviation of graph classification results under 10 runs, and provide training details in Appendix 0.A.

Results.Figure 5 shows the accuracy results of a graph classification task in three geometries across five datasets on five GNNs, see also Table 8. Figure 6 shows the distribution of \(\delta\)-hyperbolicity over instances. We see that \(\text{SPD}_{8}\) achieves better or similar accuracy than its counterparts of the same dimenison in all cases except Cheb on COX2 and GIN on ENZYMES. On the AIDS dataset, SPD achieves much better accuracy across all GNNs, and on ENZYMES SPD achieves much better accuracy on SGC.

We also observe that hyperbolic space does not yield much increased accuracy over Euclidean space in most cases, except the AIDS data set. Furthermore, SPD significantly outperforms hyperbolic space on the AIDS dataset but not the COX2 data set. Both of these datasets have the property that almost all instances are tree-like (\(\delta\leq 1\)) (see Figure 6), but the hyperbolicity constants are less concentrated in the AIDS dataset than in the COX2 dataset. It is possible that the flexibility of SPD explains the increased performance over hyperbolic space in this case. For example, SPD admits totally geodesic submanifolds isometric to hyperbolic spaces of varying constant curvatures. It would be interesting to find out, for example, if these graphs of different hyperbolicity constants stay near copies of hyperbolic space of different curvatures.
Figure 7 (a) depicts the case when the ambient geometry is Euclidean. In this example, nodes from the pink, blue and green classes are well-separated but the nodes in red and orange cannot be easily distinguished. Figure 7 (b) depicts the case when the nodes are embedded in the Poincare ball model of hyperbolic space. In the x-z plane five classes are well-separated, including the red and orange classes. Figure 7 (c) depicts the case when the nodes are embedded into SPD where the best class separation is achieved. Indeed, the Cora graph has hyperbolicity constant \(\delta=11\), so one cannot expect it to embed well into hyperbolic space.

Training TimeAs a case study on the impact of the choice of the latent space geometry on the training time of GNN models, Figure 8 compares the training efficiency of three graph neural networks on Citeseer across three 6-dimensional manifolds: \(\mathbb{R}^{6}\), \(\mathbb{H}^{6}\), and SPD\({}_{3}\). Overall, we see that models with Euclidean latent spaces needed the least amount of training time, but produced the lowest accuracy.

Figure 6: Distributions of \(\delta\)-hyperbolicity on four graph classification datasets, where each instance consists of one graph. Y-axis shows the number of graphs for a given \(\delta\)-hyperbolicity on X-axis.

Figure 7: Vizualizations of the node embeddings into three 6-dimensional geometries for SGC on the Cora dataset. In each space, the nodes are vectorized and then projected linearly to \(\mathbb{R}^{3}\) via PCA.
Moreover, hyperbolic space slows down the training in Euclidean space by up to four times, and the effect on accuracy is either slightly positive or negative. For instance, using hyperbolic space with the SGC architecture only brought small accuracy improvements, while applying it to GCN resulted in a drop in accuracy. On the other hand, even though SPD models require nearly double the training time of hyperbolic models, the SPD models bring big improvements in accuracy, not only on Citeseer in the current study case, but also on many datasets such as AIDS and PROTEINS (see Figure 5). We note that the longer training times for SPD models can be attributed to the involvement of eigendecompositions. However, the benefits of using SPD space in graph neural networks appear to outweigh this drawback.

ClassifiersOur three classification layers are built upon traditional classification methods. LINEAR-XE and SVM-MM are both linear classifiers that separate classes with hyperplanes, differing in the choice of loss functions: cross-entropy and multi-margin loss. In contrast, NC-MM layer learns class-specific centroids and then determining the class of an unlabeled node (or graph) by examining which centroid it is closest to according to a similarity function.

Table 2 shows the usefulness of our classifiers in SPD on Citeseer and Cora. Overall, we see that the MM-based classifiers (SVM-MM and NC-MM) are often helpful, outperforming Linear-XE in SPD, and when they succeed, their improvements are substantial. This means the benefits of using SPD and these advanced classifiers are complementary, resulting in stacked performance gains. This is an important finding as it hints at the possibility of accommodating more advanced classification methods recently developed in Euclidean space, when constructing graph neural networks in SPD. Note that the results on other datasets are similar, which we present in Appendix D and E.

Figure 8: Evaluation of three 6-dimensional spaces across graph neural networks in terms of training time and accuracy on Citeseer (\(\delta=5.0\)). Each point has a unique pattern that combines color and shape. For instance, a red triangular means GCN in SPD.
## 6 Conclusions

This work brings sophisticated geometric tools to graph neural networks (GNNs). Following the maxim 'complex data requires complex geometry', we leverage the flexibility of the space of symmetric positve definite (SPD) matrices to construct GNNs which do not require careful prior knowledge of graph topologies. This is a distinct advantage over familiar spaces such as Euclidean, spherical or hyperbolic geometries, where only narrow classes of graphs embed with low distortion.

To operate GNNs in SPD, we designed several building blocks, and developed a library (SPD4GNN) that enables training five popular GNNs in SPD, Euclidean and hyperbolic spaces. Our results confirm the strong connection between graph topology and embedding geometry: GNNs in SPD provide big improvements on graph datasets with multi-modal structures, with their counterparts in hyperbolic space performing better on strictly tree-like graphs.

Determining the optimal classifier for training GNNs in the complex geometry of SPD is challenging, and presents an avenue for continued improvement. This work only begins the process of designing geometrically meaningful classifiers and identifying the conditions which guarantee good performance. Additional performance gains may come through careful implementation of the computationally demanding functions in SPD. While this work contains techniques for accelerating computations in SPD, further optimization is likely possible.

Constructing tools to aid the interpretability of SPD embeddings is an important direction of future work, including quantitative measures for (a) comparing the geometry of the learned embeddings to the real-world graphs' topology and (b) understanding how the geometric features of SPD are leveraged in for graph tasks. While the results of this current work suggest some of SPD's superior performance may be due to graphs of varying hyperbolicity finding geometric subspaces optimally adapted to their curvature, such measures would enable the precise quantitative analysis required for verification.

\begin{table}
\begin{tabular}{l|c|c c c} \hline \hline  & \(\mathbb{R}^{6}\) & \multicolumn{4}{c}{SPD\({}_{3}\)} \\  & Lin-XE & Lin-XE & SVM-MM & NC-MM \\ \hline GIN & 48.2 \(\pm\) 6.3 & **68.0**\(\pm\) 1.3 & 67.3 \(\pm\) 1.2 & 67.0 \(\pm\) 0.8 \\ SGC & 62.6 \(\pm\) 3.4 & 69.4 \(\pm\) 1.0 & **69.7**\(\pm\) 0.8 & 67.9 \(\pm\) 1.5 \\ Cheb & 63.2 \(\pm\) 2.1 & 54.6 \(\pm\) 10.4 & 61.4 \(\pm\) 4.4 & **64.0**\(\pm\) 2.3 \\ GAT & 55.0 \(\pm\) 5.2 & 67.3 \(\pm\) 1.7 & **69.2**\(\pm\) 0.7 & 68.1 \(\pm\) 1.1 \\ GCN & 64.7 \(\pm\) 2.3 & **69.9**\(\pm\) 0.8 & 69.2 \(\pm\) 0.8 & 68.2 \(\pm\) 1.0 \\ \hline GIN & 77.1 \(\pm\) 1.0 & **79.9**\(\pm\) 0.6 & 79.5 \(\pm\) 0.6 & 78.8 \(\pm\) 1.0 \\ SGC & 75.7 \(\pm\) 3.6 & 81.5 \(\pm\) 0.9 & **81.8**\(\pm\) 0.3 & 81.1 \(\pm\) 0.6 \\ Cheb & 71.9 \(\pm\) 2.8 & 75.5 \(\pm\) 3.9 & 77.9 \(\pm\) 2.4 & **79.2**\(\pm\) 1.3 \\ GAT & 67.9 \(\pm\) 4.2 & 79.4 \(\pm\) 0.9 & **81.2**\(\pm\) 1.4 & **81.2**\(\pm\) 1.1 \\ GCN & 78.1 \(\pm\) 1.7 & 79.7 \(\pm\) 0.9 & **80.7**\(\pm\) 0.5 & 80.2 \(\pm\) 1.3 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison of different classifiers on Citeseer (top) and Cora (bottom). We bold the best accuracy in each row.
## 7 Ethical Considerations

We have not identified any immediate ethical concerns such as bias and discrimination, misinformation dissemination, privacy issues, originating from the contributions presented in this work. However, it is important to note that our SPD models use computationally demanding functions, such as determining eigenvalues and eigenvectors, which may incur a negative environmental impact due to increased energy consumption. Nevertheless, SPD models do not outsuffer Euclidean and hyperbolic counterparts in terms of computational overhead. This is because Euclidean and hyperbolic models would require substantial computing resources when dealing with larger dimensions, a necessity for compensating for the challenges of embedding complex graphs into these ill-suited spaces.

## Acknowledgements

We thank Anna Wienhard and Maria Beatrice Pozetti for insightful discussions, as well as the anonymous reviewers for their thoughtful feedback that greatly improved the texts. This work has been supported by the Klaus Tschira Foundation, Heidelberg, Germany, as well as under Germany's Excellence Strategy EXC-2181/1 - 390900948 (the Heidelberg STRUCTURES Cluster of Excellence).
