【グラフニューラルネットワーク】8.1~8.2
444 Views
July 08, 24
スライド概要
AI・機械学習を勉強したい学生たちが集まる、京都大学の自主ゼミサークルです。私たちのサークルに興味のある方はX(Twitter)をご覧ください！
関連スライド
各ページのテキスト
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