Hgformer: Hyperbolic Graph Transformer for Collaborative Filtering

Q: The two key problems addressed in the paper have already been extensively studied in previous works.

A: Thank you for pointing out these issues. As you mentioned, these two problems have indeed been discussed in prior works, and we have acknowledged these discussions in our Introduction section. However, as we emphasize, these challenges remain unresolved in the recommendation domain. Specifically, as demonstrated in Section E.1 of the Appendix, our proposed method addresses long-tail problems better than previous approaches. Moreover, simultaneously tackling both issues is non-trivial, and as highlighted in the Challenges parts of our Introduction, there are still significant difficulties that need to be overcome. Additionally, extending kernel functions to hyperbolic space to enable the application of hyperbolic transformers in recommendation is a novel approach.

Q: The combination of hyperbolic space and transformers has also been explored.

A: Thank you for pointing out the issue. We have also noted the paper "Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Space" and discussed the key difference in the Related Works section, which can be summarized as:

1. They focus on node classification, whereas our Hgformer is specifically tailored for collaborative filtering.
2. We propose LHGCN for effective local structure modeling in hyperbolic space, which is not explored in their work.
3. To achieve linear computational complexity, Hypformer first swaps the multiplication order of space-like values in self-attention vectors and then recalibrates the time-like values. In contrast, we adopt the cross-attention for better performance in CF tasks and directly extends the kernel function to hyperbolic space, which has a theoretical guarantee in approximation errors.

Overall, we are the first to propose a hyperbolic graph transformer in the context of collaborative filtering.

Q: Using hyperbolic space introduces additional computational overhead. Is this trade-off justified? How does the computational cost of the proposed method compare with existing approaches?

A: Thanks for your question. The operations in hyperbolic space do not differ significantly from those in Euclidean space in terms of computational complexity. The main parts of our model include LHGCN and Hyperbolic Graph Transformer. For LHGCN parts, In Section 2.2, we define the convolution in hyperbolic space by

$$\mathbf{u}_i^{(l+1)} = \mathbf{Centroid}\bigl(\{\mathbf{u}_i^{(l)}, \{\mathbf{i}_k^{(l)} : k \in N_i\}\}\bigr)$$

and $\mathbf{i}_j^{(l+1)} = \mathbf{Centroid}\bigl(\{\mathbf{i}_j^{(l)}, \{\mathbf{u}_k^{(l)} : k \in N_j\}\}\bigr).$

According to Definition B.7 in Appendix B, the above Centroid formula still yields an overall complexity $O(|E| \times d)$ for an entire pass over the graph, where $|E|$ is the number of edges and $d$ is the embedding dimension and we find that the computational complexity is similar to that of the LightGCN convolution process.

The complexity of the Hyperbolic Graph Transformer is detailed in Figure 3 in our paper and we can find that it is consistent with that of the NodeFormer, which is a graph transformer model in Euclidean space and is capable of dealing large-scale graphs. Hence, the hyperbolic variant retains the same order of computational complexity as its Euclidean counterpart.

Q: The hyperparameter settings for the baseline models are not specified in the paper.

A: Thanks for pointing out the problem. Below we provide the hyperparameter tuning ranges for baselines.

Q: Empirical validation of training/inference time on large-scale data is missing.

A: Thank you for pointing this out. We have conducted empirical evaluations and reported the average computational time per epoch for several representative baselines and our proposed model on Amazon Book (our largest dataset) and Amazon Movie. In each cell, the first value represents the training time per epoch, while the second value represents the testing time.

Q: Limited comparison with 2023–2024 hyperbolic CF models. How does Hgformer compare to recent hyperbolic CF methods in terms of performance and scalability?

A: Thank you for pointing out the issue. We have looked into recent literature from 2023–2024 and plan to include HyperCL[1], which extend contrastive learning into hyperbolic space and applied it for collaborative filtering, as one of our baselines. The results are as follows:

Q: Has a hyperparameter sensitivity analysis been conducted (e.g., curvature K, m)?

A: Thanks for the question. We provided a sensitivity analysis in Appendix E.2. However, we did not conduct a sensitivity analysis for K and m. We have now supplemented our work with an analysis for these two hyperparameters, and the results can be found at the link below. https://anonymous.4open.science/r/Hgformer-2AE0/sensitivity_analysis_rebuttal.pdf

Q:Can you clarify the negative sampling strategies used for the margin-ranking loss?

A: We adopted the default approach provided by the RecBole framework. Specifically, negative samples were uniformly drawn from items with which the user had no previous interaction. To ensure a fair and consistent comparison across different methods, all baselines utilizing negative sampling followed this same strategy and pair each positive sample with exactly one negative sample.

