【康奈尔博士论文】大规模图上准确高效的表示学习 203页

近年来，图结构数据的表示学习受到了广泛关注，这些数据在多种现实世界领域中广泛存在，涵盖了基础物理交互、生物系统、社交网络和逻辑电路等领域。然而，现有的图表示学习（GRL）模型在准确性和效率之间存在较大的矛盾。 首先，许多现实世界中的图（例如社交网络和逻辑电路）通常非常庞大，包含数百万甚至数十亿个节点和边，这对模型在训练和部署过程中的效率构成了巨大的挑战。此外，不同领域的图结构复杂且多样，同时也容易受到对抗性攻击，这些攻击通过添加或删除节点和边来扰乱图的拓扑结构。这些图的特性要求模型架构足够复杂，以生成高质量的图表示，而这往往伴随着巨大的计算开销和内存消耗。 在本论文中，我们提出了针对大规模图应用的可扩展、硬件友好、富表现力和鲁棒的图表示学习模型的研究解决方案。我们首先提出了 GraphZoom，一种快速准确的多级图表示学习方法。GraphZoom 利用轻量级算法，通过迭代减少图的规模，并基于谱图理论逐步精炼图表示，从而在保证理论精度的同时，大幅提升训练速度。与现有方法相比，GraphZoom 实现了 40.8 倍的训练加速，同时保持了相当甚至更好的准确性。 其次，我们开发了 HOGA，一种面向大规模电路图的可扩展且具有普适性的图表示学习方法，通过采用基于跳跃的图注意力机制（hop-wise graph attention scheme）。HOGA 不仅在挑战性的电路问题上超越了现有的图表示学习模型，而且通过减少图依赖带来的通信开销，能够更好地支持分布式训练，从而适用于工业规模的电路应用。 第三，我们提出了 Polynormer，一种具有线性复杂度的富表现力图变换器模型。我们从多项式函数的角度理论证明了 Polynormer 在表达能力上的优势。我们的广泛实验表明，Polynormer 在多种主流图数据集上达到了最先进的结果，并且在 Google 提供的工业规模数据集上，预测 TPU 上 AI 模型运行时的任务时，比流行基准模型提高了 31.8%。 最后，我们提出了一种高效的图拓扑学习方法 GARNET，用于应对图对抗攻击下的准确图表示学习。我们通过理论分析表明，GARNET 能够在接近线性复杂度下有效恢复来自对抗性图中的关键结构，这使得其在广泛的对抗图数据集上相较于先前的鲁棒图表示学习模型，准确性提高了最多 10.23%。