博士论文 | Cornell 2024 | 大规模图上准确高效的表示学习 203页

近年来，人们对图结构数据的表示学习兴趣激增，这种学习在现实世界的各个领域中都很普遍，涵盖了基本的物理交互、生物系统、社交网络和逻辑电路。然而，现有图表示学习 (GRL) 模型的准确性和效率之间存在很大的矛盾。首先，许多现实世界的图（例如社交网络和逻辑电路）非常大，包含数百万甚至数十亿个节点和边，这对模型的训练和部署效率构成了巨大挑战。此外，不同领域具有复杂而多样的图结构，这些结构也容易受到通过添加或删除节点和边来扰乱图拓扑的对抗性攻击。这些图属性需要复杂的模型架构来生成高质量的图表示，这通常伴随着不小的计算成本和内存使用量。

在本论文中，我们提出了涵盖可扩展、硬件友好、富有表现力和鲁棒性的 GRL 模型的研究解决方案，用于在大规模图应用上进行准确而高效的表示学习。

首先提出了 GraphZoom，一种用于快速准确 GRL 的多级方法。GraphZoom 利用轻量级算法迭代地减少 GRL 的图形大小，并基于谱图理论逐步细化图表示，并提供理论保证。与现有技术相比，这使训练速度提高了 40.8 倍，同时准确度相当甚至更高。

其次，我们通过采用跳跃式图注意方案，为大规模电路上的可扩展和可推广的 GRL 开发了 HOGA。HOGA 不仅在具有挑战性的电路问题上优于之前的 GRL 模型，而且通过减轻图依赖性造成的通信开销，对分布式训练也很友好。这使得 HOGA 适用于工业规模的电路应用。

第三，我们引入了 Polynormer，一种具有线性复杂度的富有表现力的图Transformer模型。我们从理论上通过多项式函数证明了 Polynormer 的卓越表现力。我们进行了大量的实验，结果表明 Polynormer 不仅在各种主流图形数据集上取得了最佳结果，而且在 Google 提供的用于预测 TPU 上 AI 模型运行时间的工业级数据集上，其性能比流行的基线模型高出 31.8%。

最后但同样重要的是，我们提出了一种称为 GARNET 的高效图拓扑学习方法，用于在图对抗攻击下实现准确的 GRL。我们从理论上证明了 GARNET 可以有效地从具有近线性复杂度的对抗图中恢复关键结构。与之前的稳健 GRL 模型相比，这在广泛的对抗图上将准确度提高了 10.23%。

论文题目：Accurate and Efficient Representation Learning on Large-Scale Graphs

作者：Chenhui Deng

类型：2024年博士论文

学校：Cornell University（美国康奈尔大学）

下载链接：

链接: https://pan.baidu.com/s/1pHPS_7WgUlxxwlO1Tv5ZKA?pwd=efn6

硕博论文汇总：

链接: https://pan.baidu.com/s/1Gv3R58pgUfHPu4PYFhCSJw?pwd=svp5

本论文的概述。

随着图中节点数量的增加，GRL 训练时间。

非计算图和计算图的比较。

GNN 的计算图。

Transformer 架构概述。

GraphZoom 框架概述。

HOGA 与传统 GNN 的比较 — (a) 用于说明的示例图；(b) GNN 的计算图；(c) 我们提出的方法 HOGA 的计算图。

HOGA

门控自注意力模块概述。

HOGA 和 GNN 的关键计算内核的矩阵视图 — 为简洁起见，我们省略了线性投影层，两个模型的复杂度相同。

HOGA 与 GNN 在全批量和小批量训练下的时间复杂度比较。

通过全批量和小批量训练加速 GNN 上的 HOGA。

HOGA 和 GNN 输入数据的矩阵视图。

(a) 与-反相图的示例，其中每个节点代表一个主输入/输出 (PI/PO) 或一个与门。虚线箭头表示反转边；(b) QoR 预测的概述。我们的方法仅用 HOGA 替换了 OpenABC-D 中的 GCN 模型；(c) 功能推理的概述。我们的方法仅用 HOGA 替换了 Gamora 中的 GraphSAGE 模型。

具有标量节点特征的 3 节点图的玩具示例。

先前工作和 Polynormer 中的注意力方案之间的区别 — （a）先前的 GT 使用局部和全局注意力方案，涉及在每一层同时使用局部和全局注意力；（b）我们采用局部到全局注意力方案，其中局部和全局注意力模块按顺序应用；请注意，为了简洁起见，省略了（a）中的 softmax 运算符和（b）中的注意力规范化。