网络数据的表示学习是今年机器学习和数据挖掘挖掘的热点，这也为网络数据分析提供了新的范式。图表示学习（图嵌入）的目标是将图结构数据投射嵌入到低维的连续空间，同时保留图结构的内在属性。大量的研究表明，学习到的图表示可以有效帮助各种图结构的数据挖掘任务。然而目前的网络表示学习算法要么存在不适用于大规模网络的问题，要么可能存在精度低的问题。
为了更快地在大规模数据上学习有效的图表示，我们提出了ProNE算法。ProNE的主要流程步骤如图所示。ProNE由两个步骤组成，稀疏矩阵分解步骤和谱传播步骤。首先，我们在建模图结点的相似度和负采样的过程中，充分利用了图结构的稀疏性，从而将图表示学习化归为了稀疏矩阵的分解，并使用randomized svd快速地得到了初步的图表示。
接着，为了更进一步地考虑高阶的图信息，我们借助了Cheeger不等式对图的谱空间和图分割的联系进行了分析，从而在图的谱空间设计了带通的滤波器，通过调整图的特征值让图体现出全局的聚类效果和局域的平滑效果。我们在新图上传播第一步的初始图表示，就得到了ProNE的结果。我们在PPI、Wiki、BlogCatalog、DBLP和Youtube等千级结点到百万级结点的图上进行了验证实验。
实验表明，和DeepWalk、node2vec、LINE、Grarep、HOPE等算法相比，ProNE不仅拥有不逊的精度表现，更有10-400倍的速度提升。我们在亿级结点的模拟图上进一步验证了ProNE的可扩展性。另外，ProNE的谱传播步骤作为一种通用的图表示的提升方法，值得进一步的研究。ProNE在YouTube百万级的网络上只需要10分钟就可以完成所有节点的表示学习。
速度比最快的算法LINE快9倍，比node2vec快400倍。在精度方面，ProNE在以上五个数据集上都明显好于几个对比的方法（包括DeepWalk、LINE、node2vec等）。我们还和之前的NetMF方法进行了对比，NetMF是把传统方法都统一到矩阵分解的框架下，在精度上得到了提升，但速度比较慢。相比NetMF，ProNE进一步提高了精度。提高的原因来自谱传播。
于是我们对谱传播做了进一步的分析，发现原来谱传播可以大大提高不同方法的精度。从某种意义上来说，谱传播可以作为一个通用的框架，来提升不同网络表示学习方法。