Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes to learn ultrahyperbolic representations with neural networks. Unlike prior work in ultrahyperbolic representation learning, the paper proposes dealing with an ultrahyperbolic quotient manifold to attain geodesic completeness and enable optimization of parametric models that use this space as an intermediate representation. The optimization of ultrahyperbolic neural networks is then developed in the paper, and an extension to Graph Neural Networks (GNNs) is introduced. Afterwards, the approach is evaluated in various different graph classification tasks.
main_review: Strengths

1. Overall, I think the theory presented in this paper was fairly original and significant, as it enables learning neural networks with intermediate representations that are ultrahyperbolic; notably, this is a generalization of prior work, which limits intermediate representations to spaces of constant sectional curvature. I think that using a quotient manifold construction to attain geodesic completeness and enable optimization was a clever idea, and further, the other theory necessary for optimization (namely parallel transport on $\mathcal{S}^{(p,q)}_r$ and the use of horizontal lifts) was clearly introduced and well-developed. Once these constructs were in place, the generalization of GCNs to ultrahyperbolic space was naturally given in Section 4. I think all throughout, the writing was clear and the construction was clean.

2. The results in Table 3 on node classification in graph datasets show the benefit of ultrahyperbolic space in attaining considerably better results than both the standard GCN and the hyperbolic GCN; the margin of improvement exhibited by $\mathcal{P}^{(0,4)}_1$ seems fairly significant.

Weaknesses

1. I find the results of Table 5 on graph classification to be unconvincing. The standard deviations on most numbers in the table are rather high, high enough that I'm not sure the claimed performance increase of an ultrahyperbolic space intermediate representation is statistically significant.

2. On a more fundamental level, I am unconvinced that ultrahyperbolic space is necessary to glean the benefit of an intermediate representation that allows for both positive and negative curvature. For example, I would like to see a comparison against Constant Curvature Graph Convolutional Networks (CC-GCN) [a], which allow for an intermediate representation that is a product of spaces of constant curvature. A fair comparison would be for example, a mixed signature ultrahyperbolic model ($\\mathcal{P}^{(p,q)}_r$) against a CC-GCN model with a product-like intermediate representation, e.g. $H^{p+1} \times S^q$. I would also like to see a discussion or analysis of the benefits of a product model (like CC-GCN) vs. a model that incorporates positive and negative curvatures into a single space, like the ultrahyperbolic GCN. I think this aspect is completely unaddressed as of right now.

Verdict

The paper developed ultrahyperbolic neural networks, together with clearly presented original theory. I think the way the authors handled the manifold, i.e. turning it into a quotient to enable optimization, was clever, and the necessary operations for optimization (e.g. horizontal lift) were introduced in a principled way. Empirically, the benefit of the method is not entirely convincing. Although ultrahyperbolic space seems to give a considerable improvement in the setting of node classification (Table 3), this was not the case for graph classification (Table 5) where standard deviations are high enough that it is unclear to me if the margin of improvement is statistically significant. Moreover, the paper fails to address prior work [a] on GCNs that utilize a product of constant curvature spaces to extract additional structure, as opposed to using a single space with both positive and negative curvature (i.e. ultrahyperbolic space); in particular, an empirical comparison is missing, and a discussion/analysis of differences (in particular with respect to applying these models to graph tasks). Given that this is the case, I must recommend rejection (for the time being) and that the authors improve their paper by addressing this directly; however, I do emphasize that overall, the paper is very promising.

References

[a] Bachmann, G., B'ecigneul, G., & Ganea, O. (2020). Constant Curvature Graph Convolutional Networks. ICML.

### Post-rebuttal Update

Given the thoroughness of the rebuttal and the pertinent strong results demonstrated, I've decided to update my score from a 5 to a 7.
limitations_and_societal_impact: The paper has two subsections of the conclusion that address limitations and societal impacts. In particular, the paper admits the lack of a theoretical analysis (similar to what can be found in [7]) for graphs without cycles.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper focuses on data embedded in ultrahyperbolic spaces and proposes a method to learn this representation via neural networks. By imposing a quotient structure over the ultrahyperbolic space defined in Low and Stam 2020, the authors are able to define geodesics and thus to estimate the parameters of the learning model selected.
main_review: The paper is overall well written. Section 2 is clear and well organized. 

