[TOC]

Spectral Clustering

1. Formalization

1.1. Given

• An undirected graph $G=(V,E)$ ($|V|=n$)
• The edge $(v_i,v_j)$ is weighted by similarity $w_{i,j}$

1.2. Optimization problem

$$\begin{array}{cccc}& \underset{A_i\subset V}{\text{minimize}}& & \sum _{i=1}^k\frac{\text{cut}(A_i,\overline{A_i})}{\text{Vol}\left(A_i\right)}\\ & \text{subject to}& & \underset{i=1}{\overset{k}{⨆}}{A}_i=V\end{array}$$ where $\overline{A}$ is the complement of $A$, and "cut(A)" and "vol(A)" $(A\subset V)$ are defined by $$\begin{array}{cc}\text{cut}(A,\overline{A})& =\sum _{v_i\in A,v_j\in \overline{A}}{w}_{i,j}\\ \text{vol}\left(A\right)& =\sum _{v_i\in A}{d}_i=\sum _{v_i\in A}\sum _{v_j\in V}{w}_{i,j}\end{array}$$ We denote $d_i$ by the degree of node $v_i$.

2. Preparation

Def(unnormalized graph Laplacian matrix)
We denote $D$ by the degree matrix defined by

$$D=\text{diag}(d_1,\dots ,d_n)=\left(\begin{array}{cccc}{d}_1& & & \\ & d_2& & \\ & & \ddots & \\ & & & d_n\end{array}\right)$$

We denote $L\equiv D-W$ be the unnormalized graph Laplacian matrix

-

Theorem1
For every vector $f\in R^n$ we have

$$f^{\prime }Lf=\frac{1}{2}\sum _{i,j}{w}_{i,j}(f_i-f_j{)}^2$$

(proof) $$\begin{array}{cc}{f}^{\prime }Lf& =f^{\prime }(D-W)f\\ & =\sum _i{d}_i{f}_i^2-\sum _{i,j}{w}_{i,j}{f}_i{f}_j\\ & =\frac{1}{2}(\sum _i{d}_i{f}_i^2-\sum _{i,j}{w}_{i,j}{f}_i{f}_j+\sum _j{d}_j{f}_j^2)\\ & =\frac{1}{2}\sum _{i,j}{w}_{i,j}(f_i-f_j{)}^2\end{array}$$

-

Theorem2
For $A_l\subset V,h_l\equiv (h_{1,l},\dots ,h_{n,l}{)}^{\prime }\in R^n$, where

$$h_{i,l}\equiv \frac{1_{A_l}\left(v_i\right)}{\sqrt{\text{vol}\left(A_l\right)}}$$

and

