中科院孙冰杰博士：基于网络化数据表示学习的重叠社区发现研究

雷锋网AI科技评论按：网络是大数据的重要组织形式，然而网络化的数据由于缺少高效可用的节点表示，而难于直接应用。网络化数据表示学习通过将高维稀疏难于应用的数据转化为低维紧凑易于应用的表达而受到广泛关注。网络化数据表示学习的一个重要任务就是重叠社区发现。本文就是为大家介绍基于网络化数据表示学习的重叠社区发现的最新研究。文章内容根据中科院孙冰杰博士在雷锋网GAIR大讲堂的线上直播公开课整理而成。

在近日雷锋网(公众号：雷锋网) GAIR 大讲堂线上直播课上，来自中科院计算所网络数据科学与技术重点实验室的孙冰杰博士为大家做了一场主题为「基于网络化数据表示学习的重叠社区发现研究」的分享，详细介绍了他们团队最近在基于网络化数据表示学习的重叠社区发现研究上的相关工作。

孙冰杰，中科院计算所博士研究生，主要研究方向为网络结构分析，网络表示学习。

分享内容：

我将从以下四个方面对我们团队最近所做的研究做详细介绍。

• 研究背景及挑战

• 对称编解码重叠社区发现方法：SEND

• 重叠社区发现方法加速研究

• 总结

首先看我们研究工作的背景及挑战。

大数据领域中大部分数据是以网络形式进行组织的，比如社交媒体中的社交网络，科研领域中的引用网络，生物领域的中蛋白质相互作用网络，以及交通领域中的航空网路或路网。网络化数据之后节点之间的复杂关系是导致大数据处理困难的重要原因。

网络化数据在不同粒度下对应的理论与应用研究也是不同的。在微观粒度上，主要研究的是节点层面上的任务，当节点聚集形成社区的时候，研究的是社区层面上的任务。在宏观层面上，我们研究的是在整个网络上的任务。

在这次分享上，我们主要研究在中观粒度下的社区发现任务。它主要由三元闭包理论和强弱连接理论为支撑，主要支撑的应用有社区发现应用等。

中观粒度上的社区发现任务：向下可通过节点表示支持微观粒度的任务，向上可通过网络生成支持宏观粒度的任务。

基于网络化数据表示学习的重叠社区发现所面临的问题和挑战

相对于传统节点表示，它的功能是比较单一的，只支持重叠社区指示，无法支持一些其他的任务。但现有的重叠社区指示方法没办法用在大规模网络上。这是针对社区指示能力和多任务支持能力之间的矛盾以及海量数据处理任务的挑战。

为此我们团队做了两方面的工作。

工作一：非负对称编解码模型

节点表示的社区指示能力需要满足多种约束条件。一般需要满足三个约束条件，非负性，稀疏性和分布性。

节点表示的多任务支持能力

需要节点表示能充分恢复数据在原始空间中的相似性关系，对节点表示添加的约束越多，对数据的恢复能力影响越大。因此这之间是矛盾的。矛盾主要体现在基于网络化数据表示的社区发现相关工作。     

工作一是针对重叠社区得到节点表示的社区表示能力和数据还原能力之间的矛盾。目标是保证节点表示的社区指示能力和对原始数据的还原能力。

所面临的问题：

• 如何在数据恢复过程中对节点表示进行约束增加指示能力。

• 传统的OCD只优化解码过程，节点表示功能单一，不能应用于其他任务。

• OCD节点表示的显示约束使优化困难

解决方案：用户点表示同时对原始数据进行编解码操作，保证学习到高质量节点表示。通过编解码过程对对称性节点表示进行隐式约束，保证指示能力。

具体来说，OCD模型通过重构输入数据学习节点表示，通过正则项等对节点表示进行显式约束，保证节点表示的指示能力。但传统的OCD目标函数相当于只优化了解码过程（生成原始数据）

OCD目标函数忽略了编码过程，导致模型学习到的节点表示无法充分体现节点在原空间中的相似性，因此应用在下游任务上准备性较低，且无法处理新样本数据。

以上提出的对称编解码模型可以同时解决节点表示的指示能力和对多种下游任务的支持能力。

通过优化编码和解码过程保证节点表示的数据还原能力，通过隐式约束保证节点表示的社区表示能力，从而最终在多种类型网络的多个任务上取得了目前最好的效果。

进一步介绍这个模型的普适性，我们希望这个节点表示能够用在更多的任务上。因此我们采用了多种类型的网络，比如说二部网络，有向网络、有权网络、层次网络等，也采用了多种类型输入，比如说节点序列输入，邻接矩阵输入等。

工作小结：本文工作针对重叠社区发现得到的节点表示存在的“指示能力和多任务支持”之间的矛盾，设计了一种同时优化编解码过程的模型，可以保证节点表示的指示能力并且在多种类型网络的多个任务上取得了最好的效果。

工作二：重叠社区发现方法加速研究

现有的重叠社区发现方法存在“速度与精度”之间的矛盾，在面临大规模网络时，无法拿来急用。

关于问题一，如何选择高质量的参数迭代初始点。提出利用一个与非凸目标函数近似的凸目标函数的优化结果作为非凸目标函数优化的迭代初始点，以保证最终速度和效果。

重叠社区发现的模型选择

关于问题二，解决由迭代过程的复杂性带来的优化困难问题。传统的应对迭代过程复杂性的方法是采样和近似。这类方法是影响精度且仍然不够快。

解决方案：网络结构局部聚集特性和节点表示的稀疏性，相应地设计了“维度级”和“连边级”两级加速策略，对模型进行加速。 

工作小结：针对基于泊松模型的重叠社区发现方法，目标函数的非凸性和迭代过程的复杂性，提出了两种加速策略，分别解决了初始点选择问题和迭代过程复杂问题。可以处理真实大规模网络。

综上所述：针对重叠社区发现任务，我们主要解决了三个问题。编解码模型解决了重叠社区发现得到的节点表示的社区指示能力和数据恢复能力之间的矛盾。快速初值模型解决了目标函数非凸性带来的可扩展性问题。两级加速模型解决了优化过程复杂性带来的可扩展性问题。

视频回放链接：http://www.mooc.ai/open/course/357

。