基于连续时间量子行走的图神经网络

# 基于连续时间量子行走的图神经网络

来源: https://arxiv.org/html/2608.20738

## 基于连续时间量子行走的图神经网络

DOI:XXXXXXX.XXXXXXX (https://doi.org/XXXXXXX.XXXXXXX)
会议: 请从您的权利确认邮件中输入正确的会议名称；2018年6月3日至5日；纽约州伍德斯托克
ISBN: 978-1-4503-XXXX-X/2018/06
CCS: 计算方法学，机器学习

高泽锋 邮箱: [[email protected]](mailto:[email protected])
单位: 中国人民大学，北京，中国

李健 邮箱: [[email protected]](mailto:[email protected])
备注: 通讯作者。
单位: 中国人民大学，北京，中国

刘洋 邮箱: [[email protected]](mailto:[email protected])
单位: 中国人民大学，北京，中国

孙浩 邮箱: [[email protected]](mailto:[email protected])
单位: 中国人民大学，北京，中国

2018© , 2018; 

###### 摘要

图神经网络（GNNs）已广泛应用于图结构数据。然而，大多数GNN存在两个关键弱点。首先，消息传递基于同配性假设，充当低通滤波器，因此在连接节点差异较大的异配图上表现不佳。其次，堆叠层会使节点特征指数级收敛到常数，这一问题被称为过平滑。现有工作通常分别解决这两个弱点。少数同时针对两者的方法依赖经验启发式，且许多过平滑解决方案进一步牺牲了模型的表达能力。为了从理论上同时解决这两个弱点，我们提出了CTQW-GNN，一种基于连续时间量子行走（CTQW）构建的GNN。其设计动机源于CTQW传播子$e^{-\mathrm{i}Ht}$的两个特性：(i) 它是酉的，其特征值位于单位圆上，因此没有频率分量被衰减。这直接抵消了低通偏差。(ii) 酉性保持特征范数不变，因此狄利克雷能量不会随深度指数衰减。这直接抵消了过平滑。在这些特性的指导下，CTQW-GNN结合了三个聚合模块，每个模块都源于先前工作的特定缺陷。基于CTQW的聚合通过酉传播子演化节点特征。它捕获了异配图所需的中频和高频信号，并可证明地保持狄利克雷能量不会崩溃，从而在一个分支中解决了两个弱点。CTQW-注意力聚合基于CTQW振幅构建多跳邻居图，并应用注意力机制，因此单跳聚合遗漏的远距离同配节点仍然可以被访问。低频聚合是一个标准的低通分支（GAT），用于保持在强同配图上的准确性，而在这些图中，纯CTQW分支是次优的。我们进一步提供了谱间隙分析来解释能量保持，并给出了一个类似Lieb-Robinson类型的界，为选择行走时间$t$提供了原则性规则。在14个基准测试（9个异配，5个同配）上的实验表明，CTQW-GNN在每个数据集上都达到了最先进的精度。在陈述的稀疏化规则下，Krylov传播和基于切比雪夫的稀疏化使CTQW相关计算在边数上保持线性复杂度。

###### 关键词: 深度图神经网络，过平滑，异配图，连续时间量子行走

## 1. 引言

图神经网络（GNN）已在量子物理、交通网络和推荐系统等许多重要领域得到广泛应用。这主要归因于GNN捕获节点特征和图拓扑信息的能力。尽管取得了这些显著进展，但大多数现有GNN模型仍然存在两个固有弱点（即同配性假设和过平滑），这会削弱其性能。

GNN的第一个弱点是同配性假设，因为它们通过聚合邻居信息来更新节点或边特征。这种聚合作为低通滤波器工作，保留连接节点之间的相似性并过滤差异，从而促进特征均匀性。然而，最近的研究表明，虽然这种滤波机制在连接节点相似的同配图上表现出色，但在连接节点差异较大的异配图上，它降低了GNN学习节点表示的性能（异配问题）。为了提高GNN在异配图上的性能，许多研究人员正尝试构建高通滤波器来捕获高频信息。这种方法的动机在于高频信息对异配图学习有用的发现。另一种常见的方法是聚合多跳邻居节点，以捕获远距离的同配依赖关系。

GNN的第二个弱点是过平滑问题，即增加GNN的层数会导致所有节点的特征指数级收敛到常数值。这导致大多数应用的GNN是浅层的，限制了它们的能力。最近，研究人员主要通过实施丢弃操作、归一化和修改GNN的动态系统来缓解过平滑。然而，先前的研究指出，虽然一些方法可以缓解过平滑，但代价是牺牲了GNN的表达性能。

异配性和过平滑通常被视为独立的问题进行研究，但最近的证据表明它们密切相关。最近的工作发现，解决异配性的方法也能缓解过平滑，反之亦然。然而，这些方法依赖于经验观察而非理论保证。一个可靠的解决方案需要一种聚合方法，它能够捕获多样化的频率并扩展节点邻域，同时*可证明地*防止节点特征在许多层之后收敛到常数。

在本文中，我们提出了基于连续时间量子行走的图神经网络，即CTQW-GNN，以从理论上同时解决这两个弱点。我们首先通过CTQW推导多跳节点连接和边权重。然后，我们利用单跳连接来聚合低频信息，利用多跳连接来捕获来自远距离节点的信息。这使得CTQW-GNN能够在同配图和异配图上都有效地学习。

具体来说，我们采用Graph Transformer的注意力机制，通过CTQW诱导的多跳连接来聚合远距离节点，从而捕获长程同配关系。请注意，先前的研究指出，大多数图并非纯粹的同配或异配，而是介于两者之间。此外，中频信息已被证明可以增强GNN在此类混合模式图上的性能。CTQW导出的边权重天然支持中频和高频信息的聚合，因此我们可以利用CTQW有效地捕获图中的中程频谱分量。最后，我们将从单跳和多跳连接聚合的信息与通过CTQW导出的边权重聚合的信息相结合。这个组合特征作为CTQW-GNN下一层的输入。由于CTQW的范数保持特性，图的狄利克雷能量不会指数级收敛到零，从而防止了CTQW-GNN模型中的过平滑。

本文的贡献有三点：
∙ 灵感源自CTQW的聚合方式。我们设计了基于CTQW和CTQW-注意力的聚合，它们保持量子叠加和相位驱动的干涉。
∙ 具有可证明保证的CTQW-GNN。该模型结合三种聚合方式来捕获低频、中/高频和长程信息。我们提供了谱间隙分析和一个Lieb-Robinson类型的界 $r_{\mathrm{eff}}(t)=2\lambda_{\max}t/\pi$，它们共同解释了CTQW为何能避免指数能量衰减以及如何选择$t$。
∙ 广泛的实验。CTQW-GNN在所有14个基准测试上都达到了最先进的精度，在每个数据集上都优于强基线（平均提升+1.07%；在达到饱和的同配数据集上提升+1.06%至+3.31%）。

## 2. 相关工作

**异配GNN。** 为了解决异配性问题，许多工作专注于设计不依赖同配性假设的异配GNN。这些工作主要分为两类：第一类方法结合高通和低通滤波器从邻居节点捕获信息，因为高频信息有助于解决异配性问题。第二类方法扩展节点的邻域，以聚合远距离的同配信息。我们的模型与现有方法的区别在于提供了一种混合集成方法。它巧妙地利用经典的聚合方法，如图卷积网络（GCN），来聚合低频信息。同时，对于中频和高频信息的聚合，它采用了先进的CTQW策略，从而结合了两者的优点以提高性能和效率。此外，我们的模型利用CTQW导出的连接性来巧妙地捕获长程同配依赖关系。CTQW的这种创新应用显著增强了GNN的表达能力，使得对复杂图结构的表示更加细致和全面。

**过平滑。** 过平滑是GNN中一个众所周知的问题，其特点是随着层数的增加，节点特征指数级收敛到一个相同的常数值。已经提出了许多方法来缓解它，主要从丢弃操作、归一化以及修改GNN的动态系统入手。尽管取得了显著进展，但现有方法存在一个权衡，可能会限制GNN的表达能力。我们引入了基于CTQW的聚合来抵消过平滑。与大多数将过平滑和异配性分开研究的研究不同，我们的模型同时处理这两个问题，提高了GNN在复杂图任务上的性能。此外，我们从理论上证实了这种方法的可靠性。

## 3. 预备知识

#### 符号说明
我们定义一个无向图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$，其中 $\mathcal{V}$ 是大小为 $N$ 的节点集，$\mathcal{E}$ 是边集。邻接矩阵为 $A\in\mathbb{R}^{N\times N}$。度矩阵 $D$ 是对角矩阵，其中 $D_{ii}=\sum_{j}A_{ij}$。归一化的图拉普拉斯矩阵 $L=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$（其中 $I$ 是单位矩阵）是对称的，并可表示为 $U\Lambda U^{T}$。这里，$\Lambda=diag([\lambda_{1},\lambda_{2},...,\lambda_{N}])$ 表示图信号频率，$U=\{\{u_{i}\}\}_{i=1}^{N}$ 表示频率分量。

#### 图傅里叶变换
我们将 $U$ 视为图傅里叶变换的基。图 $\mathcal{G}$ 上图信号 $x\in\mathbb{R}^{n}$ 的变换为 $\hat{x}=U^{T}x$，逆变换为 $x=U\hat{x}$。图信号 $x$ 与核 $f$ 的卷积为：
(1) $(f*x)_{\mathcal{G}}=U((U^{T}f)\odot(U^{T}x))=Ug_{\theta}U^{T}x$。
其中 $\odot$ 表示哈达玛积（逐元素乘积），$g_{\theta}$ 是一个可学习的滤波器，可以调整图信号的频率响应。例如，GCN定义卷积核 $g_{\theta}=I-\Lambda$，其中 $\lambda_{g_{\theta},i}=1-\lambda_{i}$。这表明GCN的卷积核是低通滤波器。

#### 过平滑与狄利克雷能量
近期文献主要采用图狄利克雷能量（DE）来衡量节点间特征的相似性，从而定义过平滑。定义在具有节点特征 $X$ 的无向图 $\mathcal{G}$ 上的狄利克雷能量 $E$ 为：
(2) $E(X)=\frac{1}{N}\sum_{i\in\mathcal{V}}\sum_{j\in\mathcal{N}_{i}}\left\|X_{i}-X_{j}\right\|^{2}_{2}$

根据狄利克雷能量，我们可以如下定义过平滑：
###### 定义 0。令 $X^{n}$ 表示GNN第 $n$ 层的节点特征。过平滑定义为逐层狄利克雷能量随 $n$ 指数级收敛到零：
(3) $E(X^{n})\leq ae^{-bn}$，
其中 $a$ 和 $b$ 是常数，且 $a,b>0$。换句话说，随着层数的增加，节点特征将指数级收敛到一个常数值。

#### 量子行走：入门
图上的*经典随机行（CRW）*通过扩散方程 $\dot{p}=-Lp$ 传播概率向量 $p(t)\in\mathbb{R}^{N}_{\geq 0}$，其解为 $p(t)=e^{-Lt}p(0)$。*量子行走（QW）*由1引入，并由22综述，它将实数概率替换为复数振幅 $\psi(t)\in\mathbb{C}^{N}$，将耗散生成元 $-L$ 替换为厄米哈密顿量 $H$。行走的演化遵循薛定谔方程 $\mathrm{i}\dot{\psi}=H\psi$，其解为 $\psi(t)=e^{-\mathrm{i}Ht}\psi(0)$。