算法原理优化

图等价变换

对节点进行聚合与切分，实现图结构等价变化，降低计算量与算法复杂度，提升算法性能。

图压缩

针对图幂律特性实现数据高效压缩，减少内存开销，降低随机访存，提高计算效率。

举例说明

下面以PageRank算法为例进行说明。

PageRank网页排名算法是搜索引擎中对网页进行排名的一种常用算法，本质上是一种以网页之间超链接的个数和质量，分析网页重要性的算法。在PageRank中有两种计算方式，一种是全量迭代：所有节点参与迭代计算和消息更新；另一种是残差迭代：部分节点参与迭代计算和消息更新。相比全量迭代，残差迭代单个消息携带的信息量更多。

在PageRank计算初期，绝大部分的节点均没有收敛，要参与计算，原生算法全流程采用残差迭代方式进行算法收敛，因单个消息携带的信息多，网络和数据传输的量非常大。

我们优化的算法采取残差迭代和全量迭代自适应的方式，大部分节点未收敛时采用全量迭代的方式，仅剩部分节点未收敛时采用残差迭代的方式，这样可以实现shuffle数据通信量减少50%以上。

同时我们采用图压缩的技术，优化内存空间占用。最终实现PageRank算法整体的性能，在不同规模的数据集上，相比原生算法性能可以提高1.5倍到3倍以上。