前言
本篇繼續GraphEmbedding旅途，來聊聊LINE這個方法，對應的paper為《LINE: Large-scale Information Network Embedding》。
---廣告時間，歡迎關注本人公衆号：
LINE的核心方法
首先，還是先來腦補一下LINE方法的思考過程：
相似度&距離
在上一篇中，我們已經知道DeepWalk是采用類似于Word2Vec的方法，用一個節點的鄰居序列來儲存節點在網絡中的拓撲結構，使得圖中距離較近的節點在新的向量空間中也有較近的距離，但确實沒有顯示化地定義一個距離相似度的目标函數，也不是基于對目标函數的求解來得到向量表達的。LINE方法則明确定義一個量化的相似度計算公式，而且不僅包含一階相似度，還包括了二階相似度。
一階相似度通常就是節點之間直接相連的邊，可以用邊的權重來度量。二階相似度其實也容易了解，就是兩個節點很可能沒有邊相連，但它們有很多共同的鄰居節點，如下圖所示：
事實上，我們回想一下DeepWalk的方法，也可以捕捉到5，6兩個節點的鄰居相似性對吧？但因為DeepWalk本身沒有引入節點之間邊的權重，是以較難量化6，7之間的直接相似度大小。
具體地，LINE對一階、二階相似度的定義如下所示：
事實上，**這仍然是在圖上的距離表示**，在新的向量空間中，作者并沒有給出明确的距離公式，反而是用機率分布函數來論述的。一階、二階的機率密度函數分别如下：
但為什麼是這樣？不知道。網上也沒有找到推導過程。甚至我猜想作者在思考的過程中是反過來的，即：
需要保留節點之間的相似度 -> 怎麼衡量相似度呢？想到了KL散度方法來表達兩個機率分布之間的相似度 -> 節點在圖上的相似度用機率分布很好構造，但新的向量空間中的相似度怎麼定義呢？ -> 找一個随着向量距離大小遞增的、介于0-1區間範圍的函數吧 -> 哎呀，想到了sigmoid函數(一階)、softmax函數（二階）。
除了歸因于靈光一現+打怪經驗，我沒有猜出來為啥會這樣設計。
目标函數
有了分布的表達後，分别定義了一階、二階情況下的KL散度：
事實上，這些形式與交叉熵完全一緻。是以也有很多人在刻畫兩個分布的差異性時直接用交叉熵，因為求極值的情況下，有一堆常數項是可以拿掉的。
優化方法
定義了上述的目标函數後，LINE還使用了一些降低計算量的優化技巧，而這樣技巧同樣是借鑒自文本處理領域。
對于二階相似度的KL散度目标函數而言（公式如下），
這個與DeepWalk當中在神經網絡的輸出層面臨softmax函數計算的問題何其相似啊。還記得嗎，它使用了Hierarchical Softmax來降低計算量，然後文獻\[4\]又找到了一種新的方法，稱為NEG（在Noise Contrastive Estimation的基礎上做了簡化，做了Negative sampling），并定義了一個目标函數如下圖所示：
LINE方法就是直接借用了這個想法，定義了如下所示的一個目标函數：
這個方法的本質是要将目标向量從一個噪聲分布中識别出來。但是在優化該目标的過程中，又涉及到邊采樣的問題，又引入了一個alias table的機率抽樣方法，這是一個很有趣的方法，具體原理可參考5、6兩個附錄的資料。
最終的向量化表示
事實上，LINE方法是分别求解了一階、二階相似度目标函數後，得到了兩個向量化表示，然後進行了合并。
看github上LINE的代碼，可以知道其實就是把兩個向量串聯拼接了起來：
個人感覺
其實LINE這個方法并不簡潔，雖然對于圖上節點之間的相似度定義還蠻直覺的，但是接下來轉化為優化問題求解的過程還是挺費解的，先轉換為機率分布之間的距離，後續過程中又使用了較多的優化技巧，有一種慕容功夫博采衆長的感覺，反倒不及DeepWalk那種一套降龍十八掌打下來的完整感和暢快感。
參考資料
1. [https://arxiv.org/abs/1503.03578]
2. [https://github.com/tangjianpku/LINE]
3. A. Q. Li, A. Ahmed, S. Ravi, and A. J. Smola. Reducing the sampling complexity of topic models. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 891–900. ACM, 2014.
4. T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, pages 3111–3119, 2013.
5. [https://www.keithschwarz.com/darts-dice-coins/]
6. [https://www.wangliguang.cn/?p=9]