【グラフニューラルネットワーク】8.3~8.4

2023年度後期輪読会 #11 グラフニューラルネットワーク8.3,8.4 万能近似能力を持つグラフニューラルネットワーク 京都大学理学部 2回 千葉 一世 0

8.3,8.4 万能近似能力を持つグラフニューラルネットワーク 目次 1. 同変基底 2. 高次グラフニューラルネットワーク 3. 高次ワイスファイラー・リーマン検査 4. 関係プーリング 1

同変基底 ⚫同変基底を求める目的 𝑧𝑣 = 𝑊𝐴𝑣 のような隣接行列に重みを直接掛けるモデルは同変でないという問題があった。 しかし、重みによっては同変になるものもある。 𝑇 𝑧𝑣 = 1𝑛 Av = deg v 同変になる重みの和とスカラー倍も同変であることから、 同変な重み全体Wは線形空間になる。 線形空間Wの基底を求めることができれば、その線形結合として重みを 同変であるものに制限にした同変なモデルが構築できる。 このようなモデルを同変基底を用いたアーキテクチャという。 2

同変基底 定義 ⚫ 置換 𝜋 ∈ 𝑆𝑛 𝑘 𝑛 のk階テンソル𝑋 ∈ ℝ への作用を 𝜋 ∙ 𝑋 𝑖1,…,𝑖𝑘 = 𝑋𝜋−1 𝑖1 ,…,𝜋−1 𝑖𝑘 ∀𝑖1 , … , 𝑖𝑘 ∈ 𝑛 で定義する ⚫ 𝑘 𝑙 テンソル間の関数 𝑓 ∶ ℝ𝑛 → ℝ𝑛 が同変 𝑑𝑒𝑓 ∀ 𝜋 ∈ 𝑆 , ∀ 𝑋 ∈ ℝ𝑛 𝑘 𝑛 𝑓 𝜋 ∙ 𝑋 = 𝜋 ∙ 𝑓(𝑋) つまり、任意の入力に対して並べ替えの操作を入れ替え可能 l=0の時、 ∀ 𝜋 ∈ 𝑆𝑛 , ∀ 𝑋 ∈ ℝ𝑛 𝑘 𝑓 𝜋 ∙ 𝑋 = 𝑓(𝑋) となり、不変性を表す 3

同変基底 線形関数の同変性 𝑘 𝑙 𝑘+𝑙 𝑛 𝑛 f 𝑛 線形関数 𝑓 ∶ ℝ → ℝ のテンソル表示を W ∈ ℝ として、 𝑓 𝑋 𝑖1,…,𝑖𝑙 = 𝑊 𝑓 ∙ 𝑋 𝑖 ,…,𝑖 1 = ෍ 定理8.11 𝑙 𝑓 𝑊𝑖1,…,𝑖𝑙 ,𝑗1,…,𝑗𝑘 𝑋𝑗1,…,𝑗𝑘 とする。 𝑗1 ,…,𝑗𝑘 𝑘 𝑙 𝑛 𝑛 線形関数 𝑓 ∶ ℝ → ℝ が同変 ⟺ 𝑊 𝑓 = 𝜋 ∙ 𝑊 𝑓 (∀ 𝜋 ∈ 𝑆𝑛 ) 証明は定義通りの式変形と、標準基底を代入しての比較による 4

同変基底 同変基底を求める 𝑛 𝑘 上の同値関係～を以下で定める。 𝑖~𝑗 𝑑𝑒𝑓 ∀𝑝, 𝑞 ∈ 𝑘 ), 𝑖𝑝 = 𝑖𝑞 ֞𝑗𝑝 = 𝑗𝑞 (1, 1, 1, 2 , 2, 3) ~ (5, 5, 5, 1, 1, 2) (1, 1, 1, 2, 2, 3) ≁(5, 5, 5, 1, 1, 1) (1, 2, 1, 2 , 4, 3) ~ (5, 3, 5, 3, 1, 2) (1, 2, 1, 2, 4, 3) ≁(2, 3, 1, 3, 5, 4) この～による同値類は[k]の分割を考えることに一致する。 [6] = {1,2,3,4,5,6}を{{1,2,3},{4,5},{6}}と分割し、数字を当てると (a, a, a, b, b, c)の形の同値類と対応する。 この[k]の分割の総数をベル数といい、𝐵𝑘 と表す。つまり、同値類は𝐵𝑘 個 5

