图表示学习是一种旨在将高维稀疏的图数据映射到低维稠密的向量空间中，同时保留原有图中的属性特征的图分析技术。因其生成的嵌入向量可以有效地应用到机器学习任务中，如链接预测、顶点分类、推荐系统等，近年来备受关注。然而，现实世界中图的规模经常达到百万级顶点和十亿级边的规模，对现有图表示学习方法及系统高效且可扩展地进行特征表示构成了重大挑战。

信息存储与光显示功能实验室博士生方鹏，在王芳教授指导下，提出了一种以信息为中心的基于随机游走的分布式图表示学习系统—DistGER，可以支持具有十亿级边的图数据高效地进行表示学习。为解决随机游走过程中的冗余计算和高通信开销，DistGER提出了一种以增量信息为中心的计算机制，确保在O(1)的时间内进行信息有效性的动态衡量且在计算节点间以常量级进行消息通信；考虑到随机游走固有的随机性和计算节点间负载平衡的要求，DistGER提出了适合随机游走任务特征的多阶邻近性感知的流式图划分策略，以尽可能地提高随机游走过程中对划分子图的利用率，同时，使用动态负载约束来确保各计算节点间的负载均衡；最后，DistGER设计了一个分布式Skip-Gram学习器以优化训练过程中的访问局部性、CPU吞吐量和参数同步效率，从而实现了一个端到端的分布式图表示学习系统。通过实验论证，在不同规模图数据集上，DistGER与最先进的分布式图嵌入系统相比，可以带来2.33倍到129倍的性能加速，平均减少45%的跨节点计算，且在下游任务中带来的增益超过10%。

该研究题为“Distributed Graph Embedding with Information-Oriented Random Walks”被中国计算机学会推荐的A类国际学术会议49th International Conference on Very Large Data Bases (VLDB 2023)录用。该研究工作得到了国家自然科学基金（No. U22A2027、No. 61832020及No. 61821003）等项目的资助。

图1 DistGER整体框架

图2 DistGER与现有分布式图表示学习系统在不同图数据集上的运行时间