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. Spectral embedding is a standard technique for the representation of graph data (Ng et al., 2002; Belkin & Niyogi, 2002) . Given the adjacency matrix A ∈ R n×n + of the graph, it is obtained by solving either the eigenvalue problem: or the generalized eigenvalue problem: where D = diag(A1 n ) is the degree matrix, with 1 n the all-ones vector of dimension n, L = D − A is the Laplacian matrix of the graph, Λ ∈ R k×k is the diagonal matrix of the k smallest (generalized) eigenvalues of L and X ∈ R n×k is the corresponding matrix of (generalized) eigenvectors. In this paper, we only consider the generalized eigenvalue problem, whose solution is given by the spectral decomposition of the normalized Laplacian matrix L norm = I − D −1/2 AD −1/2 (Luxburg, 2007) . The spectral embedding can be interpreted as equilibrium states of some physical systems (Snell & Doyle, 2000; Spielman, 2007; Bonald et al., 2018) , a desirable property in modern machine learning. However, it tends to produce poor results on real datasets if applied directly on the graph (Amini et al., 2013) . One reason is that real graphs are most often disconnected due to noise or outliers in the dataset. In order to improve the quality of the embedding, two main types of regularization have been proposed. The first artificially increases the degree of each node by a constant factor (Chaudhuri et al., 2012; Qin & Rohe, 2013) , while the second adds a constant to all entries of the original adjacency matrix (Amini et al., 2013; Joseph et al., 2016; Zhang & Rohe, 2018) . In the practically interesting case where the original adjacency matrix A is sparse, the regularized adjacency matrix is dense but has a so-called sparse + low rank structure, enabling the computation of the spectral embedding on very large graphs (Lara, 2019) . While (Zhang & Rohe, 2018) explains the effects of regularization through graph conductance and (Joseph et al., 2016) through eigenvector perturbation on the Stochastic Block Model, there is no simple interpretation of the benefits of graph regularization. In this paper, we show on a simple block model that the complete graph regularization forces the spectral embedding to separate the blocks in decreasing order of size, making the embedding less sensitive to noise or outliers in the data. Indeed, (Zhang & Rohe, 2018) identified that, without regularization, the cuts corresponding to the first dimensions of the spectral embedding tend to separate small sets of nodes, so-called dangling sets, loosely connected to the rest of the graph. Our work shows more explicitly that regularization forces the spectral embedding to focus on the largest clusters. Moreover, our analysis involves some explicit characterization of the eigenvalues, allowing us to quantify the impact of the regularization parameter. The rest of this paper is organized as follows. Section 2 presents block models and an important preliminary result about their aggregation. Section 3 presents the main result of the paper, about the regularization of block models, while Section 4 extends this result to bipartite graphs. Section 5 presents the experiments and Section 6 concludes the paper.
Graph regularization forces spectral embedding to focus on the largest clusters, making the representation less sensitive to noise. 
{"src": "scitldr-AIC_train", "paper_id": "H1l_0JBYwS"}