同変基底 同変基底を求める [k]の分割全体を𝑩𝑘 として、(𝑖1 , … , 𝑖𝑘 )の同値が 𝛾 ∈ 𝑩𝑘 に属することを (𝑖1 , … , 𝑖𝑘 )∈ 𝛾と表す。 𝑘 𝛾 𝑛 𝛾 ∈ 𝑩𝑘 について、テンソル𝐵 ∈ ℝ を、 右のように定義する。 1 ((𝑖1 , … , 𝑖𝑘 ) ∈ 𝛾) 𝛾 𝐵𝑖1,…,𝑖𝑘 = ቊ 0 (𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒) 一般に、k+l階層のテンソル B をk層のテンソル X に作用させるとは 𝐵 ∙ 𝑋 𝑖1,…,𝑖𝑙 = ෍ 𝐵𝑖1,…,𝑖𝑙,𝑗,…,𝑗𝑘 𝑋𝑗1 ,…,𝑗𝑘 𝑗1 ,…,𝑗𝑘 Bの添え字のl+1からk+lまでとXの成分の積の和を取る事。 𝐵 = 𝐵 1,3 , 2 , 4 の隣接行列への作用は 𝐶𝑖,𝑗 = 𝐵 ∙ 𝐴 𝑖,𝑗 = ෍ 𝐵𝑖,𝑗,𝑘,𝑙 𝐴𝑘,𝑙 = 𝑘,𝑙 ෍ 𝑘=𝑖,𝑙≠𝑖,𝑗 𝐵𝑖,𝑗,𝑘,𝑙 𝐴𝑘,𝑙 = ෍ 𝐴𝑖,𝑙 (𝑖 ≠ 𝑗) 𝑙≠𝑖,𝑗 0 (𝑖 = 𝑗) 6

同変基底 同変基底の証明 定理8.12 𝑘 𝑙 𝑛 𝑛 同変な線形変換 𝑓 ∶ ℝ → ℝ 全体は𝐵𝑘+𝑙 次元の線形空間を成し、 𝐵𝛾 𝛾 ∈ 𝑩𝑘+𝑙 は直交基底となる。 証明の概略 ・𝐵𝛾 が同変であることを確かめる。 ・各𝐵𝛾 が直交することを確かめる。 ・任意の同変なテンソルWについて、同値な添え字の成分が同じ値を 持つことを示す ・Wが𝐵𝛾 の線形結合として一通りで表せる 7

同変基底 同変基底を用いたアーキテクチャ 𝑍 = 𝜎(𝑊 𝐿 ∙ 𝜎( … 𝑊 2 ∙ 𝜎 𝑊 1 ∙ 𝐴 … )) として、 各𝑊 𝑙 を𝐵𝛾 の線形結合で表せば、全体として同変な アーキテクチャが構築できる。 ⚫ 利点 ・通常重み𝑊 𝑙 は頂点数nに依存しているが、同変基底を用いることで、 頂点数nに依存せず、異なる頂点数への汎化とメモリの削減ができる。 ・最後の層𝑊 𝐿 を階数を変えることで、グラフ全体・頂点・辺に対する値が得られ、 様々なタスクに対応できる。 ⚫ 欠点 ・頂点特徴量を考慮しておらず、表現能力が低い。 頂点特徴量も考慮した、表現能力の高いモデルを定式化する 8

高次グラフニューラルネットワーク 9

高次グラフニューラルネットワーク ● 高次グラフニューラルネットワークの入力テンソル 𝑇 ∈ ℝ𝑛×𝑛× 𝑑+1 を とする。 つまり、頂点特徴量を対角成分に並べて 𝑛 × 𝑛 × 𝑑 として、最後に隣接行列を 加えた形のテンソル 𝑋𝑗𝑘 (𝑖 = 𝑗 かつ 𝑘 ≤ 𝑑) 𝑇𝑖𝑗𝑘 = ൞0 (𝑖 ≠ 𝑗 かつ 𝑘 ≤ 𝑑) 𝐴𝑖𝑗 (𝑘 = 𝑑 + 1) 第 l 層の線形変換 𝑛𝑘𝑙−1 ×𝑑𝑙−1 𝑑𝑙−1 𝑛𝑘𝑙 ×𝑑𝑙 g𝑙 ∶ ℝ →ℝ を右のように定めて、 高次グラフニューラルネットワークを 以下で定義する 𝑧 = 𝑀𝐿𝑃(𝑔𝐿 (𝑔𝐿−1 (… 𝑔1 𝑋 … ))) 各層の最大の階数がkであるものを k次グラフニューラルネットワーク 𝑔𝑙 𝑋 :,:,…,𝑖 = 𝜎 ෍ 𝑊 𝑙,𝑖,𝑗 ∙ 𝑋:,:,…,𝑗 + 𝐶 𝑙,𝑖 𝑗=1 𝑊 𝑙,𝑖,𝑗 = ෍ 𝛼𝑙,𝑖,𝑗,𝛾 𝐵𝛾 𝛾∈𝑩𝑘𝑙 +𝑘𝑙−1 𝐶 𝑙,𝑖 = ෍ 𝛽𝑙,𝑖,𝛾 𝐵𝛾 𝛾∈𝑩𝑘𝑙 10

高次グラフニューラルネットワーク 高次グラフニューラルネットワークの万能近似能力 定理8.14 任意の不変な連続関数 𝑔 ∶ [−1, 1]𝑛 → ℝ と任意の正数 ℇ > 0 について、 高次グラフニューラルネットワーク f が存在して、 𝑔 − 𝑓 ∞ = 𝑠𝑢𝑝𝑥∈ −1, 1 𝑑 𝑔 𝑥 − 𝑓 𝑥 < 𝜀 ● 高次グラフニューラルネットワークは万能近似能力を持つ。 しかし、メモリや計算量の問題から、現実的には万能近似能力を 持つほど階数の大きいモデルは作れない。 あくまで、理論的には成り立つという話。 11

