【グラフニューラルネットワーク】5.5~5.8

2024前期輪読会 #5 グラフニューラルネットワーク 5.5-5.8 京都大学工学部理工化学科 1回生 岡本 和優 0

5.5 層別サンプリング 1

層別サンプリングとは何か 層別サンプリングは計算に含める頂点を各層で独立にサンプリング する手法である。 近傍サンプリングの復習 近傍サンプリングは𝑙層目で計算する頂点を，𝑙＋1層で計算する頂 点の近傍からサンプリングする。この意味で層間に依存性がある。 p.129 アルゴリズム5.1 𝑙層で計算する頂点 = 𝑙 + 1層で計算する頂点 + それに隣接する頂 点の集合𝑁(𝑣)からサンプリングした頂点 2

層別サンプリングの利点と欠点（近傍サンプリングと比較して） 利点 ● アルゴリズムの大幅な簡略化によって高速化が実現される。 ● 計算量が層数について指数的に増大しない（グラフニューラル ネットワークは多くの場合2～3層程度だから，そのときは近傍 サンプリングでも問題のないことが多い。）。 欠点 近傍サンプリングと異なり，隣接する頂点の中からサンプリングす るわけではないので，以下のような問題が生じる。 ● 次数の小さい頂点にメッセージが送られない場合がある （(𝑁(𝑣) ∩ 𝐵𝑙 )が空集合になることがある）。 ● サンプリングで選ばれた頂点がミニバッチから遠く離れている 場合は，その頂点の中間表現を計算することは無駄になる。 3

層別サンプリングのグラフ畳み込みネットワークへの適用 高速グラフ畳み込みネットワーク（FastGCN）はグラフ畳み込み ネットワークに層別サンプリングを適用する手法である。 グラフ畳み込みネットワークの層は p.134 (5.20) と表され，これをモンテカルロ近似すると p.134 (5.21) となるからこれを用いて集約を行う。 層別サンプリングは近傍サンプリングと異なり，頂点𝑣に隣接する 頂点の集合𝑁(𝑣)からではなく，グラフ全体の頂点の集合𝑉からサン プリングを行う。したがって，すべての頂点についてサンプリング の対象が同じなので，その結果を共有できる。 4

重点サンプリングを用いたサンプル効率の改善 高速グラフ畳み込みネットワークでは，以下の提案分布𝑞(𝑢)を用い て重点サンプリングを行う手法も提案されている。 p.125 (5.24) これを用ると，多くの頂点と隣接している頂点ほど高い確率でサン プリングすることになる。 重点サンプリングを用いた版の高速グラフ畳み込みネットワークで は，上の提案分布を用いてサンプリングした後，以下の式で集約を 行う。 p.134 (5.25) 5

層別サンプリングのまとめ p.133 アルゴリズム5.3 ● ● 層別サンプリングでは，各層が独立にサンプリングを行う。こ れをグラフ畳み込みネットワークに適用する場合は，グラフの 頂点全体の集合𝑉から（重点サンプリングを用いる場合は提案分 布を用いて）各層でサンプリングを行うことになる。 近傍サンプリングと異なり，隣接する頂点からサンプリングを 行わないことから，いくつかの欠点も生じるが，アルゴリズム の簡略化のおかげで計算が高速化される。 6

5.6 近傍サンプリングと層別サンプリングの組み合わせ 7

層別サンプリングと近傍サンプリングの組み合わせ LADIESは近傍サンプリングと層別サンプリングを組み合わせた手 法である。 層別サンプリングの候補を𝑉全体から𝐵𝑙＋1の近傍頂点に限定するこ とで無駄な計算が生じなくなる。 重点サンプリングの提案分布を𝐵𝑙＋1とのつながりの強さに基づいて p.136 (5.26) とすると，𝐵𝑙＋1に含まれる頂点の中間表現に寄与する頂点をより重 点的に選ぶことができる。 p.137 アルゴリズム5.4 8

