FANCOMI Ad-Tech Blog

株式会社ファンコミュニケーションズ nend・新規事業のエンジニア・技術ブログ

ラプラシアンの中に１人以上、ゼロ固有値がいる！

nend データ分析 ベクトル 行列 k_oomori

Introduction

　こんにちは、k_oomoriです。前回は、非負値行列因子分解という手法によって実際の広告配信結果から関連性があると思われる広告キャンペーンのペアたちを抽出する方法を紹介しました。しかし、そこに現れるキャンペーンは全てが互いに関連し合っているわけではありません。おそらくはいくつかの離散的な“島”(連結成分)に分かれて存在しています(アイドル系の島、ソシャゲ系の島など)。そこで今回はキャンペーンの集合がいくつの島に分かれるのかを機械的に調べる方法について見ていきます。これにより、行列の固有値問題という純数学的・抽象的な概念も使い方によっては実際のビジネスシーンにおいて有用な情報を提供しうるということを示したいと思います。

　なお、この記事をPDFで読みたい方はこちらからどうぞ。

隣接行列

　前回のエントリでキャンペーン間の関連性を調べることができたので、まずはこれを隣接行列(adjacency matrix)という形にまとめます。簡単な例として、5つのキャンペーン(以下ではグラフ理論(graph theory)の用語を用いてノード(node)と呼びます)の間に図1に示したような関連性がある場合を考えると、隣接行列は以下のようになります。

 A=\left(\begin{array}{ccccc}0&1&0&0&0\\1&0&1&0&0\\0&1&0&1&1\\0&0&1&0&1\\0&0&1&1&0\end{array}\right) \tag{1}

つまり、1と2を結ぶ(1,2)成分と(2,1)成分、2と3を結ぶ(2,3)成分と(3,2)成分、3と4と5の間を結ぶ(3,4)成分,(4,3)成分,(3,5)成分,(5,3)成分,(4,5)成分,(5,4)成分の値を1に、その他の値を全て0にします。ここで注意として、現在はリンクに方向がない無向グラフを考えているので、隣接行列は常に対称行列( A_{ij}=A_{ji})になります。また自分自身とのリンクも考えないため、対角成分は全て0になります。

f:id:fancs:20160502154254p:plain
図1：キャンペーン間の関連性の例：互いに関連のあるもの同士がリンク（枝線）で結ばれている

　次に、 i番目のノードの次数 ( iから出ているリンクの本数)を (i,i)成分とする対角行列 Dを考えます。上の例では

 D=\left(\begin{array}{ccccc}1&0&0&0&0\\0&2&0&0&0\\0&0&3&0&0\\0&0&0&2&0\\0&0&0&0&2\end{array}\right) \tag{2}

となります。別の書き方をすると

 
\begin{eqnarray}
D_{ii}&=&\sum_{k=1}^NA_{ik} \qquad (i=1,\ldots,N\mbox{; $N$は全ノード数}) \tag{3}\\ 
D_{ij}&=&0 \qquad\qquad\;\ (i\neq j)
\end{eqnarray}

ラプラシアンとゼロ固有値

　いよいよ表題にあるラプラシアン(Laplacian) Lを以下で定義します。 L\equiv D-A\tag{4} 図1の例に当てはめると

 L=\left(\begin{array}{rrrrr}1&-1&0&0&0\\-1&2&-1&0&0\\0&-1&3&-1&-1\\0&0&-1&2&-1\\0&0&-1&-1&2\end{array}\right)\tag{5}

これをよく見ると（というか実はLの定義式から自明なのですが）、Lの各行に注目し、要素を横に全部足していくと0になります。

 \begin{eqnarray}1+(-1)+0+0+0&=&0\\(-1)+2+(-1)+0+0&=&0\\0+(-1)+3+(-1)+(-1)&=&0\tag{6}\\0+0+(-1)+2+(-1)&=&0\\0+0+(-1)+(-1)+2&=&0\end{eqnarray}

