Semi-Supervised Classification with Graph Convolutional Networks 基于圖卷積網(wǎng)絡(luò)的半監(jiān)督分類
原文：https://arxiv.org/abs/1609.02907
參考：https://blog.csdn.net/w986284086/article/details/80270653
DGL 實(shí)現(xiàn)：https://docs.dgl.ai/tutorials/models/1_gnn/1_gcn.html
DGL 實(shí)現(xiàn)（ZACHARY空手道俱樂(lè)部網(wǎng)絡(luò)）: https://docs.dgl.ai/tutorials/basics/1_first.html
Graph and “Zachary’s karate club” problem
圖的基本概念
- 頂點(diǎn)（vertex）
- 邊（edge）
- 有向/無(wú)向圖（Directed Graph / Undirected Graph）
- 邊的權(quán)重（weight）
- 路徑/最短路徑（path / shortest path）
空手道俱樂(lè)部數(shù)據(jù)集
- 頂點(diǎn)：一個(gè)俱樂(lè)部成員
- 邊：成員之間在俱樂(lè)部以外的關(guān)系
- 無(wú)向忆畅，所有權(quán)重相同
- 問(wèn)題：以教練（0）和主席（33）兩個(gè)人為首衡未，將整個(gè)俱樂(lè)部分為兩個(gè)派別
對(duì)一個(gè)節(jié)點(diǎn)的卷積
-
與某節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)，對(duì)所有特征向量求和橄镜，表示為：
-
線性+非線性變換：
Graph Attention Networks 圖注意力網(wǎng)絡(luò)
原文：https://arxiv.org/abs/1710.10903
參考：https://www.cnblogs.com/chaoran/p/9720708.html
參考：https://www.cnblogs.com/wangxiaocvpr/p/7889307.html
參考：https://blog.csdn.net/b224618/article/details/81407969
DGL 實(shí)現(xiàn)：https://github.com/dmlc/dgl/tree/master/examples/pytorch/gat
線性變換
所有 node 共用一個(gè) W 作 feature 的線性變換，變換后 F 和 F‘ 可以不同
N 為node 數(shù)量, F 為每個(gè)node 的 feature 數(shù)（feature vector 長(zhǎng)度）
-
輸入：
-
輸出：
計(jì)算 attention coefficients
表示 node j 的 feature 對(duì) node i 的重要性：
函數(shù)a：一個(gè)單層前饋網(wǎng)絡(luò)
torch.bmm(head_ft, self.attn_l)
卷積
多頭注意力
設(shè)置 K 個(gè)函數(shù)梗搅，計(jì)算出 K 組attention coefficient禾唁，連接K個(gè)輸出：
對(duì)于最后一個(gè)卷積層，連接改為求平均：
Modeling Relational Data with Graph Convolutional Networks
原文：https://arxiv.org/abs/1703.06103
參考：https://lanzhuzhu.github.io/2017/04/30/IE/RelationExtraction/Modeling%20Relational%20Datawith%20Graph%20Convolutional%20Networks/
DGL 實(shí)現(xiàn)：https://docs.dgl.ai/tutorials/models/1_gnn/4_rgcn.html
普通GCN（本文第一種）利用圖的結(jié)構(gòu)來(lái)提取每個(gè)節(jié)點(diǎn)的特征无切，沒(méi)有利用圖的邊荡短。知識(shí)圖譜以三元組（主體、客體和主客體之間的關(guān)系）為單位組成哆键，因此圖的邊編碼了重要的關(guān)系信息掘托。而且每對(duì)節(jié)點(diǎn)之間可能存在多條邊（對(duì)應(yīng)多種關(guān)系）。
在統(tǒng)計(jì)關(guān)系學(xué)習(xí)（statistical relational learning, SRL）中籍嘹，有兩種任務(wù)闪盔，都需要從圖的相鄰結(jié)構(gòu)中恢復(fù)丟失的信息：
- 實(shí)體分類（Entity classification），例如將實(shí)體分為某種類別辱士，并賦予該類別中的一些特征
- 連接預(yù)測(cè)（Link prediction）泪掀，例如推斷某個(gè)缺失的三元組
例如知道了“小明在北京大學(xué)讀書(shū)”，就能知道“小明”應(yīng)該被歸類為“人類”颂碘，而且知識(shí)圖譜中一定有（小明异赫，住在，中國(guó)）這樣一個(gè)三元組凭涂。
R-GCN用一個(gè)圖卷積網(wǎng)絡(luò)同時(shí)解決了上述兩種問(wèn)題：
- 實(shí)體分類：每個(gè)節(jié)點(diǎn)最后使用softmax輸出
- 連接預(yù)測(cè)：利用自編碼器結(jié)構(gòu)重建圖的邊
回憶一下祝辣，普通GCN的卷積操作如下：
R-GCN的卷積操作如下：
其區(qū)別在于R-GCN中，通往一個(gè)節(jié)點(diǎn)的不同邊可以代表不同的關(guān)系切油。在普通GCN中蝙斜，所有邊共享相同的權(quán)重 W ；在R-GCN中澎胡，不同類型的邊（關(guān)系）使用不同的權(quán)重 Wr 孕荠，只有同一種邊（關(guān)系）才會(huì)使用同一個(gè)權(quán)重娩鹉。
“不同關(guān)系對(duì)應(yīng)不同權(quán)重”的做法大大增加了模型的參數(shù)量，原文使用了基分解（basis decomposition）來(lái)降低參數(shù)量和防止過(guò)擬合：
此處的 V 為基稚伍， a 為coefficient弯予，基的數(shù)目 B 遠(yuǎn)小于數(shù)據(jù)中的關(guān)系數(shù)目
Supervised Community Detection with Line Graph Neural Networks
原文：https://arxiv.org/abs/1705.08415
DGL 實(shí)現(xiàn)：https://docs.dgl.ai/tutorials/models/1_gnn/6_line_graph.html
開(kāi)頭的GCN完成了對(duì)每個(gè)節(jié)點(diǎn)的分類，這里的LGNN則是對(duì)圖中的節(jié)點(diǎn)進(jìn)行聚類（“社區(qū)發(fā)現(xiàn)”个曙，community detection）锈嫩。這個(gè)模型的一個(gè)亮點(diǎn)在于將普通GCN應(yīng)用在線圖（line graph）中
CORA：科技論文數(shù)據(jù)集
- 節(jié)點(diǎn)：2708篇論文，分為7個(gè)不同機(jī)器學(xué)習(xí)領(lǐng)域
- 有向邊：論文之間的引用關(guān)系
-
問(wèn)題：通過(guò)監(jiān)督學(xué)習(xí)對(duì)論文進(jìn)行分類
線圖
將一個(gè)老圖的邊垦搬，作為一個(gè)新圖的節(jié)點(diǎn)呼寸，畫(huà)出來(lái)的圖。下圖中的藍(lán)點(diǎn)和黑線是一個(gè)老有向圖猴贰，紅點(diǎn)既是老圖的邊对雪、也是新圖的節(jié)點(diǎn)。將相鄰的紅點(diǎn)按老邊的方向有方向地連起來(lái)米绕，就得到一個(gè)線圖瑟捣。
LGNN（這里的計(jì)算我沒(méi)有看懂）
在LGNN中有若干層，每一層的圖（x）和其線圖（y）在數(shù)據(jù)流中的變化過(guò)程如下圖：
在圖表征（x）中栅干，第 k 層迈套、第 l 個(gè)通道的第 i 個(gè)節(jié)點(diǎn)按以下公式進(jìn)行 k+1 層的更新：
類似地，線圖（y）中的運(yùn)算為：
等號(hào)的右邊可分為五部分：
-
x的線性變換
-
a linear projection of degree operator ( linear map D:F→DF where (Dx)i:=deg(i)·xi, D(x) =diag(A1)x .)on x,
-
a summation of 2j adjacency operator (linear map given by the adjacency matrix Ai,j= 1if f(i,j)∈E.) on x
-
fusing another graph’s embedding information using incidence matrix {Pm,Pd}, followed with a linear projection
-
skip-connection：將前面的非線性函數(shù)ρ換為線性變換
Stochastic Steady-state Embedding (SSE)
原文：http://proceedings.mlr.press/v80/dai18a/dai18a.pdf
DGL 實(shí)現(xiàn)：https://docs.dgl.ai/tutorials/models/1_gnn/8_sse_mx.html
Flood-fill / Infection algorithm（Steady-state algorithms）
在圖 G=(V,E) 中非驮，有 起始節(jié)點(diǎn) s ∈ V交汤，
設(shè) V = {1,...,n}，yv 為節(jié)點(diǎn) v 是否被標(biāo)記劫笙，N(v) 為 v 的所有相鄰節(jié)點(diǎn)（包括v本身）
對(duì)圖中可以到達(dá) s 的所有節(jié)點(diǎn)進(jìn)行標(biāo)記：
當(dāng)（2）迭代足夠次數(shù)后芙扎，所有可以到達(dá) s 的節(jié)點(diǎn)都被標(biāo)記，我們說(shuō)達(dá)到了穩(wěn)態(tài)（steady state）
Steady-state operator
上述過(guò)程可抽象為：
其中
在 flood-fill 算法中填大，T^=max
因?yàn)楫?dāng)且僅當(dāng) y?=T(y?) 時(shí)戒洼，y 在 T 下達(dá)到穩(wěn)態(tài)，所以稱 T 為 steady-state operator
Neural flood-fill algorithm（Steady-state embedding）
用神經(jīng)網(wǎng)絡(luò)模擬 flood-fill algorithm
- 用圖神經(jīng)網(wǎng)絡(luò) TΘ ,來(lái)代替 T
- 用向量 hv（維度為H）允华，來(lái)代替 布爾值yv
- 為節(jié)點(diǎn) v 賦予一個(gè)特征向量 xv（在 flood-fill 算法中圈浇，xv為每個(gè)節(jié)點(diǎn)編號(hào)的 one-hot code，用于區(qū)分不同節(jié)點(diǎn)）
- 只迭代有限次數(shù)靴寂，不一定達(dá)到穩(wěn)態(tài)
- 迭代結(jié)束后磷蜀，以 hv 為輸入，每個(gè)節(jié)點(diǎn)可以被到達(dá)的概率為輸出百炬，訓(xùn)練另一個(gè)神經(jīng)網(wǎng)絡(luò)
