Py学习  »  机器学习算法

TKDE21 | 网络社团发现新综述:从统计建模到深度学习

机器之心 • 2 年前 • 229 次点击  

机器之心专栏

机器之心编辑部
美国物理学会院士 Barabasi 教授在其 2012 年发表于 Nature Physics 的文章中指出:「21 世纪将是网络理论的世纪,它正在形成的理论和算法框架将成为许多研究与应用领域的新的驱动力。

大量研究显示,复杂网络普遍具有一些显著的统计特性,比如小世界效应、无标度分布、网络弹性等。尤其是,Girvan 和 Newman 发现了复杂网络的另一个重要统计特性——社团结构,即网络通常会由一些稠密相连的结点簇组成。自此,学术界掀起了对复杂网络社团结构的研究热潮。

本文是来自天津大学图机器学习与数据挖掘团队,联合莫纳什大学、麦考瑞大学,以及圣路易斯华盛顿大学 AI 权威 Weixiong Zhang 教授、UIC 数据挖掘权威 Philip S. Yu 教授等对网络社团发现领域的最新综述,首次以「从统计建模到深度学习」的新视角,为现代网络数据社团发现领域描绘出一幅宏伟而全面的蓝图。


论文链接:https://ieeexplore.ieee.org/document/9511798

1. 内容简介

社团检测(community detection)是网络分析的基本任务,旨在将网络划分为多个子结构以帮助揭示其潜在功能,被广泛用于推荐、异常检测、恐怖组织识别等领域。经典的社团检测方法通常利用概率图模型,采用各种先验知识来推断社团结构。随着网络方法试图解决的问题以及要分析的网络数据变得越来越复杂,研究者们提出了新的社团检测方法,特别是利用深度学习将网络数据转换为低维表征的方法。尽管这些方法促进了社团检测的发展,但目前仍然缺乏对社团检测理论和方法基础的系统回顾。因此,我们提出了一个统一架构来概述社团检测领域的最新发展。我们首先全面回顾了现有的社团检测方法,并介绍了一种新的分类法,该分类法将现有方法分为两类:概率图模型和深度学习。其次,我们讨论了两类方法的主要思想,并针对不同方法进行了详细概述。此外,我们还发布了一些社团检测领域常用的基准数据集,重点介绍了社团检测在各种网络分析任务中的应用。最后,我们讨论了社团检测面临的挑战,并对未来可能的研究方向提出了建议。 

图 1. 社团检测方法的分类细目 

2. 基于概率图模型的社团检测方法

基于概率图模型的方法通常采用启发式或元启发式的方法(网络建模)来检测网络社团。依据概率图模型的类型,我们将社团检测方法细分为三类:有向图模型、无向图模型以及整合有向图和无向图的混合图模型。

2.1 有向图模型

有向图模型主要基于隐变量(样本中未观察到的变量),利用结点或块结构的相似性来生成网络中的边。依据网络建模方法的不同,有向图模型可以分为三类:随机块模型、主题模型和矩阵分解。它们具有扎实的理论基础和较好的性能,得到了广泛应用。

2.1.1 随机块模型

随机块模型(SBM)是一种有效的网络块结构生成模型,其首次将统计建模应用到社团检测。SBM 使用结点隶属似然函数将网络中的结点概率性地分配给不同的社团(块结构),通过推理似然函数来迭代推断结点隶属关系,推导出网络中的隐藏社团。虽然已经提出了多种 SBM 变体,但它们的核心生成过程是类似的。生成过程可以分为两步:1)迭代地为网络中的每个结点分配一个社团;2)计算或更新连接两个结点的边的概率。

表 1. 基于 SBM 的社团检测方法 

2.1.2 主题模型

主题模型(如 LDA)是一种能够有效建模文本中隐藏主题的统计模型,通过使用潜在变量对主题进行建模。基于 LDA 的社团检测方法可以分为两类:一类将网络结构建模为文档;另一类对网络属性进行建模以检测社团。将网络结构建模为文档的方法首先假设网络中的每个结点可能属于多个社团,并将社团视为“主题”,将结点视为“文档”;其次,选择几个社团作为初始社团,根据网络拓扑结构对社团进行迭代更新,得到最终的社团划分;使用网络属性的方法主要利用社交网络的属性,例如用户兴趣,来发现社团。

