【グラフニューラルネットワーク】8.7~8.8

節：動的計画法との整合性

GNN8.7

動的計画法は，シンプルな部分問題に分割し，その解を再利用して全体の解を求める
フィボナッチ数列を例に
普通に再帰で書く場合
def fibonacci(n):
if n <= 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

法も，動的計画法である 単一始点最短経路問題 ある始点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

• https://qiita.com/wakimiko/items/69b86627bea0e8fe29d5