AAAI2017 M-NMF:《Community Preserving Network Embedding》 Reading Notes
论文地址：M-NMF Introduction Network Embedding的基本需求是保存网络机构和固有属性。而先前的方法主要保存了网络的围观结构（microscopic structure）如一阶相似度和二阶相似度（LINE，SDNE等）， 忽略了网络结构的介观社区结构（mesoscopic community structure）。针对这个问题，本文提出了一种模块化非负矩阵分解模型M-NMF，该模型将网络的社区结构融入network embedding中。利用节点表示和社区结构之间的一致关系（consensus relationship）， 联合优化基于非负矩阵分解的表示学习模型和基于模块化的社区发现模型， 这样就可以在节点表示中同时保存了微观网络结构和介观社区结构。 具体来说，对于微观结构（节点对相似性），本文使用矩阵分解来融合节点的一节相似性和二阶相似性；对于介观社区结构，通过模块度约束项来检测社区。因此，上面的两项可以通过节点的表示和基于辅助社区表示矩阵社区结构之间的一致关系来联合优化。同时，本文给出了乘法更新策略，保证了再推导参数的时候的正确性和收敛性。 M-NMF Model 对于一个无向图$G=(V,E)$, 图中有$n$个节点和$e$条边，用一个0,1二值邻接矩阵表示为$\mathbf{A}=[A_{i,j}] \in \mathbb{R}^{n \times n}$。 $\mathbf{U} \in \mathbb{R}^{n \times m}$ 为节点的表示矩阵，其中$m \leq n$，$m$是节点的嵌入维度。 建模社区结构 本文采用基于模块最大化的社区发现方法 Modularity， 给定一个邻接矩阵表示的网络$\mathbf{A}$，$\mathbf{A}$包含两个社区，根据Newman 2006b，模块度可以定义如下： $$ Q=\frac{1}{4 e} \sum_{i j}\left(A_{i j}-\frac{k_{i} k_{j}}{2 e}\right) h_{i} h_{j} $$ 其中，$k_i$表示节点$i$的度，如果$i$在第一个社区中，那么$h_i=1$,否则$h_i = -1$。 $k_ik_j$表示将所有边一分为二 参考模块度Q，那么节点$i$,$j$之间可能产生的边数。$\frac{k_{i} k_{j}}{2 e}$如果所有边随机放置，节点$i$,$j$之间的期望边数。定义一个模块度矩阵$\mathbf{B} \in \mathbb{R}^{n \times n}$，其中$B_{i,j}=A_{i,j}-\frac{k_{i} k_{j}}{2 e}$，那么$Q=\frac{1}{4 e} \mathbf{h}^{T} \mathbf{B h}$，其中$\mathbf{h}=[h_i] \in \mathbb{R}^n$，表示社区成员指标器。 如果将$Q$拓展到$k > 2$个社区，那么： $$ Q=\operatorname{tr}\left(\mathbf{H}^{T} \mathbf{B H}\right), \quad \text { s.t. } \quad \operatorname{tr}\left(\mathbf{H}^{T} \mathbf{H}\right)=n $$ 其中$tr()$表示矩阵的迹（主对角线元素和），$\mathbf{H}$是社区成员指标器，$\mathbf{H} \in \mathbb{R}^{n \times k}$，每行表示一个节点所属社区的one-hot编码。 ...