Interest has been rising lately towards methods representing data in non-Euclidean spaces, e.g. hyperbolic or spherical, that provide specific inductive biases useful for certain real-world data properties, e.g. scale-free, hierarchical or cyclical. However, the popular graph neural networks are currently limited in modeling data only via Euclidean geometry and associated vector space operations. Here, we bridge this gap by proposing mathematically grounded generalizations of graph convolutional networks (GCN) to (products of) constant curvature spaces. We do this by i) introducing a unified formalism that can interpolate smoothly between all geometries of constant curvature, ii) leveraging gyro-barycentric coordinates that generalize the classic Euclidean concept of the center of mass. Our class of models smoothly recover their Euclidean counterparts when the curvature goes to zero from either side. Empirically, we outperform Euclidean GCNs in the tasks of node classification and distortion minimization for symbolic data exhibiting non-Euclidean behavior, according to their discrete curvature.
Summary:
The authors propose using non-Euclidean spaces for GCNs. This is inspired by the recent work into non-Euclidean, and especially hyperbolic, embeddings. A few papers have recently tried to go past embeddings into building non-Euclidean models, requiring the lifting of standard operations in Euclidean space to non-Euclidean settings. This has been done in particular in hyperbolic space, but some datasets benefit from more complex spaces. The authors combine the mixed-curvature product formalism that uses products of Euclidean, hyperbolic, and spherical spaces for embeddings, but use these for GCN operations. 
Doing this requires, in particular, developing a reasonable way to perform these operations in spherical space (since Euclidean is trivial and hyperbolic has been recently worked on). The authors do a nice lifting via complex operations, and both the hyperbolic and spherical spaces can devolve into the flat Euclidean space when their curvature goes to 0. The authors implement these GCNs, train the curvatures, and demonstrate performance improvements over Euclidean only versions on node classification on benchmark datasets. They also give a fairly nice introduction to all of these ideas in an extended appendix.
Strengths, Weaknesses, Recommendation:
This paper is reasonably interesting---it joins an effort to produce non-Euclidean models in a tractable way, which is fairly challenging, but could have a good impact. On the plus side, it's great that the authors added the nice development for the spherical operations, since that will come in handy for many models. The experiments are also good. On the downside, everything here is an extension of existing work, and the body of the paper is hard to read (though this may be inevitable, there's a lot of background to go over here). Overall I recommend accepting it; I think it's a solid contribution.
Comments:
- I don't understand why the authors say that their space "interpolates smoothly" just because the limit in the curvature is the same from the left and right side. For example, the absolute value function has the same limit from the left and the right at 0, but it's not differentiable there. Is it actually true that if we take the derivatives of the piecewise hyperbolic/spherical distance function that it's differentiable at c=0? 
- There are a couple of recent papers that also consider hyperbolic GCNs, and in fact use  similar ideas for the aggregation and update steps (i.e., same lift to hyperbolic space). However, these were recently NeurIPS papers, and the text is not yet out, so I don't think this should affect the authors' independent work (and also the product part is new). I do recommend that the authors compare against those results in a future update of this work. The papers are "Hyperbolic Graph Convolutional Neural Networks" by Chami et al and Hyperbolic Graph Neural Networks by Liu et al.
- One thing that I didn't see discussed by the authors is that there are subtle difference between hyperbolic and spherical spaces. For example, the weighted midpoint of Def. 3.2 doesn't immediately extend to spherical space (or at least won't be unique). As an example, consider S^2 and the mean of two antipodal points on it---there's many choices for the midpoint. You probably have to limit the operation to a half-sphere (there's some ideas for this in Gu et al).
- For the synthetic tree, why is the number of edges 2(|V|-1) rather than |V|-1?
- Are the curvatures the same for each layer for the GCNs? This is an interesting point to discuss (some of the NeurIPS papers I mentioned train the curvature for each layer). Also, how do you select the number of factors of each type? 
- Minor, but some of these citations can be updated. The "De Sa" et al 2018 arxiv citation is really Sala et al and is an ICML '18 paper. Similarly, Gulcehre et al is a 2019 ICLR paper, and so on. It's always good to get these right.
- Is there any actual empirical importance from recovering the Euclidean case exactly for 0 curvature? The reason I ask is that my experience is that the hyperboloid is typically easier to work with.
- One useful thing to point out in B.3.3 is that in general, it need not be a diffeomorphism for all of M for any manifold, which leads to non-uniqueness. In differential geometry, the "cut locus" is the region beyond which there is this non-uniqueness.
- In the appendix, the statement "Sarkar (2011) show that a similar statement as in Theorem 2 holds for a very general class of trees" is confusing to me. The "general class", as far as I know, is actually *all* trees, weighted or unweighted.