2.1.3 矩阵分解

非负矩阵分解(NMF)既能使处理的数据的维度得到非线性的约减,还能使分解后的所有分量均为非负值。基于 NMF 的方法首先得到网络中结点高质量和低维的特征,然后基于这些新特征对结点进行聚类,从而发现高质量的社团结构。我们将基于 NMF 的方法分为五大类:基本 NMF、重叠 NMF、属性 NMF、动态 NMF 以及半监督 NMF。

表 2. 基于 NMF 的社团检测方法 

2.2 无向图模型

无向图模型基于场结构(如马尔可夫随机场 MRF),使用一元和二元势能的约束(如相邻结点间社团标签的一致性)来发现社团。基于无向图模型的方法可以分为三类:拓扑 MRF、拓扑和属性结合的 MRF 以及 MRF 和图神经网络(GNN)整合的方法。

表 3. 基于 MRF 的社团检测方法 

2.3 有向图和无向图整合的模型

混合图模型通常将有向图和无向图模型转换为统一的因子图(factor graph)来进行社团检测。虽然这些方法在一定程度上提升了社团检测的性能,但它们采用变分推断或马尔可夫链蒙特卡罗(MCMC)采样对模型进行优化,这不可避免地带来过高的计算复杂度。深度学习能够有效的对高维网络数据进行优化,逐渐被应用于社团检测。

3. 基于深度学习的社团检测方法

基于深度学习的方法旨在学习一种面向社团的网络表征来识别社团结构。它们利用一些学习策略将网络数据从原始输入空间映射到低维特征空间来推导网络表征,具有低计算复杂度、高并行化等优点。依据学习策略的不同,基于深度学习的方法主要分为四类:基于自动编码器的方法、基于生成对抗网络的方法、基于图卷积网络的方法以及图卷积网络和无向图模型整合的方法。

3.1 基于自动编码器的方法

自动编码器(AE)是一种简单但重要的神经网络模型,通过使用编码器和解码器以无监督的方式(最小化原始输入和重构数据之间的误差)学习最佳的网络表征。依据使用的 AE 类型,社团检测方法可以分为四类:堆叠 AE、稀疏 AE、降噪 AE 及变分 AE。

表 4. 基于 AE 的社团检测方法 

3.2 基于生成对抗网络的方法

生成对抗网络( GAN )具有强大的网络数据分析能力,其通常是无监督的,生成的新数据理论上与真实数据拥有相同的分布。基于 GAN 的方法主要采用对抗学习的思想,通过生成器和判别器之间的对抗博弈来检测社团。

3.3 基于图卷积网络的方法

图卷积神经网络(GCN)通过聚合结点的邻域信息来从全局上捕获用于社团检测的结点表征。基于 GCN 的方法分为两类:监督 / 半监督 GCN 以及无监督 GCN。

3.4 图卷积和无向图模型整合的方法

图卷积和无向图模型整合的方法通过利用这两类模型的优势来检测社团。考虑到 GCN 本质上是通过局部特征平滑来构建结点表征,但其没有考虑社团属性,使得结点表征不是以社团为中心的;无向图模型通常定义全局目标来描述社团,但其没有考虑结点信息,并且需要大量计算来学习模型参数。因此,GCN 和无向图模型是互补的,可以将二者结合起来以更好的进行社团检测。

4. 社团检测的应用

我们首先讨论了社团检测常用的数据集,接着介绍了社团检测的应用。

4.1 数据集

我们收集整理了两类用于社团检测的数据集,包括:人工合成数据集(如 Girvan-Newman),以及真实数据集(如社交网络、引用网络以及合作者网络等)。

表 5. 真实数据集  

4.2 实际应用

社团检测已被广泛应用于各种各样的领域和任务,例如:

