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

2024年度前期輪読会 #4 グラフニューラルネットワーク4.3 京都大学工学部情報学科 稲葉陽孔 1

解きたい問題 ● ● グラフ生成問題 入力：グラフの集合{𝐺1 , 𝐺2 ,…𝐺𝑛 } 出力：グラフ上の確率分布P(G)に従ってグラフを生成するモデル この問題に対して様々な生成モデルの枠組みが作られている。 しかし、それらのモデルには特有の問題点もある。 2

グラフ生成問題の解法 目次 1. 変分オートエンコーダー 2. 敵対的生成ネットワーク 3. 自己回帰モデル 4. 拡散モデル 3

1.変分オートエンコーダー 4

変分オートエンコーダー オートエンコーダー： エンコーダー(入力データから埋め込み表現を計算、f:X→Ｚ)と デコーダー(埋め込み表現からデータを復元、g:Ｚ→X)を訓練する手法。この時、g(f(x))=x´(∊X) とxの誤差が小さくなるように訓練する →複雑なデータxを埋め込みz∊Ｚによって簡潔に表現できる 変分オートエンコーダー： オートエンコーダーに埋め込みの確率分布(p(z))を課したもの この時、g(f(x))=x´(∊X)とxの再生成誤差だけでなくzがp(z)に従う度合いも最適化する ・欠点 ・入力データの頂点数が可変ゆえに、要素数が不変だった画像系の問題より難しい ・グラフデータの単語は単一の順序に並べられないので、この手法を使えない →これらを解決するのがGraphVAE 5

変分オートエンコーダー ・GraphVAE 従来の変分オートエンコーダーに加え、 頂点𝑖が存在する確率(𝑖 = 𝑗) とする 頂点𝑖と𝑗が連結している確率(𝑖 ≠ 𝑗) ・最大頂点数(K)を固定：𝑎𝑖𝑗 = ൝ 2 求め方{f:ℝK×K → ℝ𝐾 (エンコーダー)、g:ℝ𝐾 → ℝK×K (デコーダー)} AとA´の誤差から学習 2 1 1 0 0 1 1 1 1 0 0 A= 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 ∊ ℝK×K 入力 ＝ fでAからvec(A) ∊ ℝ𝐾 を出力 1 0 1 1 0 0 1 0 1 1 A´= 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 ∊ ℝK×K （出力)＝ gでvec(A)からA´ ∊ ℝK×K を出力 （図１） 2 6

変分オートエンコーダー 図１の学習法：AとA´は同型のグラフなのに、AとA´の誤差を２乗誤差で求めると０でなくなってしまう… だからといって頂点の並び替え方法n!通りをすべて試すと計算時間が足りない cho2014.pdf (ens.fr) →そこで頂点を近似的に配列する必要がある（ex.最大プーリングマッチング（cho2014.pdf (ens.fr) ）） 交差エントロピー損失を誤差として考える −1 𝐾 1 σ𝑖=1 𝐴𝑖𝑖 log 𝐴´𝑖𝑖 ― σ𝐾 σ 𝐴 log 𝐴´𝑖𝑗 𝐾 𝐾(𝐾−1) 𝑖=1 𝑗≠𝑖 𝑖𝑗 L(A, A´)＝ K:GraphVAEで定めた最大頂点数 A:入力データに対応した行列 A´:出力データに対応した行列 7

• https://www.di.ens.fr/willow/pdfscurrent/cho2014.pdf

2.敵対的生成ネットワーク 8

敵対的生成ネットワーク 生成器 f:Z→X と識別器 g:X→Z の２つのモデルを組み合わせた手法(Z:変数,X:グラフ) 生成器：潜在変数（ノイズ）を受け取り、グラフを生成する 識別器：グラフが本物か見極め、正負で出力（値が大きいほど本物だと認識している） 学習： 生成器が本物と似たグラフを作る→識別器も真偽を学習 →生成器も本物と似たグラフ作りを学習…といったサイクル 欠点：グラフの頂点数が可変→MolGANを使う 9

