Pseudo-Riemannian Graph Transformer

We would like to thank Reviewer AG9m for the constructive comments, we would like to address the raised weaknesses and questions as below:

Weakness 1:

(a) Establishing a theoretical proof for model properties in non-Euclidean spaces remains an open research problem, especially in the context of pseudo-Riemannian geometry. Nevertheless, among existing pseudo-Riemannian approaches, our method stands out as the most effective in both interpreting the behavior of pseudo-hyperboloids and identifying optimal configurations for the input data. In our Experiments (Section 6 in the main paper), the promising performance of $Q$-GT and $Q$-GCN2 provides evidence of their effectiveness in capturing and preserving cyclical and hierarchical patterns within an input graph. For example, on spherical datasets such as Cora and Arxiv, both models outperform existing baselines across downstream tasks. Additionally, the visualizations in Figure 3 (Section 6) and Figure 5 (Appendix H.3) highlight their capability to differentiate between high-order and low-order nodes, effectively capturing the underlying hierarchical organization.

(b) In pseudo-hyperboloid $Q_{\beta}^{p,q}$, geodesic disconnection occurs when no smooth geodesic exists between two points $x, y$, resulting in an undefined logarithmic map [1], [2]. As a result, pseudo-Riemannian methods are unable to project graph data onto the tangent space to perform graph operations, as is commonly done in hyperbolic models. Our approach conducts an extrinsic mapping $\Phi$ and a diffeomorphism $\Psi$ to transform the pseudo-hyperboloid $Q_{\beta}^{p,q}$ into the product of spherical and hyperbolic manifolds, each of which is geodesic connected—meaning any pair of points is joined by a smooth geodesic path. Our method operates directly on the product manifold, enabling better preservation of embedding quality while reducing computational complexity.

Weakness 2:

(a) We respectfully disagree with the opinion that our work mainly focus on GNNs. In fact, our study gives balanced attention to both GNNs and Transformer-based models. This is evident from the baseline selection, excluding $Q$-GCN2 (which is also our proposed method), the number of GNN and Transformer baselines is equal. Furthermore, SGFormer and HypFormer are among the strongest baselines in Euclidean and hyperbolic spaces, respectively. Our ablation study focuses on $Q$-GCN because it represents the most recent and directly relevant pseudo-Riemannian GNN approach. During the rebuttal phase, we extended our comparisons by including the Transformer-based method FPS-T and conducting additional ablation studies across both GNN and Transformer models in Tables 1, 2, and 3 (in response to Reviewer 8CPi). These results further validate the effectiveness of our proposed approach.

(b) As discussed in Weakness 1a, both $Q$-GT and $Q$-GCN2 demonstrate strong performance on real-world datasets characterized by mixed topological structures across multiple downstream tasks. To assess their ability to capture hierarchical patterns, we introduce tree-structured datasets in Appendix H.3. The resulting visualizations reveal distinct clustering of low-level nodes, indicating that both models effectively preserve the hierarchical nature of the data. However, conducting more in-depth experiments to illustrate how the models capture spherical and hyperbolic patterns is currently limited by the lack of advanced visualization tools for pseudo-Riemannian spaces, which remains as an open research challenge. As part of future work, we plan to develop a dedicated pseudo-Riemannian visualization tool to further explore and explain the geometric behavior of $Q$-GT and $Q$-GCN2.

Question 1:

The term $x_0$ refers to the first coordinate of a point $x = (x_0, x_1, ..., x_{n-1}) \in \mathbb{R}^n$. In line 99, $x_0$ appears within the context of the Lorentz model for hyperbolic space, where the first coordinate is required to be positive. In contrast, in Equation (2), $x_0$ is part of the definition of the zero-first submanifold $\hat{Q}_{\beta}^{p,q+1}$, which imposes the condition that the first coordinate of any point $x$ on the zero-first submanifold must be zero. The definition of the "zero-first submanifold" is central to our work, as it serves as an intermediary space that enables the decomposition of the pseudo-hyperboloid into a product of spherical and hyperbolic manifolds. This submanifold also facilitates the definition of our pseudo-hyperboloid vector addition.

