What Laplacian should we use for spectral clustering?

Question

The second eigenvector of the normalized Laplacian $I-D^{-1}W$ or the symmetric normalized Laplacian $I-D^{-1/2}WD^{-1/2}$ can be used to approximate a minmizer of the normalized cut problem.

Which one should be used and why ?

Answer 1

The paper "A tutorial on spectral clustering" mentions that (page 27):

Which normalized Laplacian?

Looking at the differences between the two normalized spectral clustering algorithms using $L_{rw}$ and $L_{sym}$, all three explanations of spectral clustering are in favor of $L_{rw}$. The reason is that the eigenvectors of $L_{rw}$ are cluster indicator vectors $\mathbb{1}_{A_i}$ , while the eigenvectors of Lsym are additionally multiplied with $D^{1/2}$ , which might lead to undesired artifacts. As using $L_{sym}$ also does not have any computational advantages,

we thus advocate for using $L_{rw}$.

where (page 5):

L = D - W

$L_{sym}$ := $D^{−1/2}LD^{−1/2}$ = $I − D^{−1/2}W D^{−1/2}$

$L_{rw}$ := $D^{−1}L$ = $I − D^{−1}W$.