Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This paper analyzes the effect of regularization on spectral embeddings in a deterministic block model and explicitly characterizes the spectra of the Laplacian of the regularized graph in terms of the regularization parameter and block sizes. To my knowledge, this has not been done before. Prior work either derives sufficient conditions for the recovery of all blocks in the asymptotic limit of an infinite number of nodes in the case of (Joseph & Yu, 2016), or lower bounds the number of small eigenvalues of the Laplacian of the unregularized graph on random graphs in expectation (therefore arguing in favor of regularization) in the case of (Zhang & Rohe, 2018). This paper, on the other hand, gives a precise characterization of the eigenvalues and eigenvectors (albeit in the case of a deterministic graph); the results are elegant and the analysis uses simple elementary techniques, which is very satisfying and seems to be easy to build on. The authors mention that they would like to extend this analysis to stochastic block models, which would indeed be interesting. The paper is also well written and the results are clearly presented. Overall, this is a nice contribution to spectral graph theory and so I recommend acceptance. 
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: The paper explains through a block model the impact of the complete graph regularization, intended as adding to all the entries of the adjacency matrix a constant. The paper is a nice balance between theory and practical effect, since it shows that at the end spectral embedding has an impact on larger connected block units of the graph, discarding isolated nodes. 

It also introduces the problem in a gentle way, so that the range of possible readers is wide.

In general I'm happy with the paper, no major lacks on my side

Suggestions: it is not clear how to get to Eq.7), the authors should explain the last passage before that equation a little more?  How the values of the noise alpha have been selected? How the approach scales with the number of blocks, in term of complexity?


review_title: Official Blind Review #2

Meta-review: The paper proposes a nice and easy way to regularize spectral graph embeddings, and explains the effect through a nice set of experiments. Therefore, I recommend acceptance.
Decision: Accept (Spotlight)