Question 2:

We explain how our diffeomorphic framework address the geodesic disconnection issue in our above response in Weakness 1b. The extrinsic function $\Phi$ and the diffeomorphism $\Psi$ transform a pseudo-hyperboloid $Q_{\beta}^{p,q}$ into the product of spherical and hyperbolic manifolds. Both spherical and hyperbolic manifolds are geodesic connected in our work, which enables either tangent space projection or direct learning on the manifolds. As stated in the Introduction (Section 1), our diffemorphism effectively addresses the issue of geodesic disconnection and preserves the cyclical and hierarchical structures of graphs.

Question 3:

We would like to thank you for your feedback.

In Equation (4), the variable $x$ denotes a point on the zero-first submanifold $\hat{Q}_{\beta}^{p,q+1}$ , where the first coordinate $x_0$ is constrained to be zero.

The next $q+1$ coordinates are represented by $u = (x_1, ..., x_{q+1})$, and the remaining $p$ coordinates by $v = (x_{q+2}, ..., x_{q + p + 1})$.

Meanwhile, the notation $z = (u', v')^T$ refers to a point on the product manifold , composed of two components $u' \in \mathbb{S}^q_{|\beta|}$, $v' \in \mathbb{L}^{p}_{\beta}$.

The point $z$ can be interpreted as the corresponding representation of $x$ on the product manifold.

Question 4:

We do not agree that Theorem 1 is straightforward and we would like to emphasize that this work is the first to decompose pseudo-Riemannian manifold into the product of spherical and hyperbolic spaces. Importantly, the transformation from a pseudo-hyperboloid $Q_{\beta}^{p,q}$ to the product space of spherical and hyperbolic manifolds cannot be done directly; it requires an extrinsic mapping to ensure the existence of a valid diffeomorphism. According to differential geometry theory, a diffeomorphism between two manifolds $A$ and $B$ exists only if both share the same dimensionality [3]. For any pair of points on a pseudo-hyperboloid—regardless of whether they are geodesic disconnected—the diffeomorphic transformation ensures that they become connected by both a spherical and a hyperbolic paths due to the connection property of the product space. However, a geodesic in a pseudo-hyperboloid corresponds to only one of three geometric types (hyperbolic, flat, or spherical) [1], [2]. Therefore, it is counterintuitive to assume that a single geodesic in a pseudo-hyperboloid composed of both hyperbolic and spherical paths in the product space. This is precisely why we do not use the distance metric defined in the product space. Instead, we rely on the intrinsic geodesic distance of the pseudo-hyperboloid, particularly in link prediction task. We appreciate your suggestions for further clarification and expansion of the theoretical contributions in our work. We propose an alternative and promising direction for theoretical analysis of our diffeomorphic framework is to examine how specific geometric relationships are preserved in the product space. For instance, given a pair of nodes connected by a hyperbolic geodesic in the pseudo-hyperboloid, one could investigate how this relationship is represented after mapping to the product space, and whether the hyperbolic component contributes more significantly to model performance than the spherical one.

Paper Formatting Concerns:

Thank you for your suggestion on the paper formatting. We will change the punctuation mark in line 119 and update the page numbers for references in the next version. We would also revise the formatting issues in Equations (9)–(12) in the paper as suggestion.

[1] Law, M. T.; Stam, J. "Ultrahyperbolic Representation Learning". Neural Information Processing Systems. (2020).

[2] Law, M. T. "Ultrahyperbolic Neural Networks". Neural Information Processing Systems. (2021).

[3] Joel W. Robbin, Dietmar A. Salamon. "Introduction to Differential Geometry" book, p413 (2024).

Thank you for your encouraging feedback. We would like to address the weakness points as below:

Weakness 1:

