Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
Non-parametric approaches for analyzing network data based on exchangeable graph models (ExGM) have recently gained interest. The key object that defines an ExGM is often referred to as a graphon. This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic blockmodel approximation (SBA) of the graphon. We show that, by approximating the graphon with a stochastic block model, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity.
The authors describe a new method for predicting a 
      family of random graph generators (graphons which are completely described 
      by a function w:[0,1]^2 -> [0,1]) from a series of observed graphs 
      generated from the random graph generator. They develop a method that 
      approximates the function w using step functions for the case where the 
      true function w is piecewise Lipschitz. The paper takes a new 
      approach to a previous method in Lloyd et al, avoiding the need to place a 
      prior distribution over w. Instead their approach is to apply a clustering 
      method to group similar vertices across all the observed graphs and use 
      averages in these blocks to approximate w by a step function. They 
      compare their new method against other methods for predicting the random 
      graph generator and show significant improvement over a range of different 
      scenarios. Quality ---------------- This paper has many 
      spelling mistakes, typos and layout problems, including the title which I 
      think should be perspective and not perpective. I suggest that the authors 
      give this paper a couple of proof reads to eliminate the errors. The ones 
      I found whilst reading this paper are In the paper: - The 
      title - Sentence just above eqn 5 - bottom of pg 3 has the title 
      of a subsection with no text below it - The last sentence before 
      section 3 - First sentence at the top of pg 6 references an appendix I 
      think the authors mean the supplementary material - Typo in eqn 10 
      w(u_i_y,j_v) I think should be w(u_i_y,u_j_v) - Theorem 3 uses 
      S\in\theta(n) and then subsequently the text refers to S_n. I think the 
      authors mean S_n here since I believe it is meant to be a subset of S = 
      \{1,....,n\} \ \{i,j\}. - Second sentence of sect 4.1.2 send -> end 
      In the supplementary material - ?? in theorem 2 - Lemma 3 
      mentions a proposition 8 and there is none - eqn 5 has a typo (see 
      note about eqn 10 in list above) - The statement of Lemma 2 is 
      grammatically incorrect - The statement of Lemma 3 is grammatically 
      incorrect - Theorem 3 again states S but then uses S_n - p10 
      bottom half mentions a lemma 8 and there is none (I think they mean lemma 
      4) - p12 second eqn up from bottom d_ij is missing a superscript c 
      - p12 last equation the third f_ij does not need a sup 
      Clarity -------------------------- In general, typos 
      and spelling mistakes aside, this paper is coherent and clear. There were, 
      however, a few points that could be made clearer In the Paper: 
      - The use of S and S_n was not clear and I found this confusing, I 
      think that this is possibly a typo (see above) - The first experiment 
      4.1.1 compares their method to others for an arbitrary graphon. To make 
      the comparison fair the authors use graphs of size n for the other methods 
      and two graphs of size n/2 for their method. The second plot showing how 
      their method improves with increasing numbers of observed graphs then 
      seems to use graphs of size n. This could be made clearer. - The 
      discussion of graphs with missing links talks about applying a random 
      binary matrix M to the observed graphs to eliminate some of the links. It 
      was unclear if the M remained constant across all the observed graphs 
      G_1...G_2T and then was changed for each set of observed graphs or if a 
      new M was used for each of the G_1 .. G_2T. If it was a the first way 
      round this would lead to a consistent bias in the observed graphs (since 
      vertices would consistently have missing links throughout). I think the 
      latter approach of randomising M for each graph would be more natural 
      approach. In the supplementary material: - I felt that since 
      lemma 1 - 4 were proved before theorem 3 it would make sense to place 
      lemma 5 here also. Originality ------------------------------- 
      The paper seemed original but I have had limited exposure to this area 
      of research and so can't be certain. Significance 
      --------------------------------- The paper seemed to be 
      significant, but again I have had a limited exposure to this area of 
      research so I cannot be certain.