From which world is your graph?
Discovering statistical structure from links is a fundamental problem in the analysis of social networks. Choosing a misspecified model, or equivalently, an incorrect inference algorithm will result in an invalid analysis or even falsely uncover patterns that are in fact artifacts of the model. This work focuses on unifying two of the most widely used link-formation models: the stochastic blockmodel (SBM) and the small world (or latent space) model (SWM). Integrating techniques from kernel learning, spectral graph theory, and nonlinear dimensionality reduction, we develop the first statistically sound polynomial-time algorithm to discover latent patterns in sparse graphs for both models. When the network comes from an SBM, the algorithm outputs a block structure. When it is from an SWM, the algorithm outputs estimates of each node's latent position.
(I have been asked by the area chairs to provide an extra set of eyes for this paper. Because this review is entering the discussion after the rebuttal phase, discussants were asked to consider anything raised here in light of this lack of an opportunity to give a rebuttal, as it is possible that I have misunderstood things that a rebuttal would have addressed.) 
The work presents itself as contributing a unification of two widely studied random graph models, the stochastic block model and small world model, and developing an efficient algorithm for recovering latent representations for this unified model. A problem with this claim is that, as is acknowledged in the work, this “new” unified approach is really just a (sampled) graphon model, as the authors make clear on Lines 113-114. It’s plain to any reader familiar with graphons that adaptations of both the SBM and small world model fit within the graphon framework. The SBM-graphon connection is obvious and well-studied; the SW-graphon connection is obvious in-so-much-as the small world model is really just a latent space model, though most attention for latent space graphons has been on e.g. logistic latent space models. Denoting that model the "small world” model invokes expectations of navigability results, so in general the results would be better explained in terms of a latent space model with an inverse polynomial distance kernel. All that said, the work is considered on it's merits as a contribution to the graphon literature.
Detailed comments:
1) The way the paper presents it’s results does a disservice to their strengths. The paper contributes a careful analysis of a complex algorithm that appears to bring earlier results for sampled dense graphons over to sparse graphons (Line 255: "We generalize the results in [24] for the sparse graph case.”) That said, while the results in [24] are explicitly given for dense graphs, they are sketched there for the sparse case as well (in the conclusions, with the comment "A precise statement and formulation of the results in Section 4 for the sparse setting might require some care, but should be for the most part straightforward.”).
It is possible that the details of the sketch in [24] are not nearly as “straight-forward” as the authors there claim. But engaging in a clear dialogue with the literature is a reasonable requirements for acceptance, in the eyes of this reviewer. If the paper had a (1) title and abstract and (2) related work section that made clear the position of the paper in the sampled graphon literature, specifically related to [24], that would _greatly_ improve the ability of a reader to appreciate the work. 
As is, the results pertaining to recovering both SBM and SWM networks claimed in the abstract and introduction are essentially results achieved by [24], except for (a) the sparse graph case (the polynomial small world kernel is a universal kernel in the language of the results of that work) and (b) the pairwise distance recovery. I will now focus on the pairwise distance recovery. Basically, [24] is quite general, as is the core of this work. And the focus of the title and introduction on mis-specification between the SBM and SWM feels like the wrong problem to focus on when putting forward this work.
2) Connecting the extended analysis of [24] -- roughly, to get the kernel PCA to work in the sparse regime -- is a nice if modest contribution. More significant is connecting the output of this machinery to MDS machinery to obtain the pairwise distances. This appears to be a novel point, and it seems quite useful. The analysis here does rely on some specific details of the small-world kernel, but it would be really helpful if the authors clarified what the general conditions are on the latent space kernel for some version of pairwise distance recovery to go through. It seems that the long-range links allowed by the heavy polynomial tails may be critical; is that so? Do any version of the results work for kernels with exponential tails?
3) In line with the odd focus of the introduction, the empirical comparisons made in the work are a bit off, but I'm willing to let this slip as the work isn't really an empirical paper, and should get positive "credit" for even trying to do empirical work here. The empirical work focuses on comparisons with algorithms that aren’t quite trying to do what the present algorithm is trying to do, while not benchmarking itself against methods that are designed for some of the same tasks. First, the SBA algorithm of Airoldi-Costa-Chan and SAS algorithm of Chen-Airoldi, and related network histogram methods are specifically designed for the estimation problem in Figure 4. But not compared. Second, the methods used in comparison are not really reasonable. Majority vote label propagation from [56] is an algorithm for categorical labels, not continuous embeddings. It’s not clear why [54], a paper about conformal Isomap, is called a random walk label propagation method, so that might be a crossed-up citation. It is likely that the modularity method [55] is finding a core-periphery cut with it’s main eigenvector; for this reason it would be interesting to see how a semi-supervised method does (e.g. ZGL, given the labels for the presidential candidates discussed as being given to other methods). 
As an overall comment, the empirical question is a terrific one, with high quality data, but the evaluation is not up to the standards of a thorough empirical investigation. But again, I realize that the main contribution of this work is theoretical, but I still want to register what I see as issues. I am most concerned about the lack of comparison to the other methods in the estimation in Figure 4 and Figure S9.
3) As a small comment about Figure (S)9:  for the methods under consideration it would be more honest to show the performance of the Abraham et al. algorithm in Fig 9d and the Newman spectral algorithm in Fig 9b, as opposed to just showing the cross-objectives (where the two methods fail).
4) One point that confused this reader for some time was the fact that the paper studies sparse graphons without any discussion of the tricky issues for such models. It should be made very clear that the model under consideration is the Bollobas-Janson-Riordan (2007) model (also studied by Bickel-Chen-Levina (2011), which is a sampled dense graphon. Some pointers to the emerging literature on sparse graphons defined through edge-exchangeable ideas (Crane-Dempsey 2016 building on Caron-Fox 2014, Veitch-Roy 2015, Borgs et al. 2016) would be useful to provide. 
5) The related work section overlooks that [22], Airoldi et al., makes computational improvements (in terms of complexity) on the USVT method (but still for dense graphs).
6) Ref [19], the latent space model of Hoff et al., is pegged as a “Graphon-based technique” where it should be raised as a broad citation for latent space models such as the small world model discussed herein.
7) The discussion of results for both the unipartite and bipartite graph model is nice. The bipartite model discussed here is sometimes called an affiliation network, see "Affiliation networks” by Lattanzi and Sivakumar, perhaps worth connecting to.
I think there are a lot of interesting connections made in the work. The management of errors in the isomap algorithm for recovering latent space graph models is a nice contribution.