---
title: 【グラフニューラルネットワーク】2.3
tags: 
author: [京都大学人工知能研究会KaiRA](https://convert.docswell.com/user/kyoto-kaira)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/G7WDGQYZE2.jpg?width=480
description: 【グラフニューラルネットワーク】2.3 by 京都大学人工知能研究会KaiRA
published: May 09, 24
canonical: https://convert.docswell.com/s/kyoto-kaira/K7VWLN-2024-05-09-230328
---
# Page. 1

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

グラフニューラルネットワーク第２章３節
古典的なグラフ機械学習⼿法
京都⼤学医学研究科
M1
⼩林侑⼤
0


# Page. 2

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

2.古典的なグラフ機械学習⼿法
⽬次
1. ラベル伝搬法ー転導的頂点⼆値分類問題
2. ⾏列分解
3. Deep Walk
1


# Page. 3

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

2.3 古典的なグラフ機械学習⼿法
2.3.1ラベル伝搬法
転導的頂点⼆値分類問題
𝑉# :ラベル既知頂点
𝑉! :ラベル未知頂点
0
1 𝑤
(
?
𝑤&#039;
𝑤$
0
?
𝑤 -
予測
%
𝑤&amp;
?
0 or 1
•
重みは類似度を表す。
•
⽬的は類似度をもとに頂点のラベル
るを予測すること。
→例えば、𝑤! が⼤きい場合、
?&quot; を 0と予測できれば良い
⼊⼒︓重み付きグラフ ( 𝐺 = 𝑉, 𝐸, 𝑤 )
出⼒︓教師ラベルの付いていない頂点 𝑉!
について、ラベルの推定値 )
𝑦&quot; (0か1) を求める。
2


# Page. 4

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

2.3 古典的なグラフ機械学習⼿法
2.3.1 ラベル伝搬法
解くべき最適化問題
求めたい
0
1𝑊
𝑊$%
$)
?
𝑊$(
0
𝑊$&amp;
?
•
(𝒇 ∈ ℝ# )
は頂点のラベルの推定値を表すベクトル
•
予測値は、𝒇𝒗 ≥ 0.5であれば ,
𝑦% = 1 と
し、𝒇𝒗 &lt; 0.5であれば ,
𝑦% = 0 とする。
•
類似度が⼤きい頂点が重要視される
•
類似度が⼤きい頂点同⼠は同じラベル
になる。
𝑊$&#039;
?
3


# Page. 5

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

2.3 古典的なグラフ機械学習⼿法
2.3.1 ラベル伝搬法
ラベル伝搬法の解
⽬的関数の最⼩値を求めれば良いので、⽬的関数を
𝑓&amp; について偏微分して
未知
既知
頂点のラベルの推定値で未知のものの集合𝑓&#039; を 、
既知のものの集合 𝑓( だけで表せた︕
勾配の式を0で解くと最終的に式(2.28)のように解
ける。
4


# Page. 6

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

2.3 古典的なグラフ機械学習⼿法
2.3.1 ラベル伝搬法
ランダムウォークを⽤いた解釈
ラベル伝搬法の解𝑓% は頂点𝑣から初めて訪れた教師
付きラベルが１である確率𝑞% ∈ 0,1 と⼀致する。
0
𝑣
𝑊%)
deg 𝑣
𝑢
•
類似度が⼤きい辺ほど⾼い確
率で渡っていく。
•
deg 𝑣 は頂点(𝑣)
に接続しているエッジの重みの合計
•
ラベル伝搬法は近くにある頂
点同⼠が同じラベルになるよ
うに分類される。
•
式(2.30)と式(2.25)は等価
𝑞と𝑓も⼀致。
0
𝑣 𝑞&quot;
0
1
1
5


# Page. 7

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

2.3 古典的なグラフ機械学習⼿法
2.3.2 ⾏列分解
教師なし頂点表現学習問題
•
埋め込み(embedding)︓デ
ータの情報を低次元のベクト
ルとして表現したもの
•
表現学習︓埋め込みを学習す
る
•
重み付きグラフの接続⾏列
𝐵&amp;* は頂点の埋め込みになっ
ている。
頂点の埋め込み Z&quot; ∈ ℝ,
𝑣
𝑢
頂点の埋め込み Z- ∈ ℝ,
𝑍-. Z&quot; → 辺uvの構造の情報
𝑍&quot;. Z&quot; → 頂点vの構造の情報
みたいに表せたら嬉しい。
⼊⼒︓重み付きグラフ ( 𝐺 = 𝑉, 𝐸, 𝑤 )
出⼒︓グラフ構造を考慮した頂点の埋め込みZ ∈ ℝ*×,
6


# Page. 8

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

2.3 古典的なグラフ機械学習⼿法
2.3.2 ⾏列分解
教師なし頂点表現学習問題
解くべき最適化問題
•
この問題ではスペクトル分
解と特異値分解どちらでも
同じ解となる
•
分かりやすそうなサイト
グラフの構造の情報と頂点の埋め込みの積を近づけていく
このような問題は⾏列分解により解くことができる。
•
・スペクトル分解→固有値を利⽤した分解
・特異値分解→特異値を利⽤した分解
この問題の解↓
•
スペクトル分解
https://qiita.com/jamojisan/ite
ms/b8f7a7e9b44fc3e2e41c
特異値分解︓
https://qiita.com/kidaufo/items/
0f3da4ca4e19dc0e987e
7


# Page. 9

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

2.3 古典的なグラフ機械学習⼿法
2.3.2 ⾏列分解
トピック推定
⽂書と単語の関係性を埋め込む
解くべき最適化問題
⼊⼒： 単語の集合 {𝑤$ , 𝑤% , … , 𝑤/ }
出⼒︓各⽂書 𝑡0 のトピックの割当変量 𝑈0 ∈ ℝ, (𝑖 ∈ 𝑇 )
各単語 𝑤0 のトピックの割当変量 𝑉0 ∈ ℝ, (𝑖 ∈ 𝑊 )
𝑋&amp; ∈ ℝ+ は𝑏𝑎𝑔 𝑜𝑓 𝑤𝑜𝑟𝑑𝑠といい、𝑋&amp;* ∈ ℝは
⽂書𝑡&amp; 中に単語𝑤* が出現する回数を表す。
この最適化問題は特異値分解で解くことができ、この
ような解析⼿法を潜在意味解析という。
8


# Page. 10

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

2.3 古典的なグラフ機械学習⼿法
2.3.2 ⾏列分解
映画推薦問題
解くべき最適化問題
⼊⼒： ユーザーの映画の評価履歴 {(𝑢0 , 𝑣1 , 𝑟01 )}
出⼒︓各ユーザーに対するおすすめの映画
ユーザーと映画の埋め込みを計算した後は、各ユーザ
ー𝑢&amp; が未評価の映画𝑣* につけるであろう評価値を
,
𝑟&amp;* = 𝑈&amp;, 𝑉&amp; として推定することができる。
この評価値が最も⾼い未評価の映画をユーザー 𝑢&amp; に推
薦する。
このように傾向の似た他のユーザーの消費した品⽬に
基づいて推薦を⾏う技法を協調フィルタリングという
9


# Page. 11

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

2.3 古典的なグラフ機械学習⼿法
2.3.3 Deep Walk
教師なし頂点表現学習問題
A
⼊⼒︓重み付きグラフ ( 𝐺 = 𝑉, 𝐸, 𝑤 )
出⼒︓グラフ構造を考慮した頂点の埋め込みZ ∈ ℝ*×,
A
B
B
C
C
D
頂点𝑢の周辺という条件のもとでの頂点𝑣の出現確率を
𝑝∗(𝑣|𝑢)とあらわす。
F
G
F
G
E
E
ランダムウォーク：
モデルのもとで、頂点𝑣が頂点𝑢の周囲い登場する確率を
D
A
私
C
の
F
名前
E
は
Aの周辺
と定義する。うまく学習できると、頂点𝑣と頂点𝑢の類似
度がわかる︕
10


# Page. 12

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

2.3 古典的なグラフ機械学習⼿法
2.3.3 Deep Walk
教師なし頂点表現学習問題
最⼤化する⽬的関数
真の頂点𝑢周辺の頂点𝑣の出現確率と予測した頂点𝑢周辺の頂点𝑣の出現確率を近づけていく
•
KLはカルバック・ライブラ
ー情報量 (Kullback-Leibler
divegrence) であり、⾮負
で2つの確率分布が等しいか
つその時のみ０となる。簡
単⾔えば、2つの確率分布の
距離のような意味を持つ。
最適化の⼿法は確率的勾配向上法を⽤いて⾏う
このままでは、(2.57)の分⺟の計算が⼤変なので、そ
れを避けるための⽅法としてネガティブサンプリング
が紹介されていた。
11


