摘 要：

本文聚焦于多跳图神经网络，考试测验将现有的低阶图神经网络模型扩展到高阶的多跳形式，以进行图嵌入特色表示学习。
而此方法存在低下的打算效率和有限的多跳邻域表示能力两个问题，对付低下的打算效率问题，利用迭代方法来近似繁芜邻域矩阵的幂运算，以实现近似线性打算繁芜度；对付有限的多跳邻域表示能力问题，引入正则化马尔可夫聚类方法来正则化每个迭代步中的流矩阵（毗邻矩阵）。
通过运用这两种策略构建，基于马尔可夫聚类的多跳图神经网络来完成图嵌入表示学习任务。
在图基准数据集上进行的大量验证实验，有力地证明了所提的基于马尔可夫聚类多跳图神经网络的有效性。

关键词：

深度神经网络；图神经网络；马尔可夫聚类；图表示学习

1 研究背景

作为一种通用的数据构造，图被用来建模存在内在连接关系的数据泛化表示，个中数据来源于不同的学科和运用处景，并且建模数据为节点，建模数据之间的关系为边。
为了对图数据进行剖析，现有的一种有效的方法是运用深度神经网络方法到图数据剖析中，该类方法被称为图神经网络。
作为一种主要的基于深度神经网络的图剖析方法，图神经网络在图像隐私推理、动作识别、视频择要总结、化学信息剖析和社交网络剖析等领域显示出巨大潜力。
近年来，现有的图神经网络变体模型每每遵照通报神经网络框架，个中包含通报阶段和读出阶段。
通报函数聚合每个节点的邻域节点嵌入特色表示，以天生节点嵌入特色表示；然后读出函数从节点表示空间中聚合节点嵌入特色表示，来捕获全局图信息从而天生图嵌入特色表示。
在通报框架中，由于每个节点的特色只能从间隔中央节点固定跳数的邻域中天生，因此基于迭代的通报传播方法只能将信息提取限定在局部邻域中。

为理解决上述问题，提出了多跳图神经网络聚合多跳邻域信息，以缓解该问题。
简化图卷积神经网络是一种范例的多跳图卷积神经网络，个中网络利用毗邻矩阵的 K 阶幂来得到每个节点的 K 跳邻域节点。
这种办法类似于打算机视觉中的卷积神经网络利用更大的核。
与 1 跳图卷积神经网络比较，简化图卷积神经网络通过去除图卷积神经网络中的非线性，并利用毗邻矩阵的幂得到 K 跳邻域节点嵌入特色表示来降落打算繁芜度，从而实现节点嵌入特色表示学习的优秀性能。
沿着此研究路线，提出了稠浊多跳图卷积神经网络来稠浊不同跳数的邻域节点信息，个中节点同时从 1 跳邻域到 K 跳邻域吸收潜在表示信息。
在这个模型中，每跳节点嵌入特色表示终极被拼接输入到分类器中，并且不共享待优化的参数。
当模型跳数加深时，该模型显著地增加了参数的数量和打算繁芜度。

在本文先容的研究事情中，首先考试测验将现有的多跳图神经网络扩展到更高阶形式，以得到比低阶模型更强大的表示能力。
如上所述，现有的方法直接被扩展到更高阶的模型会显著地增加参数量和打算繁芜度。
为理解决这个问题，我们利用求和聚合函数代替多跳邻域聚合时利用的拼接函数，并在多跳表示学习过程中，利用参数共享策略构建高阶多跳图神经网络。
然而，由于毗邻矩阵幂的求和形式会收敛为逆矩阵的形式且打算逆矩阵的打算效率低下，因此模型仍旧须要较高的打算繁芜度；同时，这种策略还使得稀疏的毗邻矩阵在收敛后会成为密集矩阵，而存储密集矩阵须要更大的空间繁芜度。
更严重的是，这种直接增加多跳图神经网络阶数的办法可能会导致嵌入特色学习失落败，这是由于随机游走的特性导致的；即重复运用拉普拉斯平滑会驱动毗邻关系的每个节点趋于稳态分布，此时节点的嵌入特色只与节点度干系，意味着最终生成的节点嵌入特色表示丢失了图构造信息。
为了更直不雅观地解释这些问题，我们利用一个由 7 个节点组成的示例图来展示多跳邻域的有限表示能力。
如图 1 所示，终极收敛结果表明，具有相同度节点的毗邻关系相同，显然丢失了图构造信息。
此外还不雅观察到稀疏的毗邻矩阵在收敛后，变成了须要更多内存花费的密集矩阵。
根据上述剖析，这种直接扩展的方法并不适宜图的嵌入特色表示学习。

为理解决上述两个问题，通过引入规范化马尔可夫聚类提出了一种基于马尔可夫聚类的多跳图神经网络。
首先，为办理打算效率低下的问题，基于马尔可夫聚类的多跳图神经网络采取幂迭代方法逼近逆矩阵，以实现近似线性打算繁芜度，并减轻由存储密集毗邻矩阵引起的内存花费问题；其次，对付有限的多跳邻域表示问题，基于马尔可夫聚类的多跳图神经网络依次利用规范化马尔可夫聚类中的 Regularize、Inflflation 和 Prune 算子对毗邻矩阵进行正则化，从而缓解直接扩展带来的有限表示能力的问题。
经由足够多的迭代后，簇中央节点被识别为直接连接到簇中其他节点的吸引子。
从通报的角度来看，吸引子可以用于聚合子图（簇）特色，实现高阶邻域特色的有效表示。
对付图的嵌入特色表示学习，我们利用一个大略的图嵌入求和算子，同时聚合吸引子和其他节点的嵌入特色表示信息，从而对付给定图天生高阶构造特色和局部特色。
图基准数据集上的大量实验有力地证明了基于马尔可夫聚类的多跳图神经网络的有效性和在图分类方面的卓越性能。