5.7 訓練グラフの構成法 9

グラフニューラルネットワークの訓練の高速化 グラフニューラルネットワークの訓練を高速化するために，訓練用 のグラフ𝐺から別のグラフを再構築し，それを用いてグラフニュー ラルネットワークを訓練する。 訓練に用いるグラフを小さくすることで計算量とメモリ消費量を小 さく抑えることができる。 その訓練用のグラフを再構築する方法として以下の２つが紹介され ている。 ● ● クラスタグラフ畳み込みネットワーク GraphSAINT 10

クラスタグラフ畳み込みネットワーク クラスタグラフ畳み込みネットワークは入力グラフの頂点をクラス タリングすることで，訓練用のグラフを構成する手法である（クラ スタリングには既成の頂点クラスタリングアルゴリズムを用いる）。 得られた頂点クラスタの部分誘導グラフ（そのクラスタに属する頂 点を含むグラフの一部分をそのまま切り抜いたもの）を訓練用グラ フとして用いる。 同じクラスタ内の頂点どうしは密に接続されているため，クラスタ 内に限っても効果的なメッセージ伝達が行われる。また，クラスタ 外の頂点との接続を考慮しなくても，もとの（クラスタリングして 分割する前の）訓練用グラフ𝐺での予測とは大きく異ならない。 11

確率的多重分割 クラスタグラフ畳み込みネットワークでは，異なるクラスタ間にあ る辺も訓練に用いるために，確率的多重分割という手法も提案され ている。 確率的多重分割では訓練用グラフを細かいクラスタに分割して，そ の中から複数個のクラスタを選び，それらを足し合わせた集合に含 まれる頂点から誘導される部分誘導グラフを訓練用グラフとして用 いる。 𝑉1 例えば左のグラフを考えると，クラスタ𝑉1と 𝑉2が共に選ばれたならば，その間にある辺も 訓練に用いられる。 𝑉2 𝑉3 12

GraphSAINT GraphSAINTでは頂点の部分集合をランダムサンプリングやランダ ムウォークで構成し，それによって得られた頂点の部分集合で誘導 される部分誘導グラフを訓練に用いる。 GraphSAINTのグラフ構築方法はクラスタグラフ畳み込みネットワ ークより単純だが，同等以上の性能を達成することが報告されてい る。 GraphSAINTの方が多様なグラフを実現するので，正則化や汎化の 効果がある可能性がある。 13

GraphSAINT（補足） GraphSAINTではサンプリングの際に，以下の4つのサンプラーが 用いられている。これらのサンプラーによって選ばれた頂点・辺か ら誘導される部分誘導グラフを訓練に用いる。 ● ● ● ● Random node sampler Random edge sampler Random walk sampler Multi-dimensional random walk sampler 性能はRandom node samplerがそれ以外と比較して劣っている。 14

GraphSAINT（補足2） Random node samplerは下の確率分布に基づいて，次数の大きい 頂点を高い確率でサンプリングする。 これはFastGCNの層別サンプリングに影響を受けたらしい。 Random edge samplerでは下の確率分布に基づいて，次数の小さ い頂点の間の辺ほど高い確率でサンプリングする。 頂点𝑢，𝑣に隣接する頂点が少なく，なおかつその間に辺があると き，𝑢と𝑣は互いに大きな影響を与えていると考えられる。 15

GraphSAINT（補足3） Random walk samplerはランダムに選ばれた頂点から，指定され た長さのランダムウォークを行う（通常のランダムウォーク）。 Multi-dimensional random walk samplerは以下のアルゴリズム に従ってランダムウォークを行う。 16

