携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第26天，dl.acm.org/doi/10.1145…

会议：CIKM ’17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management （CCF-B）

年度：2017

ABSTRACT

在本文中，我们研究了一种重要的、但在很大程度上还未被开发的图嵌入设置，即嵌入社区而不是每个单独的节点

我们发现社区嵌入不仅对社区级应用(如图形可视化)有用，而且对社区检测和节点分类都有好处

为了了解这种嵌入，我们的洞察力依赖于社区嵌入、社区检测和节点嵌入之间的一个闭环

• 一方面，节点嵌入可以提高社区检测，输出好的社区，适合更好的社区嵌入
• 另一方面，社区嵌入可以通过引入社区感知的高阶邻近性来优化节点嵌入

在此基础上，我们提出了一个新的社区嵌入框架，共同解决这三个任务

我们在多个真实世界的数据集上评估了这样的框架，并表明它改善了图形可视化，并在各种应用任务(如社区检测和节点分类)中优于最先进的基线

1 INTRODUCTION

传统上，图嵌入关注单个节点，目的是输出图中每个节点的向量表示，使图上“接近”的两个节点在低维空间中具有相似的向量表示。这种节点嵌入在保持网络结构方面非常成功，并显著提高了广泛的应用范围，包括节点分类[5,20]，节点聚类[27,34]，链路预测[12,19]，图可视化[24,29]和更多的[10,18]。

在本文中，我们研究了另一个重要的，但在很大程度上未被充分开发的图嵌入设置，重点是嵌入社区。一般来说，“社区嵌入”是对一个社区在低维空间中的表现。由于社区是一组紧密连接的节点，因此期望通过社区嵌入来表征其成员节点在低维空间中的分布情况

因此，我们不能简单地将社区嵌入定义为一个向量;相反，我们需要把它定义为低维空间的分布

在图1中，我们以研究充分的空手道俱乐部图1为例，展示了2D空间中的社区嵌入

如图1(a)所示，空手道俱乐部图有34个节点和78条边

我们知道这个图有两个社团，一个社团是由一个班级指导员(节点1)领导的，另一个社团是由一个俱乐部管理员(节点34)[35]领导的
一些俱乐部成员(如节点9)被认定为两个社区的“弱支持者”，因此他们可以同时属于两个社区。

在图1(b)中，我们将图可视化在2D空间中，其中每个嵌入节点都是一个2D向量

由于每个社区都是一组紧密连接的节点，我们受到高斯混合模型(GMM)[3]的激励，将每个嵌入的社区视为二维空间中的多元高斯分布

因此，我们将空手道俱乐部图中两个重叠的社区可视化为两个重叠的月食，每个月食都用一个二维均值向量和一个2 × 2的协方差矩阵表征

社区嵌入对于许多社区级应用程序非常有用
例如，社区可视化可以帮助从大图表中生成见解，或者社区推荐来搜索类似的社区

学习社区嵌入并非易事

一方面，为了实现有意义的社区嵌入，我们首先需要很好地识别社区

然后，一个简单的社区嵌入方法是:

• (1)在图上运行社区检测，如Spectral Clustering[25]，得到每个节点的社区分配
• (2)在图上应用节点嵌入，如DeepWalk[20]或LINE[24]，得到每个节点的嵌入向量
• (3)聚合每个社区中的节点嵌入向量，使其社区嵌入拟合成一个(多元高斯)分布

这种管道方法是次优的，因为它的社区检测不依赖于它的节点嵌入

另一方面，最近的研究表明，节点嵌入往往可以提高社区检测，这是因为它在低维空间中很好地保持了网络结构[5,15,27]

因此，社区嵌入的另一种可能的方法是直接对节点嵌入结果进行社区检测，从而根据每个社区的节点嵌入向量拟合出一个(多元高斯)分布

但是，这种方法也是次优的，因为现有的大多数节点嵌入方法(如DeepWalk [20]， LINE[24]和Node2Vec[12])都不知道团体结构，这使得它们的节点嵌入输入对于后续的团体检测是次优的

在第5节中，我们对上述两种方法进行了实证评估，并表明它们的性能是有限的

很少有研究将节点嵌入和社区检测结合起来考虑

它们要么需要额外的监督(例如，必须链接)[34]，要么需要很高的计算复杂度(例如，图中节点数量的二次元)[31]

此外，它们对低维空间中的社区特征描述不足，难以对重叠的社区进行准确的可视化

我们对学习社区嵌入的见解是，社区检测、社区嵌入和节点嵌入之间存在一个闭环，如图2所示

• 一方面，如前所述，节点嵌入可以提高社区检测(即①)，输出好的社区来拟合有意义的社区嵌入(即②)
• 另一方面，社区嵌入可以用来优化节点嵌入(即③)

