【博士论文】最优传输图表示学习，204页pdf

在机器学习（ML）中，一个关键的挑战是设计能够从图中高效学习的模型。这些图由带有属性的节点组成，并具有一个编码它们关系的预定结构。图表示学习（GRL）旨在将这两个异质性源编码为一个向量图嵌入，以便进行下游任务。在这个领域，最优传输（OT）在将图视为离散概率分布的意义上提供了有意义的比较。本论文通过OT的视角关注GRL，两个概念都在专门章节中介绍。现代的有监督GRL主要依赖图神经网络（GNN），它通过两个主要元素隐式地编码图拓扑：通过消息传递的节点特征嵌入和通过专门形式的池化的聚合。在这篇论文中，我们介绍了一个新的观点，将距离一些可学习的图模板的距离置于图表示的核心。这种距离嵌入是通过OT距离构建的：融合Gromov-Wasserstein（FGW）距离，它通过解决一个软图匹配问题同时处理特征和结构的不相似性。我们假设FGW距离到一组模板图的向量具有强大的区分能力，然后将其提供给一个非线性分类器进行最终预测。这种距离嵌入作为一个新的池化层，称为TFGW，并可以利用现有的消息传递技术来促进有意义的特征表示，这是端到端学习的。我们在几个图分类任务上实证验证了我们的说法，其中我们的方法在表达性和泛化能力方面都优于内核和GNN方法。本论文的另一个贡献旨在使词典学习（DL）适用于图数据集分析，这是无监督表示学习的关键工具。DL解释向量数据为几个基本元素的线性组合，通过与单一环境空间相关的不相似性来评估学到的表示的质量。由于图描述了它们自己的空间，我们提出了第一个适应于图词典学习（GDL）的线性方法，使用(F)GW作为数据拟合项。在我们的工作中，图被建模为图原子的凸组合，通过在线随机算法估算。GDL通过一个新的上界完成，该上界可以用作FGW在嵌入空间中的快速近似。我们实证地显示了我们的方法对于图聚类、分类、完成以及在线图子空间估计和跟踪的兴趣。最终，位于OT核心的质量保守性，在对比两个图的所有节点时强加了一个耦合，这在GRL中有特定的含义。通过FGW学习结构和特征表示对于由将图建模为概率分布所诱导的节点相对重要性非常敏感。管理这一额外的自由度，正如我们所做的，通过在TFGW中增加最小的计算成本但对GDL增加显著的模型复杂性来改进基于(F)GW的模型。因此，我们建议通过引入一种新的基于OT的差异，称为半松弛（融合）Gromov-Wasserstein差异（sr(F)GW），来解决(F)GW中质量保守性约束的限制。srFGW提供了两个图之间的对应关系，同时在目标图中寻找一个重新加权的子图，与输入的(F)GW距离最小。后者可以比(F)GW更有效地估计，并与专门用于图分割的方法竞争，同时更具通用性。此外，估计一个srFGW“重心”引入了一个新的DL，其中图被嵌入为单个图原子的重新加权子图。与其他基于DL的竞争者在各种无监督任务上竞争有利，同时计算速度明显更快。