はじめに

A Tutorial on Spectral Clusteringを読んだのでメモ．タイトルからわかるようにspectral clusteringを基本の部分から解説した資料．構成としてはsimilarity graphs $\rightarrow$ graph laplacians $\rightarrow$ spectral clustering $\rightarrow$ アルゴリズムの解析という感じ．とりあえずここではspectral clusteringの手前のグラフ理論的な話まで．

Similarity graphs

データ点 $x_1,\dots,x_n$ が与えられた時，データ点のペア $x_i,x_j$ の類似度を $s_{ij}\geq 0$ とする．ここで，データ間の類似度よりも多くの情報を持っていないとすれば，データを表現する良い方法はsimilarity graph $G=(V,E)$ を作ること．各頂点 $v_i$ はデータ点 $_i$ に対応し，二つのデータ点間の類似度 $s_{ij}$ が正またはある閾値より大きいとすれば，グラフのエッジは $s_{ij}$ によって重み付けられる．このようにグラフのエッジがデータ間の類似度に基づくものをsimilarity graphという．このsimilarity graphを用いてクラスタリングの問題を考えれば，エッジの重みが大きいデータ同士は同じクラスタに所属し，エッジの重みが小さいデータ同士は異なるクラスタに所属するということが直感的に言える．この考えを定式化するために，まずは基本的なグラフの概念を導入する．

graph notation

まず $G=(V,E)$ を無向グラフとして定義する．ただし，二つの頂点 $v_i,v_j$ を結ぶ各エッジは非負の重み $w_{ij}$ を持つ，重み付きのグラフとなっている．グラフの重み付き隣接行列(adjacency matrix)を $W=(w_{ij})_{i,j=1,\dots,n}$ と定義し， $w_{ij}=0$ ならば $v_i,v_j$ を結ぶエッジが存在しないことを意味する．また， $G$ が無向グラフであることから $w_{ij}=w_{ji}$ が成り立つ．頂点 $v_i\in V$ の度数(degree)を次のように定義する．

$\displaystyle d_i=\sum_{j=1}^nw_{ij}$

度数 $d_1,\dots,d_n$ を対角成分に持つ対角行列を度数行列(degree matrix)を $D$ と定義する．また，頂点の部分集合 $A\subset V$ が与えられた時，その補集合を $A$ を用いて $V\setminus A$ として記述する．さらに $v_i\in A$ を満たすかどうかを示す指示ベクトル(indicator vector)を $\mathbb{1}_A=(f_1,\dots,f_n)'\in\mathbb{R}^n$ で定義し， $v_i\in A$ が真ならば $f_i=1$ ，それ以外なら $f_i=0$ となる．指示ベクトルは式を見ればわかるように，部分集合に含まれる頂点の個数分だけ成分に1を持つベクトルになっている．

ここで部分集合 $A\subset V$ の大きさを測る以下の二つの方法について考える．

$\displaystyle |A|:=\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{vertices}\:\mathrm{in}\:A \\ \displaystyle \mathrm{vol}(A):=\sum_{i\in A}d_i$

$|A|$ は頂点の数により定義され， $\mathrm{vol}(A)$ は $A$ に含まれる頂点から伸びる全てのエッジの重みの和によって定義される． $A$ に含まれる二つの頂点がpathを持ち(どこか他のノードを介してでも繋がっている状態)，間にある全ての頂点が $A$ に含まれている場合， $A$ はconnectedであるといい， $A$ がconnectedかつ， $A$ と $\bar{A}$ の頂点同士がpathをもたない(connectedでない)場合， $A$ をconnected componentと呼ぶ．

Different similarity graphs

Similarity graphを構成することのゴールはデータ間の局所的な隣接関係をモデル化することで，その方法にはいくつか代表的な方法がある．

The $\epsilon$ -neighborhood graph

これは距離がある閾値 $\epsilon$ より小さいデータのペア全てにエッジを張る方法．この方法は接続されたデータ間の距離のスケールが大体同じ(ほぼ $\epsilon$ )になり，重みをつけたところでグラフの持つ情報はほとんど増えないため(ここの理由がよくわからない)重みのないグラフとして構成するのが一般的．

$k$ -nearest neighbor graphs

ここのゴールは頂点 $v_j$ が $v_i$ の $k$ 近傍に含まれるときに二つの頂点を接続すること．ただし，この定義だと近傍の関係性が非対称であることから有向グラフを構成する場合がある．そこで $k$ 近傍によって作られるグラフを無向グラフにする二つの方法を紹介する．一つは単純にエッジの向きを無視する方法，すなわちどちらか一方の頂点がもう一方の頂点の $k$ 近傍であればエッジを張る方法で，これは $k$ -nearest neighbor graphと呼ばれる．もう一つは双方向からエッジが張られる場合のみエッジを張る，すなわちどちらの頂点も相手の $k$ 近傍に含まれる時のみエッジを張る方法で，これはmutual $k$ -nearest neighbor graphと呼ばれる．どちらの場合でグラフを作った場合でも，endpointの類似性からエッジの重み付けを行う．

