Overlapping Community Detection with Graph Neural Networks 神经网络

【Overlapping Community Detection with Graph Neural Networks】论文： Overlapping Community Detection with Graph Neural Networks.
源码： https://github.com/shchur/overlapping-community-detection

文章概述现有的用于社团检测的神经网络只检测不相交的社区，而真实的社区却是重叠的，针对这一不足，提出了一种基于GNN的重叠社区检测模型NOCD。文章通过GCN模型学习图的隶属关系矩阵（affiliation matrix）F，用最大似然估计使F生成的图和真实图尽量相似，从而获得每个节点所属的社区。
Algorithm/Model Bernoulli–Poisson model
Bernoulli–Poisson（BP） model是一种允许重叠社区存在的图生成（graph generative）模型，根据隶属关系矩阵 F ∈ R ? 0 N × C F\in\mathbb{R}_{\geqslant0}^{N\times C} F∈R?0N×C?，可以生成对应的邻接矩阵，表示为：
A u v ～ B e r n o u l l i ( 1 ? e x p ( ? F u F v T ) ) ? \\A_{uv}\sim Bernoulli(1-exp(-F_uF_v^T))\, Auv?～Bernoulli(1?exp(?Fu?FvT?))
F u F_u Fu?是隶属关系矩阵F中节点u的行向量，直观来说，u和v的共同社区越多（即 F u F v T F_uF_v^T Fu?FvT?的点积越大），它们就越有可能有边相连。
Model definition
Bernoulli–Poisson模型的最大负对数似然估计：
? log ? p ( A ∣ F ) = ? ∑ ( u , v ) ∈ E log ? ( 1 ? e x p ( ? F u F v T ) ) + ∑ ( u , v ) ? E F u F v T ? \\-\log p\left(\left.A\right|F\right)=-\sum_{(u,v)\in E}\log\left(1-exp(-F_uF_v^T\right))+\sum_{(u,v)\notin E}F_uF_v^T\, ?logp(A∣F)=?(u,v)∈E∑?log(1?exp(?Fu?FvT?))+(u,v)∈/?E∑?Fu?FvT?
真实世界的图通常是非常稀疏的，这意味着方程中的第二项对损失的贡献要远大于第一项。于是使用了不平衡分类（imbalanced classification）的技术，通过平衡这两项来使损失函数更加合理：
L ( F ) = ? E ( u , v ) ～ P E [ ∑ log ? ( 1 ? e x p ( ? F u F v T ) ) ] + E ( u , v ) ～ P N [ F u F v T ] ? \\L(F)=-E_{(u,v)\sim P_E}\left[\sum\log\left(1-exp(-F_uF_v^T\right))\right]+E_{(u,v)\sim P_N}\left[F_uF_v^T\right]\, L(F)=?E(u,v)～PE??[∑log(1?exp(?Fu?FvT?))]+E(u,v)～PN??[Fu?FvT?]
其中， P E P_E PE?和 P N P_N PN?分别表示edges和non-edges上的均匀分布。
传统方法直接优化隶属关系矩阵F，本文使用GNN，寻找参数 θ ? \theta^\ast θ?最小化平衡的负对数似然函数：
θ ? = arg ? min ? θ L ( G N N θ ( A , X ) ) ? \\\theta^\ast=\mathop{\arg\min}\limits_{\theta}L(GNN_\theta(A,X))\, θ?=θargmin?L(GNNθ?(A,X))
使用2层的图卷积神经网络GCN作为NOCD模型的基础，GCN定义为：
F ? G C N θ ( A , X ) = R e L U ( A ^ R e l U ( A ^ X W ( 1 ) ) W ( 2 ) ) ? \\F\coloneqq GCN_\theta(A,X)=ReLU(\hat{A}RelU(\hat{A}XW^{(1)})W^{(2)})\, F:=GCNθ?(A,X)=ReLU(A^RelU(A^XW(1))W(2))
其中 A ^ = D ~ ? 1 / 2 A ~ D ~ 1 / 2 \hat{A}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{1/2} A^=D~?1/2A~D~1/2, A ~ = A + I N \tilde{A}=A+I_N A~=A+IN?。模型与标准GCN模型的两个主要区别是(1)第一个图卷积层后的batch normalization和(2)所有权重矩阵的 L 2 L_2 L2?正则化。模型有两种，一种是将节点属性X作为输入的NOCD-X，一种是使用邻接矩阵作为输入的NOCD-G。

Overlapping Community Detection with Graph Neural Networks

文章图片

Scalability
BP模型可以通过缓存技巧，使复杂度从 O ( N 2 ) O(N^2) O(N2)降低到 O ( N + M ) O(N+M) O(N+M)。通过不使用全部的邻接矩阵A，而是使用S个edges和non-deges的mini-batch，可以进一步加速。
在衡量指标的选取上，文章认为使用Jaccard和F1score可能非信息不完全的社区任意高的分数，而使用重叠归一化互信息（NMI）作为衡量指标更为健壮和有意义。
Experiment Detail 文章引入了4个新的论文引用数据集