Major Comments:
- Section 2: why is the quotient space a manifold? Are the authors excluding the axes? Because with the axes, the equivalence classes (orbits) do not have the same dimension, thus the action is not free and stating that the quotient space is a manifold because the total space is a manifold it is not straightforward.

- Section 3: in quotient spaces, the horizontal lift is a good solution to work on the tangent space. However, the curvature of the space can create problem by using only a one step horizontal lift (see e.g. the procrustes algorithm for shapes or the Align All and compute algorithm for graphs). If I am not misunderstanding, some discussion about the single lift procedure should be added.

- Section 5: if I have properly understood, the usage of the hyperbolic space to estimate the parameters allows a proper embedding of the network. If so, I would rather like to see the algorithm applied to a prediction of a graph task more than a classification task, where the output should be embedded into a suitable geoemtrical framework.

Additional comments:
- To introduce complex geometrical framework to perform classification, a well written justification is necessary. It is not clear to me how much of all the introduced framework it is acctually needed to obtain a better performance.
limitations_and_societal_impact: Yes. The conclusions and the limitations are well written.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes graph neural networks for ultrahyperbolic space along with various ways to optimize them.
main_review: Strengths

* The construction is technically sound.
* The experiments show modest improvement across the board.

Weaknesses

* None of the constructions are particularly novel. In particular, they seem to be natural extensions of the same operations in regular hyperbolic space.
* The main motivation for ultrahyperbolic manifolds seems to be to represent different parts of a graph that have different geometries. This is also the goal of the mixed curvature literature [1, 2, 3], but no discussion and experimental comparison is made with this prior work.
* The experiments heavily rely on 3 canonical datasets (Citeseer cora and pubmed) but doesn't delve into the geometric properties of said datasets. Is there any reason why one would use ultrahyperbolic GCNs on these datasets?
* While there is a general increase in performance, SOTA Euclidean methods are not compared against. This is especially important since the three datasets were shown to perform worse on hyperbolic graph models when compared against SOTA Euclidean methods.

Verdict

While the neural networks are well-constructed, nothing is particularly surprising or novel. Furthermore, the experiments do not compare against SOTA methods for both Euclidean and manifold-based graph methods and rely on 3 canonical datasets with no apparent geometric structure. As such, I lean reject.

[1] Learning Mixed-Curvature Representations in Product Spaces, ICLR 2018
[2] Mixed-curvature Variational Autoencoders, ICLR 2020
[3] Constant Curvature Graph Convolutional Networks, ICML 2020

limitations_and_societal_impact: The others adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper presents a (graph) neural network in ultrahyperbolic (semi-Riemannian) space that can be used to model hierarchical graphs with cycles. The motivation is that ultrahyperbolic manifold generalizes hyperbolic and spherical manifolds, thus providing inductive bias to those geometries. In order to avoid broken cases, the paper considers ultrahyperbolic quotient manifold such that every two points in the manifold can be connected by a geodesic. The method is evaluated in graph and node classification tasks. 
main_review: Originality: 
1)	In general, extending neural networks to semi-Riemannian space is a new and valuable idea. However, the method used in this paper to solve the brokenness of geodesic is straightforward, even a little bit trivial and lack theoretical analysis. The idea is simply that, if points x and y cannot be geodesically connected, they connect the point x with the antipodal point -y. This method would potentially hurt the expressiveness of the ultrahyperbolic space in paper [1]. 

2)	In section 3.2, the author claimed that they first formulated parallel transport of the ultrahyperbolic space. However, the parallel transport of ultrahyperbolic space was first introduced in the paper [2] (see Section 4.2.1 and 4.2.2). The authors should clarify the contributions and cite the related works properly. 

