Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper deals with the task of estimating the connection probabilities in a random graph, assuming that it is drawn from a graphon model; i.e. $P_{ij} = f(\xi_i, \xi_j)$, where $f$ is a smooth function and the $\xi_i$ are uniform random variables. The authors do so by exploiting the same ansatz as in Zhang et al: for $i \in [n]$, find several $i'$ with connection probabilities "close" to those of $i$, and average the $P_{i'j}$ to find an estimate for $P_{ij}$.

The main difference with the existing litterature is the choice of the $i'$: the authors choose an iterative procedure, building ever improving estimators of the $P_{ij}$ and using the current estimate to find the $i'$ and build the next estimator. The paper also presents a two-step procedure to choose the right number of "close" vertices.

The authors then show several theoretical properties of their algorithm, in a model including (but not limited to) the classical stochastic block model. Their bounds depend on the number of vertices correctly classified as "close" to each vertex in the graph.

Finally, they present experiments on both synthetic and real-world data; these seem to indicate that the ICE algorithm outperforms its counterparts when the graphon function $f$ becomes more complex. 
main_review: This paper presents a novel and effective method for probability estimation in graphon models. The authors show some convergence bounds on a restricted model (functions that are Lipschitz on rectangles), but the numerical experiments seem to indicate that the algorithm converges for a more general class of functions.

Overall, the paper is well-written and easy to read, with a few caveats:
* the use of "neighbors" to denote similar vertices clashes with the overwhelming acception of this term in graph theory, which causes some confusion,
* the statements of Theorems 1-4 are very convoluted, involving up to 12 different constants; I'd rather suggest very slightly weaker but more readable versions (e.g. "fusing" some constants) in the main text, and if needed putting the exact bounds in the appendix.

Those drawbacks being fairly straightforward to fix, they do not impact the overall quality of the paper too much.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies an interactive algorithm for connecting probability estimation. The proposed algorithm updates the pairwise vertex distance, neighborhood set, and the connecting probabilities iteratively to improve the estimation until the result converges. The authors have shown both theoretical and empirical results. Some practical techniques to improve the performance of the algorithm are also discussed in the paper.
main_review: I think this paper has some interesting results. The proposed algorithm is simple, efficient, and well-motivated. The experiments are well designed to demonstrate the advantages of the algorithm when compared with other approaches. The theoretical results proved reasonable guarantees for the performance of the algorithm.

I have a question about the algorithm. The proposed algorithm has an EM flavor. A natural question for such an algorithm is whether or not the algorithm is guaranteed to terminate and how many steps it takes to converge. Although some relevant analysis is given, I would appreciate a discussion for the general case, whether the result is positive or not.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors propose an iterative approach to estimate the probability of forming an edge between any two vertices in a graph, which they denote as the *connecting probability*. With only a single realization of the graph, it is a difficult task to estimate the connecting probabilities. The proposed iterative connecting probability estimation (ICE) method uses neighborhood averaging, similar to Zhang et al. (2017), but with iterative refinement of the neighborhood. They provide a theoretical analysis demonstrating that the error rate of their proposed estimation procedure is asymptotically as good as that of an "oracle" estimate that has access to the true connecting probabilities to choose the neighborhood. They also provide extensive simulations and a real data experiment demonstrating good empirical performance compared to prior work.

main_review: **Originality: Moderate**  
The basic idea is straightforward enough that I would consider it to be low in originality: iterate a neighborhood averaging algorithm multiple times until convergence. The two-stage neighborhood selection approach using different $C$ values is innovative and appears to be effective.

I did not carefully check the proofs in the supplement, so I cannot assess if there is any originality to the analysis techniques.

**Quality: High**  
The authors present a principled approach extending the neighborhood smoothing approach of Zhang et al. (2017) and present simulation results along the way justifying their decisions. These are supplemented with more extensive simulation experiments showing very impressive performance on lots of different graphon functions and a real data experiment.

