NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:4700
Title:Latent distance estimation for random geometric graphs

Reviewer 1

Originality The paper seems fairly original. The idea of leveraging known facts about linear eigenfunctions to obtain a relation between the underlying Gram matrix and the spectrum of the adjacency matrix is nice. Based on my reading of the supplement, the analysis rests heavily on prior work which bounds the error between the spectrum of T_W and T_n, in the case where W is Sobolev smooth. Quality From a limited reading of the supplement, the proof techniques make nice use of a variety of facts in operator perturbation theory, and seem interesting independent of this application. Simulations could be improved. For instance, the left plot in figure 1 could include a slope, to demonstrate the error is obeying the stated rate in Theorem 4. The probability of event E holding ‘for n large enough’ seems weak, particularly since Theorem 4 claims an asymptotic rate of estimation. Could a sense be given of how P(E) depends on n and W? Some typos, including [line number]: [32]: ‘mane’ [58]: ‘though as’ [76]: ‘nonassymptotic’ [81]: ‘UVST’ [148]: ‘need precise eigenvalue...’ [208]: ‘versin’ [224]: [Algorithm 1]: Lambda_1 is initialized to depend on lambda_i before i is defined. Should this be lambda_1? Clarity The role various elements play in the analysis could be more explicitly untangled. For instance, if I understand correctly, the Sobolev rate comes from the estimation of the spectrum of the operator T_W by the (unobserved) operator T_n, which dominates the rate of estimation of the spectrum of the operator T_n by \hat{T})_n. Similarly, given the primarily theoretical nature of this paper, more detail should be given regarding the techniques used for novel aspects of proof. For instance, on lines [78-80], the authors mention “adaption of perturbation theorems for matrix projection… to the ‘nearly orthogonal’ case.” It might have been nice to expound on this in the main text. Significance The setup is limited to the case where latent variables are sampled uniformly over the sphere. This seems unrealistic in practice and is additionally unverifiable, considering the variables are latent. The discussion section mentions extensions, but they are still restrictive, as in general the analysis critically rests on the ‘addition theorem’. Overall, this work therefore is of theoretical interest but seems unlikely to have practical impact. Particularly in light of these practical limitations, more motivation for the specific problem of latent distance estimation should have been given.

Reviewer 2

The theory presented in this paper is solid and can provide basis for further research in this area, nevertheless the experiments section can use more exploration. Scalability is not mentioned for instance. It would have been helpful to understand how does this relate to real world graphs as well. Upon looking through the author(s) response, my confidence is increased in the theoretical findings of this paper, and its ability to serve as a building block towards more complex models -- but I still think a more extensive experiments section could make the paper much stronger.

Reviewer 3

The authors consider the problem of estimating the latent variables of graphon defined on a sphere. They introduce a spectral algorithm to estimate the pairwise distances between the latent points and prove its rate of convergence. Originality. ============ The paper contains original results about the estimation of the underlying pairwise distancaes oof the latent points of a graphon (defined on a sphere). A lot of the mathematical machinery developed draws from the existing literature, but given the technical nature of the topic this is to be expected. The results are supported by theory and a set of numerical experiments. Clarity. ======== The paper is written in a clear and coherent manner. One question I have about the numerical experiments is why the score function appears to be peak not only at dimension three, but seems to have some further local maxima at 7, 11, etc. Is there an intuitive reason for this? Significance ============ Graphon estimation and latent variable models for graphs are of great relevance for learning from graphical data. Hence the contribution of the authors is certainly relevant. Where the authors could have done a better job is in pointing out potential applications of this kind of model. A brief brief example application to a real-world data set would also have strengthened the paper in my opinion. Quality ======= The quality of the paper is good, overall. There are a few statements discussion items, however, which I find could be improved. The authors state thet the usual embedding space is a sphere or the unit cube in the introduction -- I would think that for geometric graphs the cube is far more common. Are they referring to random dot-product models here? Could they provide some further reference for geometric graphs on the sphere? The authors state that random dot product are more restrictive than the model they consider here, but do not discuss how/why this is the case, so the reader is left hanging. To improve the paper I suggest adding a discussion to make the relationships clear. Are they claiming that their model is a strict superset of RDPGs? If yes please elaborate. Given that their model is based on 'relatively sparse' graphs, but many real-world networks are, in fact, very sparse, I think this aspect (which is a common sticking point with the graphon model) should be discussed in a bit more detail. Do the authors have an idea of how to make their results applicable for sparse graphs (e.g. using graphex or other constructions)? Would there be a problem with the spherical embedding space in this case? Typos: l.208 versin -> version Supplementary information l.226 -- there is a sentence starting with "In Figure.." that does not have an end. Conclusion ========== Overall I think this is a good contribution that would merit publication. [post discussion] After reading the authors' responses and the discussion, I feel this would make an interesting contribution, provided the authors improve the paper along the lines indicated in the response letter.