【IJCAI 2016】Modularity Based Community Detection with Deep Learning 阅读小记
基于低秩嵌入的视角来看,现有的社团检测算法中存在两类主要代表:随机模型(RSM)与模块度最大化模型(MOM)。在这些算法的设计过程中,都采用了非负矩阵分解与奇异值分解等技术,这些方法主要用于线性映射。然而,真实网络所具有的不同非线性特征使得上述方法难以有效应用。因此,神经网络作为一种非常有效的非线性映射工具,吸引了作者的关注,从而将其应用于社团检测领域,最终提出了Nonlinear Reconstruction (DNR)算法。
二、贡献
- 据作者所述, 他们首次将深度学习应用于社团检测领域;
- 开发了DNR模型;
- 基于DNR模型构建了semi-DNR模型, 并加入了节点间关系约束
三、问题描述： 考虑一个无向、无权的图G(N,E), 其中N代表顶点集合的数量,E代表边集合的数量, 目标是识别该网络中具有非重叠性质的社团结构
四、算法
该研究者综合运用了Newman所提出的模块度概念与自编码器技术
- 算法过程
文中的深度学习是由堆叠的自编码器 实现，单个自编码器的计算过程如下：
- 算法 DNR
为避免增加神经网络层数带来的计算复杂度问题, 本文采用了三层自编码器进行堆叠, 并通过分步训练的方式推进模型构建. 具体而言, 训练流程如下: 首先将输入 B 供第一层自编码器使用, 并通过该层获取最优权重参数; 接着将第一层的编码输出 H¹ 传递给第二层自编码器作为输入, 同理继续训练至第三层; 最终在已知的编码层输出结果基础上, 各个子网络之间保持独立运行. 如下图所示:
在社团检测模块中，在最末尾的那个自编码器的编码层输出 \text{H}^3上执行 k-means 聚类分析。
- 算法 semi-DNR
该算法是半监督，在算法中引入了约束，该约束为：假设部分节点的归属社 团已知，并且如果两个顶点属于同一个社团时，他们的低维映射h应该相似， 然后再将该先验知识加入模型训练中。具体表现为，引入矩阵 \text{O}_{N × N}=[ o_{ij }]， o_{ij }=1 表示已知两个顶点 i，j 属于同一个社团，构建损失函数
就认为该方法的核心在于通过计算两个顶点h向量间的距离来判断其是否属于同一社团，并以此为基础进行权值调节以达到优化效果。随后将这一指标与 L_θ (B,M) 线性结合进而构建新的损失函数
五、实验： 在两个人工合成网络（LFR和GN）以及六个真实世界网络上进行了测试，并将DNR方法与其六种现有算法进行了对比分析；同时将其半监督版本与另外两种类似的方法进行了比较研究。采用归一化互信息率（NMI）作为评估标准，并通过大量实验验证其有效性。
参考文献信息：
[1]. 杨磊, 曹 XOR, 韦德, 等人. 基于模块性的社区检测方法结合深度学习技术[C]// 第二届国际人工智能联合会议. AAAI Press, 2016: 2252-2258.
[2]. 自动编码器相关内容 https://www.cnblogs.com/taojake-ML/p/6475422.html