【2019/DLG】Overlapping Community Detection with Graph Neural Networks

文章链接：https://arxiv.org/pdf/1909.12201.pdf
源码链接：https://github.com/shchur/overlapping-community-detection

TL;DR

近年来 GNN 在图相关任务中取得了重大成果但在社团检测领域应用较少。目前基于深度学习的社团检测模型都只处理了非重叠的社团检测问题，而现实中的社团都是重叠的。因此本文中提出一个可以检测重叠社团的 GNN 模型。

Model / Algorithm

问题定义

对于一个无向无权图 $G$ , 可以用二值邻接矩阵 $A\in \{0,1\}^{N \times N}$ 进行表示，其中包含 $N$ 个节点 $V=\{1, \ldots, N\}$ ， $M$ 条边 $E=\left\{(u, v) \in V \times V: A_{u v}=1\right\}$ 。每个节点具有 $D$ 维属性 $X \in \mathbb{R}^{N \times D}$ 。

重叠社团检测的任务是将图中的每个节点划分到 $C$ 个社团中。这种分配的过程可以使用非负隶属矩阵表示： $F \in \mathbb{R}_{\geq 0}^{N \times C}$ ，其中 $F_{uc}$ 表示节点 $u$ 在社团 $c$ 中的隶属度。特殊情况下矩阵 $F \in\{0,1\}^{N \times C}$ ，有些节点可能不属于社团，有些节点可能属于多个社团。

对于社团检测问题，如果假定基于社团的图生成模型为 $p(G|F)$ ，社团检测任务就是从给定的图 $G$ 中推断出隶属关系矩阵 $F$ 。

NOCD Model

本文中提出的 NOCD （Neural Overlapping Community Detection）模型主要想法是结合 GNN 和 Bernoulli-Poisson 概率模型。

Bernoulli-Poisson 模型

伯努利-泊松模型是一个重叠社团的图生成模型。对于给定的隶属关系矩阵 $F \in \mathbb{R}_{\geq 0}^{N \times C}$ ，可以得到邻接矩阵 $A_{uv}$ 采样为：

$A_{u v} \sim \operatorname{Bernoulli}\left(1-\exp \left(-F_{u} F_{v}^{T}\right)\right)$

其中，行向量 $F_u$ 表示节点 $u$ 的社团隶属关系。从上式可以看出节点 $u$ 和节点 $v$ 之间属于相同社团的数量越多说明两节点之间存在边的概率越高。

模型定义

论文中将节点隶属矩阵 $F$ 直接作为模型的输出来生成：

$F:=\operatorname{GNN}_{\theta}(A, X)$

实验中论文直接使用了两层 GCN，计算方式如下：

$F:=\operatorname{GCN}_{\theta}(A, X)=\operatorname{ReLU}\left(\hat{A} \operatorname{ReLU}\left(\hat{A} X W^{(1)}\right) W^{(2)}\right)$

其中 $\hat{A}=\tilde{D}^{-1 / 2} \tilde{A} \tilde{D}^{-1 / 2}$ ， $\tilde{A} = A + I_N$ ， $\tilde{D}_{i i}=\sum_{j} \tilde{A}_{i j}$ 是度矩阵。

模型的输出层增加了非线性单元 ReLU 来保证输出是非负的。

对于伯努利-泊松模型的负对数似然函数为：

$-\log p(A | F)=-\sum_{(u, v) \in E} \log \left(1-\exp \left(-F_{u} F_{v}^{T}\right)\right)+\sum_{(u, v) \notin E} F_{u} F_{v}^{T}$

由于现实中的图是非常稀疏的，因此上式中的第二项对于损失函数的贡献较大。可以通过不平衡分类的方法来消除这两项的不平衡：

$\mathcal{L}(F)=-\mathbb{E}_{(u, v) \sim P_{E}}\left[\log \left(1-\exp \left(-F_{u} F_{v}^{T}\right)\right)\right]+\mathbb{E}_{(u, v) \sim P_{N}}\left[F_{u} F_{v}^{T}\right]$