作者簡介：

吳天龍 香儂科技researcher

作者公眾號（suanfarensheng）

其它機器學習、深度學習

演算法的全面系統講解可以閱讀《機器學習與應用》，清華大學出版社，雷明著，由SIGAI公眾號作者傾力打造，自2019年1月出版以來已重印3次。

  • 書的購買鏈接
  • 書的勘誤，優化，源代碼資源

導言

圖(graph)是一個非常常用的數據結構，現實世界中很多很多任務可以描述為圖問題，比如社交網路，蛋白體結構，交通路網數據，以及很火的知識圖譜

等，甚至規則網格結構數據(如圖像，視頻等)也是圖數據的一種特殊形式，因此圖是一個很值得研究的領域。

針對graph的研究可以分為三類：

1.經典的graph演算法，如生成樹演算法，最短路徑演算法，複雜一點的二分圖匹配，費用流問題等等；

2.概率圖模型，將條件概率表達為圖結構，並進一步挖掘，典型的有條件隨機場等

3.圖神經網路，研究圖結構數據挖掘

的問題，典型的有Graph Embedding，Graph CNN等。

本文主要針對圖神經網路，介紹一些最近幾年該領域的一些研究進展。由於應用很廣泛(主要是社交網路發展和知識圖譜的推動)，以及受到深度學習在其他領域成功的啟示，這個方向是目前機器學習領域最火的方向之一了，KDD2018中31篇tutorials裡面有9篇是關於graph的，bestpaper也是關於graph的，論文名字叫做：adversarial attacks onclassification models for graphs. 可見學術界和工業界的熱情。

本文首先介紹Graph Embedding，為結構化的graph生成分散式表示；然後介紹Graph Convolutional Network(圖卷積)，接著簡單介紹基於圖的序列建模，最後簡要總結了下GNN在各個領域的一些應用。

Graph Embedding

Graph embedding(GE)也叫做network embedding(NE)也叫做Graph representation learning(GRL),或者network representation learning(NRL),最近有篇文章把graph和network區分開來了，說graph一般表示抽象的圖比如知識圖譜，network表示實體構成的圖例如社交網路， 我覺得有點過分區分了。圖1.1是整個GE大家族，本文只介紹綠色的，藍色模型就不一一介紹了。嚴格來說，圖卷積也屬於GE的一部分，由於目標不同以及其關注度較大，我們單獨劃分出來(文章第二部分)

圖1.1 Graph Embedding大家族

WHAT & WHY

首先我們回答什麼是embedding,以及為什麼要做embedding。

WHAT?

  • Embedding在數學上是一-個函數，f : X- > Y,即將一個空間的點映射到另一個空間，通常是從高維抽象的空間映射到低維具象的空間;
  • 一般映射到低維空間的表示具有分散式稠密表示的特性；

WHY?

  • 抽象的事物應該有一個低維的表示;比如我們看到一張含有一張小狗的圖片，它底層的表示就是像素值。同樣的我們看到"dog」這個單詞時，它也應該有更低維的表示
  • 計算機和神經網路善於處理低緯度信息
  • 解決one-hot編碼問題; one-hot編碼是一 種特殊的高維到低維的映射，具有稀疏性，且向量長度較長並隨著樣本集變化而變化。one-hot編碼是一種」討巧」的編碼方式，一般無法表示兩個實體之間的相關性，embedding可以一定程度上解決這些問題。

Word2vec

Word2vec[2013]：Distributed Representations of Words and Phrases and their Compositionality

Word2vec是根據語料庫中單詞的共現關係求出每個單詞的embedding。常用word2vec模型有cbow和skip-gram,cbow根據上下文預測中心詞，skip-gram根據中心詞預測上下文。由於兩種模型相似，本節只介紹skip-gram模型。

圖1.2 skip-gram模型

Word2vec本質是一個輸入不確定的softmax回歸。普通的softmax回歸輸入是確定的，我們需要求出參數矩陣，而word2vec中，輸入的向量和參數矩陣都是不確定的，並且輸入向量才是我們真正需要的，參數矩陣則是副產品。普通的softmax回歸是一個凸優化問題，然後word2vec由於輸入不確定不是一個凸優化問題，需要採取類似於坐標上升的優化方法。

由於以下兩個原因：

1.一般來說語料庫單詞都是很多的，計算會非常長龐大。

2.正負樣本極度不均衡。

一般不直接優化圖1.1的表達式，有一些優化，比如分層softmax和負採樣，一般來說現在最常用的是skip-gram+負採樣。

這裡提示一下，一般來說遇到配分函數的計算都需要優化，優化方法一般采 用雜訊對比估計(Noise Contrastive Estimation, NCE)，負採樣(Negative Sampling)技術是NCE的一種特殊形式，後面我們會經常用到這個trick，負採樣的一般表達式如公式1.1，其中 ilde{p}(x) 是真實樣本分布， U(x) 是某個」均勻」分布或者其他的、確定的、方便採樣的分布，說白了，NCE的做法就是將它轉化為二分類問題，將真實樣本判為1,從另一個分布採樣的樣本判為0。公式1.2是word2vec應用的負採樣公式，即語料出現的Skip Gram視為正樣本，隨機採樣的詞作為負樣本。關於NCE優化等價於直接優化softmax回歸的數學證明詳見「NCE等價於softmax回歸的證明」

mathbb{E}_{oldsymbol{z} sim ilde{p}(oldsymbol{x})} log (oldsymbol{p}(mathbf{1} | oldsymbol{x}))+mathbb{E}_{oldsymbol{z} sim U(oldsymbol{z})} log (p(mathbf{p} | oldsymbol{x}))（1.1）

mathbb{E}_{w_{j} sim ilde{p}left(w_{j} | w_{i} ight)} log left(<u_{i}, v_{j}><br /> ight)+mathbb{E}_{x ilde{p}left(w_{j}<br /> ight)} log left(1-<u_{i}, v_{j}><br /> ight)（1.2）

古典方法

在word2vec出現之前[2013]，已經有一些方法試圖對gragh進行embedding，這裡簡要介紹三個：

Locally Linear Embedding:

該方法假設一個節點可以用它鄰居節點的線性組合表示，目標函數為：

phi(Y)=frac{1}{2} sum_{i}left|Y_{i}-Sigma_{j} W_{i j} Y_{j} ight|^{2}

Laplacian Eigenmaps:

該方法認為在原始空間約相似的節點（使用邊權衡量），映射到低維空間以後也會越相似。這裡L是拉普拉斯矩陣，它是GCN的理論基石，非常重要。目標函數為：

