【グラフニューラルネットワーク】8.1~8.2

2024年度前期輪読会 グラフニューラルネットワーク8.1~8.2 GNNの表現能⼒とグラフの同型性検査 2024/7/4 栗林 雷旗 0

本⽇の流れ ⽬次 1. ニューラルネットワークの表現能⼒ 2. Weisfeiler-Lehman 検査のアルゴリズム 3. グラフ同型ネットワーク 1

仮説空間と表現能⼒ ● 仮説空間: 機械学習モデルで表現できる関数の集合 f 平⾏移動 任意の関数 g 拡⼤・縮⼩ 表現能⼒ 2

万能近似能⼒ ● ベクトルデータに対するニューラルネットワーク • ● 有界の定義域内において任意の連続関数を近似できる グラフニューラルネットワーク • • 万能近似能⼒をもたない 頂点埋め込みの出⼒は各点の特徴量に依存 3

GNNが抱える問題とアプローチ 問題 1. (⼈間から⾒て)単純な問題さえ本質的に解くことができない 2. どのような問題が解けて、どのような問題が解けないか不明 アプローチ ● GNNの表現能⼒を明確にし、かつ向上させる⼿法の探究 4

グラフの同型性とWeisfeiler-Lehman検査 グラフの同型性 ● 頂点番号の⼊れ替えだけで相互に変換可能なグラフ Weisfeiler-Lehman検査 ● グラフの同型性を近似的に判定する多項式アルゴリズム 5

Weisfeiler-Lehman検査の正当性 Weisfeiler-Lehman検査が出⼒する判定 ● 同型かもしれない ● 同型ではない 同型 判定 同型かもしれない ⾮同型 判定 同型かもしれない 判定 同型ではない 6

GNNにおいてWeisfeiler-Lehman検査が失敗するケース 集約関数: メッセージ伝達結果を1本のベクトルに集約 ● 単射な集約関数: Weisfeiler-Lehman検査と同等の識別能⼒ ● 単射でない集約関数: ベクトル集約時に情報の損失が発⽣ 1 W 2 X 3 Y 4 Z 単射 7

GNNにおいてWeisfeiler-Lehman検査が失敗するケース 集約関数: メッセージ伝達結果を1本のベクトルに集約 ● 単射な集約関数: Weisfeiler-Lehman検査と同等の識別能⼒ ● 単射でない集約関数: ベクトル集約時に情報の損失が発⽣ 1 W 2 X 3 5 Y 4 Z 単射でない 8

グラフ同型ネットワークとDeepSets DeepSets ● ベクトル集合を⼊⼒, 1本のベクトルを出⼒とする機械学習モデル グラフ同型ネットワーク ● 単写な集約関数を表現できるGNN ● 和により近傍の中間表現を集約 ● 多層パーセプトロンを⽤いて集約結果を変換 9

10