1)在线社交网络:Facebook、Twitter 和微信等在线社交网络揭示了在线用户之间相似的兴趣。基于在线社会行为的社团检测能够有效推断用户之间的关系及用户偏好,被用于垃圾邮件发送者检测、危机响应等任务。
2)神经科学:神经科学是研究神经系统和大脑的学科。随着大脑映射和神经成像技术的最新发展,大脑也开始被建模为网络。基于大脑网络的社团检测能够帮助识别大脑中起作用或存在病理的功能部分。
3)图像理解:基于社团检测的图像理解通过引入社团来生成更好的图像语义描述。
4)推荐:推荐通常是根据用户购买或浏览历史记录中的信息来建立用户兴趣档案,进而向用户推荐类似物品来解决用户信息过载问题。引入社团概念的社团发现通过有效检测结点之间的关系来产生高质量的推荐结果。
5)链接预测:链接预测通过分析观察到的网络结构和外部信息来处理缺失的连接并预测未来可能的连接。引入社团概念的链接预测通过设计社团特定的相似度矩阵来分析预测结点间链接的概率。

5. 未来研究方向

然概率图模型和深度学习促进了社团检测领域的发展,但目前仍然存在一些有待解决的问题:

    1)更大规模的网络:随着网络数据规模的迅速增加,更大规模的网络逐渐成为不同科学领域的标准。这些网络通常具有数百万或数十亿的结点和边,以及更复杂的结构模式。大多数现有的社团检测方法可能需要大量的训练实例或模型参数,或是通过网络缩减或近似的方式来处理这些网络,但是不可避免的会丢失一些重要的网络信息并影响建模精度。因此,如何针对更大规模的网络,设计一个在准确性和效率方面都超过当前基准的框架是亟需解决的问题。
    2)社团的可解释性:大多数现有的社团检测方法通常利用结果中排名靠前的词或短语来解释社团,但是由于词的数量少以及词之间的关系不明确,这些方法通常不能很直观的理解社团语义。因此,如何充分利用网络信息为社团提供更好的语义解释也是未来的研究方向之一。
    3)自适应的社团模型选择:自适应模型旨在根据不同网络的特性(如异构或动态)或不同任务的特定要求(如最高准确度或最低时间复杂度)选择最合适的算法来检测社团。虽然现有方法在一定程度上可以从一种网络或任务扩展到另一种网络或任务(不可避免地会影响模型的准确性和稳定性),但是很少有方法考虑模型的自适应。因此,如何在保持模型的准确性和稳定性的情况下,设计一个可以自适应特定任务或网络的统一架构,是具有挑战但非常值得的。
    4)更复杂的网络结构:真实世界中的网络可能是异构的、动态的、分层的或者不完全的。因此,如何设计新的社团检测方法,更好的提升模型在不同类型网络上的社团检测,也是重要的研究方向。
    5)概率图模型和深度学习的整合:虽然目前已经提出了一些将概率图模型与深度学习相结合的方法,但其仍然是一个新兴的研究区域。现实世界中的网络社团模式通常是多样的,如异质性或随机性的社团结构,如何利用概率图模型和深度学习的优势,设计新的鲁棒方法,更准确地检测网络中的社团结构。此外,如何设计新的整合算法,以促进概率图模型以及深度学习在其他领域的应用,如推荐或医学诊断等,也是重要研究方向之一。

6. 总结

我们提出了一个统一架构来综述现有的社团检测方法。我们首先介绍了社团检测问题,并引入了一个新的分类法,从学习的角度将现有方法分为两类:概率图模型和深度学习。其次,我们对这两类方法进行了详细的分析和比较。我们还介绍了社团检测在各个任务和领域的广泛应用,并讨论了社团检测未来可能的研究方向。


机器之心 · 机动组

机动组是机器之心发起的人工智能技术社区,聚焦于学术研究与技术实践主题内容,为社区用户带来技术线上公开课、学术分享、技术实 践、走近顶尖实验室等系列内容。机动组也将不定期举办线下学术交流会与组织人才服务、产业技术对接等活动欢迎所有 AI 领域技术从业者加入

  • 点击阅读原文,访问机动组官网,观看全部视频内容:

  • 关注机动组服务号,获取每周直播预告



© THE END 

转载请联系本公众号获得授权

投稿或寻求报道:content@jiqizhixin.com

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/120681
 
229 次点击