本次要總結和分享的論文是 LINE: Large-scale Information Network Embedding，其鏈接 論文^[1]，所參考的實現代碼 code^[2]，這篇論文某些細節讀起來有點晦澀難懂，不易理解，下面好好分析下。

論文動機和創新點

• information network 在現實世界中無處不在，例如最常見的社交網絡圖。而這種網絡通常包含 百萬以上的節點和數以十億記的邊，如果能將這種高維復雜的網絡映射(降維) 到低維空間內，用于可視化、節點分類、預測、推薦等相關任務，則能產生巨大的商業和學術價值，而本論文就旨探討如何將高維的信息網絡 映射(降維）到低維空間內。

• 現實中的信息網絡十分復雜，通常包含 百萬以上的節點和數以十億記的邊，對于如此復雜龐大的圖結構，目前大多數的圖嵌入方法都不可行。

• 由此本文提出一種高效的網絡表征學習方法，對于有向/無向、有權重/無權重的圖都可適用，且可在單機器上、數小時之內完成對 包含百萬以上的節點和數以十億記的邊的圖網絡的 embedding 學習。

• 本論文所提方法 能保存 局部和全局的網絡結構信息，并且提出了高效的優化技巧，使得能對包含百萬節點的圖進行學習。局部網絡結構信息：節點間的一階近似性（first-order proximity） 全局網絡結構信息：節點間的二階近似性（second-order proximity） 優化技巧：edge-sample，negative-sample

• 與 DeepWalk 類似深度優先搜索相比，Line 更像一種廣度優先搜索，對于取得二階相似性，廣度更加合理。并且 Line 適用于帶權圖，而 DeepWalk 不適用。

LINE 主要內容

圖結構的定義

上述公式中?表示 節點集合，?表示邊集合，對每天邊上的權重??表示節點?和?的關系強弱，若是無向圖則?，反正則不相等。注意本論文只探討邊權重?的情況。如上所描述的圖 G 基本上可以囊括現實世界中的信息網絡。

一階相似性（first-order proximity）

對于圖中任意兩個節點,??都可以由邊進行連接，如果在圖中兩節點有邊則?，否則等于 0，這種定義也是符合現實邏輯的，在 information network 中，如果兩個用戶存在連接關系，則該兩個用戶的性格、興趣等可能存在相似性、如果兩個網頁存在連向彼此的鏈接，則該網頁內容可能存在相似性等等。在這里可以假設有一條無向邊?，其兩節點?的聯合概率可以定義如下：

由此我們可以得到在?空間上的概率分布?經驗概率分布可以定義為

其中??，由此可以的帶??上的經驗概率分布??論文提到要讓?這兩種分布 KL 散度距離越近越好，去掉一些常數，由此可得到 一階相似的損失函數：

論文里提到這種一階相似性只能應用在無向圖中，不適用有向圖，這里也可理解，按照一階相似度計算，不可能存在?與??相似 不等于??與??相似度。

那么問題來了，為何按照公式(3) 的優化方向，得出來的節點?的表示向量?真的與節點?的表示向量?就真的如 如期的那樣相似或者不相似呢？這點論文中并沒有解釋，可能是個常識性知識，但是仍值得探討下， 假設?很大，這說明實際中，節點?與??很相似，那么按這公式(3) 優化，也應該很大，則??也應該很大，則按照余弦相似度計算，則向量??與??的夾角很小，則該?與??很相似，這就符合如期了。

這里還有一個問題：由公式（1）計算出的?里面每個概率值都是有 sigmoid 計算出來的，整體并不是一個標準概率分布，因為?很有可能性發生，嚴格上來說?并不是一種分布。而?是一定的。這個問題不知如何解釋？

二階相似性（second-order proximity）

但是如果僅僅根據兩節點是否存在直接相連的邊來判斷相似性，顯然是不夠的，例如兩個用戶雖然沒有直接相連，但是他們卻存在大量共同好友，由常識也知道認為這兩用戶是相似的，但是他們的一階相似性卻為 0。由此定義二階相似性：兩節點各自相鄰節點的一階相似性。可解決一階相似性的稀疏問題。

因為二階相似性要在有向圖上適用，故對每個節點，有兩個角色要扮演：① 自身角色 ② 相對別的節點，節點作為上下文角色。例如對于有向邊，在給定節點?的情形下，?節點需要承擔上下文角色。每個節點都有兩個角色，每個角色都有兩個表示向量。例如節點?的表示向量?和上下文表示向量?。由此可得在給定?情形下，?的表示向量：

上式中??表示所有節點數量。那么對于每個節點，都可以得到一個概率分布?。同樣論文中也提出了二階的經驗分布：

其中，?表示節點?的出度，由此得到二階經驗分布??同樣去掉一些常數，可得二階相似性的損失函數：

到這來，可能有人要問，這種二階相似性計算，如何體現 “兩個節點擁有相似的相鄰節點，則該兩個節點肯定有相似性”，論文中對此也沒有任何解釋，可能是個比較常識性的問題，但是我認為仍值得深入解釋一下，這里提出我個人的想法：試想一下，在公式(4)中??與?相鄰，并且?不斷對與他相鄰的節點?施加影響，也就是相鄰節點間相互影響，并且不斷沿著邊向四周傳播影響，如果兩個節點擁有相似的鄰接點，那么這兩個節點受到的影響也是一致的，鄰接點越相似，所受的影響就越一致。

可能又有人問，為啥二階弄個上下文向量，試想一下，在公式(4)中，如果?為?，那么?與??就相等了，那么就沒有方向上的區別了。

優化技巧

邊采樣

論文里提到對于一個龐大復雜的帶權有向圖，其邊權重的方差可能是很大的，難以訓練優化，論文中提出可將每個帶權邊拆解成多個權重為?的邊。但是這樣做，圖將變得非常復雜，對機器的 memory 要求將會劇增。為了緩解這個問題，可以對邊進行帶概率（相同兩節點邊出現頻次/ 總邊數）的采樣（即采樣出的樣本服從原始樣本分布）。論文中提出使用 alias method 方法進行采樣。該方法查找時間復雜度 O(1)，但是建表時間復雜度 O(n)，但是只需建一次即可。詳情可看 alia-method^[3]。這樣就完成了對邊的采樣。

節點負采樣

與 NLP 中的 word2vec 所遇到的問題類似，對于公式(4) 來說，分母需要遍歷節點圖中的所有節點，這樣計算量可能非常巨大，因此需要采樣部分負節點，來組成負樣本，那么公式(4)可轉化成如下：

對于上面公式中的求和下標?，個人感覺改成?應該較好理解些。上式相當于把節點?與??作為一對正樣本(label=1)，而節點?與每個采樣得到的節點組成的??作為負樣本（label=-1），故里面有個負號。有正有負，有變大有變小才能優化。

在實寫代碼時，只需要將每對 pairwise 做內積乘以 label 再做 log_sigmoid，再對所有 pairwise 求和取負，再 minimize 即可。

同理在公式(3) 里面，也需要對沒有邊相連的節點進行采樣，作為負樣本，這樣 有正有負，有變大有變小才能優化。

所以對一階相似與二階相似做完負采樣后，兩者損失函數一致了，不同的是對于一階相似，需將公式(7) 中的?成?，實寫代碼時也是。

關鍵代碼

class LINEModel:def __init__(self, args):self.u_i = tf.placeholder(name='u_i', dtype=tf.int32, shape=[args.batch_size * (args.K + 1)])self.u_j = tf.placeholder(name='u_j', dtype=tf.int32, shape=[args.batch_size * (args.K + 1)])self.label = tf.placeholder(name='label', dtype=tf.float32, shape=[args.batch_size * (args.K + 1)])self.embedding = tf.get_variable('target_embedding', [args.num_of_nodes, args.embedding_dim],initializer=tf.random_uniform_initializer(minval=-1., maxval=1.))self.u_i_embedding = tf.matmul(tf.one_hot(self.u_i, depth=args.num_of_nodes), self.embedding)if args.proximity == 'first-order':self.u_j_embedding = tf.matmul(tf.one_hot(self.u_j, depth=args.num_of_nodes), self.embedding)elif args.proximity == 'second-order':self.context_embedding = tf.get_variable('context_embedding', [args.num_of_nodes, args.embedding_dim],initializer=tf.random_uniform_initializer(minval=-1., maxval=1.))self.u_j_embedding = tf.matmul(tf.one_hot(self.u_j, depth=args.num_of_nodes), self.context_embedding)self.inner_product = tf.reduce_sum(self.u_i_embedding * self.u_j_embedding, axis=1)self.loss = -tf.reduce_mean(tf.log_sigmoid(self.label * self.inner_product))self.learning_rate = tf.placeholder(name='learning_rate', dtype=tf.float32)# self.optimizer = tf.train.GradientDescentOptimizer(learning_rate=self.learning_rate)self.optimizer = tf.train.RMSPropOptimizer(learning_rate=self.learning_rate)self.train_op = self.optimizer.minimize(self.loss)

由上面代碼可以看出 當選擇一階相似性時：節點?是從??矩陣里取表示向量，模型也只更新??矩陣；當選擇二階相似性時：節點?是從??矩陣里取表示向量，模型會更新??矩陣；

class DBLPDataLoader:def __init__(self, graph_file):self.g = nx.read_gpickle(graph_file)self.num_of_nodes = self.g.number_of_nodes()self.num_of_edges = self.g.number_of_edges()self.edges_raw = self.g.edges(data=True)self.nodes_raw = self.g.nodes(data=True)self.edge_distribution = np.array([attr['weight'] for _, _, attr in self.edges_raw], dtype=np.float32)self.edge_distribution /= np.sum(self.edge_distribution)self.edge_sampling = AliasSampling(prob=self.edge_distribution)self.node_negative_distribution = np.power(np.array([self.g.degree(node, weight='weight') for node, _ in self.nodes_raw], dtype=np.float32), 0.75)self.node_negative_distribution /= np.sum(self.node_negative_distribution)self.node_sampling = AliasSampling(prob=self.node_negative_distribution)self.node_index = {}self.node_index_reversed = {}for index, (node, _) in enumerate(self.nodes_raw):self.node_index[node] = indexself.node_index_reversed[index] = nodeself.edges = [(self.node_index[u], self.node_index[v]) for u, v, _ in self.edges_raw]def fetch_batch(self, batch_size=16, K=10, edge_sampling='atlas', node_sampling='atlas'):if edge_sampling == 'numpy':edge_batch_index = np.random.choice(self.num_of_edges, size=batch_size, p=self.edge_distribution)elif edge_sampling == 'atlas':edge_batch_index = self.edge_sampling.sampling(batch_size)elif edge_sampling == 'uniform':edge_batch_index = np.random.randint(0, self.num_of_edges, size=batch_size)u_i = []u_j = []label = []for edge_index in edge_batch_index:edge = self.edges[edge_index]if self.g.__class__ == nx.Graph:if np.random.rand() > 0.5: # important: second-order proximity is for directed edgeedge = (edge[1], edge[0])u_i.append(edge[0])u_j.append(edge[1])label.append(1)for i in range(K):while True:if node_sampling == 'numpy':negative_node = np.random.choice(self.num_of_nodes, p=self.node_negative_distribution)elif node_sampling == 'atlas':negative_node = self.node_sampling.sampling()elif node_sampling == 'uniform':negative_node = np.random.randint(0, self.num_of_nodes)if not self.g.has_edge(self.node_index_reversed[negative_node], self.node_index_reversed[edge[0]]):breaku_i.append(edge[0])u_j.append(negative_node)label.append(-1)return u_i, u_j, labeldef embedding_mapping(self, embedding):return {node: embedding[self.node_index[node]] for node, _ in self.nodes_raw}

上述代碼中的圖已假定邊權重均為 1，相當于已經對帶權重的邊進行了拆解了多條二元邊；首先進行 邊采樣，然后再對節點進行了負采樣，負采樣得到?的?均為-1。

個人總結

• 本論文剛剛讀起來，有點晦澀難懂，總覺得有些地方不嚴謹。但是仔細推敲下，貌似沒啥大問題

• 論文讀起來感覺很復雜的樣子，但是代碼真的挺簡單的。

參考資料

[1]

論文: http://www.www2015.it/documents/proceedings/proceedings/p1067.pdf

[2]

code: https://github.com/snowkylin/line

[3]

alia-method: %28https://blog.csdn.net/haolexiao/article/details/65157026%29

關于本站

“機器學習初學者”公眾號由是黃海廣博士創建，黃博個人知乎粉絲23000+，github排名全球前100名（33000+）。本公眾號致力于人工智能方向的科普性文章，為初學者提供學習路線和基礎資料。原創作品有：吳恩達機器學習個人筆記、吳恩達深度學習筆記等。

往期精彩回顧

• 那些年做的學術公益-你不是一個人在戰斗

• 適合初學者入門人工智能的路線及資料下載

• 吳恩達機器學習課程筆記及資源（github標星12000+，提供百度云鏡像）
  

• 吳恩達深度學習筆記及視頻等資源（github標星8500+，提供百度云鏡像）

• 《統計學習方法》的python代碼實現（github標星7200+）

• 機器學習的數學精華（在線閱讀版）
  

備注：加入本站微信群或者qq群，請回復“加群”

加入知識星球（4300+用戶，ID：92416895），請回復“知識星球”

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的员外带你读论文：LINE: Large-scale Information Network Embedding的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。