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

A Network Embedding Method Based on Graph Folding

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

Abstract: With the full application of information technology, information networks are becoming ubiquitous. Social networks, citation networks, telecommunication networks, and even biological networks have made information network research attract the attention of researchers in many disciplines. Network embedding is a low-dimensional vector representation learning method of nodes that preserves information such as network topology and node content. In the low-dimensional space, network analysis and mining tasks may be easier to solve, and the computational complexity of tasks may also be lowered. This paper designs and implements a network embedding method based on complete subgraph folding. This method regards the k-complete subgraphs of the target network as supernodes and uses an arbitrary network embedding algorithm to learn the vector representation of supernodes in the new network of supernodes. Then we use the learned vector representation to initialize the members’ vector representation of the supernode, after that, the target network will be fed into an arbitrary network embedding algorithm and learn to get the final vector representation of nodes. In this paper, we select to use Deepwalk algorithm in the experiments. Experiment results show that the proposed method significantly improved the speed of network embedding. At the same time, the node vectors learned by the proposed method also out-performed the original Deepwalk algorithm in selected downstream applications.