We’re pleased to hear that you value the elegance of our contributions to graph learning in pseudo-Riemannian geometry. In line 47, we mentioned the concepts of space and time dimensions of pseudo-Riemannian manifolds. A more detailed explanation is provided in Section 2 (lines 97–98). Given a point $x=(x_0, x_1, ..., x_{q}, x_{q+1}, ..., x_{q+p})$ on the pseudo-hyperboloid $Q_{\beta}^{p,q}$ , the first $q + 1$ coordinates $(x_0, x_1, ..., x_q)$ correspond to time dimensions, while the remaining $p$ coordinates $(x_{q+1},..., x_{q+p})$ represent space dimensions. The concepts of time and space dimensions originate from Einstein’s general theory of relativity which described the four-dimensional spacetime. The time and space dimensions are formalized within the framework of pseudo-Riemannian geometry[1], then widely adopted in pseudo-Riemannian learning methods [2], [3], [4]. However, finding the appropriate time and space dimensions that align with the graph structure is a non-trivial and time-consuming task as it requires extensive training if done manually. To address this challenge, we introduces an automated space searching algorithm that efficiently discovers optimal pseudo-Riemannian configurations based on the Gaussian Sectional Curvature. This significantly reduces manual effort and improves model performance.

[1] O’neill, B. V. "Semi-Riemannian Geometry With Applications to Relativity", 54 (1983).

[2] Law, M. T.; Stam, J. "Ultrahyperbolic Representation Learning". Neural Information Processing Systems. (2020).

[3] Law, M. T. "Ultrahyperbolic Neural Networks". Neural Information Processing Systems. (2021).

[4] Xiong, B.; Zhu, S.; Potyka, N.; Pan, S.; Zhou, C.; Staab, S. "Pseudo-Riemannian Graph Convolutional Networks". Neural Information Processing Systems. (2021).

We would like to thank Reviewer 8CPi for the constructive comments, we would like to address the raised weaknesses and questions as below:

Weakness 1:

We sincerely thank you for suggesting the Lorentzian residual connection [1]. In contrast to our pseudo-hyperboloid addition in Section 4, this approach performs entirely within the hyperbolic manifold, eliminating the need for tangent space. However, adapting the Lorentzian residual connection to pseudo-hyperboloids $Q_{\beta}^{p,q}$ requires extending it to product manifolds, which presents a non-trivial challenge. Building upon the definition of Lorentzian residual connection [1], we propose the following (straightforward) extension:

$$w_1 x \oplus_{\beta} w_2 y = \left( \frac{\sqrt{|\beta|}(w_1 u_1 + w_2 u_2)}{|| w_1 u_1 + w_2 u_2 ||},\ \frac{\sqrt{|\beta|}(w_1 v_1 + w_2 v_2)}{\left| \left| w_1 v_1 + w_2 v_2 \right| \right|_{\mathbb{L}}} \right)$$

where $w_1, w_2$ are the weights, $x = (u_1, v_1)^T$, and $y = (u_2, v_2)^T$ are two points in the product space of spherical and hyperbolic manifolds. The work in [1] proved that the denominator in hyperbolic part $| || w_1 v_1 + w_2 v_2 ||_{\mathbb{L}} |$ has a positive lower bound when the weights are positive. However, this property does not hold for the spherical denominator $|| w_1 u_1 + w_2 u_2 ||$, whose value can range from $0$ to $+\infty$ for any choice of $w_1$, $w_2$. To eliminate numerical instability in the spherical case, additional constraints may be required but potentially increasing computational complexity. On the other hand, our pseudo-hyperboloid vector addition maintains feature integrity, thereby improving the model’s learning capacity over prior pseudo-Riemannian approaches.

Weakness 2:

Table 1. Comparison to FPS-T in node classification results (F1-score).

Table 2. Comparison to FPS-T in link prediction results (ROC AUC, %).