The fully connected graph

これは，単純に正の類似度を持つ全てのデータのペアにエッジを張る方法でエッジの重みは $s_{ij}$ になる．グラフは局所的な隣接関係を表現すべきであるため，この構成方法は類似度関数そのものが局所的な隣接関係を捉えているような場合のみ有効に働く．類似度関数の例としてはGaussian similarity function $s(x_i,x_j)=\exp(-||x_i-x_j||^2/(2\sigma^2)$ などがあげられ，この場合 $\sigma$ がどれくらい離れた頂点を見るか調節する．これは丁度 $\epsilon$ -neighborhood graphの $\epsilon$ と似た働きをする．

上記3つの構成方法は全てspectral clusteringで一般的に用いられる．どの構成方法を使えばより良い結果が得られるかという理論的な回答は(このtutorialが執筆された時点では)ないらしい．

Graph laplacians and their basic properties

Spectral clusteringにおいて重要となってくるのはgraph Laplacian matricesで，spectral graph theoryとして古くから研究されているよう．graph convolutional networksなどでもお馴染み．"graph Laplacian"という呼称はいろんなところで使われていて文献によってgraph Laplacianの定義が違うので他の文献を読むときには注意とのこと．

以下， $G$ を無向グラフ， $W$ をグラフの重み行列として扱い， $w_{ij}=w_{ji}\geq 0$ を満たす．また，ここでは固有ベクトルを使うときは正規化されている仮定は置かず，固有ベクトルは値が小さい順に並んでいるものとする．

The unnormalized graph Laplacian

正規化されていないgraph Laplacian matrixを以下のように，度数行列と重み行列の差として定義する．

$\displaystyle L=D-W$

ここではspectral clusteringで必要とされる命題を以下にまとめる．

Proposition 1 (properties of $L$ )

全てのベクトル $f\in\mathbb{R}^n$ に対し次の関係が成り立つ． $\displaystyle f'Lf=\frac{1}{2}\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2$
$L$ は半正定値対称行列
$L$ の最小固有値は0であり，対応する固有ベクトルは $\mathbb{1}$ (成分が全て1のベクトル)となる．
$L$ は $n$ 個の非負の実数固有値を持つ． $0=\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n$

証明

$d_i$ の定義より， $\displaystyle \:\\ \displaystyle f'Lf=f'Df-f'Wf=\sum_{I=1}^nd_if_i^2-\sum_{i,j=1}^nf_if_jw_{ij} \\ \displaystyle =\frac{1}{2}\left(\sum_{i=1}^nd_if_i^2-2\sum_{i,j}^nf_if_jw_{ij}+\sum_{j=1}^nd_jf_j^2\right)=\frac{1}{2}\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2 \\$ 　　　　　　 1行目は $L=D-W$ の関係性と $D$ が対角行列であることから導かれる．また，2行目は $f_i^2$ の項を無理やり二つに分けることで因数分解可能な形にし， $d_i=\sum_jw_{ij}$ を利用して最終的な形を導いた．
$L$ が対称行列であることは $D,W$ が対称行列であることから言える．また全ての $f\in\mathbb{R}^n$ に対して $f'Lf\geq 0$ であることから固有値が0以上，すなわち半正定値であることが言える．
$D$ の $i$ 番目の対角成分は $d_i=\sum_{j=1}^nw_{ij}$ で与えられることから， $L=D-W$ の関係性より $L\mathbb{1}=0$ となる．よって固有値と固有ベクトルの関係性から $L\mathbb{1}=\lambda\mathbb{1}=0\mathbb{1}$ が得られ，固有値0に対応する固有ベクトルは $\mathbb{1}$ であることがわかる．
自明．

また，以下の命題はspectral clusteringを考える上で重要な命題．

Proposition 2 (Number of connected components and the spectrum of $L$ )

$G$ を非負の値で重み付けられた無向グラフとする． $L$ の値0の固有値の数 $k$ はグラフのconnected components $A_1,\dots,A_k$ の数と等しい．また，値0の固有値が張る固有空間は各connected componentsの指示ベクトル $\mathbb{1}_{A_1},\dots,\mathbb{1}_{A_k}$ によって張られる．

証明

$k=1$ の場合について考える． $f$ を値が0の固有値に対応する固有ベクトルとする．すると固有値と固有ベクトルの関係と命題1の1から以下が成り立つ．

$\displaystyle 0=f'Lf=\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2$

$w_{ij}$ は非負であることから全ての項が0の時に成り立つ．つまり，二つの頂点 $v_i,v_j$ が結ばれている時(つまり $w_{ij}\gt 0$ の時)， $f_i=f_j$ が成り立つ必要がある．つまり接続関係にある全ての頂点に対して $f$ は一定である必要がある．グラフがただ一つのconnected componentで構成されている場合，固有値0に対応する固有ベクトルは $\mathbb{1}$ のみを持ち，これはconnected componentの指示ベクトルになっていることがわかる．

次に $k$ が2以上の時について考える．この時，一般性を失うことなく頂点を，所属するconnected componentの順に並べることができる．すると，各頂点は異なるconnected componentに含まれる頂点とは接続を持たないためadjacency matrix $W$ はブロック対角行列になる．よって $L=D-W$ の関係から $L$ も同様にブロック対角行列になる．すなわち $i$ 番目のconnected componentに関数graph Laplacian matrix $L_i$ を対角成分に持つ行列として表現できる． $k=1$ の場合の議論を考えれば各graph Laplacian matrix $L_i$ の0固有値に対応する固有ベクトルはその集合の指示ベクトルになるため， $L$ の0固有値に対応する固有ベクトルは各connected componentの指示ベクトルになることが言える．よって0固有値の個数とconnected componentの数は等しいことが言える．

The normalized graph Laplacians

先ほどまでは正規化されていないgraph Laplacianを扱ってきた．今度は正規化されたgraph Laplacianを考える．正規化されたgraph Laplacianには以下の2種類の表現方法がある．

$\displaystyle L_{sym}:=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-1/2} \\ \displaystyle L_{rw}:=D^{-1}L=I-D^{-1}W$

