graph Laplacians is used.We name both algorithms after two popular papers,for more references and history please see Section 9. Normalized spectral clustering according to Shi and Malik(2000) Input:Similarity matrix SER"xm,number k of clusters to construct. Construct a similarity graph by one of the ways described in Section 2.Let W be its weighted adjacency matrix. Compute the unnormalized Laplacian L. Compute the first k generalized eigenvectors u1,...,uk of the generalized eigenprob- lem Lu=入Du. 。LetU∈Rnxk be the matrix containing the vectors山1，：，uk as columns. For i=1,...,n,let yiERk be the vector corresponding to the i-th row of U. Cluster the points (vi)i=1...n in Rk with the k-means algorithm into clusters C1:....Ck. Output:Clusters A1,...,Ak with Ai=jlyCi}. Note that this algorithm uses the generalized eigenvectors of L,which according to Proposition 3 correspond to the eigenvectors of the matrix Lw.So in fact,the algorithm works with eigenvectors of the normalized Laplacian Lw,and hence is called normalized spectral clustering.The next algorithm also uses a normalized Laplacian,but this time the matrix Lsym instead of Lrw.As we will see,this algorithm needs to introduce an additional row normalization step which is not needed in the other algorithms.The reasons will become clear in Section 7. Normalized spectral clustering according to Ng,Jordan,and Weiss(2002) Input:Similarity matrix SERnxm,number k of clusters to construct. Construct a similarity graph by one of the ways described in Section 2.Let W be its weighted adjacency matrix. Compute the normalized Laplacian Lsym. Compute the first k eigenvectors u1,...,uk of Lsym. Let UE Rnxk be the matrix containing the vectors u1,...,uk as columns. Form the matrix TE Rnxk from U by normalizing the rows to norm 1, that is set ti=u/(∑ku绿)/2. .For i=1,...,n,let yi ER be the vector corresponding to the i-th row of T. Cluster the points (yi)i=1.....n with the k-means algorithm into clusters C1,...,Ck. Output: C1 usters A1,.·,Ak with A:={功∈C}. All three algorithms stated above look rather similar,apart from the fact that they use three different graph Laplacians.In all three algorithms,the main trick is to change the representation of the abstract data points zi to points yiER.It is due to the properties of the graph Laplacians that this change of representation is useful.We will see in the next sections that this change of representation enhances the cluster-properties in the data,so that clusters can be trivially detected in the new representation. In particular,the simple k-means clustering algorithm has no difficulties to detect the clusters in this new representation.Readers not familiar with k-means can read up on this algorithm in numerousgraph Laplacians is used. We name both algorithms after two popular papers, for more references and history please see Section 9. Normalized spectral clustering according to Shi and Malik (2000) Input: Similarity matrix S ∈ ❘ n×n, number k of clusters to construct. • Construct a similarity graph by one of the ways described in Section 2. Let W be its weighted adjacency matrix. • Compute the unnormalized Laplacian L. • Compute the first k generalized eigenvectors u1, . . . , uk of the generalized eigenprob￾lem Lu = λDu. • Let U ∈ ❘ n×k be the matrix containing the vectors u1, . . . , uk as columns. • For i = 1, . . . , n, let yi ∈ ❘ k be the vector corresponding to the i-th row of U. • Cluster the points (yi)i=1,...,n in ❘ k with the k-means algorithm into clusters C1, . . . , Ck. Output: Clusters A1, . . . , Ak with Ai = {j| yj ∈ Ci}. Note that this algorithm uses the generalized eigenvectors of L, which according to Proposition 3 correspond to the eigenvectors of the matrix Lrw. So in fact, the algorithm works with eigenvectors of the normalized Laplacian Lrw, and hence is called normalized spectral clustering. The next algorithm also uses a normalized Laplacian, but this time the matrix Lsym instead of Lrw. As we will see, this algorithm needs to introduce an additional row normalization step which is not needed in the other algorithms. The reasons will become clear in Section 7. Normalized spectral clustering according to Ng, Jordan, and Weiss (2002) Input: Similarity matrix S ∈ ❘ n×n, number k of clusters to construct. • Construct a similarity graph by one of the ways described in Section 2. Let W be its weighted adjacency matrix. • Compute the normalized Laplacian Lsym. • Compute the first k eigenvectors u1, . . . , uk of Lsym. • Let U ∈ ❘ n×k be the matrix containing the vectors u1, . . . , uk as columns. • Form the matrix T ∈ ❘ n×k from U by normalizing the rows to norm 1, that is set tij = uij/( P k u 2 ik) 1/2. • For i = 1, . . . , n, let yi ∈ ❘ k be the vector corresponding to the i-th row of T. • Cluster the points (yi)i=1,...,n with the k-means algorithm into clusters C1, . . . , Ck. Output: Clusters A1, . . . , Ak with Ai = {j| yj ∈ Ci}. All three algorithms stated above look rather similar, apart from the fact that they use three different graph Laplacians. In all three algorithms, the main trick is to change the representation of the abstract data points xi to points yi ∈ ❘ k . It is due to the properties of the graph Laplacians that this change of representation is useful. We will see in the next sections that this change of representation enhances the cluster-properties in the data, so that clusters can be trivially detected in the new representation. In particular, the simple k-means clustering algorithm has no difficulties to detect the clusters in this new representation. Readers not familiar with k-means can read up on this algorithm in numerous 7