網路表示學習(一)--結構篇
圖結構數據是除了圖片、文本、語音之外又一常見且重要的數據類型，例如社交網路數據、引用網路數據、和生物蛋白質數據等等。在針對圖像、文本等數據的機器學習任務中，都有相對應的方法，將這些數據中的特徵用一個稠密向量進行表示，然後再運用於各種各樣的任務中去。網路表示學習就是將網路中結點的特徵，嵌入(Embedding)至低位向量中的方法。學習到的這些向量將會保留圖結構數據結點的相似性，使得一些下游機器學習任務，例如結點分類、結點聚類、連接預測、可視化等等的模型泛化性能得到增強。
本文首先將會介紹網路表示學習最為著名的三份工作：DeepWalk、LINE和Node2Vec。
然後將會介紹兩篇在AAAI18上的兩篇網路結構表示學習的新工作HARP、GraphGAN
一、DeepWalk: Online Learning of Social Representations
DeepWalk可以稱得上是這個方向上最著名的工作了，幾乎所有網路表示學習相關的論文，都會引用DeepWalk作為Baseline之一，同時DeepWalk也是很多相關工作所使用的底層方法之一。可見這份工作在網路表示學習領域的地位。
1. Method
DeepWalk最主要的貢獻就是他將Network Embedding與自然語言處理中重要的Word Embedding方法Word2Vec聯繫了起來，使得Network Embedding問題轉化為了一個Word Embedding問題。
轉化方法其實很簡單，就是隨機遊走。如下圖所示，DeepWalk通過從每個結點出發n_walks次，每一步都採取均勻採樣的方式選擇當前結點的鄰接結點作為下一步的結點隨機遊走。當遊走的路徑長度達到walk_length後，停止一次遊走。這樣就生成了一個個遊走的序列，每個序列都稱為一個walk。每個walk都被當成Word2Vec中的一個句子，而每個結點都是Word2Vec中的一個詞。
之後的演算法幾乎和Word2Vec的Skipgram版本完全一樣。使用一個大小為window_size的滑動窗口作為一條walk的context，使用一個context中的中心詞去推測所有context中的其他詞，使用的目標函數也與Word2Vec一致。
2. Experiments
DeepWalk選擇Multi-Label Classification作為評價演算法Performance的指標。評價中將通過DeepWalk學習獲得的Embedding按照不同的比例劃分為訓練集與測試集。訓練集作為N個one-vs-rest對率回歸分類器的訓練數據，將其中置信度最高的k個類別作為結點的預測類別。其中N為類別的個數，k為結點的標籤數。
實驗結果如下所示：
二、LINE: Large-scale Information Network Embedding
雖然DeepWalk通過隨機遊走的方式，將圖結構數據轉化為了自然語言處理的任務來完成。但是，圖結構中節點的關係往往比詞上下文關係更加的複雜。通常部分的圖結構數據中邊具有權重，使用現有的Word2Vec方法無法很好的應對這個問題。此外，在現實世界數據中，圖的規模往往過於龐大，以至於存下所有的walk的開銷將十分驚人。
1. Method
LINE不再採用隨機遊走的方法。相反，他在圖上定義了兩種相似度——一階相似度與二階相似度。
- 一階相似度：一階相似度就是要保證低維的嵌入中要保留兩個結點之間的直接聯繫的緊密程度，換句話說就是保留結點之間的邊權，若兩個結點之間不存在邊，那麼他們之間的一階相似度為0。例如下圖中的6、7兩個結點就擁有很高的一階相似度。
- 二階相似度：二階相似度用一句俗話來概括就是「我朋友的朋友也可能是我的朋友」。他所比較的是兩個結點鄰居的相似程度。若兩個結點擁有相同的鄰居，他們也更加的相似。如果將鄰居看作context，那麼兩個二階相似度高的結點之間擁有相似的context。這一點與DeepWalk的目標一致。例如下圖中的5、6兩點擁有很高的二階相似度。
LINE的目標就是保留這兩種相似度。
- LINE的一階相似度
兩個結點實際的一階相似度表達如下：
其中W是所有邊權重之和。而兩個結點embedding之間的相似度為：
其中u是結點的embedding。即兩個結點表示的內積套上一個 對率函數的結果。這樣一來目標函數設為實際相似度與表示相似度之間的KL散度就可以了，這樣一來，只要最小化KL散度(下式中約去了一些常數)，就能保證表示相似度盡量接近實際相似度。
- LINE的二階相似度 兩個結點實際的二階相似度表達式如下：
其中wij是邊ij的權重，di是結點i的出度。兩個結點embedding的相似度為：
其中V為結點i的所有鄰居，這裡與一階相似度不同的地方是，對於鄰居結點，使用了另一組的embedding，稱作context。目標函數依舊是KL散度，也就是最終，擁有相似鄰居的結點，將會擁有相近的embedding。最終要獲得同時包含有一階相似度和二階相似度的embedding，只需要將通過一階相似度獲得的embedding與通過二階相似度獲得的embedding拼接即可。
2. Experiments
同樣也來看一下LINE在結點分類任務中的表現：
可以看到，當考慮到一階相似度之後，也就是邊的權重後，LINE的表現效果要略好於DeepWalk。
三、Node2Vec: Scalable Feature Learning for Networks
Node2Vec是一份基於DeepWalk的延伸工作，它改進了DeepWalk隨機遊走的策略。
1. Method
Node2Vec認為，現有的方法無法很好的保留網路的結構信息，例如下圖所示，有一些點之間的連接非常緊密(比如u, s1, s2, s3, s4)，他們之間就組成了一個社區(community)。網路中可能存在著各種各樣的社區，而有的結點在社區中可能又扮演著相似的角色(比如u與s6)。
Node2Vec的優化目標為以下兩個：
- 讓同一個社區內的結點表示能夠相互接近，或
- 在不同社區內扮演相似角色的結點表示也要相互接近。
為此，Node2Vec就要在DeepWalk現有的基礎上，對隨機遊走的策略進行優化。Node2Vec提出了兩種遊走策略：
- 廣度優先策略
- 深度優先策略
就如上圖的標註所示，深度優先遊走策略將會限制遊走序列中出現重複的結點，防止遊走掉頭，促進遊走向更遠的地方進行。而廣度優先遊走策略相反將會促進遊走不斷的回頭，去訪問上一步結點的其他鄰居結點。
這樣一來，當使用廣度優先策略時，遊走將會在一個社區內長時間停留，使得一個社區內的結點互相成為context，這也就達到了第一條優化目標。相反，當使用深度優先的策略的時候，遊走很難在同一個社區內停留，也就達到了第二條優化目標。
那麼如何達到這樣的兩種隨機遊走策略呢，這裡需要用到兩個超參數p和q用來控制深度優先策略和廣度優先策略的比重，如下圖所示。
假設現在遊走序列從t走到v，這時候需要算出三個係數，分別作為控制下一步走向方向的偏置α
其中d(t, x)代表t結點到下一步結點x的最短路，最多為2。
- 當d(t, x)=0時，表示下一步遊走是回到上一步的結點；
- 當d(t, x)=1時，表示下一步遊走跳向t的另外一個鄰居結點；
- 當d(t, x)=2時，表示下一步遊走向更遠的結點移動。
而Node2Vec同時還考慮了邊權w的影響，所以最終的偏置係數以及遊走策略為
這樣一來，就可以看出，超參數p控制的是重新訪問原來結點的概率，也就是保守探索係數，而超參數q控制的是遊走向更遠方向的概率，也就是激進探索係數。如果q較大，那麼遊走策略則更偏向於廣度優先策略，若q較小，則偏向於深度優先策略。
2. Experiments
多標籤分類任務中可以看出，當調整好適當的p、q值之後，Node2Vec的效果要略好於DeepWalk
四、HARP: Hierarchical Representation Learning for Networks
上面介紹了DeepWalk、LINE、Node2Vec三個網路表示學習中最為著名的三種演算法。但是，這三個演算法都有一個共同的弱點，那就是他們所捕捉的網路結點關係過近，都是局部鄰居。LINE僅僅只考慮到了一階鄰居與二階鄰居之間的相似度關係。DeepWalk與Node2Vec雖然可以通過隨機遊走，獲得較長的遊走序列，但是遊走的長度比起現在圖數據的規模，隨機遊走的長度還是太短了。所以就需要想一種方法捕捉全局的相似度。
1. Method
HARP採取的方式就是通過多次摺疊，將原來的大圖層層收縮為較小的圖，使得通過較短的隨機遊走距離，能夠覆蓋所有的，然後將小圖作為上面三個演算法的輸入，學習Embedding。在將收縮後的小圖被學習到的Embedding，作為摺疊前的的圖的Embedding的初始化，繼續將摺疊前的圖輸入到表示學習演算法之中。最終再層層學得原來大圖的Embedding。HARP的演算法流程如下圖所示。
圖摺疊演算法
那麼要理解HARP這個演算法的關鍵，就在於圖摺疊演算法。HARP的圖摺疊演算法，主要有以下兩種方法
- 邊摺疊 (Edge Collapsing)邊摺疊演算法選擇儘可能多的邊，這些邊沒有共同的頂點，即每個頂點只有一條與之連接的邊被選中。然後，如下圖(a)所示，這些邊被摺疊成為一個結點，成為了摺疊後的新結點。
- 星摺疊 (Star Collapsing)雖然邊摺疊在最好的情況下每一輪摺疊可以將結點的數量縮減一半，這樣一來圖摺疊演算法的總次數為O(logk)。但在某些特殊情況下卻不能很好的發揮作用。如下圖(b)所示，星形結構是網路中最常見結構之一，在這種結構中，如果使用邊摺疊演算法，那麼就至多隻能摺疊一條邊，演算法要執行的總次數則會退化為O(k)。所以，HARP採用了另外一種摺疊策略，就是星摺疊。如下圖(c)所示，星狀網路中有兩種結點，中心結點和周圍節點，星摺疊方法就是將同一個中心結點的周圍結點兩兩配對，摺疊成一個結點，來盡量減少星狀結構的周圍結點，以增強邊摺疊的效率。
HARP在每次摺疊的時候，先是使用星摺疊減少星形結構，然後再執行一次邊摺疊。具體的圖摺疊演算法流程如下面的偽代碼所示。
2. Experiment
通過HARP的多標籤分類結果可以看出，使用HARP的圖摺疊和層級訓練的手段後，相較於其相應的底層演算法，都有一定的提升。實際上，經過我本人的實驗，在更大規模的圖上(結點數量達到數十萬甚至上百萬時)，這樣的提升將會更加明顯。
五、GraphGAN: Graph Representation Learning with Generative Adversarial Nets
GraphGAN這份工作，顧名思義，就是嘗試使用生成對抗網路(Generative Adversarial Nets, GAN)來增強網路表示學習的表現。
1. Method
要是理解GAN，那麼GraphGAN的大題模塊及其作用應該就能夠很容易地想到。GraphGAN一共包含兩個主要的模塊：
- 判別器 由於Network Embedding任務大多是無監督，結點本身不帶有任何標籤，所以判別器要判別的就是網路自身帶有的信息，也就是連接信息。GraphGAN中的判別器實際上就是一個連接預測器，通過輸入兩個結點的Embedding來判定兩個結點之間是否存在一條邊。
- 生成器 生成器的作用就是通過合理的方式生成一些點對，然後將這些點對輸入到判別器中，盡量讓判別器將這兩個點對誤認為是在圖上存在邊的兩個結點的Embedding。
之後的訓練過程就是生成器與判別器較量的過程。生成器不斷調整每個結點的Embedding以及自己的參數，使得按照自己的規則生成出來的兩個就節點對能夠被判別器判別成為存在連接。而判別器則通過調整自身的參數，使自己能夠準確的將圖中實際存在邊的結點對判定為true而將生成器生成的結點對判定為false。他們兩個共同組成GraphGAN的目標函數：
2. Implemention
那麼GraphGAN中的判別器與生成器具體是怎麼實現的呢？
前面介紹的DeepWalk、LINE、Node2Vec等方法都是先獲得一些context，然後通過訓練使得這些結點的Embedding相互接近，然後通過隨機的負採樣得到一些負樣本，讓這些負樣本的結點之間的Embedding相互遠離。事實上GraphGAN的判別器與前面工作的context訓練非常相似，也是讓ground truth的Embedding相互接近，讓生成器生成的節點對的Embedding相互遠離。
這樣一來生成器看似是代替了原來負採樣的過程，然而生成器卻需要能夠生成與ground truth盡量相似的數據，這就與原來的負採樣不太一致。那麼這是為什麼呢？
產生這樣疑惑的原因是我們從以判別器為主的角度來看待這個模型。如果我們從生成器的角度來理解這個模型的時候，這些疑惑就會得到解釋。判別器僅僅只是作為訓練時的目標函數的實現，它起到的作用有兩個，一是讓ground truth相互接近，另外一個就是給生成器提供損失函數。而一個經過精心設計的生成器，就可以利用這樣的損失函數，訓練出我們需要的Embedding。
下面就來介紹一下GraphGAN的生成器是如何工作的。
首先，生成器要遵守以下三個原則：
- Normalized，即所有結點被當作負樣本的概率之和為1；
- Graph-structure-aware，結點被選中負樣本的概率隨著據中心結點的最短路增大而減小；
- Computational efficient，不能針對所有結點來計算softmax，只能關聯到一個結點的小子集。
演算法開始前，需要生成每個結點的BFS樹，然後為了選取某一個結點的負採樣，需要沿著該結點的BFS樹向下或向上遍歷。從某個父節點轉移到它的子節點或父節點的概率為：
然後，一個結點最終被選取為起始結點的負樣本的概率為：
以下圖為例子，給定一個圖，現在要從vc這個點開始負採樣，那麼先以vc為根生成BFS樹。然後再算出每個結點與其子結點的轉移概率，通過這個概率採樣子節點，直到哪個結點被遍歷了兩次，結束。輸出這個重複遍歷的結點作為負樣本。這個遍歷過程中涉及到的所有其他結點(綠色結點)都要在訓練中訓練到。
這樣的作法複合上面提出的三種原則，論文中給出了詳細的證明。
3. Experiment
同樣來看看GraphGAN的多標籤分類的實驗結果
六、總結
本文介紹了幾種針對網路結構進行表示學習的方法，首先是DeepWalk、LINE、Node2Vec三個最為著名的工作。之後介紹了近兩年的一些針對網路結構的網路表示方法HARP和GraphGAN，瞭解近些年針對結構的網路表示學習的一些新思路。但是，現實中的網路中的內容遠遠不止結構這麼簡單。網路中的結點可能有不同的類別，每種結點又可能有不同的屬性。所以，還需要有針對利用網路中其他信息的相關研究。
七、參考文獻
[1] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014: 701-710.
[2] Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, 2015: 1067-1077.
[3] Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016: 855-864.
[4] Chen H, Perozzi B, Hu Y, et al. Harp: Hierarchical representation learning for networks[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
[5] Wang H, Wang J, Wang J, et al. Graphgan: Graph representation learning with generative adversarial nets[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
推薦閱讀：