$L_{sym}$ は対称行列になっていて， $L_{rw}$ はrandom walkと密接な関係がある．以下に $L_{sym},L_{rw}$ に関する命題を示す．

Proposition 3 (Properties of $L_{sym}$ and $L_{rw}$ )

全ての $f\in\mathbb{R}^n$ において以下が成り立つ．

$\displaystyle f'L_{sym}f=\frac{1}{2}\sum_{i,j=1}^nw_{ij}\left(\frac{f_i}{\sqrt{d_i}}-\frac{f_j}{\sqrt{d_j}}\right)^2$

2. $\lambda$ が固有ベクトル $w=D^{1/2}u$ に対応する $L_{sym}$ の固有値であるとき， $\lambda$ は固有ベクトル $u$ に対応する $L_{rw}$ の固有値になる．

3. $\lambda$ と $u$ が一般化固有値問題 $Lu=\lambda Du$ の解ならば， $\lambda$ は固有ベクトル $u$ に対応する $L_{rw}$ の固有値になる．

4.0固有値に対応する $L_{rw}$ の固有ベクトルは $\mathbb{1}$ ．また，0固有値に対応する $L_{sym}$ の固有ベクトルは $D^{1/2}\mathbb{1}$

5. $L_{sym},L_{rw}$ は共に半正定値で $n$ 個の非負な実数固有値 $0=\lambda_1\leq\dots\leq\lambda_n$ を持つ．

証明

基本的には命題1の1と同様の方針で， $L_{sym}=I-D^{-1/2}WD^{-1/2}$ を代入して解ける．計算式は省略．
$\displaystyle L_{sym}w=D^{-1/2}LD^{-1/2}w=\lambda w \\ \displaystyle D^{-1}LD^{-1/2}w=\lambda D^{-1/2}w \\ \displaystyle L_{rw}D^{-1/2}w=\lambda D^{-1/2}w \\ \displaystyle L_{rw}u=\lambda u$
$\displaystyle L_{rw}u=D^{-1}Lu=\lambda u \\ \displaystyle Lu = \lambda Du$
3から $L\mathbb{1}=0D\mathbb{1}$ となり， $D^{-1}L\mathbb{1}=L_{rw}\mathbb{1}=0\mathbb{1}$ が得られる．また，2より $L_{sym}$ の固有ベクトルは $D^{1/2}\mathbb{1}$
$L_{sym}$ に関しては命題1の2と同様1の右辺が正であることから言える． $L_{rw}$ に関しては2の $L_{sym}$ との関係性から言える．

また，以下の命題により，正規化されたgraph Laplacianの0固有値の個数はconnected componentの数と関係があることが言える．

Proposition 4 (Number of connected components and spectra of $L_{sym}$ and $L_{rw}$

$L_{rw}$ と $L_{sym}$ の0固有値の個数 $k$ はグラフのconnected componentの数と等しい． $L_{rw}$ の固有空間は指示ベクトル $\mathbf{1}_{A_i}$ によって張られ， $L_{sym}$ は $D^{1/2}\mathbb{1}_{A_i}$ によって固有空間が張られる．

証明

命題3の内容を使って命題2と同様の手順により導けるので割愛．

まとめ

Graph Laplacianとかは流行りの？graph convolution等との関係も深く他にもいろんな場面で見る気がするのでそれなりに勉強できてよかった．

最近生成モデルを中心に勉強してたから久しぶりに線形代数に触れられて楽しい．

機械学習とかコンピュータビジョンとか

CVやMLに関する勉強のメモ書き。

A Tutorial on Spectral Clusteringを読んだのでメモその１

はじめに

Similarity graphs

graph notation