很荣幸能够参与到鲲鹏众智项目中。我们团队参与的项目为图分析算法代数化优化三期，要求完成 3 个图算法的代数转换求解的理论体系构建和优化，给出等价性推导过程和正确性证明，基于 SuiteSparse 完成算法求解原型 demo 开发，并且性能达到指定目标。

首先分享一下我对于图代数化计算这一理念的理解和心得。图作为当今计算机科学中常见的数据结构，衍生出了非常丰富问题和算法。由于在实际应用中使用的图数据规模往往是巨大的，使得很多即使是多项式甚至是线性复杂度的图分析算法都面临效率上的不足。并行化是优化算法性能的重要手段，然而由于图分析算法的复杂多样，往往需要对一个图算法进行定制的线程控制和调度设计才能够起到有效的加速效果，大大地提升了设计并行的图分析算法的难度。图代数化计算则是提供了一种通用的并行框架，通过将图上的操作转化为代数计算的方式，即可以调用成熟的代数计算库来进行高效地并行计算。这种理念可以将并行算法开发者从复杂的线程控制和调度中解放出来，为开发并行的图分析算法提供便利。而且，由于代数计算库的高度成熟，使用图代数化计算实现的图算法对比相应的并行算法往往也能带来性能上的提升。

接下来分享一些我们团队工作中的贡献。我个人在项目中主要负责标签传播算法的代数化实现以及优化。标签传播算法是社交网络分析中的一个常见算法，其通过迭代的方式将图中每个节点的标签更新为其邻居中数量最多的标签，直至收敛或到达最大迭代次数为之。这是一个已经存在代数化实现基线的算法。该基线使用一个对角矩阵来存储每个节点的标签，在每一轮迭代中，将该对角矩阵和图的邻接矩阵相乘，其结果的每一行便对应一个结点的各个邻居的标签。然而，该算法在每一轮迭代中需要统计各个标签出现的次数，在该基线的代数化实现方式下没有办法使用代数算子进行这一步骤的计算，只能通过效率较低的排序加遍历的做法来实现计数的功能。我们团队的主要创新即是针对这一不足提出了一种新的代数化实现方式，通过使用行独热矩阵代替对角矩阵存储结点标签的方法，高效地使用代数算子在乘法过程中附带完成了计数步骤，从而大大提升了标签传播算法的性能。除却这一创新点外，我们也在工程层面上进行很多细节的优化，这些优化主要集中在如何快速地构建我们想要的矩阵和向量，如何减少频繁且重复地内存分配、访问和释放等方向上。虽然这些工作都不能称得上是创新，但一方面极大地锻炼了我的动手能力，另一方面也促使我对于加速代数计算的逻辑和原理有了更深的理解。

通过我们的项目经历可以看到，即使是同样的算法，其也可能存在不同的代数化实现方式，且不同的实现方式之间也可能存在较大的性能差别。这也意味着，虽然设计图代数化算法不需要自己动手控制和调度线程，但是想要设计出贴合代数计算加速逻辑的高质量图算法代数化形式，还是离不开对于代数计算加速原理的学习和理解。

最后，十分感谢众智计划给予我们这次开拓眼界和动手实践的机会。感谢团队中的老师和同学们的指导和帮助，也十分感谢对接的华为专家们提供的建设性的意见，在这样一次项目中我真的收获颇丰。

复旦大学--大数据学院--图计算与知识管理实验室--杨博驭

指导老师--郑卫国