Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: To unify the successes of hyperbolic graph convolutional networks (GCN) in modeling hierarchical structures and spherical manifolds in modeling cycles,
the authors generate a diffeomorphism $\psi$ from pseudo-hyperboloids ( $Q_\beta^{(s,t)}$ with $t+1$ time dimensions and $s$ spatial dimensions) into product manifolds of a sphere and Euclidean space. The special form of this diffeomorphism allows them to formulate expMap, logMap, parallel transport operations and geodesics to avoid broken cases (using antipodal points). The resulting Q-GCNs have learnable layer-wise parameters in Euclidean space and can be used for both graph reconstruction (GR) and link prediction (LP) / node classification (NC) tasks. Q-GCNs outperform competitors such as $\kappa$-GCN's and HGCN's on these tasks on a majority of the datasets (Tables 1 and 2). The authors also conduct a thorough parameter sensitivity analysis and computation time analysis (Tables 5 and 4).

strengths_and_weaknesses: Strengths
1. As summarized above, the approach is motivated quite well both from an intuitive and from a theoretical viewpoint.
2. Q-GCNs outperform competitors such as $\kappa$-GCN's and HGCN's on GR or LP/NC tasks on a majority of the datasets (Tables 1 and 2)
3. The authors also conduct a thorough parameter sensitivity analysis and computation time analysis (Tables 5 and 4).
4. Q-NNs, another variant introduced using the authors' theoretical analysis, outperforms MLPs on NC tasks in Table 3.

Weaknesses

1. Some of the theorems reported by the authors are quite technical and require significant background on pseudo-Riemannian manifolds. But it is not clear how novel these results would be considered in those fields. For instance, is the proof for theorem 2 is significantly novel w.r.t. the proof of theorem 1 in [21] ? It is also not clear why the discontinuous operation in (4) doesn't sacrifice the diffeomorphic property. It's possible parallel transport doesn't require the continuity property, but this isn't explicitly pointed out.

2. The authors do not provide pseudo-code for their training and inference algorithms either in the main body of the paper or in the Appendix.
So it is not entirely obvious to a reader when exactly the antipodal operation described after Theorem 4 or in the bias translation subsection of Sec. 3.2 is applied, although this can be inferred from (6).

3. Error bars are reported in tables 2 and 3, but not in table 1.

questions: The authors mention at the end of the Optimization section that dedicated optimization like [21] would be considered in future work.
What advantage would dedicated optimization provide ?

Please note the questions inherent in Weaknesses 1 and 2 above.

limitations: 
The authors mention that improvements might be necessary for automatically choosing time dimensions of Q-GCNs in Sec. 5
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors extended the graph convolutional networks to the graph representation into pseudo Riemannian geometry. Pseudo-Riemannian geometry was introduced as a possible embedding space for hierarchical graphs and graphs with cycles. As the space is equipped with metric, geodesic, exp and log map, the authors extend the graph convolutional neural network model to such framework. The model performance is showcased on both graph reconstruction data, link prediction and node classification.
strengths_and_weaknesses: The authors focus on an important topic which is the extension of the neural network models to a geometrical framework beyond the Euclidean space or any other Smooth Manifold. Geometrical setting is well introduced and the geometrical tools are well described. They showcase the model in three important tasks related to graph analysis.
The main strengths are: (1) the attention to a careful geometrical embedding of the data (2) a well-structured paper (3) complete experiments.
The main weakness is lack of novelty compare to [21] and the complexity of the framework, which it is not well justified throughout the paper. 

