Curve Your Attention: Mixed-Curvature Transformers for Graph Representation Learning

1. In the Related Work section, the authors are missing reference to a fundamental recent paper learning jointly on both hyperbolic and spherical spaces in a unified end-to-end pipeline: KDD 2022: Iyer et al. 2022. Dual-Geometric Space Embedding Model for Two-View Knowledge Graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '22). Association for Computing Machinery, New York, NY, USA, 676–686. https://doi.org/10.1145/3534678.3539350

2. In the Preliminaries, the authors should also provide formulas for the retraction operators including interpretation of the exponential mapping and log mapping operations e.g., why the Euclidean tangent space is needed etc.

3. In the Experiments section, it seems strange that the authors are utilizing synthetic geometric graph datasets, when their motivation was that hierarchies and cycles are commonly found in real-world datasets. As such, the motivation behind using Table 1 needs to be defined better.

4. The novelty of this work is also lacking. Chami et. al, already propose the using of retraction operators (exponential and log mapping that can be generalized to any non-Euclidean geometric space of constant curvature K. Further, product spaces have also already been proposed. Moreover, even integrating both hyperbolic and spherical spaces jointly has been proposed by Iyer et. al. This work just seems to be a combination of all of the above works.

• The motivation for non-Euclidean Transformers is not fully justified. The introduction claims they are necessary for modeling hierarchical and cyclic graphs but does not provide compelling evidence current Euclidean Transformers fail on such structures. More analysis on the limitations of existing methods is needed.

1. The stereographic model limits flexibility compared to input-dependent curvatures. Methods like heterogeneous manifolds (cited in the paper) can adapt curvature per node/edge based on features. Fixing curvature by attention head may be too restrictive. The paper could experiment with more adaptive curvature mechanisms.

2. Scalability is a concern. The largest graph evaluated has only 4,000 nodes and 88k edges. More experimentation on large real-world networks is important to demonstrate practical value.

3. No transformer-based baselines are compared.

4. Ablation studies could provide more insight. For example, how do learned curvatures evolve during training? How sensitive is performance to curvature initialization? Are some attention heads more "non-Euclidean" than others?

• 1. Rather incremental The design of FPS-T is clearly an adaptation of the work of (Bachmann & al, 2020) to transformer-like architectures.
• 2. No theoretical insights There are no significant theoretical analysis that would provide insights on specific features of FPS-T: e.g when graphs whose sectional curvature distribution has a large variance what would be a good constant curvature space (or product of spaces) to discriminate them ?
• 3. Few unclear parts remain:
  • i) I think that equation 4 is wrong: expressions of Q and K seem wrong as a such linear transformation will not embed a stereographic embedding in the tangent space in V. are there missing log_V mappings ?
    • ii) Equation 6 is not clearly explained. Moreover a conformal factor of 1 seems to lead to a ill-defined aggregation function, this point should be clarified by authors.
    • iii) Could you further characterize the resulting function $exp_0( f_{act} (log_0))$ when $f_{act}$ is not differentiable everywhere as the ReLU activation function ?
    • iv) Section 4.5 is not totally clear: I believe that the ‘kernelization’ aims at approximating the softmax activation $\sigma(< Q_i, K_j>)$ not just the inner product $< Q_i, K_j>$ otherwise I do not see the point. Moreover no context is provided w.r.t the current SOTA to reduce the computational cost of transformers.
• 4. Incomplete experiments and analysis:
     • i) Under exploited synthetic experiments: could you provide curvatures for the designed graphs so that we can quantify their correspondences to estimated constant curvatures in FPS-T? Could you perform a sensitivity analysis w.r.t the embedding dimensions and the number of considered heads for both FPS-T and Token_GT?
     • ii) No ablation study w.r.t learning the curvatures instead of taking fixed ones, e.g according to modes of the estimated sectional curvatures. This could be at least considered on the toy datasets.
     • iii) Potential fairness issues in the benchmarks on real-world networks which should be discussed by authors: a) Most of benchmarked methods depend on a considerably fewer hyperparameters and the validation grid seems to considerably differ from original paper, while also fitting transformer-based approaches better. Moreover these methods tend to be considerably faster than FPS-T so fitting original validation grids in the paper seems affordable. Could authors provide performances distributions across validated hyperparameters to get an idea of the method robustness? ; b) Laplacian Eigenvectors are by default included in transforms and no considered for GNNs while there are Spectral augmentation techniques that could also be used.; c) the duality w.r.t hops vs number of layers is clearly different between GNN-based and transformer-based approaches. I would suggest to use e.g Jumping Knowledge concatenation of embeddings for both methods to relax the dependency to a well-chosen validated hyperparameter.
     • iv ) SOTA methods for node classification tasks are not present in the benchmark and clearly seem to outperform FPS-T e.g [A, B]

[A] Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., ... & Precup, D. (2022). Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35, 1362-1375.

[B] He, M., Wei, Z., & Xu, H. (2021). Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34, 14239-14251.