phi(Y)=frac{1}{2} sum_{i j}left(Y_{i}-Y_{j} ight)^{2} W_{i j}

Graph Factorization:

該方法通過矩陣分解求得embedding表示，目標函數為：

phi(Y, lambda)=frac{1}{2} sum_{(i, j) in E}left(W_{i j}-<Y_{i}, Y_{j}><br /> ight)^{2}+frac{lambda}{2} sum_{i}left|Y_{i}<br /> ight|^{2}

Deepwalk

Deepwalk[2014] : DeepWalk: online learning of social representations

思考一個問題，既然自然語言中的單詞(word)可以通過共現關係進行embedding,那graph類似於 整個語料庫，圖中節點(node)類似於單詞，我們可不可以通過node之間的共現關係對graph中的node進行embdding呢?答案的關鍵在於怎麼描述node的共現關係。對於word2vec來說，語料庫中每一個句子都可以描述單詞之間的共現，那麼我們可不可以構造一個類似於句子」的序列呢，把這些序列作為node的」句子」來得到其embedding呢?實際上，deepwalk的工作就是在graph. 上構造這些「句子」,然後直接使用word2vec模型訓練得到graph中每個node的embedding表示!

Deepwalk是基礎的network embedding演算法，是將word2vec直接用於graph的演算法，只是增加了隨機遊走以構造序列（類似於word2vec的語料庫）。公式1.3 是random walk的公式，根據邊權來完全隨機的選擇下一個節點，實際上random walk是一種可回頭的深度優先搜索。

