一种基于图折叠的网络嵌入方法

随着信息技术的广泛应用，信息网络正在变得无处不在，社交网络、引文网络、电信网络乃至生物网络等各类网络让信息网络研究受到了众多学科研究人员的关注。网络嵌入是一种保留网络拓扑信息和节点内容等其他附带信息的网络节点低维向量表示学习方法，在新的低维空间中网络分析挖掘任务可能更容易被解决，任务的运算复杂性也有可能降低。本文设计实现了一种基于完全子图折叠的网络嵌入方法，该方法把目标网络的k完全子图视为超节点，在以超节点为单位的新网络上使用任意网络嵌入算法学习超节点的向量表示，之后把超节点的向量表示作为对应k-完全子图中所有节点输入到任意网络嵌入学习算法的初始值，重新学习获得节点最终的向量表示。本文使用Deepwalk算法进行了实验，实验结果表明，本方法不但大幅提升了网络嵌入的速度，而且本方法学到的节点向量在一些下游应用中的表现也优于纯粹的Deepwalk算法。

从社交网络到万维网，图是呈现各种真实世界信息的普遍方式。给定网络结构，通常需要预测与图中每个节点相关联的信息(通常称为属性或标签)。

这些信息可以代表数据的各个方面。

例如， 在社交网络上，它们可以代表一个人所属的社团，或者代表网络上文档内容的类别。在现实的世界中存在着很多大型的网络，这些网络可能包含数十亿个节点和边，因此很难在整个网络上执行复杂的推理过程。为解决这一问题，降维的技术应运而生。其核心思想是将图中的每个节点转换为一个低维的潜在表示，利用这些表示可以在网络图上进行操作，如社团划分、链路预测等。

传统的图降维的方法在小规模网络上效果良好[1]，但是传统的方法存在着复杂度高的问题，因此使得传统的图降维的方法在大规模网络上并不适用。

近年来随着图表示学习的发展， DeepWalk [2]、Line [3]、Node2vec [4]等算法被提出，这些基于神经网络的方法已被证明具有高度的可扩展性和较高的性能，在大型网络中的分类和链路预测任务上取得了很好的结果。

基于神经网络的方法虽然取得了较好的效果，但是这些方法存在着一些共同的弱点。它们都是局部方法， 更加关注于节点周围的结构， 例如DeepWalk 和Node2vec 利用短随机游走来获取节点的本地邻居。

这种对局部结构的关注导致忽略了全局关系，这就使得学习到的表示可能忽略或根本无法发现重要的全局结构。现实生活中，许多实际网络中通常包含由若干结点组成的完全子图，一些实际网络甚至是由一些完全子图通过公共节点链接而成的[5]，因此在社团划分的角度考虑，在一个完全图内的节点在大概率上可以视为一个社团结构内的节点。

因此通过在网络中寻找完全子图进而折叠， 是一件很有意义的事情。