Spectral  Embedding of Regularized Block Models
Authors: Nathan De Lara
Thomas Bonald
Venue:  (2020)
Keywords: Spectral embedding
regularization
block models
clustering

Abstract: 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. 

Published as a conference paper at ICLR 2020
SPECTRAL EMBEDDING OF REGULARIZED BLOCK MODELS
Nathan De Lara & Thomas Bonald Institut Polytechnique de Paris Paris, France
(nathan. delara, thomas. bhommssbbonlldjeeeeeecoorrrrsss
ABSTRACT
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. this paper, we explain simple block model the impact of the complete graph regularization. whereby constant added to all entries of the adjacency matrix. Specifically, we show that the regularization forces the spectral embedding focus on the largest blocks, making the representation less sensitive to noise or outliers. We illustrate these results both on both synthetic and real data, showing how regularization improves standard clustering scores.
INTRODUCTION
Spectral embedding a standard technique for the representation of graph data (Ng et al. 2002
Belkin & Niyogi 2002).. Given the adjacency matrix A R of the graph, is obtained by solving either the eigenvalue problem:
LX with X
(1)
or the generalized eigenvalue problem:
DXA, with XTDX=1,
where D = dia,(AA,)) is the degree matrix, with the all-ones vector of dimension n, L = D A the Laplacian matrix of the graph, A E B&xk is the diagonal matrix of the smallest (generalized) eigenvalues of I. and X Raxk 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 the normalized Laplacian matrix Luorm = D 1/2 1/2 AD-1/2
(Luxburg. 2007
The spectral embedding be interpreted equilibrium states of some physical systems (Snell & Doyle 2000 Spielman 2007] [Bonald et al. 2018). desirable property in modern machine learning. However, it tends produce poor results real datasets if applied directly the graph (Amini ct 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 pro- posed. The first artificially increases the degree of each node by constant factor (Chaudhuri 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 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 al. (2016) through eigenvector perturbation 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 separate the blocks in decreasing order of size, making the embedding less sensitive to noise or outliers in the data.

---

Published as a conference paper at ICLR 2020
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 emhedding to focus on the largest clusters. Moreover, our analysis involves some explicit characterization of the eigenvalues, allowing parameter.
quantify the impact of the regularization
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 extends this result bipartite graphs. Section presents the experiments and Section concludes the paper.
2 AGGREGATION OF BLOCK MODELS
Let A E REx" be the adjacency matrix of an undirected, weight graph, that is symmetric matrix such that A, > if and only if there is an edge between nodes and j. with weight Asy- Assume that the nodes of the graph can be partitioned into K blocks of respective sizes 71,... .......... R so that any two nodes of the same block have the same neighborhood, i.e., the corresponding rows (or columns) of A are the same. Without any loss of generality, assume that the matrix A has rank K. We refer to such a graph as a block model.
Let Z xa be the associated membership matrix, with Z₁ if index i belongs block and 0 otherwise. We denote by W 2 R the diagonal matrix of block sizes.
Now define = z AZ E R This the adjacency matrix of the aggregate graph, where each block of the initial graph replaced by single node; two nodes in this graph connected by edge of weight equal to the total weight edges between the corresponding blocks in the original graph. We denote by / diag(AÁ, k) the degree matrix and by T. D the Laplacian matrix of the aggregate graph.
The following result shows that the solution to the generalized eigenvalue problem that of the aggregate graph:
( follows from Proposition Let x be a solution to the generalized eigenvalue problem:
Lx ADx.
Then either Z x and À 1 or Zy where y is a solution the generalized eigenvalue problem:
Ly = XDy.
Proof. Consider the following reformulation of the generalized eigenvalue problem 3
Ax Dr(1 A)-
(5)
Since the rank of A is equal to K, there are K eigenvectors x associated with the eigenvalue 1, each satisfying z 0. By orthogonality, the other eigenvectors satisfy x = Zy for some vector y E R We get:
AZy = DZy(1 A),
so that
Ay Dy(1 A). Thus is solution the generalized eigenvalue problem
REGULARIZATION OF BLOCK MODELS
Let A be the adjacency matrix of some undirected graph. We consider regularized version of the graph where an edge of weight a is added between all pairs of nodes, for some constant a >> 0. The corresponding adjacency matrix given by:
A, A aJ,
2

---

Published as a conference paper at ICLR 2020
where J 1, is the all-ones matrix of same dimension A. We denote by Da diag(Aalm) the corresponding degree matrix and by La Da Aa the Laplacian matrix.
We first consider simple block model where the graph consists of K disjoint sizes R1 > R2 > ... d nodes, with n 2 1. In this case, we have A zz" where the membership matrix.
of respective
The objective of this section to demonstrate that, in this setting, the k-th dimension of the spectral embedding isolates the k largest cliques from the rest of the graph, for any k E (2..... K}
Lemma 1. Let \1 I x2 S I An be the eigenvalues associated with the generalized eigenvalue problem:
LAv ADnI.
66)
We have A = 0 A2 S. AK < AK+1=
Ap =
Proof. Since the Laplacian matrix La positive semi-definite, all eigenvalues are non-negative (Chung) 1997). We know that the eigenvalue 0 has multiplicity 1 on observing that the regularized graph is connected. Now for any vector 2.
T A x² Ax + or aorTTa J== x|1 + x) 20,
that the matrix Aa is positive semi-definite. In view of (5). this shows that X < for any eigenvalue The proof then follows from Proposition T on observing that the eigenvalue has multiplicity n K.
Lemma 2. Let be a solution to the generalized eigenvalue problem 6 with X E (0. There exists some E {+1,- -1} such that for each node in block j.
x
sign(x,) =s
nj
Proof. In view of Proposition I we have Zy where y is solution the generalized eigenvalue problem of the aggregate graph, with adjacency matrix:
Ag z A. = - (A+
Since A T and W ZT we have A, = W + JZ. Using the fact that Z1ę 1ns
we get J = 1, _ = ZJK ZT with JK = 1x1 1 the all-ones matrix of dimension x K, so that:
Å. W aJR)W,
where Ix is the identity matrix of dimension K x K. We deduce the degree matrix:
W D. = W(W + +mllk),
and the Laplacian matrix:
- a -J W)
The generalized eigenvalue problem associated with the aggregate graph is:
L. = XDay-
After multiplication by W-1, we get:
a(nlK JKW)y X(W + anIx)y.
Observing that JK 1 1x Wy (1T x 1k. we conclude that:
(an(1 X) XW)y 1x.
and since W = diag (lag(()). (1I, , nx).
Vj = 1, K, Vj &
(8)
An; - a(1 - 2)n
The result then follows from the fact that Zy.
3

---

Published as a conference paper at ICLR 2020
Lemma 3. The K smallest eigenvalues satisfy:
0 = A1
11
A2
< P2 < ... < AK < PK.
where for all 1...., K,
en
an + n2
Proof. We know from Lemma 1 that the K smallest eigenvalues are in [0, 1). Let be solution to the generalized eigenvalue problem (6) with À E (0, 1). We know that x = Zy where y is an cigenvector associated with the same eigenvalue À for the aggregate graph. Since 1x is an eigenvector for the eigenvalue O, we have y Da 1x = 0. Using the fact that Da = W W(W + onTx), get:
K
my(ng an)y: = O. Σ
We then deduce from
and (8 that À & {Mi...., jK} and
K
Σ
ny (n + am)
1
O.
\/11 -1
This condition cannot be satisfied if À < in or >> μæ as the terms of the sum would be either all positive or all negative.
Now let y' be another eigenvector for the aggregate graph, with y² DDa 0. for the eigenvalue
X E (0, 1). By the same argument, we get:
K
Σ
ny(ng + an)usu/ = 0,
1=1
and
K ny(ny + om)
A/1; - N/n, - 0.
with X' & {.I,..., / This condition cannot be satisfied and X' are the same interval (py, My+1) for some j as the terms in the sum would be all positive. There are K - cigenvalues in (0, 1) for - such intervals, that is one eigenvalue per interval.
The main result of the paper is the following, showing that the k- largest cliques of the original graph can be recovered from the spectral embedding of the regularized graph dimension k. Theorem 1. Let X be the spectral embedding of dimension as defined by 2 for some k in the set (2...., K}.
Then sign(X X) gives the largest blocks of the graph.
Proof. Let x be the j-th column of the matrix X, for some j f2..... k}. In view of Lemma this is the eigenvector associated with eigenvalue Ay (Hy-1.H4)) so that
1- Xj n E (ng-1. A
In view of Lemma 2 all entries of x corresponding to blocks of size n1. n2.... .2..... have the same sign, the other having the opposite sign.
Theorem can can be extended in several ways. First, the assumption of distinct block sizes can easily be relaxed. If there are distinct values of block sizes, say my...., m blocks of sizes n1 >... >> Nl there are L distinct values for the thresholds μı and thus L distinct values for the eigenvalues X, in [0, 1). the multiplicity of the j-th smallest eigenvalue being equal to my. The spectral embedding in dimension h still gives k 1 cliques of the largest sizes.

---

Published as a conference paper at ICLR 2020
Second, the graph may have edges between blocks. Taking A ZZ" + for instance, for some parameter 2 0, the results are exactly the same, with a replaced by c+a. A key observation is that regularization really matters when + 0, in which case the initial graph becomes disconnected and, in the absence of regularization, the spectral emhedding may isolate small connected components of the graph. In particular, the regularization makes the spectral embedding much less sensitive to noise, as will be demonstrated in the experiments.
Finally, degree correction can be added by varying the node degrees within blocks. Taking A OZz"0, 0, for some arbitrary diagonal matrix 0 with positive entries, similar results can be obtained under the regularization Aa A a0Je. Interestingly, the spectral embedding in dimension & then recovers the k - 1 largest blocks in terms of normalized weight, the ratio of the total weight of the block to the number of nodes in the block.
REGULARIZATION OF BIPARTITE GRAPHS
Let B = R4*m be the biadjacency matrix of some bipartite graph with respectively n, m nodes in each part, i.c. B, > 0 if and only if there is an edge between node i in the first part of the graph and node j in the second part of the graph, with weight Biy. This is an undirected graph of n m nodes with adjacency matrix:
0
B
BTT
0
The spectral embedding of the graph 2 can be written in terms of the biadjacency matrix as follows:
{
BX2 = (1 B D2X2(I-A)
where X1,X2 are the embeddings of each part of the graph, with respective dimensions n x k and m x kt D1 = diag( (Bl,) and D: = diag(B"11, ). In particular, the spectral embedding of the graph follows from the generalized SVD of the biadjacency matrix B.
The complete regularization adds edges between all pairs of nodes, breaking the bipartite structure of the graph. Another approach consists in applying the regularization the biadjacency matrix, iee, in considering the regularized bipartite graph with biadjacency matrix:
Ba + aJ,
where J 1 Th is here the all-ones matrix of same dimension as B. The spectral embedding of the regularized graph is that associated with the adjacency matrix:
0
Ba
A.
(10)
BTT
0
As in Section 3 consider block model that the biadjacency matrix B is block-diagonal with all-ones block matrices on the diagonal. Each part of the graph consists of K groups of nodes of respective sizes n1 > ... n.K and mi ... > m., with nodes of block in the first part connected only to nodes of block j in the second part, for all j= 1,...,
We consider the generalized eigenvalue problem (6) associated with the above matrix Ag- In view of (9). this is equivalent to the generalized SVD of the regularized biadjacency matrix B,, We have the following results, whose proofs
deferred to the appendix:
Lemma 4. Let A1 S A I .... S An be the eigenvalues associated with the generalized eigenvalue problem (6) We have X1 0 < d2 S.....5 ...
λK < Ax+1 =... An-2K <... < Xn 2.
Lemma 5. Let x be a solution to the generalized eigenvalue problem 6 with X E (0, There exists 81, 82 E {+1,- -1} such that for each node i in block j of part p 2), n,m;
sign(x:)) = Sp
2 21 - X.
(n, + am) am))
Lemma 6. The K smallest eigenvalues satisfy:
0 >1 < M1 2 42 Ax < SKK
where for all j= 11=11... 1,..,, K,
n;m
11j = 1
(n, + am) + am)
5

---

Published as a conference paper at ICLR 2020
Theorem 2. Let X be the spectral embedding of dimension defined by 22. for some k. in the set 12). Then sign(X) gives the largest blocks of each part of the graph.
Like Theorem the assumption of decreasing block sizes can easily be relaxed. Assume that block pairs are indexed in decreasing order of M4j. Then the spectral embedding of dimension & gives the k 1 first block pairs for that order. It interesting to notice that the order now depends on a: when + 0+, the block pairs j of highest value (A, + my ) (cquivalently, highest harmonic mean of proportions of nodes in each part of the graph) are isolated first; when +00 the block pairs j of highest value m, (equivalently, the highest geometric mean of proportions of nodes in each part of the graph) are isolated first.
The results also extend to non-block diagonal biadjacency matrices B and degree-corrected models, as for Theorem
EXPERIMENTS
now illustrate the impact of regularization on the quality of spectral embedding. We focus on a clustering task, using both synthetic and real datasets where the ground-truth clusters are known. In all experiments, we skip the first dimension of the spectral embedding as not informative (the corresponding eigenvector is the all-ones vector, up to some multiplicative constant). The code to reproduce these experiments is available onlind"
5.1 TOY GRAPH
We first illustrate the theoretical results of the paper with a toy graph consisting of cliques of respective sizes 2. We compute the spectral embeddings in dimension 1, using the second smallest eigenvalue. Denoting by Z the membership matrix, we get X (-00.8, 0.11, 0.05)² for 1, showing that the embedding isolates the largest cluster, this not the case in the absence of regularization, where R 00.1,
5.2 DATASETS
This section describes the datasets used in our experiments. All graphs are considered as undirected. Table presents the main features of the graphs.
Stochastic Block-Model (SBM) We generate 100 instances of the same stochastic block model (Holland et al. 1983). There 100 blocks of size 20, with intra-block edge probability set 0.5 for the first 50 blocks and 0.05 for the other blocks. The inter-block edge probability set to 0.001 Other sets of parameters can be tested using the code available online. The ground-truth cluster of each node corresponds to its block.
20newsgroup (NG) This dataset consists of around 18000 newsgroups posts on 20 topics. This defines weighted bipartite graph between documents and words. The label of each document corresponds to the topic.
Wikipedia for Schools (WS) (Haruechaiyasak & Damrongrat 2008 This is the graph of hyper- links between a subset of Wikipedia pages. The label of each page is its category (c.g.. countries, mammals, physics).
Table 1: Main features of the graphs.
dataset
SBM 2000 ~ 5.103
NG
WS
# nodes (n)
10723
4591
# edges
s 2.106
~ 2.10
# clusters in ground truth
100
20
14
http://///thhho.oo////a/ttteeeea -mbeddi
1o

---

Published as a conference paper at ICLR 2020
5.3 METRICS
We consider a large set of metries from the clustering literature. All metrics upper-bounder by and the higher the score the better.
Homogeneity (H), Completeness (C) and V-measure score (V) Rosenberg Hirschberg, 2007]. Supervised metrics. A cluster is homogeneous if all its data points are members of a single class in the ground truth. A clustering is complete all the members of class in the ground truth belong to the same cluster in the prediction. Harmonic mean of homogeneity and completeness.
Adjusted Rand Index (ARD) (Hubert Arabic 1985). Supervised metric. This the corrected for chance version of the Rand Index which is itself accuracy pairs of samples.
Adjusted Mutual Information (AMT) version of the mutual information.
Vinh et al.
2010) Supervised metric. Adjusted for chance
Fowlkes-Mallows. Index (FMI)
(Fowlkes & Mallows 1983) Supervised metric. Geometric mean between precision and recall on the edge classification task, as described for the ARI.
Modularity (Q)
Unsupervised metric. Fraction of edges within clusters com- pared to that is some null model where edges are shuffled at random.
Newman 2006).
Normalized Standard Deviation (NSD) viation in cluster size.
Unsupervised metric. minus normalized standard de-
5.4 EXPERIMENTAL SETUP
All graphs are embedded in dimension 20, with different regularization parameters. To compare the impact of this parameter across different datasets, we use a relative regularization parameter (w/n" (n,, where w 1 A1, the total weight of the graph.
We use the K-Means algorithm with to cluster the nodes in the embedding space. The parameter K set the ground-truth number of clusters (other experiments with different values of K are reported in the Appendix). We use the Scikit-learn (Pedregosa al. (2011) implementation of K- Means and the metries, when available. The spectral embedding and the modularity are computed with the Seikit-network package, see the documentation for more detail
5.5 RESULTS
We report the results Table for relative regularization parameter a 0, 0, 10. We that the regularization generally improves performance, the optimal value of a depending on both the dataset and the score function. As suggested by Lemma 3 the optimal value of the regularization parameter should depend on the distribution of cluster sizes, on which we do not have any prior knowledge.
To test the impact of noise on the spectral embedding, we add isolated nodes with self loop to the graph and compare the clustering performance with and without regularization. The number of isolated nodes is given as a fraction of the initial number of nodes in the graph. Scores are computed only on the initial nodes. The results are reported Table 3 for the Wikipedia for Schools dataset. We observe that, in the absence of regularization, the scores drop even with only 1% noise. The computed clustering is trivial partition with all initial nodes the same cluster. This means that the 20 first dimensions of the spectral embedding focus the isolated nodes. On the other hand, the scores remain approximately constant the regularized case, which suggests that regularization makes the embedding robust to this type of noise.
https://scikitt-etwook..
10/
7

---

Published as a conference paper at ICLR 2020
Table 2: Impact of regularization clustering performance.
SBM
a
C
V
ARI
AMI
FMI
NSD
0
0.19
0.27
0.22
0.0
0.01
0.03
0.45
0.76
0.1
0.33
0.35
0.34
0.0
0.01
0.01
0,52
0.91
1
0.36
0.37
0.36
0.0
0.01
0.01
0,50
0.92
10
0.28
0.34
0.30
0.0
0.00
0.02
0.36
0.78
NG
H
C
V
ARI
AMI
FMI
Q
NSD
0.40
0.70
0.51
0.19
0.50
0.34
0.21
0.55
0.1
0.44
0.70
0.54
0.22
0.54
0.35
0.21
0.59
0.46
0.67
0.54
0.20
0.54
0.33
0.20
0.60
0.37
0.55
0.45
0.13
0.44
0.26
0.17
0.56
WS
ARI
AMI
FMI
Q
NSD
0
0.23
0.29
0.25
0.05
0.25
0.26
0.25
0.49
0.1
0.26
0.29
0.28
0.10
0.27
0.26
0.29
0.61
0.23
0.24
0.23
0.04
0.23
0.20
0.30
0.65
10
0.19
0.22
0.20
0.00
0.19
0.20
0.23
0.53
Table 3: Impact of noise on clustering performance (WS dataset).
=
noise
H
C
V
ARI
AMI
FMI
0 %
0.23
0.29
0.25
0.05
0.25
0.26
0.25
0.49
1 %
0.00
0.49
0.00
0.00
0.00
0.39
0.00
5 %
0.00
0.49
0.00
0.00
0.00
0.39
0.00
10
0.00
0.49
0.00
0.00
0.00
0.39
0.00
noise
H
C
V
ARI
AMI
FMI
0 %
0.23
0,24
0.23
0.04
0.23
0.2
0.3
0.65
1 %
0.24
0.24
0.24
0.04
0.23
0.2
0.3
0.66
5 %
0.23
0.23
0.23
0.05
0.22
0.2
0.3
0.67
10
0.24
0,23
0.23
0.05
0.23
0.2
0.3
0.67
CONCLUSION AND PERSPECTIVES
In this paper, we have provided a simple explanation for the well-known benefits of regularization on spectral embedding. Specifically, regularization forces the embedding to focus on the largest clusters, making the embedding more robust to noise. This result was obtained through the explicit characterization of the embedding for simple block model, and extended to bipartite graphs.
An interesting perspective of our work is the extension to stochastic block models, using for instance the concentration results proved in (Lei et al. 2015 Le et al., (017). Another problem of interest the impact of regularization on other downstream tasks, like link prediction. Finally, we would like further explore the impact of the regularization parameter, exploiting the theoretical results presented in this paper.
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Arash A Amini, Aiyou Chen, Peter J Bickel, Elizaveta Levina, et al. Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41 41(4):207-22122, 2013.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-591, 2002.
Thomas Bonald, Alexandre Hollocou, and Marc Lelarge. Weighted spectral embedding of graphs. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 494-501. IEEE, 2018.
Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. In Conference on Learning Theory, pp. 35-1, 2012.
Fan RK Chung. Spectral graph theory. American Mathematical Soc., 1997.
Edward B Fowlkes and Colin L Mallows. A method for comparing two hierarchical clusterings. Journal of the American statistical association, 78(383):553-569 1983.
Choochart Haruechaiyasaa and Chaianun Damrongrat. Article recommendation based on a topic model for wikipedia selection for schools. In International Conference on Asian Digital Libraries, pp. 339-342. Springer, 2008
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-13,, 1983.
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193-218 1985.
Antony Joseph, Bin Yu, et al. Impact of regularization spectral clustering. The Annals of Statis- tics, 44(4):1765-177)) 2016.
Nathan De Lara. The sparse + low rank trick for matrix factorization-bant graph algorithms. In Proceedings of the 15th International Workshop Mining and Learning with Graphs (MLG), 2019.
Can M Le. Elizaveta Levina, and Roman Vershynin. Concentration and regularization of random graphs. Random Structures & Algorithms, 51(3):538-555 2017.
Jing Lei, Alessandro Rinaldo, et al. Consistency of spectral clustering in stochastic block models.
The Annals of Statistics, 43(1)2215-237, 2015.
Ulrike Luxburg. A tutorial spectral clustering. Statisties and Computing, 17(4):395-416, De- cember 2007. ISSN 0960-3174. doi: 10.1007/s11222-000
000/10010011 11tp://112222000200000
Mark FJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(2)):8577-8882. 2006.
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems, pp. 849 856, 2002.
F. Pedregosa. G. Varoguaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825- 2011.
Tai Qin and Karl Rohe. Regularized spectral clustering under the degree-corrected stochastic block- model. In Advances in Neural Information Processing Systems, pp. 31 3120-3128, 2013.
Andrew Rosenberg and Julia Hirschberg. V-measure: A conditional entropy-based external cluster evaluation measure. In Proceedings of the 2007 joint conference empirical methods in natural language processing and computational natural language learning (EMNLP- -CNNLL,,,, pp. 410- 420, 2007.

---

Published as a conference paper at ICLR 2020
P Snell and Peter Doyle. Random walks and electric networks. Free Software Foundation, 2000.
Daniel A Spielman. Spectral graph theory and its applications. In Foundations of Computer Science, 2007. 07 48th Annual IEEE Symposium on, pp. 29-38. IEEE, 2007.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11 1(00)))2837-28844 2010.
Yilin Zhang and Karl Rohe. Understanding regularized spectral clustering via graph conductance. In Advances in Neural Information Processing Systems, pp. 10631-10640, 2018.
APPENDIX
We provide proof of Theorem 2 as well as a complete set of experimental results.
A REGULARIZATION OF BIPARTITE GRAPHS
The proof of Theorem follows the same workflow that of Theorem | Let Z1 R=* and Zz E R K be the left and right membership matrices for the block matrix B E Raxm The aggregated matrix B zf B22 E R The diagonal matrices of block sizes are W1 7 Z1 and W₂ Z Zz. We have the equivalent of Proposition] 1
Proposition 2. Let 21, 22 be solution to the generalized singular value problem:
{
Br D B xι o D202
Then either xf = =z and a or I1 Ziy1 and x2 Z22//2 where y1, U2 is solution to the generalized singular value problem:
By DD
BTT y D22222
Proof. Since the rank of B is equal to K, there n- K pairs of singular vectors (111, .22) associated with the singular values O, each satisfying 2 æ1 and Z x2 = O. By orthogonality, the other pairs of singular vectors satisfy 21 = Z1811 and 22 Zozz for some vectors yı, 1/2 R By replacing these in the original generalized singular value problem, we get that (3/1 122 is solution the generalized singular value problem for the aggregate graph.
In the following, focus the block model described in Section where B Z,
Proof of Lemma f The generalized eigenvalue problem (6) associated with the regularized matrix Aa is equivalent to the generalized SVD of the regularized biadjacency matrix Ba:
{
B a Da,1 Bd æ = a Da,232,
with = 1- X.
In view of Proposition 2 the singular value o = 0 has multiplicity n K, meaning that the eigen- K. Since the graph is connected, the eigenvalue 0 has multiplicity 1. The proof then follows from the observation that if (2) is a pair of singular vectors for the singular value o, then the vectors (z1, = are eigenvectors for the eigenvalues 1 o, 1
value À = 1 has multiplicity
Proof of Lemma 5 By Proposition the aggregate graph:
2 we can focus on the generalized singular value problem for
Balz oD..11 {
BT = oD..282.
Since
B, WT(k + axx W
10

---

Published as a conference paper at ICLR 2020
and
{
Da.1 Wi(W: + am!), Da. W2(Wi amml),
we have:
WI + aJk W222 W + ann)yno {
W2(xx + aJk) WW19 = W2 + ammmm)) N20.
Observing that Jx W1 oc 1K and JK W222 x 1x. we get:
{
(W2 + amlk 1 W282 & lk, (W1 anlx 2 With x 1x.
As two diagonal matrices commute, we obtain:
{ (Wi + amlk) (W2 + amlk) 1 - W, W291 = (mi + amlk) + 72222) lks (W1 + anIx) (W + amik) y)20 W, W282 (n ne(W2 + amil lkk
for constants 7/1 7/2 and
m (n, + am) + 122m
M1.
(ny + om on))mm) amm)o - nymy
71 + 72(m, + am)
12.1 = (nj + on) + am)o my
Letting 81 -sign(m (n, + am) + m2m;) and 82 - sign ( + mm + am)), we get:
sign(V1.)) = $1
sign(y2.)) =
n,m
20=1-A
(ny an) + am)
and the result follows from the fact that ZivI and x2 = Z282.
Proof of Lemma The proof is the same as that of Lemma where the threshold values follow
from Lemma 5
m2
Mj = (n, am) (m, + am)
Proof of Theorem Let æ be the j-th column of the matrix X, for some j E .2...., k}. In view of
Lemma 6 this is the eigenvector associated with eigenvalue X3 E (#j-1. M2)) view of Lemma all entries of æ corresponding to blocks of size ni 122 ..., , have the same sign, the other having opposite sign.
B EXPERIMENTAL RESULTS
In this section, we present more extensive experimental results.
Tables 4 and present results for the same experiment as in Table 2 but for different values of K, namely K (bisection of the graph) and K K Kruth/22 (half of the ground-truth value). As for K Ktrue. regularization generally improves clustering performance. However, the optimal value of a remains both dataset dependent and metric dependent. Note that, for the NG and WS datasets, the clustering remains trivial in the case K 2, one cluster containing all the nodes, until a certain amount of regularization.
Table 6 presents the different scores for both types of regularization the NG dataset. As see, preserving the bipartite structure of the graph leads to slightly better performance.
Finally, Table 7 shows the impact of regularization in the presence of noise for the NG dataset. The conclusions are similar as for the WS dataset: regularization makes the spectral embedding much more robust to noise.
11

---

Published as a conference paper at ICLR 2020
Table Impact of regularization on clustering performance.
SBM
H
C
V
ARI
AMI
FMI
Q
NSD
0
0.00
0.43
0.00
0.0
0.0
0.10
0.00
0.01
0.1
0,00
0.47
0,00
0.0
0.0
0.10
0.00
0.00
1
0.01
0.04
0.01
0.0
0.0
0.07
0.34
0.83
10
0.01
0.09
0.01
0.0
0.0
0.09
0.13
0.22
NG
ARI
AMI
FMI
Q
NSD
0.00
0.36
0.00
0.00
0.00
0.23
0.00
0.00
0.1
0.00
0.36
0.00
0.00
0.00
0.23
0.00
0.00
0.15
0.72
0.25
0.06
0.25
0.28
0.16
0.63
10
0.12
0.61
0.20
0.04
0.20
0.26
0.13
0.51
WS
ARI
AMI
FMI
Q
NSD
0.00
0.49
0.00
0.00
0.00
0.39
0.00
0.00
0.1
0.07
0.42
0.13
0.00
0.12
0.34
0.09
0.26
0.03
0.27
0.05
-0.01
0.05
0.35
0.09
0.13
10
0.02
0.16
0.04
-0.02
0.03
0.34
0.10
0.16
Table 5: Impact of regularization on clustering performance. K K
SBM
H
C
V
ARI
AMI
FMI
Q
NSD
0
0.08
0.21
0.11
0.0
0.00
0.05
0.41
0.47
0.1
0.20
0.27
0.23
0.0
0.01
0.02
0.55
0.84
1
0.24
0.29
0.26
0.0
0.00
0.02
0.54
0.90
10
0.19
0.28
0.23
0.0
0.00
0.03
0.40
0.70
NG
ARI
AMI
FMI
Q
NSD
0.27
0.76
0.40
0.11
0.39
0.31
0.20
0.41
0.1
0.28
0.73
0.41
0.11
0.40
0.30
0.18
0.43
0.38
0.72
0.50
0.18
0.50
0.34
0.21
0.57
10
0.31
0.62
0.42
0.11
0.42
0.27
0.17
0.51
WS
H
ARI
AMI
FMI
Q
NSD
O
0.23
0.29
0.25
0.05
0.25
0.26
0.25
0.49
0.1
0.26
0.29
0.28
0.10
0.27
0.26
0.29
0.61
0.23
0.24
0.23
0.04
0.23
0.20
0.30
0.65
10
0.19
0.22
0.20
-0.00
0.19
0.20
0.23
0.53
12

---

Published as a conference paper at ICLR 2020
Table 6: Regularization of the adjacency vs. biadjacency matrix on the NG dataset (a 1).
K Ktroe/2 /2
V
ARI
AMI
FMI
Q
std
Adj. Biadj.
0.38 0.41
0.72
0.50
0.18
0.50 0.52
0.34 0.35
0.21
0.57
0.72
0.52
0.19
0.21
0.61
K Kerue
ARI
AMI
FMI
Q
std
Adj. Biadj.
0.46
0.67
0.54
0.20
0.54
0.33
0.2
0.60
0.47
0.68
0.56
0.21
0.55
0.34
0.2
0.61
Table Impact of noise on clustering performance (NG dataset).
noise
H
C
V
ARI
AMI
FMI
std
0 %
0.40
0.70
0.51
0.19
0.50
0.34
0.21
0.55
1 %
0.00
1.00
0.00
0.00
0.00
0.23
0.00
5 %
0.14
0.65
0.23
0.06
0.23
0.27
0.13
0.30
10 %
0.00
0.36
0.01
0.00
0.00
0.23
0.00
0.00
noise
H
C
V
ARI
AMI
FMI
Q
std
0 %
0.46
0.67
0.54
0.20
0.54
0.33
0.2
0.60
1 %
0.48
0.66
0.56
0.21
0.56
0.33
0.2
0.64
5 %
0.49
0.66
0.56
0.23
0.56
0.34
0.66
10 %
0.45
0.66
0.54
0.20
0.54
0.33
0.2
0.59
13


Reviews:
[{"review_id": "rJlOcA2CKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nIt also introduces the problem in a gentle way, so that the range of possible readers is wide.\n\nIn general I'm happy with the paper, no major lacks on my side\n\nSuggestions: 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?\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bke7Sj6f9r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)