---
title: 【グラフニューラルネットワーク】8.7~8.8
tags: 
author: [京都大学人工知能研究会KaiRA](https://convert.docswell.com/user/kyoto-kaira)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/87DYVQXW7G.jpg?width=480
description: 【グラフニューラルネットワーク】8.7~8.8 by 京都大学人工知能研究会KaiRA
published: July 12, 24
canonical: https://convert.docswell.com/s/kyoto-kaira/KWWE1X-2024-07-12-124839
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/87DYVQXW7G.jpg)

節：動的計画法との整合性
GNN8.7
動的計画法は，シンプルな部分問題に分割し，その解を再利用して全体の解を求める
フィボナッチ数列を例に
普通に再帰で書く場合
def fibonacci(n):
if n &lt;= 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
動的計画法の場合
def fibonacci(n):
fib = [1, 1]
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
return fib[n]
メッセージ伝達型GNNは，動的計画法である
集約 (h(l)
(l)
= fθ,l+1
h(l+1)
v
v , {{hv ∣ u ∈ N (v)}})
​
​
​
​
前の層の中間表現を利用して，次の層の中間表現を計算している
ラベル伝播法（ランダムウォーク近似）も，動的計画法である
ラベル伝播法
一部の頂点に教師ラベルが付いており，ラベルが付いていない残りの頂点のラベルを予測したい
ラベル伝播法はランダムウォークで解釈可能
解fv ﻿は，頂点v﻿からランダムウォークを始めて，初めて訪れた教師ラベル付き頂点のラベルが1である確率qv ﻿と一致する．
​
​
動的計画法で定式化
(l)
qv :=﻿（頂点v﻿からl ﻿歩以内でラベル付き頂点を訪れる確率，初めて訪れたラベル付き頂点が正例である確率）と定義する
初期値は
​
(1, yv ) if v ∈ VL
q(0)
v ={
(0, 0.5) if v ∈ VU
​
​
​
​
​
漸化式は（v ∈ VU のとき）
(l+1)
qv,1
​
= ∑
u∈N (v)
(l+1)
qv,2
​
=
Wvu (l)
q
deg(v) u,1
​
​
​
​
1
Wvu (l) (l)
∑
qu,1 qu,2
(l+1)
deg(v)
qv,1 u∈N (v)
​
​
​
​
​
​
​
節：動的計画法との整合性
GNN8.7
1


# Page. 2

![Page Image](https://bcdn.docswell.com/page/VJP6VLPXE8.jpg)

法も，動的計画法である
単一始点最短経路問題
ある始点s ∈ V ﻿から任意の頂点v ∈ V ﻿までの最短経路長dv ﻿を求めたい
Bellman-Ford法とは
Bellman–Ford
​
https://qiita.com/wakimiko/items/69b86627bea0e8fe29d5
漸化式で書くと
0 if v = s
d(0)
v ={
∞ if v 
=s
​
​
(l)
d(l+1)
= min (d(l)
v
v , min (du + Wvu ))
​
​
​
​
​
u∈N (v)
アルゴリズム整列性があると，GNNの学習効率が良い
機械学習モデルf ﻿とアルゴリズムg﻿が次のような合成で表せて，各部分モデルfi ﻿が部分アルゴリズムgi ﻿を効率的に学習できるとき，ア
ルゴリズム整列性があるという．
​
f = fL ∘ fL−1 ∘ ⋯ ∘ f1
g = gL ∘ gL−1 ∘ ⋯ ∘ g1
​
​
​
​
​
​
​
​
つのモデルで複雑な手続きをEnd-to-Endで表現するのは難しい
シンプルな部分アルゴリズムならモデル表現は比較的容易
➡︎
学習しやすい
まずは単純なGNNを使用してみよう
「近傍の頂点を重視する」というシンプルな規則が制度向上に寄与することが多い
やたら表現力の高いモデルを使っても，以下のような問題が生じる
過学習しやすい
計算量，メモリ消費量が大きい → 実装・保守のコスト高い
単純なモデルから始めよう
SGC：単純グラフ畳み込み（3.2.4節[P.79~]）
GAT：グラフ注意ネットワーク（3.2.2節[P.76~]）
GIN：グラフ同型ネットワーク（3.2.3節[P.263~]）
ただし，表現能力が重要となる場面もある
グラフ頂点数が少なく，多くの対称性を持つグラフ
ex）化合物グラフ
より大きな表現力が必要
「近傍の頂点を重視する」規則があまり効かない
対処法 ：表現力の高いモデルを使う
対処法 ：乱択特徴量
学習データが非常に多い場合
近年の大規模学習の成功例のように，GNNでもうまく行くかも？
1
1
2
節：動的計画法との整合性
GNN8.7
2


