ラプラス・ベルトラミ作用素とグラフラプラシアンの固有値

曲がった空間のラプラシアンは、計量の逆行列と行列式だけで書けます^[1,2]。

$Δ f = - \frac{1}{∣ g ∣} \frac{\partial}{\partial x ^{i}} (∣ g ∣ g^{ij} \frac{\partial f}{\partial x ^{j}})$

極座標に入れれば $\frac{1}{r} \partial_{r} (r \partial_{r} f)$ の形が出ます。グラフの上では $L = D - W$ という行列になる。同じ作用素の顔です。

平坦な場合の復習

$R^{n}$ の標準計量では、 $g^{ij} = δ^{ij}$ 、 $∣ g ∣ = 1$ です。上の式は次に戻ります^[1]。

$Δ f = - i \sum \frac{\partial ^{2} f}{\partial ( x ^{i} ) ^{2}}$

符号にマイナスが付いています。リーマン幾何では $Δ$ を正の作用素として扱う約束です^[1]。

解析の教科書では逆符号で書きます。固有値の符号がひっくり返るだけなので、どちらを使うかを最初に決めておきます。

定義そのもの

もとの定義は $Δ f = - div (grad f)$ です^[1]。

外微分と余微分で書くと $Δ f = d^{*} df = - * d * df$ になります^[1]。ヘッセ行列のトレースでも書けて、 $Δ f = - tr (Hess f)$ 。

微分形式に広げたホッジ・ラプラシアン $d δ + δ d$ を $0$ 形式に制限したものが、この作用素です^[4]。

座標での式を組む

手順は $3$ 段です。計量の逆行列 $g^{ij}$ を出し、行列式の平方根 $∣ g ∣$ を出し、上の式に入れる。

対角な計量なら、逆行列は各成分の逆数、行列式は対角成分の積です。ほとんどの例はこれで終わります。

$∣ g ∣$ は体積要素と同じ量です。座標のセルがどれだけ伸びているかを表しています。

例：平面の極座標

$g_{r r} = 1$ 、 $g_{θ θ} = r^{2}$ なので $g^{r r} = 1$ 、 $g^{θ θ} = 1/ r^{2}$ 、 $∣ g ∣ = r$ 。

入れると次のようになります。

$Δ f = - \frac{1}{r} [\frac{\partial}{\partial r} (r \frac{\partial f}{\partial r}) + \frac{\partial}{\partial θ} (\frac{1}{r} \frac{\partial f}{\partial θ})]$

展開すると $- (f_{r r} + \frac{1}{r} f_{r} + \frac{1}{r ^{2}} f_{θ θ})$ 。よく見る形です。

第 $2$ 項の $1/ r$ が、 $∣ g ∣ = r$ から出ています。座標を曲げたぶんの補正です。

例：3 次元の球座標

$∣ g ∣ = r^{2} sin θ$ 、 $g^{r r} = 1$ 、 $g^{θ θ} = 1/ r^{2}$ 、 $g^{φφ} = 1/ (r^{2} sin^{2} θ)$ 。

$Δ f = - \frac{1}{r ^{2}} \partial_{r} (r^{2} \partial_{r} f) - \frac{1}{r ^{2} sin θ} \partial_{θ} (sin θ \partial_{θ} f) - \frac{1}{r ^{2} sin ^{2} θ} \partial_{φ}^{2} f$

$r$ を止めると、後ろの $2$ 項が単位球面のラプラシアンになります。前の $1$ 項が半径方向。

この分解が、変数分離で球面調和関数が出てくる仕組みです。

自己随伴で正

コンパクトで境界がない場合、 $Δ$ は $L^{2}$ 内積について自己随伴で、しかも正です^[1]。

$(Δ f, h) = (f, Δ h), (Δ f, f) \geq 0$

$(Δ f, f) = ∥ grad f ∥^{2}$ から出ます。等号は $f$ が定数のときだけ。

$2$ 階の楕円型作用素なので、コンパクト多様体ではスペクトルが離散になります^[1]。固有値は有限重複度を持ち、固有関数が完全正規直交系を作る。

固有値を小さい順に $0 = λ_{0} < λ_{1} \leq λ_{2} \leq \dots$ と並べられます。

例：球面のスペクトル

標準計量の $S^{n}$ では、固有値が完全に分かります^[1]。

$spec (S^{n}) = {k (n + k - 1) ∣ k = 0, 1, 2, \dots}$

固有関数は $R^{n + 1}$ の $k$ 次斉次調和多項式を球面に制限したものです^[1]。 $n = 2$ なら球面調和関数。

重複度も数えられます^[1]。

$dim H_{k} = (k n + k) - (k - 2 n + k - 2)$

計量を $c$ 倍すると固有値は $1/ c$ 倍になります。半径 $a$ の球面なら $k (n + k - 1) / a^{2}$ です^[1]。

例：平坦トーラスのスペクトル

$T_{Γ} = R^{n} /Γ$ に平坦な計量を入れます。 $Γ$ は階数 $n$ の格子です^[1]。

双対格子を次で定めます^[1]。

$Γ^{*} = {x \in R^{n} ∣ ⟨ x, y ⟩ \in Z \forall y \in Γ}$

$x \in Γ^{*}$ に対して $f_{x} (y) = e^{2 π i ⟨ x, y ⟩}$ がトーラス上の関数になります。これが固有関数です^[1]。

$Δ f_{x} = 4 π^{2} ∥ x ∥^{2} f_{x}$

スペクトルは双対格子のベクトルの長さで決まります。格子の形が、そのまま音の高さの表に化ける。

