【グラフニューラルネットワーク】6.5

2024年度前期輪読会 #9 「グラフニューラルネットワーク」 6.5 スペクトルをもとにした古典的な手法 京都大学理学部 宮本真弥 0

6.5 スペストルをもとにした古典的な手法 目次 1. 行列分解 2. スペクトルクラスタリング 3. カットとスペクトルクラスタリングの関係 1

1. 行列分解 2

1. 行列分解 復習:行列分解 以下の教師なし頂点表現学習問題を考える 問題 入力: 重み付きグラフ 𝐺 = 𝑉, 𝐸, 𝑤 出力: グラフ構造を考慮した頂点の埋め込み 𝒁 ∈ ℝ𝑛×𝑑 この問題は隣接行列の行列分解により解くことができる 最適化問題は以下で定義 1 2 ⊤ min ෍ ෍ 𝑫𝑢𝑣 + 𝑾𝑢𝑣 − 𝒁𝑢 𝒁𝑣 𝑛×𝑑 2 𝑍∈ℝ 𝑢∈𝑽 𝑣∈𝑽 この問題の最適解は行列(𝑫 + 𝑾)の固有値𝜆1 ≥ ⋯ ≥ 𝜆𝑛 ≥ 0と固有ベクトル 𝑣1 , 𝑣2 , … , 𝑣𝑛 を用いると次のようになる 𝒁 = 𝜆1 𝒗1 , 𝜆2 𝒗2 , ⋯ , 𝜆𝑑 𝒗𝑑 ∈ ℝ𝑛×𝑑 3

1. 行列分解 k-正則グラフにおける行列分解の解釈 ● k-正則グラフ⋯ すべての次数がkであるグラフ 𝐃= 円環グラフ(k=2) 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 𝐃= 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 k=4 k-正則グラフの非正規化ラプラシアンは𝑳 = 𝑫 − 𝑨 = 𝑘𝑰𝑛 − 𝑨 𝑳が固有値𝜆に属する固有ベクトル𝒉を持つとき、 𝑳𝒉 = 𝜆𝒉 ⇔ 𝑘𝒉 − 𝑨𝒉 = 𝜆𝒉 ⇔ 2𝑘 − 𝜆 𝒉 = 𝑘𝒉 + 𝑨𝒉 = 𝑫 + 𝑨 𝒉 よって𝒉は(𝑫 + 𝑨)の固有値(2𝑘 − 𝜆)に属する固有ベクトル ● 4

1. 行列分解 k-正則グラフにおける行列分解の解釈 再掲:行列分解の最適化問題の解 𝒁 = 𝜆1 𝒗1 , 𝜆2 𝒗2 , ⋯ , 𝜆𝑑 𝒗𝑑 ∈ ℝ𝑛×𝑑 k-正則グラフの場合、これは非正規ラプラシアンの固有ベクトルを固有値の 小さい順に𝑑個出力することに相当する。 頂点𝑣に割り振られた固有ベクトル𝒛の固有値𝜆が大きいならば、 𝑫 + 𝑨 𝒛 = 𝑘𝒛 + 𝑨𝒛 = 𝜆𝒛 ⇔ 𝑨𝐳 = 𝜆 − 𝑘 𝒛 ⇔ 𝒛⊤ 𝑨𝒛 = 𝜆 − 𝑘 𝒛⊤ 𝒛 つまり𝒛⊤ 𝑨𝒛が大きいので、𝐳は𝑉𝑎𝑟 𝒛 = 𝒛⊤ 𝑫 − 𝑨 𝒛が小さな滑らかな信号 一般のグラフでも(𝑫 + 𝑨)の固有ベクトルと(𝑫 − 𝑨)の固有ベクトルは似た傾 向を持つことが多いが、もちろん異なるときもあるので行列分解とグラフフー リエ基底どちらが有用かは場合による。 5

