[グラフ理論] グラフラプラシアンと固有値、GFT

2023年02月03日

グラフ理論

グラフラプラシアンと固有値、GFT

本記事は、グラフラプラシアンとその固有値に関する理論を解説する。さらに、グラフフーリエ変換 (GFT) を導入し、その応用や Python による実装例も示す。

ソースコード

github

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

google colaboratory

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

実行環境

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

!sw_vers

ProductName:		macOS
ProductVersion:		15.2
BuildVersion:		24C101

!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
numpy     : 1.25.2
matplotlib: 3.8.1

Watermark: 2.4.3

1. グラフラプラシアンの基礎

1.1 グラフの定義

頂点数を $N$ とする無向グラフ $G = (V, E)$ を考える。 $V$ は頂点の集合で、大きさは $|V| = N$ である。 $E$ は辺の集合で、各辺は $(i, j)$ の形で表される。隣接行列を $\mathbf{A}$ とすると、要素 $A_{ij}$ は頂点 $i$ と頂点 $j$ が隣接するかを示す。無向グラフの場合、$\mathbf{A}$ は対称行列となる。 $A_{ij} > 0$ なら辺の重みがあるグラフを、$A_{ij} \in {0,1}$ なら単純グラフを表す。

1.2 次数行列

次数行列 $\mathbf{D}$ は対角行列であり、対角要素 $D_{ii}$ は頂点 $i$ の次数を表す。次数は隣接行列の行和で定義される。つまり、$D_{ii} = \sum_{j=1}^{N} A_{ij}$ となる。重み付きグラフでも同様に行和を用いる。よって、$\mathbf{D}$ は常に非負の要素を持つ対角行列になる。

1.3 グラフラプラシアンの定義

グラフラプラシアン $\mathbf{L}$ は次のように定義される。 $$ \mathbf{L} = \mathbf{D} - \mathbf{A}. $$ これは実対称かつ半正定値な行列である。頂点数が $N$ の場合、$\mathbf{L}$ は $N \times N$ の大きさとなる。 $\mathbf{L}$ の各行の和は 0 になる。この性質から、$\mathbf{L}$ には必ず固有値 0 が存在する。

1.4 グラフラプラシアンの性質

$\mathbf{L}$ は半正定値 (固有値がすべて 0 以上)。
固有値の最小値は 0 で、その固有ベクトルは一様ベクトルになる。
連結グラフなら固有値 0 の重複度は 1 である。
非連結グラフなら、連結成分の数だけ 0 の固有値がある。
行列 $\mathbf{L}$ は対称なので、直交固有ベクトルによる分解が可能。

1.5 応用例

グラフカットの評価 (ノルム最小化)。
クラスタリング (スペクトラルクラスタリング)。
データ解析 (頂点上の信号処理)。
推薦システムでのユーザ間グラフなどへの応用。

1.6 簡単なPythonによる実装例

以下のコード例では、単純グラフを想定する。変数名に型名を付与している。

import numpy as np

# 頂点数
N = 5

# 隣接行列の例 (対称行列)
A = np.array([[0, 1, 0, 1, 0], [1, 0, 1, 0, 0], [0, 1, 0, 1, 1], [1, 0, 1, 0, 1], [0, 0, 1, 1, 0]], dtype=float)

# 次数行列
D = np.diag(A.sum(axis=1))

# グラフラプラシアン
L = D - A

# 固有値と固有ベクトルの計算
eigvals, eigvecs = np.linalg.eigh(L)

print("L:")
print(L)
print("Eigenvalues:")
print(eigvals.round(2))
print("Eigenvectors:")
print(eigvecs.round(2))

L:
[[ 2. -1.  0. -1.  0.]
 [-1.  2. -1.  0.  0.]
 [ 0. -1.  3. -1. -1.]
 [-1.  0. -1.  3. -1.]
 [ 0.  0. -1. -1.  2.]]
Eigenvalues:
[0.   1.38 2.38 3.62 4.62]
Eigenvectors:
[[ 0.45  0.51 -0.6  -0.2  -0.37]
 [ 0.45  0.51  0.6  -0.2   0.37]
 [ 0.45 -0.2   0.37  0.51 -0.6 ]
 [ 0.45 -0.2  -0.37  0.51  0.6 ]
 [ 0.45 -0.63  0.   -0.63  0.  ]]

この例では、単純な 5 頂点グラフを作成している。
固有値や固有ベクトルを求めることで、スペクトラル特性を分析できる。