これは取りも直さず、 \vec{v}=(1\ 1\ 1\ 1\ 1)^T （ {}^Tは転置(transpose)の意）が Lの固有値0に属する固有ベクトルになっているということを意味しています(固有値、固有ベクトルの定義についてはAppendix Aをご参照ください)：

 
\begin{eqnarray}
L\vec{v}&=&\left(\begin{array}{rrrrr}1&-1&0&0&0\\-1&2&-1&0&0\\0&-1&3&-1&-1\\0&0&-1&2&-1\\0&0&-1&-1&2\end{array}\right)
\left(\begin{array}{c}1\\1\\1\\1\\1\end{array}\right)\\
&=&\left(\begin{array}{rrrrrrrrr}1\times 1&+&(-1)\times 1&+&0\times 1&+&0\times 1&+&0\times 1\\(-1)\times 1&+&2\times 1&+&(-1)\times 1&+&0\times 1&+&0\times 1\\0\times 1&+&(-1)\times 1&+&3\times 1&+&(-1)\times 1&+&(-1)\times 1\\0\times 1&+&0\times 1&+&(-1)\times 1&+&2\times 1&+&(-1)\times 1\\0\times 1&+&0\times 1&+&(-1)\times 1&+&(-1)\times 1&+&2\times 1\end{array}\right)\\
&=&\left(\begin{array}{c}0\\0\\0\\0\\0\end{array}\right)=0\times \left(\begin{array}{c}1\\1\\1\\1\\1\end{array}\right)=0\times \vec{v}\tag{7}\\
\mbox{∴}& & L\vec{v}=0\cdot \vec{v}
\end{eqnarray}

ここでは図1のケースについて具体的な計算によって \vec{v}=(1\ 1\ 1\ 1\ 1)^Tが Lの固有値0に属する固有ベクトルであることを示しましたが、一般に任意の隣接行列 Aに対して(4)式によって定義されるラプラシアン Lは常に \vec{v}=(1\ 1\ \cdots\ 1\ 1)^Tを固有ベクトルに持ち、その固有値は0であることを示すことができます。

連結成分

f:id:fancs:20160502154300p:plain
図2：非連結グラフの例

　図1の例では、ノード1～5が全体として一つの島を作っていました。つまり、連結グラフ(connected graph)をなしていました。では、ノード2と3の間に関連がなく、図2のように2つの島（連結成分(connected components)と言います）に分かれていた場合、それが Lの性質にどのように反映されるか、見ていきましょう。 Lを計算すると

 L=\left(\begin{array}{rr|rrr}1&-1&0&0&0\\-1&1&0&0&0\\\hline0&0&2&-1&-1\\0&0&-1&2&-1\\0&0&-1&-1&2\end{array}\right)\tag{8}

となります。わかりやすくするよう、補助線をつけました。①②と③④⑤が Lの中で完全に分離していることが見て取れます。(8)式より、 \vec{v}_1=(1\ 1\ 0\ 0\ 0)^Tと \vec{v}_2=(0\ 0\ 1\ 1\ 1)^Tはともに Lの固有値0に属する互いに線形独立な固有ベクトルであることがわかります。 (先ほど出てきた \vec{v}=(1\ 1\ 1\ 1\ 1)^Tは \vec{v}_1と \vec{v}_2の線形結合(linear combination)として書けるので独立ではなく、従ってここでは考慮する必要はありません。) つまり、(8)で与えられる Lはゼロ固有値を2つ持っていることがわかります。実際、特性多項式(characteristic polynomial)を計算しても


\begin{eqnarray}
\det(L-xI) &=& \det\left(\begin{array}{cc}1-x & -1\\-1 & 1-x\end{array}\right)\cdot \det\left(\begin{array}{ccc}2-x & -1 & -1\\-1 & 2-x & -1\\-1 & -1 & 2-x\end{array}\right)\\
&=& -x^2(x-2)(x-3)^2\tag{9}
\end{eqnarray}

となり、 x=0が2重根になっていることがわかります。
　一般に、ラプラシアンのゼロ固有値の個数と対応するグラフの連結成分の数はぴったり一致しているということが示されます。（※この証明は少々面倒な議論が必要となるのでAppendix Bに回します。）実際、前のセクションでラプラシアンは常に \vec{v}=(1\ 1\ \cdots\ 1\ 1)^Tを固有ベクトルに持ち、その固有値が0であることを示しました。これによりどんなグラフでも連結成分の数は常に1個以上であり、0個というおかしな結論が導かれることがないことが保証されます。
　ノードの数が5個程度の場合は、図1や図2のようにグラフを書いてやればそれらが幾つの互いに無関係なグループに分かれるのかすぐにわかりますが、数が100個200個と増えてくると、いちいち全部を図示していくわけにはいきません。そのような場合でもNumPyにラプラシアンを読み込ませておいて

