【グラフニューラルネットワーク】8.5~8.6

2024前期輪読会 #12 グラフニューラルネットワーク 8.5-8.6 京都大学大学院 医学研究科 修士二年生 津村 颯人 0

はじめに Chapter 8 の狙い ● Chapter 8 は GNN が本質的に解けない問題が存在することをテーマ としている。 ● 今日の発表ではまず、MPNN の表現能力を局所分散アルゴリズムを通じて 確認する。 ● 次に、MPNNの表現能力の限界を、乱択特徴量を採用することによって 突破し、万能近似能力が得られることについて紹介する。 1

8.5 局所分散アルゴリズムの等価性 2

8.5 局所分散アルゴリズムの等価性 局所分散アルゴリズムとは? 局所分散アルゴリズム (distributed local algorithm)は、 分散ネットワークにおいて、各ノードが限られた情報のみを用いて 協調動作を行うアルゴリズムの一種である ● ● クライアント・サーバモデル メインフレームシステム ● ● ● P2Pネットワーク ブロックチェーン 分散コンピューティングシステム 3

8.5 局所分散アルゴリズムの等価性 局所分散アルゴリズムとは? 局所アルゴリズムの性質 ● 各ノードは, 近傍ノードのみと 通信を行う. ● 各ノードは, 近傍ノードとの 通信で得られた情報をもとに更新する. この過程を反復的に繰り返す. ● 全ノードが同じアルゴリズムに従う. • つまり, 通信結果と内部状態が同じ2つの コンピュータは, 次の時刻に同じ内部状態に 遷移する 4

8.5 局所分散アルゴリズムの等価性 局所分散アルゴリズムとMPNN 局所分散アルゴリズムは MPNN の計算に対応している. 対応表 局所分散アルゴリズム MPNN コンピュータ ノード 通信ケーブル エッジ 通信網 グラフ 内部状態 中間表現 通信規則 集約関数 通信関数 層の数 局所分散アルゴリズムは頂点に値を割り当てる 計算を表す. 5

8.5 局所分散アルゴリズムの等価性 局所分散アルゴリズムが解けない問題 問題1 最大次数が有限であるグラフに対して最小頂点被覆問題の近似度が2より も良くならない グラフGに対して、Gの頂点の部分集合Rであって、 Gのどの辺についても少なくともどちらかの端点がRに 含まれているものを、Gの頂点被覆という。 Gの頂点被覆のうち、要素数が最小のものを求める問題を 最小頂点被覆問題という。 オレンジの点からなる集合は頂点被覆である。 右のグラフを入力として、最小頂点被覆問題を解いた 解がαのとき、近似度はα/3 となる。 5. 最小頂点被覆問題 - Fixstars Amplify 量子コンピューティングクラウド 6

• https://amplify.fixstars.com/ja/demo/lucas2014_4_3_vertex_cover

8.5 局所分散アルゴリズムの等価性 局所分散アルゴリズムが解けない問題 問題2 最大次数がΔであるグラフに対して最小支配集合問題の近似度(Δ+1)を 達成できるが、Δ+1よりも良い近似度を達成できない。 与えられたグラフ G(V,E) の頂点集合 V’⊆V で、V' に属さない 全ての頂点vについて、vの隣接頂点のいずれか一つがV'に 属するようなV'(支配集合)のうち、最小のものを求める問題を、 最小支配集合問題という。 右の赤い点は支配集合V'であり、最小のものは(b)と(c) 近似度は (提案した支配集合の個数)/(最適な支配集合の個数) 例えば (a) だと 3/2=1.5 Dominating set - Wikipedia 7

• https://en.wikipedia.org/wiki/Dominating_set