変分オートエンコーダー ・MolGAN 基本的にGraphVAE と同様、「最大頂点数を固定」、「隣接行列を出力するものを生成器に用いる」 →こうすることで、一般的にGraphVAEの時のように頂点を並べ替える必要がなくなる （∵識別器として一般的に使われるGNNの動作は頂点の並び替えに依存しない（定理3.4参照）） 損失関数：WGANの損失関数 ℙg ：生成器が作ったグラフの確率分布 ℙ𝑟 ：本物のグラフの確率分布 D(x):グラフｘを入力データとした際の、識別器による出力値 用語集 E[x]：xの期待値 x~Ｐ(x):xが確率分布P(x)に従って分布する 10

3.自己回帰モデル 11

自己回帰モデル データをx=𝑥1 𝑥2 … 𝑥𝑖 というように列で分解し、xから続く𝑥𝑖+1 を予測し、その後に続く𝑥𝑖+2 を予測… を繰り返すことで全データを生成するモデル（言語系の予測に用いられる） →しかし、グラフデータには順序がなく、出力する順序が定まらない→そこでGraphRNN ・GraphRNN グラフの頂点に一様ランダムに番号を振り、頂点{1,2}の間に辺があるか、頂点{1,3}の間に辺 があるか…というように辺の有無を表す2値変数をRNNで順番に出力する 利点： ・あらかじめ頂点数の上限を決める必要がない ・番号付け自体を確率変数とすることで頂点番号を整列する処理が(明示的には)必要ない 欠点： ・頂点数をnととすれば番号付けはn!通り考えられ、すべて考えるのは膨大すぎる 12

自己回帰モデル この欠点を解消するため、番号付けの正規化を行う 具体例 １.一様ランダムに番号を振る ２．頂点１を始点に、番号の小さい隣接点(未到達)を 優先的にたどる 2 5 4 3 1 3.訪れた順に番号を振る 4.2~3を繰り返す 利点：番号付けの多様性を削減しながら 同型グラフを増やせる (1つのみだと訓練の過程が同変でなくなり、 2 5 似たグラフも番号付けが違えば異なるグラフ として扱ってしまう) １ 4 3 13

4.拡散モデル 14

拡散モデル データ分布P(𝑥0 )にノイズを加え、 P(𝑥1 )に変換する過程を用いた生成モデル 𝑥𝑡𝑛+1 ………… 𝑥𝑡0 𝑥𝑡𝑛 ………… :ノイズ付与(順過程) :ノイズ除去(逆過程) 元データ: 𝑥0 = 𝑥𝑡0 ~ P(𝑥0 ) ノイズを加えたデータ：𝑥𝑡1 , 𝑥𝑡2 ,…=𝑥1 ~ P(𝑥1 ) 学習：1. によって元データにノイズ𝜀𝑡0 , 𝜀𝑡1 , …を順次加える 2. 「 によって受け取った情報{𝑥𝑡𝑖+1 , 𝑡𝑖+1 }から、1.で与えられたノイズを 予測(予測値: 𝜀´𝑡𝑖 )し、 𝑥𝑡𝑖 を予測する…」を繰り返す 3. 𝜀𝑡𝑖 と{𝜀´𝑡𝑖 }の誤差(i=0,…n)を計算し、それを元にノイズ除去器が学習 15

拡散モデル Niuの拡散モデル（n頂点無向グラフの作成） グラフを隣接行列A0 ∊ ℝ𝑛×𝑛 として表現 順過程：隣接行列に、正規分布に従うノイズ分布ε ∊ ℝ𝑛×𝑛 を足す 逆過程：特殊なグラフニューラルネットワークを用いることで順過程で加えたε ∊ ℝ𝑛×𝑛 を予測し、 元の隣接行列を予測 これらの過程を繰り返すことでデータを生成 Joの拡散モデル(頂点特徴量を持つグラフの作成) データを隣接行列A0 ∊ ℝ𝑛×𝑛 と特徴行列X0 ∊ ℝ𝑛×𝑛 の組で表現 ノイズが付与されたグラフ(A𝑡 , 𝑋𝑡 )から、隣接行列と特徴行列それぞれに付与されたノイズ量を予測 16

生成モデルの応用場面 17

生成モデルの応用場面 変分オートエンコーダー 敵対的生成ネットワーク （による生成モデル） 分子構造の最適化、創薬 グラフ上の最適化問題をベクトルの最適化問題に帰着 目的関数値の高いグラフの生成 MolGAN・ORGAN (こういった生成に関しての訓練を施すことで、 薬らしさや水溶性などの指標を作成) 18

19