假设有一个社区k，我们已经将它的社区嵌入到一个低维空间的多元分布中

然后，我们可以强制社区k的成员节点在该低维空间中接近其社区嵌入的均值向量

因此，这些相同社区的节点往往具有相似的节点嵌入向量

与一阶二阶邻近性相比，社区嵌入不需要两个节点直接相连，也不需要共享许多“上下文”

因为社区中两个节点之间的连接可以是高阶的，所以我们认为社区嵌入是在节点嵌入中引入一种社区感知的高阶邻近性

这种从社区嵌入到节点嵌入的反馈帮助我们完成了循环

希望社区感知节点嵌入可以作为后续社区检测的更好输入，从而得到更有意义的社区嵌入结果

在闭环洞察的指导下，我们提出了一种新的社区嵌入框架ComE，将社区嵌入、社区检测和节点嵌入三者结合起来共同解决

我们将社区嵌入定义为一个多元高斯分布，并利用它通过高斯混合公式从节点嵌入结果中进行社区检测

表示图为$G=(V,E)$，其中$V$是节点的集合，$E$是边的集合

这种高斯混合公式使我们能够有效地检测群落，并从$O(|V|)$时间的$G$中推断它们的群落嵌入分布

考虑到社区分配和社区嵌入，我们扩展了DeepWalk和LINE的神经网络公式，以保持第一、第二和高阶(社区感知)相邻

对于这种神经网络公式，我们提出了一种可扩展的推理算法，其复杂度与图大小$O(|V|+|E|)$线性

我们总结我们的贡献如下

• 我们引入了一种新的联合建模框架，利用节点嵌入、社区检测和社区嵌入之间的闭环来学习图的嵌入
• 我们提出了一种可扩展的推理算法，其复杂度为$O(|V|+|E|)$，通常低于现有的高阶近似感知方法(表1)
• 我们在多个真实世界的数据集上使用各种应用任务来评估ComE。同时，该方法在社区检测方面至少提高了6.6% (NMI)和2.2% ~ 16.9%(电导)，节点分类方面至少提高了0.8% ~ 26.9%(宏观f1)和0.71% ~ 48%(微观f1)

2 RELATED WORK

我们在表1中总结了我们的工作与一些有代表性的相关工作在图嵌入和社区检测方面的差异

接下来我们将详细讨论相关工作

2.1 Graph Embedding

随着从社交网络到各种信息网络的图形数据数量的增加，一个重要的问题出现了，即如何表示一个用于分析[11]的图形

图嵌入是最先进的图表示框架，其目的是将图投影到低维空间中以供进一步应用[16,20,26]

在嵌入目标方面，现有的图嵌入方法大多集中在节点上。例如，早期的方法，如MDS [7]， LLE [21]， IsoMap[26]和Laplacian特征映射[2]，目的是保持一阶邻近性，提取图亲和矩阵的主导特征向量

最近的一些方法开始利用神经网络来学习每个节点的表示，可以是浅层架构[12,24,33]，也可以是深层架构[1,8,18,29]

• DeepWalk[20]通过路径采样对节点嵌入的二阶接近度进行建模，使用分层softmax进行推理的复杂度为$O(|V|log|V|)$
• Node2Vec[12]通过一个控制路径采样过程扩展了DeepWalk，该过程需要$O(|V|a^2)$，其中$a$为图的平均度;因此，其模型复杂度$O(|V|log|V|+|V|a^2)$
• LINE[24]和SDNE[29]保持一阶二阶接近，但代价分别是$O(a|E|)$和$O(a|V|)$

与我们的方法相比，上述工作具有较低或相当的复杂性，但没有试图检测或代表社区

社区结构是一种重要的网络属性，在节点嵌入中一直被考虑

• 例如，在SAE[27]中，作者表明光谱聚类可以被视为重构图的归一化相似矩阵，但其代价昂贵，复杂度至少为$O(|V{|}^{2.367})$。因此，他们建议直接构造复杂度为$O(|E|)$的归一化相似矩阵，并将其输入到复杂度为$O(|V|)$的堆叠式自动编码器中进行重构。结果的节点嵌入用于K-means聚类，并表明获得更好的社区比光谱聚类
• 同理，DNR[34]从复杂度为$O(|V{|}^2)$的图构造一个模块化矩阵，然后对模块化矩阵应用堆叠的Auto-Encoder进行节点嵌入。它还引入了必须链接来监督节点嵌入
• 更高阶的接近方法，如GraRep[5]和HOPE[19]，并没有明确的社区意识。此外，GraRep学习一个高阶跃迁概率矩阵，然后对复杂度为$O(|V{|}^3)$的矩阵进行奇异值分解(SVD)

