text: SERS:基于稀疏矩阵乘法(SpMM)的ERS社交网络测量/图最短路径计算方法
  物理学中对网络的建模，对宇宙的探索均离不开对物理世界的建模。
  图模型是一种常见的建模方式，如社交网络、蛋白质网络、病毒传播网络等。
  对图的特征挖掘，除了文本特征外，对图本身的结构测量与挖掘也是一个重要的研究课题。
  在图论中提交的最短路径计算问题，可以从一个邻接矩阵中挖掘出一条两个节点之间的最短路线。
  而本文主要讨论给定一个网络，生成其有向图和无向图，从而得到图的邻接矩阵，在此条件下，如何快速计算全节点最短路径这一任务。
  JERS中提出了基于提前收敛的方法，得到了在CPU平台上，OpenBLAS要优于Numpy的实现;而在GPU上，则用CuPy版本性能更优。
  观察图的输入，邻接矩阵通常为稀疏矩阵，在迭代过程中逐渐变为稠密矩阵，本文的一个思路是在稀疏矩阵计算矩阵乘积时，利用稀疏矩阵乘法来对原流程进行加速，因为稠密矩阵上SpMM比常规矩阵乘法更耗时。
  以微博社交网络为例，8508个节点的邻接矩阵非零元素为617958，实际上，这就是节点的边数，该矩阵的非零元素占总元素(这个总元素数就是8508个节点两两组队，大约是72,386,064)比例为0.008536，是典型的稀疏矩阵。
  因此，利用scipy.sparse的csr_matrix和cupy库中的CUDA版本的cupyx.scipy.sparse中csr_matrix中实现的SPMM对矩阵乘积进行加速，可以大大提升稀疏图上的全节点最短路径(APSP)的计算效率。
  在ERS算法中，每轮计算前非零值占比如图1所示:
  图1 计算前输入矩阵的非零值占比迭代图 考虑到稀疏矩阵乘法(SPMM)算法在稀疏矩阵上的优势，设定了触发SPMM计算的阈值，当输入的非零值元素比例小于0.1时，即占比小于10%，利用SpMM计算;超过阈值，仍用稠密矩阵乘法，即Numpy、CuPy等计算库的实现的常规两矩阵乘法操作。
  在一台32核2.1GhzCPU、128G内存、11G显存的GTX1080Ti显卡的服务器上，运行基于SpMM优化的Numpy版本的ERS算法和SpMM优化的Cupy版本的ERS算法，所得结果对比如图2所示:
  图2 基于SpMM加速的算法与稠密矩阵乘法上的性能对比 由此可见，在CUDA平台上，SpMM加速的S-ERS-CP算法比基于CuPy的ERS-CP算法，性能提高了17.3%;而在CPU平台上，SpMM加速的S-ERS-N算法比基于Numpy的ERS-N算法，性能提高了23.3%。
  事实上，这性能提升仅共四步中的一步，Epoch=1时利用SpMM替换常规矩阵乘法得到的加速提升，而对于一些稀疏图，如每部计算结果的非零元素密度小于阈值的情况，加速的效果将更优。
  结论，SERS算法在输入矩阵和中间计算结果矩阵为稀疏矩阵的图、网络的全节点最短路径计算任务上，有显著的计算耗时优化提升以及内存占用优化提升。
  具体实现可参考。