ラプラシアン行列
グラフ理論の数学的分野において、ラプラシアン行列(ラプラシアンぎょうれつ、Laplacian matrix)は、グラフの行列表示(行列表現)である。アドミタンス行列(admittance matrix)、キルヒホッフ行列(Kirchhoff matrix)、離散ラプラシアン(discrete Laplacian)、またはラプラス行列と呼ばれることもある。ラプラシアン行列はグラフの多くの有用な性質を探るために使うことができる。キルヒホッフの定理と一緒に、任意のグラフについての全域木の数を計算するために使うことができる。グラフの最疎カットはチーガー定数 (グラフ理論)によってそのラプラシアンの2番目に小さい固有値を使って近似することができる 。また、非線形次元削減を構築するためにも使うことができる。これは、様々な機械学習応用のために有用かもしれない。
n個の頂点を持つ単純グラフを考えると、そのラプラシアン行列L_{n \times n}は以下の式で定義される。
L = D - A
上式において、Dはグラフの次数行列、Aは隣接行列である。Gは単純グラフであるため、Aの成分は1または0のみであり、その対角要素は全て0である。
有向グラフの場合は、入次数または出次数のいずれかが、応用に依存して使われるだろう。
Lの要素は式
L_{i,j} := \begin{cases}
\deg(v_i) & \mbox{if}\ i = j \\
-1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise}
\end{cases}
によって与えられる。上式において、\operatorname{deg}(v_i)は頂点iの次数である。
L^\text{sym} := D^{-\frac{1}{2} L D^{-\frac{1}{2} = I - D^{-\frac{1}{2} A D^{-\frac{1}{2},
として定義される。
L^\text{sym}の要素は
L^\text{sym}_{i,j} := \begin{cases}
1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
-\frac{1}{\sqrt{\deg(v_i)\deg(v_j)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise}.
\end{cases}
によって与えられる。
L^\text{rw} := D^{-1}L = I - D^{-1}A
として定義される。
L^\text{rw}の要素は
L^\text{rw}_{i,j} := \begin{cases}
1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
-\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise}.
\end{cases}
によって与えられる。
一般化ラプラシアンQは
\begin{cases}
Q_{i,j} < 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j\\
Q_{i,j} = 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is not adjacent to } v_j \\
\mbox{any number} & \mbox{otherwise}.
\end{cases}
として定義される。
普通のラプラシアンは一般化ラプラシアンであることが分かる。
以下はラベル付けされた無向グラフとそのラプラシアン行列の単純な例である。
(無向)グラフGと固有値\lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}を持つそのラプラシアン行列Lについて:
Lは対称である。
Lは半正定値である(すなわち全てのiについて\lambda_i \ge 0)。これは接続行列の節で検証される。これは、ラプラシアンが対称であり、優対角行列であるという事実からも見ることができる。
LはM-行列である(その非対角成分は非正であり、そのうえその固有値の実部は非負である)。
Lの全ての行の和と列の和はゼロである。実際、和の計算において、頂点の次数には隣接する頂点ごとに「−1」が足される。
その結果、\lambda_0 = 0となる。これは、ベクトル\mathbf{v}_0 = (1, 1, \dots, 1)がL \mathbf{v}_0 = \mathbf{0} を満たすためである。これは、ラプラシアン行列が特異行列であることも暗示する。
グラフ中の成分 (グラフ理論)の数はラプラシアンの零空間の次元であり、0固有値の固有値と固有ベクトルである。
Lの最小の非ゼロ固有値はスペクトルギャップと呼ばれる。
Lの2番目に小さな固有値(ゼロかもしれない)はGの代数的連結度(Fiedler値)であり、グラフの最疎カットを近似する。
ラプラシアンは、関数f : V \to \mathbb{R}(VはGの頂点セット、n = |V|)のn次元ベクトル空間上の作用素である。
Gがk正則である時、正規化ラプラシアンは\mathcal{L} = \tfrac{1}{k} L = I - \tfrac{1}{k} Aである(Aは隣接行列、Iは単位行列)。
複数の連結成分を持つグラフについて、Lは区分対角行列であり、それぞれの区分はそれぞれの成分についての(場合によると頂点を順序付けし直した後の)各ラプラシアン行列である(すなわちLは区分対角行列と置換相似である)。
ラプラシアン行列Lの跡(トレース)は2m(mは考慮されているグラフの辺の数)と等しい。
M_{ev} = \left\{\begin{array}{rl}
1, & \text{if } v = i\\
-1, & \text{if } v = j\\
0, & \text{otherwise}.
\end{array}\right.
によって与えられる辺e(頂点iとjを連結している; i > j)と頂点vについて要素Mevを持つ|e| \times |v|有向接続行列Mを定義する。
次に、ラプラシアン行列Lは
L = M^\textsf{T} M\,,
を満たす(M^\textsf{T}はMの転置行列)。
ここで、単位ノルム固有値ベクトル\mathbf{v}_iおよび対応する固有値\lambda_iを使ったLの固有値分解を考える。
\begin{align}
\lambda_i & = \mathbf{v}_i^\textsf{T} L \mathbf{v}_i \\
& = \mathbf{v}_i^\textsf{T} M^\textsf{T} M \mathbf{v}_i \\
& = \left(M \mathbf{v}_i\right)^\textsf{T} \left(M \mathbf{v}_i\right) \\
\end{align}
\lambda_iはベクトルM \mathbf{v}_iとそれ自身の内積として書くことができるため、これは\lambda_i \ge 0であり、したがってLの固有値は全て非負であることを示す。
変形ラプラシアン(deformed laplacian)は通常以下のように定義される。
\Delta(s) = I - sA + s^2(D - I)
上式において、Iは単位行列、Aは隣接行列、Dは次数行列、sは(複素)数である。ここで留意すべきは、標準的なラプラシアンは単に\Delta(1)となることである。
(対称)正規化ラプラシアンは以下のように定義される。
L^\text{sym} := D^{-\frac{1}{2} L D^{-\frac{1}{2} = I - D^{-\frac{1}{2}AD^{-\frac{1}{2}
上式において、Lは(非正規化)ラプラシアン、Aは隣接行列、Dは次数行列である。次数行列Dは対角行列で正であるため、その逆数平方根D^{-\frac{1}{2}は単にその対角成分がDの対角成分の正の平方根の逆数である対角行列となる。対称正規化ラプラシアンは対称行列である。
L^\text{sym} = S S^*が存在する。Sは、列が頂点によって添え字を付けられ、行がGの辺によって添え字が付けられた行列である。これらは、辺e = {u, v} に対応するそれぞれの行がuに対応する列において成分\frac{1}{\sqrt{d_u}を、vに対応する列において成分-\frac{1}{\sqrt{d_v}を、それ以外では0成分を持つことになるように索引付けされる(注: S^*はSの転置行列を示す)。
正規化ラプラシアンの全ての固有値は実数かつ非負である。これは以下のように見ることができる。L^\text{sym}は対称であるため、その固有値は実数である。これらの固有値は全て非負である。固有値λを持つL^\text{sym}の固有ベクトル gを考え、g = D^\frac{1}{2} fを仮定する(gおよびfを頂点v上の実関数と見なすことができる)。すると、
\lambda \ = \
\frac{\langle g, L^\text{sym}g\rangle}{\langle g, g\rangle} \ = \
\frac{\left\langle g, D^{-\frac{1}{2} L D^{-\frac{1}{2} g\right\rangle}{\langle g, g\rangle} \ = \
\frac{\langle f, Lf\rangle}{\left\langle D^\frac{1}{2} f, D^\frac{1}{2} f\right\rangle} \  = \
\frac{\sum_{u \sim v}(f(u) - f(v))^2}{\sum_v f(v)^2 d_v} \ \geq \
0,
となる。ここでは内積\langle f,g\rangle = \sum_{v} f(v)g(v)(全ての頂点vにわたる和)を用い、\sum_{u\sim v}は隣接頂点 {u,v} の全ての非順序対にわたる和を示す。量\sum_{u,v}(f(u) - f(v))^2はfの「ディリクレ和」と呼ばれるが、式\frac{\left\langle g, L^\text{sym}g\right\rangle}{\langle g, g\rangle} はgのレイリー商と呼ばれる。
1をそれぞれの頂点上に値1を想定する関数とする。すると、D^\frac{1}{2} 1は固有値0を持つL^{\text{sym}の固有関数である。
実際、正規化対称ラプラシアンの固有値は0 = μ0 ≤ … ≤ μn−1 ≤ 2を満たす。これらの固有値(正規化ラプラシアンのスペクトルと呼ばれる)は、一般グラフに対するその他のグラフ不変量とよく関連する。
酔歩(random walk)正規化ラプラシアンは
L^\text{rw} := D^{-1} L
として定義される。Dは次数行列である。次数行列D対角行列であるため、その逆行列D^{-1}は単純に対角行列として定義され、これはDの対応する正の対角成分の逆数である対角成分を持つ。
孤立した頂点(次数が0)について、一般的な選択は対応する要素L^\text{rw}_{i,i}を0にすることでる。
この慣習によって、固有値0の多重度がグラフの連結した構成要素の数と等しくなるという良い性質がもたらされる。
L^\text{rw}の行列要素は以下の式で与えられる。
L^{\text{rw}_{i,j} := \begin{cases}
1 & \mbox{if}\ i = j\ \mbox{and}\ \deg(v_i) \neq 0\\
-\frac{1}{\deg(v_i)} & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise}
\end{cases}
酔歩正規化ラプラシアンの名称は、この行列がL^\text{rw} = I - P(P = D^{-1}Aは単純にグラフ上の酔歩者〈ランダムウォーカー〉の遷移行列)という事実から来ている。例えば、 e_i がi番目の標準基底ベクトルを示すものとする。すると、x = e_i P は頂点iから一歩進んだ後の酔歩者の位置の分布を示す確率ベクトルである; すなわち、 x_j = \mathbb{P}\left(v_i \to v_j\right)。より一般的には、もしベクトル x がグラフの頂点上の酔歩者の位置の確率分布であるとすれば、x' = x P^tはt歩後の酔歩者の確率分布である。
L^\text{rw} = I-D^{-\frac{1}{2}\left(I - L^\text{sym}\right) D^\frac{1}{2}
となることを確認することができる。
すなわち、L^\text{rw}は正規化ラプラシアンL^\text{sym}と類似している。この理由のため、L^\text{rw}がたとえ一般にエルミート行列でないとしても、実固有値を持つ。実際、その固有値は(エルミート行列である)L^\text{sym}のものと一致する。
グラフ上の酔歩に関する余談として、単純無向グラフを考える。酔歩者が時間tに頂点iにいる確率を考え、酔歩者が時間t-1に頂点jにいた確率分布を仮定する(任意の頂点に結合したいかなる辺に沿った一歩について一様の見込みを仮定する):
p_i(t) = \sum_j \frac{A_{ij}{\deg\left(v_j\right)} p_j(t - 1),
または行列-ベクトル記法で:
p(t) = A D^{-1} p(t - 1).
(t\rightarrow \inftyとして設定される平衡はp = A D^{-1} p として定義される。)
D^{-\frac{1}{2} p(t) = \left[D^{-\frac{1}{2} A D^{-\frac{1}{2}\right] D^{-\frac{1}{2} p(t - 1)
と書き直すことができる。
A_\text{reduced} \equiv D^{-\frac{1}{2} A D^{-\frac{1}{2}は簡約隣接行列と呼ばれる対称行列である。したがって、この酔歩者の一歩はA_\text{reduced}の累乗を必要とする。A_\text{reduced}は対称行列であるため、これは単純な操作である。
ラプラシアン行列は、離散ラプラス演算子の特定の事例の行列表現として解釈することができる。このような解釈によって、例えば、ラプラシアン行列を無限の数の頂点と辺を持つグラフ(無限サイズのラプラシアン行列となる)の場合に一般化することが可能となる。
\phiがグラフにわたる熱分布を記述すると想定する(\phi_iは頂点iにおける熱である)。ニュートンの冷却の法則に従えば、節iと節jの間を移る熱は、もし節iと節jが連結されているならば、\phi_i - \phi_jに比例する(節が連結されていないならば、熱は移らない)。
すると、熱用量kについて、
\begin{align}
\frac{d \phi_i}{d t}
&= -k \sum_j A_{ij} \left( \phi_i - \phi_j \right) \\
&= -k \left( \phi_i \sum_j A_{ij} - \sum_j A_{ij} \phi_j \right) \\
&= -k \left( \phi_i \ \deg(v_i) - \sum_j A_{ij} \phi_j \right) \\
&= -k \sum_j \left( \delta_{ij} \ \deg(v_i) - A_{ij} \right) \phi_j \\
&= -k \sum_j \left( \ell_{ij} \right) \phi_j.
\end{align}
行列-ベクトル記法では、
\begin{align}
\frac{d\phi}{dt} &= -k(D - A)\phi \\
&= -kL \phi
\end{align}
これから、
\frac{d \phi}{d t} + kL\phi = 0
が得られる。
この方程式が、行列 −Lがラプラス演算子\nabla^2を置き換えている熱方程式と同じ形式であることに気付く。ゆえに、Lは「グラフラプラシアン」と呼ばれる。
この微分方程式の解を探すため、1階の行列微分方程式を解くための標準的な技法を適用する。すなわち、Lの固有ベクトル\mathbf{v}_i(L\mathbf{v}_i = \lambda_i \mathbf{v}_i)の線形結合として\phiを書く。時間に依存する\phi = \sum_i c_i \mathbf{v}_i。
元の式に代入する(ここで留意すべきは、Lが対称行列であるためにその単位ノルム固有ベクトル\mathbf{v}_iは直交であるという事実を用いる点である):
\begin{align}
\frac{d\left(\sum_i c_i \mathbf{v}_i\right)}{dt} + kL\left(\sum_i c_i \mathbf{v}_i\right) &= 0 \\
\sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i L \mathbf{v}_i\right] &= \\
\sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i \lambda_i \mathbf{v}_i\right] &= \\
\frac{dc_i}{dt} + k \lambda_i c_i &= 0\\
\end{align}
c_i(t) = c_i(0) e^{-k \lambda_i t}
である。
前掲のように、Lの固有値\lambda_iは非負であり、これは微分方程式の解が(指数関数的に減衰するか一定に留まるかのいずれかのみであるため)平衡に近づくことを示している。これは、\lambda_iと初期条件c_i(0)が与えられれば、いかなる時点における解も見つけることができることも示している。全体の初期条件\phi(0)の観点からそれぞれのiに対するc_i(0)を探すためには、単純に\phi(0)を単位ノルム固有ベクトル\mathbf{v}_iへと射影する。
c_i(0) = \left\langle \phi(0), \mathbf{v}_i \right\rangle
無向グラフの場合は、Lが対称行列であるためこれはうまくいき、スペクトル定理によって、その固有ベクトルは全て直交する。そのため、Lの固有ベクトルに対する射影は単純に、指数関数的に減衰し、互いに独立な一連の座標への初期条件の直交座標変換である。
\lim_{t \to \infty}\phi(t)を理解するためには、残る項 c_i(t) = c_i(0) e^{-k \lambda_i t}は\lambda_i = 0のもののみであることに留意すべきである。これは
\lim_{t\to\infty} e^{-k \lambda_i t} = \left\{\begin{array}{rlr}
0 & \text{if} & \lambda_i > 0 \\
1 & \text{if} & \lambda_i = 0
\end{array}\right\}
となるためである。
言い換えると、系の平衡状態はLの核によって完全に決定される。
なぜなら定義\sum_{j}L_{ij} = 0によれば、全てが1のベクトル\mathbf{v}^1は核内にある。また、グラフ中にk個の互いに素な連結成分が存在するならば、この全てが1のベクトルは1と0からなるk個の独立な\lambda = 0固有ベクトルの和へと分割できる。それぞれの連結成分は連結成分中の要素では1を持つ固有ベクトルと、その他の場所では0を持つ固有ベクトルと対応している。
この結果は、N個の頂点を持つグラフについて任意の初期条件c(0)では、
\lim_{t\to\infty}\phi(t) = \left\langle c(0), \mathbf{v^1} \right\rangle \mathbf{v^1}
となる。上式において、
\mathbf{v^1} = \frac{1}{\sqrt{N} [1, 1, ..., 1]
である。
\phiの個々の要素\phi_j、すなわちグラフ中の個々の頂点jについて、これを
\lim_{t\to\infty}\phi_j(t) = \frac{1}{N} \sum_{i = 1}^N c_i(0)
と書き直すことができる。
言い換えると、定常状態では、\phiの値はグラフの個々の頂点において同じ値に収束する。この値は全ての頂点の初期値の平均である。これは熱拡散方程式の解であるため、直感的に完全に筋が通っている。グラフ中で隣接する要素は、エネルギーが互いに連結した全ての要素にわたって均等に広がるまでエネルギーを交換することが予測される。
本節では、グラフにわたって経時的に拡散する関数\phiの例を示す。この例中のグラフは2次元離散グリッド上に構築され、グリッド上の点は8個の隣接点と連結している。3つの初期点は正の値を持つと指定されているのに対し、グリッド中の残りの値は0である。経時的に、指数関数的減衰によってグリッド全体へとこれらの点上の値が均等に分布する。
このアニメーションを生成するために使われた完全なMATLABのソースコードを以下に示す。ソースコードは、初期条件の指定、これらの初期条件のラプラシアン行列の固有値への射影、これらの射影された初期条件の指数関数的減衰のシミュレーションの過程を示す。
グラフラプラシアン行列は、有限差分法によって得られた(半正定値)ラプラシアン作用素に対する近似の行列形式としてさらに見ることができる。この解釈では、グラフの全ての頂点はグリッド点として扱われる; 頂点の局所連結性はグリッド点における有限差分近似ステンシル (数値解析)を決定し、グリッドのサイズは常に全ての辺について1であり、いかなるグリッド点上にも制約はない。これは斉次なノイマン境界条件、すなわち自由境界の場合に相当する。
ラプラシアン行列の類似物は、有向多重グラフに対しても定義することができる。この場合、ラプラシアン行列Lは
L = D - A
と定義される。上式においてDは頂点iの出次数と等しいDi,iを持つ対角行列、Aはiからjへの辺の数(ループを含む)と等しいAi,jを持つ行列である。