The authors are extending the GNN to the pseudo-Riemannian setting, but the geometrical tools seem to be the one already introduced in [21].  If the main difference is the spherical mapping described in Th. 2, I don't understand why a map preserving the curvature should be preferable to a map with the same properties but with a flat curvature image (which is easier to handle). 
In Section 4, the authors describe how to extend the GNN to the framework by mapping node features (in the Euclidean setting) to the described embedding and then mapping them again into the tangent space (which is flat by definition). Is it a geometrical virtuosism or a necessity? In addition, there is a tangent space approximation centered in the south pole described in section 3.2. The tangent space approximation is a bad approximation of positively curved spaces if there is no ensurance about how the data are concentrated. This step is vague and unclear to me.
Lastly, there should be a stronger justification to the introduction of such complex (and parametric -see time dependence) setting. As there are many different embedding graphs procedure, which are the strenghts of such embedding? This should be better enlightened in both the introduction and the experiments, as not all the reader might be familiar with such embedding.

[21] Law and Stam (2020) Ultra hyperbolic Representation Learning.

questions: Introduction: For a reader without a strong knowledge on graph embedding, it is not very clear the motivation of the work. Why such complex embedding is required for graph embedding? Authors should help the reader understanding the literature gap they are trying to fill, maybe adding a simple example in a sentence.
14 what does it means graphs with different curvature? The curvature of the embedding space? In geometry, the curvature is a property of the metric. This sentence is not so clear as the reader might be more familiar with the metric curvature rather than the graph curvature. Notice that this is an important point to be clarified throughout the paper.
29-30 I don’t understand why the authors cite these examples. Is the spherical embedding another embedding for graphs? If so should be better explained as it is the only other example of non-Euclidean data type for which Neural Networks have been extended.

Section 3 The theory described in Section 3 strongly relies on [21]. I think the novelty should be better enlighten and justified. Is the Theorem 2 needed to extend the GNN? Why?

Subsection 3.2: Tangential Transformation. I don’t understand a tangential approximation in a point should be a good approximation of the data. Especially in the example with positive curved spaces, the tangent space centered in a point could be a bad approximation of your data if there is no ensurance of data concentration. A better justification should be provided.

Experiments: How do the authors justify a 100% mean Average Precision in Table 1?

limitations: The paper is complex and extend the GNN to a pseudo-Riemannian embedding of Graphs. As the geometrical embedding is fully described by [21], the paper should be better framed to justify which geometrical tools are necessary to extend GNN and why this complex framework is needed compared to more intuitive GNN on the Euclidean embedding or Hyperbolic embedding of graphs.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a non-Euclidean GCN based on pseudo-Riemannian geometry. The major idea is to generalise GCN operations including feature transformation and neighbourhood aggregation into pseudo-Riemannian manifolds. Different from Riemannian manifolds such as sphere and hyperboloid, the main challenge is the broken geodesic issue (i.e., there exists broken geodesic for which standard operations are not well defined). The authors propose to use “diffeomorphism operations” to define basic operations like linear transformation and aggregation. Experiment results on three graph learning benchmarks show significant improvements. 
strengths_and_weaknesses: Strengths
1.The authors extended GCN into pseudo-Riemannian manifolds (more specifically, pseudo-hyperboloid) with non-positive definite metric. The motivation is inspired by Marc T. Law, et al. 2020. However, different from Marc T. Law, et al. 2020, the authors propose to generalize the neural network operations into the pseudo-hyperbolic space.
2. The proposed operations and tools seem technical solid. The main non-trivial part is that there exists broken geodesic for which standard manifold operations like expmap and logmap cannot be defined.  The authors propose to map the operations into diffeomorphic manifolds that are easy to operate. The proposed tools might be useful for generalizing other neural models to pseudo-hyperboloid like generative models.
3.Evaluation results on three graph learning tasks are strong enough to show the benefits of the proposed method on embedding graphs, especially when the graphs have mixed curvature.
Weaknesses
There are a few minor issues that could be fixed during the rebuttal 
1. The authors should give enough details of the baselines and explain why choosing them
2. For a given dataset, how to decide the proper settings of time dimension and why choosing those time dimensions (2,4,8,…) in the evaluation is not clear enough

