Spectral embedding of regularized block models
  Spectral embedding is a popular technique for the representation of graph
data. Several regularization techniques have been proposed to improve the
quality of the embedding with respect to downstream tasks like clustering. In
this paper, we explain on a simple block model the impact of the complete graph
regularization, whereby a constant is added to all entries of the adjacency
matrix. Specifically, we show that the regularization forces the spectral
embedding to focus on the largest blocks, making the representation less
sensitive to noise or outliers. We illustrate these results on both on both
synthetic and real data, showing how regularization improves standard
clustering scores.