Similar to $Q$-GT, FPS-T [2] is a graph Transformer designed for graphs with mixed structural properties, which becomes the concerns of the reviewers. FPS-T operates in a product space of Riemannian stereographic manifolds $\lbrace st^{i} \rbrace^{H}_{i=1}$, where each component $st^{i}$ has a trainable curvature $\kappa_i$ that can be positive, negative, or zero. To address this concern, we conduct a comparative evaluation of $Q$-GT and FPS-T on both node classification and link prediction tasks, with the results presented in Table 1 and Table 2. For fairness, we set $H=2$ since our product space also has two components. First, FPS-T incurs significant computational overhead due to the use of tangent mappings and the costly computation of Laplacian eigenvectors. As a result, it runs out of memory on three large-scale datasets: Arxiv, Penn94, and Twitch Gamers. Second, the model's trainable curvatures $\kappa_i$ fail to converge to optimal values. On node classification tasks for Cora and Citeseer, FPS-T underperforms compared to $Q$-GT. Specifically, the learned curvatures $(\kappa_1, \kappa_2)$ converge to $(0.023, 0.025)$ on Cora and $(0.008, 0.007)$ on Citeseer, which do not reflect the hyperbolic geometry. In contrast, $Q$-GT benefits from operating directly on the product of spherical and hyperbolic manifolds, which is diffeomorphic to the pseudo-hyperboloid, thereby enhancing its performance.

Weakness 3:

To address concerns about the computational cost of $Q$-GT, we provided a detailed complexity comparison in Table 4 and Table 5 below (in response to Reviewer V9gp). In terms of runtime, $Q$-GT requires significantly more time than SGFormer and HypFormer. However, its memory usage is comparable to these models on the Cora and Pubmed datasets. Notably, on Penn94, $Q$-GT achieves the lowest memory consumption among all baselines. We also evaluated $Q$-GT against strong baselines on larger datasets (Products and Vessel from the Open Graph Benchmark) as reported in Table 3. While $Q$-GT is indeed more demanding in terms of both runtime and memory, it delivers substantially superior performance compared to SGFormer and HypFormer, demonstrating the value of the proposed geometric framework.

Weakness 4:

Table 3. Comparison on Open Graph Benchmark (OGB) datasets.

To further assess the scalability of our model, we conducted additional evaluations of $Q$-GT and other strong baselines on two recommended datasets from the Open Graph Benchmark: 'ogbn-products' (Products) and 'ogbl-vessel' (Vessels), where the results are shown in Table 3. All experiments were performed with all Transformer models configured with 1 layer, GNNs with 3 layers, and training conducted over 200 epochs. It is obvious that $Q$-GT achieves the highest performance on both datasets, outperforming the strongest baselines by 7.3% on Products and 32.09% on Vessel. However, as shown in Table 4 and Table 5, $Q$-GT introduces higher computational and memory costs compared to other baselines. We recognize this as a limitation of our current approach and plan to investigate more efficient solutions in future work.

Weakness 5:

As depicted in Figure 3 (Section 6 in the main paper), high-level nodes appear more scattered, forming several small clusters that include only a few low-level nodes, suggesting the presence of localized hierarchical patterns. However, the overall hierarchical structure is not clearly visible in this visualization, because the Cora dataset lacks a well-defined hierarchy, as reflected by its Gaussian Sectional Curvature (GSC) distribution, which tends to be more spherical. To better illustrate the model's ability to capture hierarchical structure, we introduce three synthetic tree-structured datasets in Appendix H.3. The visualizations of these datasets reveal distinct clusters of low-level nodes (represented by red and pink) in $Q$-GT and $Q$-GCN2, demonstrating the hierarchy of the datasets. Additionally, we compare to hyperbolic baseline, Hypformer on these tree datasets. Hypformer achieves average AUC scores of 95.10, 92.37, and 91.06 on Tree-1, Tree-2, and Tree-3, respectively. These results are comparable to $Q$-GT and $Q$-GCN2 , further confirming that both models are effective in capturing and representing hierarchical structures.

Weakness 6:

