![概要
スペクトルグラフ理論 : グラフを解析する手法の話
? グラフの隣接行列 (のようなもの) の固有値?固有
ベクトルが，元のグラフの何らかの性質を物語っている
入門的な話をします
1
2
4 5
3
G AG
?グラフカット
?彩色数
?グラフ直径
等
μ1 = -2
μ2 = -1.170
μ3 = 0
μ4 = 0.6888
μ5 = 2.4811
[01010]
[10110]
[01001]
[11001]
[00110]
固有値:](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-3-320.jpg)
![定義
? G = (V, E) : n 頂点無向グラフ (有向グラフは扱わない)
? AG := G の隣接行列，DG := G の次数行列
1
2
4 5
3
G
[01010]
[10110]
[01001]
[11001]
[00110]
AG DG
[2 ]
[ 3 ]
[ 2 ]
[ 3 ]
[ 2]](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-8-320.jpg)
![定義
? G = (V, E) : n 頂点無向グラフ (有向グラフは扱わない)
? AG := G の隣接行列，DG := G の次数行列
? LG := -AG + DG ラプラシアン行列
1
2
4 5
3
G
LG
[ 2 -1 0 -1 0]
[-1 3 -1 -1 0]
[ 0 -1 2 0 -1]
[-1 -1 0 3 -1]
[ 0 0 -1 -1 2]](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-9-320.jpg)
![定義
? AG, LG は実対称なので実数の固有値を持つ
? λ1 ≤ λ2 ≤ λ3 ≤ … ≤ λn : LG の固有値
? ψ1, ψ2, ψ3, …, ψn : 各 λi に対応する固有ベクトル
1
2
4 5
3
G
LG
[ 2 -1 0 -1 0]
[-1 3 -1 -1 0]
[ 0 -1 2 0 -1]
[-1 -1 0 3 -1]
[ 0 0 -1 -1 2]](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-10-320.jpg)
![ラプラシアンの性質
? ベクトル x に対して， ? ? ? ? ? = ? ? ? ? ?
2
?,? ∈?(?)
? なので LG は半正定値行列である
? λ1 = 0
? 半正定値行列なので固有値は ≥ 0
? LG 1 = 0 なので LG は固有値 0 を持つ
1
2
4 5
3 [ 2 -1 0 -1 0]
[-1 3 -1 -1 0]
[ 0 -1 2 0 -1]
[-1 -1 0 3 -1]
[ 0 0 -1 -1 2]](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-17-320.jpg)
![ラプラシアンの性質
λ2 はどうか?
? 行列 M, ベクトル x に対して，
? ? ??
? ? ?
を M に関する x のレイリー商と呼ぶ．
(正規化された2次形式)
1
2
4 5
3 [ 2 -1 0 -1 0]
[-1 3 -1 -1 0]
[ 0 -1 2 0 -1]
[-1 -1 0 3 -1]
[ 0 0 -1 -1 2]](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-18-320.jpg)
![ラプラシアンの性質
補題. ?2 = min ?⊥1
? ?
? ?
?
? ?
?
(= min
?⊥1, ? =1
? ? ? ? ?
2
)
?,? ∈?
1
2
4 5
3 [ 2 -1 0 -1 0]
[-1 3 -1 -1 0]
[ 0 -1 2 0 -1]
[-1 -1 0 3 -1]
[ 0 0 -1 -1 2]
1
2
4 5
3
0.63246
0.19544
0.19544 -0.51167
-0.51167](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-19-320.jpg)
![ラプラシアンの性質
補題. ?2 = min ?⊥1
? ?
? ?
?
? ?
?
証明：略 (適当に線形代数するとできる)
ちなみに：
? 実対称行列ならラプラシアンでなくても成立
1
2
4 5
3 [ 2 -1 0 -1 0]
[-1 3 -1 -1 0]
[ 0 -1 2 0 -1]
[-1 -1 0 3 -1]
[ 0 0 -1 -1 2]](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-20-320.jpg)
![応用の话
(あまり追えてないので軽くやります)
グラフ同型性判定
? [Babai, Grigoryev, Mount ‘82]
固有値の重複度が定数なら多項式時間で判定可能．
? [Furer ‘95]
実数計算無しのアルゴリズムを提案](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-37-320.jpg)
![応用の话
グラフ彩色
? 3彩色問題 : 頂点を3色に塗り分け，同じ色の点同士は
結ばれてないようにしたい
? 有名な NP 完全問題
? 入力が 3彩色可能なグラフに制限されていても難しい
? [Alon, Nabil ‘97] 入力を 3 彩色可能なランダムグラフに
制限したとき，確率ほぼ 1 でグラフを3彩色する．](https://image.slidesharecdn.com/20130905kusumoto-130905034856-/85/-40-320.jpg)
スペクトラルグラフ理论入门
- 2. 自己紹介 楠本 充 aka @ir5 所属 : 京都大学 岩間研究室 修士二年 研究 : 理論系のグラフアルゴリズム PFI : インターン(2012) → アルバイト プログラミングコンテストに参加していた系の人 ? GCJ(2011), ICPC(2012), TCO(2013) ← !!New!!
- 3. 概要 スペクトルグラフ理論 : グラフを解析する手法の話 ? グラフの隣接行列 (のようなもの) の固有値?固有 ベクトルが，元のグラフの何らかの性質を物語っている 入門的な話をします 1 2 4 5 3 G AG ?グラフカット ?彩色数 ?グラフ直径 等 μ1 = -2 μ2 = -1.170 μ3 = 0 μ4 = 0.6888 μ5 = 2.4811 [01010] [10110] [01001] [11001] [00110] 固有値:
- 4. アウトライン ? 線形代数の軽い復習 ? スペクトルグラフ理論の概要 ? 理論の話 ? 応用の话 (軽く)
- 5. 線形代数 例 : ? = 1 2 2 4 のとき， 1 2 2 4 1 2 = 5 1 2 , 1 2 2 4 ?2 1 = 0 ?2 1 なので A の固有値は 5, 0 で，対応する固有ベクトルは 1 2 , ?2 1 . n×n 行列 A に対してスカラー λ，ベクトル ψ ≠ 0 が Aψ = λψ を満たすとき λ を A の固有値，ψ を固有ベクトルと言う．
- 6. 線形代数 「?ψ ≠ 0，Aψ = λψ」 ? det(A - λI) = 0 で det(A - λI) は λ の n 次多項式なのでこのような λ は 高々 n 個ある． 異なる λ に属する固有ベクトルは互いに直交する． λ に属する固有ベクトルは無限個考えられるが， その中でも線形独立なものだけを考える． n×n 行列 A に対してスカラー λ，ベクトル ψ ≠ 0 が Aψ = λψ を満たすとき λ を A の固有値，ψ を固有ベクトルと言う．
- 7. 線形代数 一般に ? 固有値は複素数かもしれない ? 線形独立な固有ベクトルは n 個未満かもしれない が，A が実対称行列のときは ? 固有値は全て実数 ? 固有ベクトルの各要素は全て実数 ? 固有ベクトルが正規直行基底になるように n 個取れる (よく知られた性質) n×n 行列 A に対してスカラー λ，ベクトル ψ ≠ 0 が Aψ = λψ を満たすとき λ を A の固有値，ψ を固有ベクトルと言う．
- 8. 定義 ? G = (V, E) : n 頂点無向グラフ (有向グラフは扱わない) ? AG := G の隣接行列，DG := G の次数行列 1 2 4 5 3 G [01010] [10110] [01001] [11001] [00110] AG DG [2 ] [ 3 ] [ 2 ] [ 3 ] [ 2]
- 9. 定義 ? G = (V, E) : n 頂点無向グラフ (有向グラフは扱わない) ? AG := G の隣接行列，DG := G の次数行列 ? LG := -AG + DG ラプラシアン行列 1 2 4 5 3 G LG [ 2 -1 0 -1 0] [-1 3 -1 -1 0] [ 0 -1 2 0 -1] [-1 -1 0 3 -1] [ 0 0 -1 -1 2]
- 10. 定義 ? AG, LG は実対称なので実数の固有値を持つ ? λ1 ≤ λ2 ≤ λ3 ≤ … ≤ λn : LG の固有値 ? ψ1, ψ2, ψ3, …, ψn : 各 λi に対応する固有ベクトル 1 2 4 5 3 G LG [ 2 -1 0 -1 0] [-1 3 -1 -1 0] [ 0 -1 2 0 -1] [-1 -1 0 3 -1] [ 0 0 -1 -1 2]
- 11. 例 1 2 4 5 3 λ1 λ2 λ3 λ4 λ5 ψ1 ψ2 ψ3 ψ4 ψ5 1 2 3 4 5
- 12. 例 λ1 λ2 λ3 λ4 λ5 λ6 λ7 λ8 λ9 ψ1 ψ2 ψ3 ψ4 ψ5 ψ6 ψ7 ψ8 ψ9
- 13. スペクトルグラフ理論 AG や LG の固有値と固有ベクトルを使ってグラフの性質を 解析する分野 例： λ2 = 0 ? グラフ G が非連結 λk = 0, λk+1 > 0 ? グラフ G が k 個連結成分を持つ λ1 λ2 λ3 λ4 λ5 λ6
- 14. スペクトルグラフ理論 歴史: 1950s～, 古くからある 理論的な興味: グラフの特徴と固有値の特徴をうまく関連付けたい． ? グラフのパラメータを不等式で bound する 応用: ? スペクトラルクラスタリング ? 画像のセグメンテーション ? グラフの同型性判定 ? グラフの平面描画 ? etc.
- 15. スペクトルグラフ理論 今日の内容 (再) : スペクトルグラフ理論の入門的な内容 Yale 大学の Daniel Spielman 先生の講義録の前半部を 強く参考にしています http://www.cs.yale.edu/homes/spielman/561/
- 16. ラプラシアンの固有値
- 17. ラプラシアンの性質 ? ベクトル x に対して， ? ? ? ? ? = ? ? ? ? ? 2 ?,? ∈?(?) ? なので LG は半正定値行列である ? λ1 = 0 ? 半正定値行列なので固有値は ≥ 0 ? LG 1 = 0 なので LG は固有値 0 を持つ 1 2 4 5 3 [ 2 -1 0 -1 0] [-1 3 -1 -1 0] [ 0 -1 2 0 -1] [-1 -1 0 3 -1] [ 0 0 -1 -1 2]
- 18. ラプラシアンの性質 λ2 はどうか? ? 行列 M, ベクトル x に対して， ? ? ?? ? ? ? を M に関する x のレイリー商と呼ぶ． (正規化された2次形式) 1 2 4 5 3 [ 2 -1 0 -1 0] [-1 3 -1 -1 0] [ 0 -1 2 0 -1] [-1 -1 0 3 -1] [ 0 0 -1 -1 2]
- 19. ラプラシアンの性質 補題. ?2 = min ?⊥1 ? ? ? ? ? ? ? ? (= min ?⊥1, ? =1 ? ? ? ? ? 2 ) ?,? ∈? 1 2 4 5 3 [ 2 -1 0 -1 0] [-1 3 -1 -1 0] [ 0 -1 2 0 -1] [-1 -1 0 3 -1] [ 0 0 -1 -1 2] 1 2 4 5 3 0.63246 0.19544 0.19544 -0.51167 -0.51167
- 20. ラプラシアンの性質 補題. ?2 = min ?⊥1 ? ? ? ? ? ? ? ? 証明：略 (適当に線形代数するとできる) ちなみに： ? 実対称行列ならラプラシアンでなくても成立 1 2 4 5 3 [ 2 -1 0 -1 0] [-1 3 -1 -1 0] [ 0 -1 2 0 -1] [-1 -1 0 3 -1] [ 0 0 -1 -1 2]
- 21. テストベクトル 右辺が何かのグラフパラメータになるように x を取ると， グラフパラメータを固有値で下から bound できて便利． (そのような x をテストベクトルと呼ぶ) 補題より，何か適当な ? ⊥ 1を取ってくると以下が成立 ?2 ≤ ? ? ? ? ? ? ? ?
- 22. テストベクトル 例: ?(S) := {(u, v)∈E | u∈S, v ? S} ? ? ? min ? |? ? | min( ? , ??? ) (edge expansion) ? グラフのカットに関するパラメータの1つ ? (各頂点から平均何本辺が外に出ているか?) ? h(G) の計算はNP完全 S G ?(S)
- 23. テストベクトル 例: ?(S) := {(u, v)∈E | u∈S, v ? S} ? ? ? min ? |? ? | min( ? , ??? ) (edge expansion) |? ? | ? = 4/4 = 1 |? ? | ? = 2/1 = 2
- 24. テストベクトル 証明 ? S を最小のedge expansion を達成する頂点集合とする： ? ? = |? ? | ? ． ? ベクトル y を ? ? = 1 ?? ? ∈ ? 0 ????????? とおく． ? yT LG y = ?(S) である． 定理． λ2 ≤ 2h(G) S G ?(S)
- 25. テストベクトル 証明 (cont.) ? x = y - s1 (s := |S| / |V|) とおくと， ? x ⊥ 1 ? xTLGx = ?(S) ? xTx = |S|(1-s) となるので， 定理． λ2 ≤ 2h(G) S G ?(S) ?2 ≤ ? ? ? ? ? ? ? ? = ? ? ? 1 ? ? ≤ 2?(?)
- 26. 独立集合?彩色数 定理． S を G の独立集合とする． S の平均次数を dave(S) とするとき，以下が成立． ? ≤ ?(1 ? ? ???(?) ? ? ) ? 証明はテストベクトルによる． ? ただし ?2 = m?? ? ? ? ? ? ? ? ? ? を用いる これを利用して彩色数を bound できる．
- 27. 独立集合?彩色数 定理． χ(G) を G の彩色数とすると， ? ? ≥ ? ? ? ? ? ? ???(?) 証明 ? k = χ(G) として Si を色 i の点集合とすると ?? ≤ ? 1 ? ? ??? ?? ? ? i = 1,...,k について足すと， n ≤ n(k - dave(G)/λn) ∴ k ≥ λn / (λn - dave(G))
- 28. Cheeger の不等式 d(S) := S の次数和 ? ? ? min ? |? ? | min(? ? ,? ??? ) (conductance) ? カットに関するパラメータの一つ |? ? | min(? ? ,? ??? ) = 4/12 = 1/3
- 29. Cheeger の不等式 さらに ? ? ? ? ? ? 1 2 ? ? ? ? ? 1 2 とする． ? 対角成分が 1 になるように行と列に値をかけたもの 0 = ν1 ≤ ν2 ≤ ν3 ≤ ... ≤ νn : NG の固有値 ? 左側はテストベクトルによる． ? 右側は結構難しい．Luca Trevisan の確率的手法による 証明がカッコいい． 定理 (Cheeger の不等式)： ?2 2 ≤ ? ? ≤ √(2?2)
- 30. Cheeger の不等式 いい点： 固有ベクトルを求めると実際にこの不等式を達成する カット集合 S を1つ求めることができる． ? 対応するベクトルの要素が閾値より低いものを カット頂点に選ぶ，とかする → 質の良いカットを求められる可能性 ? ? ≤ √(2?2)
- 31. 隣接行列の固有値
- 32. 隣接行列 隣接行列の固有値?固有ベクトルについて考える． ? μ1 ≥ μ2 ≥ μ3 ≥ … ≥ μn : AG の固有値 ? φ1, φ2, φ3, …, φn : 各 λi に対応する固有ベクトル とする
- 33. 隣接行列 なぜ λi と μi で並びが逆? もし G の次数がすべて d なら LG = dI - AG なので ? LG の最大固有値 = d - (AG の最小固有値) ? … ? LG の最小固有値 = d - (AG の最大固有値) と対応しているため． 性質 (Perron-Frobenius) : G が連結なとき， ? μ1 + μn ≥ 0 ? μ1 > μ2 ? φ1 > 0 とか
- 34. 彩色数 (Wilf の定理) 次の補題を利用する： ? i. (G の平均次数) ≤ μ1 ? ii. グラフから1頂点削除すると隣接行列の最大固有値は 変わらないか，減少する． 証明： n の帰納法による． ? n=1 は自明．n ≥ 2 のときを考える． ? i. より，次数 μ1 以下の点があるのでそれを v とする． ? ii. と帰納法の仮定より G-{v} は μ1+1 色で塗れる． v の次数は μ1 以下なので，μ1+1 色のうち使われてない色で v を塗ると良い． ? ? ≤ ?1 + 1
- 35. 応用の话
- 36. 応用の话 (あまり追えてないので軽くやります) グラフ同型性判定 ? 2つのグラフ G, H が同型か判定したい ? 一般には P 問題でも NP完全でもないと予想されている ? 自明なこと: G, H で固有値の列が違う ? G, H は非同型 ? 逆は成立しない．
- 37. 応用の话 (あまり追えてないので軽くやります) グラフ同型性判定 ? [Babai, Grigoryev, Mount ‘82] 固有値の重複度が定数なら多項式時間で判定可能． ? [Furer ‘95] 実数計算無しのアルゴリズムを提案
- 38. 応用の话 スペクトラルクラスタリング ? グラフのクラスタリングアルゴリズム ? Normalized cut という edge expansion を少し変形した パラメータを最大化する． ? 固有ベクトルを計算することで，良い normalized cut を 得られる． ? 一応理論上の bound 有り? ? 実用上は理論の bound よりも良い性能が出る模様 ? データマイニングの分野で結構応用されているっぽい?
- 39. 応用の话 画像セグメンテーション ? Normalized cut の応用 ? グラフの密度と出力の精度にトレードオフがある Spectral segmentation with multiscale graph decomposition. Cour et al. ‘05
- 40. 応用の话 グラフ彩色 ? 3彩色問題 : 頂点を3色に塗り分け，同じ色の点同士は 結ばれてないようにしたい ? 有名な NP 完全問題 ? 入力が 3彩色可能なグラフに制限されていても難しい ? [Alon, Nabil ‘97] 入力を 3 彩色可能なランダムグラフに 制限したとき，確率ほぼ 1 でグラフを3彩色する．
- 41. 応用の话 グラフ彩色 アルゴリズム： ? 隣接行列の固有ベクトル φn, φn-1 を計算 ? 2次元上の点集合 (φn(i), φn-1(i)) を考える． それらを原点を通る直線で n/2 個ずつに分ける． ? 「直線から近い点」「直線から遠くて (左側 |右側) に ある点」の 3 つに分類 → 3彩色になるよう調整する
- 42. プログラミングコンテスト における固有値 実際使われた例は殆ど見かけない．強いて挙げるなら… KUPC2013 K問題 「encode/decode」 「長さ L の0/1 列と↓のグラフの長さ L+10 のウォークを 1対1対応させる関数を作れ．」 長さ L のウォークの個数 = Θ(μ1^L) で，↑のグラフでは μ1 = 2 であることを利用する． http://www.math.dartmouth.edu/~m68f11/algcomb.pdf
- 43. グラフスペクトル解析ツール 実際に固有値を見たい人向けツール 他にも多数． Sage ： 本格的数式処理システム http://www.sagemath.org/ newGraph : 手軽 http://www.mi.sanu.ac.rs/newgraph/
- 44. まとめ スペクトルグラフ理論の入門的な内容について発表した． 理論： ? ラプラシアンのテストベクトルによるパラメータ bound ? カットパラメータ ? 独立集合，彩色数 応用： ? スペクトラルクラスタリング ? グラフ彩色 他にも グラフ直径，Expander グラフ，グラフ平面描画， ランダムウォーク，行列木定理など．