Community Preserving Network Embedding閱讀報告

02-21

轉載請註明出處：

每周一篇機器學習論文筆記zhuanlan.zhihu.com

論文來源：AAAI-2017

論文鏈接：Community Preserving Network Embedding

論文原作者：Xiao Wang, Peng Cui, JingWang, Jian Pei, Wenwu Zhu, Shiqiang Yang;

（侵刪）

Abstract

Network Embedding 是一種用於輔佐網路分析(network analysis)的方法，它的主要目的是為了學到網路中節點的相對低維且有效的表達，從而取代鄰接矩陣這種高維且高雜訊表達方法。作者認為，很多network embedding方法把重心放在了保留網路結構，但是沒有考慮過保留網路中社區結構的重要性。因此為了能夠讓embedding出來的結果能夠保留這兩種特性，作者提出了一種基於矩陣分解的模型，Modularized Nonnegative Matrix

Factorization (M-NMF)。M-NMF 通過非負矩陣分解來學習網路結構特徵，利用模塊度的矩陣表達公式來約束學出來的特徵的社區結構，從而做到學到的表達兩者皆不誤。

Introduction

該部分首先介紹了傳統表達方法的問題：

網路分析很大程度上依賴於節點的表達，而傳統的表達方法如鄰接矩陣通常只能表示出網路的拓撲結構，而無法表達出節點所代表的更深層的意義
傳統的表達方法往往回面臨維度高，數據稀疏，高雜訊等問題，導致效率和效果都大打折扣

從上述兩點可以看到，network embedding引入的目的就是為了能夠讓節點的表達不僅具有更豐富的意義，還要降低維度從而降低稀疏性和雜訊問題。通俗一點就是盡量地短小精悍。

然後作者回顧了近幾年的論文，發現大部分論文學習低維表達的時候都很注重微觀網路結構，即保留節點與節點之間的關係，但是並沒有注意到比較宏觀的社區結構。直觀上來說，一個社交網路中，除了節點之間的交互關係之外，不同的用戶自然也會形成不同的群體，因此，作者認為無論如何，社區屬性對於一個網路來說都是不可或缺的。

基於此，作者提出了能夠既保留結構屬性，有保留社區屬性的方法 M-NMF。

該文章的貢獻如下：

提出了M-NMF，該方法能保留網路結構和社區結構
提出了高效更新M-NMF的優化公式，並且證明了是可收斂的
在9個數據集上驗證了通過M-NMF學出來的特徵在節點劃分、節點聚類兩種方法中都非常可觀

Algorithm

網路結構的保留可以利用一階相似度(first-order proximity)和二階相似度(second-order proximity) [1] 甚至高階相似度(high-order proximity) [2] 來實現，但是如何保留社區結構呢？

首先便是要像網路結構一樣，找到一個衡量社區結構的指標。幸運的是，早在2004年就提出了模塊度（Modularity）[3] [4]

$Q=frac{1}{2e}sum_{ij}[A_{ij}-frac{k_ik_j}{2e}]delta(h_i,h_j)=Tr(H^TBH)$

上面的公式中， $A_{ij}$ 值得是節點 i, j是否相鄰， $k_i,k_j$ 代表的是點i, j的度數， $e$ 代表的是邊的數目， $h_i,h_j$ 向量代表的是兩者所屬的社區， $delta(cdot,cdot)= egin{cases} 1 &mbox{if $h_i = h_j$}\ 0 &mbox{otherwise} end{cases}$ 。

左邊的公式可以推到出右邊的表達形式，其中矩陣 $H$ 各行代表的是各節點所屬社區。 $B_{ij}=A_{ij}-frac{k_ik_j}{2e}$ （模塊度的意義在這裡就不贅述了）

那麼找到衡量指標之後，下一步便是如何結合網路結構和社區結構的衡量指標，從而構成一個相互制約的損失函數。

作者敏銳地察覺到模塊度的矩陣表達形式可以作為嫁接模塊度和特徵學習的橋樑，因此提出了矩陣分解這種方法。

作者所提供的大致步驟如下：

網路結構：通過節點的一階相似度+二階相似度構造相似度矩陣S

一階相似度矩陣：一階相似度描述的是兩個節點之間的直接關係，作者通過鄰接矩陣來代表一階相似度矩陣。 $S^{(1)}=A$
二階相似度矩陣：二階相似度描述的是兩個節點的鄰居的相似度，作者利用鄰接向量的餘弦相似度描述 $S^{(2)}=frac{mathcal{N_i}mathcal{N_j}}{Vertmathcal{N_i}Vert Vertmathcal{N_j}Vert}$
網路結構矩陣通過兩者加權的形式得到： $S=S^{(1)}+eta S^{(2)}$
保留網路結構的network embedding目標方程：

$mathop{min}_{M,U}Vert S-MU^TVert_{F}^2$

根據作者的定義，M是一個偏好矩陣（文中沒有詳細的解釋），U是節點的表達矩陣

社區結構：模塊度公式+矩陣分解

從網路結構的矩陣分解公式中可以知道，U是節點的表達矩陣，因此U不能只從S矩陣中學到結構特徵，還要和結合模塊度學到社區特徵。恰好模塊度公式中的H代表的意義是節點-社區矩陣，現在有了節點特徵矩陣U，作者再定義一個社區特徵矩陣C，從而得到以下目標方程：

$alphamathop{min}_{H,U,C}Vert H-UC^T Vert_{F}^2-eta Tr(H^TBH)$

最後，將兩者結合起來，得到最終的目標方程：

$mathop{min}_{M,U,H,C}Vert S-MU^TVert_{F}^2+alphaVert H-UC^T Vert_{F}^2-eta Tr(H^TBH)$

得到目標方程之後，作者通過輪流更新M, U, H, C來優化方程，最後，U內第i行的行向量代表的就是第i節點的embedding結果。（優化過程很複雜，這裡就不po上來了，大家有興趣可以看看作者的論文）

實驗結果

在聚類方法中的準確率

2. 在分類問題中的準確率

實驗數據集在論文中有給出描述以及下載鏈接~

個人看法

從公式中我們可以看到，作者通過引入一個新的「社區表達矩陣」C，結合「節點表達矩陣」U，通過矩陣分解的方法來結合模塊度公式中原有的「社區矩陣」H，這樣一來，embedding的過程中使用模塊度公式來約束社區結構。但是這種方法引入的假設變數有點多，雖然實驗效果不錯，但解釋起來始終有些牽強。同時，根據[5]中所說，矩陣分解方法需要開的內存太高，難以針對大規模數據。

[1] 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.

[2] Cao S, Lu W, Xu Q. Grarep: Learning graph representations with global structural information[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, 2015: 891-900.

[3] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133.

[4] Newman M E J. Modularity and community structure in networks[J]. Proceedings of the national academy of sciences, 2006, 103(23): 8577-8582.

[5] Zhang D, Yin J, Zhu X, et al. Network Representation Learning: A Survey[J]. arXiv preprint arXiv:1801.05852, 2017.