1. 行列分解 グラフラプラシアンの比較 あらかじめ50:50でクラスタリングされている右のグラフを 非正規化ラプラシアン、対称正規化ラプラシアン、推移ラプラ シアンの3つの方法での2次元埋め込みの比較 ● 非正規化ラプラシアン 𝑳の固有ベクトルは次の問題の解 min𝑉 𝑉𝑎𝑟(𝑓) = min𝑉 ෍ 𝑓∈ℝ 𝑓∈ℝ 𝑓 𝑢 −𝑓 𝑣 2 , ||𝑓||2 = 1 {𝑢,𝑣}∈𝐸 接続する辺が多い頂点ほど（つまり次数が大きい頂 点）、ディリクレエネルギーの寄与が大きい。よっ て、この最適化問題ではできるだけディリクレエネ ルギーの寄与が大きい頂点の信号を小さくしようと するため、次数の小さい頂点の信号は極端な値にな ることがある。またこれによって、次数の大きい頂 点はほとんど同じ埋め込みになってしまう。 6

1. 行列分解 グラフラプラシアンの比較 対称正規化ラプラシアン・推移ラプラシアン 次数により正規化しているので外れ値がでにくく、 線形分離に近い形になっている。よってラベルを予 測する問題で有用。 一般的には推移ラプラシアンを用いるのがよいと される。 𝑫−1 𝑳𝒗 = 𝜆𝒗 ⇔ 𝑳𝒗 = 𝜆𝑫𝒗 ⇔ 𝑳 − 𝜆𝑫 𝒗 = 0 𝜆 = 0のとき(𝑳 − 𝜆𝑫)は非正規化ラプラシアンになる ので、𝒗は同じクラスタ内の頂点で近い値をとるが、 対称正規化ラプラシアンの固有ベクトル𝒉は 1 𝒉 = 𝑫2 𝒗(∵ 命題6.8)より、同じクラスタ内でも deg(𝒗)に比例した値をとってしまう。対称正規化ラ プラシアンは計算上での利点もないので推移ラプラ シアンのほうがよい。 ● 7

2.スペクトルクラスタリング 8

2. スペクトルクラスタリング ベクトルクラスタリング問題 以下の問題設定を考える 問題 入力：ベクトルの集合𝒙1 , 𝒙2 , … , 𝒙𝑛 , クラスタ数 𝐾 出力：各ベクトルに対するクラスタの割当 𝜋 ∶ 𝑛 → [𝐾] ● K-means法⋯ データの距離を用いるクラスタリング手法 各頂点にクラスタをランダム に振り、重心を計算 各頂点のクラスタを重心の近 いほうに振りなおす 各クラスタの頂点の重心を 計算、以後繰り返し 9

2. スペクトルクラスタリング K-means法の問題点 K-means法は球形のクラスタを仮定しているため、折れ曲がったク ラスタには対応していない。 →スペクトルクラスタリングはこの問題を解消 10

2. スペクトルクラスタリング スペクトルクラスタリングの手順 1. 頂点クラスタリング問題に帰着 k-近傍グラフなどを構成 辺の重みはガウスカーネル ||𝒙𝑖 − 𝒙𝑗 ||2 𝑾𝑖𝑗 = exp − 2𝜎 2 がよく用いられる。 2. ラプラシアンを用いた頂点埋め込みを求める 類似度の高い頂点がほぼ同じ値に凝縮される →K-means法が使えるようになる 3. 埋め込みに対してK-means法を適用しクラスタ リング クラスタ数は固有値の大きさから推測可能 11

2. スペクトルクラスタリング スペクトルクラスタリングのアルゴリズム 入力: 重み付き隣接行列 𝑾 ∈ ℝ𝑛×𝑛 埋め込みの次元 𝑑 クラスタ数 𝐾 出力: 各頂点に対するクラスタの割当 // 次元行列の計算 // ラプラシアン行列の計算 // 固有値の小さい順 3. 𝑫 = 𝐷𝑖𝑎𝑔 𝑾𝟏 𝑳=𝑫−𝑾 𝒉1 , … , 𝒉𝑛 ← 𝑳の正規直交固有ベクトル 4. 𝒁 ← [𝒉2 , … , 𝒉𝑑+1 ] ∈ ℝ𝑛×𝑑 5. 𝜋 ← 𝒁に対してK-means法を適用し、各頂点に対するクラスタの割り当て を計算 6. 𝑹𝒆𝒕𝒖𝒓𝒏 𝜋 1. 2. // 埋め込み行列の計算 12

