Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of sensing a notion of the true distance between nodes of a 
network. This allows to estimate the true position of these nodes up to pairwise scaling. The 
cradle of this approach is essentially organized into two steps: a) compute a matrix factorization 
of the matrix associated with the graph, i.e., spectral embedding, and b) perform a nonlinear 
dimensionality reduction step. The main observation, subject to necessary conditions, is that 
Euclidean distances of the spectral embeddings agree with geodesic distances between the 
graph nodes. Numerical experiments provide evidence that the proposed approach works.

main_review: -) The paper is relatively well-written, although some improvements in written English would 
be welcome (also, the authors use the word "between" too often). 

-) The theory appears to be correct; at least up to the part I could confidently follow it. Moreover, 
most concepts discussed in the paper are clear, and previous work is mentioned.

-) One think I missed is comparison with other methods. Is the case that no other methods 
can solve these problems? Euclidean distance to geodesic distance mappings are a well 
studied topic. 

-) Other applications can be found in:
https://www.isca-speech.org/archive/archive_papers/interspeech_2010/i10_2742.pdf
https://arxiv.org/pdf/1902.01395.pdf

What is new compared to those viewpoints?

-) It is my impression that the new approach need a few parameters to have the proper 
values in order to work. How the value of hyperparameters (e.g., dimension of spectral 
embeddings) affects the performance of the proposed approach for the real datasets? 
How about other methods?

-) Line 109: did you mean to say "Wasserstein distance"?

-) Line 112: "legitimately" is a rather strange word in this context. Please rephrase.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The manuscript shows that by combining matrix factorisation with dimension reductions, one is able to reconstruct data (up to some invariances) by only considering a kernelised set. The main contribution is to show an explicit relation between the geodesic distances in the manifold that supports the kernelised data, and the distance of the original data set with respect to a Riemannian metric.
main_review: The results themselves are interesting and open up possibilities for further research and applications. As this is a mainly theoretical paper, the experiments are not as important as the theoretical results and does not detract that much from the quality of the paper.
limitations_and_societal_impact: These results are supplemented by experiments on both synthetic data, and two real datasets. The experiments are not incredibly in depth and it is hard to say exactly how "good" they are. I can appreciate the lack of benchmarks here, but if possible it would be nice to see some sort of comparison or discussion of the quality of the results.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of finding the latent variables $Z$ given noisy observations of $f(Z_i, Z_j)$ with unknown $f$, and suggests applying matrix factorization (e.g. spectral embedding) + nonlinear dimension reduction (e.g. isomap). It shows mathematically that under some assumptions on the kernel $f$, finding geodesic distance in the manifold (which the matrix factorization step approximates) is equivalent to finding the geodesic distance in the original latent space. Experiments on simulated and real-world data are provided.
main_review: This paper seems sufficiently different from the cited works [12] and [57], and appears to be the first to provide theoretical analysis with general kernel $f$ and continuous variables $Z$. This work could be an important step to more rigorously understanding why nonlinear dimensionality reduction methods work so well in practice.

The main question I have is regarding the air traffic data experiment. Why should LA and NY be far from each other in the embedding space? Is the hypothesis that the latent variable $Z_i$ is the geographical location of city $i$? Since there are a lot of other factors (e.g. population, economic size, airport size) that go into deciding whether there should be a flight between two cities, one could even argue that LA and NY as two coastal hubs should be close to each other in an embedding space. Also, how are we meant to interpret the structures in Figure 3 c? For example, what does it mean for points to be spread out vs. clumped? What are the clusters within North America?

This paper is written clearly and easy to follow, but I have a few clarification questions:
- Typo in Theorem 1, "Let $a$, $b$ any two points" -> "Let $a$, $b$ be any two points".
- In page 2 last sentence, a graph adjacency matrix is not necessarily sparse.
- Is the norm in (2) and the following paragraph the l2 norm?


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of recovering a notion of distance between the nodes of a graph. The authors write their main problem very abstractly and provide an excellent description of particular A's, f's, and Z_i's that are of interest in a wide range of applications. The main contribution is to prove that a low-dimensional embedding is related to a topological manifold.  In this regard, it is a follow-up to results by Rubin-Delanchy in [21] from 2020.  The paper seems to be well written, though I was not able to follow all the technical details in the supplementary material as it is pretty far from my expertise.
main_review: The authors start with problem statement (1) but later make a few more assumptions on f (e.g., pos. def., f is C^2, Hessian is pos. def., and a non-degeneracy condition). I think the authors will want to notify the readers at least that those assumptions are coming.  The authors mentioned that it is technically challenging to extend their results to the case when f is symmetric but not positive definite. What are the issues there? One issue is that the eigenvalue decomposition (a.k.a. Mercer expansion for pos. def. functions) is no longer uniformly and absolutely convergent to f.  I am under the impression that if one assumes that f has a little more regularity (e.g., Lipschitz continuous in both variables separately), one can keep the uniform and absolutely convergent properties for symmetric f. I am not aware of a particular reference, though, but Schmidt, Weyl, Smithies, Hammerstein, and Brown were interested in this. 

Theorem 1 is an excellent result that tells us that finding the geodesic distance in M is equivalent to minimizing path-lengths in Z under the Riemannian metric.  Section 3.3 is welcomed as it shows the potential use of that connection. Can the authors add a comment on why f needs to be C^2? 

The practical applications also look impressive as a non-expert in the field of spectral embedding. 
limitations_and_societal_impact: While the authors did make assumptions and the methodology does have limitations, the authors did not address the consequences of these limitations in terms of the potential applications.
review_title: null

Meta-review: The paper revisits the problem of recovering positions of points given the similarity information. It proposes to do: first, a spectral embedding and second, a nor linear embedding to obtain the positions. As reviewers note, the interesting contributions are in connecting the geometry between spectral approximations (X) and true embeddings (Z). Overall, the theory and experiments are interesting. A minor comment, currently, the paper assumes that A is fully known and the theory goes through. What happens A is partially known (akin to recovering positions from partial similarity information). What kinds of consistency results are required for the approximations to succeed? 

Decision: Accept (Poster)