Modularity Based Community Detection with Deep Learning 阅读笔记
一、创新点
1、提出DNR模型
2、对DNR模型改进，加入节点约束，提出semi-DNR模型
3、第一次将深度学习应用到社区检测
二、研究背景
模块或群落结构的识别对于描述和理解复杂系统非常重要。现有的多种社团检测算法中有两类代表：随机模型和模块度最大化模型。
2.1 问题描述
设无向无权图 G =（V，E），其中V = {v1, v2, …, vN } 是N个顶点的集合，E = {eij} 是边的集合，每条边都连接着V中的两个顶点。
G的邻接矩阵是一个非负对称的矩阵 A = [aij]，aij = 1，顶点 i 和 j 之间有边；aij = 0，顶点 i 和 j 之间无边。
社团检测的问题是要找到 K个模块或社区 {𝑉𝑖 𝑖=1)𝐾} 的子图，这些子图的顶点之间的联系比与外部顶点的联系更紧密。在这里，考虑不相交的社区。
2.2 随机模型（Stochastic Model）
在随机模型中，aij 可以被看作是结点 i 和 j 相连的概率。如果结点 i 和 j 是相连的，可以进一步认为此概率由结点 i 和 j 生成属于同一社区的边的概率确定。
引入潜在变量 H = [hik]∈𝑅+(𝑁×𝐾)，其中 hik 代表结点 i 产生属于社区 k 的边的概率。这个潜在变量还可以捕捉到结点 i 属于社区k的概率。H 的每一行都可以被视为社区成员的分布的结点。结点 i 和 j 被属于社区 k 的链接连接的概率为 hikhjk，它们连接的概率为：
因此，社区检测问题可以被表述为非负矩阵分解 𝐴≈𝐴 ̂=𝐻𝐻𝑇。
基于NMF的社区检测方法的目的是找到一个非负的成员矩阵 H 来重建邻接矩阵 A 。有两个常见的目标（损失）函数来量化重建误差。
第一种是基于平方损失函数，它等同于两个矩阵之差的Frobenius规范的平方
第二种是基于两个矩阵之间的Kullback-Leibleer divergence（KL-divergence）。
2.3 模块度最大化模型（Modularity Optimization Model）
该模型由Newman引入最大化模块化函数Q，该函数定义为社区内边的数量与所有对顶点上此类边的预期数量之间的差。 例如，一个有两个社区的网络
Maximizing Eq. (1) 是一个NP难题，实际中，可以通过把变量hi设置成随机值解决，同时 hTh=N。
当K>2时，社团多于两个，可以定义特征矩阵 H = [hik]∈𝑅+(𝑁×𝐾) 得到
基于瑞利熵数，这个问题的解决方案是模块化矩阵B的前最大K个特征向量。矩阵H的每一行都可以被看作是潜空间中相应顶点的新表示，然后用聚类算法，如k-means，用来将结点分类到潜空间中不相干的组。
2.4 研究方法
虽然设计的目的不同，这两类模型都在寻找低秩嵌入来最好地代表和重建网络拓扑结构。
但是这两种方法都只能通过线性重建来重建原始的网络，忽略了网络的非线性特性，而真实的网络有各种非线性特征，使得这些模型在实践中不那么有效。
神经网络是一个非常好的非线性映射的方法，所以作者将深度学习应用于社团检测，提出了Deep Nonlinear Reconstruction（DNR）算法。将该方法扩展到一个半监督的社区检测算法中，在图结点之间加入成对的约束，提出了semi-DNR模型。
三、算法
3.1 DNR
自动编码器是一种特殊的神经网络，用于学习一种新的表示方法，可以最好地接近原始数据，它是该模型的一个关键构件，模型由堆叠的自编码器实现，单个自编码器的计算过程如下：
B
H
M
input
encoder
decoder
ERROR
编码器将原始数据B映射到一个低维嵌入，解码器将潜伏表示H映射回原始数据空间，即重构原始数据。
自动编码器的目的是学习一个低维非线性表征H，该表征能够最好地重建原始数据B，即最小化原始数据B和重建数据M之间的差异。
矩阵B输入自动编码器， bij = aij - (𝑘𝑖 𝑘𝑗)/2𝑚 ∈𝑅(𝑁×𝐾)，通过编码得到矩阵H，H作为下一层输入通过解码得到矩阵M，
以欧式距离和sigmoid交叉熵为真实值B和估计值M之间的距离度量函数 Lθ，重建误差小于一定值停止，S(.)为激活函数sigmoid 或tanh，其中WH和dH是要在编码器中学习的参数， WM和dM是要在解码器中学习的参数。
公式（2）
训练完自动编码器后，就可以得到WH和dH和编码器公式（2）可以用来生成所有顶点的新表示。
单独增加神经网络的层数会带来计算上的复杂，所以采用多个自编码器堆叠来实现深度学习。
堆叠的实现方式是：三个自编码器分别训练，如首先将 B 输入第一个encoder，训练以得到最佳权值， 然后将第一个的编码输出 H1 作为第二个encoder的输入，直到训练完第三个。
H1
H2
H3
input B
encoder
encoder
encoder
所以在已知编码层输出的情况下，三个自编码器是互相独立的。最后在社团检测部分，对最后一个自编码器的编码层输出进行 k-means 聚类。
3.2 semi-DNR
semi-DNR (Pairwise Constrained Semi-supervised Community Detection)算法是半监督，在算法中引入顶点的成对约束。
该约束为：假设部分节点的归属社团已知，并且如果两个顶点属于同一个社团时，他们的低维映射 h 应该相似， 然后再将该先验知识加入模型训练中。
具体表现为，引入矩阵 O = [oij]∈𝑅(𝑁×𝑁) (𝑖,𝑗∈𝑠𝑎𝑚𝑒 𝑐𝑜𝑚𝑚𝑢𝑛𝑖𝑡𝑦&“oij” =1;𝑖,𝑗∈𝑑𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑡 𝑐𝑜𝑚𝑚𝑢𝑛𝑖𝑡𝑦&“oij” =0)，构建损失函数纳入自动编码器：
可以理解为，直接计算两个顶点的h向量之间的距离，如果已知属于同一个社团，那么该距离就会产生作用，从而对权值调节起修正作用。然后将其和Lθ(B,M) 线性结合起来，半监督DNR（semi-DNR）的总体损失函数为：
四、实验结果
在两个人工合成网络（LFR和GN）以及6个真实的网络中进行实验，并且将DNR与6种算法对比，semi-DNR与2种类似的方法比较，评价指标为归一化互信息（NMI）。
例如，LFR的叠加自动编码器网络由三个自动编码器组成。其中第一个自动编码器是1000-512-1000，第二个是512-256-512，第三个是256-128-256。
所有的自动编码器都是单独训练的。如前所述，模块化矩阵作为第一个自动编码器的输入，结果输入下一个编码器。
训练批次设定为网络的大小，并且最多运行100000次迭代。对于每个网络我们用10个随机初始化训练一个DNR模型，并从三个自动编码器中提取潜在的表征用于聚类。最后，采用k-means进行聚类，并返回具有最大模块化的结果。
合成网络：GirvanNewman（GN）网络和Lancichinetti-Fortunato-Radicchi（LFR）网络。
GN网络由128个节点组成，分为4个社区，每个社区32个节点。每个节点平均有16条边，其中Zout边是社区间的边。结果如图（a）。DNR优于所有的竞争方法，特别是当Zout>6时。
LFR网络比GN网络更复杂。节点数设为1000，平均度数为20，顶点度数的指数和社区大小分别为-2和-1，混合参数μ从0.6到0.8变化。作者设置了两组网络：一组社区规模为10到50，另一组为20到100。
这两组网络的结果显示在图（b）和（c）中。如图所示，DNR可以成功地检测出小型和大型社区。当μ>0.65时，它在小社群规模的网络上取得了最佳性能（b），而μ>0.6时，它在大社群规模的网络上取得了最佳性能（c）。
表1中在真实网络，将DNR与其他著名的基于模块化的社区检测方法进行比较。实验中，采用了欧氏距离和sigmoid交叉熵作为误差函数。
采用L2准则的DNR（DNR L2）和采用交叉熵距离的DNR（DNR CE）优于大多数竞争的基于模块化的优化算法。
为了评估新的半监督semi-DNR方法，实验使用了在没有标签信息的情况下很难找到满意的社区结构的网络。（b，c，d）网络上表现平平，Zout=7的GN网络，其中没有标签的方法也能取得较好的结果进行比较。
在Zout=7的GN上，所有的方法通过强制执行相同百分比的标签都有类似的改进。
在无监督方法不能获得满意结果的网络上，相比之下，半DNR在相同数量的标签下取得了更好的性能。意味着半DNR在使用成对约束方面比其他方法更有效。此外，在多层上执行成对约束的性能也有类似的改进，说明semi-DNR只需通过一层图的正则化就能充分发掘成对约束。
参考文献
[1] 论文
[2] 【IJCAI 2016】Modularity Based Community Detection with Deep Learning 阅读小记