They also present theoretical results that I find to be of value. It is good to see that the proposed iteration has the same asymptotic error rates as an "oracle" estimator that knows the true neighbors. Again, I did not check the proofs for correctness.

**Clarity: High**  
I found the paper to be extremely well written and very easy to understand. Thank you! I have just a few minor points for improvement below.

The authors use the term "neighbors" of a vertex $i$ to denote a group of vertices with similar connecting probabilities compared to $i$. This may be confusing to some readers because the term "neighbors" is usually used to denote vertices connected to $i$. Perhaps this could be clarified with a 1-sentence explanation in the intro.

In Figure 4, showing 2 probability matrices in a single figure is confusing. Since the matrices are symmetric, only a triangular portion is necessary, which allows the matrices to be shown in this way, but there is plenty of room to show all 4 matrices as separate subfigures.

Table 1: Use bold to denote the method that performs the best in terms of RMSE (excluding oracle) to simplify comparison between methods.

Why did you choose the single test subject for the real data experiment?

**Significance: Moderate**  
This paper certainly advances statistical network estimation, but it is an incremental improvement on Zhang et al. (2017), which limits significance somewhat in my view. The approach could have some broader impact given the wide applicability of network analysis in many disciplines.

**Comments after author response and discussion:**  
I find the proposed method to be simple and provably effective, which is a very good combination. All the paper needs is a few minor revisions, such as changing the use of the word "neighbor", as discussed. Adding some more experimental results on the projectome data, even in the supplementary, would also strengthen the paper.

limitations_and_societal_impact: The authors provide a very brief discussion of limitations in the conclusion. Some discussion of societal impact is provided in the supplement.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper discusses a new strategy for graphon estimation that is based on an iteratively updating the graphon by considering certain neighborhoods of the nodes.

main_review: The paper discusses a novel idea for graphon estimation: instead of using a "one-shot" approach, e.g., based on a singular value decomposition, the idea is to use an procedure that --- starting from an initial guess --- updates the graphon estimate iteratively.
The problem of graphon estimation is indeed very relevant, and the presented theoretical guarantees and numerical experiments corroborate the results of the authors.

I have a number of concern regarding the paper, in terms of the presentation and the results.
First I found the initial discussion and the abstract to be somewhat misleading. The authors state that there are no strong assumptions that need to be made, but they assume that the graph is generated by a graphon model. This implies conditionally independent edges / vertex exchangability, and seems to be a pretty strong assumption to me. 
I think the presentation should have been clearer in stating that the problem is that of estimating a graphon, rather than estimating the connection probability -- which is a more general (and more vague) idea.

Given that the authors concentrate on graphon models, it would have however also been useful to discuss the aspect of sparsity -- it is well known that graphons are essesntially models for dense graphs; while one can adjust the density of them to a certain extend via a scaling parameter, but obtaining truly sparse graphs would require to turn to something like a graphex, or edge-exchangable models. This is a limitation that should have been discussed in more detail in my opinion.
Indeed, we (basically) see a repercussion of this issue of graphons in Assumption 2, where the neighborhood size of a node needs to grow as (n log n)^(1/2).

I would have also liked to see more theoretical discussion (and perhaps some numerical experiments) on the choice of the C parameter; indeed as the authors point out in the conclusion, we may actually have very different C for different vertices.
Similarly, how the initial estimate of the connection probability matrix P should be chosen, and what is effect would be on the algorithm seems a question that is somewhat underdeveloped in the paper.

While some of these flaws will be very difficult to address in a revised version,  I think the paper has an interesting algorithmic idea and so I see it slight above the threshold.

=========
I thank the authors for their answers. I have updated my score, following the response and the comments from the other reviewers.
limitations_and_societal_impact: There are several limitations, in particular w.r.t. the considered network model (a graphon) -- see above.
review_title: null

Meta-review: The paper presents a simple iterative and provably effective method for graphon estimation, which improves on previous "single shot" estimation techniques. The reviewers were in consensus that the idea is very natural and well-studied, and a significant contribution to the graphon literature.
Decision: Accept (Poster)