(NOCD)Overlapping Community Detection with Graph Neural Networks

admin管理员组

文章数量:1626244

论文地址
代码地址
本文提出了一种基于图神经网络的重叠社区检测模型。Neural Overlapping Community Detection(NOCD) model.

可以看做BigCLAM的升级版。

核心思想：将GNN的强大能力与伯努利-泊松概率(Bernoulli–Poisson)模型结合起来。

Bernoulli–Poisson modelBernoulli-Poisson (BP)模型是一种考虑到重叠社区的图生成模型。

根据BP模型，图是如下方式生成的：给定从属关系 F ∈ R ≥ 0 N × C F \in \mathbb{R}_{\ge0}^{N \times C} F∈R≥0N×C​, 邻接矩阵项 A u v A_{uv} Auv​被采样为：

A u v ∼ B e r n o u l l i ( 1 − e x p ( − F u F v T ) ) (1) A_{uv} \sim Bernoulli(1 - exp(-F_uF_v^T))\tag {1} Auv​∼Bernoulli(1−exp(−Fu​FvT​))(1)其中Fu是节点u(矩阵F的第u行)的社区从属的行向量。直观的说，节点u和v的共同社区越多(即较高的点积 F u F v T F_uF_v^T Fu​FvT​)，他们被连接成边的可能性越大。

该模型有许多令人满意的特性:它可以生成各种社区拓扑(例如嵌套的、分层的)，能导致社区之间的密集重叠，并且具有计算效率。现有的研究建议在BP模型中使用坐标上升的最大似然估计或马尔可夫链蒙特卡罗进行推断。

Model definition
我们不是将隶属矩阵F作为一个自由变量来进行优化(BigCLAM)，而是通过一个GNN生成F:

F : = G N N θ ( A , X ) (2) F := GNN_\theta(A,X)\tag {2} F:=GNNθ​(A,X)(2)输出层采用逐元素的ReLU激活函数，以确保f的无负性。

BP模型的负对数似然损失函数为:(推导过程BigClam中用) − l o g p ( A ∣ F ) = − ∑ ( u , v ) ∈ E l o g ( 1 − e x p ( − F u F v T ) ) + ∑ ( u , v ) ∉ E F u F v T (3) -logp(A|F) = -\sum\limits_{(u,v)\in E}log(1- exp(-F_uF_v^T)) + \sum \limits_{(u,v)\notin E}F_uF_v^T \tag{3} −logp(A∣F)=−(u,v)∈E∑​log(1−exp(−Fu​FvT​))+(u,v)∈/​E∑​Fu​FvT​(3)但是现实中的图通常是非常稀疏的(绝大部分节点之间没有连接 ( u , v ) ∉ E (u,v) \notin E (u,v)∈/​E)，这意味着式3中的第二项将为损失提供更大的贡献。因此，需要通过平衡这两个项来抵消这一点，这是不平衡分类的一种标准技术。

L ( F ) = − E ( u , v ) ∼ P E [ l o g ( 1 − e x p ( − F u F v T ) ) ] + E ( u , v ) ∼ P N [ F u F v T ] (4) \mathcal{L}(F) = -\mathbb{E}_{(u,v) \sim P_E}[log(1-exp(-F_uF_v^T))]+\mathbb{E}_{(u,v)\sim P_N}[F_uF_v^T]\tag{4} L(F)=−E(u,v)∼PE​​[log(1−exp(−Fu​FvT​))]+E(u,v)∼PN​​[Fu​FvT​](4)其中 P E P_E PE​和 P N P_N PN​分别表示边和非边上的均匀分布。

该方法不像传统方法那样直接优化隶属矩阵F，而是搜索神经网络参数 θ ∗ \theta ^* θ∗,以最小化(平衡的)负对数似然函数:

θ ∗ = arg ⁡ θ min ⁡ L ( G N N θ ( A , X ) ) (5) \theta^* = \arg\limits_{\theta} \min \mathcal{L}(GNN_\theta(A,X)) \tag{5} θ∗=θarg​minL(GNNθ​(A,X))(5)GNN进行社区预测的优点： 首先，由于适当的归纳偏差，GNN为邻近节点输出相似的社区隶属向量，与简单模型相比，这提高了预测质量。此外，这样的公式使我们能够无缝地将节点特征分配到模型中。如果节点属性X不可用，我们可以简单地使用A作为节点特性。最后，根据公式2，我们甚至可以预测出在训练时没有看到的节点的社区。

ScalabilityBP模型的一个优点是它可以有效地评估计算损失L(F)及其梯度。通过使用缓存技巧，我们可以将这些操作的计算复杂度从O(N^2)降低到O(N + M)。由于现实世界网络的稀疏性，这已经导致了较大的加速(通常M<<N^2)，但我们还可以进一步加速，在计算损失时，我们不是使用A的所有项(公式4)，而是在每个训练历元采样一小批S边和非边，从而近似计算∇L inO(S)(类似于mini-batch SGD)。

Model architecture在本文的实验中，作者使用的是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 ) ) (6) F := GCN_\theta (A,X) = ReLU(\widehat{A}\;ReLU(\widehat{A}XW^{(1)})W^{(2)}) \tag{6} F:=GCNθ​(A,X)=ReLU(A ReLU(A XW(1))W(2))(6)其中， A ^ = D ~ − 1 / 2 A ~ D ~ − 1 / 2 \widehat{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​是具有自环的邻接矩阵。 D ~ i i = ∑ j A ~ i j \tilde{D}_{ii} = \sum_j\tilde{A}_{ij} D~ii​=∑j​A~ij​是 A ~ \tilde{A} A~的对角度矩阵。

NOCD模型与标准GCN的两个主要区别是：

• (1)第一个图卷积层后的批量归一化。
• (2)L2正则化应用于所有权矩阵。

Assigning nodes to communities根据隶属矩阵进行社区划分，如果节点u的隶属关系Fuc高于一个固定的阈值p，那么我们就将节点分配给社区C。文中实验采取p=0.5.

本文标签： CommunityOverlappingNOCDDetectionNetworks