A Min-max Cut Algorithm for Graph Partitioning and Data Clustering

July 9, 2022

重みつき隣接行列で表した無向グラフを2分割するクラスタリングであり、グラフ間の類似を最小化し、グラフ内のノードの類似の最大化をはかる。隣接行列を$W_{uv}$, $\text{cut}(A, B)=W(A, B)$, $W(A, B) = \sum_{u\in A, v\in B}W_{uv}$として、以下の目的関数を最小化する分割を探索する。ノードを2つに分ける最適解はNP完全であるため、近似解をもとめる。 $$ \text{Mcut} = \frac{\text{cut}(A, B)}{W(A)} + \frac{\text{cut}(A, B)}{W(B)} $$

$W_A$や$W_B$をサブグラフ$A$, $B$内の類似度、$W_{A, B}, W_{B, A}$をグラフ間の類似度とする。 $W$を次のようにインデックスを置きかえても一般性は失われない。 $$ W= \begin{pmatrix} W_A & W_{A, B} \\ W_{B,A} & W_B \end{pmatrix} $$

並びかえた後では、$D=\text{diag}(W\boldsymbol{e})$, $\boldsymbol{e}=[1,\dots , 1]^\top$, $\boldsymbol{\rm x}=(1\dots 1, 0\dots 0)^\top$, $\boldsymbol{\rm y}=(0\dots 0,1\dots 1)^\top$ とすると、MCutを以下のように表せる。 $$ \text{Mcut}=\frac{\boldsymbol{\rm x}^\top(D-W)\boldsymbol{\rm x}}{\boldsymbol{\rm x}^\top W\boldsymbol{\rm x}} + \frac{\boldsymbol{\rm y}^\top(D-W)\boldsymbol{\rm y}}{\boldsymbol{\rm y}^\top W\boldsymbol{\rm y}} $$

Mcutの最適化はNP完全なので、線形緩和問題を考える。ノードを$u$として、$u \in A$であれば$a$, $u\in B$であれば$-b$のどちらに属するか示す最適な$\boldsymbol{\rm q}(q_u=\{a, -b\})$を見つける。このとき、目的関数は $$ \min_{\boldsymbol{\rm q}}\text{Mcut}(A, B)=\min_{\boldsymbol{\rm q}}\frac{J_N(A, B)}{1-J_N(A, B)/2}\Rightarrow \min_{\boldsymbol{\rm q}}J_N(A, B) $$ ただし $$ J_N(A, B)\equiv J_N(\boldsymbol{\rm q})=\frac{\boldsymbol{\rm q}^\top (D-W)\boldsymbol{\rm q}}{\boldsymbol{\rm q}^\top D\boldsymbol{\rm q}} $$

$q_u$を区間$[-1, 1]$の実数とすると、レイリー商$J_N(\boldsymbol{\rm q})$を最小化する解は$\boldsymbol{\rm q}^\top \boldsymbol{\rm e}=0$ として $$ (D-W)\boldsymbol{\rm q}=\zeta D\boldsymbol{\rm q} $$ のFiedler vector $\boldsymbol{\rm q}_2$とその固有値 Fiedler value $\zeta_2$である。 Fielder vectorをソートし、Mcutを最小値にする分割を線形探索する。

線形探索で分割した後は、境界に近いノードが所属するサブグラフを他方に移し、Mcutの値をさらに最小化する。 $l(A, B)=W(A, B)/W(A)W(B)$の値が小さいほど、境界に近い。

論文へのリンク