IJCAI 2019 | ProNE: 高精度快速网络表示学习算法

论文作者：Jie Zhang， Yuxiao Dong， Yan Wang， Jie Tang， and Ming Ding

论文地址：http://keg.cs.tsinghua.edu.cn/jietang/publications/IJCAI19-Zhang-et-al-ProNE-fast-and-scalable-network-representation-learning.pdf

代码& 数据：https://github.com/THUDM/ProNE

网络数据的表示学习是今年机器学习和数据挖掘挖掘的热点，这也为网络数据分析提供了新的范式。图表示学习（图嵌入）的目标是将图结构数据投射嵌入到低维的连续空间，同时保留图结构的内在属性。大量的研究表明，学习到的图表示可以有效帮助各种图结构的数据挖掘任务。然而目前的网络表示学习算法要么存在不适用于大规模网络的问题，要么可能存在精度低的问题。

为了更快地在大规模数据上学习有效的图表示，我们提出了ProNE算法。ProNE的主要流程步骤如图所示。ProNE由两个步骤组成，稀疏矩阵分解步骤和谱传播步骤。

首先，我们在建模图结点的相似度和负采样的过程中，充分利用了图结构的稀疏性，从而将图表示学习化归为了稀疏矩阵的分解，并使用randomized svd快速地得到了初步的图表示。接着，为了更进一步地考虑高阶的图信息，我们借助了Cheeger不等式对图的谱空间和图分割的联系进行了分析，从而在图的谱空间设计了带通的滤波器，通过调整图的特征值让图体现出全局的聚类效果和局域的平滑效果。我们在新图上传播第一步的初始图表示，就得到了ProNE的结果。

我们在PPI、Wiki、BlogCatalog、DBLP和Youtube等千级结点到百万级结点的图上进行了验证实验。实验表明，和DeepWalk、node2vec、 LINE、 Grarep、HOPE等算法相比，ProNE不仅拥有不逊的精度表现，更有10-400倍的速度提升。我们在亿级结点的模拟图上进一步验证了ProNE的可扩展性。另外，ProNE的谱传播步骤作为一种通用的图表示的提升方法，值得进一步的研究。下图和表给出了ProNE以及对比的几个算法在5个数据集上的表现。ProNE在YouTube百万级的网络上只需要10分钟就可以完成所有节点的表示学习。速度比最快的算法LINE快9倍，比node2vec快400倍。

在精度方面，ProNE在以上五个数据集上都明显好于几个对比的方法（包括DeepWalk、LINE、node2vec等）。我们还和之前的NetMF方法进行了对比，NetMF是把传统方法都统一到矩阵分解的框架下，在精度上得到了提升，但速度比较慢。相比NetMF，ProNE进一步提高了精度。提高的原因来自谱传播。于是我们对谱传播做了进一步的分析，发现原来谱传播可以大大提高不同方法的精度。从某种意义上来说，谱传播可以作为一个通用的框架，来提升不同网络表示学习方法。

表：不同对比方法在5个数据集上的实验效果（精度）

学术头条已建立微信交流群，想进群的同学请加学术君微信：AMiner308，记得备注：名字+单位/学校噢！