ベクトル場とグラフ理論で利用される演算子の対比

ベクトル場の演算子 $ \mathrm{div} \cdot \mathrm{grad} = \Delta$ とグラフ理論におけるラプラシアン行列$L$の対応関係を整理する。 両者の理論的背景を備忘録として整理しておく。 とても興味深い内容である。

github

  • jupyter notebook形式のファイルはこちら

google colaboratory

  • google colaboratory で実行する場合はこちら

実行環境

OSはmacOSである。LinuxやUnixのコマンドとはオプションが異なりますので注意していただきたい。

!sw_vers

ProductName:		macOS
ProductVersion:		13.5.1
BuildVersion:		22G90

!python -V

Python 3.9.17

基本的なライブラリをインポートし watermark を利用してそのバージョンを確認しておきます。 ついでに乱数のseedの設定をします。

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import random

import scipy
import numpy as np

import matplotlib
import matplotlib.pyplot as plt


seed = 123
random_state = 123

random.seed(seed)
np.random.seed(seed)


from watermark import watermark

print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))

Python implementation: CPython
Python version       : 3.9.17
IPython version      : 8.17.2

scipy     : 1.11.2
matplotlib: 3.8.1
numpy     : 1.25.2

Watermark: 2.4.3

ベクトル場と演算子 (div, grad)

ベクトル場の概要

ベクトル場は、空間の各点にベクトルが割り当てられた構造である。 物理学では流体速度や電磁界などを表す際に用いられる。 機械学習の最適化問題でも、勾配ベクトル場が活用される場面が多い。

ベクトル場 $\mathbf{F}$ を考える。 たとえば $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ のように定義域から終域へ写像する。 各点 $ \mathbf{x} \in \mathbb{R}^n $ に対して、$\mathbf{F}(\mathbf{x})$ は $n$ 次元ベクトルを返す。

grad (勾配) 演算子

スカラー場 $ f(\mathbf{x}) $ に対して、その勾配は $$ \mathrm{grad} \cdot f = \nabla f $$ と書かれる。 成分で書けば、$\displaystyle \nabla f = \left( \frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n} \right) $ となる。

座標変換にも依存するが、ユークリッド空間では単純に偏微分ベクトルで表現される。 物理的には、最も大きく変化する方向を示す。 機械学習の勾配降下法では、この勾配を利用してパラメータを更新する。

div (発散) 演算子

ベクトル場 $\mathbf{F}(\mathbf{x}) = (F_1, F_2, \ldots, F_n)$ に対する発散は $$ \mathrm{div} \cdot \mathbf{F} = \nabla \cdot \mathbf{F} $$ と表記される。 成分表記では、$ \nabla \cdot \mathbf{F} = \sum_{i=1}^n \frac{\partial F_i}{\partial x_i} $ となる。

流体の例では、発散が正の値は「源」、負の値は「吸い込み」を意味する。 信号処理でも、ノイズ除去などに発散を使った手法がある。 ラプラシアン演算子もこの組み合わせで定義される。

ラプラシアン (div grad) の定義

スカラー場 $ f(\mathbf{x}) $ に対するラプラシアンは $$ \Delta f = \mathrm{div}(\mathrm{grad} \cdot f) $$ と書ける。 すなわち $$ \Delta f = \nabla \cdot (\nabla f) = \sum_{i=1}^n \frac{\partial^2 f}{\partial x_i^2} $$ である。

この演算子は偏微分方程式で重要な役割を果たす。 熱方程式や波動方程式など、多数の現象がラプラシアンを通じて記述できる。 離散化すると、グラフ理論のラプラシアン行列へ結びつく。

グラフ理論におけるラプラシアン行列

グラフ構造の基礎

グラフ理論では、頂点集合と辺集合からなる構造を扱う。 企業でのレコメンドシステムは、アイテムやユーザを頂点として扱う。 エッジの重みが類似度や関連度を示すことも多い。

無向グラフ $G = (V, E)$ を考える。 頂点数を $n$、辺数を $m$ とし、頂点は $V = {1, 2, \ldots, n}$。 辺 $(i, j) \in E$ は頂点 $i, j$ 間の接続を表す。