We appreciate your feedback and will update the terminology in the next version of the paper. The term "geodesic disconnection" is originated from the work $Q$-GCN.

Question 1:

We discussed about extending Lorentzian residual connection [1] in our reply in Weakness 1. We concluded that adapting Lorentzian residual connection to product space is a non-trivial challenge due to the numerical instability in spherical denominator.

Question 2:

Given the final representations of $Q$-GT and $Q$-GCN2, we first apply our diffeomorphic mapping to transform them into the product space and extract the hyperbolic components. We then use hyperbolic UMAP with 'output_metric=hyperboloid' to embed these features into a 2D hyperboloid. In Figure 3 (Section 6 in the paper), we further project these hyperbolic outputs onto the Poincaré disk, since the original embeddings lie in a 2D hyperboloid space. In contrast, for the tree datasets shown in Appendix H.2, we directly visualize the hyperbolic UMAP outputs without projection to the Poincaré disk, as this yields clearer visualizations. We avoid applying the logarithmic map before UMAP, as tangent space mappings can introduce distortions in the quality of the hyperbolic embeddings [1].

[1] He, Neil, Menglin Yang, and Rex Ying. "Lorentzian residual neural networks." arXiv preprint arXiv:2412.14695 (2024).

[2] Cho, Sungjun, et al. "Curve your attention: Mixed-curvature transformers for graph representation learning." arXiv preprint arXiv:2309.04082 (2023).

We would like to thank Reviewer V9gp for the constructive comments, we would like to address the raised weaknesses and questions as below:

Weakness 1:

We agree with Reviewer V9gp that our work requires the assumption of a linear relationship between the ideal standard deviation $\sigma_i$ and the space dimension $p_i$. In general, the ideal standard deviation can be modeled as any bijective function of $p_i$, such as a quadratic function $p_i^2$ or an exponential form $e^{p_i}$, as long as it aligns with the curvature behavior of the three geometric settings (i.e., monotonically increasing in spherical space and inversely related in hyperbolic space; see Appendix C.3 for details).
However, using alternative forms like the quadratic $p_i^2$ results in a steeper rate of change, which may lead to suboptimal manifold selection. To clarify this hypothesis, we define the ideal standard deviation $\sigma_i$ using a quadratic formulation as follows:

$$\sigma_i = \begin{cases} \sigma_{\text{max}} - (\sigma_{\text{max}} - \sigma_{\text{min}}) \left(\frac{2p_{i} - (d + 1)}{d-3} \right)^2 & \text{if $ (d-1)/2 < p_i \leq d-1$} ; \\ 1 & \text{if $p_i = (d-1)/2$} ; \\ \sigma_{\text{min}} + (\sigma_{\text{max}} - \sigma_{\text{min}}) \left(\frac{2p_{i}}{d-3} \right)^2 & \text{if $ 0 \leq p_i < (d-1)/2$}. \end{cases}$$

Then we apply the space searching algorithm in Section 5 to four benchmark datasets: Cora, Citeseer, Airport, and Pubmed. The resulting space dimensions are $p_i = 4, 7, 2, 4$, respectively. However, when compared to the configurations shown in Fig. 2 (Section 6) and Fig. 4 (Appendix H), these values do not correspond to the optimal configurations for pseudo-hyperboloids. This suggests that the assumption of a linear rate of change in standard deviation aligns well with the variation in space dimension $p_i$. While further theoretical justification is needed, our experimental results provide strong evidence that the linear assumption is effective in practice. A more detailed theoretical analysis would require a proper model of the underlying graph manifold in real world dataset, which can be considered as a future work.

Weakness 2:

Table 4. Comparison of training time (in seconds).

Table 5. Comparison of GPU memory usage (in MiB).

