When I was reading paper, some people used this Laplacian metrix as a small step in their network analysis. I then found some papers and tutorials regarding this topic to have a general idea of what it is. The followings are some summary for reference.
Either Laplacian graph or spectral clustering is in the field of spectral graph theory. It studies the properties of graphs via the eigenvalues and eigenvectors of their associated graph matrices: the adjacency matrix and the graph Laplacian and its variants.
The most important application of the Laplacian is spectral clustering that corresponds to a computationally tractable solution to the graph partitionning problem.
Another application is spectral matching that solves for graph matching.
Basic information:
Degree matrix: a diagonal matrix which contains information about the degree of each vertex — the sum of weights of all edges attached to that vertex. The value of diagonal is the degree of the vertex.
Similarity function: also called similarity measures, to quantify the similarity between two objects and is the basic and preliminary thing to do clustering. Denoted as $s_{ij}$ between point i and point j. Some examples: Cosine similarity, kernel functions, Gaussian similarity ($s(x_i, x_j) = exp(-|x_i-x_j|^2/2\sigma^2)$).
Similarity graph: to model the local neighborhood relationships between the data points. There are several similarity graphs can be chosen:
- ε-neighborhood graph: connect all points whose pairwise distances that are smaller than ε. The ε-neighborhood graph is usually considered as an unweighted graph. (以数值来说话)
- k-nearest neighbor graphs: connect vertex $v_i$ with vertex $v_j$ if $v_j$ is among the k-nearest neighbors of $v_i$. (Attention: this definition can lead to a directed graph, as the neighborhood relationship is not symmetric, e.g. vertex $v_j$ can be the k-th nearest neighbor of $v_i$ but $v_i$ may not be the k-th nearest neighbor of $v_j$) (以个数来说话)
- fully connected graph: simply connect all points with positive similarity with each other, and weight all edges by $s_{ij}$. As the graph should represent the local neighborhood relationships, this construction is only useful if the similarity function itself models local neighborhoods, e.g. Gaussian similarity function.
Graph Laplacian and properties
The unnormalized Laplacian matrix:
$$ L = D - A $$
where, D is the degree matrix and A is the adjacency matrix of the graph.
Property of the unnormalized laplacian matrix:
- For every vector $f\in R^n$: $f’Lf=\frac12\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2$
- L is symmetric and positive semi-definite
- The smallest eigenvalue of L is 0, the corresponding eigenvextor is the constant one vector 1.
- L has $n$ non-negative, real-valued eigenvalues $0=\lambda_1 \le \lambda_2 \le … \le \lambda_n$
The normalized Laplacian:
There are two matrices that are called normalized graph Laplacians in literature:
$$L_{sym} = D^{-1/2}LD^{-1/2} = I - D^{-1/2}WD^{-1/2}$$
$$L_{rm} = D^{-1}L = I - D^{-1}W$$
The first matrix is denoted by $L_{sym}$ as it is symmetric matrix.
The seond one is denoted by $L_{rm}$ as it is closely related to a random walk.
Property of the normalized laplacian matrix:
- For every vector $f\in R^n$: $f’L_{sym}f=\frac12\sum_{i,j=1}^nw_{ij}(\frac{f_i}{\sqrt {d_i}} - \frac{f_j}{\sqrt {d_j}})^2$
- $\lambda$ is an eigenvalue of $L_{rw}$ with eigenvector $u$ if and only if $\lambda$ is an eigenvalue of $L_{sym}$ with eigenvector $w=D^{1/2}u$
- $\lambda$ is an eigenvalue of $L_{rw}$ with eigenvector $u$ if and only if $\lambda$ and $u$ solve the generalized eigenproblem $Lu = λDu$
- 0 is an eigenvalue of $L_{rw}$ with the constant one vector 1 as eigenvector. 0 is an eigenvalue of $L_{sym}$ with eigenvector $D^{1/2}1$.
- $L_{sym}$ and $L_{rw}$ are positive semi-definite and have $n$ nonnegative real-valued eigenvalues $0 = λ_1 ≤···≤ λ_n$.
Spectral clustering algorithms
Assume the data consists of $n$ “points” $x_1,…,x_n$ which can be arbitrary objects. We measure their pairwise similarities $s_{ij} = s(x_i,x_j)$ by some similarity function which is symmetric and non-negative, and we denote the corresponding similarity matrixby $S = (s_{ij} )_{i,j=1,…,n}$.
Unnormalized spectral clustering
Input: Similarity matrix $S ∈ R^{n×n}$, number k of clusters to construct.
- Construct a similarity graph by one of similarity functions. Let $W$ be its weighted adjacency matrix.
- Compute the unnormalized Laplacian $L$.
- Compute the first $k$ eigenvectors $u_1,…,u_k$ of $L$
- Let $U ∈ R^{n×k}$ be the matrix containing the vectors $u_1,…,u_k$ as columns.
- For $i = 1,…,n$, let $y_i ∈ R^k$ be the vector corresponding to the i-th row of $U$
- Cluster the points $(y_i)_{i=1,…,n}$ in $R^k$ with the k-means algorithm into clusters $C_1,…,C_k$
Output: Clusters $A_1,…,A_k$ with $A_i =\{j|y_j ∈ C_i\}$.
Normalized spectral clustering using $L_{rw}$
Input: Similarity matrix $S ∈ R^{n×n}$, number k of clusters to construct.
- Construct a similarity graph by one of similarity functions. Let $W$ be its weighted adjacency matrix.
- Compute the unnormalized Laplacian $L$.
- Compute the first k generalized eigenvectors $u_1,…,u_k$ of the generalized eigenproblem $Lu=λDu$
- Let $U ∈ R^{n×k}$ be the matrix containing the vectors $u_1,…,u_k$ as columns.
- For $i = 1,…,n$, let $y_i ∈ R^k$ be the vector corresponding to the i-th row of $U$
- Cluster the points $(y_i)_{i=1,…,n}$ in $R^k$ with the k-means algorithm into clusters $C_1,…,C_k$
Output: Clusters $A_1,…,A_k$ with $A_i =\{j|y_j ∈ C_i\}$.
Normalized spectral clustering using $L_{sym}$
Input: Similarity matrix $S ∈ R^{n×n}$, number k of clusters to construct.
- Construct a similarity graph by one of similarity functions. Let $W$ be its weighted adjacency matrix.
- Compute the normalized Laplacian $L_{sym}$.
- Compute the first k eigenvectors $u_1,…,u_k$ of $L_{sym}$
- Form the matrix $T ∈ R^{n×k}$ from $U$ by normalizing the rows to norm 1,that is set $t_{ij} =u_{ij}/(\sum_k u_{ik}^2)^{1/2}$.
- For $i = 1,…,n$, let $y_i ∈ R^k$ be the vector corresponding to the i-th row of $T$
- Cluster the points $(y_i)_{i=1,…,n}$ in $R^k$ with the k-means algorithm into clusters $C_1,…,C_k$
Output: Clusters $A_1,…,A_k$ with $A_i =\{j|y_j ∈ C_i\}$.
Attention: Eigenvalues will always be ordered increasingly, respecting multiplicities. Therefore, “the first k eigenvectors” refers to the eigenvectors corresponding to the k smallest eigenvalues.
Reference:
https://www.sciencedirect.com/science/article/pii/S1053811917305463
https://link.springer.com/content/pdf/10.1007%2Fs11222-007-9033-z.pdf
http://www2.imm.dtu.dk/projects/manifold/Papers/Laplacian.pdf
https://csustan.csustan.edu/~tom/Clustering/GraphLaplacian-tutorial.pdf
https://www.youtube.com/watch?v=FRZvgNvALJ4