スペクトルクラスタリング｜ネットワーク科学

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：グラフラプラシアンとスペクトル　|　関連：モジュラリティ最大化・ランダムウォークと拡散の数理

要点（BLUF）

スペクトルクラスタリング：ラプラシアンの小さい方の固有ベクトルでノードを低次元に埋め込み、その空間でクラスタリングする。
Fiedlerベクトル（ $\lambda_2$ の固有ベクトル）の符号が、グラフを「切るエッジ数が少ない」ように2分割する。
モジュラリティ最大化（モジュラリティ最大化）とは別経路でコミュニティを見つける。クラスタリング一般は機械学習のturf、ここはグラフ分割の数理。

概念：固有ベクトルで切る

コミュニティ検出（第3章）はモジュラリティを最適化する組合せ問題でした。スペクトルクラスタリングは全く別のアプローチ：グラフを「切るとコストが最小になるように」2分割する問題を、ラプラシアン（グラフラプラシアンとスペクトル）の固有値問題に緩和して解きます。整数の分割問題を連続の固有値問題に置き換えることで、効率的に良い分割が得られます。

数式：最小カットの緩和

グラフを2集合 $A, B$ に分けるとき、切れるエッジ数（カット）を小さく、かつ両側のサイズをバランスさせたい。各ノードに $x_i \in \{+1, -1\}$ を割り当ててカットを書くと、これは

\min_{\mathbf{x}} \; \mathbf{x}^\top L \mathbf{x} = \min_{\mathbf{x}} \sum_{(i,j)\in E}(x_i - x_j)^2

を、 $\mathbf{x}$ が定数ベクトルでない（ $\mathbf{x} \perp \mathbf{1}$ ）という制約の下で解くことに対応します。 $x_i$ を整数 $\pm 1$ に限るのは NP困難。そこで $x_i$ を実数に緩和すると、答えは「 $\mathbf{1}$ に直交する範囲でレイリー商を最小化するベクトル」 — すなわち $\lambda_2$ の固有ベクトル（Fiedlerベクトル）になります。その符号でノードを2群に振り分けるのが基本形です。

$k$ クラスタへ拡張するときは、小さい方から $k$ 個の固有ベクトルを並べて各ノードを $k$ 次元に埋め込み、その空間で k-means します。

コードで確認

import networkx as nx
import numpy as np

# 2つの密なクラスタを1本の橋で弱く繋ぐ
G = nx.Graph()
G.add_edges_from(nx.complete_graph(5).edges())            # ノード0-4
G.add_edges_from(nx.complete_graph(range(5, 10)).edges()) # ノード5-9
G.add_edge(0, 5)                                          # 橋

L = nx.laplacian_matrix(G).toarray().astype(float)
vals, vecs = np.linalg.eigh(L)
fiedler = vecs[:, 1]                  # 2番目に小さい固有値の固有ベクトル
labels = (fiedler > 0).astype(int)    # 符号で2分割

print("Fiedlerベクトルの符号による分割:", labels.tolist())
print("前半5ノード:", labels[:5].tolist(), " 後半5ノード:", labels[5:].tolist())

実行結果：

Fiedlerベクトルの符号による分割: [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
前半5ノード: [1, 1, 1, 1, 1]  後半5ノード: [0, 0, 0, 0, 0]

ラプラシアンの第2固有ベクトルの符号だけで、2つのクラスタ（0-4 と 5-9）がきれいに分離されました。橋（エッジ0-5）を1本だけ切る最小カットを、固有値計算が自動的に見つけています。

手順の図解

graph LR
    A["グラフ"] --> B["ラプラシアン L=D-A"]
    B --> C["下位k個の固有ベクトル<br/>を計算"]
    C --> D["各ノードをk次元に埋め込み"]
    D --> E["k-means等でクラスタリング"]

数式の直観的意味

Fiedlerベクトルが分割を与えるのは、 $\mathbf{x}^\top L\mathbf{x} = \sum (x_i-x_j)^2$ を「定数を除いて最小化」するベクトルだからです。これは「密に繋がったノードどうしには似た値を、疎にしか繋がらないノードには違う値を」割り当てるのが最適、という意味。密な塊の内部では値がほぼ揃い、塊の境界で符号が切り替わる。だから符号で切ると、ちょうど「繋がりの薄いところ」で分割できます。 $\lambda_2$ が小さい（代数的連結度が低い、グラフラプラシアンとスペクトル）ほど、きれいに切れる境界が存在する証拠です。ランダムウォーク（ランダムウォークと拡散の数理）の視点では「ウォーカーが長く閉じ込められる領域＝クラスタ」に対応します。

⚠️ よくある誤解・落とし穴

どのラプラシアンを使うかで結果が変わる：正規化ラプラシアン（ $L_{sym}$ , $L_{rw}$ ）は次数の偏りに頑健で、実務では正規化版がよく使われます。
緩和解は近似：実数緩和した固有ベクトルを符号で離散化するので、厳密な最小カットとは限りません。
モジュラリティ最大化とは別物：スペクトルクラスタリングは「カット最小化」、モジュラリティは「ヌルモデル超過」。同じコミュニティを返すとは限りません（モジュラリティ最大化）。

対応シミュレーション

本文のコードがそのまま検証用です。k-means などクラスタリング一般は機械学習へ（薄リンク）。