知識星球本文為 1 月 10 日，上海交通大學博士生、微軟亞洲研究院實習生——王鴻偉在第 23 期 PhD Talk 中的直播分享實錄。
網路特徵學習（network representation learning / network embedding）是近年來興起的一個特徵學習的研究分支。
作為一種降維方法，網路特徵學習試圖將一個網路中的節點對映到一個低維連續向量空間中，併在該低維空間中保持原有網路的結構資訊，以輔助後續的連線預測、節點分類、推薦系統、聚類、視覺化等任務。
在本期的 PhD Talk 中，來自上海交通大學的博士生王鴻偉，和大家一起回顧了近五年來網路特徵學習領域的研究進展。
隨後，他還以第一作者的身份，為大家解讀了上海交通大學、微軟亞洲研究院和香港理工大學在 AAAI 2018 上發表的工作：GraphGAN: Graph Representation Learning with Generative Adversarial Nets。該工作引入生成對抗網路（GAN）的框架，利用生成器和判別器的對抗訓練進行網路特徵學習。
最後，他還簡單介紹了網路特徵學習在情感預測和推薦系統領域的應用，這些工作是他以第一作者發表在 WSDM，CIKM，WWW 等資料挖掘國際頂級會議上的最新成果。
△ Talk 實錄回放
Outline
本次直播主要分為三個部分。首先，我會為大家介紹 Graph Representation Learning 的定義、應用、分類方法和相關代表作。
第二部分，我將為大家介紹我們發表在 AAAI 2018 上的一篇論文 GraphGAN: Graph Representation Learning with Generative Adversarial Nets。
最後，我還將介紹我們在 Graph Representation Learning 領域的一些應用，包括推薦和情感預測。
上圖底部是三份比較有價值的資料，第一份是 Graph Embedding 的 Survey，第二份是一個論文清單，其中包含近五年來較為經典的 Network Representation Learning 相關論文。第三份是我寫的關於推薦系統和網路表示學習的文獻綜述，歡迎大家參考。
關於GRL
首先簡單介紹一下 Graph Representation Learning 的定義，中文可以稱之為圖特徵學習或者網路特徵學習。其主要目的在於，將圖中每一個節點都對映到一個低維向量空間，並且在此空間內保持原有圖的結構資訊或距離資訊。
以上並非官方權威定義，Graph Representation Learning 目前沒有任何官方定義或名字，它也可以被稱作 Network Embedding、Graph Embedding 或 GRL。
我們來看上圖中的簡單例子，左圖有三個節點和三條邊，其中的數字表示各邊的權值 weight，我們透過 GRL 將其對映到一個二維空間中。可以發現，如果兩個點之間的 weight 越大，那麼它們之間的距離就越近。這就是 GRL 的精髓所在，即在低維空間中保持原有圖的結構資訊。
Graph Representation Learning 的應用相當廣泛，它可以被用於鏈路預測、 節點分類、推薦系統、視覺、知識圖譜表示、聚類、Text Embedding 以及社會網路分析。
GRL分類方法
我們將 GRL 的方法按照三種不同分類來進行簡單介紹。
首先按輸入進行分類，既然是 GRL，那麼其輸入肯定是一張圖，但圖的種類有很多：
第一種叫同構圖，即圖中的節點和邊都只有一種，比如取用網路，其中的節點表示每篇 paper，邊表示取用關係。同構圖又可以根據是否有加權進行細分，即其邊是否權值、邊是否有向，以及邊是否有正負號。
第二種是異構圖，即網路中的節點和邊不止一種，一般分為兩種情況：
1. 多媒體網路。比如有的 paper 就考慮過一張圖具備影象和文字兩種節點，以及影象文字、影象影象和文字文字這三種邊。
2. 知識圖譜。圖中節點表示的是物體，邊表示的關係。每一個三元，HRT 都表示頭節點 H 和尾節點 T 有關係 R。由於關係 R 可以有很多種，因此 KG 也屬於一種異構圖。
第三種是 Graph with side information，side information 即為輔助資訊。這種圖是指除了邊和點之外，節點和邊都會帶有輔助資訊，比如邊和點都有 label，邊和點都有 attribute，或者 note 有 feature。
它們的區別在於 label 是類別型的，attribute 可以是離散的，也可以是連續的，而 feature 就可能是文字或影象等更複雜的一些特徵。
第四種是 Graph Transformed from non-relational data，即從非關係型資料中轉換成的圖，一般是指在高維空間中的一些資料。這通常是早期 GRL 方法會用到的資料，其中最為典型的例子是稍後還將提到的流形學習，我們可以將這種方法理解為一種降維方法。
按輸出內容我們也可以對 GRL 方法進行分類。
第一種方法會輸出 node embedding，即為每個節點輸出 embedding，這也是最常見的一種輸出。我們前面說到的那些方法基本上都是輸出 node embedding。
第二種方法是輸出 edge embedding，即為每個邊輸出 embedding。這種輸出有兩種情況，一種是在 KG 裡面，我們會為每一個 relation，也就是每條邊都有輸出。在 link prediction 的應用中，我們也會為每一條邊來輸出一個特徵，併在後續工作中將其作為邊的特徵來進行一些分類任務。
第三種方法會輸出 sub-graph embedding，也就是子圖的 embedding，包括子結構或團體的 embedding。
第四種是全圖的 embedding，即為一個整圖來輸出 embedding。如果我們對蛋白質、分子這類數量較多的小圖進行 embedding，就可以對比兩個分子的相似性。
第三種分類方法是按照方法來進行分類。
第一種方法是基於矩陣分解。一般來說矩陣分解包含奇異值分解和譜分解，譜分解就是我們常說的特徵分解，這種方法是比較傳統的方法。
第二種方法是基於隨機遊走。這種方法盛名在外，我們後面會提到的 Deep Walk 就是基於隨機遊走的方法。
第三種方法是基於深度學習。其中包括基於自編碼器以及基於摺積神經網路。
第四種方法是基於一些自定義的損失函式。這其中又包括三種情況，第一種是最大化邊重建機率，第二種是最小化基於距離的損失函式，第三種是最小化 margin-based ranking loss，這種方法常見於 KG embedding。
上圖是我整理的 GRL 方法代表作。按照時間順序可將它們分為三類，第一類是傳統方法，包含 PCA、LDA、MDS 等降維方法。
2000 年左右出現了一批較為經典的方法，包括 ISOMAP 同態對映，LLE 區域性線性鑲嵌，LE 拉普拉斯特徵分解。
最近五年被提出的方法也有很多，我將它們分作四類，每類都和上文提到的按方法分類逐一對應。
LDA 線性判別分析是一種傳統的有監督降維方法。我們可以看到，右圖裡面有兩類點，有正號表示的一類和有負號表示的一類。
我們需要將二維的點對映到一維上去，LDA 的標的在於讓這些投影相同類的點在投影過後，同類的點之間距離盡可能變近，即讓它們的協方差盡可能小，而不同類的點之間的距離盡可能遠。只有這樣，它才能在低維空間中對這些點進行分類或聚類操作。
Locally Linear Embedding 是一種典型的流形學習方法，它是指將高維空間中的輸入對映到低維空間，並且在低維空間中保持鄰居之間的線性依賴關係。
左下圖就是一個很典型的流形學習，流形指的是在高維空間中存在某些低維結構，比如說圖 A 很像一個瑞士捲，它其實就是一個典型的在三維空間中的二維結構。透過 LLE 我們將其展成一個二維結構。
這種方法的目的在於保持高維空間中的鄰居資訊。其具體做法如下：對於每一個點 Xi，首先需要確定其鄰居集合，然後再來計算 Wik Wij 這些引數。這些引數的意思是，我想用這些鄰居來重新構建 Xi，這個會有唯一的解析解。在拿到 W 引數之後，我們再在低維空間中用 W 進行約束，學習得到低維的一個 embedding。
Word2vec 的本質其實是 word embedding，不是 network embedding。但由於它對後續的 network embedding 方法影響深遠，所以我們來簡單介紹一下。
Word2vec 中有一個 skip-gram 模型，這個模型的本質在於為每個詞得到一個特徵，並用這個特徵來預測周圍的詞。因此，其具體方法就是將機率最大化。這個機率是指，給定一個中心詞 WT，在以它為中心、視窗為 T 的範圍中的每個詞的機率。
這個機率實際上是使用 softmax 進行計算的。由於 softmax 開銷很大，我們通常會用 negative sampling 來進行代替。negative sampling 是指為每個詞從整個詞表中選擇一些 negative samples，把他們作為負樣本。
Word2vec 在 Nerwork Embedding 中有兩篇很典型的工作，分別是 DeepWalk和 Node2vec。這兩篇工作分別發表於 KDD 14 和 KDD 16。
DeepWalk 相當於 random walk + word2vec。從圖中的每個節點出發，隨機進行 random walk，從當前節點均勻、隨機地選擇下一個節點，然後再從下個節點均勻、隨機地選擇下一個節點。
這樣重覆 N 次之後會得到一個 path，這個 path 就可以被當做一個 sentence。這樣一來，就將問題完全轉換到了 Word2vec 的領域。
大家可能會問，這個方法豈不是很簡單？不就是把 Word2vec 用到了 network embeddding 嗎？
對的，就是這麼簡單。有時候 research 並不會過分強調你的方法有多新穎、數學有多花哨，而在於你能不能提出一種 motivation 夠強、動作夠快的方法。
Node2vec 在 DeepWalk 的基礎上又做了改進。它把原來的 random walk 改成了 biased random walk。
在 DeepWalk 裡，我們是均勻地選擇下一個節點。但在 Node2vec 裡，則是不均勻地選擇下一個節點。我們可以選擇模仿 DFS 不斷往圖的深處走, 也可以模仿 BFS 繞著一個點打轉。因此，Node2vec 相比 DeepWalk 也就是新增了一個簡單改進。
LINE 的全稱是 Large-scale Network Information Embedding。這篇文章發表於 WWW 15。這個工作屬於我們之前提到的自定義損失函式，因為它定義了兩種損失函式，一種是一階的臨近關係，另一種是二級臨近關係。
所謂的一階臨近關係就是指兩個點之間是否只有相連。在右圖中我們可以看到，點六和點七之間有邊相連，那就可以認為它們擁有一階臨近關係。
二階關係是指兩個點的鄰居的相似度。右圖中點五和點六雖然沒有直接相連，但它們的鄰居是完全重合的，因此可以認為點五和點六的二階臨近關係很強。基於這樣一種臨近關係，LINE 定義了兩個損失函式 O1 和 O2，然後基於這兩個損失函式來進行 network embedding 的學習。
TransX 表示一系列方法，X 可以指代任何字母，這些方法都是基於 KG embedding。KG embedding 是指將 KG 中的每個 entity 和 relation 都對映到一個低維連續空間中，並且保持原來的圖結構資訊。比較經典的方法有 TransE、TransH 和 TransR，統稱為基於翻譯的方法。
TransE 思路很簡單，就是強制讓 Head Embedding + relatioon embedding = tail embedding。換而言之，也就是把 head 加 relation 給翻譯成 tail。由於這篇文章發表於 NIPS 13，因此它後續又引出了一大波 TransX 的方法。大家可以去看上圖底部的這篇 survey，至少有 10 篇左右。
最後一篇是 SDNE，全名為 Structured Deep Network Embedding。這篇文章發表於 KDD 15，其本質就是基於 auto encoder 的一種 network embedding。
儘管右圖看著比較複雜，其實它的思路非常簡單。作者設計了一個 auto encoder，其輸入是每個點的鄰接向量。
損失一共有三項，第一項是重建損失，第二項是 proximity loss term，意思是如果兩個節點有邊連線，那它們的 embedding 必須儘量接近，具體接近程度取決於它們的權重。weight 越大，那麼對這項損失的懲罰力度就越大。第三項是正則化項。
GraphGAN
前文將 Network Embedding 的方法歸為三類，而我們在 GraphGAN 裡將其分為兩類，第一類叫生成式模型，第二類叫判別式模型。
生成式模型是指，假定在圖中存在一個潛在的、真實的連續性分佈 Ptrue(V|Vc)。對於給定的 Vc 而言，我們可以看到 Vc 跟四個節點相連線，圖中除了 Vc 之外還有五個節點。Ptrue(V|Vc) 就是指在除了 Vc 之外其他節點上的分佈。
假設圖中對於每個 Vc 都有這麼一個分佈，那麼圖中的每條邊都可以看作是從 Ptrue 裡取樣的一些樣本。這些方法都試圖將邊的似然機率最大化，來學習 vertex embedding。我們之前提到的 DeepWalk 和 Node2vec 都屬於生成式模型。
判別式模型是指，模型試圖直接去學習兩個節點之間有邊的機率。這種方法會將 Vi 和 Vj 聯合作為 feature，然後輸出的是 edge 的機率 P(edge|Vi, Vj)。這種方法的代表作是 SDNE，以及 DASFAA 上的一篇 PPNE。
這樣分類之後，一個很自然的想法是，判別式模型和生成式模型能否進行聯合。這兩者其實可以看作是一個硬幣的兩面，他們是相互對立又相互聯絡的。
之前提到的 LINE 其實已經對此進行了嘗試。文中提到的一階關係和二階關係，其實就是兩個模型的不同標的函式。
生成對抗網路自 2014 年以來得到了很多關註，它定義了一個 game-theoretical minimax game，將生成式和判別式結合起來，並且在影象生成、序列生成、對話生成、資訊檢索以及 domain adaption 等應用中都取得了很大的成功。
受以上工作啟發，我們提出了 GraphGAN，它是一個在網路生成學習中將生成模型和判別模型加以結合的框架。
接下來為大家介紹 Mnimax Game。其中 V 是節點集合，E 是邊集合，我們將 N (Vc) 這個記號定義為 Vc 在圖中的所有鄰居，將 Ptrue (Vc) 定義成 Vc 的真實的連續性分佈。
GraphGAN 試圖學習以下兩個模型：第一個是 G(V|Vc)，它試圖去接近 Ptrue (Vc)。第二個是 D(V|Vc)，它的標的是判斷 V 和 Vc 是否有邊。
因此，我們會得到一個 two-player minimax game。這個公式是本文的關鍵所在，只有充分理解這個公式，才能繼續之後的理解。
在這個公式中，我們做了一個 minimax 操作。在給定θD的情況下，我們試圖對其進行最小化，這個公式其實是對圖中每一個節點的兩項期望求和。
下麵來看生成器的實現和最佳化。在 GraphGAN 中，我們選了一個非常簡單的生成器，生成器 D(V, VC) 就是一個 sigmoid 函式，它先將兩者的 embedding 做內積，再用 sigmoid 函式進行處理。對於這樣的實現，它的梯度自然也較為簡單。
透過上圖可以看出，我們在每一步的迭代中，從 Ptrue 中 sample 出來了一些跟 Vc 真實相鄰的綠點，然後從 G 中又生成了一些跟 Vc 相連的藍點。我們將綠點作為正樣本，將藍點作為負樣本來訓練 D，在得到 D 之後，再用 D 中的訊號去反過來訓練 G。
這就是之前所說的 policy gradient 過程。我們不斷重覆這個過程，直到生成器 G 和 Ptrue 極為接近。
在剛開始的時候，G 相對比較差，因此對於給定的 Vc 而言，G sample 的點都是一些離 Vc 很遠的點。隨著訓練的不斷進行，G sample 的點會逐漸向 Vc 接近，到最後 G sample 的點幾乎都變成了真正跟 Vc 相鄰的點，也就是 G 和 Ptrue 已經很難被區分了。
接下來，我們來討論一下 G 的實現過程。一種最直觀的想法是用 softmax 來實現 G，也就是將 G(v|VC) 定義成一個 softmax 函式。
這種定義有如下兩個問題：首先是計算複雜度過高，計算會涉及到圖中所有的節點，而且求導也需要更新圖中所有節點。這樣一來，大規模圖將難以適用。 另一個問題是沒有考慮圖的結構特徵，即這些點和 Vc 的距離未被納入考慮範圍內。
第二種方法是使用層次 softmax，具體來說就是組織了一棵二叉樹，然後將所有節點都放在葉節點的位置，再將當前的 Vc 從根開始計算。
由於從根到每個葉結點都存在唯一路徑，因此這個計算可以轉換成在樹的路徑上的計算，即它的計算複雜度為 logN ，N 代表樹的深度。這種做法雖然可以簡化計算，但它仍然沒有考慮到圖結構特徵。
第三種方法是 Negative Sampling。這種方法其實是一個最佳化方法，它並沒有產生有效的機率分佈，並且同樣沒有考慮圖的結構特徵資訊。
在 GraphGAN 中，我們的標的是設計出一種 softmax 方法，讓其滿足如下三個要求。第一個要求是正則化，即機率和為 1，它必須是一個合法的機率分佈。第二個要求是能感知圖結構，並且能充分利用圖的結構特徵資訊。最後一個要求是計算效率高，也就是 G 機率只能涉及到圖中的少部分節點。
對於每個給定的結點 Vc，我們都需要以 Vc 為根來進行一次 BFS 寬度優先搜尋，然後得到一顆以 Vc 為根的 BFS tree。對於這棵樹上的每一個節點，我們都定義了一個 relevance probability。實際上是一個在 Vc 的鄰居上的 softmax。
我們可以證明如下三個性質：
1. graph softmax 的機率和是1；
2. 在 graph softmax 中，兩個節點在原圖中的距離越遠，那麼它們的機率也隨之越低。這其實就是充分利用了圖的結構特徵，因為兩個節點在原圖中的最短距離越遠，它們之間有邊的機率也會相應越低；
3. 在 graph softmax 的計算中，計算只會依賴於 O(d log V)。d 是圖中每個節點的平均度數，V 是圖 G 中的節點大小。這個數字會明顯小於 softmax 的複雜度。
我們還相應設計了一種生成策略。這種這種生成策略並不需要將所有機率都算出來後再進行 sample，而是可以邊計算邊 sample。
GraphGAN 的演演算法如上，輸入是一些超引數，我們想輸出生成式模型 G 和判別式模型 D。第 3-12 行是演演算法的每一次迭代過程。在每一次迭代過程中，我們都重覆用生成器來生成 s 個點，並用這些點來更新 θG 的引數。
隨後，再重覆構造正負樣本來訓練 D，這樣做是出於穩定性的考慮。因為我們知道 GAN 的訓練穩定性是一個重要問題。
實驗
我們的實驗資料集一共是如上五個。Baseline 選用的是DeepWalk，LINE，Node2vec 和 Struc2vec。
我們將 GraphGAN 用到瞭如下三個測場景中，第一個是 link prediction，預測兩個點之間是否有邊的機率。圖 4 展示的是 GraphGAN 的學習曲線，對於生成器而言，在訓練大概十輪之後就很快趨於穩定，並且後續一直保持效能。
對於 D 來說，它的效能是先上升，之後出現緩慢的下降。這和我們之前所描述的 GAN 框架也是相吻合的。表 1 展示了 GraphGAN 在兩個資料集上都得到了最好的結果。
第二個測試場景是 Node Classification，在這個場景中我們想對節點進行分類，我們用的資料集是 BlogCatalog 和 Wikipedia。在這樣的資料中，我們的方法取得了最好的效果。
第三個測試場景是推薦。所用的資料集是 MovieLens，我們的方法也取得了最好的效果。
總結
本文提出的 GraphGAN 是一種結合了生成模型和判別模型的框架。其中生成器擬合 Ptrue，判別器嘗試去判別兩個點之間是否有邊。
G 和 D 實際上是在進行一個 minmax game，其中 G 試圖去產生一些假的點。這些假的點不能被 D 所判別，而 D 試圖去將真實值跟假的點分別開來，以避免被 G 所欺騙。
此外，我們還提出了一種 Graph Softmax 作為 G 的實現，剋服了 softmax 和層次 softmax 的缺陷，具備三個良好性質。
GRL的其他應用
DKN 是我們發表在 WWW 2018 上的論文，它提出了一個可用於新聞推薦的 deep knowledge-aware network。在 DKN 中，我們將 KG 中的 entity embedding 和 word embedding 在一個 CNN 框架中加以結合，並且提出了一種 attention based 點選率預測模型。
第二個應用是 SHINE，這篇論文發表於 WSDM 2018。它的目的在於預測微博使用者對名人明星的情感。我們提出了一種基於自編碼器的框架，這個框架其實類似於 SDNE，將它應用於三者並加以結合進行情感預測。
>>>> 獲取完整PPT和影片實錄
關註PaperWeekly微信公眾號，回覆20180110獲取下載連結。
點選以下標題檢視往期實錄：
關於PaperWeekly
PaperWeekly 是一個推薦、解讀、討論、報道人工智慧前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號後臺點選「交流群」，小助手將把你帶入 PaperWeekly 的交流群裡。
