グラフラプラシアンの解釈と接続行列

グラフラプラシアン（Graph Laplacian）がなぜラプラシアンと呼ばれるのかを、普通の関数に対するラプラシアンオペレータと比較して直観的に説明する。ついでに普通の関数のときにラプラシアンとまとめて紹介されるナブラについて、それに対応する接続行列について紹介する。

グラフラプラシアンってカタカナで書くとめちゃくちゃ読みにくいな。Graph Laplacianなら全然読めるけど両方カタカナで空白つけないのが良くない。こういうのGraphが漢字なら日本語にしたとき丁度よいのだが。

Graph Laplacianの定義

無向グラフ $G = (V, E)$ 、 $| V | = n$ に対して次の $n \times n$ 行列 $L (G)$ をGraph Laplacianといい、グラフ $G$ が何を指すか明らかなときは単に $L$ とかく。もしくは $L$ のときもある。

$L (G)_{i j} = {\begin{matrix} \deg (v_{i}) & (i = j) \\ - 1 & (i \neq j and {v_{i}, v_{j}} \in E) \\ 0 & (i \neq j and {v_{i}, v_{j}} \notin E) \end{matrix}$

$L (G)_{i j}$ はGraph Laplacianの $(i, j)$ 要素を示し、 $v_{i} \in V$ は $i$ 番目の頂点を示す。 $\deg$ は頂点の次数。念のため次数とはその頂点につながっている辺の数のこと。

グラフの次数行列 $D$ と隣接行列 $A$ を用いるとグラフラプラシアンは次のようにかける。

$L = D - A$

いずれも $G$ によって決まる行列だが明らかなので省略する。次数行列（degree matrix）とは対角成分に頂点の次数を持つような対角行列（非対角成分がゼロ）、隣接行列（adjacency matrix）とは ${0, 1}$ のみを要素にもつ行列で $i, j$ 間のエッジが存在すれば $1$ 、そうでなければ $0$ を取る。

$\begin{matrix} D_{i j} = {\begin{matrix} \deg (v_{i}) & (i = j) \\ 0 & (i \neq j) \end{matrix} \\ A_{i j} = {\begin{matrix} 1 & ({v_{i}, v_{j}} \in E) \\ 0 & ({v_{i}, v_{j}} \notin E) \end{matrix} \end{matrix}$

Graphラプラシアンの例

こういうグラフの場合を考えると、それぞれ次のようになる。

$\begin{matrix} D = [\begin{matrix} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 \end{matrix}], A = [\begin{matrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{matrix}] \\ L = [\begin{matrix} 2 & - 1 & - 1 & 0 & 0 & 0 \\ - 1 & 4 & - 1 & - 1 & - 1 & 0 \\ - 1 & - 1 & 2 & 0 & 0 & 0 \\ 0 & - 1 & 0 & 3 & - 1 & - 1 \\ 0 & - 1 & 0 & - 1 & 3 & - 1 \\ 0 & 0 & 0 & - 1 & - 1 & 2 \end{matrix}] \end{matrix}$

ここまでは普通の話。（ここからがマグマなんです）

Laplacianといわれる理由

名前からして実関数に対するラプラシアンオペレータと関係ないとおかしいだろうということで実際関係していることを直観的に示していく。簡単な場合を使って2変数関数 $f (x, y)$ に対するラプラシアンを考える。

$Δ \equiv \frac{\partial^{2}}{\partial x^{2}} + \frac{\partial^{2}}{\partial y^{2}}$

とおくと、これは関数に作用して関数値を返す演算子となり

$Δ f (x, y) = \frac{\partial^{2} f (x, y)}{\partial x^{2}} + \frac{\partial^{2} f (x, y)}{\partial y^{2}}$

となる。こっちのラプラシアンをGraph Laplacianと結びつけるために、この値を離散化して数値計算しようと試みてみる。もっとも単純な離散化のやり方は次だろう。

$\begin{aligned} \frac{\partial^{2} f (x, y)}{\partial x^{2}} & = \frac{1}{h} (\frac{f (x + h, y) - f (x, y)}{h} - \frac{f (x, y) - f (x - h, y)}{h}) \\ = \frac{f (x + h, y) - 2 (x, y) + f (x - h, y)}{h^{2}} \end{aligned}$

小さい $h$ をとって素朴に前進差分と後退差分を使って勾配を計算し、さらにその差から2階微分を求めている。 $y$ についても同じことをやると次がすぐにわかる。

$\begin{matrix} \frac{\partial^{2} f (x, y)}{\partial x^{2}} + \frac{\partial^{2} f (x, y)}{\partial y^{2}} \\ = \frac{f (x + h, y) + f (x - h, y) + f (x, y + h) + f (x, y - h) - 4 f (x, y)}{h^{2}} \end{matrix}$

もう言いたいこと分かったと思うがこれは実平面を拡張したような次のグラフに対応している。

直観的に符号が定義と異なるが、このグラフから向きという概念をなくすということを考えればいい。このグラフはもともとの実平面の性質から数字の大小という意味で「向き」をもっているが、無向グラフの世界ではそのような概念は無いのでラプラシアンをグラフに作用させることを考えるにあたって「自分引く相手の総和」を用いることはまぁアナロジーとして許せる範囲だろう。

ついでにグラフ上の調和関数を考える時はゼロかゼロでないかが重要なので符号が逆転していても構わない。ということでGraph Laplacianは普通のラプラシアンのグラフに対する拡張っぽくなっていることが気持ち的には分かった。もっとうまい説明は無数にある気がしているが次にいく。

グラフに対するLaplacianと調和関数

ここまでの話を踏まえてグラフの頂点を定義域とする関数 $f : V \to R$ を考えると、実関数に対するラプラシアンから得た「自分引く相手の総和」というアナロジーから次の値をおもいつく。

$Δ f (v) = \sum_{(v, e) \in E} (f (v) - f (e)) (v \in V)$

書き換えると

$Δ f (v_{i}) = \sum_{j = 1}^{n} I ({v_{i}, v_{j}} \in E) (f (v_{i}) - f (v_{j}))$

ここで、 $I$ は指示関数（indicator function）で引数内が成り立つなら1、それ以外の場合にはゼロとなる便利なヤツ。実関数にたいするLaplacianがある種の演算子であったことを考えるとグラフに対するLaplacianも $f$ という関数を介することなく定義されるべきだろう。そこで2番目のラプラシアンの定義式より、各 $f (v_{j})$ の係数を抜き出しておいたものを $L$ とおくとこれはGraph Laplacianの定義そのもの。これは式をいじるまでもなく簡単に確かめられる。あとは

$L f (v_{i}) \equiv \sum_{j = 1}^{n} L_{i j} f (v_{j}), i = 1, 2, \dots, n$

とでも定義してやれば同じように使える。注意しておくとこれは行列の計算でもなんでもなくてただ $L f$ をこう定義しただけ。ようは $L$ が $f$ によらずに決定されていてこの $L$ を用いることで $i = 1, \dots, n$ に対する $f (v_{i})$ のラプラシアンが計算できていればいい。

関数 $f : V \to R$ についても調和関数かどうかがこれによって定義できる。 $f : V \to R$ がグラフ $G$ 上で調和であるとは $i = 1, 2, \dots, n$ について

$L f (v_{i}) = 0$

を満たすこと。まぁそらそうだよな。いくらでも他の書き方は存在します。

勾配に対応する接続行列

実関数の場合には $Δ = \nabla \cdot \nabla$ というような式があったがこれに対応するものが有向グラフの場合にはある。もう一度いうと有向グラフの場合にはある。無向グラフには向きという概念が無いから勾配という概念に対応するものも無くてまぁ不思議ではないね。

接続行列の定義

無向グラフ $G = (V, E)$ 、 $| V | = n, | E | = m$ に対する接続行列（incidence matrix） $B$ はそれぞれの要素が次のようになる $n \times m$ 行列

$B_{i j} = {\begin{matrix} 1 & (v_{i} \in e_{j}) \\ 0 & (v_{i} \notin e_{j}) \end{matrix}$

$v_{i}, e_{j}$ はそれぞれ $i$ 番目の頂点と $j$ 番目の辺のこと。有向グラフの場合には次のようにやるのが自然だろう。

$B_{i j} = {\begin{matrix} 1 & (e_{j} = (v, v_{i}) for some v) \\ - 1 & (e_{j} = (v_{i}, v) for some v) \\ 0 & (otherwise) \end{matrix}$

少しだけ説明すると、有向グラフでは辺 $e = {v, w}$ において $v$ と $w$ の順番に意味があるので集合ではなくベクトルのような記法 $e = (v, w)$ を用いることが多い。集合の場合には要素の順番は考慮されないがベクトルの場合は考慮するので。ただ、完全にベクトルというわけではなく有向グラフの場合にも $v \in e$ なんかの使い方はゆるす。

接続行列の例

例をみたほうが早いだろう。Graphラプラシアンのときと同じグラフを用いる。

このグラフに対する接続行列は $n = 6, m = 8$ の $n \times m$ 行列になり、

$B = [\begin{matrix} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix}]$

が各要素の値となる。行が頂点に対応していて列が辺に対応している。もし列の値を埋めるなら必ず2つの要素が1になる列に注目して辺の両端に対応する所に１を埋めていくのが易しい。次に有向グラフの場合の例、さっきのグラフの各辺に適当に向きを入れてみる。

この場合も簡単で、結果は次のようになる。

$B = [\begin{matrix} - 1 & 0 & - 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & - 1 & 0 & 1 & - 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & - 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & - 1 & - 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & - 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix}]$

有向グラフの場合は各列で $1, - 1$ がそれぞれ1回ずつあらわれる。

勾配と接続行列の関係

有向グラフを考えると、グラフ上の関数の勾配 $\nabla f$ を次のように与えるのが自然だろう。

$\nabla f (v) = {\begin{matrix} f (w) - f (v), e = (v, w) \in E \\ f (v) - f (w), e = (w, v) \in E \end{matrix}$

少し書き方はビミョーな感じはするが、ようするにある点 $v$ における勾配は、そこに接続している辺ごとに定義されていてその辺の向きによってどっちかの差分で定義されるというもの。これを実関数のときのアナロジーでいうと、関数 $f (x, y)$ のある点 $(a, b)$ における勾配は $x$ 成分 $f_{x} (a, b)$ と $y$ 成分 $f_{y} (a, b)$ が存在するということに対応する。3変数関数なら3成分あるし4変数なら4成分というようにある点に対していくつかの勾配成分があることは自然なことだ。

ちなみに無向グラフに対しては差分を取るときの符号が決められないのでこのようにしてグラフ上の関数の勾配を考えることはできない。有向グラフの接続行列を考えるとGraph Laplacianと同じようにして勾配をあたえる計算式を作り出せる。

$B^{⊤} f (e_{j}) \equiv \sum_{i = 1}^{n} B_{j i} f (v_{i}), j = 1, 2, \dots, m$

これを踏まえると接続行列の転置 $B^{⊤}$ がナブラ

$\nabla = {(\frac{\partial}{\partial x}, \frac{\partial}{\partial y})}^{⊤}$

に対応していることがわかる。

接続行列とグラフラプラシアンの関係

ここまでくると $Δ = \nabla \cdot \nabla$ のアナロジーにより $L = B B^{⊤}$ であってほしいが実際これは成り立つ。次のようにして示せる。

$\begin{aligned} (B B^{⊤})_{i j} & = \sum_{k = 1}^{m} B_{i k} (B^{⊤})_{k j} \\ = \sum_{k = 1}^{m} B_{i k} B_{j k} \\ = {\begin{array}{c} \sum_{k = 1}^{m} B_{i k} B_{i k} & (i = j) \\ - 1 & (i \neq j and e_{k} \in E for some k) \\ 0 & (otherwise) \end{array} \\ = {\begin{array}{c} \deg (v_{i}) & (i = j) \\ - 1 & (i \neq j and e_{k} \in E for some k) \\ 0 & (otherwise) \end{array} \\ = L \end{aligned}$

次のようにしてってわけでもなんでもないが2行目の式から左辺の行列の $i, j$ 要素は接続行列の $i$ 行目と $j$ 行目の内積で表せるということがわかるので、あとは具体例も参照しつつ $i = j$ の場合とそうでない場合において何が起こるかを確かめていけばいい。明らかなように無向グラフの場合は接続行列の要素に負の値が無いからどうやっても $L = B B^{⊤}$ とはならないことに注意。

以上でグラフラプラシアンを普通のラプラシアンのグラフに対する拡張であるという風に解釈できた。ついでに勾配のナブラに対する接続行列も有向グラフの場合にはちゃんとイケてることも確認した。