【图神经网络】图分类学习研究综述[1]：图分类问题定义与基于图相似度的图分类

以GNN为基础的图分类学习综述[1]：阐述了图分类问题的基本概念和意义，并探讨了基于图相似度的图分类方法

论文阅读：围绕GNN展开的图分类学习研究综述

• 2. 基于图相似度计算的方法用于对图进行分类

  • • 2.1 基于核概念的技术用于提取和比较复杂网络的特征

    • • 2.1.1 通过路径分析构建网络拓扑特征的技术
      • 2.1.2 通过子图分析提取网络局部特征的技术
      • 2.1.3 通过子树分析提取网络层次化特征的技术

    • 2.2 基于图匹配的图分类

论文阅读：基于GNN的图分类学习研究综述

摘要

关键词 ：图分类、图核、图卷积；图池化；图神经网络

---

图数据 (graph data) 普遍应用于各个领域用来表征复合对象元素间的相互关联。如社交网络中的人际互动引文网络中的文献引用关系生物化学网络中的分子间作用连接以及交通网络中地点间的交通联系。在这些图结构中研究者通常关注的焦点包含节点分类图分类以及链路预测等问题。

本文重点研究的是图分类问题。对于任意一组输入图，在进行分类时的任务是建立与预设类别标签之间的关联，并识别这些未知图像所属的类别。

• 在化学信息学领域中，在分析分子图的基础上系统性地推断化合物分子的诱变性能力及其毒性特征等关键性质；
  • 在生物信息学领域中，在构建蛋白质网络模型的基础上确定特定蛋白是否为酶，并进一步评估其在疾病治疗中的潜在作用。

图分类的研究方法主要包括：

1. 基于图核的方法
2. 基于图匹配的方法
3. 基于图深度学习的方法

本文将现有图分类方法总结为两大类：
第1类：基于相似度计算的图分类方法：通过计算成对图的相似度对图进行分类，包括图核方法和图匹配方法。其中:

• 基于对节点邻域关系的分析构建节点特征向量的方法通常被用作衡量网络结构相似性的标准，在传统的网络分析中具有重要的地位。
• 通常将复杂网络分解为特定模式或模板进行识别和比较。通过对不同网络中这些特定模式或模板的对比, 可以衡量网络间的差异性, 并从而实现对网络结构的理解和分类任务。

在早期阶段, 图分类问题主要集中于图核技术的研究. 然而这种方案在灵活性上存在不足, 并且计算开销较大. 此外, 图的特征提取过程与图的分类过程相互独立, 从而难以根据特定任务进行针对性优化.

第二类是基于图神经网络的图像分类任务。在处理图像分类问题时，该技术主要包含卷积操作和池化操作等关键环节。

卷积算子通过某种机制提取图中节点及其连接关系所蕴含的关键信息作为特征表示；池化操作则通过对局部区域特征的学习生成全局图谱的高层次抽象信息作为分类依据

本文第一节阐述了图分类问题的定义，并对该领域中的问题及挑战进行了深入探讨。第2节对基于相似度计算的图分类方法进行了综述。其中包含了基于图核方法的图分类以及基于图匹配技术的应用。第3节详细介绍了基于图神经网络框架下的图分类方法，并对其相关工作展开了分析。第4节着重探讨了评估机制的设计与实现过程，并重点分析了当前主流方法在性能指标上的优劣对比情况。第5节系统梳理了不同应用领域的典型案例，并归纳总结了当前研究的主要方向和发展趋势。最后一个小结部分对全文进行了总结。

---

1. 图分类问题定义及挑战

1.1 图分类问题与符号定义

在图数据挖掘领域，图分类问题被视为一个关键研究方向。具体而言，在这一研究框架下，
我们关注的是建立各子类别的明确关联关系。对于包含N个子类别的节点集合V以及其对应的属性
向量集合X={x_v | v∈V}来说，在这种情况下，
我们假设每个节点v对应于一个特定类别c∈C，
其中C={c_1,c_2,…,c_K}表示所有可能的类群。
基于此假设，在这种情况下，
我们所关心的就是从属性空间X到类别空间C的映射函数f(x)。
这种映射函数f(x)能够有效地将属性空间中的各个点映射到相应的类别空间中。
基于此模型框架，
我们可以将这一过程视为一种典型的监督学习过程：
即通过训练样本对模型参数进行优化，
最终使得模型能够对未知的新样本做出合理的预测结果。
在这种情况下，
我们的目标就是通过分析节点属性与子类别的关联关系，
来实现对未知节点所属类别的准确预测。

对于一个图G=(V,E,X)，其标签y进行标注。其中：

