AI研习丨基于马尔可夫聚类的多跳图神经网络

大家好，欢迎来到IT知识分享网。

文/ 范晓龙，公茂果，武越

摘 要：

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

关键词：

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

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期

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