Overlapping Community Detection with Graph Neural Networks

admin管理员组

文章数量:1626372

论文： Overlapping Community Detection with Graph Neural Networks.
源码： https://github/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。

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个新的论文引用数据集
为了证明GNN的存在是必要的，还与将GNN替换成多层感知机（MLP）和直接优化F的方法进行了对比，结果说明使用GNN是有意义的

本文标签： DetectionCommunityOverlappingNetworksneural