在面向图结构数据的机器学习领域，图核方法模型和图神经网络模型是两种被广泛使用的模型。近年来，许多工作试图将图核方法模型的高度可解释性、图神经网络模型的高阶特征提取能力相互结合起来，其中图神经正切核（GNTK）模型就是典型代表之一。在形式上，图神经正切核模型属于图核方法模型，但本质上等价于一个输出特征维度是无限大的图神经网络模型。
图神经正切核由于其对图神经网络可训练性和表达能力进行理论分析的重大意义一直受到持续性的关注，现有的相关方法效果已经十分优秀。现有的方法仅考虑了有边相邻的节点之间的消息传递，并没考虑到节点的重要程度信息，也不能从较远的节点传播信息，并且模型训练开销大。为此，我们首先基于多头注意力机制提出增强型的图神经正切核模型AttentionGNTK，然后利用量子并行计算的优势对计算过程进行加速，对应的量子模型被称为GraphQNTK。
论文链接：
https://openreview.net/forum?id=RBhIkQRpzFK
代码链接：
https://github.com/abel1231/graphQNTK
该工作的亮点总结如下：
- 注意力增强型的GNTK。 原始的GNTK的聚合函数是相对简单的，将其自身的感受野（respective field）限制在邻域内。本文提出的方法将感受野扩大到整幅图并引入了多头注意力机制，扩大了节点间消息传递的半径，并使消息传递聚焦在具有相似关键特征的节点上。
- 模型的训练过程等价于无限宽极限下的拥有注意力机制的图神经网络。 一般情况下，训练一个有注意力的深层图神经网络是很困难的，寻找一组最合适的超参数也是极为棘手的，特别是当GNN输出的宽度、注意力层输出的宽度或头（head）的数量变得很大时。利用神经正切核（NTK）理论，我们将无限宽度的多头注意力机制融入到GNTK中，接着，通过核方法来替代训练无限宽极限下的拥有注意力机制的图神经网络。
- 量子计算技术的加速效果。尽管GNTK等价于训练无限宽图神经网络，但其代价仍然相对于数据量呈二次曲线增长，这对于大数据集来说是难以解决的。为此，我们重新设计了注意力增强型的GNTK，将其拆分一个个近似线性的模块，并使用量子线性代数算法（quantum basic linear algebra subroutines）将它们重新组合起来，最终形成量子图神经正切核核方法GraphQNTK。由于量子计算的并行性质，GraphQNTK从理论上将计算复杂度降低到O（N）。
一、 背景
1.1 图神经网络 (Graph Neural Network)：
图神经正切核 (Graph Neural Tangent Kernel，GNTK)： 为了分析图神经网络的可训练性和表达能力，深度学习理论研究工作者将神经正切核（NTK）理论推广到图数据处理问题上，并提出了图神经正切核模型[1]，它将这种过度参数化的图神经网络表示为提取非线性特征的线性化模型。形式上，图神经正切核属于图核方法，拥有优化简单、模型可解释性强等优点；本质上，训练一个图神经正切核等价于训练一个无限宽的图神经网络，因此该模型也继承了图神经网络可以提取节点高阶特征的优势。具体来说，图神经正切核是根据网络输出相对于网络参数的梯度之间的内积来定义的
1.2 量子机器学习 (Quantum Machine Learning)：
近年来，量子计算技术的兴起带动了一大批量子相关的研究和应用，其中量子机器学习受到了大家的广泛关注。相对于传统的机器学习或者深度学习方法，量子机器学习的潜在优势包括使用量子模型挖掘数据（尤其是量子数据）中的潜在特征，或是使用量子算法辅助加速传统模型的训练或者推理过程。目前，从使用的量子计算宏观方法上来划分，量子机器学习模型主要分为两类
- 基于量子变分线路（Quantum Variational Circuit） 的量子机器学习模型：量子线路是在量子计算机中实现量子算法的主流技术路线之一，而量子线路由量子比特和量子门构成。受到传统神经网络的启发，人们将量子线路参数化为可调节、可优化的量子变分线路，赋予了量子线路拟合复杂函数的能力。这类量子机器学习模型通过将经典数据编码到量子态，经过量子变分线路的处理，再经过量子测量得到量子线路的输出，并以此作为量子模型的预测值来和真实标签一起计算损失函数，最后通过经典优化器优化量子变分线路中的可微参数，直到损失函数收敛。目前的量子计算机仍处于NISQ（Noisy Intermediate Scale Quantum）阶段，对量子比特数和量子门数量有着非常严苛的限制，而使用量子变分线路构建的量子算法被视为可以在NISQ阶段发挥量子计算优越性的最主要的方法。
- 基于量子线性代数算法（Quantum Basic Linear Algebra Subroutines） 的量子机器学习模型：量子计算的基础是量子力学，而量子力学的基本假设之一就是封闭环境下量子态的演化是一种酉变换，而酉变换属于线性变换。因此，量子计算这种线性运算法则天生地适用于做线性变换的算法。同时，依赖于量子比特高维空间表征能力（ n个量子比特可以表示 2的n次方维的复空间中的任意点）和量子并行计算能力，量子线性代数算法往往能获得加速效果。然而，在量子计算机上实现量子线性代数算法目前仍是一大难点。因此，基于量子线性代数算法的量子机器学习模型在近期只能在经典计算机上做模拟，尚且无法在真实量子环境下运行，但这种方法可以更好的利用量子计算的潜在优势，所以仍受到了许多学者的关注。本论文提出的方法便基于量子线性代数算法，使用量子算法减少图神经正切核方法的时间复杂度。
二、Motivation
我们的建模动机来源于两方面：
- 其一，已经有量子机器学习成果[3]表明，量子线性代数方法可以被用来加速无限宽多层前馈神经网络所对应的神经正切核的计算过程，同时在推理过程中也可以借助HHL算法来进行加速，并且对应的量子模型获得了指数级的加速效果；
- 其二，图神经正切核GNTK的提出为训练无限宽的图神经网络提供了理论支撑，其计算核矩阵包括两个子过程，即邻居节点特征聚合和中央节点特征更新，其中中央节点特征更新是一个无限宽多层前馈神经网络，该子过程可以通过量子算法进行加速，所以要想使得整个的模型仍可被量子算法加速，就需要对邻居节点特征聚合这一子过程使用量子算法进行重新设计。而邻居节点特征聚合其实也是一个线性变换，恰好满足了量子计算天生适合做线性算法的特性，我们希望依靠量子叠加原理并行计算核矩阵中的元素。同时，我们考虑了一种更为复杂的特征聚合方式，即模型每一次的特征聚合范围将被拓展为整个图。为了实现这个想法，我们引入了无限宽的注意力机制[5]。值得注意的是，我们保留了GNTK原有的邻域特征聚合过程，因为考虑到原始的图结构，邻居节点理应对中央节点传递更多的信息。最后，我们将提出一种特定的酉变换以便在量子计算环境下实现特征聚合这一子过程。
三、方法
相较于原始的图神经正切核方法，我们首先提出了一种注意力增强型的图神经正切核AttentionGNTK，然后利用量子并行计算的优势对计算过程进行加速，对应的量子模型被称为GraphQNTK。
3.1 问题定义
3.2 模型设计
模型设计思路如上图所示。原始的图神经正切核GNTK仅考虑了有边相邻的节点之间的消息传递，并没考虑到节点的重要程度信息，也不能从较远的节点传播信息。训练GNTK等价于训练一个无限宽的GNN，于是我们引入了无限宽的注意力机制来适应这样的极限情况。无限宽的注意力机制指的是注意力层的输出维度是无限大的，头（head）的数量也是无限多的，在这种极限情况下，注意力机制也可以抽象为一个高斯过程，其对应的神经正切核为
通过观察(7)式可以看到，中央节点的特征更新其实就是将协方差矩阵/协方差矩阵的导数矩阵中的元素做统一的变换，参考量子并行的原理，如果可以将协方差矩阵/协方差矩阵的导数矩阵中的元素编码到一个量子叠加态中，那么就存在一个量子酉变换统一地将矩阵中所有元素的值变换到目标值。
对于图神经正切核来说，初始的图神经正切核矩阵以及协方差矩阵均被初始化为节点特征间的内积，也就是说
我们希望借助于QRAM和量子内积估计（Quantum Inner Product Estimation）算法将初始的图神经正切核矩阵以及协方差矩阵编码到量子叠加态中。
为此，我们首先假设存在QRAM可以将节点特征向量以幅度编码（Amplitude Encoding）的方式编码到量子态中，
利用量子内积估计算法，我们在量子叠加态中制备得到了初始的图神经正切核矩阵以及协方差矩阵
通过上述量子线性代数算法的迭代可以实现AttentionQNTK多层模型的的量子近似核估计。最终的核矩阵中的元素将被保存在量子态中。在推理阶段，需要使用这个核矩阵来对未知图进行分类，可以考虑使用量子态层析（tomography）将量子态解析为矩阵表示，但量子态层析的所需的时间可能是指数级大的。为此，当本文所提出的量子算法运行在真实的量子计算机中时，我们建议采用HHL方法来对未知图进行分类，
四、实验结果
我们在10个图分类任务的数据集上验证了所提出方法的有效性。
- 数据集： 我们选择了六个节点特征是离散值的图数据集，包括MUTAG，PROTEINS，PTC，NCI1， IMDB-B， IMDB-M，以及四个节点特征是连续值的图数据集，包括ENZYMES，PROTEINS-Full，BZR，COX2。
- 评价指标： 与之前的图分类相关工作一致，我们采用分类准确度作为评价指标。
- Baseline： 我们对比了几种主流的图神经网络模型和图核方法模型，具体模型可见实验结果表格。
- 实验结果： 下面两张表格展示了我们提出的AttentionGNTK模型和GraphQNTK模型分别在点特征是离散值的图数据集和节点特征是连续值的图数据集上的表现。
可以看到，我们在6个具有离散节点特征和4个具有连续节点特征的图分类任务上取得的结果，AttentionGNTK在七个数据集上表现均优于原始的图神经正切核模型，说明多头注意力机制引入的必要性。至于其他的图核模型和图神经网络模型，我们的模型仍然可以在四个公开数据集上稳定得带来提升。在量子模型之间的对比中，我们的模型在6个数据集上的表现中有4个超过了QS-CNN，不同于我们所提出的全量子图学习模型，QS-CNN中包含了大量的经典模块来提升模型的分类性能。虽然用量子算法重新设计后的模型在分类准确度上有所降低，但理论上量子并行将为模型训练带来平方级的加速效果。
五、总结
我们提出了一个名为 AttentionGNTK 的增强型图神经正切核模型，以改善现有的图神经正切核模型的消息传递机制，同时，我们利用量子计算算法重新设计了AttentionGNTK，提出了GraphQNTK来减少模型训练的时间复杂度。以图分类准确度为评价指标，我们在十个公开图数据集上验证了我们方法的性能且实验结果表明了我们提出的模型能够有效地提升图神经正切核模型的分类准确度，并在降低模型训练的时间复杂度的同时不显著降低分类准确度。
参考文献
[1] Du S S, Hou K, Salakhutdinov R R, et al. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 2019, 32.
[2] Arora S, Du S S, Hu W, et al. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 2019, 32.
[3] Zlokapa A, Neven H, Lloyd S. A quantum algorithm for training wide and deep classical neural networks. arXiv preprint arXiv:2107.09200, 2021.
[4] Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Physical review letters, 2009, 103(15): 150502.
[5] Hron J, Bahri Y, Sohl-Dickstein J, et al. Infinite attention: NNGP and NTK for deep attention networks. International Conference on Machine Learning. PMLR, 2020: 4376-4386.
[6] Jacot A, Gabriel F, Hongler C. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 2018, 31.
[7] Nielsen M A, Chuang I. Quantum computation and quantum information. 2002.
[8] Kerenidis I, Landman J, Prakash A. Quantum algorithms for deep convolutional neural networks. International Conference on Learning Representations, 2020.
作者：唐叶辉
来源：公众号【 sjtuThinklab】
快抢沙发！
