Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper considers the problem of embedding graphs into continuous spaces.  The emphasis is on determining the correct dimension and curvature to minimize distortion or a threshold loss of the embedding.

Pros:
The problem is clearly stated and easy to understand.
The limitations of the three local curvatures are shown empirically and theoretically

Cons:
Experiments seem inconclusive, with no discussion of the results
Proposed global curvature characterizes the optimal embedding parameters but not a different, efficiently calculable discrete curvature to approximate them
Analysis of particular graph families doesn’t necessarily inform what to expect from embedding large graph data

Overall, I lean towards rejecting this paper.  The problem does seem an important one, but it seems the main contribution of this paper is comparing the local curvatures against an oracle for determining optimal curvature in embedding space, without putting forward an alternative method.

Questions:
Why is it reasonable to take these curvature metrics and use them directly as the curvature of the ambient space at all?  Especially given that Ollivier curvature belongs to a small interval and Forman curvature is always negative.

Does any of the graph family analysis carry over to more general graphs?  For example, assuming some priors about the appearance of these families as subgraphs, or the observed features of real networks in [1]?

[1] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Gharamani. Kronecker graphs: an approach to modeling networks. arXiv:0812.4905v1, 2008.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: The paper presents a novel notion named glocal graph curvature, which offers a solution to determine the optimal curvature for embedding. In particular, the global graph curvature depends on both dimension and loss function used for the network embedding. Besides, the authors studied the existing local curvatures and show that the existing graph curvatures may not be able to properly capture the global graph structure curvature. Extensive results demonstrate the statements proposed in the paper. In general, I like the paper due to its nice presentation, interesting view of graph curvature, and solid theoretical analysis. However, I am not familiar with graph curvature. All I can say is the approach is intuitively appealing, the text is well written and easy to follow, even for an outsider. I do not know any related works or what to expect from the results. I could not find anything wrong with this paper, but also do not have any intelligent questions to ask. 
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: Summary: 
This paper is about curvature as a general concept for embeddings and ML applications. The origin of this idea is that various researchers have studied embedding graphs into non-Euclidean spaces. Euclidean space is flat (it has zero curvature), while non-Euclidean spaces have different curvature; e.g., hyperbolic space has a constant negative curvature. It was noted that trees don't embed well into flat space, while they embed arbitrarily well into hyperbolic space.

All of the notions of curvature, however, are defined for continuous spaces, and have to be matched in some sense to a discrete notion that applies to graphs beyond a particular class like trees. The authors study this setting, consider a variety of existing notions of curvature for graphs, introduce a notion of global curvature for the entire graph, and now to efficiently compute it. They also consider allowing these concepts to vary with the downstream task, as represented by the loss function.


Pros, Cons, and Recommendation

The study of the various proposed distances is fairly interesting, although it's hard to say what the takeaway here is. I think the part I'm struggling with the most is the motivation. Why do we care about using a space of constant curvature? True, we do so when it's appropriate---we embed trees into hyperbolic space. But when we have a more complicated and less regular graph, then compressing all of that curvature information into a scalar doesn't seem like a good idea, and indeed that's the point of the Gu et al work that's being built on here: it mixes and matches various component spaces that each have constant curvature, but altogether have varying curvature.

At the same time, I like the idea of studying a bunch of proposed measures and attempting to gain new insights. This is a pretty unusual paper for ICLR, since the experimental section is really barely there, and what's most interesting are really these atomic insights. If the authors work on the motivation I would consider accepting it---for now I gave it weak accept.



Comments:
- The distinction between what the authors think of as "global" and "local" curvatures is confusing and should be explained further. From what I can see, the authors think of global as being a scalar, and local as being defined at each point; intuitively these seem like pretty bad labels. I would think of the "global" one as being coarse, and the "local" as being more refined, since it contains a lot more information. This is also related to the motivation: why stuff all of this information into one single scalar curvature? It forces you to take averages, while Gu et al defined a distribution over the local curvatures.

If the idea is to simply use one space and not a product, there are in fact various spaces with non-constant curvature, e.g., the complex manifold CH^n.

- Why do your need your graph to be unweighted at the very beginning of Section 2? On the other hand, you may want to define your graph to be connected for the distortion function to be well-defined.

- The statement "1, graph distances are hard to preserve:..." isn't really meaningful, since for the example in 4.3.1, it is possible to embed that graph arbitrarily well. That is, even if the distortion isn't 0, it can be made as small as we desire. There are indeed graphs that are hard to embed (i.e., have lower bounds that do not go to 0) in reasonably tractable spaces, and the authors actually prove such a result, but the star graph is not one of these.

- There's various tricks that actually make some of these graphs very easy to embed. One example is K_n in 4.33. Instead of just embedding K_n, embed the star graph on n+1 nodes, and place a weight of 1/2 on each edge. Now every pair of (non-central) nodes is at distance exactly. 1, and this thing is embeddable into hyperbolic space, etc. Interestingly, this is actually predicted by the Gromov hyperbolicity (for K_n_ that the authors briefly mention.

The reason I bring this up is that even if the authors' project is successful, simple graph transformations may induce much better embeddings. That's fine, though, although it should be mentioned.

- Can the authors write out what's going on for the hyperbolic lower bound on D_min in the  proof of Thm. 4.1?
review_title: Official Blind Review #2

Meta-review: This paper studies the problem of embedding graphs into continuous spaces.  The authors focus on determining the correct dimension and curvature to minimize distortion or a threshold loss of the embedding. The authors  consider a variety of existing notions of curvature for graphs, introduce a notion of global curvature for the entire graph, and how to efficiently compute it.

Reviewers were positive about the problem under study, but agreed that the current manuscript somewhat lacks a clear contribution. They also pointed out that the goal of using a global notion of curvature should be better motivated. For these reasons, the AC recommends rejection at this time. 
Decision: Reject