Why Laplacian Matrix need normalization and how come the sqrt of Degree Matrix?

Unnormalized Laplacian serve in the approximation of the minimization of RatioCut, while normalized Laplacian serve in the approximation of the minimization of NCut.

Basically, in the unnormalized case, you optimize an objective relative to the number of nodes in each cluster.
And, in the normalized case, you optimize the objective relative to the volume of each cluster.

The square root comes from this: $f^top(I-D^{-1}A)f = g^top(I-D^{-1/2}AD^{-1/2})g$ where $g=D^{1/2}f$.

So, if your optimization method relies on a symmetric PSD matrix, you use the symmetric normalized Laplacian, and then remove the bias by computing $D^{-1/2}g$ to recover $f$.

Let $G=(V,E)$ be a graph with vertex set $V={v_1,dots,v_n}$ and edge set $E$, $w_{ij}$ denote the positive weight on the edge between $v_i$ and $v_j$. Let ${C_i:1 le i le k}$ be a disjoint partition of $V$. Define
Cut(C_i:1le ile k)triangleqfrac{1}{2}sum_{c=1}^k sum_{i in C_c,jin bar C_c}A_{ij}
RatioCut(A_i:1le i le k)triangleqsum_{i=1}^kfrac{Cut(A_i,bar A_i)}{|A_i|}
NCut(A_i:1le i le k)triangleqsum_{i=1}^kfrac{Cut(A_i,bar A_i)}{vol(A_i)}

f_i=begin{cases}sqrt{|bar A|/|A|} {amp}amp; text{if } v_iin A\sqrt{|A|/|bar A|} {amp}amp; text{if } v_i in bar Aend{cases}

f^top L f {amp}amp; = frac{1}{2}sum_{i,j=1}^n w_{ij}(f_i-f_j)^2 \
{amp}amp; = frac{1}{2}sum_{iin A,jin bar A}w_{ij}left(sqrt{frac{|bar A|}{|A|}} sqrt{frac{|A|}{|bar A|}}right) frac{1}{2}sum_{iin bar A,jin A}w_{ij}left(-sqrt{frac{|bar A|}{|A|}}-sqrt{frac{|A|}{|bar A|}}right) \
{amp}amp;=Cut(A,bar A)left(frac{|bar A|}{|A|} frac{|A|}{|bar A|} 2right)\
{amp}amp;=Cut(A,bar A)left(frac{|A| |bar A|}{|A|} frac{|A| |bar A|}{|bar A|}right)\
{amp}amp;=|V| RatioCut(A,bar A)

You can also see that $sum_{i=1}^n f_i=0$, so $fperp mathbb 1$.

So minimizing RatioCut is equivalent to the following problem:
min_{Asubset V}f^top L ftext{ subject to $fperpmathbb 1$, $f_i$ as defined in Eq.eqref{1}},|f|^2=sqrt{n}

For this case, define
sqrt{frac{vol(bar A)}{vol(A)}} {amp}amp;text{if $v_iin A$}\
sqrt{frac{-vol(A)}{vol(bar A)}} {amp}amp;text{if $v_iin bar A$}\

Similar to above, we have $Dfperp mathbb 1$, $f^top D f=vol(V)$ and $f^top L f=vol(V)NCut(A,bar A)$.
Minimizing NCut is equivalent to
min_{Asubset V} f^top L f text{ subject to $f$ as in Eq.eqref{2}, $Dfperp mathbb 1$ and $f^top Df=vol(V)$}
Substituting $g=D^{1/2}f$ we get
min_{Asubset V} g^top D^{-1/2}LD^{-1/2} g text{ subject to $g=D^{1/2}f$, $f$ as in Eq.eqref{2}, $gperp D^{1/2}mathbb 1$ and $|g|^2=vol(V)$}

Then observe that $D^{-1/2}LD^{-1/2}$ is the symmetric normalized Laplacian.


Понравилась статья? Поделиться с друзьями:
Website Name