Implementation of M-NMF

发表于 | 分类于

本文的主要目的是实现论文Community Preserving Network Embedding(Xiao Wang)中提到的M-NMF算法。在作者个人主页可以下载该论文，并且有论文算法的matlab版demo code提供下载。

算法简介

算法背景

Network Embedding，其主要目的是学习网络中结点的低维向量表示，而其基本的要求之一是能够保存网络的结构信息和内在信息。如今大多的网络嵌入方法主要保存网络的微观(microscopic)结构，如一阶亲密度和二阶亲密度（具体含义在之后进行介绍），而往往忽略了细观(mesoscopic)结构。具体来说，多数网络嵌入方法更关注网络的微观结构，即网络结点中成对的关系或者相似度，而往往忽略了社区结构描述这一重要性质。许多拥有多个社区的网络，往往在相同社区之间的结点有密集连通，而社区之间的连通则相对稀疏，因此社区之间的结构同样需要引起我们学习的关注。

另外，细观社区结构在结点表达方面比微观结构有着更多的限制，比如在同一社区内的结点应该比在其他不同社区的结点更相似；在同一社区中的两个结点，即使他们在微观结构中为弱连接，他们的亲密度仍可通过社区结构而增强。

为了解决社区结构被忽视的问题，本文作者提出了M-NMF算法，即模块化非负矩阵分解模型，能够同时保存网络的微观(microscopic)结构和细观(mesoscopic)结构。M-NMF是基于非负矩阵分解（NMF）框架的网络嵌入方法。具体而言，它通过最大化模块性来发现社区结构，并且通过NMF来学习结点的表示。

算法内容

对社区间结构进行建模——Modularity

作者在M-NMF算法中使用了模块度这一指标，用于建立社区结构。具体而言，给定具有两个社区的网络，其模块度定义如下(Newman 2006b):

image.png

其中，Aij即为网络的矩阵表示，ki为结点i的度，而如果结点i属于第一个网络，那么hi=1，反之为-1。而(k_i*k_j)/2e则为结点i和j之间我们所期望的边的数量。作者使用模块度矩阵B来替代上述式中的项，即B_ij=A_ij-(k_ik_j)/2e。因此我们有Q=1/4e**h‘ Bh**，其中h=[h_i]∈R^n为社区成员指标。

为了将两个社区拓展为多个社区，作者将社区成员指标扩展成H∈R^(n×k)，其中每一社区为一行，为了保证每个结点只能被划分到一个社区，因此添加了限制tr(H^T H)=n（tr(X)是指矩阵X的迹，即主对角线（从左上方至右下方的对角线）上各个元素的总和）。因此最终我们有新的模块度表达如下：

image.png

我们要做的就是尽量最大化模块度，使得社区结构更为明显。

对社区内结构进行建模

  • 一阶亲密度

image.png

简单来说，即如果两个结点之间存在边，则亲密度为1，否则为0。因为一阶亲密度是网络最直接的信息，因此需要进行保存。然而，真实网络中的边往往是稀疏的，经常会出现两个结点共同连接许多相同的邻居，但却没有互相连通的情况，因此需要考虑二阶亲密度。

  • 二阶亲密度

image.png

作者使用矩阵image.png来保存结点i与其他结点之间的一阶亲密度。使用余弦相似度来计算二阶亲密度，可得如下公式：

image.png

  • 保存机制

为了能够同时保存上述两个亲密度，作者使用最终的相似度矩阵image.png，其中η为二阶亲密度的权重。随后，作者使用非负矩阵分解框架NMF来对矩阵S进行分解，分解为基矩阵M和表达矩阵U，以达到降维的效果。因此得到以下损失函数：

image.png

该损失函数越小，则说明我们非负矩阵分解（降维）的效果越好。

统一化network embedding模型

由于我们需要将上述社区结构和社区内结构两种模型统一起来，因此需要提供一个中介。本文作者使用了一个辅助矩阵C，其中C的每一行是每个社区的表达。而在作者的观点来看，如果一个结点i的表达与某个社区r即为相似，那么该结点很可能就属于该社区，因此其将这种结点的社区倾向表示为U_iC_r（这里的U中的每一行是指通过非负矩阵分解后每个结点的表达）。

如果结点表达与社区表达完全正交，说明两者完全不同。而我们在之前就已经介绍了社区成员指标H（指示结点属于哪个社区），因此需要尽可能使得UC’与H一致。最终，我们有以下目标函数：

image.png

整个M-NMF模型的简要概述可以用作者个人网页上的图进行描述：

image.png

优化

由于上述目标函数为非凸函数，因此作者将其分解为四个子问题来进行优化，并且使每个子问题收敛至最佳。此部分不进行具体解释。

个人看法

我感觉这篇论文是很有价值的一篇论文，其不仅能够保存网络的社区内结构和社区结构，并且巧妙地使用辅助矩阵将两种模型结构结合起来。思路清晰简单，易于理解，在原有NMF框架上补充模块度这一度量指标，形成自己的新算法。这篇论文可以改进的地方是，它只使用了边连通性这一网络信息，而没有考虑结点属性。如果将结点属性也结合起来，社区划分效果应该会更好，当然是针对属性增强网络而言。