上述算法在节点嵌入时既不尝试嵌入社区，也不显式地检测社区，但由于实际工作网络的稀疏性，其复杂度普遍较高

很少有工作试图明确地将社区嵌入到低维空间中。例如，M-NMF[31]构造复杂度为$O(|V{|}^2)$的模块化矩阵，然后利用非负矩阵分解学习复杂度为$O(|V{|}^2)$的节点嵌入和社区检测

相对而言，M-NMF用一个向量表示每个社区，因此我们不会认为它产生一个社区嵌入

此外，其复杂性通常高于我们的$O(|V|+|E|)$的复杂性，因为在实际操作中图形稀疏，$|E|\ll |V{|}^2$。

2.2 Community Detection

团体检测的目的是发现图上的节点组，使组内的连接比组间的连接密集[30]

随着社交网络的普及，最近的社区检测研究开始利用图上丰富的节点交互，如节点的内容为[22]，属性为[23]，节点到节点扩散为[4]

在[32]中可以找到最近社区检测算法的全面调查

在这项工作中，我们将社区检测应用于节点和边不含附加信息的齐次图

早期的同构图上的团体检测方法往往直接对图邻接矩阵采用不同的聚类算法

• 例如[25]，将光谱聚类应用于社会网络，提取社区
• 在[13]中，训练一个拉普拉斯正则化GMM来捕获最近邻图的流形结构。

近年来随着神经网络和深度学习的发展，利用节点嵌入辅助社区检测[15,27]

这种工作通常是先将图嵌入到一个低维空间中，然后对嵌入结果应用K-means等聚类算法

尽管这些基于节点嵌入的方法在社区检测方面取得了成功，但它们往往没有将节点嵌入和社区检测结合起来进行优化

由于他们的目标主要是社区检测，他们不一定有明确的社区嵌入概念

3 PROBLEM FORMULATION

作为输入，我们给定一个图$G=(V,E)$，其中$V$是节点集，$E$是边集

传统的图嵌入的目的是学习每个$v_i\in V$的节点嵌入为${\phi }_i\in R^d$

在本文中，我们还尝试学习社区嵌入

假设图$G$上有$K$个群落，对于每个节点$v_i$，我们表示其群落分配为$z_i\in \{1，\dots K\}$

受高斯混合公式[3]的启发，我们将社区嵌入定义为低维空间中的多元高斯分布

定义3.1

一个群落$k$ ($k\in \{1，\dots ，K\}$)在d维空间中为多元高斯分布$N({\psi }_k，{\Sigma }_k)$，其中

• ${\psi }_k\in R^d$为均值向量
• ${\Sigma }_k\in R^{d\times d}$为协方差矩阵

作为输出，我们的目标是:

• (1)每个节点$v_i\in V$的节点嵌入${\phi }_i$
• (2)团体成员( community membership )${\pi }_{ik}$，使${\sum }_{k=1}^K{\pi }_{ik}=1$，对于每个节点$v_i\in V$，每个团体$k\in \{1，\dots K\}$
• (3)每个群落$k\in \{1，\dots K\}$的群落嵌入参数$({\psi }_k，{\Sigma }_k)$

我们在表2中总结了所有的符号

3.1 Community Detection and Embedding

对于给定的节点嵌入，检测社区并了解其社区嵌入的一种简单方法是采用管道方法

例如，如图2所示，我们可以运行光谱聚类(Spectral Clustering)来检测群落，然后为每个群落拟合一个高斯混合

但这种流水线方法缺乏统一的目标函数，后期嵌入节点难以优化

另外，我们也可以基于GMM进行社区检测，并将其嵌入到单个目标函数中

即，我们认为每个节点$v_i$的嵌入${\phi }_i$是由社区$z_i=k$产生的多元高斯分布，那么$V$中所有节点的可能性为

• 其中$p(z_i=k)$是节点$v_i$属于团体$k$的概率

为简便起见，我们表示$p(z_i=k)$为${\pi }_{ik}$

则有${\pi }_{ik}\in [0,1]$，${\sum }_{k=1}^K{\pi }_{ik}=1$

在社区检测中，这些${\pi }_{ik}$表示每个节点$v_i$的混合社区成员，它们是未知的

另外，$p(v_i|z_i=k;{\phi }_i，{\psi }_k，{\Sigma }_k)$是一个多元高斯分布，定义如下

在社区嵌入中，$({\psi }_k，{\Sigma }_k)$是未知的

通过优化Eq. 1 w.r.t ${\pi }_{i}k$和$({\psi }_k，{\Sigma }_k)$，我们同时实现了团体检测和嵌入

3.2 Node Embedding

传统上，节点嵌入的重点是保持一阶或二阶邻近性

例如，为了保持一阶接近，LINE[24]通过最小化来强制两个相邻节点具有相似的嵌入