$$1_{A_l}\left(v_i\right)\equiv \{\begin{array}{cc}1& (v_i\in A_l)\\ 0& \left(\text{otherwise}\right)\end{array}$$

Then, we have

$$h_l^{\prime }L{h}_l=\frac{\text{cut}(A_l,\overline{A_l})}{\text{vol}\left(A_l\right)}$$

(proof) $$\begin{array}{cc}{h}_l^{\prime }L{h}_l& =\frac{1}{2}\sum _{i,j}{w}_{i,j}(h_{i,l}-h_{j,l}{)}^2\\ & =\frac{1}{2}\sum _{i,j}{w}_{i,j}(\frac{1_{A_l}\left(v_i\right)}{\sqrt{\text{vol}{A}_l}}-\frac{1_{A_l}\left(v_j\right)}{\sqrt{\text{vol}{A}_l}})\\ & =\sum _{v_i\in A_l,v_j\in \overline{A_l}}{w}_{i,j}\frac{1}{\text{Vol}\left(A_l\right)}\\ & =\frac{\text{cut}(A_l,\overline{A_l})}{\text{Vol}\left(A_l\right)}\end{array}$$

-

Theorem3
$h_l^{\prime }D{h}_m={\delta }_{l,m}$

(proof)

$$\begin{array}{cc}{h}_l^{\prime }D{h}_m& =\sum _i{d}_i{h}_{i,l}{h}_{i,m}\\ & =\sum _i{d}_i\frac{1_{A_l}\left(v_i\right)}{\sqrt{\text{vol}{A}_l}}\frac{1_{A_l}\left(v_i\right)}{\sqrt{\text{vol}{A}_m}}\\ & ={\delta }_{l,m}\end{array}$$

3. Relaxation

$$\begin{array}{cccc}& \underset{A_i\subset V}{\text{minimize}}& & \sum _{i=1}^k\frac{\text{cut}(A_i,\overline{A_i})}{\text{Vol}\left(A_i\right)}\\ & \text{subject to}& & \underset{i=1}{\overset{k}{⨆}}{A}_i=V\\ \iff & \underset{A_i\subset V}{\text{minimize}}& & Tr\left(H^{\prime }LH\right)\\ & \text{subject to}& & \underset{i=1}{\overset{k}{⨆}}{A}_i=V\\ & & & H^{\prime }DH=I_k\\ \simeq & \underset{H\in R^{n\times k}}{\text{minimize}}& & Tr\left(H^{\prime }LH\right)\\ & \text{subject to}& & H^{\prime }DH=I_k\\ \iff & \underset{T\in R^{n\times k}}{\text{minimize}}& & Tr\left(T^{\prime }{D}^{-1/2}L{D}^{-1/2}T\right)\\ & \text{subject to}& & T^{\prime }T=I_k\\ & & & (T=D^{1/2}H)\end{array}$$

We call those of equations (1), (2), (3), and (4) from above.

proof(1)$\iff$(2) $$\begin{array}{cc}Tr\left(H^{\prime }LH\right)& =\sum _{l=1}^k{h}_l^{\prime }L{h}_l\\ & =\sum _{l=1}^k\frac{\text{cut}(A_l,\overline{A_l})}{\text{vol}\left(A_l\right)}\end{array}$$

$(l,m)$ element of $H^{\prime }DH$ = $h_l^{\prime }D{h}_m={\delta }_{l,m}$

proof(3)$\iff$(4)

(3)$\Rightarrow$(4)

If $H$ is the optimal solution of (3), we set $T=D^{1/2}H$. Then, we have $T^{\prime }T=H^{\prime }{D}^{-1/2}{D}^{-1/2}H=H^{\prime }{D}^{-1}H=I_k$, thus $H$ is the feasible solution of (4). Moreover, we have $$\begin{array}{cc}Tr\left(T^{\prime }{D}^{-1/2}L{D}^{-1/2}T\right)& =Tr\left(H^{\prime }LH\right)\end{array}$$ Therefore, the optimal value of (4) is less than or equal to the optimal value of (3). The other is proved in the same way.

For solving optimization of (4), we show below theorem.

Theorem4 (Extermal partial trace)
行列$A\in C^{n\times n}$をエルミート行列とし,その固有値を${\lambda }_1,\cdots ,{\lambda }_n$. 対応する固有ベクトルを$u_1,\cdots ,u_n,⟨u_i,u_j⟩={\delta }_{i,j}$とする. このとき, 固有値について${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$が成立しているならば,任意の$q\in \{1,2,\dots ,n\}$と正規直交系$\{x_1,\cdots ,x_q:x_i\in C^{n\times n},⟨x_i,x_j⟩={\delta }_{i,j}\}$に対して,

$$\sum _{i=1}^q{\lambda }_i\le \sum _{i=1}^q{x}_i^{\ast }A{x}_i$$

が成立.さらに,$x_i=u_i(i=1,2,\cdots ,q)$ ならば等号が成立.

Proof. $A$はエルミート行列なので,固有値は全て実数でありユニタリ行列によって対角化出来ることに注意する.(証明略)
$A$はエルミート行列なので, $$UA{U}^{\ast }=\left(\begin{array}{ccc}{\lambda }_1& & \\ & \ddots & \\ & & {\lambda }_n\end{array}\right)=diag({\lambda }_1,\dots ,{\lambda }_n)$$ となるような$U=(u_1,u_2,\dots ,u_n{)}^{\ast }$をとることができる. ここで,$x_1,x_2,\dots ,x_q,x_{q+1},\dots x_n$が$C^n$の正規直交基底になるように$x_{q+1},x_{q+1},\cdots ,x_n$をとる. また, $X:=(x_1,\dots ,x_n)$と定義する.このとき, $$\begin{array}{c}{X}^{\ast }AX=\left(\begin{array}{c}{x}_1^{\ast }\\ ⋮\\ x_n^{\ast }\end{array}\right)A(x_1,\dots ,x_n)=\left(\begin{array}{c}{x}_1^{\ast }A\\ ⋮\\ x_n^{\ast }A\end{array}\right)(x_1,\dots ,x_n)\end{array}$$ ゆえに,$X^{\ast }AX$の$(i,j)$成分は $x_i^{\ast }A{x}_j$ と表される. ここで任意の正方行列$B\in C^n$に対して$s$次主小行列(首座小行列) principal submatrix を $B_s$と表記することにする. つまり $$\begin{array}{c}B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \cdots & b_{1n}\\ b_{21}& b_{22}& \cdots & b_{2n}\\ ⋮& ⋮& \ddots & \\ b_{n1}& b_{n2}& \cdots & b_{nn}\end{array}\right),B_s=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \cdots & b_{1s}\\ b_{21}& b_{22}& \cdots & b_{2s}\\ ⋮& ⋮& \ddots & \\ b_{s1}& b_{s2}& \cdots & b_{ss}\end{array}\right)\end{array}$$ このとき, $$\sum _{i=1}^q{x}_i^{\ast }A{x}_i=Tr[(X^{\ast }AX{)}_q]$$ が成立.一方で $$\begin{array}{cc}(i,j)\text{element of}{X}^{\ast }AX& =(i,j)\text{element of}{X}^{\ast }{U}^{\ast }diag({\lambda }_1,\dots ,{\lambda }_n)\\ & =(i,j)\text{element of}{Y}^{\ast }diag({\lambda }_1,\dots ,{\lambda }_n)Y(Y=UX\in C^n)\\ & =\sum _{k=1}^n|y_{ki}{|}^2{\lambda }_k\end{array}$$ 以上より, $$\begin{array}{cc}\sum _{i=1}^q{x}_i^{\ast }A{x}_i& =Tr[(X^{\ast }AX{)}_q]\\ & =\sum _{i=1}^q\sum _{k=1}^n|y_{ki}{|}^2{\lambda }_k\\ & =\sum _{k=1}^n(\sum _{i=1}^q|y_{ki}{|}^2){\lambda }_k\end{array}$$ ここで,$U,X$はユニタリ行列であるので,$Y=UX\in C^{n\times n}$もユニタリ行列.(例えば任意の$a,b\in C^{n\times n}$に対して, $⟨UXa,UXb⟩=⟨a,b⟩$ を示せば良い.) ゆえに,行ベクトルの長さは1であるので, $$0\le \sum _{i=1}^q|y_{ki}{|}^2\le \sum _{i=1}^n|y_{ki}{|}^2=1(k\in \{1,2,\dots ,n\left\}\right)$$ また,列ベクトルの長さは1であるので, $$\sum _{k=1}^n\sum _{i=1}^q|y_{ki}{|}^2=\sum _{i=1}^q\sum _{k=1}^n|y_{ki}{|}^2=q$$ よって, ${\sum }_{i=1}^q{x}_i^{\ast }A{x}_i={\sum }_{k=1}^n({\sum }_{i=1}^q|y_{ki}{|}^2){\lambda }_k$は $$\begin{array}{c}\sum _{i=1}^q|y_{ki}{|}^2=\{\begin{array}{c}1(k\in \{1,2,\dots ,q\left\}\right)\\ 0\left(others\right)\end{array}\end{array}$$ のとき最小値${\lambda }_1+\cdots +{\lambda }_q$をとる. (気持ちとしては出来るだけ小さい${\lambda }_k$に$|y_{ki}|$を割り当てることを考える.) また, $x_i=u_i(i=1,2,\dots ,q)$ならば, $$X^{\ast }AX=U{U}^{\ast }diag({\lambda }_1,\dots ,{\lambda }_n)U{U}^{\ast }=diag({\lambda }_1,\dots ,{\lambda }_n)$$ であるので等号成立.

3.1. Solving below optimization problem

$$\begin{array}{cccc}& \underset{T\in R^{n\times k}}{\text{minimize}}& & Tr\left(T^{\prime }{D}^{-1/2}L{D}^{-1/2}T\right)\\ & \text{subject to}& & T^{\prime }T=I_k\\ & & & (T=D^{1/2}H)\end{array}$$ Let $T$ be $$\begin{array}{c}T\equiv (x_1,\dots ,x_k)\end{array}$$ where $x_i\in R^n$. Considering the constraint, we have $$T^{\prime }T=I_k\iff ⟨x_i,x_j⟩={\delta }_{i,j}$$ , which implices $x_i,\dots ,x_k$ are orthogonal system. If we see $D^{-1/2}L{D}^{-1/2}\in R^{n\times n}$ as the $A$ of theorem4, $$\begin{array}{c}Tr\left(T^{\prime }{D}^{-1/2}L{D}^{-1/2}T\right)=Tr\left(T^{\prime }AT\right)=\sum _{l=1}^k{x}_i^{\prime }A{x}_i\end{array}$$

Therefore, if we list eigenvalues of $A=D^{-1/2}L{D}^{-1/2}$ in ascending order ${\lambda }_1,\dots ,{\lambda }_n$ and the corresponding orthgonal system $u_1,\dots ,u_k$, we get the optimal value of ${\sum }_{l=1}^k{\lambda }_k$ when $T=(u_1,\dots ,u_k)$.

When clustering, we set $H\equiv D^{-1/2}T\in R^{n\times k}$ and $y_i\equiv (h_{i,1},\dots ,h_{i,k})\in R^k(i=1,\dots n)$, we apply the other clustering method to $\{y_i\mid v_i\in V\}$

3.2. Reference

https://www.slideshare.net/pecorarista/ss-51761860