GraphSAINT（補足4） Multi-dimensional random walk samplerは具体的に例えば以下 のようなことを行っている。 A E B C D 左のグラフを考えて，𝑉𝐹𝑆＝{𝐵, 𝐷}とする。𝑉𝐹𝑆から 𝐵が選ばれて，𝐵に隣接する頂点の中から𝐶が選ば れたとすると，𝑉𝐹𝑆＝{𝐶, 𝐷}，𝑉𝑠＝｛𝐵, 𝐷｝に更新 される。このとき𝐶はまだ𝑉𝑠に追加されず，その後 に𝑉𝐹𝑆から選ばれて初めて𝑉𝑠に追加される。最後に 𝑉𝑠に含まれる頂点から誘導される部分誘導グラフを 構成する。 [1907.04931] GraphSAINT: Graph Sampling Based Inductive Learning Method (arxiv.org) GraphSAINTについて詳細は[1907.04931] GraphSAINT: Graph Sampling Based Inductive Learning Method (arxiv.org)を参照。 [1907.04931] GraphSAINT: Graph Sampling Based Inductive Learning Method (arxiv.org) 17

• https://arxiv.org/abs/1907.04931

訓練用のグラフを構成する手法の利点 訓練用のグラフを構築する手法の場合，訓練用のグラフさえ構築す れば，通常のグラフに対する予測・訓練を行うだけなので，原理的 にはどのようなグラフニューラルネットワークにも組み合わせるこ とができ，加えて高速化に対応していないグラフニューラルネット ワークの実装をそのまま使うことができる。 この意味で，訓練用のグラフを構成する手法は近傍サンプリングや 層別サンプリングと比較して，汎用性が高い点・実装が容易である 点において優れていると言える。 18

5.8 応用例（PinSAGE） 19

PinSAGEとは何か PinSAGEはGraphSAGEをもとにして設計された，Pnterestのため に開発されたグラフニューラルネットワークを用いた推薦モデルで ある。 PinSAGEではピンとボードを頂点とするグラフを構築し，グラフ ニューラルネットワークを用いてピンの埋め込みを計算する。ピン 𝑖がボード𝑣にまとめられたとき，𝑖と𝑣の間に辺が張られる。 Pinterestではコンテンツ（写真など）をピン と呼び，その一覧表をボードと呼ぶ。 p.141 図5.3 20

重点プーリング PinSAGEの基本的な方針とアーキテクチャはGraphSAGEと同一だ が，PinSAGEでは近傍サンプリングを行わずに𝐾＝50個の近傍頂点 を以下の方法で選択し固定して用いる。 頂点𝑢からランダムウォークを何度か走らせ，訪れた頻度が高い上 ෩ 位𝐾個の頂点を𝑢の新しい近傍頂点𝑁(𝑢)と定義し，それぞれ訪れた 頻度で重み付けして（𝛼𝑢 ∈ ℝ𝑛 は訪れた頻度を正規化して和を1に したベクトル） p.141 (5.27) によって集約する。この機構を重点プーリングと呼ぶ。 21

重点プーリングの利点 重点プーリングには以下のような利点がある。 ● ● ● ● 多くの近傍を持つ頂点でも，集約する頂点の数は変わらず𝐾個で ある。したがって𝑂(𝐾)時間で集約できる。 頂点𝑢に関連がある重要な頂点の情報を重点的に集めることによ り，制度の向上が期待できる。 すべての頂点の次数が𝐾に均一化されるため，並列化しやすい。 近傍サンプリングと異なり，実行する度にサンプリングを行う 必要がない。 22

PinSAGEの訓練と計算 PinSAGEは以下で定義されるマージン損失を用いて，関連するピ ンの埋め込みが近くなるように訓練する。 p.142 (5.28) 訓練データ数が非常に多いため，複数のGPUを用いた並列化が導入 されている。また計算の際も各頂点の埋め込みを並列で求めること で，計算を高速化している。 各頂点の埋め込みさえ求めておけば，あるピンに対してその埋め込 みに近い埋め込みを持つ頂点を選ぶことで，関連のあるピンを推薦 できる。 23

24