【ETH博士论文】利用图上的全局信息进行机器学习，217页pdf

将数据表示为图在生物化学、社交网络、交通网络、自动驾驶和天气预测等诸多领域中越来越普遍。图的流行源于其灵活的表达方式和模拟交互的内在能力。然而，这种丰富的表示方式在对数据建模时提出了独特的挑战，需要在尽可能多地获取图的信息与保持计算可行性之间找到平衡。经过几十年的嵌入方法和图核方法等多种方法的探索后，现在的焦点已转向可以在图上操作的深度学习方法的发展。这些方法，被称为图神经网络(GNNs)，通过邻域聚合更新每个节点的表示。尽管GNNs在实证上取得了强大的成功，但最近的工作发现了它们的一些局限性，例如无法在图中长距离传输信息，以及在区分非同构图方面的限制。这些局限性直接与图神经网络的设计范例相关，该范例通过邻域聚合模型图中的局部结构信息。虽然这种范式编码了相关和关键的信息，但如何最好地抵消由此产生的局限性仍然是一个开放的问题。

本论文探讨了全局信息在生成有意义的图表示中的作用，这些图表示不受邻域聚合问题的影响。我们并不寻求取代现今强大的邻域聚合方法，而是研究全局信息如何补充或提供图中局部信息的替代视角。 本论文的第一个贡献是介绍一种将图表示为高维曲线的新颖方式，我们称之为过滤曲线。过滤曲线是一种通过在多个尺度上捕捉信息来生成图的全局表示的有效方法，可以完全无参数。基于曲线的表示还带来了其他好处，比如直接创建图的向量表示的方法，使其可以与标准的机器学习算法一起使用。除了其效率和易用性之外，我们发现我们最简单的过滤曲线形式已经达到了与更复杂、高度参数化的最新竞争方法竞争的实证性能，这证明了全局图表示的价值。

第二个贡献是研究如何结合全局和位置信息来改善图表示。我们引入了一种结构感知的Transformer，它结合了来自消息传递GNNs的局部结构信息和来自Transformer架构的全局信息，这是第一个将Transformer和任意GNN集成到一个单一模块的图Transformer。我们通过引入一种新的结构感知自注意力计算来实现这一点，该计算基于子图在感兴趣的节点处的相似性过滤节点，使得基于结构和属性相似性的比较更加稳健。此外，我们抽象这个公式，并提供一个可以定制到感兴趣的领域的通用框架。我们的图Transformer在几个基准数据集上达到了最先进的性能，并且优于架构的仅全局和仅局部等效项，突显了结合这两种图视角的潜力。 最后，第三个贡献是对当前评估图生成模型的过程的实证分析，该过程依赖于全局图摘要统计和最大平均差异（MMD）。我们发现了社区采用的当前程序中的一些问题，这在最坏的情况下会导致伪结果，因此我们提出了一个修改后的工作流程来避免这些情况。

我们通过为将全局和局部信息结合在图表示中的未来工作提供展望来结束这篇论文。随着越来越多的新领域开始将它们的数据表示为图，如何学习图的有意义表示的范式可能会发生变化或需要新的方法。从这个角度来看，我们预期将全局信息融入图表示的提出的方法将在图学习的当前和未来应用中证明其实用性。