2017-Community Preserving Network Embedding
Paper:AAAI-2017
链接:Community Preserving Network Embedding
源代码:https://github.com/benedekrozemberczki/M-NMF
参考:
非负矩阵分解:
参考:
1. 摘要:
以前的网络嵌入文章侧重于保持microscopic structure,比如:first-/ second-order 成对节点之间的相似性。然而mesoscopic community structure也是网络中很重要的特征,却被忽略。基于此,
- 本文提出Modularized Nonnegative Matrix Factorization(M-NMF)模型,将社区结构考虑进节点嵌入里面。(对于first-/ second-order 相似性,采用非负矩阵分解进行学习表达;对于mesoscopic community structure,基于模块度矩阵约束进行社区检测;)使得学习出来的embedding能够同时保留节点对之间的结构相似性以及社区结构的特征。
- 作者探索了节点表示和社区结构之间的关系,然后基于表示学习模型和模块度社区检测模型联合优化NMF,能够同时保持microscopic和社区结构。
- 同时提出了multiplicative更新规则来学习模型参数,保证了正确性和收敛性。
- 节点聚类和节点分类两个网络分析任务证明了(M-NMF)模型的有效性和鲁棒性。
但是矩阵分解方法内存开销太大。
2. 引言:
传统的网络表达方法邻接矩阵只能表示网络的拓扑结构,并且邻接矩阵稀疏高维性且具有很高的噪声,表达效果差强人意。
文献【Wang, X.; Jin, D.; Cao, X.; Yang, L.; and Zhang, W. 2016. Semantic community identification in large attribute networks. In Thirtieth AAAI Conference on Artificial Intelligence.】说明了社区结构是很重要的网络特征,能够揭示网络中的组织结构和功能组件。
因此,如果学习的嵌入空间能够很好的反映原始网络中的社区结构是网络嵌入方法很关键的部分。
3. Related Work
NE:
回顾了DeepWalk、LINE、GraRep、TADW(文本信息)、结合label信息等网络嵌入方面的文章(这些文献没有考虑社区结构)。
回顾了社区检测方法:
社区检测综述:
Fortunato, S., and Hric, D. 2016. Community detection in networks: A user guide. arXiv preprint arXiv:1608.00163.
4. 本文算法M-NMF模型:
第一:建模社区结构(衡量社区结构的指标:模块度)
基于模块度矩阵的社区检测方法(模块最大化)广泛应用于社区检测(2006年,A包含两个社区,即k=2),模块度定义如下:
模块度矩阵B定义如下:其中ki是节点i的degree,e表示边的数目,hi和hj向量代表的是两者所属的社区,如果i在第一个社区,那么hi=1,否则hi=-1:
扩展向量h,使得模块度可以度量k>2个社区:
矩阵H的每一行,只有一个元素是1,其余元素都是0.(1的元素表明该节点属于ki的社区),则Q如下:
第二:建模microscopic结构
① first-order相似性建模:
② second-order相似性建模(节点的邻域相似度,采用两个节点邻域的cosine相似性来表示):
则结合first-order和second-order相似性之后,最终相似性矩阵S等于:
在NMF框架中,引入了非负的偏好矩阵M和非负的表达矩阵U(大小都是m*n),M的作用就是将矩阵U转换成大小为n✖n的矩阵,这样就可以计算损失函数了。
需要注意的是,该模型不局限于first-order和second-order相似性矩阵,也可以添加high-order相似性,则保留微观网络结构embedding的目标函数如下(3):【节点相似度和节点表示之间的误差】
有了矩阵S以后,引入社区结构的嵌入:
作者引入了辅助的非负社区表达矩阵C(大小是k*m),矩阵Cr的每一行表示第r个社区的m维表示向量。
如果一个node的表示和一个社区有很高的相似性,那么这个node就倾向于属于这个社区:
如果节点i的表达和社区r成正交,那么这个表达就完全不属于这个社区。可以采用下面这个公式来计算node i属于社区r的倾向性:
我们希望UCT(T表示矩阵C的转置)和community indicator matrix H越接近越好:
作者定义了一个社区表达矩阵C,在矩阵C的辅助下,我们将节点表达矩阵U,投影到community indicator H中,(矩阵H表示某一个节点属于某一个社区的矩阵,即节点-社区矩阵,每一行表示一个节点所属社区的one-hot编码)
表达矩阵U由microscopic结构(S)和mesoscopic community structure(H)共同约束。因此U会具有更多的区分性。
最终本文的目标函数如下(4):
α和β是正参数,最终得到的矩阵U的第i行就代表第i个节点的embedding结构。
5. 优化:(具体看论文)
目标函数(4)是非凸的,作者将公式(4)分为4部分子问题,并迭代优化这四部分(更新M、U、H和C),保证每一个子问题收敛到一个local最小值。
6. 实验评估:
① 节点聚类:
K-means进行聚类,但是K-means对初始值比较敏感,因此重复了20次(每一次都是一组新的初始中心),取平均结果如表格1所示。M-NMF一直比M-NMF0结果要好,说明结合社区结构来学习节点表达的重要性。
节点准确率的度量采用文献【Cai, D.; He, X.; Han, J.; and Huang, T. S. 2011. Graph reg- ularized nonnegative matrix factorization for data representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(8):1548–1560.】 的方法。
② 节点分类:
随机挑选80%的节点作为训练集,剩余20%作为测试集。采用LIBLINEAR包训练分类器。(重复5次,然后取平均值)
结果表明利用community indicator H来指导表示学习,能够提高准确率。H就类似于一个伪label,学习到的节点表示有更好的区分性。
M-NMF和M-NMF0相比,结果要好,同样说明结合社区结构来学习节点表达的重要性。
③ 参数分析:
节点聚类和节点分类的准确率随着参数的变化情况。
Fig1可以看出,准确率比较稳定,几乎没有什么大的变化。Fig1a 最差的准确率也达到43%,比其它方法要好。
α=0.5,β=5时,K从3-13准确率的变化情况。