基于图神经网络的图摘要研究综述
随着大规模图的日益普及，在提取、处理和解释大型图数据方面出现了越来越多的计算挑战。因此，寻找方法来总结这些扩展图，同时保留它们的关键特征是很自然的。在过去，大多数图形摘要技术都试图从统计上捕捉图形中最重要的部分。然而，今天，现代图数据的高维和复杂性使得深度学习技术更加流行。因此，本文对基于图神经网络(gnn)的深度学习总结技术的进展进行了全面的综述。我们的研究包括对当前最先进的方法的回顾，包括循环
目录
摘要
随着大规模图的日益普及，在提取、处理和解释大型图数据方面出现了越来越多的计算挑战。因此，寻找方法来总结这些扩展图，同时保留它们的关键特征是很自然的。在过去，大多数图形摘要技术都试图从统计上捕捉图形中最重要的部分。然而，今天，现代图数据的高维和复杂性使得深度学习技术更加流行。因此，本文对基于图神经网络(gnn)的深度学习总结技术的进展进行了全面的综述。我们的研究包括对当前最先进的方法的回顾，包括循环gnn，卷积gnn，图自编码器和图注意力网络。本文还讨论了一个新兴的研究方向，即使用图强化学习来评估和提高图摘要的质量。此外，该调查还提供了基准数据集、评估指标和实验设置中经常使用的开源工具的详细信息，以及对研究社区关注图形摘要的详细比较、讨论和总结。最后，调查总结了一些开放的研究挑战，以激励在这一领域的进一步研究。
影响报告
图摘要是管理大图的关键任务，大图在现代应用中无处不在。在本文中，我们总结了图形摘要方法的最新发展，提供了对这些方法的更深刻的理解，并列出了源代码和可用资源。该研究涵盖了广泛的技术，包括传统和基于深度学习的方法，特别强调gnn。我们的目标是帮助研究人员对基于gnn的图形摘要方法有一个基本的了解，从有用的资源中受益，并思考未来的方向
索引词
深度学习，图神经网络，图摘要
一.介绍
大图形正变得越来越普遍。随着生成的数据量的增加，大型图形在各种领域建模中变得越来越普遍，例如社交网络、蛋白质、万维网、用户操作等等。然而，随着这些图表规模的增长，理解和分析它们变得越来越具有挑战性。此外，使用大型图形执行快速计算并将其产生的知识可视化也变得越来越困难。许多人声称需要更快、更有效的算法来克服这些障碍[1]，[2]。然而，越来越多的研究人员认为总结也许能解决这个棘手的问题。摘要不仅可以帮助现有算法更快地解析数据，还可以压缩数据，减少存储需求，并有助于图形可视化和意义构建[3]
图摘要是在保留图的关键属性的同时找到图的浓缩表示的过程[2]。图1显示了一个典型的图形摘要过程的简单示例。该过程包括删除原始图的对象，并用较少的相同类型的对象替换它们，以生成原始图的浓缩表示。
图1.一个图形总结过程的例子。
从原始图中删除对象，并用较少的相同类型的对象替换，从而得到原始图的压缩表示
大多数传统的图摘要方法涉及使用传统的机器学习方法或图结构查询，例如度，邻接性或特征向量中心性，以找到图的浓缩图形表示[2]。一种流行的汇总技术是通过聚集密度最大的子图来对输入图中的结构进行分组[4]。例如，GraSS模型[5]侧重于准确的查询处理，并结合了基于随机游走模型的形式语义来回答对图结构摘要的查询，而graph Cube[6]是一个集成了网络结构摘要和属性聚合的数据仓库模型。该模型还支持大型多维网络上的OLAP查询。
值得注意的是，聚类方法遵循与摘要类似的方法，将图划分为可以进一步总结的节点组。大多数传统的图聚类方法使用传统的机器学习和统计推断来基于节点的连通性和结构相似性来度量节点的紧密度[7]。例如，Karrer等[8]使用随机块模型来检测大型稀疏图中的聚类或群落。然而，另一种图摘要方法更侧重于节点选择和识别稀疏图，这些稀疏图可用于导出更小的图[9]。例如，Doerr等人[10]引入了一种基于遍历图的采样方法，该方法从一组起点(例如节点或边)开始，然后根据图对象的最新信息向样本池中添加。然而，尽管这些方法在过去很流行，但它们的计算量非常大。它们也需要大量的内存来存储，使它们不适合当今现代、复杂和大规模的数据集。
图上的深度学习是一种强大的计算技术，适用于各种大小的图，学术界和工业界一直对它感兴趣。图神经网络(gnn)是图的深度学习技术中最成功的范例。他们的多层深度神经网络不仅能够降低任务的维数，还支持大规模图的高速计算[11]。在过去的几年里，已经提出了几种使用GNN作为摘要引擎的策略，并且这条研究路线有望在未来产生更富有成效的结果。这些基于gnn的方法在图分类、节点表示学习和链接预测等各种任务中表现出了良好的性能。此外，随着这一领域的研究不断发展，我们可以期待更多依赖gnn的创新和有效的图摘要方法。
A.关于图表摘要的现有调查
在过去的十年中，已经进行了许多审查，承认图形摘要的重要性。它们通常涵盖一系列主题，如图分区、图采样、图粗化和图嵌入，以及图摘要的特定用例，如模式发现、社区检测、欺诈检测和链接预测。此外，基于科学计算的图形摘要技术也进行了几次全面的调查：[2]，[3],[12]。然而，只有Chen等人的最新工作[12]将最新的机器学习技术与传统方法进行了比较。
在图采样[13]、[14]、图分区[15]、[16]、图聚类[17]、[18]等方面也有一些研究。其他调查关注图表示学习[19]，[20]和图嵌入[21]，[22]。由于这些研究流希望创建低维版本的图，它们与图摘要的概念密切相关。然而，尽管这些研究深入分析了图形摘要技术在重要和高需求领域的应用，但基于gnn的图形摘要方法并不是他们关注的主要领域。因此，这些调查没有对所有可用的图形总结技术提供全面和结构化的评估。
B .贡献
在这篇综述中，我们回顾了gnn在图形摘要方面的发展。总的来说，我们的目标是为研究人员和实践者提供对过去、现在和未来使用gnn进行图形摘要的方法的全面了解。我们的具体贡献包括:
1.第一个基于深度gnn的图摘要综述
据我们所知，这篇论文是第一个致力于用gnn进行图形摘要的全面调查。以前的调查主要集中在传统的图形摘要方法上，而没有考虑深度学习技术。由于目前还没有关于gnn图形摘要的专门研究，本研究旨在通过详细和结构化的调查来填补这一空白，并促进该领域的进展。
2.理解性的综述
本文对基于gnn的图摘要方法进行了全面的综述。我们还强调了与传统方法相比，不同GNN技术的好处。在每种方法中，我们都介绍了最著名的方法及其对该领域的贡献。
3.资源和复制现有的结果
我们汇集了一组支持gnn图形摘要的资源，包括尖端模型，用于比较的标准化数据集，以及再现现有的公开可用实现。我们的目标是为那些寻求理解和应用gnn进行图摘要的人提供一个资源。
4.未来的发展方向
我们确定并讨论未来的挑战和新方向。通过对现有挑战和潜在进展途径的探索，我们的目标是指导用于图形摘要的gnn的未来研究和开发。
我们审查的大多数论文发表在著名的国际会议(如SIGKDD, NeurIPS, ICLR, ICML, KDD, WWW, IJCAI和VLDB)或同行评议期刊(如ACM, IEEE, Elsevier和Springer)上，涉及人工智能，大数据，数据挖掘和web服务领域。在我们的调查中，我们发现不同的领域使用不同的术语来指代图摘要，例如“粗化”、“还原”、“简化”、“抽象”和“压缩”。虽然这些概念相对可以互换使用，但术语粗化、简化和总结通常更为常见
本综述的其余部分的结构如下:第二节介绍了图摘要的概念，主要定义和背景信息。第三节概述了图摘要的发展。第四节概述了最近开发的基于gnn的图摘要方法。第五节讨论了用于图摘要的图强化学习方法。第六节概述广泛采用的执行资源的结构。最后，第七节探讨了一些开放的研究挑战，这些挑战将在第八节得出结论之前激励进一步研究。
二.定义和背景
本节概述了图形摘要技术的关键定义和背景信息。
1.定义1（图）
图可以表示为元组
，其中
表示节点或顶点的集合
， E表示连接节点对的边或链路的集合
。图由
维邻接矩阵
表示，如果边
出现在
中，则
为1，否则为0。如果
不等于
，则图是有向的；否则，它是无向的。当边与集合
中的权重相关联时，图称为加权网络;否则，它就是一个未加权的网络。如果每条边
都有一个相关的标签，则认为
是有标签的。另外，如果每个节点
有唯一的标签，则节点也被标记；否则，
被认为未标记
2.定义2（图摘要）
给定一个图G，摘要
是
的浓缩表示，保留了它的关键属性。图摘要技术涉及对给定图的聚合、选择或转换，并产生图摘要作为输出。
正如定义2中概述的那样，图摘要方法分为三个主要类别:聚合、选择和转换。选择方法通过简单地删除对象而不替换它们来使图更稀疏，而聚合方法用相似的对象替换那些被删除的对象，但只有较少的对象。例如，一个超级节点可以替换一组节点。与选择和聚合类似，转换方法也涉及从图中删除对象，但这一次被删除的对象被转换为不同类型的对象，例如嵌入向量[23]
聚合
聚合是图形摘要中应用最广泛的技术之一。聚合方法主要分为两大类：节点分组的聚合方法和边缘分组的聚合方法。节点分组方法将节点分组为超级节点，而边分组方法通过将图中的边聚合为虚拟节点来减少图中的边数量。聚类和社区检测是基于分组的方法的示例。虽然总结图表并不是这些过程的明确主要目标，但输出可以修改为非特定于应用程序的摘要[2]。
选择
有两组主要的选择技术:抽样和简化。采样方法侧重于从输入图中选取节点和边的子集[24]，而简化或稀疏化方法则涉及去除不太重要的边或节点。这样，它们往往类似于降维问题的解决方案[9]。
转化
图投影和图嵌入是该方法的两大类。一般来说，图投影是指将具有各种层间节点和边的二分图转换为简单(单层)总结图的汇总技术。相反，图嵌入是指将一个图转换成一个保持原始图的拓扑结构的同时的降低维表示[25]。
三.图摘要:发展过程
一段时间以来，图形摘要在网络分析、数据挖掘、机器学习和可视化等领域一直发挥着重要作用。图2展示了图摘要的演变过程，显示了它是如何从传统的计算方法发展到多层gnn的。本节简要概述了该领域的三种不同的传统方法，并解释了GNN技术相对于传统方法的优势。
图2.图摘要和回顾技术的时间轴
A.基于聚类的方法
图聚类可以被认为是一种图总结技术，因为它涉及到将图中相似或相关的节点分组在一起，这样做可以减少原始图的复杂性和大小。简单来说，图聚类提供了一种将大型复杂图压缩或总结为较小簇的方法，每个簇捕获原始图的结构或功能的某些方面[1]。使用聚类的图摘要技术可以分为三大类：基于结构的、基于属性的和基于结构-属性的方法。后者结合了结构信息和属性信息，被认为是最有效的[26]。例如，Boobalan等人[27]提出了一种将图节点的结构相似度和属性相似度结合在一起的方法，称为k-NASS （k- neighbor Attribute Structural Similarity）。该方法提高了具有丰富属性的复杂图的聚类精度。然而，由于高内存和计算需求，聚类具有许多属性的大型图仍然具有挑战性。
B.统计推断
图摘要的统计推断技术简化了原始图的复杂性，同时保留了其重要特征。这些技术分为两类:模式挖掘和采样。模式挖掘识别图中的代表性模式或子图，以创建浓缩的摘要。另一方面，抽样从图中随机选择一个节点或边的子集，并基于该子集估计整个图的属性。采样技术的一个例子是Node2vec[28]，它在图中生成随机的节点序列，称为walk，以创建图摘要。各种抽样技术，如随机抽样[28]、分层抽样[29]、滚雪球抽样[30]，都可以用于图的摘要。每种技术都有其优点和缺点，选择取决于要处理的具体问题和数据。
C.目标驱动
用于图形摘要的目标驱动技术涉及构建针对特定应用程序或任务量身定制的图形摘要。它们是一种强大的捕捉与特定应用程序或任务相关的图形中特定特征或关系的工具。通过将图形摘要优化到特定目标，可以创建更有效和高效的摘要，可用于获得更好的见解并做出更好的决策[31]。用于图形摘要的重要目标驱动技术包括实用程序驱动和查询驱动技术。实用程序驱动的技术旨在总结大型图，同时保留其基本属性和结构，以最大限度地提高其对下游任务的有用性。人类审稿人根据节点分类和链接预测等特定任务评估摘要的效用[32]。查询驱动技术通过使用查询语言中的查询识别相关子图或模式来总结图。与查询匹配的结果子图成为图摘要的构建块，支持目标下游任务[33]。目标驱动总结技术的选择取决于分析的具体目标，因为一些技术可能保留全局属性，而另一些技术可能捕获局部结构。它还取决于可用的计算资源以及原始图的复杂性和大小。
D.为什么用gnn进行图摘要？
近年来，深度学习已经获得了显著的突出，由于其高准确性，现在被认为是最有效的人工智能形式之一。传统的深度学习方法已经表明，它们在欧几里得数据(例如，图像、信号和文本)上表现得非常好，现在在非欧几里得数据领域（例如，图和流形结构）上的应用越来越多。作为一种深度学习方法，gnn是一种多层神经网络，它在图结构上学习，最终执行与图相关的任务，如分类、聚类、模式挖掘和总结[34]
如前所述，传统的图摘要方法大多基于传统的机器学习或图结构查询，如度、邻接性和特征向量中心性，其目的是找到整个图的浓缩图形表示[6]。然而，这些方法中涉及的两两相似性计算需要相当高的计算能力。gnn的显式学习能力避开了这个问题。此外，甚至可以从属性图的低维表示中构建强大的模型[36]。与标准的机器学习算法不同，使用GNN，不需要遍历所有可能的节点顺序来表示一个图。相反，gnn单独考虑每个节点，而不考虑输入节点的顺序。这避免了冗余计算。
与传统方法相比，用于图摘要的GNN模型的主要优势是能够使用低维向量来表示大型图的特征[37]。此外，gnn用于将信息从一个节点传递到下一个节点的消息传递机制是学习大型图中节点和子图的模式和邻居的最成功的学习框架[11]。以半监督或无监督的方式训练GNN也很容易进行聚合、选择或将图转换为低维表示[38]。在这方面，最近用gnn进行图摘要的成功为新的研究指明了有希望的方向。例如，Brody等人[39]和Goyal等人[40]开发的GNN模型表示低维动态图，为将GNN推广到更复杂的动态图中提供了良好的基础。
四.使用GNNS进行图摘要
本节概述了最近使用gnn进行图形摘要的研究。每个小节涵盖了四种主要的方法：循环图神经网络（RecGNNs）、卷积图神经网络（ConvGNNs）、图自动编码器（GAEs）和图注意力网络（GATs）。图3显示了四种不同类型的GNN模型。在每个小节中，我们首先简要介绍了GNN模型的架构，然后回顾了最著名的方法以及每种方法对该领域的贡献。在每个小节的末尾，我们提供了代表性的基于gnn的方法的关键特征的全面总结。我们在表1、表2、表3和表4中分别对RecGNN、ConvGNN、GAE和GAT架构进行了比较分析。这些表格包括不同模型之间的评估方法、性能指标、训练数据、优势和局限性的比较。
图3.GNN 架构
A.基于recgnn的方法
recgnn是gnn的早期实现，旨在通过广义递归神经网络（RNN）架构获取节点表示。在这些框架中，信息在节点和相邻节点之间传递，以达到稳定的平衡[34]，[41]。节点的隐藏状态通过下面的式子更新
其中为节点
在时刻
的隐藏状态，表示
在动态图序列中特定时间步学习到的节点
的信息。
表示节点
在图中的相邻节点集合，提供了节点
在图结构中的上下文和连通性信息。
是邻居节点
在时间步
时候的隐藏态，这有助于更新节点
在前一个时间步长的隐藏状态，反映了相邻节点对
表示的影响。
是加权矩阵，用于聚合相邻节点的隐藏状态。
这里，通常是一个简单的元素激活，如ReLU、tanh或sigmoid。这种简单的激活通常用于在节点表示中引入非线性和捕获复杂模式。然而，这可以被循环更新函数所取代，循环更新函数使用门控机制，如LSTM（长短期记忆）[42]或GRU（门控循环单元）[43]单元。在这种情况下，将使用LSTM或GRU单元计算每个节点的隐藏状态更新，这比简单的元素激活函数更复杂和复杂。这些单元确定节点
在时刻
的隐藏状态如何基于其当前和以前的隐藏状态以及来自其相邻节点的信息进行更新，从而使模型能够捕获动态图结构数据中的时间依赖性[44]。
基于recgnn的图摘要方法主要集中于图的采样和嵌入，即从图中生成序列并将这些序列嵌入到低维的连续向量空间中。在下面，我们将首先简要介绍LSTM和GRU架构，然后深入研究基于它们各自结构的图摘要方法。
1)基于LSTM的方法
LSTM是一类RNN，它使用一系列门来并发地对序列数据中的长期和短期依赖关系建模[54]。LSTM处理大型图结构数据的改进架构被称为GraphLSTM[55]。通常，模型的输入由图节点或边的序列组成，它们使用LSTM单元按顺序处理。在每个时间步，模型根据输入节点或边和前一个状态更新其内部状态，如式2所示。
该单元由多个门组成，其操作描述如下[55]：
在给定的方程中，变量和
分别作为遗忘门、输入门和输出门。遗忘门在决定节点
在时间
时从单元状态（长期记忆）中保留或丢弃哪些信息方面起着至关重要的作用。另一方面，输入门负责决定哪些新信息应该存储在节点的单元状态中。此外，输出门调节从当前单元状态输出的信息。最后，节点
在时刻
的隐藏状态使用输出门和单元状态更新如下：
单元状态表示LSTM网络在时刻
的记忆单元。它充当长期记忆，能够在扩展序列上存储信息。为了计算
，首先计算新的候选值
，然后使用遗忘门、输入门和新的候选值更新节点
在时刻
的单元状态。这些门考虑了节点
在时间
时的先前隐藏状态
和当前输入特征向量
。此外，
和
分别是与每个门相关的权重和偏差。
通过在多个时间步骤上重复这个过程，模型捕获图中的依赖关系，并生成一个最终的隐藏状态，该状态总结了整个图中包含的所有信息。这使得保存之前的输入和图的结构的记录成为可能。在处理完所有节点和边后，使用图的最终状态LSTM作为图的汇总表示。然后，这个汇总向量可以用作下游机器学习模型的输入，或者作为其他图分析任务的特征[56]
基于LSTM的图摘要方法已被证明对一系列任务是有效的，例如图聚类、图分类和链接预测。例如，Taheri等人[45]利用各种基于图lstm的方法从图结构中生成序列，包括宽度优先搜索、随机行走和最短路径。最后，他们训练了一个图LSTM，将这些图序列嵌入到一个连续的向量空间中。编码器在时间步长t处的隐藏状态如下：
其中为时刻
的输入向量，
表示给定训练编码器LSTMenc在时刻步
的隐藏状态。同样，解码器在时间步长
处的隐藏状态定义为式10
Bojchevski等人[47]提出了NetGAN，这是一种基于递归的模型，用于捕获潜在的结构信息，从而学习有意义的网络嵌入。NetGAN利用生成模型的强大功能，通过随机游走来学习图的紧凑表示，从而在保留其基本特征的同时更有效地处理大型图。作为一种变体，Wu等[48]对NetGAN模型进行了修改，形成了一个新的具有人工边缘的适合于社区检测的社会网络。Jin等人[46]也开发了一种基于图LSTM的图表示学习方法。在这里，不同大小的图形表示被编码成低维向量。Li等[57]提出了一种使用图LSTM和ConvGNN来改进知识图问答的图摘要技术。在这种方法中，问题、实体和关系被表示为具有很少维度的向量，但关系的关键属性被很好地保留了下来。
一些研究也关注于动态图中节点模式的演化。例如，Zhang等人[56]介绍了一种基于lstm的方法，一种称为DynGNN的单阶段模型。该模型将RNN嵌入到GNN模型中以产生紧凑形式的表示。Khoshraftar等[50]提出了一种通过LSTM将大图转换为低维表示的动态图嵌入方法。该模型使用LSTM利用时间游走捕捉时间变化，然后将学习到的参数转移到node2vec[28]中，以合并每个图的局部结构。类似地，Ma等人[49]引入了一种动态RecGNN模型，该模型依赖于图LSTM对不断发展的图中的动态信息建模，同时降低图的维数并学习流形结构。节点信息通过以下方式持续更新：记录边缘之间的时间间隔；记录边的序列；并在节点间连贯地传递信息。Goyal等人[40]的另一项工作也提出了一种学习动态图中时间转移的方法。该框架基于深层架构，主要由密集层和循环层组成。在训练过程中，模型大小和待训练权重的数量可能是一个问题，但作者通过统一的节点采样克服了这个问题
2)基于GRU的方法：
GRU是图LSTM的一种变体，它包含一个门控RNN结构，并且比标准图LSTM具有更少的训练参数。GRU和LSTM之间的关键区别在于每个模型中的门的数量。GRU单元不那么复杂，只有两个门，“reset”和“update”[58]。
在这些方程中，是复位门，
是更新门。
是模型在前一个时间步长的输出。与LSTM类似，
计算新的候选值，
使用更新门和新的候选值更新节点
在时刻
的隐藏状态。
是各自门的偏置和权值。
同样，通过在几个时间步骤上重复这个过程，模型学习了图中节点之间存在的依赖关系，从而允许它构建一个最终的隐藏状态，该状态总结了图的所有信息。GRU单元用于捕获图结构数据中的时间依赖性的的适应性允许进行有效的信息聚合和上下文建模，从而使基于gru的方法成为总结复杂图结构信息的有希望的选择。例如，Taheri等[52]提出了DyGrAE模型，该模型能够在压缩动态图的维度的同时学习动态图的结构和时间动态。GRU模型捕获图的拓扑结构，而LSTM模型学习图的动态。Ge等[53]开发了一种门控递归算法，不仅解决了一些节点聚集问题，而且提取了节点之间的深度依赖特征。生成的模型称为GR-GNN，它基于执行聚合和结构的GRU。Li等人的GRU模型[51]将输入图编码为固定大小的向量表示，然后将其送入序列解码器以生成摘要作为输出。该模型有效地捕获了输入图中节点和边之间的结构信息和依赖关系，这对于生成连贯和信息丰富的图摘要至关重要。
表1 选择基于识别的图摘要方法的比较分析
|
参 考 |
模 型 名 称 |
方 法 |
评 估 |
绩 效 指 标 |
训 练 数 据 |
优势 | 局限性 |
| Taheri等[45] |
S2S- N2N- PP |
L S T M |
节 点 分 类 |
准 确 率 |
有 标 签的，无 标 签 的 |
鲁棒性能，捕获全局结构，无监督学习。 |
Weisfeiler-Lehman标签性能有限， 对噪音敏感 |
| Taheri等[45] |
Graph LSTM |
L S T M |
图 的 分 类 |
准 确 率 |
有 标 签 的 |
结合长期依赖关系，有效的节点表示。 | 依赖于预训练的嵌入，对节点排序敏感，缺乏对可扩展性的讨论。 |
| Bojchevski等[47] | NetGAN |
L S T M |
链 接 预 测 |
链 路 预 测 精 度 |
有 标 签 的 |
生成方法，可扩展性，无监督学习。 | 大量图的实际限制，由于使用gan的训练不稳定性。 |
|
Wu等[48] |
GSGAN |
L S T M |
社 区 检 测 |
A R I |
有 标 签 的 |
灵活的稀疏化，通过使用随机漫步处理大数据，准确的噪声过滤 | 分析保证有限，添加人工边缘（与图总结的目的相矛盾），缺乏与其他模型的比较。 |
| Ma等[49] | DyGNN |
L S T M |
节 点 分类，链 路 预 测 |
M R R,召回率 |
有 标 签的，无 标 签 的 |
结合时间信息，考虑各种影响 | 标签信息有限，超参数无参数分析。 |
| Khoshraftar等[50] |
LSTM Node2vec |
L S T M |
节 点 分类，链 路 预测，异 常 检 测 |
A U C, F1 分 数 |
有 标 签 的 |
结合时间信息，优于最先进的方法，保持长期依赖关系。 | 固定长度的历史，记忆密集，没有注意机制。 |
|
Li等[51] |
GGS- NNS |
G R U |
节 点 分类 |
准 确 率 |
有 标 签 的 |
捕获时间信息，合理的可伸缩性，端到端学习 | 有限的全局信息，大型图的复杂性，任务特定的架构 |
| Taheri等[52] |
Dy GGNN |
G R U |
图 分 类 |
准 确 率 |
有 标 签 的 |
捕获拓扑和时间特征，序列到序列架构，无监督 | 不能扩展到非常大的图，有限的评估，复杂性和计算成本。 |
| Ge等[53] |
GR- GNN |
G R U |
图 分类，节 点 分 类 |
准 确 率 |
有 标 签 的 |
深度特征提取，鲁棒性和通用性强，计算效率高。 | 有限的评估范围，有限的深度链相关特征提取。 |
B.基于图卷积神经网络的方法
基于图卷积神经网络的方法的总体思想是将卷积神经网络泛化到图结构数据上[34]。ConvGNN和RecGNN的主要区别在于信息传播的方式。虽然卷积神经网络在每个时间步应用不同的权重，但recgnn以迭代的方式应用相同的权重矩阵，直到达到平衡[69]。
换句话说，ConvGNN模型是一种支持图结构的神经网络架构形式，并以卷积的方式从每个节点的邻域聚集节点信息。ConvGNN模型在学习图表示方面表现出了很强的表达能力，从而在图摘要方面表现优异[69]。
基于convgnn的方法分为两类：基于频谱的方法和基于空间的方法[34]。
1)基于谱的方法：
基于谱的方法描述基于谱图理论和图信号滤波的图卷积。在谱图理论中，图与滤波器的乘法（卷积）在傅里叶域中定义[70]。
虽然计算包含定义良好的平移属性，但它相对昂贵，并且过滤器通常不本地化。由于复杂性水平随着图的规模而增长，一种解决方案是使用Chebyshev的理论[71]只检查有限数量的邻居。切比雪夫多项式递归定义为：
其中。这里，
表示切比雪夫多项式的变量。
是一个非负整数它决定了多项式的阶数也就是切比雪夫多项式的阶数。它是
次多项式函数，它的值取决于由式15递归关系定义的
和
的值
这一理论导致了几项研究，探索了将近似应用于谱图卷积的想法。例如，Defferrard等[72]通过在图上设计局部卷积滤波器，将cnn推广到图上。他们的主要思想是利用图的谱域，并使用切比雪夫多项式近似来有效地计算局部滤波器，如下所示：
式中，表示图拉普拉斯算子，
为节点特征矩阵，
为带滤波参数的图卷积算子，
为缩放拉普拉斯算子，定义为
，
为切比雪夫多项式近似的阶数。
参数是可学习的滤波器系数。他们还介绍了一个图形汇总过程，将相似的顶点分组在一起，以及一个图形池化过程，重点是产生更高的过滤器分辨率。这项工作已被用作几项研究的基础，这些研究利用切比雪夫多项式来加速卷积计算。
作为一种变体，Kipf等[59]对原始框架进行了一些简化，以提高模型的分类性能和对大型网络的可扩展性。这些简化构成了GCN(图卷积神经网络)模型的基础，这已经成为各种图形相关任务的流行选择。给定一个邻接矩阵为的无向图，他们计算归一化图的拉普拉斯函数
如下：
其中是单位矩阵，
是对角度矩阵，
表示与节点
相连的边的权值之和
在这项工作中，Kipf等人提出了使用图滤波器的简单一阶近似，而不是像Defferrard等人[72]那样直接使用高阶Chebyshev多项式计算图卷积。他们将图卷积运算定义为[59]：
其中表示第
层的隐藏节点特征。
为第
层的权值矩阵，
为添加自环的邻接矩阵。
是
的对角度矩阵。在这里，使用归一化图拉普拉斯算子
来聚合相邻节点的信息。因此，传播可以写成如下：
其中h (l) i为节点i在第1层的特征向量，Ni为图中节点i的邻居集合。W(l)是第l层的权值矩阵。σ（·）是应用于元素的激活函数
最近，已经提出了几种成功的光谱方法变体，例如S-GCN[60]和后来的SIGN[62]。S-GCN是一种简化的GCN模型，但在图形摘要方面没有任何性能妥协。S-GCN模型背后的思想是首先将大型卷积滤波器转换成较小的卷积滤波器，然后去除最终的非线性层。受之前的ConvGNN模型的启发，Rossi等人[62]随后提出了SIGN，通过组合各种可修改的图卷积滤波器将ConvGNN扩展到极大的图，以实现更快的训练和采样目的。
基于频谱的ConvGNN方法的另一个突出研究方向围绕着转换图对象，例如嵌入。例如，Jiang等人[63]引入了一种用于图嵌入的分层ConvGNN。该团队在谱卷积神经网络的基础上，为端到端图分类任务提供了一种有效的表示学习方案。更具体地说，他们提出了一个学习图特征嵌入的框架，同时也考虑了网络架构和主题之间的关系。Deng等人[61]引入了一个多层框架，以提高无监督方式嵌入的可扩展性和准确性。该模型最初生成一个新的、高效的图，其中包含有关节点属性和原始图的拓扑的信息。然后，它反复聚合具有高光谱相似性的节点，将图分解成许多较小的图。
2)基于空间的方法：
基于空间的方法处理节点的局部邻域，从邻近节点聚合节点表示以了解其属性。这种卷积神经网络通过直接在图域中定义卷积来模仿cnn的卷积操作。基于光谱的方法相对昂贵且计算时间较长，而基于空间的方法结构简单，并产生了具有图摘要挑战的前沿结果[73]。
作为与Kipf和Welling模型[59]密切相关的方法，GraphSAGE将他们的框架扩展到归纳设置[64]。GraphSAGE是第一个引入节点智能采样和使用空间卷积进行节点嵌入的小批量训练的方法。更新后的传播规则使用均值聚合器函数，公式如下[64]：
其中，平均聚合器函数结合了节点
及其采样邻居的特征。聚合函数可以是均值、最大池化或任何其他形式的聚合。例如，平均聚合可以定义为：
其中为节点
在第
层的特征向量，
为节点
的采样邻居数。
通过将一个可学习的权重矩阵应用于聚合特征表示，得到节点
的更新特征
：
其中为第
层节点
更新后的特征向量。
是第
层的权矩阵。
是应用于元素的激活函数（例如，ReLU）。结果向量的维数是输入特征向量的两倍，因为它同时包含原始节点特征和聚合的邻居特征。GraphSAGE是一个更灵活的模型，允许使用不同类型的聚合器函数。这使得它成为具有异构节点类型的图的一个很好的选择，其中不同类型的信息需要以不同的方式聚合。GraphSAGE还被证明在图分类和节点分类等任务上表现良好，这两者都与图摘要任务密切相关。
Chen等人[65]介绍了FASTGCN，这是一种节点抽样方法，利用重要性抽样获得更好的摘要。通过仅对一小部分节点进行采样并利用重要性权重，FASTGCN在保持高水平性能的同时近似于图卷积操作。这导致在训练过程中更快的收敛，使其特别适合大规模的基于图的任务。后来，Huang等人[74]和Zeng等人[66]分别提出了分层采样和图形采样方法，以进一步提高性能。Huang等人[74]专注于解决节点智能采样中的冗余问题，而Zeng等人的GraphSAINT[66]旨在纠正小批量估计器在采样子图进行训练时的偏差和方差。GraphSAINT对于基于图形的任务特别有用，因为在这些任务中，处理大规模图形在计算上具有挑战性。其基于采样的方法和小批量校正机制使其成为可扩展和精确的图形摘要的强大工具。在最近的一个变体中，Li等人[75]引入了针对包含不同节点类型和层间边的二部图量身定制的二部GraphSAINT。该框架包含一个用户-项目图，支持用户和项目嵌入，节点嵌入到两个独立的特征空间中——一个用于用户相关信息，另一个用于项目相关信息。
还引入了许多基于聚合的方法来总结图，而不会牺牲原始图中的太多信息。然后可以使用总结的图来协助进一步的网络分析和图挖掘任务。例如，Yan等[67]介绍一种名为GroupINN的新方法，它通过总结来增强ConvGNN，从而更快地训练、去噪数据并提高可解释性。他们采用了端到端神经网络模型，该模型具有专门的节点分组层，通过降维有效地总结了图。Hu等[76]考虑了结构相似性，将具有相似结构的节点聚合为超节点。然后对汇总的图进行细化，以恢复每个节点的表示。为此，采用深度分层ConvGNN （H-GCN）体系结构进行半监督节点分类，该体系结构具有几个粗化操作层和几个精化操作层。细化层的目的是恢复原始图的结构，用于图分类任务
卷积神经网络的最新发展表明，在医疗保健和人体运动分析方面，图摘要具有令人兴奋的潜力[68]，[77]。例如，Wen等人[68]提出了一种很有前途的诊断自闭症谱系障碍的方法，即通过多视图图卷积网络解析大脑结构信息。Dang等人[77]介绍了一种新型的图卷积网络，称为多尺度残差图卷积网络，与其他最先进的模型相比，它在预测人体运动方面表现出优越的性能。
表2基于卷积神经网络的图总结方法的比较分析
|
参 考 |
模 型 名 称 |
方 法 |
评 估 |
绩 效 指 标 |
训 练 数 据 |
优势 | 局限性 |
| Kipf等[59] |
GCN |
光谱 |
节 点 分 类 |
准 确 率 |
有 标 签的， |
克服了图拉普拉斯正则化的局限性，降低了复杂度，提高了可扩展性，提高了预测性能。 | 内存需求，仅限于有向边，不支持边特征，限制了假设。 |
| Wu等[60] |
SGC |
光谱 |
节 点 分 类 |
准 确 率 ， 微 F1 分数 |
有 标 签 的 |
易于实现，适用于大规模图形，内存效率高。 |
有限的表达能力，层次表示的损失，在处理复杂图的限制，由于其简化的性质。 |
| Deng等[61] |
Graph Zoom |
光谱 |
节 点 分 类 |
准 确 率 ， 微 F1 分数 |
有 标 签 的 |
适用于不同类型的图，保存局部和全局结构，可扩展到巨大的图 | 缺少节点标签保存，对大型图的支持有限。 |
| Rossi等[62] | SIGN | 光谱 |
节 点 分 类 |
准 确 率 |
有 标 签 的 |
对图形不规则性的鲁棒性，一般适用性（可应用于各种基于图形的任务），更快的训练和推理。 | 限于无向图，依赖于算子组合的选择。 |
| Jiang等[63] |
Hi-GCN |
光谱 |
图 分 类 |
准 确 率 , A U C, 敏感性和特异性 |
有 标 签 的 |
层次图卷积，对神经科学的贡献，相关性的考虑。 | 复杂的优化，有限的比较与以往的工作 |
| Hamilton等[64] |
Graph SAGE |
空间 |
节 点 分 类 |
微 F1 分 数 |
有 标 签 的 |
可扩展性，归纳学习，灵活使用聚合策略 | 同态假设，有限全局环境，过度平滑，超参数敏感性。 |
|
Chen等[65] |
Fast GCN |
空间 |
节 点 分 类 |
微 F1 分 数 |
有 标 签 的 ， 无 标 签 的 |
易于抽样实现，尽管使用重要抽样来加速训练，但仍保持模型的准确性 | 有限的比较与最先进的，机会减少抽样方差仍然存在。 |
| Zeng等[66] |
Graph SAINT |
空间 |
节 点 分 类 |
准 确 率 ， 微 F1 分 数 |
有 标 签 的 |
通过引入“邻居爆炸”对大图进行高效训练，降低训练复杂度。 | 采样开销，预处理要求，对未见图的有限泛化。 |
|
Yan等[67] |
GroupINN |
空间 |
节 点 分 类 |
准 确 率 ， 微 F1 分 数 |
有 标 签 的 |
提供可解释性，参数减少，捕获复杂关系。 | 有限的应用，依赖于数据质量，缺乏对神经科学领域范围以外的不同数据集或任务的通用性。 |
| Wen等[68] | MVS-GCN | 空间 | 图的分类 |
准 确 率 ， A U C , 敏感性和特异性 |
有 标 签 的 |
多视图脑网络嵌入，可解释性，有效的图结构学习 | 负连接词的有限贡献，超参数的影响，解释复杂大脑网络的挑战。 |
C.基于图自编码器的方法
自编码器是由一个编码器和一个解码器组成的神经网络。通常，编码器将输入数据转换为压缩表示，而解码器则根据编码器的输出重建实际输入数据[85]。图自动编码器，或GAEs，是一种可以应用于图结构的GNN，允许模型学习图的紧凑和信息表示。最近，由于具有显著的降维潜力，图自动编码器因其总结图形的能力而获得了越来越多的兴趣[36]。
GAE中编码器和解码器的结构可以根据具体实现和图数据的复杂性而变化。通常，编码器和解码器都是神经网络架构，旨在有效地处理图数据[86]。编码器的架构可能包括多层图形卷积或聚合，然后是非线性激活函数。编码器的输出是潜在空间中图形的紧凑且信息丰富的表示。另一方面，解码器利用从编码器获得的潜在表示重构原始图结构。解码器的体系结构应该反过来反映编码器的体系结构。它将潜在表征转换回图形结构[11]
GAE的目标是学习一个编码器和解码器，以减少原始图与解码图的重建误差之间的差距，同时也鼓励潜在表示捕获有关图结构的有意义的信息[87]：
其中表示重构图，重构图可以由重构特征、图结构或两者组成。
为邻接矩阵，
为输入节点特征矩阵。
作为图编码器，负责将图和节点特征转换为压缩表示。相反，
充当图形解码器，负责从潜在表示中重建原始图形或其组件。
GAE可以使用各种损失函数进行训练，例如均方误差（MSE）或二元交叉熵（BCE）。它们还可以扩展为包含额外的约束或正则化技术，以提高学习到的图表示的质量[88]。例如，对于图重构，目标是最小化原始邻接矩阵与重构邻接矩阵
之间的差。MSE损失计算公式如下[78]：
其中，为图中节点数，
和
分别为原始邻接矩阵和重构邻接矩阵的元素。
大多数基于GAE的图摘要方法使用组合架构，包括convgnn或recgnn[78]，[89],[80]。例如，Kipf等人[78]基于他们之前对谱卷积的研究[59]，提出了一种针对无向图的变分图自编码器（VGAE）。VGAE结合了[89]中基于变分自编码器的两层ConvGNN模型。VGAE的主要概念是将输入图数据表示为概率分布，而不是潜在空间中的单个点。这个分布捕获了图的潜在表示中的不确定性和可变性。VGAE不是直接从编码器获得固定的潜在表示，而是从学习分布中采样一个随机点。VGAE中的编码器通常由两个或多个图卷积层组成，这些层处理输入的图数据并产生潜在节点表示。每个图卷积层可以定义如下[78]：
其中表示编码器第
层的潜在节点表示。
是带自环的图的邻接矩阵。
是
的对角度矩阵。
是第
层的权值矩阵。
是应用于元素的激活函数（例如，ReLU）。
VGAE通过从潜在空间的高斯分布中采样潜在表示来引入GAEs的随机性。分布的均值
和对数方差
由最后一个图卷积层的输出得到
这里，表示编码器的最后一层。
和
分别是可学习的权重矩阵，用于获取均值和对数方差。
为了从高斯分布中采样，使用了重参数化技巧[90]。随机噪声向量从标准高斯分布
中采样。然后将采样后的潜在表示
计算为：
最后，解码器将采样的潜在表示映射回图空间。在VGAE中，重建通常使用潜在节点表示之间的内积来预测邻接矩阵
：
其中为sigmoid激活函数，保证预测邻接矩阵
在[0,1]范围内。
VGAE中的损失函数由两项组成：重建损失和kullback-leibler （KL）发散损失[91]。重建损失度量预测邻接矩阵与实际邻接矩阵
之间的差异。KL散度损失惩罚学习到的潜在分布与标准高斯分布的偏差。总体损失函数为这两种损失之和，如下所示：
作为VGAE的扩展，Hajiramezanali等[80]通过集成RecGNN和GAE构建了变分图RNN，以模拟节点属性和拓扑依赖关系的动态。该模型的目的是学习一种可解释的潜在图表示，并对稀疏动态图进行建模。
还有一些基于GAE的聚合方法。这些通常被设计为将图聚类任务的挑战表述为摘要问题。例如，Cai等人[82]提出了一种用于聚类属性多视图图的图循环自编码器模型。该方法背后的基本概念是考虑所有视图的共同特征和使每个图视图与众不同的特征。为此，该框架包括两个独立的模型：全局图自编码器（GGAE）和部分图自编码器（PGAE）。GGAE的目的是学习所有视图共有的特征，而PGAE则捕获不同的特征。在获得输出后，使用软k均值聚类算法将单元分组成簇。Fan等[81]引入了One2Multi Graph Autoencoder （OMGAE）用于多视图图聚类。OMGAE利用共享编码器从图的多个视图中学习公共表示，并使用多个解码器分别重构每个视图。此外，OMGAE引入了一种新的注意力机制，该机制在聚类过程中根据每个视图的重要性为其分配不同的权重。该模型被训练成最小化联合损失函数，同时考虑重构误差和聚类性能。Mrabah等[84]为属性图聚类设计了一种新的图自编码器模型GAE-KL。该模型使用目标函数的新公式，其中包括一个kl -散度项，以学习图结构和节点属性的解纠缠表示。然后，根据节点在结构和属性方面的相似性，使用解纠缠表示对节点进行聚类。作者还引入了一种新的评价指标，称为基于聚类的分类精度（CCA）来衡量聚类性能。
最近，Salha等人[83]提出了一种图自编码器架构，该架构使用一跳线性模型对图信息进行编码和解码。该方法简化了模型同时仍然在图摘要任务（如节点聚类和图分类）上实现高性能。独特的是，本文提出了一个设计图形自编码器模型的方向，以平衡性能和简单性。
表3基于图自编码器的图形摘要方法的比较分析
|
参 考 |
模 型 名 称 |
评 估 |
绩 效 指 标 |
训 练 数 据 |
优势 | 局限性 |
| Kipf et al. [78] |
VGAE |
链接 分 类 |
A P， A U C |
有 标 签的，无 标 签 的 |
生成模型，无监督学习，可扩展到大型图，变分推理。 | 有限的表达能力，依赖于训练数据的质量和数量，图结构假设。 |
| Wang et al. [79] |
MGAE |
图聚类 |
准 确 率 ， F 1 分 数 ， 精度，召 回率，A R I |
有 标 签 的 |
结构与内容信息融合，深度边缘架构，高效训练流程。 |
召回指标的性能，与其他算法相比改进有限，结构和内容的静态设置。 |
| Hajiramezanali等[80] |
VGRNN |
链接预测 |
A P ， A U C |
有 标 签的，无 标 签 的 |
建模的灵活性，可解释的潜在表征，随机潜在变量的结合。 | 具有更灵活先验的边际改进，预测非常稀疏图的挑战，直接优化的可跟踪性。 |
|
Fan等[81] |
One2Multi |
图聚类 |
准 确 率 ， A U C , N M I , A R I |
有 标 签的，无 标 签 的 |
多视图信息有效融合，嵌入与聚类联合优化。 | 耗时，引入噪音，深层关系的能力有限 |
| Cai et al. [82] |
GRAE |
图 聚 类 |
准 确 率 , A U C ， N M I ， A R I |
有 标 签的，无 标 签 的 |
多视图有效融合，自适应权值学习，自训练聚类 | 参数敏感性，数据集依赖性，齐次图假设。 |
| Salha等[83] |
Linear AE |
链接预测 ， 节点聚类 |
平 均 准 确 率 ， A U C - R O C , A M I |
有 标 签的，无 标 签 的 |
17个具有不同大小和特征的现实世界图的分析，一跳相互作用。 | 跨数据集的性能变化，基准数据集的相关性，深度模型的有限评估 |
| Mrabah等[84] |
R-GAE |
图聚类 |
准 确 率 ， N M I ， A R I |
有 标 签 的 |
提高聚类性能，控制FR和FD之间的权衡，理论和经验支持，有组织的方法，以及集成的灵活性。 |
不能合并结构和内容信息，在fr和fd之间权衡，不适合生成特定于图形的输出。 |
D.基于GAT的方法
注意机制的概念最早由Bahdanau及其同事于2014年提出[98]。目标是允许对顺序数据的长期依赖进行建模，并提高自编码器的性能。
注意机制的概念最早由Bahdanau及其同事于2014年提出[98]。目标是允许对顺序数据的长期依赖进行建模，并提高自编码器的性能。从本质上讲，注意力允许解码器将注意力集中在输入序列中最相关的部分，其中最相关的向量接收到最高的权重。图注意网络（GATs）[92]也是基于同样的思想。他们使用基于注意力的邻域聚合，为邻域中的节点分配不同的权重。这种类型的模型是用于节点聚合的最流行的GNN模型之一，主要是因为它降低了存储复杂性以及节点和边的数量。GAT的关键表述是：
式中，为节点
的隐藏特征向量，
为节点
的相邻节点集合，
为相邻节点
的隐藏状态，
为权重矩阵，
为衡量节点
对节点
重要性的关注系数。关注系数计算公式为：
式中为标量能量值，计算式为：
其中为可学习的参数向量，
表示串联。
函数将非线性引入模型，并有助于防止梯度消失。
函数对所有相邻节点的能量值进行归一化，使注意力系数之和为1
通过计算相邻节点的关注系数，GATs能够选择性地关注每个节点图中最重要的部分。这允许模型自适应地调整到不同的图结构和任务。注意机制还意味着GATs可以将节点和边缘特征合并到模型中，使其非常适合于摘要任务，例如复杂图的节点分类[99]
今天，GATs被认为是学习大规模图的最先进的模型之一。然而，最近Brody等人[39]认为GATs实际上并不计算动态注意力；相反，它们只计算一种有限形式的静态注意力。为了支持他们的说法，他们引入了GATv2，这是这种注意力网络的一个新版本，它能够表达需要计算动态注意力的问题。关注动态权重的重要性，这些作者认为，只支持静态注意力的问题可以通过改变GAT方程的内部过程的顺序来解决,如式34所示
作为GAT的另一种变体，Xie等[93]提出了一种新的多视图图注意网络MGAT，以多视图方式支持基于注意机制的低维表示学习。作者重点研究了一种基于视图的注意力方法，该方法不仅聚合了基于视图的节点表示，而且将各种类型的关系集成到多个视图中。
Tu等人[95]探索了在推荐任务中使用图摘要和精炼二部用户-项目图的好处。他们将条件注意机制应用于基于任务的子图来确定用户偏好，这强调了总结和增强知识图以支持推荐系统的潜力。Salehi等人[94]定义了一个基于自动编码器架构的模型，该模型具有图注意机制，可以学习图的低维表示。该模型将输入图中的信息压缩成一个固定大小的潜在向量，作为整个图的总结。通过使用注意力，模型能够识别图中的关键节点和边缘并确定优先级，使其更有效地捕获图的结构和语义属性。
Chen等人[96]和Li等人[97]最近对GATs进行的研究表明，图注意网络在总结和分析各个领域的复杂图数据方面具有潜力。Chen等人提出了一种用于旅游推荐的多视图图关注网络。该模型考虑了几种不同类型的用户行为，例如预订酒店、预订航班和留下餐厅评论，并在此过程中学习了一种注意力机制，以权衡不同观点对推荐的重要性。Li等人开发了一种用于知识图补全的多关系图注意网络。该模型集成了注意机制和边缘嵌入，以捕获知识图中实体之间复杂的语义关系。
表4.基于GAT的图摘要方法的比较分析
|
参 考 |
模 型 名 称 |
评 估 |
绩 效 指 标 |
训 练 数 据 |
优势 | 局限性 |
| Velivckovic等[92] |
GAT |
节点 分 类 |
准 确 率 ， 微 F 1 分 数 |
有 标 签的，无 标 签 的 |
专注于相关节点的自适应关注机制，捕获图中的远程依赖关系的能力，处理大型图结构的可扩展性 | 计算复杂的大型图，内存密集的训练，容易过度平滑。 |
| Xie等al. [93] |
MGAT |
节 点 分类，链 接 预 测 |
微 F 1 分 数 ， A U C |
有 标 签 的 |
端到端多视图图嵌入框架，基于注意力的节点信息集成，高效高效的性能，以及对复杂图网络的可泛化性。 | 缺乏对时间动态的考虑，复杂图网络的可扩展性有限，大正则化项的过拟合风险，缺乏与其他多视图嵌入方法的可比性 |
| Salehi et al [94] |
GATE |
传 导 和 感 应 节 点 分 类 |
准 确 率 |
有 标 签 的 |
归纳学习能力，灵活统一的架构，高效可扩展性，定量和定性综合评价。 | 依赖于图结构，缺乏标签信息，需要统一的架构来处理转换和归纳任务。 |
| Brody et al [39] | GATv2 |
节 点 分 类 ， 链 接 预 测 |
准 确 率 ， R O C - A U C |
有 标 签的，无 标 签 的 |
解决了GAT模型的局限性，对噪声的鲁棒性更强，可以处理更复杂的节点间交互，提高了精度。 |
问题和数据集依赖，预测最佳架构的困难，理论和实际模型之间的性能差距。 |
| Tu et al [95] |
KCAN |
推 荐 系 统 |
Hit @ k, D C G @ k, A U C |
有 标 签 的 |
有效的知识图谱蒸馏，知识图谱精化，显著改进，保留局部偏好。 | 抽样偏差，时间复杂度，可解释性，可扩展性，超参数敏感性。 |
| Chen et al [96] |
MV-GAN |
推 荐 系 统 |
Re call @k, CG @k |
有 标 签 的， 无 标 签 的 |
利用数据稀疏性，多视图图嵌入，视图级关注机制，可解释性。 | 有限的考虑因素，复杂性和可扩展性，有限的考虑多种模式。 |
| Li et al [97] |
MRGAT |
图 分 类 ， 节 点 分类， 链 接 预 测 |
MR，MRR, Hit@k |
有 标 签 的 ， 无 标 签 的 |
信息特征的选择性聚合、实体和关系特征的有效融合、可解释性和计算效率的考虑。 |
复杂性和冗余计算，采样有用的错误训练样例，利用其他背景知识，注意头的影响。 |
五.图强化学习
强化学习（RL）是一种基于顺序决策的数学模型，它允许智能体通过对其行为的反馈，在交互式设置中通过试错来学习。由于强化学习在跨学科领域的成功和快速发展，最近学者们开始研究图结构数据的强化学习模型，即图强化学习或GRL[100]。GRL在很大程度上是基于Bellman理论实现的[101]，其中环境被表示为一个图，节点表示状态，边表示状态之间可能的转换，奖励与特定的状态-动作对或节点相关联。GRL的关键组成部分如下[100]：
1.环境（图）
图表示代理运行的环境。定义为
，其中
为节点集合，表示状态，
是表示状态之间可能转换的边的集合。
2.状态（s）
在GRL中，状态s对应于图中的特定节点。每个节点可能具有提供状态信息的相关属性或特性。
3.动作（a）
动作a对应于代理在特定状态（节点）时可以做出的决定或移动。在基于图的环境中，操作可能与遍历节点之间的边或在节点上执行某些操作有关。
4.转换模型（T）
转换模型定义图的动态，指定通过采取特定动作（边）从一个状态（节点）移动到另一个状态的概率。，其中
为当前状态（节点），
为动作（边），
为下一状态（节点）。
5.奖励函数(R)：
奖励函数定义了代理在给定状态（节点）采取特定动作后获得的即时奖励在状态
下采取行动
所获得的预期即时奖励。
6.策略（π）：
与标准RL类似，图RL中的策略是代理用来决定在每个状态（节点）中采取哪个动作的策略。在状态
下采取行动
的概率。
7.价值函数(V)和Q函数(Q)：
在图RL中，价值函数和Q函数
分别表示代理从特定状态（节点）开始并遵循策略
，或在状态
中采取行动
然后遵循策略
，可以获得的期望累积奖励。Q-learning算法可表述为：
在每个时间步，状态
使用基于
值的行为策略与环境交互。它采取行动
，获得奖励
，并根据环境反馈过渡到新状态
。这个过程用于迭代地更新
表，不断地合并来自新状态
的信息，直到达到终止时间
。
GRL的主要目标是获取一个策略，该策略在一系列动作上最大化期望Q函数，目标策略定义为[102]：
其中，表示对策略
和转移
（即状态转移和奖励）分布的期望。表达式
表示从时间步
（当前时间步）开始并持续
步到未来获得的贴现奖励之和。
是在时间步长
采取行动后，在时间步长
处获得的奖励。贴现因子
是介于0和1之间的值，它决定了即时奖励相对于未来奖励的重要性。它对未来的奖励进行了折扣，使它们的重要性低于眼前的奖励。较小的
值使代理更目光短浅，而较大的
值使代理更有远见。总体目标是找到从状态
开始并采取行动
的期望奖励和（
函数）最大化的策略
。
实现这一目标需要使用各种算法，如Q-learning，或利用策略梯度方法，根据观察到的奖励和转移更新值或策略参数[86]。
GRL采用了各种各样的算法，它经常利用gnn来有效地处理和学习结构为图的数据。gnn通过考虑其相邻节点在更新节点表示方面发挥着至关重要的作用，并且它们无缝集成到RL框架中，以有效地处理特定于图的任务。它们无缝地集成到图形摘要框架中，以有效地处理涉及图摘要结构的任务。例如，Yan等人[103]引入了一种专门为图采样设计的基于congnn的神经网络，可以从基板网络的不规则图拓扑中自动提取空间特征。为了优化学习智能体，他们采用了一种流行的并行策略梯度训练方法，提高了训练的效率和鲁棒性。Wu等人[104]通过将其表述为离散动作空间中的强化学习任务来解决图信号采样问题。他们使用深度q网络（DQN）使智能体能够学习有效的采样策略。为了使训练过程更具适应性，他们修改了步骤和情节。在每一集中，智能体学习如何在每一步中选择一个节点，并在剧集结束时选择最佳节点。他们还重新定义了行动和奖励，以适应采样问题。在Wu等人[105]的另一项工作中，提出了一种用于gnn迁移学习的强化样本选择方法。该方法使用GRL来指导迁移学习，减少源域和目标域之间的分歧。
还有一系列GRL研究试图使用这种范式来评估和提高图表摘要的质量。例如，Amiri等人[106]引入了一个基于任务的GRL框架来自动学习如何生成给定网络的摘要。为了提供寻找最佳基于任务的摘要的最佳解决方案，作者将CNN层与强化学习技术相结合。为了提高摘要的质量，作者后来提出了NetReAct[107]，这是一个用于图形摘要的交互式学习框架。该模型使用人类反馈与强化学习相结合来改进摘要，同时将文档网络可视化。
在另一项研究中，Wickman等人[108]最近提出了一个图稀疏化框架SparRL，该框架由GRL授权，可用于具有特定减少目标的任何边缘稀疏化分配。该模型以边缘缩减率作为输入，学习模型决定如何最好地修剪边缘。SparRL以顺序的方式进行，从图中删除边，直到所有边被修剪。在另一项工作中，Wu等[48]引入了GSGAN，这是一种用于社区检测任务中的图稀疏化的新方法。GSGAN擅长识别在原始图中不明显的关键关系，并通过引入人工边缘提高社区检测效率。GSGAN采用生成对抗网络（GAN）模型，生成随机漫步，有效捕获网络的底层结构。这种方法的独特之处在于它利用了强化学习，这使得该方法能够通过从一个特殊设计的奖励函数中获得奖励来优化学习目标。这个强化学习组件引导生成器创建高信息量的随机漫步，最终提高社区检测任务的性能。Yan等[111]提出了一种GRL方法来总结地理知识图谱。为了更透彻地理解总结过程，该模型利用具有空间特异性的成分，在图中同时包含了外在信息和内在信息。作者还讨论了基于空间的模型的有效性，并将其模型的结果与包含非空间实体的模型的结果进行了比较。
最近，许多文章讨论了在神经科学和计算机视觉等领域使用基于gnn的grl来总结和分析复杂图形数据的潜力[109]，[110]。例如，Zhao等人[109]提出了一种由GNN引导的深度强化学习方案，作为分析大脑网络的一种方式。该模型使用强化学习框架来学习选择网络中信息量最大的节点的策略，并将其与GNN相结合来学习节点表示。此外，Goyal等人[110]提出了一种基于gnn的图像分类方法，该方法依赖于强化学习。该模型将图像表示为图形，并学习图形卷积滤波器从图形表示中提取特征。他们表明，在图像分类和强化学习任务的基准数据集上，他们的模型优于几种最先进的方法。
在表5中，我们总结了具有代表性的基于grl的图摘要方法的关键特征。对不同模型的评估方法、性能指标、训练数据、优势和局限性进行了比较
表5.基于grl的图摘要选择方法的比较分析
|
参 考 |
模 型 名 称 |
评 估 |
绩 效 指 标 |
训 练 数 据 |
优势 | 局限性 |
| Wu et al. [104] |
DQN |
图 重 构 |
准 确 率 |
有 标 签 的 ， 无 标 签 的 |
高效的图形采样，RL方法，不需要标记数据，自动化潜力，提高重建精度。 | 大图上的性能限制，采样集大小，训练图上的假设。 |
| Amiri等[106] |
NetGist |
影 响 力 最 大化 ，社区检测 |
ρnetgist |
有 标 签 的 ， 无 标 签 的 |
自动灵活地为给定任务集生成有意义的图形摘要，泛化到看不见的实例 |
计算复杂性，任务依赖性，图优化问题的范围有限，缺乏与现有方法的比较。 |
| Amiri等[107] |
NetReAct |
图聚类 |
ρnetreact |
有 标 签 的 ， 无 标 签 的 |
结合人的反馈，群体之间有意义的关系，多尺度可视化 | 非专家反馈的简单性，人类反馈的稀疏性和不一致性，更大文档数据集的可扩展性，需要进一步的探索和发展。 |
| Wickman et al. [108] |
SparRL |
网 页 排名 ，社区结构 |
斯皮尔曼ρ指数，ARI |
有 标 签的，无 标 签 的 |
任务适应性、学习效率和收敛性、灵活性、效率和易用性。 |
涉及矩阵运算，对于大型图形可能需要大量计算，基于采样的技术，仅限于静态图形设置。 |
| Wu et al. [105] |
RSS-GNN |
迁移学习 |
A U C - R O C |
有 标 签 的 , 无 标 签 的 |
高效有效的样本选择，缓解源域图和目标域图之间的分歧。 | 不可微的样本选择，计算复杂性，推广到新的下游任务。 |
| Zhao et al. [109] |
BNN- GNN |
图分类 |
平均 准确率 ，AUC |
有 标 签 的 , 无 标 签 的 |
改进的分类性能、自定义聚合、有效的脑网络分析、元策略应用的灵活性、对不同输入类型的鲁棒性。 | 性能随输入类型的变化，概括性，超参数敏感性，可解释性。 |
| Zhao et al. [109] | GNRL | 图分类 |
Topk 准确性 |
有 标 签 的 , 无 标 签 的 |
改进的图像表示、可解释性、有效的训练和可伸缩性 | 缺乏粗糙图表示的鲁棒性，训练时间和gpu利用率，对无模型技术的改进有限，缺乏对其他环境的通用性 |
六.已发表的算法和数据集
在下一节中，我们将提供基准测试数据集、评估指标和开源实现的全面概述。这些关键组成部分在文献调查的第四和第五节中进行了广泛的检查和阐述。通过深入研究这些方面，我们的目标是提供对上述部分所涵盖的景观的全面理解。
A:数据集
在该领域的开发中使用了合成数据集和真实数据集。合成数据集是由基于人工设计规则的模型创建的，而真实世界的数据集是从实际应用中收集的，用于评估实际使用中提出的方法的性能。流行的现实世界数据集分为五类：引文网络、社交网络、用户生成网络、生物信息学网络和图像/神经图像，以及知识图谱。表六概述了上述类别中最常用的数据集。此外，图4提供了每种工具每年的开发趋势，提供了关于它们随时间演变和可用性的有价值的见解。
表6.公开的数据集
| 类别 | 数据集 | URL | |
| 引用网络 | Cora | Projekt Relational - FIT ČVUT https://relational.fit.cvut.cz/dataset/CORA |
|
| Citeseer | Projekt Relational - FIT ČVUThttps://relational.fit.cvut.cz/dataset/CiteSeer |
||
| PubMed |
https://relational.fit.cvut.cz/dataset/PubMed Diabetes |
||
| DBLP | Index of /xmlhttps://dblp.uni-trier.de/xml/ |
||
| ACM | 404 - Page not foundAMiner利用数据挖掘和社会网络分析与挖掘技术，提供研究者语义信息抽取、面向话题的专家搜索、权威机构搜索、话题发现和趋势分析、基于话题的社会影响力分析、研究者社会网络关系识别等众多功能。http://www.arnetminer.org/openacademicgraph |
||
| 社交网络 | |||
| IMDB | |||
| Karate | |||
| DNC | |||
| UCI | |||
| 用户网络 | Amazon | ||
| Yelp | |||
| Epinions | |||
| Taobao | |||
| MovieLens | |||
| Last-FM | |||
| Eumail | |||
| Enron | |||
| POL.BLOGS | |||
|
生物信息 网络 ，图像/神经图像 |
PPI | ||
| MUTAG | |||
| PTC | |||
| ENZymes | |||
| NCI | |||
| Flickr | |||
| fMRI | |||
| ADNI | |||
| ABIDE | |||
| 知识图 | |||
| 合成网络 |
图4.被评审论文中数据集的逐年发展。
B.评估指标
gnn通常通过节点分类、图分类、图聚类、推荐和链接预测等任务进行评估。为了提供每个研究中使用的评估标准的概述，我们根据他们用于评估其方法的指标对我们所审查的每一篇文章进行了分类。这些指标主要包括准确率、精密度、召回率、f1得分和AUC-ROC。表7列出了最常用的评价指标及其计算公式或描述:
表7评价指标
| 评价指标 | 公式/描述 |
| 准确率 | |
| 精度 | |
| 平均精度 | |
| F1-分数 | |
| 特异性 | |
| AUC-ROC | ROC曲线下的面积。 |
| ARI | 调整后的兰德指数，衡量两个数据聚类之间的相似性。 |
| NMI | 归一化互信息度量两个聚类之间的相似性。 |
| Hit@k | 排名前k的相关项数/k |
| NDCG@k | k处的归一化贴现累积增益。 |
| 斯皮尔曼 |
度量两个变量之间单调关系的强度和方向。 |
| 预期的比率。 | |
| 量化识别相关文件的难易程度。 | |
| 平均排名 | |
| 平均倒数秩 |
C.开源实现
表八和表九提供了所选方法的详细比较，展示了通过两种领先的基于gnn的图汇总评估技术（节点分类和链接预测）复制已建立的可比模型的结果。评估在静态数据集（如Cora和Citeseer）以及动态数据集（如Enron和Facebook）上进行，以评估模型在不断发展的图结构中的性能。这种比较包括模型名称、平台、数据集、指标、超参数和实现源，所有实现都是使用Python 3开发的。x和流行的框架，如PyTorch， PyTorch几何，或TensorFlow。
表8.使用节点分类进行评估的已发表文献中的可比模型。
S/D：静态/动态，NL：层数，AF：激活函数，DR: dropout率，LR：学习率，WD：权值衰减。
表9.使用链接预测进行评价的已发表文献的可比模型。
S/D：静态/动态，NL：层数，AF：激活函数，DR: dropout率，LR：学习率，WD：权值衰减。
七.讨论及未来方向
本综述在图形摘要的背景下对gnn进行了全面的研究，重点关注了关键方法，如RecGNN、ConvGNN、GAE、GAT和新兴的GRL领域。每种方法都为捕获图数据中固有的复杂关系提供了独特的视角和方法
基于recgnn
的方法可以通过使用递归单元来识别跨层的长期依赖关系，从而在递归邻域扩展期间捕获大量信息。此外，这个过程是相当的高效。值得注意的是，如果加入卷积滤波器，RecGNN模型还可以提高训练期间的数值稳定性。然而，由于梯度消失问题（循环架构中的一个常见问题），它们可能在远程依赖建模中面临挑战。
基于卷积神经网络
的方法利用了更多的空间方法，有效地聚合了局部邻域信息。这种方法在局部结构信息丰富的任务中特别有效。尽管如此，卷积方法可能无法完全捕获全局上下文，这在某些摘要任务中可能是至关重要的。此外，大多数用于图摘要的现有ConvGNN模型都简单地假设输入图是静态的。然而，在现实世界中，动态发展的图/网络更为常见。例如，在社交网络中，用户的数量、他们连接的朋友以及他们的活动都在不断变化。为此，在静态图上学习convgnn可能不会产生最好的结果。因此，需要对动态ConvGNN模型进行更多的研究，以提高大规模动态图摘要的质量。
基于图自编码器
的方法为图上的无监督学习提供了一个强大的框架。通过学习编码和解码图数据，GAEs可以生成保存基本拓扑信息的紧凑表示。然而，摘要的质量很大程度上取决于编码器和解码器的选择，这可能是一个重要的设计选择。此外，大多数基于图自编码器的方法通常是非正则化的，主要关注于最小化重建误差，而忽略了潜在空间的数据分布。然而，这可能会导致在处理稀疏和嘈杂的现实世界图形数据时，图形总结效果不佳。虽然关于GAE正则化的研究很少[112]，但这方面还需要更多的研究。
基于图注意力机制
的方法引入了一种关注机制，允许对节点对表示的贡献进行加权。这种方法可以自适应地突出图中的重要特征和关系。虽然GATs提供了一种灵活的机制，可以潜在地优于其他方法，但它们也可能需要更多的计算资源，并且容易在较小的数据集上过度拟合。鉴于该领域的最新进展，我们期望在未来看到更多关于使用GATs创建静态和动态图的压缩表示的研究。
基于图强化学习
的方法将强化学习与图模型结合在一起通过从奖励反馈中学习来选择性地总结图。这种方法很有希望用于以决策为中心的摘要任务，如图压缩或关键子结构识别。设计定制的深度GRL架构，以实现图形摘要，是未来一个很有前途的方向。然而，相对较新的GRL在定义奖励和有效探索图空间方面面临挑战。
在所有方法中，我们观察到捕获图结构不同方面的能力和计算效率之间的权衡。此外，每种方法的性能可能会根据所使用的数据集的特征和所处理的特定摘要任务而有很大差异。我们的分析揭示了这种图数据的复杂性和深度学习的早期阶段对图挖掘技术提出了重大挑战。为了解决这些障碍并推动未来的进展，我们确定了使用gnn进行图形摘要的四个潜在方向。
A.动态图
在现实世界中，图所表示的数据可以随着时间的推移而变化，从而在图的拓扑结构中产生变化，例如出现新的边、消失的节点或随时间变化的属性。这些动态会导致整个图表发生根本性的变化。总结动态图通常需要将图分解为以不同时间增量拍摄的一系列快照。然后在这些快照上训练模型，但是可能会出现许多挑战。迄今为止，为解决这些问题而开发的方法主要集中在捕获时间模式和图拓扑中的变化。然而，这些方法往往难以有效地处理大规模动态图并准确地捕捉图关系的演变本质。该领域的未来工作将集中在开发更具可扩展性的算法上，这些算法可以在不影响处理速度或准确性的情况下处理更大的动态图形。
B.基于任务的总结
随着图形大小的增长，图形摘要是至关重要的，它有助于理解、语义构建和分析。不同的任务，如发现社区或确定有影响力的节点，需要量身定制的总结策略。这就需要为每个独特的任务开发特定的方法，以有效地识别相关的模式。此外，尽管基于任务的总结是至关重要的，但这一研究领域的成功案例很少[106]，[107]，仍然是一个未被充分探索的领域。开放的研究问题包括如何在流和异构图上执行基于任务的摘要，以及如何在学习过程中利用人类反馈。
C.评估基准
图摘要过程的最优结果是原始图的“良好”摘要。然而，评估摘要的“好坏”是一项特定于应用程序的任务，它取决于手头的任务。例如，基于抽样的方法是根据抽样的质量来评估的，而基于聚合的方法是根据分类的质量来评估的，等等。目前的研究通常将其方法与一种或多种既定方法进行比较，以衡量其结果的质量。例如，文献中使用的指标包括信息丢失、可视化的易用性和稀疏性[2]。然而，在验证过程变得复杂并且涉及更多元素的情况下，例如可视化和多分辨率摘要，需要更多不同的评估度量
D.生成模型
在生成模型的上下文中，图形摘要可以用于生成与原始图形具有相似属性的新图形。生成模型，比如VAEs，图变换、图对抗网络（GANs）和图自回归模型为图摘要提供了有效的方法。这些模型可以学习图数据中的模式，并通过从学习到的分布中采样或顺序生成节点和边来生成新的图摘要。研究人员不断探索新技术来突破模型架构、可扩展性、可控性和可解释性的界限[47]、[108]、[48]。该领域提供了令人兴奋的创新机会，并有潜力通过更有效和准确的图形摘要技术来改变各个领域。
八.总结
多层深度神经网络在深度学习方面的新进展使得快速有效地生成大型复杂图的浓缩表示成为可能。本文综述了gnn图摘要的技术发展趋势和最新研究进展。我们概述了不同的图形摘要技术，并对当前基于gnn的图形摘要方法进行了分类和描述。我们还讨论了一个新的研究方向，重点是强化学习方法来评估和提高图摘要的质量。
为了推进这一领域的研究，我们还概述了几种常用的基准测试工具，包括数据集、开源代码和生成汇总图的技术。此外，根据调查结果，我们确定了未来研究的四个有希望的方向。我们坚信，使用gnn进行图形摘要不仅仅是一个过去的趋势。相反，它在不同领域的广泛应用中有着光明的前景
作为我们未来工作的潜在重点领域，我们努力深入研究基于gnn的生成模型的能力，包括VGAEs[78]和GANs[47]，[48]，以突破图摘要和生成的界限。此外，我们将探索GRL[108]的潜力，基于它们的总结表示来创建新的图。通过解决挑战和扩展图合成的前沿，我们设想为数据分析师和研究人员提供强大的工具，以有效和深刻地分析复杂的图结构数据。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
24
0- 0
已为社区贡献1条内容
所有评论(0)