>>> from numpy import *   
>>> l,v = linalg.eig(L)

とやってやればlに固有値の配列が返されるので、その中にいくつゼロ固有値があるかを調べればそれだけで連結成分の数がわかるのです。やっぱり自動化は最高だぜ！
　それでは確認のため実際のデータに適用してみましょう。145個のキャンペーンが絡む解析結果からラプラシアンを構成し、固有値を調べてみると0が17個ありました。一方、隣接行列を詳細に検証してみたところ、実際に17のブロックに分かれることがわかりました！両者が一致することは理論的に証明されていたとしても、実際に泥臭い計算で合うことが示せるとより確信が持てます。

ラプラシアンの固有値の性質

　ラプラシアンの固有値の性質についてもう少し詳しく見ていきましょう。ここから先は少しadvancedな内容になりますが、結果を将来のエントリで使う可能性があるのでここで扱っておきます。
　まず、前述のように無向グラフの隣接行列は対称行列なので、そこから定義されるラプラシアンも対称行列になります。また隣接行列、ラプラシアンの定義から行列の各成分は明らかに実数（もっと言うと実整数）です。線形代数において、実対称行列の固有値は全て実数であることが知られています。このことから、ラプラシアンの固有値は全て実数であることがわかります。
　さらに、ラプラシアンの固有値は全て0か正の実数であり、決して負にはならないことが次のようにして示せます。
【証明】 n \times n行列 Mと任意の n次元ベクトル \vec{v}=(x_1\ \cdots\ x_n)^Tに対し、実二次形式(real quadratic form)を

 \displaystyle q(M; \vec{x})\equiv \vec{x}^T M\vec{x}=\sum_{i,j=1}^nM_{ij}x_ix_j\tag{10}

で定義すると、ラプラシアンに対する実二次形式は

 \begin{eqnarray}
q(L; \vec{x}) &=& \sum_{i=1}^nx_i(L\vec{x})_i = \sum_{i=1}^nx_i\sum_{j=1}^nA_{ij}(x_i-x_j)\\
&=&\frac{1}{2}\sum_{i,j}(x_iA_{ij}-x_jA_{ji})(x_i-x_j)\\
&=&\frac{1}{2}\sum_{i,j}A_{ij}(x_i-x_j)^2\ge 0\tag{11}
\end{eqnarray}

となり、決して負にはならないことがわかります（この性質を半正定値性(positive semi-definiteness)と言います）。一方、 Lのn個の固有値を \lambda_i (i=1,\ldots,n)、対応する固有ベクトルを\vec{v}_iとすると


\begin{eqnarray}
& &L(\vec{v}_1 \ \ \vec{v}_2 \ \ \cdots \ \ \vec{v}_n) = (\lambda_1\vec{v}_1 \ \ \lambda_2\vec{v}_2 \ \ \cdots \ \ \lambda_n\vec{v}_n)\\
& &=(\vec{v}_1 \ \ \vec{v}_2 \ \ \cdots \ \ \vec{v}_n)\left(
\begin{array}{cccc}
\lambda_1&0&\cdots&0\\
0&\lambda_2&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&\lambda_n
\end{array}
\right)\tag{12}
\end{eqnarray}

と書くことができます。ラプラシアンのような実対称行列の場合、n個の固有ベクトル\{\vec{v}_i\}_{i=1}^nは線形独立に取れるので、正規直交化(orthonormalize)することによってn\times n行列 P\equiv (\vec{v}_1\ \vec{v}_2\ \cdots\ \vec{v}_n)は直交行列となり、Pの逆行列は P^{-1}=P^Tによって与えられます。(12)の両辺に左から P^{-1}をかけると

 P^{-1}LP=\left(\begin{array}{cccc}\lambda_1&0&\cdots&0\\0&\lambda_2&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\lambda_n\end{array}\right)\tag{13}