questions: 1.Is it possible to directly perform aggregation in the pseudo-hyperboloid, like using  Frechet mean to simplify the aggregations as done by Y. Zhang, et al. 2021.?
2.The authors use tangent space optimization. Is there any guarantee for doing so? 

[1] Y. Zhang, et al. Lorentzian Graph Convolutional Networks. 2021.
limitations: Yes, the authors have highlighted the limitations of their work in the Broder Impact section
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors extend existing Graph Convolutional Networks (GCNs) on non-Euclidean Riemannian manifolds to a larger class of pseudo-Riemannian manifolds which generalizes hyperboloid and sphere. They extend neural network operations into geodesically disconnected pseudo-Riemann manifolds by developing some new geodesic tools, and derive a pseudo-Riemannian GCN (Q-GCN) which models data in pseudo-Riemannian manifolds of constant nonzero curvature. This method provides a geometric inductive bias that captures heterogeneous topologies. The representational capabilities are examined through experiments on graph reconstruction, node classification and link prediction tasks. The empirical results show that the proposed method outperforms Euclidean GCNs and non-Euclidean GCN counterparts with an acceptable increase in time complexity.
strengths_and_weaknesses: Strengths:
- The work is original: there has not been any existing works about GCNs on pseudo-Riemannian manifolds. 
- The presentation of the paper is clear. 
- The paper includes adequate theoretical derivations on how the geodesic tools are developed, and empirical results to support that the proposed Q-GCN accommodates topologically heterogeneous graphs well, and outperforms other existing methods, either with Euclidean GCNs or non-Euclidean GCNs, on most of the datasets.

Weaknesses:
- It would be better to include some visualizations either for illustrating the theoretical part or presenting the experimental results.

questions: Please refer to the weakness above.
limitations: The authors have adequately addressed the limitations of the proposed method, such as higher computational costs, and the results on graphs with dominating hierarchical properties.
review_title: null

Meta-review: metareview: This paper is about using certain types of non-Euclidean spaces for representations. The background context for the paper is roughly the following: hyperbolic spaces have been recently popularized for embedding tree-like data. These are one of the three types of so-called constant curvature Riemannian manifolds. More recently, to handle more types of data, products of manifolds were proposed. This is more flexible, as such spaces can represent many more flavors of data. The authors of the present work further generalize these embedding spaces by using pseudo-Riemannian manifolds, which, unlike Riemannian manifolds, do not require positive semidefinite metrics. 

The hope for these types of spaces is that they are even more flexible, capable of representing potentially any type of structure. The cost is that they have weird behavior, and that the operations developed for more specific spaces do not easily lift. The authors derive these various operations and build equivalents of GNNs in these spaces, performing comparisons that are favorable against some of the existing literature. 

This paper's strengths are that it does heavy technical work to get these fairly complicated spaces to work. The idea has potential, and there's plenty of additional interesting questions that result from examining these spaces and models built over them.

Most of the reviewers were in agreement about the paper's contributions. One reviewer disagreed and asked some reasonable questions, but most of these are answerable, and I encourage the authors to carefully revise some of their writing to produce additional intuition that provides these answers. Ultimately, I believe the paper clears the bar.

I will note a few downsides that I think the authors should address in their next revision:
- The authors should more carefully compare to products of Riemannian manifolds. The current motivation isn't sufficient (the authors say "the simple combination of spaces still does not accommodate topologically heterogeneous graphs very well"). Are there canonical graphs where pseudo-Riemannian manifolds provide low-distortion embeddings and no product manifold does? Or some other type of evidence?

- Similarly, in the experiments, the comparison against k-GCN, which is probably the closest competitor since it effectively generalizes hGCN, should be attempted with more combinations of spaces (i.e., instead of just H^5 x S^5, you could do H^2 x S^8, H^4 x S^6, and so on). This would make the comparison more fair, as currently the authors provide many more q-GCN implementations. More generally, not sure why there isn't a hyperparameter search over the signature rather than fixing it a priori.


confidence: Certain
Decision: Accept