2. 固有値と固有ベクトルの性質

2.1 固有値の定義

行列 $\mathbf{M}$ に対し、ベクトル $\mathbf{x}$ とスカラー $\lambda$ が存在して、 $$ \mathbf{M}\mathbf{x} = \lambda \mathbf{x} $$ が成り立つとき、$\lambda$ は固有値、$\mathbf{x}$ は固有ベクトルと呼ばれる。

2.2 グラフラプラシアンの固有値分解

グラフラプラシアン $\mathbf{L}$ は実対称行列なので、固有値は実数である。さらに、正定値であるため、固有値は 0 以上で並ぶ。 $\mathbf{L}$ のスペクトル分解は、 $$ \mathbf{L} = \mathbf{U} \Lambda \mathbf{U}^\top $$ という形で書ける。 $\Lambda$ は固有値を対角に並べた行列、$\mathbf{U}$ は固有ベクトルを列に並べた直交行列。

2.3 固有値の並び順

固有値を昇順に並べると、 $$ 0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_N $$ となる。ここで、連結グラフなら $\lambda_2$ は 0 より大きい。 $\lambda_2$ は、グラフの連結性を判定する目安 (Fiedler value) とも呼ばれる。

2.4 固有ベクトルの解釈

$\lambda_1 = 0$ に対応する固有ベクトルは一様ベクトル。
$\lambda_2$ に対応する固有ベクトル (Fiedler vector) は、頂点の二分割を示唆する。
他の固有ベクトルも、グラフ構造に沿った振動モードを示す。

2.5 数学的な見方と写像

グラフラプラシアンは、$V \to \mathbb{R}^N$ の空間で作用する線形写像とみなせる。写像 $\mathbf{L}: \mathbb{R}^N \to \mathbb{R}^N$ はベクトルを別のベクトルに写す。固有ベクトルはその変換で伸び縮みせず、スカラー倍となる方向を示す。

2.6 固有値計算のコスト

固有値の計算は一般に $O(N^3)$ の計算量がかかる。
大規模グラフでは反復法や近似アルゴリズムの利用が多い。
企業で扱う数百万頂点規模のグラフでは、効率化が鍵となる。

2.7 具体的な数値例

例えば、$N = 4$ の簡単なグラフを考える。隣接行列を $$ \mathbf{A} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} $$ とする。このとき、 $$ \mathbf{D} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix} $$ となる。よって、$\mathbf{L} = \mathbf{D} - \mathbf{A}$ は $$ \begin{pmatrix} 1 & -1 & 0 & 0 \\ -1 & 3 & -1 & -1 \\ 0 & -1 & 2 & -1 \\ 0 & -1 & -1 & 2 \end{pmatrix} $$ になる。これを計算すると、固有値は概ね $[0, 2, 3, 4]$ となる。直交固有ベクトルの空間を調べると、各頂点の構造的特徴が見えてくる。

3. GFT (グラフフーリエ変換)

3.1 GFTの定義

GFTは、グラフ上の信号を周波数領域に変換する手法である。フーリエ変換が従来の周期関数を正弦波基底に展開するように、 GFTは頂点間の繋がりを反映した固有ベクトル基底に展開する。つまり、グラフラプラシアンの固有ベクトルが「フーリエ基底」となる。

3.2 GFTの数式的表現

頂点上の信号をベクトル $\mathbf{x} \in \mathbb{R}^N$ とする。グラフラプラシアンの固有ベクトルを列に並べた直交行列を $\mathbf{U}$ とする。すると、GFT は以下で与えられる。 $$ \hat{\mathbf{x}} = \mathbf{U}^\top \mathbf{x}. $$ ここで、$\hat{\mathbf{x}}$ は周波数領域の表現となる。逆変換は $$ \mathbf{x} = \mathbf{U} \hat{\mathbf{x}}. $$

3.3 低周波・高周波の概念

固有値が小さい部分はグラフ上で緩やかな変動を表す (低周波)。
固有値が大きい部分は頂点間で急激な変動を表す (高周波)。
グラフ特有の幾何構造に適応したスペクトル分析が可能。

3.4 GFTの応用例

グラフ信号処理におけるフィルタ設計。
ノイズ除去や圧縮での活用。
推薦システム。
ソーシャルネットワーク解析でのクラスタ検出。

3.5 Python実装例

簡単なGFTを行うコード例を示す。