となります。つまり、ある直交行列Pを用いるとP^{-1}LPが対角成分に固有値が並んだ対角行列の形に書くことができます。これを行列の対角化と言います。これを用いると、先ほどの実二次形式は

 
\begin{eqnarray}
& &q(L; \vec{x})=\vec{x}^T(PP^{-1})L(PP^{-1})\vec{x}=(P^T\vec{x})^T\cdot P^{-1}LP\cdot (P^T\vec{x})\\
& &\phantom{q(L; \vec{x})}=\vec{y}^T\left(
\begin{array}{cccc}
\lambda_1&0&\cdots&0\\
0&\lambda_2&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&\lambda_n
\end{array}
\right)\vec{y}=\sum_{i=1}^n\lambda_i y_i^2\tag{14}
\end{eqnarray}

と書けます。ここで P^T\vec{x}\equiv \vec{y}とし、P^{-1}=P^Tを使いました。式(11)と(14)から、

 \displaystyle\sum_{i=1}^n\lambda_i y_i^2 \ge 0 \tag{15}

が結論されます。任意の実数 y_iに対して(15)が成り立つためには、 \lambda_iは全て0以上でなければなりません。以上のことから、ラプラシアンの固有値は全て0以上の実数であることが示されました。

今後の展望

f:id:fancs:20160502154305p:plain 図3：2つの島が弱く結合している例

　今回は、グラフに含まれる連結成分の数がラプラシアンのゼロ固有値の数として表現されているということをお話ししました。しかし、実際には図3のようにほとんど2つに分かれているんだけれどもかろうじてつながっているというケースもありえます。このグラフについてラプラシアンを計算し、固有値を求めてみると

 
\begin{eqnarray}
\det (\lambda I-L) &=& \det \left[
\begin{array}{cccccccc}
\lambda-4 &1&1&1&0&0&0&1\\
1&\lambda -3&1&1&0&0&0&0\\
1&1&\lambda -3&1&0&0&0&0\\
1&1&1&\lambda -3&0&0&0&0\\
0&0&0&0&\lambda -3&1&1&1\\
0&0&0&0&1&\lambda -3&1&1\\
0&0&0&0&1&1&\lambda -3&1\\
1&0&0&0&1&1&1&\lambda -4
\end{array}
\right]\\
&=&-\lambda (\lambda-4)^5(\lambda^2-6\lambda+2)=0\\
\mbox{∴} \ \lambda_1=0,\quad &\lambda_2&=3-\sqrt{7}\simeq 0.3542, \quad
\lambda_3=\lambda_4=\lambda_5=\lambda_6=\lambda_7=4,\quad \lambda_8=3+\sqrt{7}\simeq 5.645
\end{eqnarray}

となります。比較のため、①と⑧のリンクを切って2連結成分に分離したものについても固有値を求めてやると

 
\lambda_1=\lambda_2=0,\quad \lambda_3=\lambda_4=\lambda_5=\lambda_6=\lambda_7=\lambda_8=4

つまりグラフが完全に2つに分かれている場合はゼロ固有値が2つになるのに対し、それらが弱く結合されている場合は0ではないが他と比べて小さな固有値(0.3542)が出現するということがわかります。これは直観にも合ってはいるのですが、定量的な判断が必要なため今回の方法では検出するのが難しいです。今後はこのようなコミュニティ検出にチャレンジしてみたいと思っています。

Summary

　I first defined adjacency matrix and Laplacian from a given graph, and showed that the Laplacian always has at least one 0-eigenvalue and the corresponding eigenvector. Then I argued that the multiplicity of 0-eigenvalues in the spectrum of the Laplacian agrees with the number of connected components of the graph concerned. In the coming blog entry I hope to tackle the community detection problem of a quantitative nature.

Appendix A: 固有値・固有ベクトルとは

　正方行列 Aに対して

 
A\vec{x}=\lambda\vec{x}\tag{16}

