线性代数考研，线性代数考研大纲
在面向图结构数据的机器学习领域，图核方法模型和图神经网络模型是两种被广泛使用的模型。近年来，许多工作试图将图核方法模型的高度可解释性、图神经网络模型的高阶特征提取能力相互结合起来，其中图神经正切核（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从理论上将计算复杂度降低到 。
一、 背景
1.1 图神经网络 (Graph Neural Network)：
首先考虑一种简单的图神经网络模型，在第 层中该模型先使用sum将邻居节点的特征 聚合起来
然后使用多层神经网络MLP更新中央节点的特征
其中 和 是归一化系数。当每层的输出趋向于无穷大，即 在 时的输出维度趋向于无穷大时，这样的过参数化图神经网络被称为无限宽的图神经网络。由于计算资源的限制，很难直接部署和训练这样的一个模型。
图神经正切核 (Graph Neural Tangent Kernel，GNTK)：为了分析图神经网络的可训练性和表达能力，深度学习理论研究工作者将神经正切核（NTK）理论推广到图数据处理问题上，并提出了图神经正切核模型[1]，它将这种过度参数化的图神经网络表示为提取非线性特征的线性化模型。形式上，图神经正切核属于图核方法，拥有优化简单、模型可解释性强等优点；本质上，训练一个图神经正切核等价于训练一个无限宽的图神经网络，因此该模型也继承了图神经网络可以提取节点高阶特征的优势。具体来说，图神经正切核是根据网络输出相对于网络参数的梯度之间的内积来定义的
图神经正切核通过迭代计算高斯过程的协方差矩阵 (covariance)及其导数 (derivative covariance)来间接获得。对于图神经网络的聚合函数(1)来说，图神经正切核以及协方差矩阵的表达式为
而对于中央节点的特征更新函数(2)来说，协方差矩阵及其导数的表达式其实就是MLP的神经正切核演化过程
而第 层的图神经正切核可以写为
将最后一层得到的 中的所有元素做相加，可以得到图神经正切核的最终表达形式
这其实等价于在图神经网络的最后一层使用了sum_pooling来把所有节点特征加和在一起作为整个图的特征。 是一个 大小的对称矩阵，每一个元素表示两幅图之间的相似度。
如果输入了一个新的图，那么对于这个图的类别预测可以写为
其中 中的元素是输入图和训练集之间的GNTK值，而 是one-hot编码后的真实标签。
1.2 量子机器学习 (Quantum Machine Learning)：
近年来，量子计算技术的兴起带动了一大批量子相关的研究和应用，其中量子机器学习受到了大家的广泛关注。相对于传统的机器学习或者深度学习方法，量子机器学习的潜在优势包括使用量子模型挖掘数据（尤其是量子数据）中的潜在特征，或是使用量子算法辅助加速传统模型的训练或者推理过程。目前，从使用的量子计算宏观方法上来划分，量子机器学习模型主要分为两类
基于量子变分线路（Quantum Variational Circuit）的量子机器学习模型：量子线路是在量子计算机中实现量子算法的主流技术路线之一，而量子线路由量子比特和量子门构成。受到传统神经网络的启发，人们将量子线路参数化为可调节、可优化的量子变分线路，赋予了量子线路拟合复杂函数的能力。这类量子机器学习模型通过将经典数据编码到量子态，经过量子变分线路的处理，再经过量子测量得到量子线路的输出，并以此作为量子模型的预测值来和真实标签一起计算损失函数，最后通过经典优化器优化量子变分线路中的可微参数，直到损失函数收敛。目前的量子计算机仍处于NISQ（Noisy Intermediate Scale Quantum）阶段，对量子比特数和量子门数量有着非常严苛的限制，而使用量子变分线路构建的量子算法被视为可以在NISQ阶段发挥量子计算优越性的最主要的方法。
基于量子线性代数算法（Quantum Basic Linear Algebra Subroutines）的量子机器学习模型：量子计算的基础是量子力学，而量子力学的基本假设之一就是封闭环境下量子态的演化是一种酉变换，而酉变换属于线性变换。因此，量子计算这种线性运算法则天生地适用于做线性变换的算法。同时，依赖于量子比特高维空间表征能力（ 个量子比特可以表示 维的复空间中的任意点）和量子并行计算能力，量子线性代数算法往往能获得加速效果。然而，在量子计算机上实现量子线性代数算法目前仍是一大难点。因此，基于量子线性代数算法的量子机器学习模型在近期只能在经典计算机上做模拟，尚且无法在真实量子环境下运行，但这种方法可以更好的利用量子计算的潜在优势，所以仍受到了许多学者的关注。本论文提出的方法便基于量子线性代数算法，使用量子算法减少图神经正切核方法的时间复杂度。
二、Motivation
我们的建模动机来源于两方面：
其一，已经有量子机器学习成果[3]表明，量子线性代数方法可以被用来加速无限宽多层前馈神经网络所对应的神经正切核的计算过程，同时在推理过程中也可以借助HHL算法来进行加速，并且对应的量子模型获得了指数级的加速效果；
其二，图神经正切核GNTK的提出为训练无限宽的图神经网络提供了理论支撑，其计算核矩阵包括两个子过程，即邻居节点特征聚合和中央节点特征更新，其中中央节点特征更新是一个无限宽多层前馈神经网络，该子过程可以通过量子算法进行加速，所以要想使得整个的模型仍可被量子算法加速，就需要对邻居节点特征聚合这一子过程使用量子算法进行重新设计。而邻居节点特征聚合其实也是一个线性变换，恰好满足了量子计算天生适合做线性算法的特性，我们希望依靠量子叠加原理并行计算核矩阵中的元素。同时，我们考虑了一种更为复杂的特征聚合方式，即模型每一次的特征聚合范围将被拓展为整个图。为了实现这个想法，我们引入了无限宽的注意力机制[5]。值得注意的是，我们保留了GNTK原有的邻域特征聚合过程，因为考虑到原始的图结构，邻居节点理应对中央节点传递更多的信息。最后，我们将提出一种特定的酉变换以便在量子计算环境下实现特征聚合这一子过程。
三、方法
相较于原始的图神经正切核方法，我们首先提出了一种注意力增强型的图神经正切核AttentionGNTK，然后利用量子并行计算的优势对计算过程进行加速，对应的量子模型被称为GraphQNTK。
3.1 问题定义
图数据集表示为集合 及其对应的类别标签 ，其中每个图是由节点和边构成 , 每个图附带邻接矩阵 ，以及节点特征 . 图分类任务是找到一个映射 从而预测未知图的标签。
3.2 模型设计
模型设计思路如上图所示。原始的图神经正切核GNTK仅考虑了有边相邻的节点之间的消息传递，并没考虑到节点的重要程度信息，也不能从较远的节点传播信息。训练GNTK等价于训练一个无限宽的GNN，于是我们引入了无限宽的注意力机制来适应这样的极限情况。无限宽的注意力机制指的是注意力层的输出维度是无限大的，头（head）的数量也是无限多的，在这种极限情况下，注意力机制也可以抽象为一个高斯过程，其对应的神经正切核为
其中 指的是神经网络高斯过程核（Neural Network Gaussian Process Kernel，NNGP），且 指的是注意力层的输出NNGP， 指的是注意力层的输入NNGP， 和 同理。我们将无限宽的注意力机层添加在了原始GNTK每一层的尾部，以使消息传递可以在整幅图上进行运作，可以有效缓解图结构部分缺失或图结构含噪声的问题。
这样得到的模型被我们称为注意力增强型的GNTK（AttentionGNTK），然而，和原始的GNTK一样，AttentionGNTK依然需要计算一个完整的核矩阵，其时间复杂度为 。为此，我们希望借助于量子计算来加速这一过程。
在将整个模型重新设计为量子模型之前，首先介绍一下量子并行（Uuantum Parallelism）的原理。考虑一个函数映射 ，并且有预先给定的输入集合 ，任务是将所有输入集合中的元素都作用函数 并得到所有的输出结果。
如果使用经典计算机来完成这个任务，假设只有一个寄存器可用，那么需要依次向这个寄存器中写入一个 ，作用函数 并读出结果 ，整个过程需要反复执行 次，也就是需要评估 次函数 ；而如果使用量子算法完成这个任务，量子叠加原理将使函数评估次数减少为一次，原理是首先将输入集合中的所有元素编码到一个量子叠加态中 ，假设存在一个酉变换 可以实现与函数 相同的映射，那么将 作用在该量子叠加态上，得到的量子态 将包含所有的输出结果。量子并行的简答示意图如下图所示。
通过观察(7)式可以看到，中央节点的特征更新其实就是将协方差矩阵/协方差矩阵的导数矩阵中的元素做统一的变换，参考量子并行的原理，如果可以将协方差矩阵/协方差矩阵的导数矩阵中的元素编码到一个量子叠加态中，那么就存在一个量子酉变换统一地将矩阵中所有元素的值变换到目标值。
对于图神经正切核来说，初始的图神经正切核矩阵以及协方差矩阵均被初始化为节点特征间的内积，也就是说
我们希望借助于QRAM和量子内积估计（Quantum Inner Product Estimation）算法将初始的图神经正切核矩阵以及协方差矩阵编码到量子叠加态中。
为此，我们首先假设存在QRAM可以将节点特征向量以幅度编码（Amplitude Encoding）的方式编码到量子态中，
利用量子内积估计算法，我们在量子叠加态中制备得到了初始的图神经正切核矩阵以及协方差矩阵
其中 对应于节点之间的内积。
对于邻居节点特征聚合过程来说，第 层的初始协方差矩阵/初始图神经正切核在 位置上的元素值等于第 层的协方差矩阵/图神经正切核在 位置上的元素值的累加和，这个过程在表面上不适用于量子并行的设计要求，即矩阵中某一元素从输入到输出的变换与其他元素无关。但这个过程本质上还是一种线性变换，为此我们设计了一种酉算子来以便在量子计算环境下完成这个过程。
在这里我们以模型的第1层邻居节点特征聚合过程来分析，考虑酉算子
其中 定义为完成量子内积估计算法的整个量子线性变换操作。将酉算子 作用于全 初态，我们得到另一个叠加态
于是，该酉算子实现的变换近似地将第 层的协方差矩阵/图神经正切核矩阵在 位置上的元素值的累加了起来，从而得到了下一层的协方差矩阵/图神经正切核矩阵。该方法可以推广到第 ( )层邻居节点特征聚合过程，并可以适用于在量子计算环境下将矩阵中所有元素加和并得到(8)式的图神经正切核矩阵最终表示。
对于无限宽的注意力层来说，我们对论文[5]中的无限宽注意力机制的NNGP和NTK进行了放缩，以适应量子并行的适用条件，
其中 指的是矩阵元素乘法。因此，存在一种酉变换来实现
通过上述量子线性代数算法的迭代可以实现AttentionQNTK多层模型的的量子近似核估计。最终的核矩阵中的元素将被保存在量子态中。在推理阶段，需要使用这个核矩阵来对未知图进行分类，可以考虑使用量子态层析（tomography）将量子态解析为矩阵表示，但量子态层析的所需的时间可能是指数级大的。为此，当本文所提出的量子算法运行在真实的量子计算机中时，我们建议采用HHL方法来对未知图进行分类，
其中 将以同样的方式（QRAM）编码到量子态中，而 便是调用所设计的量子算法来得到输入图和训练集中每一个图之间的近似AttentionQNTK。之后利用HHL算法和量子内积估计方法（如Swap-Test）来输出得到分类预测值。
四、实验结果
我们在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 】
Illustration by Manypixels Gallery from IconScout
-TheEnd-
多家技术企业招聘来啦！
多家技术企业招聘来啦！有求必应的小将收集到来自TechBeat技术社群内技术企业的招人需求，包含来自科技大厂微软亚研、腾讯、小红书等企业，科技明星公司始途科技、梅卡曼德等企业的算法工程师等正式及实习岗位，欢迎有需求的大家向这些公司投递简历哦！
扫描了解详情~
点击右上角，把文章分享到朋友圈
⤵一键送你进入TechBeat快乐星球
线性代数考研(线性代数考研大纲)
