【グラフニューラルネットワーク】2.1~2.2

2024前期輪読会#2 グラフニューラルネットワーク 2-1,2 京都大学工学部 木村優汰 0

グラフニューラルネットワーク 目次 1. ニューラルネットワーク 2. グラフ理論 1

2.1 ニューラルネットワーク 2

2.1.1 機械学習モデルの訓練と推論 機械学習モデル:fθで表す。（θがパラメータ） （ニューラルネットワークは機械学習モデルの種類） 推論（inference）:入力xに対して出力fθ(x)を求める操作 訓練（training）:適切なパラメータθを探す操作(=損失関数を小さくする操作) 訓練→推論 損失関数の最小化=精度の良いモデルの作成 損失関数を最小化するアルゴリズム:最適化アルゴリズム (SGD,Adam,etc) 3

2.1.2 多層パーセプトロン x1 y1 :活性化関数σ、x:入力 x2 z1 ・入出力ともにベクトル ・以下の式で定義 f(x) = σ(Wσ(Wσ(…Wσ(W(x)…)) W:重みを要素とする行列 ・繰り返し単位:層 ・線形変換と非線形変換を交互に行うモデル 4

2.1.3 畳み込みニューラルネットワーク 入力データ フィルタ 出力データ （３次元の畳み込み演算） 畳み込み層:以下の式で定義 (xは三階のテンソルとする) = (h:画像の高さ,w:幅,c:チャンネル数) W:フィルタ(カーネル) 5

2.1.3 畳み込みニューラルネットワーク 畳み込みニューラルネットワークの構造 入力 データ 入力 層 畳み込 み層 ブーリン グ層 全結合 入力層:特徴マップの作製 ブーリング層:特徴マップのサイズを小さくする 6

2.1.4 誤差逆伝播法と一気通貫学習 誤差逆伝播法:誤差の勾配を計算するアルゴリズム （勾配:パラメータの最適化に用いた） 利点:数値微分よりも効率的、精度が高い 計算コスト(一度の計算で求まる)、実装の容易性 一気通貫学習:中間ステップを挟まずに入力から望ましい出力を 一気に得る機械学習の手法 利点:ステップごとの個別の最適化よりも効率的 中間表現の必要性がないのでモデルがシンプルに表せる 7

2.2 グラフ理論 8

2.2.1 グラフの定義 V = {1,2,3,4,5} 2 E = {{1,2},{1,3},{2,3},{2,4},{2,5} 3 G = (V,E) 5 グラフとは? → 頂点（ノード）と辺（エッジ）で構成される データ構造のこと 1 4 グラフGは頂点集合Vと辺集合Eで定義 *辺{u,v}のうちu=vの場合の辺を自己ループという 9

2.2.2,3 近傍、次数 頂点vの近傍(neighborhood):vと辺を共有する頂点、N(v)で書く vとuが近傍＝uはvに隣接している 例えば、N(2) = {1,3,4,5} 頂点vの次数(degree):vに隣接する頂点の数,deg(v)で書く 例えば、deg(2)=4 次数行列:各頂点vについてdeg(v)を対角成分に並べた対角行列 Diag(deg(1),…,Deg(n)) 10

2.2.4 部分グラフ 部分グラフ:グラフの一部を取り出したグラフ G=(V,E)について、V’ V,E’ E,G’=(V’,E’)なるG’:部分グラフ 誘導部分グラフ:EのうちV’に属する頂点間の辺をすべて含む 部分グラフ 4 1 G 1 1 2 2 3 3 2 3 5 11

2.2.5 ウォークとパス ウォーク:辺をたどって作成した頂点の列 ex){1,3,1,2,4,2,5},{2,4,2,5,2,1,3} パス:頂点の重複がないウォークのこと ex){1,3,2,5} 12

2.2.6 連結性 連結グラフ:パスによってすべての頂点間を行き来できるグラフ 非連結グラフ:連結でないグラフ 連結成分:極大な連結部分グラフ 13

2.2.7 隣接行列と接続行列 隣接行列:各頂点間が辺で結ばれている時１それ以外の時０の行列 頂点同士の接続関係を表す 最短経路問題 接続行列:頂点iと辺jが接続している時１それ以外の時0の行列 頂点と辺の接続関係を表す グラフの辺の数 これらはグラフの行列による表現方法 14

2.2.8 重み付きグラフ 各辺が実数値を持つようなグラフ G = (V,E,w) w:辺に重みを与える関数 で定義 重み付き隣接行列（１の代わりに重みを要素とする行列）で表現 類似度行列との同一視 次数:近傍の重みの和 15

2.2.9 有向グラフ 有向グラフ:辺に向きをつけたグラフ (向きなし→無向グラフ) 無向グラフを一般化したグラフ Ex)Webページのリンク構造、交通ネットワーク 本書では基本無向グラフで考える 16

2.2.10 同類選好的グラフと異類選好的グラフ 同類選好:似た者同士が辺でつながる可能性が高い 異類選好:異なる者同士が辺でつながる可能性が高い 同類選好→ソーシャルネットワーク (コミュニティの形成) 異類選好→映画関係者同士のつながり 17

18

19