2. スペクトルクラスタリング ■補足｜グラフの構築について von Luxburgの「A Tutorial on Spectral Clustering」では3つのグラフ構 築手法が紹介されている。 ・𝜀-近傍グラフ⋯ベクトル間の距離を用いて、距離近傍内にある頂点と辺を結 びグラフを構築する方法 ・k-近傍グラフ⋯ 各頂点に対して最も近いk個の頂点と辺を結びグラフを構築 する方法、すべての頂点からk本の辺を引く方法と、すべての頂点の次数がkと なるようにうまく辺をとる方法がある。後者を相互k-近傍グラフという。 ・全結合グラフ⋯すべての頂点間に辺を引いてグラフを構築する方法。この場 合、データの類似度が辺のデータに落とし込まれていないので、辺に重みをつ けることで類似度を表現。ここでよく使われるのが前述したガウスカーネルで ある。 論文では、一般にk-近傍グラフを用いるのがよいと主張されている。根拠とし て隣接行列が疎になることと、経験的にパラメータによる不安定性が小さいこ とが述べられている。 13

3. カットとスペクトルクラスタリングの関係 14

3. カットとスペクトルクラスタリングの関係 単純なカットの問題点 まず頂点のニ分割クラスタリング問題を考える（重みありでも同様） 問題 入力: グラフ 𝐺 = 𝑉, 𝐸 出力: 頂点の分割 (𝑆, 𝑉 ∖ 𝑆) この問題を解くには、頂点集合𝑆と𝑉 ∖ 𝑆の間の辺の本数 Cut 𝑆 = Cut 𝑆, 𝑉 ∖ 𝑆 = ({{𝑢, 𝑣} ∈ 𝐸 | 𝑢 ∈ 𝑆, 𝑣 ∉ 𝑆 )| を最小化する argmin Cut 𝑆, 𝑉 ∖ 𝑆 𝑆⊆𝑉 を求めればよいように思えるが… 15

3. カットとスペクトルクラスタリングの関係 単純グラフの問題点 しかし多くの場合1点や2点な ど、小さい𝑆が選択されてしまい うまくいかない。 原因:𝑆の大きさを考慮していない →𝑆の大きさを考慮したカットの 定義が必要 ● 比カット ● 正規化カット ● コンダクタンス 16

3. カットとスペクトルクラスタリングの関係 集合の大きさを考慮したカットの定義 比カット（Ratio Cut） RatioCut(𝑆) Cut(𝑆) Cut(𝑆) ≔ + 𝑆 |𝑉 ∖ 𝑆| RatioCut(G) ≔ min RatioCut(𝑆) 𝑆⊆𝑉 ・集合の頂点の数で正 規化 ・𝑆としてある程度大き なものが選択される 正規化カット (Normalized Cut) NCut(𝑆) Cut(𝑆) Cut(𝑉 ∖ 𝑆) ≔ + vol(𝑆) vol(V ∖ 𝑆) NCut(𝐺) ≔ min NCut(𝑆) コンダクタンス 𝜙 𝑆 Cut(𝑆) ≔ min{vol(𝑆), vol(𝑉 ∖ 𝑆)} vol(𝑆) ≔ ෍ deg(𝑢) ・正規化カットと同様 ・任意の頂点集合𝑆 ⊆ 𝑉 に対して 𝑆⊆𝑉 𝑢∈𝑆 ・辺の数で正規化 ・内部で強く結びつい ているような集合が選 択される 𝜙 𝐺 ≔ min 𝜙 𝑆 𝑆⊆𝑉 𝜙 𝑆 ≤ NCut 𝑆 ≤ 2𝜙(𝑆) の関係が成り立つ 参考：石原尚．”研究発表スライドがサクサク作れるPowerPointテンプレート（2022版）”．note．2022-05-30更新 17

3. カットとスペクトルクラスタリングの関係 比カットと非正規化ラプラシアンの関係 |𝑉∖𝑆| 𝑉 |𝑆| 𝑓𝑣𝑆 = − 𝑆 𝑉 𝑉∖𝑆 𝑣∈𝑆 という信号𝑓 𝑆 ∈ ℝ𝑛 を考えると、比カットの最小化は 𝑣 ∈𝑉∖𝑆 min RatioCut(𝑆) = min Var 𝑓 𝑆 𝑠. 𝑡. ||𝑓 𝑆 ||2 = 1, ෍ 𝑓𝑣𝑆 = 0 𝑆⊆𝑉 𝑆⊆𝑉 𝑣∈𝑉 と等価。一方、非正規化ラプラシアンの第2固有値𝜆2 と固有ベクトル𝒉2 は min Var 𝑓 𝑠. 𝑡. ||𝑓||2 = 1, ෍ 𝑓𝑣 = 0 𝑓⊆ℝ𝑛 𝑣∈𝑉 の最適値及び最適解である。上の問題は、下の問題の信号を𝑓 𝑆 に制限したもの であるから RatioCut(𝐺) ≥ 𝜆2 が成り立つ。逆に下の問題は上の問題を離散的な信号から任意の連続信号に緩 和した問題ととらえることができる。 18

2. スペクトルクラスタリング ■補足｜式6.24と式6.121の違いについて 式6.24は min𝑛 Var 𝒇 𝑠. 𝑡. ||𝒇||2 = 1, 𝒇⊤ 𝒉1 = 0 𝑓⊆ℝ となっており、厳密には式6.121 min Var 𝒇 𝑠. 𝑡. ||𝒇||2 = 1, ෍ 𝑓𝑣 = 0 𝑓⊆ℝ𝑛 𝑣∈𝑉 と異なる。 グラフが連結であるならばこの二つの式は等価になる。なぜなら グラフが連結なら𝒉1 が定数関数になるため、 1 ⊤ 𝒇 𝒉1 = 0 ⇔ ෍ 𝑓𝑣 ∙ = 0 ⇔ ෍ 𝑓𝑣 = 0 𝑛 𝑣∈𝑉 𝑣∈𝑉 となるからである。ここではグラフをカットする問題を考えているので、グラ フが連結であることを前提としているためこのような違いが生じたと思われる。 19

3. カットとスペクトルクラスタリングの関係 正規化カットと対称正規化ラプラシアンの関係 deg(𝑣)vol(𝑉∖𝑆) vol(𝑉)vol(𝑆) 𝑓𝑣𝑆 = deg(𝑣)vol(𝑆) − vol(𝑉)vol(𝑉∖𝑆) 𝑣∈𝑆 という信号を考えると、NCutの最小化は 𝑣 ∈𝑉∖𝑆 min NCut(𝑆) = min Var sym 𝒇𝑆 𝑠. 𝑡. ||𝒇𝑆 ||2 = 1, ෍ deg(𝑣)𝑓𝑣𝑆 = 0 𝑆⊆𝑉 𝑆⊆𝑉 𝑣∈𝑉 と等価。対称正規化ラプラシアンの第2固有値𝜆2 ∈ ℝと固有ベクトル𝒉2 ∈ ℝ𝑛 は min Var sym 𝒇 𝑠. 𝑡. ||𝒇|| = 1, ෍ deg(𝑣)𝒇 = 0 𝑓⊆ℝ𝑛 2 𝑣 𝑣∈𝑉 の最適値及び最適解なので、比カットと同様に以下の関係が成り立つ NCut(𝐺) ≥ 𝜆2 また、NCutやコンダクタンスを𝜆2 で上から抑えられる（チーガーの不等式） 1 𝜆2 ≤ 𝜙 𝑆 ≤ 𝜆2 , 𝜆2 ≤ NCut(𝑆) ≤ 2 2𝜆2 2 20

3. カットとスペクトルクラスタリングの関係 複数のクラスタへの分割 これまでの議論を一般のクラスタリングに拡張 問題 入力：グラフ 𝐺 = 𝑉, 𝐸 , クラスタ数 𝐾 出力：各頂点に対するクラスタの割当 𝜋 ∶ 𝑛 → [𝐾] 複数クラスタがある場合のカットの定義 𝐾 Cut(𝑆𝑘 ) RatioCut(𝑆1 , 𝑆2 , … , 𝑆𝐾 ) ≔ ෍ |𝑆𝑘 | 𝑘=1 𝐾 Cut(𝑆𝑘 ) NCut(𝑆1 , 𝑆2 , … , 𝑆𝐾 ) ≔ ෍ vol(𝑆𝑘 ) 𝑘=1 Cut(𝑆𝑘 ) 𝜙 𝑆1 , 𝑆2 , … , 𝑆𝐾 ≔ max 𝑘=1,2,…,𝐾 vol(𝑆𝑘 ) 21

3. カットとスペクトルクラスタリングの関係 複数のクラスタへの分割 ニ分割の場合と同様に議論できる。ここでは比カットのみ扱う。 1 𝑓𝑣 𝑆,𝑘 = ቐ |𝑆𝑘| 0 𝑣 ∈ 𝑆𝑘 の信号を考えると、最小化問題は次と等価 𝑣 ∉ 𝑆𝑘 𝐾 min ෍ Var(𝒇(𝑆,𝑘) ) s.t. ||𝒇(𝑆,𝑘) ||2 = 1, 𝒇 𝑆,𝑘 ⊤ 𝒇(𝑆,𝑙) = 0 ∀𝑘 ≠ 𝑙 𝑆1 ,…,𝑆𝐾 𝑘=1 この問題を一般の連続信号に緩和した問題 𝐾 min 𝒉1 ,…,𝒉𝐾 ∈ℝ ෍ Var(𝒉𝑘 ) s.t. || 𝒉𝑘 ||2 = 1 𝒏 ∀𝒌, 𝒉⊤ 𝑘 𝒉𝑙 = 𝟎 ∀𝑘 ≠ 𝑙 𝑘=1 の最適解はグラフスペクトル基底[𝒉1 𝒉2 , … , 𝒉𝐾 ]となる。最適値は 𝐾 ෍ 𝜆𝑘 (≤ RatioCut(𝐺)) 𝑘=1 22

3. カットとスペクトルクラスタリングの関係 複数のクラスタ分割最小化問題の計算量 ニ分割の場合 ３つ以上の分割の場合 一次の埋め込みによって各デー タが数直線に埋め込まれる。各頂 点が近いほど同じ値に埋め込まれ るから、クラスタは図のように右 と左に分かれていると考えられる。 よって分割の候補は(𝑛 − 1)通り ニ分割の場合と違って、分割の候 補を絞ることができないので、考え られるすべての分割を計算するしか ない。よって分割の候補は𝐾 𝑛 通り。 計算量が膨大になるので厳密な解が 求められない。→スペクトルクラス タリング 𝑆1 𝑆2 23

まとめ まとめ１ まとめ２ まとめ３ 行列分解による最適解はグラフフーリエ基底と解釈できる 推移ラプラシアンがうまく頂点を分類する スペクトルクラスタリングはデータの形状に対して柔軟に対応 カット最小化問題の緩和はグラフフーリエ基底が最適解 カット最小化問題は計算量が膨大。よってスペクトルクラスタリングが有効 24

25

参考文献 Ulrike von Luxburg「A Tutorial on Spectral Clustering」2007 URL: https://arxiv.org/pdf/0711.0189 26

• https://arxiv.org/pdf/0711.0189