• V代表节点集，
• E⊆V×V代表边集，
• X∈ℝ^{n×D}为各节点对应的特征矩阵，
  其中X_i代表第i号节点对应的特征向量。
• A∈ℝ^{n×n}则用于描述各节点间的邻接关系。
  如表1所示，则总结了全文中常见符号及其对应含义

1.2 图分类中的问题与挑战

图分类任务存在的问题和难点主要包括以下几个方面：
（1）图数据的复杂多样性
例如社交网络、化学分子结构、生物蛋白质结构等，每种类型的图中都包含不同的特征信息和结构信息。这种多样的信息提高了图数据的分类难度。此外，图数据是非欧氏空间数据，一般来说，每个图的节点数不同，图中节点连接方式不同，每个节点的邻居个数也不同。卷积、池化等在欧式数据中比较容易定义的操作，难以直接迁移到图数据上。
（2）图结构信息的有效建模
图数据的结构信息是指图上节点之间的连接关系，包括节点的一阶连接信息，二阶信息以及高阶信息等。图上机器学习的最基础挑战之一就是找到一种可以表示、编码图结构的方法，从而使得图结构信息可以被机器学习方法有效利用。
图的结构信息对于图分类任务也至关重要。例如，在生物信息学等领域中的数据集中，图的属性标签与图上的某些结构有着必然的联系。然而Errica等人在实验中发现，目前基于图神经网络的图分类方法在大部分数据集上并没能有效地利用到图的结构信息, 其对于图分类的预测性能甚至不如没有建模图结构信息的方法。因此，如何有效建模并合理利用图结构信息是图分类任务面临的 一大重要挑战。
（3）强表达能力且高校的模型构建
目前基于信息传递的图神经网络方法都与1-WL图同构测试有着紧密的联系。Xu等人[24]已经证明，基于信息传递的图神经网络，其表达能力的上界就是1-WL (Weisfeiler-Lehman) 图同构测试。近年也有一些对表达能力更强的基于高阶WL图同构测试的图神经网络的探索。但总的来说，WL测试关注的是对图是否同构的判断。一方 面，对图同构的判断还未被证明可以在多项式时间内完成，通常计算复杂度较高。另一方面，在这种标准下，并不能保证表达能力强的模型，也就是对图是否同构的判断准确率高的模型，在图分类问题上也表现得好。基于此，探索合适的图分类模型表达能力的判断标准非常重要，这也是对图分类本质的探索过程。如何构建一个具有强表达能力且高效的模型是图分类问题中的一个关键挑战。

2. 基于图相似度计算的图分类

在许多依赖图形表示数据的领域中（如信息可视化、网络分析等领域），评估图之间的相似度是一个关键问题。这些方法还可以应用于多种下游任务（如上述提到的任务），例如图像检索、网络关系分析等。本节将重点讨论基于图相似度的分类方法。
对于一组给定的图形，在应用基于相似度计算的分类方法时（即通过计算不同图形之间的相关性），首先会利用核化或匹配技术来计算两个图形之间的相似程度。然后通过机器学习模型（如支持向量机或神经网络等），根据已经得到的相关性矩阵对这些图形进行分类。
这类方法所依据的一个基本假设是：如果两个图形具有较高的相关性，则它们可能属于同一类别。这类方法的关键在于如何有效地衡量不同图形之间的相关性。

2.1 基于图核的图分类

作为一类将低维空间中的非线性不可分问题映射到高维空间中实现线性可分的技术，
其核心在于衡量成对数据间的相似程度。
而图核（graph kernel）作为一种特殊的用于度量图之间相似性的核函数，
其本质是首先定义显式或隐式计算两个不同对象之间的相似性。
基于此，
基于图核的分类方法实际上就是先通过计算各目标对象间的相似关系，
然后利用这些关系构建判别模型。
值得注意的是，
基于图核进行分类的过程如上所述，
如具体实施细节可参考附录部分：

图核被定义为在图空间\mathcal{G}上的对称正定函数。值得注意的是，这种函数同样能以希尔伯特空间中的内积形式表达。具体而言，在给定一个图G时，存在从该图空间到希尔伯特空间的映射函数\phi（即\phi : \mathcal{G} \rightarrow \mathcal{H}），使得对于任意两个图G_1和G_2之间满足k(G_1, G_2) = \langle \phi(G_1), \phi(G_2) \rangle的关系式成立。由此可见，在这种定义下所引出的一种性质即是：其能够将高维空间中的内积运算转化为低维子空间内的计算方式。这导致了两种主要的计算方式：第一种是直接指定每个图对应的特征映射函数\phi（即显式地定义每个特定类型的特征），然后通过对这些特征向量之间的内积运算来获得两两之间相似度；第二种则是通过隐式的角度来计算相似度矩阵（kernel matrix），无需明确知道具体的特征映射关系即可直接求解任意两个对象间的相似度度量值。因此，在这一框架下所建立起来的方法体系的核心要素就在于如何巧妙地设计适合特定应用场景下的合适核函数形式。