import numpy as np

# 隣接行列 (例)
A = np.array([[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]], dtype=float)

# 次数行列
D = np.diag(A.sum(axis=1))

# グラフラプラシアン
L = D - A

# 固有値と固有ベクトル
eigvals, eigvecs = np.linalg.eigh(L)

# 任意の信号 (頂点に値があると想定)
x = np.array([1, 2, 3, 4], dtype=float)

# GFT
xhat = eigvecs.T @ x

# 逆GFT
x_inv = eigvecs @ xhat

print("Original Signal:", x)
print("Transformed Signal:", xhat.round(2))
print("Inverse Signal:", x_inv.round(2))

Original Signal: [1. 2. 3. 4.]
Transformed Signal: [-5.   -2.04  0.71 -0.58]
Inverse Signal: [1. 2. 3. 4.]

eigvecs が固有ベクトルを列ベクトルとして含む。
xhat が GFT 後の周波数領域表現となる。
x_inv は逆変換で元の信号に戻した結果。

3.6 メリット

グラフ構造を反映した周波数解析が可能。
次元削減やクラスタリングなど、多様な応用が広がる。
ノイズ低減や特徴抽出に活用できる。

3.7 デメリット

固有値計算が高コスト (大規模グラフでの計算負荷)。
動的に更新されるグラフには不向き (再計算が必要)。
基礎理論の習得が難しく、導入ハードルが高い。

4. 企業における応用例

4.1 レコメンドシステム

ユーザとアイテムの相互関係をグラフとみなし、GFTで特徴を抽出する。類似ユーザがもつ信号成分を基底展開することで、柔軟な予測が可能となる。協調フィルタリングと組み合わせる事例もある。大手ECサイトなどでは数千万ユーザ規模での効率化が課題になる。

4.2 ソーシャルネットワーク分析

ユーザ間のつながりをグラフ構造で表し、コミュニティを可視化する。固有ベクトルを用いることで、分割や影響力のある頂点を検出できる。バズを起こしやすいユーザの発見などに応用。

4.3 交通ネットワーク解析

道路や鉄道の結節点を頂点とし、路線や経路を辺として表す。 GFTを用いて混雑のパターンを周波数空間で分析できる。交通量予測や経路最適化に寄与する。

4.4 IoTデバイス管理

センサ同士のネットワークが大規模なグラフを形成する。固有値スペクトルで異常センサを特定し、早期対策につなげる。クラスタ単位での障害検知や故障予測が可能となる。

5. 数学的計算例と詳細

5.1 グラフラプラシアンの固有値分解の計算例

$N = 3$ の小規模グラフを例にする。隣接行列を $$ \mathbf{A} = \begin{pmatrix} 0 & 2 & 0 \\ 2 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} $$ とする。次数行列は $$ \mathbf{D} = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{pmatrix}. $$ よって、 $$ \mathbf{L} = \begin{pmatrix} 2 & -2 & 0 \\ -2 & 3 & -1 \\ 0 & -1 & 1 \end{pmatrix} $$ となる。この行列 $\mathbf{L}$ の固有値は、計算すると概ね $[0, 2, 4]$ 程度となる。固有ベクトルをそれぞれ求めることで、GFTの基底を得られる。

5.2 固有ベクトルに基づく信号の解釈

例えば、固有値 0 に対応する固有ベクトルは全ての頂点が同じ符号となる場合が多い。次に大きい固有値 2 に対応する固有ベクトルは、辺の一部に正負の違いが現れる。こうしたベクトルで信号を表現することで、グラフ上のゆるやかな変動や急峻な変動を区別できる。

5.3 フィルタリングの設計

GFT を用いて、信号 $\mathbf{x}$ を $\hat{\mathbf{x}}$ に変換する。次に、特定の固有値帯域を強調・抑制するフィルタ対角行列 $\mathbf{H}$ を用いる。つまり、 $$ \hat{\mathbf{y}} = \mathbf{H} \hat{\mathbf{x}}, $$ とする。逆変換で、 $$ \mathbf{y} = \mathbf{U} \hat{\mathbf{y}} $$ を得る。この $\mathbf{y}$ がフィルタ後の信号となる。

5.4 計算例でのフィルタ適用

上記の例で、固有値が小さい成分を残すフィルタを考える。 $\lambda = 0$ に対応する成分を 1、他を 0 にするようなフィルタを適用する。すると、最もゆるやかな成分のみを抽出できる。これは、グローバルなトレンドを捉えるイメージになる。