8.5 局所分散アルゴリズムの等価性 なぜ表現能力が制限されているのか? 1. 通信回数および層数が有限であるため、大きなグラフが入力されたときに グラフの大域的な構造を用いずに局所的な情報だけから頂点の出力を 決定する必要があるから。 2. すべての頂点が一様に初期化されるため、頂点の区別がつかず、対称性が 破れない。 例) GNNは頂点特徴量に基づいて状態が初期化されるので、正則グラフ(全ての頂点が同じ次数 をもつグラフ)を入力すると、全ての頂点の出力が同じになる。 2. について、これを解決するために局所分散アルゴリズムでは乱択特徴量を 採用することで、ランダム性が導入され表現力が向上する。 最小頂点被覆問題の近似度: (Δ+1)→O(logΔ) に改善 これはGNNでも効果がある。 8

8.6 乱択特徴量 9

8.6 乱択特徴量 頂点が区別できない問題のアプローチ 頂点同士の区別がつかない…… →最初からノードの区別をつけてしまえばOK! 問題点 2 1 3 4 5 1. GNNがノード番号を暗記してしまう。 2. 場合によってはIDが非常に大きくなってしまう。 例えばソーシャルネットワークだと、頂点が 数百万あることはしばしばあり、この識別番号を One-Hot で表現すると、次元が数百万になり、 学習が安定しない。 10

8.6 乱択特徴量 乱択特徴量の導入 これらの問題を解決するために、乱数をノード特徴量に入れることを試みる。 具体的には、頂点の中間表現を以下のように初期化する。 Xv は頂点特徴量で、rv は独立同分布から抽出される乱択特徴量である。 つまり、ノード特徴ベクトルに乱数ベクトルを concat するイメージ 2 1 頂点特徴量 3 4 5 乱択特徴量 11

8.6 乱択特徴量 乱択GNNの万能近似能力 定理 n 頂点のグラフ上の任意の不変な関数 G→z について、ある関数 f0aggregate, …… fn-1aggregate, f readout が存在する。 で定義されるGNNは、確率1で を満たす。 12

8.6 乱択特徴量 乱択GNNの万能近似能力の証明 集約関数は以下のように変形できる。 ① 乱択特徴量の集合。 ② 乱択特徴量の間に辺があることを示す。 ③ 乱択特徴量と頂点特徴量の間の関係を示す。 集約関数の定義は、 これによって、 hv(l) には v から l ホップ以内の頂点の乱択特徴量の集合と、辺の情報と、 乱択特徴量と頂点の関係が格納される。 13

8.6 乱択特徴量 乱択GNNの万能近似能力の証明 とする。f recoonstruct は、全ての頂点についての乱択特徴量の集合と、辺の情報と、乱択特徴量 の頂点の関係をもとにグラフを復元する。 ただし、頂点番号は元のものではなく、rv を v の頂点番号として用いている。 このグラフを g に入力すると、g は不変なので、元のグラフと同じ出力が得られる。(おわり) このアプローチは著者の佐藤さんが提案したもので、最小頂点被覆問題や最大マッチング問題に関する効果も、 元論文(https://arxiv.org/pdf/2002.03155)にて言及している。 14

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

8.6 乱択特徴量 乱択特徴量による表現能力の向上 WRテストで見分けられないグラフ GNNが見る木(色情報)は入力グラフが 正則だったりすると、各頂点をうまく 識別できない。 実用例だと、ベンゼン環を入力したとき にこんな問題が発生しうる。 乱択特徴量を採用することで、 各頂点を識別することが可能になる。 https://arxiv.org/pdf/2002.03155 15

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

16

8.6 乱択特徴量 乱択GNNの万能近似能力の補足 乱択特徴量には重複がないと仮定する。この仮定が満たされる確率は1。 この証明は、頂点数が定数であることを前提としている。もし頂点数が無制限であれば、 万能近似能力は失われる。これはGNN の層数が一般的に定数であるためである。 そこで、GNN の層数を頂点数にあわせて可変であることを許すと、頂点数が可変の場合でも 同様に万能近似能力が得られる。ただし、この場合は、層数が無制限になってしまうので、 集約関数を層の間で適切に共有する必要がある。 17