形は聞こえるか

スペクトルが同じなら形も同じか、という問いが立ちます。答えは否です。

Milnor が反例を作りました^[1]。次元 $16$ 以上のすべての次元で、同スペクトルだが等長でない平坦トーラスの組が存在します。

鍵は双対格子です。 $2$ つのトーラスが同スペクトルであることは、原点まわりのどの球にも $Γ_{1}^{*}$ と $Γ_{2}^{*}$ の元が同数入ることと同値になります^[1]。

$Γ (8) \oplus Γ (8)$ と $Γ (16)$ という $2$ つの格子が、その条件を満たしながら等長にならない^[1]。音は同じでも形が違う例です。

グラフの上のラプラシアン

離散の側にも同じ名前の作用素があります^[3]。

頂点に重み付きの辺があるグラフで、隣接行列を $W$ 、次数を対角に並べた行列を $D$ とします。

$L = D - W$

これが非正規化グラフラプラシアンです^[3]。 $n \times n$ の行列で、対称かつ半正定値になります。

二次形式が本質です^[3]。

$f^{T} L f = \frac{1}{2} i, j \sum w_{ij} (f_{i} - f_{j})^{2}$

隣り合う頂点での値の差を、重みを付けて足した量。連続の側で $(Δ f, f) = ∥ grad f ∥^{2}$ だったものと同じ役割です。

固有値 0 が数えるもの

$L$ の最小固有値は $0$ で、対応する固有ベクトルは全成分が $1$ のベクトルです^[3]。

もっと強い主張があります。固有値 $0$ の重複度は、グラフの連結成分の個数に等しい^[3]。

固有空間は、各成分の指示ベクトルが張ります。連続の側で、調和 $0$ 形式の次元が連結成分の数だったのと同じ形です^[4]。

canvas: 式は呼び出しにそのまま書いてください。この引数は焼けません -> drawMath(… label …)

離散でも連続でも、 $0$ 固有値がつながり方を数えている。

正規化ラプラシアン

次数がばらつくときは、正規化した形を使います^[3]。

$L_{sym} = D^{- 1/2} L D^{- 1/2} = I - D^{- 1/2} W D^{- 1/2}, L_{rw} = D^{- 1} L = I - D^{- 1} W$

$L_{rw}$ はランダムウォークに対応します。 $L_{rw}$ の固有値問題は、一般化固有値問題 $Lu = λ D u$ と同じ^[3]。

$L_{sym}$ の二次形式にも、差の形が残ります^[3]。

$f^{T} L_{sym} f = \frac{1}{2} i, j \sum w_{ij} (\frac{f _{i}}{d _{i}} - \frac{f _{j}}{d _{j}})^{2}$

スペクトラルクラスタリング

小さいほうの固有値に属する固有ベクトルを並べ、その座標で点をクラスタに分ける。これがスペクトラルクラスタリングです^[3]。

固有値 $0$ が連結成分を数えるので、 $0$ に近い固有値は「ほとんど切れている」場所を拾います。

弱い辺をまたぐ差は二次形式にほとんど効きません。だから固有ベクトルはそこで符号を変え、切れ目を教えてくれる。

曲面の上の振動が節線で分かれるのと、同じ理屈です。

グラフラプラシアン $L = D - W$ の固有値 $0$ の重複度が表すのはどれですか。

辺の本数
連結成分の個数
頂点の次数の最大値

__RESULT__

$f^{T} L f = \frac{1}{2} \sum w_{ij} (f_{i} - f_{j})^{2}$ が $0$ になるのは、つながっている頂点で $f$ が同じ値をとるときです。各連結成分の上で定数、という自由度がそのまま固有空間の次元になります。

書き下した式を確かめる

書き下した式が正しいかどうかは、 $3$ つの当て方で確かめられます。

定数関数に当てて $0$ になるか見ます。 $Δ1 = 0$ が成り立たなければ、どこかで符号か係数を落としています。

平坦な場合に戻るか見ます。極座標の式で $θ$ に依存しない関数を入れると、 $- (f_{r r} + f_{r} / r)$ が残る。これは $1$ 次元の動径方向の式です。

既知の固有関数を入れる手もあります。トーラスで $e^{2 π i ⟨ x, y ⟩}$ を入れて $4 π^{2} ∥ x ∥^{2}$ が出れば、係数がそろっています。

計量の行列式と逆行列。この $2$ つを出せば、曲がった空間でもグラフの上でも、同じ作用素が書けます。

参考

Mark Hamilton, Uwe Semmelmann. *Vorlesungsskript Differentialoperatoren auf Mannigfaltigkeiten*. Universität Stuttgart, SS 13.

Laplace operator. Encyclopedia of Mathematics.

Ulrike von Luxburg. *A Tutorial on Spectral Clustering*. Statistics and Computing 17 (4), 2007.

Yuchen Chen. *Hodge Decomposition*.

計量の逆行列と行列式だけで、曲がった空間のラプラシアンが書けます。$\Delta f = -\frac{1}{\sqrt{|g|}}\partial_i(\sqrt{|g|}\,g^{ij}\partial_j f)$ に極座標を入れれば $1/r$ の項が出て、球座標なら半径方向と球面方向に分かれる。コンパクトならスペクトルは離散で、$S^n$ では $k(n+k-1)$、平坦トーラスでは双対格子の $4\pi^2\|x\|^2$。スペクトルが同じでも形が同じとは限らず、Milnor が 16 次元以上で反例を作りました。グラフでは $L = D - W$ になり、固有値 $0$ の重複度が連結成分の数を数える。