を満たすベクトル\vec{x}(\ne \vec{0})とスカラー \lambdaが存在するとき、 \lambdaを Aの固有値(eigenvalue)、 \vec{x}を\lambdaに属する固有ベクトル(eigenvector)と呼びます。行列がベクトルに作用した結果として得られるベクトルは一般には元のベクトルと平行になるとは限りませんが、ある特定の向きのベクトルに対してはスカラー倍されるだけで向きは変わらないという意味になります。
　またより一般に、ベクトル空間V上に作用する線形変換 Aに対して固有値・固有ベクトルの概念を定義することができます。例として、(無限次元)ベクトル空間Vとして連続関数全体の集合を、その上の線形変換として1階の微分演算子d/dxを考えたとき、

 
\displaystyle \frac{d}{dx}e^{\lambda x} = \lambda e^{\lambda x}\tag{17}

なのでe^{\lambda x}は固有値\lambdaに属するd/dxの固有ベクトル(この場合固有関数(eigenfunction)とも言う)になっています。
　物理学の分野においても量子力学のシュレーディンガー(Schrödinger)方程式が固有値問題の形をとって現れます。

 
\begin{eqnarray}
& &\hat{H}\psi(\vec{x})=E\psi(\vec{x}) \\
& &\hat{H}\equiv -\frac{\hbar^2}{2m}\vec{\nabla}^2+V(\vec{x})\tag{18}
\end{eqnarray}

Appendix B: ラプラシアンのゼロ固有値の個数とグラフの連結成分の数が等しいことの証明

　「連結成分」のセクションで後回しにした証明を行います。
【証明】ラプラシアンのゼロ固有値の数をm、グラフの連結成分の数をcと置きます。まず、(8)式のときと同様、c個のブロックに対角化された Lに対しては各ブロック上での値が全て1、その他の値が全て0というベクトル

 
\vec{v}_i=(0\ \ \cdots\ \ 0\ \ \overbrace{1\ \ 1\ \ \cdots\ \ 1\ \ 1}^{i\mbox{番目のブロック}}\ \ 0 \ \ \cdots\ \ 0)^T, \qquad (i=1,\ldots,c)\tag{19}

が線形独立な固有値0の固有ベクトルとして構成できるので、m\ge cであることはすぐにわかります。ここで、 \vec{w}が Lの固有値0の固有ベクトルであるとすると、

 
\vec{w}^TL\vec{w}=0\tag{20}

一方、(11)の導出と同様にして

 
\displaystyle\vec{w}^TL\vec{w}=\frac{1}{2}\sum_{i=1}^c\left(\sum_{j,k\in C_i}A_{jk}(w_j-w_k)^2\right)\tag{21}

ここで、隣接行列 Aは各連結成分ブロック(C_i)の上でしか0でない値を持たないということを使いました。(20)と(21)より、A_{jk}が0でない全てのノードのペア(j,k)に対してw_j=w_kでなければなりません。ところがグラフが連結であるということの意味は、連結成分内の全てのノードが何らかの経路で繋がれているということなので、任意の2つのノードj,kに対して経路 j\to p_1\to p_2\to \cdots\to p_{l}\to kが存在して A_{jp_1}=A_{p_1p_2}=\cdots =A_{p_lk}=1となります。従って結果的に w_j=w_{p_1}=\cdots =w_{p_l}=w_k\ (\forall j,k\in C_i)でなければなりません。
　以上のことより、 \vec{w}が固有値0の固有ベクトルとなるためには各連結成分上において値が全て一致していなければならないですが、他の連結成分との間には特に条件が課せられることはありません。従って、固有値0の固有ベクトル\vec{w}の一般形は(19)の \vec{v}_iを用いて

 \displaystyle\vec{w}=\sum_{i=1}^c a_i \vec{v}_i\tag{22}

と書けます。ところがこの式は、 Lの固有値0の固有ベクトル\vec{w}は必ず(19)のベクトル \{\vec{v}_i\}_{i=1}^cの線形結合として表せるということを示しているので、他に独立な固有ベクトルは存在せず、従ってc個より多くのゼロ固有値を持つことはありません。これにより、m=cであることが示されました。

References

[1] Madeleine Udell, “Introduction to Spectral Graph Theory,” http://www.stanford.edu/~udell/doc/udell11_spectralnotes.pdf
[2] Santo Fortunato, “Community detection in graphs,” Physics Reports 486, pp. 75-174 (2010).