pleft(c_{i}=x | c_{i-1}=v ight)=left{egin{array}{ll}{frac{pi_{infty}}{Z},} & { ext { if }(v, x) in E} \ {0,} & { ext { otherwise }}end{array} ight.（1.3）

LINE

LINE[2015] : Large scale information network embedding

作者認為高緯度相似的節點，映射到低維空間也應該是相似的。就兩個節點的相似性，作者有兩個維度的定義：

1st order proximity：在高維層次即原始圖中，表示為節點之間的邊權；在低位層次即兩個向量要是比較近似的，用一個sigmoid函數表示。

2st order proximity：用於有向圖，如果無向圖可以變成有向圖。在高維層次，表示為兩個節點之間有多少公共一度節點；在低維層次表示為一個條件概率。

圖1.3 LINE模型

1st order proximity：直接相連的節點之間的相似度

2st order proximity：通過一階公共節點傳遞的相似度，這個地方是比較迷惑人的，包括網上很多博客解釋都是含糊不清或者是錯的。其實最主要的是每個節點都有兩個向量，一個是環境向量 （vec{u}_{j}） ，一個是自身向量（ vec{u}_{j} ）。環境向量處於被動地位，用於描述該節點充當context角色時的表示，自身向量即為最終embedding得到的向量，表示為條件概率可以理解為從節點i到節點j的概率，這表徵著該節點作為環境時跟其它節點的關係。

需要注意的是1st order proximity和2nd order proximity是分別優化的，當然對於 p_{2}left(v_{j} | v_{i} ight) 又是一個softmax,我們同樣使用負採樣優化技術:

log sigmaleft(<vec{u}_{j}^{prime}, vec{u}_{i}><br /> ight)+sum_{i=1}^{K} E_{Psi_{n} sim P_{n}(v)}left[log sigmaleft(-<vec{u}_{j}^{prime}, vec{u}_{i}><br /> ight]<br /> ight.（1.4）

最後注意一點，LINE基於鄰域相似的假設，這其實是一種基於BFS方法。

GraRep

GraRep[2015] : Learning Graph Representations with Global Structural

圖1.4 節點之間K(1,2,3,4)階相似性

LINE只考慮2-order相似性好嗎?為什麼不考慮3-order, 4-ord.... 如圖1 .4中，我們很明顯知道上面一行A1與A2的關係強於下面一行，那麼怎麼描述這種關係呢? GraRep就是解決這個問題，和LINE思路一樣，每個節點兩個向量，一個自身向量，一個環境向量。

首先定義k—order相似性:

L_{k}=sum_{w in V} L_{k}(w)（1.5）

其中 L_{k}(w) 表示對於特定節點w的k-order相似性, L_{k}(w) 表示為公式1.6(已經使用了負採樣優化):

L_{k}(w)=left(sum_{c in V} p_{k}(c | w) log sigma(vec{w} cdot vec{c}) ight)+lambda mathbb{E}_{c^{prime} in p_{k}(V)}left[log sigmaleft(-vec{w} cdot vec{c}^{prime} ight) ight]（1.6）

其中 p_{k}(c | w) 表示從w節點經過k跳以後到達c的概率，即 p_{k} 為節點k階轉移矩陣。一階轉移矩陣可以用歸一化鄰接矩陣 oldsymbol{A}=oldsymbol{D}^{-1} oldsymbol{W} 表示，那麼k階轉移矩陣為 P_{k}=A^{k} ,即

p_{k}(c | w)=A_{w, c}^{k}

p_{k}(c) 表示圖中k跳的邊緣分布，即隨機選擇開始位置，經過k跳以後到達c的概率:

p_{k}(c)=sum_{omega^{prime}} qleft(w^{prime} ight) p_{k}left(c | w^{prime} ight)=frac{1}{N} sum_{w^{prime}} A_{w, c}^{k}（1.7）

其中 qleft(w^{prime} ight) 表示 w^{prime} 節點的先驗分布，這裡假設為均勻分布，即

oldsymbol{q}left(oldsymbol{w}^{prime} ight)=frac{1}{N}

將1.6, 1.7代入並令導數為0,可以得到下式:

W_{i}^{k} cdot C_{j}^{k}=log left(frac{A_{i, j}^{k}}{sum_{t} A_{t, j}^{k}} ight)-log left(frac{lambda}{N} ight)（1.8）

即求一個矩陣分解即可，丟棄C矩陣(環境向量組成的矩陣)，W矩陣即為所求。

Node2vec

Node2vec[2016] : Scalable Feature Learning for Networks

圖1.5 BFS和DFS搜索

前面說到Deepwalk其實是基FDFS模型, LINE和GraRep是基於DFS的模型,一般來說基於BFS的模型傾向於獲取圖中的內容相似性(即局部相似性)，基於DFS的夜型更傾向於獲取結構相似性。那麼能否設計一種可以平衡BFS和DFS的模型呢? Node2vec給出了一種方案,它設計了一個二階隨機遊走，通過p, q兩個參數來平衡BFS和DIS兩種搜索策略。

圖1.6是p, q控制的二階隨機遊走

圖1.6是p, q控制的二階隨機遊走的示意圖，其中a是關於當前節點v搜索下一個節點2的函數，p,q為超參數,表達式如下:

alpha(t, x)=left{egin{array}{ll}{frac{1}{p},} & { ext { ifd }_{t x}=0} \ {1,} & { ext { ifd }_{t x}=1} \ {frac{1}{q},} & {i f d_{t x}=2}end{array} ight.（1.9）

那麼從當前節點v隨機遊走到下一個節點x的概率就是其歸一化形式:

p(x | v)=frac{alpha(t, x)}{sum_{(y, v) in E} alpha(t, y)}（1.10）

從公式1.9和1.10可以看出, p控制著隨機遊走以多大的概率「回頭」，q控制著隨機遊走偏向於DFS還是BFS,當q較大時，傾向於BFS, 當q較小時: 傾向於DFS。 特別地，當p, q都為1時，等價於random walk。

node2vec在工業界也十分成功，有兩個案列：

Facebook：廣告領域定製化受眾

Tencent：微信朋友圈廣告(Lookalike)策略

Struc2vec

struc2vec[2017]:struc2vec:Learning Node Representations from Structural Identity

Struc2vec認為node的embedding不應該考慮任何相鄰性，而是只考慮節點的空間結構相似性。它認為deepwalk和node2vec等模型之所以有效是因為，現實世界中相鄰的節點往往有比較相似的空間環境，因此這種方法有效，但是有些時候這種方法會失效，例如圖1.7。

圖1.7 gragh結構相似形

圖1.7中，節點u和v,之間可能相隔很遠，但是結構上他們卻是十分相似的，GE演算法應該考慮這種遠距離的結構相似形。那麼怎麼用數學語言描述這種結構相似形呢? 一個直觀的想法是，如果兩個節點的所有鄰居組成的兩個序列相似，那麼這兩個節點就比較相似，實際上,論文正是使用這種方式分層定義結構相似形的。

考慮節點u，令 R_{k}(u) 表示與u最短距離為k的節點集合，s(S)表示節 點集合 s subset V 的有序度(degree)序列，定義 f_{k}(u, v)

f_{k}(u, v)=f_{k-1}(u, v)+gleft(sleft(R_{k}(u), sleft(R_{k}(v) ight) ight) ight)（1.11）

g函數是比較兩個序列相似度的函數，可以是Dynamic Time Warping(動態時間規整演算法)，用來計算兩個可能長度不等的序列的相似 f_{k}(u, v) 表徵節點u, v之間的結構不相似性，可以看出，隨著k增大， f_{k}(u, v) 的感受野越來越大，因此我們需要先在底層k = 1比較節點之間相似性，如果兩個節點之間關係較緊密，我們需要在更高層次(更大感受野)來度量兩個節點的相似性，公式1.13反應出這一點(傾向於向上遊走)。

利用 f_{k}(u, v) 構造分層圖，同層之間節點之間的權值如公式1.12,相鄰層對應節點的權值為公式1.13

w_{k}(u, v)=e^{-f_{k}(u, v)}（1.12）

left{egin{array}{l}{w_{left(u_{k}, u_{k+1} ight)}=log left(Gamma_{k}(u)+e ight), quad Gamma_{k}(u)=sum_{v in V} 1left(w_{k}(u, v)>overline{w}_{k}<br /> ight)} \ {w_{left(u_{k}, u_{k-1}<br /> ight)}=1}end{array}<br /> ight.（1.13）

接下來就是隨機遊走構建sequence了，首先每一步有一個概率p在本層， 1-p跳出本層，如果在本層按照公式1.14採樣下一個節點，如果跳出本層，按照公式1.15來選擇上一層 left(u_{k+1} ight) 還是下一層 left(u_{k-1} ight) :

p_{k}(v | u)=frac{e^{-f_{k}(u, v)}}{Z_{k}(u)}（1.14）

left{egin{aligned} p_{k}left(u_{k+1} | u_{k} ight) &=frac{w_{( } u_{k}, u_{k+1} )}{w_{( } u_{k}, u_{k+1} )+w_{( } u_{k}, u_{k-1} )} \ p_{k}left(u_{k-1} | u_{k} ight) &=1-p_{k}left(u_{k+1} | u_{k} ight) end{aligned} ight.（1.15）

關於struc2vec有一個很成功的工業應用：螞蟻金服風控模型。應用了struc2vec後，相比於node2vec有質變(AUC 70+ -> 90+)。

GraphSAGE

GraphSAGE[2017] : Inductive representation learning on large graphs

介紹一組概念:

  • 直推式學習:直接根據graph學習到個N x F的矩陣，graph結構變化是要重新學習的
  • 歸納式學習:利用節點鄰域信息直接學習出新增節點(unseen node) 的embedding表示

前面介紹的模型全部都是直推式學習，換句話說當graph變化時，需要重新學習。GraphSAGE是歸納式學習的一個代表，它不直接學習每個節點的表示，而是學習聚合函數，學到了聚合函數以後，對於新增的節點我直接生成它的embedding表示，而不需要重頭學習。下面演算法就是GraphSAGE的核心內容了，圖1.8更形象的表示這一演算法。

圖1.8 GraphSAGE模型示意圖

該演算法分為兩步:

1.鄰居採樣:因為每個節點的度是不一致的，為了計算高效，為每個節點分層(K層)採樣固定數量的鄰居。

2.鄰居特徵聚集:通過聚集採樣到的鄰居特徵，更新當前節點的特徵，網路第k層聚集到的鄰居即為BFS過程第k層的鄰居採樣。

Aggregator function要求要對順序不敏感，因為random選擇的node本身是無序的，可以有如下幾種選擇，當然也可以自己設計:

  • Mean aggregator: h_{v}^{k} leftarrow sigmaleft(W . M E A Nleft(left{h_{v}^{k-1} ight} cupleft{h_{u}^{k-1}, forall u in mathcal{N}(v) ight} ight) ight)
  • LSTM aggregator: LSTM輸入是有序的，每次採樣的node需要shuffle一下
  • Pooling aggregator: Aggregator_{k}^{p o o l} leftarrow max left(left{sigmaleft(W_{p o o l} h_{u_{i}}^{k}+b ight), forall u_{i} in mathcal{N}(v) ight} ight)
  • GCN aggregator:圖卷積聚合器，後文再表

CANE

CANE[2017] : Context-Aware Network Embedding for Relation Modeling

圖1.9 附帶文本信息得社交網路

前面所有模型都是在圖結構上做文章，但是現實世界中節點和邊上有豐富的信息(如圖1.9),包括我們組現在遇到問題(我們在對拼車的規模與成本之間關係建模)，節點和邊的信息都是不可忽略的。我們應該使用這些信息，由於graph embedding是伴隨社交網路發展的，所以大多數文章把節點上的信息當做文本信息處理，類似的模型還有CENE,將文本轉化為特殊的節點，這樣就有兩種連邊，(節點-文檔)以及(節點-節點)，對兩種邊一起建模，trans-net將機器翻譯的一些東西引進來，這些都是和nlp相關的，就不都說了，這裡只簡單介紹CANE，CANE兼顧結構相似性和文本內容相似性，應用attention機制， 可以自適應地計算文本之間的相似性。

圖1.10 CANE模型框架示意圖

圖1.9是CANE的框架示意圖，從最底層看，使用訓練好的詞向量(就是一開始我們提到的word2vec)先把每個節點的文本信息表示為一個矩陣，然後使用行卷積變換;接著P和Q和一個Attention係數矩陣執行 anh left(P^{T} A Q ight) 運算, oldsymbol{F}_{i j} 表示著 P_{i} 對 Q_{j}的重要程度，然後分別採用的row-pooling和column-pooling +softmax產生一個注意力向量，比如 a^{p} 就表示v對P每列的重要程度;最後使用注意力向量和原詞向量矩陣相乘得到最終的v對u和u對v的text向量，分別表示為 v_{(u)}^{t} ，和 u_{(v)}^{t} 損失函數由兩部分表示，一部分代表結構相似性 L_{s}(e) , 另一部分代表文本信息相關性 L_{t}(e) :

L(e)=L_{s}(e)+L_{t}(e) (1.16)

考慮結構相似性，和LINE相似:

pleft(v^{s} | u^{s} ight)=frac{exp left(<u^{s}, v^{s}><br /> ight)}{sum_{z in V} exp left(<u^{s}, v^{s}><br /> ight)}（1.17）

L_{s}(e)=w_{u, v} log pleft(v^{s} | u^{s} ight)（1.18）

文本相似性由三部分組成，分別為text-text相似性，text-structure相似性 和structure-text相似性:

L_{t}(e)=alpha L_{t t}(e)+eta L_{t s}(e)+gamma L_{s t}(e)（1.19）

L_{t t}(e)=w_{u, v} log pleft(v^{t} | u^{t} ight)（1.20）

L_{t s}(e)=w_{u, v} log pleft(v^{t} | u^{s} ight)（1.21）

L_{s t}(e)=w_{u, v} log pleft(v^{s} | u^{t} ight)（1.22）

當然，對於公式中所有的softmax,都需要使用負採樣加速的。

SDNE

SDNE[2016]: Structural Deep Network Embedding

嚴格來說，前面所有模型都是淺層模型，SDNE是一個基於自編碼器的深度模型，圖1.11 是該模型的架構示意圖

圖1.11 SDNE模型示意圖

SDNE基於深度自編碼器，它的輸入是graph的鄰接矩陣，每個node對應一行，該行表示該node與其他所有node是否有邊。它的損失函數有兩部分組成，第一部分是基於「如果兩個node有邊，那麼他們應該是相似」的事實，第二部分是重建所示，公式如下:

mathcal{L}_{m i x}=mathcal{L}_{2 n d}+alpha mathcal{L}_{1 s t}+v mathcal{L}_{r e g}（1.23）

注意 mathcal{L}_{r e g} 是正則化項。 mathcal{L}_{2 n d} 是重建損失，表達式為公式1.24:

egin{aligned} mathcal{L}_{2 n d} &=sum_{i=1}^{n}left|left(hat{x}_{i}-x_{i} ight) odot b_{i} ight|_{2}^{2} \ &=|(hat{X}-X) odot B|_{F}^{2} end{aligned}（1.24）

這裡面有一個小trick,就是公式里的B,它會增大對0的懲罰，即對於xi=0, bi較大， 對於xi≠0, bi較小。這裡是基於兩個考慮:

  • 一般來說鄰接矩陣都比較稀疏，如果不對向量中的0做特殊懲罰，容易得到0向量的平凡解。
  • 原始圖中兩個node之間沒有邊(鄰接矩陣中對應值為0),並不代表他們真的沒有關係，可能因為圖不完整或者兩個節點不是直接相連而是K-hop鄰域(K > 1)。 mathcal{L}_{1 s t} 控制有邊的兩個node, embedding得到的向量接近，表達式為公式1.25:

mathcal{L}_{2 n d}=sum_{i, j}^{n} s_{i, j}left|left(hat{y}_{i}^{(K)}-y_{i}^{(K)} ight) ight|_{2}^{2}（1.25）

其中 oldsymbol{s}_{i, j} 表示兩個節點的邊權。

GraphGAN

GraphGAN[2018] : GraphGAN: Graph Representation Learning with Generative Adversarial Nets

如果評出最近兩年最火的模型是什麼?那麼GAN一定在候選名單中，GAN和VAE是目前最優秀也是最經常拿來比較的兩個深度生成模型，順便提一句，最近有一篇paper: Variational Inference: A Unified Framework of Generative Models and Some Revelations將GAN和VAE統一到變分推斷的框架下，作者大喊一句:你們別打了，都是自家兄弟，相煎何太急。

回歸正題，最火的模型當然也要在最火的方向摻和一腳，這就是GraphGAN, 類似的模型還有ANE(Adversarial Network Embedding),這裡只介紹GraphGAN。

GraphGAN思想是，生成器生成一條圖中不存在的邊，判別器判斷一條邊是否為圖中存在的邊，當訓練完全以後，生成器生成的邊和圖中真實存在的邊無法分辨，即embedding成功，換句話說生成器逼近網路一階信息。

先看GraphGAN的目標函數:

min _{ heta_{G}} max _{ heta_{D}} V(G, D)=sum_{c=1}^{V}left(mathbb{E}_{v sim p_{ ext {rrue}}}left(cdot | v_{c} ight)left[log Dleft(v, v_{c} ; heta_{D} ight) ight] ight)+left(mathbb{E}_{v sim Gleft(cdot | v_{c} ; heta_{G} ight)}left[log left(1-Dleft(v, v_{c} ; heta_{D} ight) ight) ight] ight)（1.26）

公式1.26可以這樣理解:

  • 固定 heta_{D} 看 min _{ heta_{G}} ; 只有後面一項和 heta_{G} 有關，最小化後面一項相當於最大化 Dleft(v, v_{c} ; heta_{D} ight) ,其中v是從 Gleft(cdot | v_{c} ; heta_{G} ight) 採樣的，換句話說v是生成器G生成的樣本。也就是說 min _{ heta_{G}} 的目的是讓判別器D認為生成器G產生的樣本為真，這是優化生成器。
  • 固定 heta_{G} 看 max _{ heta_{D}} ;兩項都和 heta_{D} 有關，對於第一項，最大化第一項相當於最大化 Dleft(v, v_{c} ; heta_{D} ight) ,其中v是從 p_{ ext {true}}left( . | v_{c} ight) 採樣的，換句話說是讓判別器D認為真實的樣本為真;對於第二項，最大化第二項相當於最小化 Dleft(v, v_{c} ; heta_{D} ight) ,其中v是從 Gleft(cdot | v_{c} ; heta_{G} ight) 採樣的，換句話說是讓判別器D認為生成器G產生的樣本為假。這是優化判別器。

所有的GAN的loss函數(最小最大遊戲)都可以這麼理解。現在看看生成器和判別器的形式:

Dleft(v, v_{c} ight)=sigmaleft(d_{v}^{T} cdot d_{v_{c}} ight)=frac{1}{1+exp left(-d_{v}^{T} cdot d_{v_{c}} ight)}（1.27）

Gleft(v | v_{c} ight)=frac{exp left(g_{v}^{T} cdot g_{v_{c}} ight)}{sum_{v eq v_{c}} exp left(g_{v}^{T} cdot g_{v_{c}} ight)}（1.28）

如上，判別器是一個sigmoid函數，生成器是一個softmax函數，實際上你可以設計任何合理的生成器與判別器。正如我們所見，式1.27是一個softmax, 我們需要優化它，論文中作者設計了一種叫做GraphSoftmax的優化方法，這裡不詳細介紹了，有興趣的同學移步論文。

GraphWave

GraphWave[2018]: Learning Structural Node Embeddings via Diffusion Wavelets

模型特點：

完全非監督，不需要任何先驗知識。對比以往的模型，大多需要一些先驗，比如struc2vec的先驗是一個節點的局部性可以由其鄰居的度序列表示（關於struc2vec，以及其他主流GE方法，這篇文章有詳細介紹）；然而GraphWave只需要輸入拉普拉斯矩陣即可。

完整的數學證明——數學使人安心。以前的方法都是啟發式的，這篇論文作者使用大量篇幅證明使用GraphWave，結構等價/相似的節點具有近乎相同/相似的嵌入。在數學上的保證總能給人心安不是嗎？

總結

前面說了很多GE的模型，從古典方法，到只考慮結構的模型，再到考慮節點和邊extra info的模型，再到深度模型，大家可能覺得眼花繚亂，並不知道實際中應該用哪個模型。

這裡我提示一句，你選擇的模型一定要和你的實際問題相關:

  • 比如如果你的問題更加關注內容相似性(局部鄰域相似性)那麼你可以選擇node2vec, LINE, GraRep等;
  • 如果你的問題更加關注結構相似性，你可以選擇struc2vec, 這裡可以簡單說一下為什麼 螞蟻金服風控模型使用struc2vec相比node2vec有質的提升，這是因為在風控領域，你可信並不能代表你的鄰居可信(有些「大V」節點鄰居眾多)，但是一個直觀的感覺是，如果兩個人在圖中處於相似的地位(比如兩個「大V")，那麼這兩個人應該都可信或都不可信，並且-般來說這樣的兩個人(節 點)都相聚比較遠;
  • 再者如果你的模型需要考慮節點和邊的額外信息，那麼你可選擇CANE, CENE, Trans-net等 ;
  • 如果你想處理大規模易變圖，你可以採用GraphSAGE, 或者先使用其他GE方法，再使用GraphSAGE歸納學習;
  • 如果你想微調你的模型，你可選擇GraphGAN;
  • 甚至你可以選擇很多GE方法，並將得到的embedding向量進行聚合，比如concat等方式;

總之，選用什麼模型取決你的問題!

圖卷積（Graph CNN）

前面是GE領域的概述了，現在要說的是另一個事情就是圖卷積(Graph Convolutional Neural Network,GCN),其實這相對於GE是另一個思路，GE基於高維相似性映射到低維以後也是相似的，我們想使用深度學習應該先學習圖嵌入(借鑒nlp中的word2vec) ，而GCN就是直接端到端分類或回歸，當然也可以先使用進行圖嵌入，拿到嵌入向量以後進行gcn,另外gcn很多時候會附帶的產生圖嵌入。

一般來說GCN分為兩大類，一種是譜圖卷積，是在傅里葉域進行卷積變換;另一種是非譜圖卷積(也叫做「空間域卷積」)，是直接在Graph上進行卷積。我們分別介紹這兩類，圖2.1 是GCN的大家族。

圖2.1 Graph CNN的大家族

Spectral Convolution

譜圖卷積需要補充一些理論知識。如果沒有這些背景知識，你是看不懂GCN的，或者僅僅是一知半解，不會有深入的理解（關於這塊的詳細解釋，見github原文）。

? Graph拉普拉斯運算元

? Graph上的傅里葉(逆)變換

? Graph上的譜圖卷積

1st Spectral Convolution: Spectral Networks and Locally Connected Networks on Graphs

Graph上的譜圖卷積表達式為：

(f * h)_{G}=Uegin{pmatrix} lambda_{1} & & & \ & lambda_{2} & & \ & & ... & \ & & & lambda_{n} end{pmatrix} U^{T} f(2.14)

寫成矩陣形式為：

(f * h)_{G}=Uleft(left(U^{T} f ight) odotleft(U^{T} h ight) ight)（2.15）

公式2.15是我們推導半天的最終成果了， U^{T} f 和 U^{T} h 分別為Graph原特徵的傅里葉變換和卷積核的傅里葉變換，兩者點乘，再左乘U即為原空間的卷積。

那麼第一代譜圖卷積就呼之欲出了，只需要把 hat{h}left(lambda_{l} ight)

作為卷積核參數即可!表達式如下:

y_{ ext {outppt}}=sigma(Uegin{pmatrix} heta_{1} & & & \ & heta_{2} & & \ & &... & \ & & & heta_{n} end{pmatrix}U^{T} x) (2.16)

大功告成!我們現在可以按照式2.16進行譜圖卷積了。但是1st Spectral Convolution還有一些不完美的地方:

  • 計算量大，每次卷積運算都要進行矩陣相乘，計算複雜度 Oleft(N^{3} ight) (即使使用優化的斯坦福演算法複雜度也是 Oleft(N^{2.37} ight) ,且需要特徵分解，特徵分解複雜度為 Oleft(N^{3} ight) ，沒有spatial localization(空間局部性)，傳統的CNN受控於感受野，每次卷積只需考慮一小部分鄰域，但是GCN是每一次卷積都要考慮所有的節點。
  • 參數個數 Oleft(N ight) , 傳統的CNN參數個數是常數，例如3*3的卷 積核有9個參數。

2nd Spectral Convolution

2nd Spectral Convolution[2016] : Convolutional neural networks on graphs with fast localized spectral filtering

1st Spectral Convolution有一些不完美的地方， 2nd Spectral Convolution就是解決這些問題的! 我們先把圖卷積重寫:

y=sigmaleft(U g_{ heta}(Lambda) U^{T} x ight)(2.17)

其中 Lambda 是特徵值組成的對角矩陣，那麼對於1st Spectral Convolution,

g_{ heta}(Lambda)=operatorname{diag}( heta)（2.18）

對於2nd Spectral Convolution,把 g_{ heta}(Lambda)

改為如下形式

g_{ heta}(Lambda)=sum_{k=0}^{K-1} heta_{k} Lambda^{k}（2.19）

我們把式2.19代入到2.17得到第二代卷積的公式:

egin{aligned} y &=sigmaleft(U sum_{k=0}^{K-1} heta_{k} Lambda^{k} U^{T} x ight) \ &=sigmaleft(sum_{k=0}^{K-1} heta_{k} U Lambda^{k} U^{T} x ight) \ &=sigmaleft(sum_{k=0}^{K-1} heta_{k} L^{k} x ight) end{aligned}（2.20）

式2.20推導過程中應用了特徵分解的性質 U Lambda^{k} U^{T}=L^{k}

公式2.20即為第二代卷積公式，當我們事先把 L^{k} 計算好，每一步只需要向量與矩陣相乘，複雜度降低為 Oleft(K N^{2} ight) ,如果使用稀疏矩陣演算法，複雜度為 O(K|E|) ，但是第二代卷積怎麼體現spatial localization呢?

這裡介紹一個拉普拉斯運算元的性質:

Lemma2.1:如果 d_{G}(m, n)>s ,則 L_{m, n}^{s}=0 , d_{G}(m, n)

表示圖G中節點m和n的最短距離。

由Lemma 2.1可知，式2.20的卷積公式僅使用K-hop鄰域，即感受野半徑是K。

論文中提到另一種優化方式，將 L^{k} 利用切比雪夫展開來優化計算複雜度，優化後計算複雜度也為O(K|E|)，我本身沒有看出有什麼加速.

切比雪夫展開：任何k次多項式都可以使用切比雪夫多項式展開

切比雪夫展開公式為:

egin{array}{l}{T_{0}(x)=1} \ {T_{1}(x)=x} \ {T_{k}(x)=2 x T_{k-1}(x)-T_{k-2}(x)}end{array}(2.21)

將2.20中的 L^{k}

使用切比雪夫展開可得：

y==sigmaleft(sum_{k=0}^{K-1} heta_{k} T_{k}( ilde{L}) ight)（2.22）

其中 ilde{L}=2 frac{L}{lambda_{mathrm{ma}}}-I_{N}

,這是為了將L的譜半徑約束到[-1, 1],使得在連續相乘的時候不會爆炸。

總結2nd Spectral Convolution:計算複雜度降低為O(K|E)只考慮K-hop鄰域，有一定的空間局部性

3rd Spectral Convolution[2017] : Semi-supervised classification with graph convolutional networks

到第二代，譜圖卷積已經基本成型，第三代GCN改動不大了，概括兩個點:

1.令K=1,即每層卷積只考慮直接鄰域，這類似於CNN中3*3的kernel。

2.深度加深，寬度減小(深度學習的經驗，深度>寬度)。

總結2nd Spectral Convolution:

  • 計算複雜度降低為O(|E|)
  • 只考慮1 - hop鄰域，通過堆疊多層，獲得更大的感受野

Spatial Convolution

前面講的都是基於譜圖理論的卷積，思想是在原空間卷積不好做，那就在圖拉普拉斯運算元的傅里葉域做。那麼是否可以直接在原空間做卷積呢?答案是可以的，Spatial Convolution(空間域卷積)就是直接在圖上做卷積，我們知道卷積核大小是固定的，也就是我們需要選擇固定大小的鄰域來做卷積，但是相比於規則網格結構，graph中的節點通常具有不同個數的鄰域，這是在原空間做卷積的主要困難。

DCNNs[2016] : Diffusion-convolutional neural networks

圖2.2 DCNNs用於Node分類和Graph分類的示意圖

DCNNs可以應用於兩種任務，一個是節點分類，一個Graph分類， 我們先說節點分類任務。對於節點分類任務，卷積公式為:

Z_{t i j k}=fleft(W_{j k}^{c} cdot sum_{l=1}^{N_{t}} P_{t i j l}^{*} X_{t l k} ight)（2.27）

其中 X_{t l k} 表示第t個Graph G_{t} , 第l節點的第k個特徵； P_{t i j l}^{*} 表示 G_{t} 的i節點經過j跳以後達到l節點的概率， P_{t i j l}^{*}=P_{t i k}^{j} , P_{t} 為 G_{t} 的轉移矩陣， P_{t}^{j} 為 G_{t} 的j跳轉移矩陣，f為非線性激活函數； W^{c} 為卷積核。將式2.27表達為張量形式為：

Z_{t}=fleft(W^{c} odot P_{t}^{*} X_{t} ight)（2.28）

對於Graph分類任務，對於 G_{t} 上的每個節點i，取H跳的所有鄰居的第F個特徵求均值，乘以權值 W^{mathrm{c}} 即可，表達式如下：

Z_{t}=fleft(W^{c} odot 1_{N_{t}}^{T} P_{t}^{*} X_{t} / N_{t} ight)（2.29）

得到Z以後，按照圖2.2架構網路即可。

DCNNS總結：

●卷積核參數O(H*F)

●考慮H跳鄰域

CNN4G[2016] : Learning convolutional neural networks for graphs

該模型是針對Graph分類任務的，主要思路是選出一-些節點代表整個Graph,並為每個節點選出特定個數的鄰域，然後在每個節點和其鄰域節點組成的矩陣上做卷積。

演算法步驟:

  1. 找出w個節點，這w個節點可以代表整個Graph,文章使用的是centrality的方法，即選出w個最中心的節點。具體的計算該node與所有node距離和，距離和越小越中心，如圖2.3中，左邊紅色節點與其他所有節點距離和為23,右邊紅色節點為25，所以左邊紅色節點更中心，應該優先選它。
  2. 為每個節點找出K個鄰域，作為該節點的感受野，如圖2.42.1先選出一階鄰域，一 階鄰域不夠就選-二階鄰域，直到至少K個節點，或者沒有節點可選.2.2選出的節點如果不夠，補充0向量，如果多了就按照中心rank排名刪除後面的節點.
  3. 選出的w個節點，每個節點和其鄰域節點都可以組成規則的(K + 1) * F的矩陣，而所有的邊也可以組成-個(K +1)*(K + 1)* F的張量，在這些張量上做卷積，如圖2.5。

圖2.5 對每組節點卷積示意圖

GAT[2018] : Graph Attention Networks

該模型結合了注意力機制，可以動態計算節點之間的相關性，並且該模型可以直推式學習，也可以歸納式學習，是非譜圖卷積領域裡state-of-the-art的方法，在很多公開數據集取得了非常好的效果。

圖2.6 注意力機制與multi-head注意力機制

這個模型最最重要的就是attention,即動態計算鄰域節點和該節點的強度關係，我們將看到只要用到attention的思路都是一樣的， 論文Attention is all you need總結的很精準。

GATs的輸入是節點特徵的集合

mathbf{h}=left{vec{h}_{1}, vec{h}_{2}, ldots, vec{h}_{N} ight}, vec{h}_{i} in mathbb{R}^{F}

其輸出是經過變換後的節點特徵集合

mathbf{h}^{prime}=left{vec{h}_{1}^{prime}, vec{h}_{2}^{prime}, ldots, vec{h}_{N}^{prime} ight}, vec{h}_{i}^{prime} in mathbb{R}^{F^{prime}}

注意力係數計算如下：

e_{i j}=aleft(W vec{h}_{i}, W vec{h}_{j} ight)（2.30）

其中a表示注意力機制函數, 將上式歸一化得到:

alpha_{i j}=operatorname{softmax}left(e_{i j} ight)=frac{exp left(e_{i j} ight)}{sum_{k in N_{i}} exp left(e_{i k} ight)}（2.31）

其中 mathcal{N}_{i} 表示節點i的鄰域節點集合。

將注意力機制函數用單獨一層神經網路來表示，參數為 vec{a} in mathbb{R}^{2 F^{prime}} ，則式2.31可寫為:

alpha_{i j}=frac{exp left(vec{a}^{T}left[W vec{h}_{i} | W vec{h}_{j} ight] ight)}{sum_{k in N_{i}} exp left(vec{a}^{T}left[W vec{h}_{i} | W vec{h}_{j} ight] ight)}（2.32）

其中||表示concat運算。一旦得到注意力係數，則輸出即為變換後的特徵與注意力係數的線性組合:

vec{h}_{i}^{prime}=sigmaleft(sum_{k in N_{i}} alpha_{i j} W vec{h}_{j} ight)（2.33）

如圖2.6所示，我們可以設計K注意力係數,並將它們的結果聚合起來，聚合函數可以選擇concat或者avg

egin{aligned} vec{h}_{i}^{prime} &=left|_{k=1}^{K} sigmaleft(sum_{k in mathcal{N}_{i}} alpha_{i j}^{k} W^{k} vec{h}_{j} ight) ight.\ vec{h}_{i}^{prime} &=sigmaleft(frac{1}{K} sum_{k=1}^{K} sum_{k in mathcal{N}_{i}} alpha_{i j}^{k} W^{k} vec{h}_{j} ight) end{aligned}（2.34）

我們可以用多個GAT layer嵌套起來，已獲得更大感受野。

總結

一般來說GCN分為兩大類，一種是譜圖卷積，是在傅里葉域進行卷積變換;另一種是非譜圖卷積(也叫做「空間域卷積")，是直接在Graph.上進行卷積。譜圖卷積有一套統一的理論支持，但是有時候會受到圖拉普拉斯運算元的限制;空間域卷積更加靈活，主要困難在於選擇定量鄰域上，很多模型千奇百怪，沒有統一理論，更多是一種trick。

基於圖的序列建模

接著一塊說說圖序列建模吧，這類問題相對較少，比較典型的例子是交通路網數據，短期內路網結構可以認為是不變的，但是裡面的數據是流動的，換句話說graph是固定的，但是裡面的數據是時間序列的，類比於視頻預測一樣，預測接下來一段時間，圖中數據的變化，例子路網eta，路網流量預測等問題。

先簡單說一下ConLSTM的思路，假設我想做視頻預測的任務，那麼我需要獲取每一幀圖像的空間(歐幾里得空間)信息，同時視頻的連續幀之間具有時間相關性，也就是說我需要同時獲取空間和時間相關性。但是傳統的LSTM輸入是一維向量，如果我將視頻每一幀圖像展開為-維向量，那麼將失去他們的空間信息。如果我可以讓LSTM可以處理輸入為二維的圖像，那該多好啊，我們就可以同時獲取其空間和時間信息，這就是ConvL STM解決的問題。簡單來說ConvLSTM將LSTM中所有的矩陣相乘運算換為卷積網路，詳細內容大家可以參看論文ConvolutionalLSTMNetwork:A.Machine Learning Approach for PrecipitationNowcasting。

DCRNNS

DCRNNs[2018]:DiffusionConvolutional Recurrent NeuralNetwork: Data-Driven Traffic Forecasting

Graph上的時間序列建模問題可以描述為:

left[X^{left(t-T^{prime}+1 ight)}, ldots, X^{(t) } ; mathcal{G} ight] ightarrow h( .) ightarrowleft[X^{(t+1)}, ldots, X^{( t+T)} ight](3.1)

即Graph固定下，根據前一段序列預測後一段序列，是一個seq2seq問題。

有了ConvLSTM的思路，我們很自然可以想到，將GCN和RNN結合起來，改造出新的適合處理Graph輸的RNN模型即可，DCRNNs就是將DCNNs和GRU結合起來的例子，為了可以抓取上游和下游的信息，作者對DCNNs增加了雙向擴散，雙向擴散卷積公式如下:

X_{ :, p} star g f_{ heta}=sum_{k=0}^{K-1}left( heta_{k, 1}left(D_{o}^{-1} W^{T} ight)^{k}+ heta_{k, 2}left(D_{I}^{-1} W^{T} ight)^{k} ight)(3.2)

其中Do和Di分別表示出度矩陣和入度矩陣，式3.2計算的是第p的特徵(通道)的卷積公式，對於有Q個卷積核的卷積運算表達式如下:

H_{ :, q}=a(sum_{p=1}^{P} X_{ :, p} star_{mathcal{G}}.f_{Theta_{q, p, :, :}} )(3.3)

其中q=1,2，…Q，那麼將式3.3應用到GRU中，可以得到DCGRU表達式：

egin{aligned} r^{(t)} &=sigmaleft(Theta_{r} star_{mathcal{G}}left[X^{(t)}, H^{(t-1)} ight]+b_{r} ight) \ u^{(t)} &=sigmaleft(Theta_{u} star gleft[X^{(t)}, H^{(t-1)} ight]+b_{u} ight) \ mathcal{C}^{(t)} &= anh left(Theta_{c} star gleft[X^{(t)},left(r^{(t)} odot H^{(t-1)} ight) ight]+b c ight) \ mathcal{H}^{(t)} &=u^{(t)} odot mathcal{H}^{t-1}+left(1-u^{(t)} ight) odot mathcal{C}^{(t)} end{aligned}(3.4)

實際上該問題是一個seq2seq建模問題，因此我們可以使用常用的encoder-decoder框架，如圖3.1

圖3.1DCRNNs

3.2GAT-LSTM

GAT-LSTM[2019]: Graph Attention LSTM

這篇論文是鄙人的一點小小貢獻，和上面DCRNNs一樣，只不過我將DCNNs換成更加強大的GATs。我解決的是城市路網的交通流預測，城市路網是有潮汐現象的，所以其實路網之前的權值是不固定的，應該是變化的，DCRNNs路網權值是固定的，是一個距離的函數。

GAT-LSTM公式如下:

egin{aligned} i^{(t)} &=sigmaleft(gleft(X^{(t)} ; W_{x i}, a_{x i} ight)+gleft(H^{(t-1)} ; W_{h i}, a_{h i} ight)+b_{i} ight) \ f^{(t)} &=sigmaleft(gleft(X^{(t)} ; W_{x f}, a_{x f} ight)+gleft(H^{(t-1)} ; W_{h f}, a_{h f} ight)+b_{f} ight) \ o^{(t)} &=sigmaleft(gleft(X^{(t)} ; W_{x o}, a_{x o} ight)+gleft(H^{(t-1)} ; W_{h o}, a_{h o} ight)+b_{o} ight) \ mathcal{C}^{(t)} &=f^{(t)} odot mathcal{C}^{(t-1)}+i^{(t)} odot anh left(gleft(X^{(t)} ; W_{x c}, a_{x c} ight)+gleft(H^{(t)} ; W_{h c}, a_{h c} ight)+b_{c} ight) \ mathcal{H}^{(t)} &=o^{(t)} odot anh left(mathcal{C}^{(t)} ight) end{aligned}(3.5)

圖3.2是GAT-LSTM變換的示意圖，圖3.3是我使用的encoder-forecaster框架，其中虛線代表狀態拷貝，使用encoder-forecaster框架是基於如下考慮:

●編碼-解碼網路的解碼器一般還需要輸入，訓練期間使用標準值，推斷期間使用預測值;而編碼預測

網路的預測網路是不需要額外輸入的，這可以避免推斷期間的誤差傳遞

●編碼-解碼網路的編碼器和解碼器可以是完全不相關的模型，但是編碼-預測網路的編碼器與預測器是對稱的，這是因為編碼器中高層次的狀態已經獲得了全局的時空關係，可以指導和更新預測器低層狀態

圖3.2 GAT-LSTM特徵變換示意圖

圖3.3encoder- forecaster框架示意圏

3.3.總結

基於Graph的序列建模研究的不多，目前主流方法是使用GCN改造RNN,是的模型可以同時獲取Graph的空間相關性和時間相關性。

GNN應用簡介

社交網路數據挖掘

社交廣告(lookalike)/社區挖掘/link prediction

CV領域，尤其是3D

例如：基於人體骨架關鍵點的人類動作識別——ST-GCN(AAAI 2018)。

ST-GCN主要原理：

1. 在每一幀內部，按照人體的自然骨架連接關係構造空間圖；

2. 在相鄰兩幀的相同關鍵點連接起來，構成時序邊；

3. 所有輸入幀中關鍵點構成節點集（node set），步驟 1、2 中的所有邊構成邊集（edge set），即構成所需的時空圖。

Image Captioning(ECCV 2018)

NLP

GNN在NLP應用不多，這裡就整體在high level上簡單介紹GNN的應用吧：

在20NG/ohsumed/R52和R8/MR測試，其中MR輸於CNN域LSTM的方法，這可能因為詞序對情感分類是一個不可不略的特徵。

這也側面反應了目前GCN與NLP融合的境況，忽略詞序的任務可能比較適合，但是很多NLP任務都是seq相關的，這也是為什麼2019年了GCN還在研究怎麼文本分類...

一個可能的解法是使用LSTM進行encoding獲得序列特徵+GCN獲取的非序列特徵融合+Attention也許是處理NLP中序列建模的一個方向。

例如：文本分類(AAAI 2019)/Semantic Role Labeling(EMNLP 2017)

知識圖譜

TransE：KG Embedding baseline, TransE是知識圖譜embedding方法，基本思想是對於一個三元組(h,r,t) 其嵌入向量使得h+r-l = 0。衍生：TransH/TransR/TransD/TransE/TransA

R-GCN：節點分類/link-prediction

Relational Graph Attention Networks(ICLR 2019 openreview)

R-GCN是第一次GCN引入知識圖譜，時間節點在(2017年)。基本思路，每種relation搞一個L，link predicition基本思路是有一個打分函數，會對每個entity embedding和relation打分。負採樣為負樣本。

Zero-shotRecognitionvia Semantic Embeddings and Knowledge Graphs（基於語義嵌入和知識圖譜零次識別）

Convolutional2DKnowledgeGraph Embeddings（卷積二維知識圖譜嵌入）

生物製藥

對於自然科學中物質結構的研究,例如：molecule generated with graph VAE

交通領域

路況預測/ETA/滴滴供需預測(AAAI 2019)

基於圖卷積路況預測的ETA深度模型

文章到此就算結束了，本文對當前主流的Graph神經網路進行了綜述，最後總結一句話:如果你的問題適合建模為Graph,那麼你應該把80%的經歷花在構圖上，只要你的Graph足夠準確，數據足夠精確且豐富，那麼你可以有一萬種方法解決你的問題。

以上全當是拋磚引玉，希望對大家有所幫助。更多更詳細的內容，可關注作者GitHub獲取：

github.com/talorwu/Grap

相關文章：

1. 「雜訊對比估計」雜談：曲徑通幽之妙: blog.csdn.net/c9yv2cf9i

2. Facebook：廣告領域定製化受眾: geek.csdn.net/news/deta

3. Tencent：微信朋友圈廣告(Lookalike)策略: sohu.com/a/124091440_35

4. 金融智能在螞蟻金服的發展與應用: sohu.com/a/162168329_99

5. Attention is all you need：arxiv.org/abs/1706.0376


推薦閱讀：
相关文章