Q:There is inconsistent formula formatting (e.g., Equation 12 and lines 304–307).

A: Thanks for pointing our this inconsistency! We acknowledge that they can indeed be easily misunderstood. In lines 304–307, the $u^{final}$ and $i^{final}$ are derived from Equation 14, where $u^{global}$ and $i^{global}$ are obtained from Equation 5. Meanwhile, Equation 12 is introduced to reduce the computational complexity of Equation 3 (which leads to Equation 5) to linear complexity. We will add further clarifications in the paper to improve its readability.

References:

[1] Qin Z, Cheng W, Ding W, et al. Hyperbolic Graph Contrastive Learning for Collaborative Filtering[J]. IEEE Transactions on Knowledge and Data Engineering, 2024.

Q: Inconsistency between two aggregation approaches

A: Sorry for the misunderstanding. These two types of aggregation serve different purposes in our model. The aggregation in Section 2.2 indicates gathering neighbor information for each node to capture multi-hop relationships, which is performed in multiple layers—thus, any distortion at this stage would accumulate significantly. In contrast, the aggregation of local and global information in Section 2.4 is simply fusing information from the two representation space for each node, which is a much simpler operation and involves negligible information distortion. In fact, aggregation step in Section 2.4 can be easily replaced by the weighted centroid of two embeddings defined in Definition B4 in the Appendix, and we conducted additional comparative experiments:

We observe that the differences between the two methods are marginal.

Q: Implementations of SGFormer, NodeFormer and Hypformer

A: We adopted the encoder parts of these models straightforwardly and replace their output layers with recommendation-specific modules (For NodeFormer, SGFormer we applied BPR loss, which is the same as LightGCN and NGCF and for Hypformer, we applied Hyperbolic Margin Ranking Loss, which is the same as our hyperbolic baselines). The detailed implementations are publicly available in the anonymized GitHub repository in the Abstract.

Q: Lack of mathematical justification for LHGCN

A: Thanks for pointing out this issue. In the following, we provide a theoretical analysis supporting our claims.

For a set of hyperbolic points $N \subset H^{d+1, K}$, for each point $x_i \in N$, the centroid is defined as the point $c \in H^{d+1, K}$ that minimizes the sum of squared hyperbolic distances:

$Centroid(N) = \arg\min_{c \in H^{d+1, K}} \sum_{x_i \in N} (d^K(c,x_i))^2 = \arg\min_{c \in H^{d+1, K}} f(c).$

Its closed-form solution is given by

$c^* = \sqrt{K} \frac{\sum_{x_i \in N} x_i}{| \sum_{x_i \in N} x_i |_M}.$

Another way is to aggregate at a north pole point $o$

$\bar{c}' = \frac{1}{|N|}\sum_{x_i \in N} log_o(x_i),$

and then map them back:

$\bar{c}^* = exp_o(\bar{c}') = cosh\Bigl(\frac{|\bar{c}'|_M}{\sqrt{K}}\Bigr)o + \sqrt{K},sinh\Bigl(\frac{|\bar{c}'|_M}{\sqrt{K}}\Bigr)\frac{\bar{c}'}{|\bar{c}'|_M}.$

Since $f(c)$ is convex in hyperbolic space (see [1]), it follows that

$f\left(c^*\right) \le f\left(\bar{c}^*\right)$

This means that aggregation in Euclidean space is only a suboptimal solution and will lead to distortion.

Q: Is there validation set? How do authors get the results?

A: Thanks for the questions. To ensure accuracy and fairness in our experiments, all the models were tested on RecBole, a widely accepted framework in the field of recommender systems. The dataset was split into training, validation, and test sets with an 8:1:1 ratio. During training, we adopted an early-stop mechanism for all models, stopping training if no improvement was observed on the validation set for 30 epochs and the best-performing parameters on the validation set were selected for final evaluation on the test set.

Q: No statistical significance tests (t-tests, confidence intervals)

A: We respectfully clarify that we calculate p-values for our experiments, which is depicted in the caption of table 1. Here, we provide the specific p-values and t-values:

Q: Essential References Not Discussed

A: Thanks for pointing out the problem. For "Hyperbolic Attention Networks", "Performers" and "Nyströmformer", we would like to add them into Graph Transformer part in Related Works and for "Causal Intervention for Leveraging Popularity Bias in Recommendation", "SASRec" and "BERT4Rec", we would like to add an extra section in Appendix for discussion.

Reference:

[1]Bacák M. Computing medians and means in Hadamard spaces.