隣接行列と次数行列

グラフ $G$ の隣接行列を $\mathbf{A}$ とする。 サイズは $n \times n$ で、$\mathbf{A}_{ij} = 1$ ならば頂点 $i$ と $j$ が隣接。 一般に重みがある場合は、その重みが書かれる。

次数行列を $\mathbf{D}$ とする。 対角成分 $\mathbf{D}_{ii}$ は頂点 $i$ の次数（接続数または重みの合計）を表す。 他の要素は 0 となるので、$\mathbf{D}$ は対角行列になる。

グラフのラプラシアン行列

グラフのラプラシアン行列 $\mathbf{L}$ は、 $$ \mathbf{L} = \mathbf{D} - \mathbf{A} $$ として定義される。 各頂点の次数から隣接関係を引いた形になっている。

しばしば正規化ラプラシアンとして $$ \mathbf{L}_{\text{norm}} = \mathbf{D}^{-\frac{1}{2}} \mathbf{L} \mathbf{D}^{-\frac{1}{2}} $$ を用いることもある。 スペクトルクラスタリングやグラフ信号処理において重要である。

固有値と固有ベクトル

$\mathbf{L}$ は、非負の固有値を持つ半正定値行列である。 最小固有値は 0 に対応し、固有ベクトルは定数ベクトルになる。 グラフの連結性やクラスターの情報が固有値に反映される。

このラプラシアン行列は、連続的なラプラシアンを離散化した形ともみなせる。 イメージとしては、ベクトル場の $\mathrm{div},\mathrm{grad}$ が行列で表されたもの。 頂点間の繋がりを離散的に表現した形である。

数学的な関係性の解説

連続と離散の対応

連続空間の微分演算子 $ \Delta = \mathrm{div} \cdot \mathrm{grad} $ は、空間の各点における二階微分の和を表す。 一方、グラフのラプラシアン $\mathbf{L}$ は離散構造での差分を表現する。

スカラー場 $f(\mathbf{x})$ を頂点上のスカラー量 $f(i)$ に置き換える。 勾配に対応する「差分」をエッジごとに計算し、それを頂点に集計する操作が発散に該当する。 その結果、$\mathbf{L}$ が離散的な $ \mathrm{div} \cdot \mathrm{grad} = \Delta $ とみなせる。

離散ラプラシアンの定義

ある頂点 $i$ に対して、$f(i)$ から隣接頂点 $j$ の $f(j)$ へ向かう差分を足し合わせる。 次数行列 $\mathbf{D}$ と隣接行列 $\mathbf{A}$ の組み合わせで、その差分が表現される。 結果として $$ (\mathbf{L} \mathbf{f})(i) = \sum_{j \in N(i)} [f(i) - f(j)] $$ という形になる。 ここで $N(i)$ は頂点 $i$ の隣接頂点集合である。

これは連続空間での $$ \Delta f (\mathbf{x}) = \sum_{k=1}^n \frac{\partial^2 f}{\partial x_k^2} $$ に対応する。 「近傍」の頂点との差を中心頂点に集約する操作が、二階微分の離散化に近い。

スペクトル的な観点

ラプラシアン $\mathbf{L}$ の固有値分解は、連続ラプラシアンの固有関数分解と類似する。 固有値が小さい部分は「緩やかな変化」を示し、大きい固有値は「急激な変化」を示す。 グラフクラスタリングは固有ベクトルを利用して分割を行う。

物理の熱方程式や拡散方程式も、スペクトル分解により離散的に解釈できる。 グラフ信号処理では、ラプラシアン固有ベクトルがフーリエ基底として利用される。 このように、連続と離散の境界を超えた一貫した構造が見えてくる。

まとめ

ベクトル場の $ \mathrm{div} \cdot \mathrm{grad} = \Delta$ と、グラフ理論のラプラシアン行列$L$には深い対応関係がある。 連続の微分演算が離散の差分演算に置き換わり、熱拡散や波動などと同様の現象を表せる。

結論

この記事では、ベクトル場の演算子 $ \mathrm{div}\cdot\mathrm{grad}=\Delta $ と、グラフ理論におけるラプラシアン行列$L$の関係を概説した。

参考文献