2 多跳图神经网络

与迭代地运用 1 跳通报函数的低阶图神经网络不同，多跳图神经网络旨在直接为每个节点天生多跳邻域连接，然后将其通报给目标节点以天生节点的低维嵌入表示向量。
多跳架构能直接增加模型的感想熏染野，有效缓解迭代通报函数带来的一系列问题，如繁芜度过大、梯度消逝等问题。
首先，我们给出一种范例的多跳图神经网络，即简化图卷积神经网络。
简化图卷积神经网络通过去除图卷积神经网络中的非线性，并利用毗邻矩阵的幂得到 K 跳邻域节点嵌入特色表示来降落打算繁芜度，从而实现节点嵌入特色表示学习的卓越性能。
SGC 的前向传播形式为

只管简化图卷积神经网络是一个线性模型，然而该模型与 K 层的图卷积神经网络有相同的吸收域，这是由于毗邻矩阵的 K 次幂表示在图中节点之间一个至多长度为 K 的路径，即 K 跳邻域。
因此，我们认为，简化图卷积神经网络是一种范例的 K 跳图神经网络。
然而，简化图卷积神经网络的架构可能会导致过平滑问题，这是由于不同的节点可能须要不同的邻域范围导致的。
一种办理上述问题的方法是稠浊不同跳的邻域节点嵌入表示。
基于此思想，提出了稠浊多跳图卷积神经网络，来稠浊聚合 1 跳邻域到 K 跳邻域范围内的节点特色信息。
从前向传播的角度来看，稠浊多跳图卷积神经网络可看作是简化图卷积神经网络的一种扩展模型，这是由于稠浊多跳图卷积神经网络拼接k跳邻域节点嵌入特色表示。

稠浊多跳图卷积神经网络的实验结果表明，参数 K常日被指定为 3 以得到更好的节点嵌入表述学习性能。
这表明，该模型实质上仍旧是低阶的形式，无法被扩展到更高阶以得到更佳的模型性能。
为得到更高阶形式的模型以得到更佳的性能，本文在简化图卷积神经网络和稠浊多跳图卷积神经网的根本上，考试测验设计更高阶的多跳图卷积神经网络。
一个自然的方法是直接增加 K，并且修正拼接算子为求和算子，即

式中，求和算子比较拼接算子须要更小的空间繁芜度，尤其是 K 更大时。
进一步地，当 K 趋于无穷时，可以得到矩阵序列收敛，这是由于毗邻矩阵为对称正则化矩阵且谱半径小于 1，则有

3 马尔可夫聚类算法

首先先容马尔可夫聚类算法。
作为一种迭代聚类算法，马尔可夫聚类算法包括 Expansion 算子和 Inflation 算子，用于识别强连接节点，并将它们分组到相同簇中。
作为一种大略直不雅观的图聚类算法，马尔可夫聚类算法缺少可扩展性，并可能使得输出结果碎片化。
为理解决上述问题，提出了正则化马尔可夫聚类算法来完成图聚类任务。
正则化马尔可夫聚类算法在保留马尔可夫聚类算法优点的同时减少了其缺陷。
详细地，在正则化马尔可夫聚类算法中， Expansion 算子被更换为如下的 Regularize 算子：

4 基于马尔可夫聚类的多跳图神经网络

在基准数据集上的 10-Fold 交叉验证均匀准确率与标准差的实验结果，如表 1 所示。
从该实验结果中可以不雅观察到，本章所提出的基于马尔可夫聚类的多跳图神经网络模型 (MCMGN) 优于基线模型。
更详细地说，与三个基于核的模型比较，所提模型在七个图基准数据集上实现了最好的图分类性能，证明了基于马尔可夫聚类的多跳图神经网络模型完成图分类任务的精良表现。
与图嵌入表示学习模型比较，所提的基于马尔可夫聚类的多跳图神经网络模型利用高阶多跳邻域节点嵌入表示来增强模型的表示能力，使模型在图分类任务上表现出精良的性能。
同时，实验结果也有力地解释了高阶多跳邻域，对图的嵌入特色表示学习的有益影响。
与带有图嵌入模块的节点嵌入表示学习方法比较，可以不雅观察到所提的基于马尔可夫聚类的多跳图神经网络模型，优于带有图嵌入模块的节点嵌入表示学习方法。
我们认为，所得结果的紧张缘故原由是，基于马尔可夫聚类的多跳图神经网络模型是为图嵌入表示学习任务设计的，而上述基线模型是为节点嵌入表示学习设计，并未有效地利用高阶多跳邻域信息。
因此，基于马尔可夫聚类的多跳图神经网络模型在所有基准数据集上，实现了分类性能的显著提升，表明了所提方法的有效性。

5 结束语

本文提出了一种基于马尔可夫聚类的多跳图神经网络模型，来办理现有模型直接扩展至高阶多跳图神经网络的打算效率低下和多跳图表示能力有限两个问题；同时详细剖析了这两个限定涌现的缘故原由，并给出了相应的办理方案，即迭代逼近方法和马尔可夫聚类正则化方法，以实现对图的低维嵌入特色表示学习并实现精良的性能。
大量实验结果有力地证明了基于马尔可夫聚类的多跳图神经网络模型，在图嵌入特色表示学习方面的优胜性。

（参考文献略）

选自《中国人工智能学会通讯》

2022年第12卷第7期

人工智能青年学者学术分享