图嵌入作为一种有效的图分析技术近年来备受关注，其旨在将图数据映射为低维稠密向量，进而应用到机器学习任务中，如链接预测、节点分类、推荐系统、可视化等。然而，现有图嵌入技术中普遍存在计算开销大和有效性难以保证的问题，对大规模图则更为甚之。

信息存储与光显示功能实验室博士生方鹏，在王芳教授、施展副教授的指导下，通过分析基于随机游走的图嵌入技术发现，现有方法采用的“一刀切”策略预先设定了随机游走的路径长度和每个节点的采样次数，一方面影响了训练模型的有效性，另一方面更是严拖累了计算性能。针对上述问题该工作设计了一种高效且可拓展的熵驱动图嵌入模型(HuGE)：（1）基于共同邻居和节点的度两种属性提出一种混合属性感知的随机游走策略来捕获节点的特征，既保证了节点间的相似性，也避免了游走过程中回溯产生冗余的问题；（2）基于信息熵和相对熵分别来决定游走路径长度和节点重复采样次数，解决了现有模型中需要依靠人工经验设置超参数的问题。通过大量实验论证，在不同规模图数据集上，与现有流行的图嵌入技术相比，HuGE不仅可以为下游任务提供超过10%的收益，还可以实现22至126倍的加速。

该研究题为“HuGE: An Entropy-driven Approach to Efficient and Scalable Graph Embeddings”发表在中国计算机学会推荐的A类国际学术会议IEEE International Conference on Data Engineering (ICDE 2021)。该研究工作得到了国家自然科学基金（No. 61772216、No. 61821003、No. U1705261）等项目的资助。

图1 HuGE总体框架

图2 HuGE与多种现有图嵌入技术在不同图数据集上的运行时间