（事后将论文阅读报告给导师看后，才知道实验室有个师姐在刚过去的年底已经投了上面的idea的论文，并且被录用了。晚了一步，哭哭~）

算法实现

数据集

在作者提供的数据集链接中，我选择使用Facebook数据集，因为其可以使用matlab直接打开，而其他数据集则是比较生疏的格式，暂且不理会。使用的Facebook数据集共包含4个大学的4个社交网络，具体的信息介绍如下：

Particularly, we used four social networks in four universities,i.e., Amherst (2021 nodes, 81492 edges, 15 communities), Hamilton (2118 nodes, 87486 edges, 15 communities), Mich (2933 nodes, 54903 edges, 13 communities) and Rochester (4145 nodes, 145305 edges, 19 communities)

通过下载数据集后进行研究，可知其每个网络的格式均相同，共有4个常量矩阵。包含adj/edge/edge2/gnd四个，顾名思义，adj为邻接矩阵，edge和edge2为边矩阵，而gnd则为社区分类。通过细究数据可以发现，facebook的社交网络实际上是有向图网络，而论文中需要的是有向图，因此单单根据adj是无法正确实现的，所以提供的数据集将边集也给出了，edge为原网络的边集合，而edge2则将其边进行了反向的复制，以便根据其完成无向图。

因此接下来主要利用edge2来完成实验。

具体实现

其实作者基本在其demo中已提供算法实现，我们只需要初始化一些输入变量即可。本文的重点其实是掌握概念，同时能够了解如何实现论文的算法思路等。根据我们在算法原理中已知的目标函数，即：

image.png

我们可知需要有以下输入：S、M、U、C、H、B,其中，S为亲密度矩阵，需自行计算得出；而其他大部分则进行初始化即可。计算的过程以及初始化的过程也很简单，不进行具体的讨论。而作者所给的demo才是算法关键，不过由于matlab代码很简单，基本根据公式就可以写出代码了，因此也不进行具体解释了。

实验结果

接下来的实验设置以m=100, alpha=0.5, beta=0.5, lambda=1e9，并且只验证一个社交网络：Amherst。

目标函数的收敛性

Amherst大学的Object value收敛性：

image.png

Node clustering

文中作者使用K-means进行结点聚类，并且使用了一篇论文里的adopted accuracy来进行评价。这个评价度量方式我不是很懂，也找不到相关的论文。按照我自己的理解，由于我们已知一个社交网络里有k个社区，因此在使用K-means聚类时，直接设置k为该值即可。然而我们已知所有结点所属于的社区，但在聚类后却无法得知结点对应的社区。

k = 15;
[Idx, Ctrs, SumB, D] = kmeans(U,k);
A = cell(k,1);
for n = 1:k
A{n} = find(Idx == n);
end

因此，我认为应该是采取比较简单的方式，即根据我们聚类得到的15个簇，根据簇内结点多数原则来确定该簇属于哪个社区，如此便可得知哪些簇聚类正确或错误。最终，可计算出一个总的正确率。（不知这样子做是否严谨，然而正确率的计算我只想出这个方法…）

不知原作者在论文中的accuracy这一概念是如何得出的。

Node classification

这里实际上就变为一个多分类的问题，作者采用的是一种LIBLINEAR的方法。直接在对应网站即可下载得到压缩包，解压后运行即可使用。注意需要改变当前路径，并且目前我所知的方法是只能在命令行输入执行命令。

下面把基本分类步骤解释如下：

我们由之前的M-NMF已知有结点的表达矩阵U，再加上原有的gnd数据保存各结点的分类，那么就需要将上述矩阵划分为训练集和验证集，来进行训练和分类。为了在随机排列结点时能够保持U和gnd的对应关系不变，因此需要我将两部分矩阵连接起来，形成统一的data矩阵。

虽然，选取前80%为训练集，后20%为验证集。由于libinear需要原始数据为稀疏矩阵，因此首先将其转换成sparse矩阵，再进行模型训练，部分代码如下：(参考博客：http://blog.csdn.net/zouxy09/article/details/10947411）

sp = sparse(train_data);
model = train(group, sp,'-c 1')
% group保存数据标签，sp为稀疏后的训练数据矩阵

由上述两行代码即可训练得出对应模型，再结合代码进行预测即可：

[predict_label, accuracy, dec_values] = predict(label, test, model);
% label为验证集标签，test为稀疏后的验证数据矩阵

流程如上，不再进行具体演示。

总结

由于我对matlab的使用很不熟练，一点点的小问题都需要上网搜索，所以时间基本就耗在这个部分了。除了对上面的node clustering之后的评判标准不太清楚外，其他部分都比较清晰了。附上代码：https://github.com/DesmonDay/Algorithm/tree/master/M-NMF