其中$\sigma (x)=1/(1+exp(-x))$为s型函数

为了保持二阶邻近性，LINE和DeepWalk[20]都强制两个节点共享许多“上下文”(即ζ跳内的邻居)以具有相似的嵌入

在这种情况下，每个节点都有两个角色:自己的节点和其他一些节点的上下文

为了区分这些角色，DeepWalk为每个节点$v_j$引入了额外的上下文嵌入，作为$\phi {’}_j\in R^d$。表示$C_i$为$v_i$的上下文集合。

然后，我们采用负采样[17]来定义一个函数，用于测量$v_i$生成每个上下文$v_j\in C_i$ 的情况

其中$v_l{P}_n(v_l)$表示根据概率$P_n(v_l)$对节点$v_l\in V$进行抽样，将其作为$v_i$的“负上下文”。

我们将$P_n(v)l)\propto r_l^{3/4}$设为[17]中建议的值，其中$r_l$为$v_l$的度

总的来说，有消极的环境

一般来说，最大化Eq. 4强制节点$v_i$的嵌入${\phi }_i$最好地生成其正面语境${\phi }_j^{\prime }$，而不是负面语境${\phi }_l^{\prime }$

然后，我们可以最小化以下目标函数以保持二阶邻近性:

• α > 0是一个权衡参数

3.3 Closing the Loop

为了完成图2中的环路，我们需要将社区检测和社区嵌入反馈到节点嵌入

假设我们在3.1节中确定了混合社区成员${\pi }_{ik}$和社区嵌入$({\psi }_k，{\Sigma }_k)$

然后，我们可以重用公式1，通过将${\phi }_i$的嵌入节点视为未知的，来实现这种反馈

有效地，优化公式1 w.r.t φi使同一社区内的节点${\phi }_i$更接近对应的社区中心${\psi }_k$

也就是说，共享一个社区的两个节点很可能具有相似的嵌入

与一、二阶邻近性相比，该设计在节点嵌入上实现了社区感知的高阶邻近性，有利于后期的社区检测和嵌入

例如，在图1(a)中，节点3和节点10是直接相连的，但根据[35]，它们倾向于属于两个不同的社区

因此，如果只保留一阶接近，我们可能无法很好地分辨它们的社区成员差异

又如，节点9和节点10共享多个一跳和两跳邻居，但与节点10相比，节点9根据[35]趋向于更接近节点1主导的社区

因此，如果只保留二阶邻近性，我们可能也不能很好地分辨它们的社区成员差异

在闭环的基础上，将社区检测、社区嵌入和节点嵌入结合起来进行优化

我们考虑三种类型的邻近性，包括一阶邻近性、二阶邻近性和高阶邻近性

一般来说，结合不同类型的接近度进行节点嵌入的方法有两种:

• (1)“连接”，例如，LINE首先分别优化eso1和O2，然后它将两个结果嵌入到每个节点连接成一个长向量作为最终输出
• (2)“统一”，例如SDNE[29]学习每个节点的单个节点嵌入，以同时保持一阶和二阶邻近性

在本文中，为了鼓励节点嵌入统一多种邻近类型，我们采用了统一方法，其他方法留待以后研究

因此，基于式1，我们定义了社区检测和嵌入的目标函数，并将节点嵌入的高阶接近度强制为

然后，我们统一了节点嵌入的一阶和二阶邻近性

ComE的最终目标函数是

我们最终的优化问题变成:

• 其中$diag({\Sigma }_k)$返回${\Sigma }_k$的对角线条目

我们特别引入了一个约束$diag({\Sigma }_k)>0$对于每个$k\in \{1，\dots ，K\}$，以避免优化L的奇异性问题

类似于GMM[3]，对于优化L存在不受约束的退化解。也就是说，当一个高斯分量坍缩到一个点时，$diag({\Sigma }_k)$变成了零，这使得$O_3$变成了负无穷

4 INFERENCE

…

5 EXPERIMENTS

Datasets

Baselines

5.1 Graph Visualization

5.2 Community Detection

5.3 Node Classification

5.4 Model Study

读后总结

2022/08/09 第一次阅读

本文的从社区分类的角度入手

之前的工作表明：

• 社区嵌入利于节点嵌入
• 节点嵌入又有利于社区嵌入

但是之前都是管状结构（算法有先后顺序）

本文则是同时利用社区嵌入和节点嵌入进行优化

同时一个新颖的地方在于，作者将社区类比于一个高斯分布

求社区的嵌入也就是求对应的高斯分布

节点嵌入则是借鉴LINE和DeepWalk，得到损失函数$O_1$和$O_2$

利用社区嵌入得到损失$O_3$

联合三者的损失，得到最终的目标优化函数

以此训练模型，得到嵌入

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正