在图核领域中，R-卷积核通常被视为一种高级结构，在处理复合对象时（如图），它将这些复杂对象分解为若干独立的部分（如子图或子树）。随后通过比较各部分之间的关系来评估整体相似性。在图像分类任务中，常见的图核方法主要包括以下三类：

• 基于路径的图核
• 基于子图的图核
• 基于子树的图核

这些方法均建立在R-卷积核的基础上，并将其作为核心框架展开研究；它们是该技术框架下的具体实现。主要区别体现在对图结构的不同分解方式上：通过路径分析、子图构建以及树状结构划分等手段将复杂网络拆解为路径、子图和树状结构；进而采用显式或隐式的方式对网络相似性进行量化评估。通常情况下，在显式计算条件满足且生成特征向量的空间维度 manageable时？A这种情况下（指显性条件满足时），其运算速度和内存占用效率往往优于隐式算法。

2.1.1 基于路径的图核方法

在基于路径的图论框架下，在研究两个网络或结构间的相似程度时，我们关注的是两网络间共同拥有的关键特征量。这种特征量通常与网络中各节点间的相互关联性有关，在实际应用中具有重要的价值。核心区别在于对'网络'这一概念的具体定义方式不同：一种是基于'连接'关系的网络模型（如传统的无向或有向图），另一种则是以特定规则下的连接行为为基础构建的动态网络模型（如交通网、信息传播网等）。

在现有研究中发现：随机游走模型虽然在某些方面具有良好的特性（如鲁棒性），但其计算复杂度较高且容易导致计算过程中的'重叠回溯'问题（即同一节点多次被访问导致结果偏差）。本文重点分析了另一种更为基础的方法——'基于最短距离'的方法（shortest path kernel）。该方法的基本思路是：首先将原图转换为一个带有边权重的网络结构，在这个新构造的网络中每条边被赋予当前节点对之间的'最小距离'作为权重；然后通过某种方式比较两个这样的网络结构是否具有较高的相似性。

具体而言，在这种方法下：我们首先需要确定每个节点之间的最小距离值；接着利用这些值构建一个新的加权邻接矩阵；最后通过计算这两个加权邻接矩阵之间的某种内积形式来衡量两者的相似程度。在这种框架下：每一条边都代表了对应两组数据点之间的一种联系强度；而整个系统的相似性则可以通过统计所有可能的连接强度总和来进行评估。

2.1.2 基于子图的图核方法

基于子图结构的图核用于度量不同网络模型之间的相似性时

2.1.3 基于子树的图核方法