高次ワイスファイラー・リーマン検査 12

高次ワイスファイラー・リーマン検査 ● K次ワイスファイラー・リーマン検査 頂点のk個組に対して色を割り当て、色集合が一致するかを調べる アルゴリズムはワイスファイラー・リーマン検査とほとんど同じで、 0 ・色の初期値設定 ℎ𝑣 ← 𝐼𝑛𝑖𝑡 𝐺, 𝑣 𝐼𝑛𝑖𝑡 𝐺, 𝑣 は 𝐺, 𝑣 と 𝐺, 𝑢 が同型かつその時のみ同じ値を持つ関数 𝑢~𝑣 𝐺 , 𝑢 と 𝐺 , 𝑣 が同型 ⇔ ൞ 𝑋𝑢 𝑖 = 𝑌𝑣 𝑖 1 2 𝑢𝑖 , 𝑢𝑗 ∈ 𝐸1 ֞ {𝑣𝑖 , 𝑣𝑗 } ∈ 𝐸2 ・色の更新 𝑙+1 ℎ𝑣 𝑙 ←(ℎ𝑣 , 𝑙 ℎ𝑢 | 𝑢 ∈ 𝑁1 (𝑣) , … , 𝑙 ℎ𝑢 | 𝑢 ∈ 𝑁𝑘 (𝑣) ) 𝑁𝑖 𝑣 ≝ 𝑣1 , … , 𝑣𝑖−1 , 𝒗, 𝑣𝑖+1 , … , 𝑣𝑘 𝒗 ∈ 𝑉} 注意：k=1の時は通常のワイスファイラー・リーマン検査と一致しない 13

高次ワイスファイラー・リーマン検査 高次ワイスファイラー・リーマン検査の性質 (a) 任意のkについて、k次WL検査は同型なグラフについて必ず 「同型かもしれない」と出力 (b)頂点数nの同型でないグラフについて、n次WL検査は必ず 「同型でない」と出力 (c)任意のkについて、k次WL検査が「同型かもしれない」と出力する 同型でないグラフが存在 (d)通常のWL検査と2次WL検査は同じ出力をする (e)任意のkについて、k+1次WL検査が「同型かもしれない」と出力する ⇒ k次WL検査は必ず「同型かもしれない」と出力 (f)任意のk≧2について、k次のWL検査で「同型かもしれない」と出力して、 k＋1次WL検査で「同型でない」と出力する同型でないグラフが存在 14

高次ワイスファイラー・リーマン検査 高次WL検査と高次GNNの関係性 定理8.15 高次WL検査と高次GNNの等価性 ・k次ワイスファイラー・リーマン検査が「同型かもしれない」と出力するグラフに k次グラフニューラルネットワークは同一の埋め込みを出力する。 ・任意のnに対し、k次グラフニューラルネットワークが存在し、 k次ワイスファイラー・リーマン検査が「同型でない」と出力する頂点数nの グラフに異なる埋め込みを出力する。 この定理と高次ワイスファイラー・リーマン検査の性質から、 k次グラフニューラルネットワークはkについて表現能力が狭義 単調増加していく。 ● 計算量の問題からkが小さいものしか実用的でないが、 k=3,4程度でもメッセージ伝達型よりも高い表現能力を持つ ● 15

高次ワイスファイラー・リーマン検査 俗版ワイスファイラー・リーマン検査 俗版ワイスファイラー・リーマン検査 : k次ワイスファイラー・リーマン検査の色の更新式 ℎ𝑁𝑢𝐹(𝑣) ≝ ℎ 𝑢,𝑣2,…,𝑣𝑘 , ℎ 𝑣1,𝑢,…,𝑣𝑘 , … , ℎ 𝑣1,𝑣2 ,…,𝑢 𝑙+1 ℎ𝑣 𝑙 ← (ℎ𝑣 , と変更したもの 𝑙 ℎ𝑁𝐹(𝑣) | 𝑢 ∈ 𝑉 𝑢 ) • 俗版ワイスファイラー・リーマン検査の利点 k次の俗版WL検査は、(k+1)次WL検査と同じ出力をする 記憶領域を、𝑂 𝑛𝑘+1 から 𝑂(𝑛𝑘 )に減らすことができ、メモリの節約になる 16

関係プーリング 17

関係プーリング 関係プーリング : 不変でない関数を不変な関数に変換する手法 𝑓 を任意のモデルとして以下でhを定める 1 𝑧 = ℎ 𝐴, 𝑋 = ෍ 𝑓(𝜋 ∙ 𝐴, 𝜋 ∙ 𝑋) 𝑛! 𝜋∈𝑆𝑛 関係プーリングの良い性質 ・任意の関数 𝑓 について、関係プーリングｈは不変 ・関係プーリングは万能近似能力を持つ ● 関係プーリングの欠点 ・計算量が Ω 𝑛! ● サイズが小さく、対称性の高い化合物分類に用いる。 計算量を減らすために、すべては計算せずランダムサンプリングする 方法などが考えられている 18

19