5.5 フロベニウスノルムによる誤差評価

信号の近似精度を評価するとき、$|| \mathbf{x} - \mathbf{y} ||_F$ のようなノルムを用いる。 GFT の圧縮やフィルタリング後の誤差を定量的に示すことが可能である。大規模データでも、部分的に固有成分を用いることで圧縮率と精度を調整できる。

5.6 具体的な数値を用いた計算例 (Python)

以下は、$N=4$ のグラフでフィルタリングを行う例である。

import numpy as np

# 隣接行列
A = np.array([[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 1], [1, 1, 1, 0]], dtype=float)

# 次数行列
D = np.diag(A.sum(axis=1))

# ラプラシアン
L = D - A

# 固有値・固有ベクトル
eigvals, eigvecs = np.linalg.eigh(L)

# 信号
x = np.array([10, 5, 3, 1], dtype=float)

# GFT
xhat = eigvecs.T @ x

# 小さい固有値のみ残すフィルタ (閾値=2)
H = np.diag([1 if val < 2 else 0 for val in eigvals])

# フィルタ適用
xhat_filtered = H @ xhat

# 逆変換
x_filtered = eigvecs @ xhat_filtered

# 誤差評価
error = x - x_filtered
error_norm = np.linalg.norm(error)

print("Original Signal     :", x.round(2))
print("Eigenvalues        :", eigvals.round(2))
print("GFT Coefficients   :", xhat.round(2))
print("Filtered Coeffs    :", xhat_filtered.round(2))
print("Filtered Signal    :", x_filtered.round(2))
print("Error Vector       :", error.round(2))
print("Error Norm         :", error_norm.round(2))

Original Signal     : [10.  5.  3.  1.]
Eigenvalues        : [-0.  2.  4.  4.]
GFT Coefficients   : [-9.5   4.95  2.87  3.46]
Filtered Coeffs    : [-9.5  0.   0.   0. ]
Filtered Signal    : [4.75 4.75 4.75 4.75]
Error Vector       : [ 5.25  0.25 -1.75 -3.75]
Error Norm         : 6.69

このように、特定の固有値帯域のみを残すフィルタを適用できる。結果として、低周波成分のみを保持した近似が得られ、信号が平滑化される。

6. まとめと活用方法

6.1 理論的まとめ

グラフラプラシアン $\mathbf{L} = \mathbf{D} - \mathbf{A}$ はグラフ解析の重要行列。
固有値 0 が少なくとも 1 つあり、それがグラフの連結性と関係する。
固有ベクトルは「スペクトル基底」として機能し、GFTで利用される。
GFT は頂点信号を周波数空間に写像する枠組み。

6.2 実装面での考慮

小規模グラフならNumPyの固有値計算関数で容易に実装できる。
大規模グラフでは疎行列に特化したアルゴリズムや近似手法を導入する。
PythonのSciPyやPyTorchでも疎行列演算を活用できる。
計算精度や計算時間のトレードオフを考慮する。

6.3 企業利用時のメリット

ソーシャルグラフやユーザ-アイテム関係を高次元で扱える。
既存の単純な手法では捉えにくい複雑なクラスタ構造を探れる。
一度固有分解を行えば、多様な信号処理タスクに応用可能。
レコメンドシステムやセンサデータ解析において新たな視点が得られる。

6.4 企業利用時のデメリット

数百万～数億頂点クラスでは固有分解が困難。
動的グラフでは、都度再計算が必要。
理論や数式の理解が必須で、人材育成にもコストがかかる。

6.5 最新動向

グラフニューラルネットワーク (GNN) との融合が進む。
スペクトラルGNN ではラプラシアン固有値を活用し、局所演算を定義。
グラフ信号処理の高速化や近似アルゴリズムの研究が活発。

結論

この記事では、グラフラプラシアンとその固有値、そしてGFTを概観した。グラフラプラシアンは、グラフ上の構造解析やスペクトラルクラスタリングに必須である。固有値と固有ベクトルが示す意味を理解することで、グラフ信号をより深く分析できる。 GFTを通じて、頂点上の信号を周波数領域に写し、平滑化や特徴抽出など幅広い応用が可能になる。企業においては、推薦システムやソーシャルネットワーク分析などに応用できる。ただし、大規模なグラフにおける計算コストや動的環境下での再計算が課題となる。