基于子树的图核方法在度量图的相似度时，先将图转化成树，再通过度量树相似度来度量图相似度。主要方法有基于子树模式的图核，基于树模式的图核等。其中，Weisfeiler-Lehman子树核（WL子树核）是使用最广泛的基于子树的图核方法。**该方法的主要思想是将图分解为子树，通过度量子树间的相似度来获得图的相似度。**它是基于1维的Weisfeiler-Lehman图同构测试提出的一种快速特征提取机制。给定多个节点标签离散的图，先将每个节点的邻居聚合并对邻居进行排序，节点标签和排序后的邻居标签共同组成多重集合（multiset）。然后对这些多重集合进行压缩映射，得到对应的新标签。接着将这些新标签赋给节点，此时完成一次迭代 ，如图3中的a-d所示，需要注意的是，多重集合压缩和重新标记的过程是所有输入图共同进行的，标签压缩的对应关系也是所有图共享的。在图G_1,G_2上迭代h次的WL子树核定义为:
k_{WL_{subtree}^{(h)}}(G_1,G_2)=\left \langle \phi _{WL}^h (G_1), \phi _{WL}^{h}(G_2) \right \rangle
其中，\phi_{WL}^{h}(G)定义为h次迭代中节点标签出现次数的特征向量。\phi_{WL}^{h}(G)=(c_0(G,\sigma _{01})),...,(c_0(G,\sigma _{0|\sum _0|})) ,...,(c_h(G,\sigma _{0h})),...,(c_h(G,\sigma _{h|\sum _h|})),(c_i(G,\sigma _{ij})表示节点标签\sigma_{ij}在图G中出现的次数。可以看出，WL子树核是通过对两个图中共同的子树结构进行计数进而计算图相似度的。在N个图迭代h次的情况下，算法复杂度为O(Nhm+N^2hn)，其中n和m表示图中最大节点数和最大边数。图3是WL子树核在两个图上迭代计算一次的过程，其中，经过压缩得到的每个标签都代表一个子树模式 。例如标签11，表示一个高度为1，根节点为4，邻居节点为1，1，3和5的子树。表2对本文中介绍的3种代表性传统图核方法进行了对比。

Yanardag等研究团队表明，在现有的图谱化方法中关键子结构性素之间存在高度依赖关系。具体而言，在基于Graphlet的方法中（如图2所示），每个Graphlet都可以通过向另一个Graphlet添加一条边或一个节点来生成（例如F3可以通过增加一条边从F4生成）。随着单个Graphlet单元尺寸的增长呈指数级扩大特征空间会导致冗余信息大量增加进而引发所谓的对角控制问题：即在同一数据集中同一张图与其自身间的相似度远高于与其他不同图之间的相似度。基于此背景Yanardag等人开发出了一种深度图谱化策略：
k_{dgk}(G_1,G_2)=\phi (G_1)^TM\phi (G_2)
其中M是一个反映关键子结构性素间相互关系的矩阵。对于M矩阵的具体计算有两种思路：第一种思路是当关键子结构性素间存在明确的数学关联时可依据它们之间的相似度直接构建M矩阵；第二种思路则建议将这些关键子结构性素视为类似于语言学中的"单词"并采用自然语言处理领域中的词嵌入技术来隐式学习它们之间的相似度关系从而构建M矩阵。
上述研究不仅涵盖了基于Weisfeiler-Lehman子树谱化方法还囊括了传统的Graphlet谱化方法这两种核心算法均成功整合到该深度图谱化的统一框架下并通过实验验证它们在分类任务上的性能表现具有较高的一致性提升效果。

该方法通过融合不同节点间的关联信息以及利用核函数对数据进行非线性映射的能力，在基于图相似度计算的基础上实现了有效的分类效果。然而，在现有技术中通常将特征提取与分类器设计分离进行，在实际应用中难以实现整体优化目标。此外，在现有研究中发现该类算法在计算效率相对较低的情况下难以应用于大规模数据集中的图结构分析问题

2.2 基于图匹配的图分类

图匹配是一种图相似度度量的方法。图匹配包括精确图匹配和非精确图匹配，精确图匹配需要图之间节点的映射关系，应用于图同构，子图同构，最大公共子图的判别等问题中。非精确图匹配多数可以形式化为图编辑距离GED（graph edit distance）的计算。
这里主要介绍非精确图匹配进行图分类的方法。这类方法的核心是先通过跨图机制对两个图之间的某种相似度度量进行计算。例如图编辑距离，然后通过相似度度量对图进行分类，常用的分类器是最近邻分类器。基于图匹配的图分类过程如图4所示：

该研究探讨了多种基于图数据的相似度计算方法及其应用。
（1）Li等提出了一种称为图匹配网络模型（GMN）的方法，在计算两个图之间的相似度时综合考虑了同一子图内节点特征与异构子图间节点特征的影响机制。
当输入一对具有显著相似程度的子图时 ，该模型能够有效提取并融合各子图间的特征表示 ，并通过跨层注意力机制自动学习各子层间的关联关系 最终生成反映两子图之间相似程度的数值指标
。
（2）Bai等则设计了一种基于卷积神经网络的相似度计算框架（GSimCNN），其核心创新在于引入了新的交互层结构 ，能够动态地捕捉并表达不同子图间节点间的复杂关联关系 该模块能够自动学习各子层间的特征融合权重 并生成一个完整的相似度矩阵
。
（3）在此基础上 SimGNN 方法进一步优化 通过引入多层感知机结构实现了对上述生成过程的有效建模 同时显著提升了计算效率
该模型不仅能够高效地提取跨子graph 的全局特征 还能通过端到端的学习框架实现快速相似度计算

尽管基于深度学习的这些图匹配方法获得了图的表现形式或相似性分数，并未显式地执行后续步骤中的图分类任务。然而，在本质上与之高度相关的是其生成的表现特征和相似性得分矩阵；这两个要素都可以通过特定的方式被用来完成图像分类的任务。因此，在本文中我们将这些方法归类为基于相似性计算的图像分类技术。

基于图匹配原理构建的图相似度计算方法在计算机科学领域广泛应用于二分类函数相似度搜索任务，并通过分析代码特征来识别是否存在特定不稳定结构。此外，在生物化学领域中这一方法也被用来评估化合物之间的性质差异性。