Quality: 
1)	The authors try to solve the broken issues of ultrahyperbolic manifold by identifying each pair of antipodal points to one point, I was mainly concerned with the expressiveness of the induced space as it is no longer a standard pseudo-sphere. It is clear that the pseudo-sphere can generalize spherical and hyperbolic spaces well [1], but simply identifying each pair of antipodal points to one point would hurt the expressiveness of the space. The author used the quotient space, which does not satisfy a lot of properties of the pseudo-hyperboloid used in the paper [1]. Taking sphere as an example, why a point x and its antipodal point -x leads to duplications? these two points could be used to describe different nodes in a cycle of graph. It seems like the “quotient space” even cannot model a cycle graph well. Note that in a spherical space, point x and point -x can describe two antipodal nodes in a graph.  Instead, the quotient space can only model a half-cycle relationship, as it treats points x and -x equally. 
2)	The author showed some intuitions of the quotient manifold in Fig 1, where the space-like geodesic could be used to describe cycle, and the time-like geodesic could be used to describe trees, but if we treat each pair of antipodal points to one point, the geodesic cannot fully describe some relationships. (e.g. starting with point x, there is only a half-cycle passing x, but not a full cycle). 
3)	In line 83, the author also claimed that the quotient manifold is only a submanifold of pseudo-sphere, but it is not clear which submanifold it is. A submanifold can only express some sub-information of the original manifold. The author might need to clarify what information loss it led to.
4)	I would advocate the authors to provide more theoretical analysis w.r.t the method, and try to understand more on the expressiveness of the ultrahyperbolic quotient manifold. So far, it is unclear how the method works to model tree and cycles as the space used in this paper is not an ultrahyperbolic manifold anymore. 

Clarity: the paper is well-written and well-organized, there are some minor points that need to be clarified. 

1)	In line 78, does the radius r only play a role of scaling factor? Assuming infinite precision, I think it is true, but in practice, I would imagine that changing the radius r would also influence the experiment results. In paper [3], the authors showed some improvements by learning the right curvatures. The author might also want to do some ablation study on this issue.
2)	The toy experiments in section 5.1 follows mainly the experimental setting of paper [1], but show different results (the best performance is achieved by different time dimension), it would be better if the author can add more details to explain the results. 

Significance: 
      The experiments lack some comparisons to some existing works. 
1)	Since the proposed method is a little bit straightforward, and the theoretical contribution is not significant, I would suggest doing more experiments to compare the method with some more recent baselines, e.g. produce space [4], to showcase the advantages of the method. 

2)	How to determine the time dimension? Could you provide some insights on this? it would also be interesting to do some ablation study on the time dimensions if possible. Consider adding them into the appendix. 

[1] Law, M.T. and Stam, J., 2020. Ultrahyperbolic representation learning. NeurIPS 2020.
[2] Gao, T., Lim, L.H. and Ye, K., 2018. Semi-Riemannian manifold optimization. arXiv preprint arXiv:1812.07643.
[3] Chami, I., Ying, Z., Ré, C. and Leskovec, J., 2019. Hyperbolic graph convolutional neural networks. Advances in neural information processing systems, 32, pp.4868-4879.
[4] Bachmann, G., Bécigneul, G. and Ganea, O., 2020, November. Constant curvature graph convolutional networks. In International Conference on Machine Learning (pp. 486-496). PMLR.

Post Rebuttal:
 The authors give more intuitions to the expressiveness of the manifold (e.g.. to describe cyclic relationships), so I raised my score. But I still suggest the authors provide more theoretical analysis w.r.t the method.

limitations_and_societal_impact: Not applicable
review_title: null

Meta-review: There is a lot of support for this paper, which proposes a mathematical elegant and convincing method for embedding graphs in non-Euclidean spaces, namely ultrahyperbolic spaces. The experiments - despite some caveats mentioned - provide sufficient evidence for the validity of the approach.
Decision: Accept (Spotlight)