【IJCAI 2016】Modularity Based Community Detection with Deep Learning 阅读小记

一、动机
  从低秩嵌入的角度来看，现有的多种社团检测算法中有两类代表：随机模型（Stochastic Model）和模块度最大化模型（Modularity Optimization Model）。在这两种算法的设计中用到了非负矩阵分解和奇异值分解，这两种方法为线性映射。但是，真实的网络存在不同的非线性特征，使得这些方法不能很好地运用。目前，神经网络是一个非常好的非线性映射的方法，所以作者将深度学习应用于社团检测，提出了Nonlinear Reconstruction（DNR）算法。

二、贡献
  1、 具作者所知，他们是第一次成功将深度学习用于社团检测的；
  2、 提出了DNR模型；
  3、 在DNR的基础上加入节点之间关系的约束，提出了semi-DNR模型

三、问题描述：
  给定一个无向无权图G(N,E)$G(N,E)$，N$N$为顶点数，E$E$为边数，寻找网络中的非重叠性社团。

四、算法

• 思路
  作者结合了Newman提出的模块度（modularity）和自编码器，将模块度矩阵作为自编码器的输入，用欧氏距离和sigmoid交叉熵作为误差损失函数训练网络，最后用k-means对模型中的编码进行聚类得到社团。

• 算法过程
  文中的深度学习是由堆叠的自编码器实现，单个自编码器的计算过程如下：
  

  

• 算法 DNR
    考虑到单独增加神经网络的层数会带来计算上的复杂，所以采用多个自编码器堆叠来实现深度学习，文中采用三个自编码来堆叠。堆叠的实现方式是：三个自编码器分别训练，如首先将 B 输入第一个，训练以得到最佳权值， 然后将第一个的编码输出 H1${\text{H}}^1$ 作为第二个自编码器的输入，重复上述步骤，直到训练完第三个。所以在已知编码层输出的情况下，三个自编码器是互相独立的。如下图：
  

  

  最后在社团检测部分，对最后一个自编码器的编码层输出 H3${\text{H}}^3$进行 k-means 聚 类。

• 算法 semi-DNR
    该算法是半监督，在算法中引入了约束，该约束为：假设部分节点的归属社 团已知，并且如果两个顶点属于同一个社团时，他们的低维映射h应该相似， 然后再将该先验知识加入模型训练中。具体表现为，引入矩阵 ON×N=[oij]${\text{O}}_{N\times N}=[o_{ij}]$， oij$o_{ij}$=1 表示已知两个顶点 i$i$，j$j$ 属于同一个社团，构建损失函数
  
  
  对于该做法我的理解为，直接计算两个顶点的h向量之间的距离，如果已知属于同一个社团，那么该距离就会产生作用，从而对权值调节起修正作用。然后将其和Lθ(B,M)$L_{\theta }(B,M)$线性结合起来，生成新的损失函数：
  

  

五、实验：
  在两个人工合成网络（LFR和GN）以及6个真实的网络中进行实验，并且将DNR与6种算法对比，semi-DNR与2种类似的方法比较，评价指标为归一化互信息（NMI），最终表现良好。

参考文献：
[1]. Yang L, Cao X, He D, et al. Modularity based community detection with deep learning[C]// International Joint Conference on Artificial Intelligence. AAAI Press, 2016:2252-2258.
[2]. 自动编码器参考 https://www.cnblogs.com/taojake-ML/p/6475422.html