High performance optimization and acceleration for randomWalk, deepwalk, node2vec (Python)
deepwalk、node2vec的高性能优化 转自知乎: https://zhuanlan.zhihu.com/p/348778146 原作者:马东什么 首先是graph的存储问题,看了很多实现node2vec或deepwalk的library,大都是以networkx或是类似的python class对象为graph的存储形式进行开发,首先我们需要知道目前单机版的deepwalk和node2vec的主要的性能瓶颈在random walk部分,因为底层的word2vec基本上都是直接调用的gensim的word2vec(gensim的word2vec基于c++开发,目前新版的gensim的word2vec的fast version使用了cython代替了原来的一些逻辑实现,个人感觉从word2vec层面再去做优化太复杂了,也很难比gensim做的更好,除此之外另一个思路就是用tf.keras或torch来实现word2vec,借用gpu的算力来试图击败gensim,然而看完这几篇,我心灰意冷了: Word2vec on GPU slower than CPU · Issue #13048 · tensorflow/tensorflow[github.comDoes Gensim library support GPU acceleration?stackoverflow.com graph通常以相互引用的内存指针的方式存储在内存中,这意味着每个节点在内存中都位于不同的位置,这种基于基于链表的思想,使得内存访问的速度成为了主要的瓶颈,因为每次从一个节点移动到另一个节点,都需要在内存中寻址和查询,一种更好的方式是把节点都打包到数组中,因为数据的内存地址一般是连续的,在内存访问上的开销要小很多;(这里还没有提到networkx本身用纯python编写导致的较低效的编译效率问题,具体可见: 马东什么:为什么python这么慢?numba解决了什么问题? ) 一个较好的解决方案就是使用scipy.sparse.csr_matrix对graph进行存储和后续的访问等, csr_matrix可见下: 马东什么:scipy sparse 中稀疏矩阵的常见存储方式zhuanlan.zhihu.com 可以看到,通过将graph转化为csr_matrix,利用其巧妙地存储方式,可以大大提高节点和节点之间的访问效率。 下面就来看一个非常nice的小众的graph library,csr_graph和nodevectors,nodevectors基本上是对csr_graph做的封装,底层的逻辑直接使用了csr_graph的接口api,所以直接研究csr_graph即可。 VHRanger/CSRGraphgithub.com: """ This top level python class either calls external JIT'ed methods or methods from the JIT'ed internal graph """ def __init__(self, data, nodenames=None, copy=True, threads=0): """ A class for larger graphs. NOTE: this class tends to "steal data" by default.
…