【博士论文】图表示学习的谱理论与自监督学习

来自清华大学的裘捷中博士论文，入选2023年度“CCF博士学位论文激励计划”初评名单！

https://www.ccf.org.cn/Focus/2023-11-29/798503.shtml

图结构数据在我们身边无处不在，例如社会网络、生物网络和交通网络。图表 示学习算法的设计对图结构数据的理解、分析和推理至关重要。近年来，以节点嵌 入和图神经网络为代表的图表示学习算法得到了蓬勃发展和巨大成功。本论文从 多个角度研究图表示学习，包括节点嵌入的谱理论，基于谱理论的大规模节点嵌入 的算法，图神经网络的自监督学习算法和图表示学习在社会影响力预测中的应用。

首先，本文提出了节点嵌入的谱理论框架。以 DeepWalk 和 node2vec 为代表 的基于随机游走采样的节点嵌入算法在许多图学习任务上获得成功，但其背后的 机理却鲜为人知。这限制了节点嵌入算法的应用和发展。本文分析了这些算法在 无限采样和有限采样两种情况下的行为：在无限采样时，将这些算法统一到矩阵 分解框架中，并建立起被分解矩阵和图谱理论的关系；在有限采样时，通过分析 马尔科夫链上共现矩阵的收敛速度，给出了这些算法的样本有效性和时间复杂度。 其中，为了对有限采样的情况进行研究，证明了马尔科夫链矩阵切诺夫界，对著名 的概率论工具切诺夫界进行了推广。

其次，本文基于节点嵌入的谱理论提出了经济、可扩展且高质量的节点嵌入 算法，用来嵌入十亿节点和千亿条边的超大图。随着网络数据的爆炸式增长，工 业界对超大图节点嵌入的需求越来越旺盛。本文提出使用直接矩阵分解而不是随 机梯度下降来解决节点嵌入问题；随后通过算法和系统协同设计，结合了随机游 走矩阵多项式稀疏化、高性能图引擎、并行哈希和高性能随机奇异值分解等技术， 实现了可扩展性和高性能。 再次，本文探索了图神经网络的自监督学习算法。基于自监督学习的预训练 方法在计算机视觉和自然语言处理领域已经取得了巨大成功。受此启发，提出了 基于自监督的图神经网络预训练框架图对比编码。该框架可以从图数据中进行自 监督预训练和结构信息的学习，并且在下游的十个图数据集和三个图学习任务中 取得和基线算法相似或更好的效果。 最后，本文研究了如何将图表示学习应用于社会影响力预测。本文将社会影 响力预测建模成图分类问题，并提出了端到端的基于图表示学习的模型；该模型 的预测效果显著优于基于人工特征和领域知识的传统模型。