In our paper, we provided a runtime comparison of three pseudo-Riemannian models in Appendix H.2. To offer a more comprehensive complexity analysis, we further evaluate the runtime and memory usage of $Q$-GT against strong baselines, including SGFormer, HypFormer, and $Q$-GCN, as suggested in Question 1. The detailed results are presented in Table 4 and Table 5. A comparison between $Q$-GCN and $Q$-GCN2 shows that our diffeomorphic framework achieves better efficiency in both runtime and memory. This is because $Q$-GCN framework relies on a combination of diffeomorphic and tangent space mappings in product manifolds, whereas our approach operates directly within the product manifold space. Nonetheless, $Q$-GT incurs higher computational and memory overhead compared to GNNs, SGFormer, and HypFormer, particularly on large-scale datasets like Products and Vessel. We attribute this overhead to Transformer components such as linear attention, the refining function, and residual connections, which we recognize as a limitation of our method. However, this trade-off enables $Q$-GT to deliver strong performance on large datasets, as shown in Table 3. $Q$-GT delivers the best performance across both datasets, surpassing the strongest baselines by 7.3% on Products and 32.09% on Vessels. We are optimistic that future work can further reduce the model’s complexity and retain its effectiveness.

Weakness 3:

We would like to clarify that our space searching algorithm is introduced to identify optimal pseudo-Riemannian manifolds for graph embedding. While it may incur higher computational costs on large graphs, it is significantly more efficient than the brute-force approach used in prior works such as $Q$-GCN (see Section H.2 for runtime comparison). In node classification and link prediction tasks, we compare the results of all pseudo-Riemannian methods ($Q$-GCN, $Q$-GCN2, and $Q$-GT) using the manifold configurations computed by our algorithm. To ensure fairness, we also perform a brute-force search over all manifold configurations on four benchmark datasets—Airport, Cora, Citeseer, and Pubmed (see Figure 2 in Section 6 and Appendix H.1). The results reveal that $Q$-GCN's chosen manifold does not align with the outcome of our space search algorithm or the intrinsic topology of the input graph, and it fails to outperform $Q$-GCN2 and $Q$-GT on the optimal pseudo-hyperboloid.

Question 1:

We provided a complexity comparison in Table 4 and Table 5, as discussed in Weakness 2. Overall, $Q$-GT introduces higher computational and memory costs compared to other baselines. We acknowledge this as a shortcoming and intend to explore solutions in future work.

Question 2:

We understand that scalability is a key concern for Transformer-based models. To evaluate this, we tested our $Q$-GT and other Transformers on larger datasets from the Open Graph Benchmark, with the results reported in Table 3 above (in response to Reviewer 8CPi). Additionally, runtime and memory comparisons with other baselines are provided in our reply in Weakness 2. Although $Q$-GT incurs high computational complexity, this trade-off results in notably strong performance of $Q$-GT. We recognize that improving the complexity of $Q$-GT remains an important direction for future work.

Question 3:

The most critical component of QGT is the diffeomorphic mapping, which transforms the pseudo-hyperboloid into a product space of spherical and hyperbolic geometries. The diffeomorphic framework enables a more interpretable evolution of the pseudo-hyperboloid $Q_{\beta}^{p,q}$, leading to our efficient space searching algorithm for determining the optimal pseudo-hyperboloid. By addressing the issue of geodesic disconnection, it facilitates the adaptation of standard architectures (e.g., GNNs and Transformers) to pseudo-Riemannian spaces. Moreover, by preserving both spherical and hyperbolic characteristics, the diffeomorphic mapping contributes to improved performance in graph learning tasks. Additionally, other components such as linear attention, the refining function, and residual connections also play a crucial role in the success of $Q$-GT.

To interpret the learned embeddings, we employ the UMAP tool for visualization. For instance, in Appendix H.3, we visualize the embeddings of tree-structured datasets on the hyperbolic component of the product space. The visualizations reveal that in $Q$-GCN2 and $Q$-GT, red and pink nodes—corresponding to lower-level nodes—form distinct clusters, indicating that hierarchical information is effectively preserved. In contrast, $Q$-GCN exhibits oversmoothing, where embeddings of low-level and high-level nodes become indistinguishable, suggesting a loss of hierarchical structure.