图数据(graph data)广泛地存在于我们的生活中, 用于表示复合对象元素之间的复杂关系. 例如社交网络, 引文网络, 生物化学网络, 交通网络等. 不同于结构规则的欧式数据, 图数据的结构复杂, 蕴含着丰富的信息. 近年来, 对图数据的研究是学术界的一个热点. 图上的研究问题包括节点分类[1, 2], 图分类[3, 4], 链路预测[5]等, 本文主要关注图分类问题. 给定一组图, 图分类的目标是学习图和对应类别标签的映射关系, 并预测未知图的类别标签. 图分类是一个重要的数据挖掘任务, 可以应用在很多领域, 例如化学信息学中, 通过对分子图进行分类来判断化合物分子的诱变性、毒性、抗癌活性等[6, 7]; 生物信息学中, 通过蛋白质网络分类判断蛋白质是不是酶, 是不是具有对某种疾病的治疗能力[8, 9]. 从这个角度来看, 图分类研究具有非常重要的意义.

图分类的研究方法主要包括基于图核的方法, 基于图匹配的方法和基于图深度学习的方法. 目前已有一些针对图分类领域中某类特定方法的综述, 如图核方法综述[10, 11], 图相似度学习综述[12]. 但就我们所知, 当前还没有既包括传统方法又包括近年来快速发展的深度学习方法的图分类研究综述. 为了方便更多的研究人员, 本文梳理总结了图分类的各类研究方法和这些研究之间的相互关系.

本文将现有图分类方法总结为两大类, 第1类是基于相似度计算的图分类方法. 基于相似度计算的图分类是通过计算成对图的相似度对图进行分类, 包括图核方法和图匹配方法. 其中, 图核方法主要通过图核的定义来计算图的相似度, 是常见的传统图分类方法. 过去多年中已经有多种基于图核的分类方法被提出[13-15], 它们共同的思想是将图分解为某种子结构, 通过对比不同图上的子结构来计算图的相似度进而进行图分类. 基于图匹配方法的图分类方法, 则是通过考虑一些跨图的因素来计算图之间的相似度分数进而对图分类. 早期的图分类问题主要关注于图核方法, 然而这种方法不够灵活且通常计算代价较大, 图的特征提取过程和图的分类是独立进行的, 因此无法针对具体任务进行优化.

第2类是基于图神经网络的图分类方法. 随着深度学习在图像, 文本等领域的成功, 研究人员开始关注用深度学习建模图数据. 基于深度学习的图数据建模方法也逐渐被应用于图分类问题[16-19]. 其中, 图神经网络应用于图分类问题时, 主要包括卷积算子和池化算子两个重要部分. 卷积算子利用结构和节点特征信息对图的特征进行提取, 池化算子对特征进行汇总得到整个图的表示用于分类. 本文从这两个角度对基于图卷积神经网络的图分类进行了总结分析.

尽管近期已有大量的基于图神经网络的方法应用于图分类任务, 但这个领域仍然存在许多问题和挑战, 例如领域内不同模型的实验设置不同导致的复现困难; 有些模型在特定数据集上表现较好, 但模型泛化能力有限; 此外, 图分类任务中对图结构信息的利用也是一个挑战. 本文从这个角度总结分析了图分类中存在的挑战和未来的研究方向.

本文第1节给出图分类问题定义并指出图分类领域中的问题和挑战. 第2节梳理了基于相似度计算的图分类方法, 其中包括基于图核方法的图分类和基于图匹配的图分类. 第3节介绍并分析了基于图神经网络的图分类方法. 第4节关注图分类方法的评价, 包括图分类的数据集, 评价指标和一些典型方法的效果对比分析. 第5节汇总了图分类在各个领域的应用场景并给出未来可能的研究趋势. 最后一节总结全文.

本节我们给出图分类问题的定义和全文的符号定义, 并简要总结图分类中的问题与挑战.

图分类是图数据挖掘的一个重要研究问题, 其目标是找到图和对应类别标签的映射关系. 具体来说, 给定一组图 ${\boldsymbol{G}} = \{ {G_i}\} _{i = 1}^N$ 及其标签 ${\boldsymbol{Y}} = \{ {{\cal{Y}}_i}\} _{i = 1}^N$ 其中每个图表示为 ${G_i} = (V,E,X)$ . 图分类任务是指利用图的邻接矩阵A和特征信息X, 通过机器学习的方式获取图和对应类别标签的映射关系并预测未知图的标签. 为了正确预测图的类别, 需要充分地利用给定的结构信息和节点特征信息. 常见的图分类包括图的二分类及多分类问题[4], 此时, 每个图对应一个类别标签 ${{\cal{Y}}_i} = \{ {y_{i,j}}\} _{j = 1}^1$ . 除此之外, 图分类还包括多标签分类问题[20], 多标签是指每个图对应的标签可以有一个或多个(M), 即 ${{\cal{Y}}_i} = \{ {y_{i,j}}\} _{j = 1}^M$ .

对于图 $G = (V,E,X)$ , 图标签为 ${\cal{Y}}$ . $V$ 表示图中节点集合, $|V| = n$ 为节点数. E表示图中边的集合, $E \subseteq V \times V$ . $X$ 表示图上节点的特征矩阵, $X \in {R^{n \times D}}$ . ${X_i}$ 表示第 $i$ 个节点的特征向量, $D$ 为节点的特征维度. 此外, $A \in {R^{n \times n}}$ 表示图的邻接矩阵, 表明图上节点之间的连边关系. 表1中汇总了全文中常见的符号及其表示的含义.

图分类是图领域中一个极具挑战的任务, 当前图分类任务上仍然存在许多问题和难点, 主要包括以下几个方面.

(1)图数据的复杂多样性

生活中有大量的数据都可以用图这种数据结构进行表示. 例如社交网络, 化学分子结构, 生物蛋白质结构等. 每种类型的图中都包含不同的特征信息和结构信息. 这种多样的信息提高了图数据的分类难度. 此外, 图数据是非欧空间数据, 一般来说, 每个图的节点数不同, 图中节点连接方式不同, 每个节点的邻居个数也不同. 卷积、池化等在欧式数据中比较容易定义的操作, 很难直接迁移到图数据上. 图数据的复杂性和多样性, 为图数据的分类带来非常大的挑战.

(2)图结构信息的有效建模

作为非欧数据, 图的结构信息非常丰富. 图数据的结构信息是指图上节点之间的连接关系, 包括节点的一阶连接信息, 二阶信息以及高阶信息等[21]. 图上机器学习的最基础挑战之一就是找到一种可以表示、编码图结构的方法, 从而使得图结构信息可以被机器学习方法有效利用[22]. 图的结构信息对于图分类任务也至关重要. 例如, 在生物信息学等领域的数据集中, 图的属性标签与图上的某些结构模式有着必然的联系. 然而Errica等人[23]在实验中发现, 目前基于图神经网络的图分类方法在大部分数据集上并没能有效地利用到图的结构信息, 其对于图分类的预测性能甚至不如没有建模图结构信息的方法. 因此, 如何有效建模并合理利用图结构信息是图分类任务面临的一大重要挑战.

(3)强表达能力且高效的模型构建

目前基于信息传递的图神经网络方法都与1-WL图同构测试有着紧密的联系. Xu等人[24]已经证明, 基于信息传递的图神经网络, 其表达能力的上界就是1-WL (Weisfeiler-Lehman)图同构测试. 近年也有一些对表达能力更强的基于高阶WL图同构测试的图神经网络的探索[25, 26]. 但总的来说, WL测试关注的是对图是否同构的判断. 一方面, 对图同构的判断还未被证明可以在多项式时间内完成, 通常计算复杂度较高. 另一方面, 在这种标准下, 并不能保证表达能力强的模型, 也就是对图是否同构的判断准确率高的模型, 在图分类问题上也表现得好[27]. 基于此, 探索合适的图分类模型表达能力的判断标准非常重要, 这也是对图分类本质的探索过程. 如何构建一个具有强表达能力且高效的模型是图分类问题中的一个关键挑战.

在很多用图来表示数据的领域, 图之间相似度度量是关键问题之一[12], 它可以进一步处理一些下游任务, 包括图分类, 图聚类和相似性搜索等. 本节关注利用图的相似度度量进行图分类的方法. 给定一组图, 基于相似度计算的图分类方法先通过图核或者图匹配的方法获得两个图之间的相似度度量, 然后利用机器学习方法, 根据已经得到的相似度度量对图进行分类. 这类方法隐含的假设是当两个图相似度较高时, 它们所属的类别也相同. 这类方法的关键是对图之间相似度的计算. 本节从相似度计算的角度, 将基于图相似度计算的图分类分为基于图核的方法和基于图匹配的方法, 分别进行介绍和分析.

核方法是一类把低维空间下非线性可分问题转化为高维空间下线性可分问题的方法, 其核心在于度量成对数据的相似性. 图核(graph kernel)是一种特殊的核方法, 其核心在于对图之间的相似度的度量. 基于图核的图分类方法实质是先利用图核方法显式或隐式地计算图之间的相似度, 然后利用核机器通过图相似度进行图分类. 基于图核进行图分类的过程如图1所示.

图核是一个定义在图空间 ${\cal{G}}$ 上的对称正定函数, 这个函数也可以表示为希尔伯特空间的一个内积. 具体来说, 当给定图 $G$ 时, 存在一个图空间到希尔伯特空间的映射 $\phi :{\cal{G}} \to {\cal{H}}$ , 使得 $k({G_1},{G_2}) = \langle \phi ({G_1}),\phi ({G_2})\rangle $ [28]. 可以看出, 核函数可以将高维空间的内积运算转换为低维空间的核函数计算[29]. 这种定义导致了两种计算图核的方法[30], 一种是显式地定义每个图的特征映射函数 $\phi $ , 然后通过特征映射后的向量内积得到图之间的相似度. 另一种是通过核函数隐式计算, 不需要知道具体的特征映射函数 $\phi $ , 直接通过核函数的定义计算得到任意两个图之间的相似度度量核矩阵(kernel matrix), 用来连接核函数和用于分类的核机器算法. 图核方法在图分类问题中被广泛使用[10], 其核心在于定义合适的核函数.

R-卷积核[31]是常见图核方法的顶层框架, 直观来看, R-卷积核的框架将复合对象(例如图)按照某种分解方式分解为不同的组件(例如子图, 子树), 然后通过对比每对组件来计算复合对象的相似度[11]. 用于图分类的常见图核方法包括3类: 基于路径的图核, 基于子图的图核和基于子树的图核. 他们都基于R-卷积核[31]的框架定义的, 都是R-卷积核的实例. 这3类图核方法的主要区别在于图的分解方式. 基于路径, 子图和子树的图核方法分别将图分解为路径, 子图和子树, 然后利用显式或者隐式的方法对图的相似度进行计算. 一般来说, 当显式计算可行, 并且得到的特征向量维度数不是过高, 那么它通常比隐式计算更快、内存效率更高[10].

基于路径的图核方法中, 两个图的公共路径越多, 它们越相似. 这类方法的核心在于对路径的不同定义, 主要方法有最短路径核[13]和随机游走核[32, 33]. 随机游走核存在计算复杂度大, 路径回溯等问题. 本文中我们主要关注最短路径核[13], 该方法是将图分解为节点之间的最短路径, 然后对比两个图中任意对节点间的最短路径, 从而计算图的相似度. 最短路径核方法先是将原始图转化为最短路径图, 最短路径图中节点集同原图中节点集一样, 不同的是, 最短路径图中的边用两个节点中的最短路径长度标记. Borgwardt等人[13]用弗洛伊德算法(Floyd-Warshall)得到最短路径图, 设 ${G_1},{G_2}$ 是两个输入图, 最短路径图分别是 ${S_1},{S_2}$ . 然后在 ${S_1} = ({V_1},{E_1})$ 和 ${S_2} = ({V_2},{E_2})$ 上定义最短路径图核:

其中, $k_{\rm{walk}}^{(1)}$ 是边上的半正定核, 可以被定义为狄拉克核函数, 即当 ${e_1}$ 和 ${e_2}$ 长度相同时其值为1, 否则为0. 可以看出, 相同长度的最短路径越多, 图的相似度越高. 计算最短路径图的弗洛伊德算法复杂度为 ${\rm O}({n^3})$ , 考虑两个图中所有边对时, 最短路径核算法的复杂度为 ${\rm O}({n^4})$ .

基于子图的图核在度量图的相似度时, 先将图转换成子图结构的组合, 再通过比较两个图中的子图分布来度量图相似度[34]. 主要方法有循环模式核, 最优分配核等[14, 35, 36]. 其中的一个经典方法是Graphlet图核[14]. Graphlet是指由 $m$ 个节点组成的子图, 一般而言 $m \in \{ 3,4,5\} $ . 图2给出了大小为4的所有Graphlet. Graphlet图核方法通过对Graphlet计数的方式来对比不同的图. 定义 $G = \{ Graphlet(1),\cdots,Graphlet({N_k})\}$ 为大小为 ${N_k}$ 的Graphlet的集合, ${f_G}$ 是一个长度为 ${N_k}$ 的向量, ${f_G}$ 的第 $i$ 个值表示 $Graphlet(i)$ 在图 $G$ 中出现的频次. 给定两个大小为 $n$ 的图 ${G_1},{G_2}$ , 其中 $n > k$ . Graphlet图核定义为:

其中, 向量 ${f_{{G_i}}}$ 可以看作是图 ${G_i}$ 的特征向量. 可以看出, Graphlet核值是通过两个图的特征向量的内积来显式计算得到的. 由于每个图中有 $\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$ 个大小为 $k$ 的子图[11], 计算该图的特征向量复杂度为 ${\rm O}({n^k})$ , 因此, 该方法不适用于大规模的图.

基于子树的图核度量图的相似度时, 先将图转换成树, 再通过度量树相似度来度量图相似度. 主要方法有基于子树模式的图核, 基于树模式的图核等[7,15, 37]. 其中, Weisfeiler-Lehman子树核(WL子树核)[15]是使用最广泛的基于子树的图核方法. 该方法的主要思想是将图分解为子树, 通过度量子树间的相似度来获得图的相似度[34]. 它是基于1维的Weisfeiler-Lehman图同构测试[38]提出的一种快速特征提取机制. 给定多个节点标签离散的图, 先将每个节点的邻居聚合并对邻居进行排序, 节点标签和排序后的邻居标签共同组成多重集合(multiset). 然后对这些多重集合进行压缩映射, 得到对应的新标签. 接着将这些新标签赋给节点, 此时完成一次迭代, 如图3中a–d所示. 需要注意的是, 多重集合压缩和重新标记的过程是所有输入图共同进行的, 标签压缩的对应关系也是所有图共享的. 在图 ${G_1},{G_2}$ 上迭代 $h$ 次的WL子树核定义为:

其中, $\phi _{\rm{WL}}^h(G)$ 定义为 $h$ 次迭代中节点标签出现次数的特征向量. $\phi _{\rm{WL}}^h(G) = ({c_0}(G,{\sigma _{01}}),\cdots,{c_0}(G,{\sigma _{0|{\sum _0}|}}),\cdots,{c_h}(G,{\sigma _{0h}}),\cdots, $ $ {c_h}(G,{\sigma _{h|{\sum _h}|}}))$ , ${c_i}(G,{\sigma _{ij}})$ 表示节点标签 ${\sigma _{ij}}$ 在图 $G$ 中出现的次数. 可以看出, WL子树核是通过对两个图中共同的子树结构进行计数进而计算图相似度的. 在 $N$ 个图迭代 $h$ 次的情况下, 算法复杂度为 ${\rm O}(Nhm + {N^2}hn)$ , 其中 $n$ 和 $m$ 表示图中最大节点数和最大边数. 图3是WL子树核在两个图上迭代计算一次的过程[15], 其中, 经过压缩得到的每个标签都代表一个子树模式. 例如标签11, 表示一个高度为1, 根节点为4, 邻居节点为1, 1, 3和5的子树. 表2对本文中介绍的3种代表性传统图核方法进行了对比.

Yanardag等人[39]发现, 在常见的图核方法中, 用于计算核矩阵的子结构并不独立. 例如在Graphlet图核方法中, 一个Graphlet可能由另一个Graphlet添加一条边或者一个节点得到(图2中F3可以由F4增加一条边得到). 由于随着Graphlet尺寸增大, 特征空间指数级增加, 而子结构之间的依赖导致这样的特征空间中存在大量冗余. 此外, 特征空间维度的指数级增长会导致核方法中的核矩阵的对角控制问题, 也就是同一个数据集中, 一个图只与自己本身相似, 而与其他图不相似. 为了解决这两个问题, Yanardag等人[39]提出了深度图核方法:

其中, M是一个表示子结构之间关系的矩阵. 关于M矩阵的计算有两种方法: (1)在子结构之间具有清晰的数学关系时, 可以利用它们之间的相似度来计算M矩阵; (2)将子结构当做”单词”, 利用自然语言处理领域的单词嵌入技术学习子结构隐式表达之间的相似度矩阵M. 上文中提到的基于WL子树核方法和Graphlet图核方法都可以应用于这个深度图核的框架下并在分类效果上取得了一致性的提升.

过去几年中, 有大量的图核方法被提出并应用于图分类任务中, 图核方法结合了图的表示能力和核方法的区分能力[11], 可以解决基于图相似度计算的图分类任务. 但这些方法中特征表示和分类的过程是分开进行的, 无法统一优化. 另外, 基于图核的方法计算复杂度通常较高, 无法应用到大规模图中.

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

图匹配方法通常利用跨图节点的对比来计算两个图之间的相似度. Li等人[43]首先提出图匹配网络模型(GMN),该模型计算图之间相似度时不仅考虑每个图内节点信息, 也考虑跨图节点的信息. 输入一对图时, GMN同时学习两个图的表示, 通过跨图的注意力机制计算跨图节点的相似性, 图的表示不仅依赖于本图中的邻居节点也依赖于另一个图中的节点. GMN可以保证当两个图匹配度较高时, 学得的表示也更相似, 相似度分数更高. 类似地, Bai等人[44]提出了基于卷积神经网络的图相似度计算模型(GSimCNN). 不同于GMN, GSimCNN设计了图交互层计算两个图中每对节点的相似度并形成图相似度矩阵. 接着用多个卷积神经网络层对相似度矩阵进行特征提取, 计算得到两图的相似度分数. 在GSimCNN的基础上, Bai等人[45]提出了快速计算图相似度的模型SimGNN. 该模型不仅计算了跨图的节点相似度向量, 而且计算了两个图表示间的相似度向量, 进而利用这两个相似度向量计算得到两个图的相似度分数. 虽然这些基于深度学习的图匹配方法得到图的表示或者相似度分数后, 没有显式地进行后续的图分类任务, 但他们本质与图分类任务非常接近, 图的表示和图相似度分数都可以用来完成图分类任务[41], 因此本文将它们归于基于图相似度计算的图分类中.

基于图匹配的图相似度计算方法常常被用于计算机安全领域中二分函数相似度搜索, 检测代码中是否含有已知不稳定结构. 也常被用于生物化学领域中, 利用图相似度分数判断化合物属性. 具体应用方法详见第5节.

前文介绍的图核方法很多年来都是图分类中的主导方法, 也取得了不错的分类效果[25]. 但由于这些方法通常依赖于一组固定特征, 其特征表示难以有效地适应于新的数据分布. 随着图深度学习的发展[46], 一些神经网络方法开始用于解决图分类任务. 本节重点关注基于图神经网络的图分类方法, 这类方法通过端到端的方式进行模型的优化学习, 为图分类的准确率带来了较大的提升.

应用于图像分类任务的传统卷积神经网络, 主要包括卷积和池化两个操作, 这两个操作依赖于图像数据的结构规则性和平移不变性. 类比于图像分类任务, 图卷积神经网络应用于图分类问题时, 同样需要关注卷积和池化算子. 但不同于图像数据, 图数据是非欧空间数据, 同一个数据集中的每个图大小不同, 结构不一. 图中的每个节点也具有不同的局部结构, 为图分类中卷积算子和池化算子的设计带来了巨大的挑战. 给定一组图. 基于图神经网络的图分类方法通常先通过卷积的方式对这些图进行多次特征变换, 然后在此基础上进行池化操作, 将图的规模缩小. 这个过程可以重复多次, 最终得到整个图的表示, 从而进行分类. 本节就从图分类任务中的卷积算子和池化算子角度, 对基于图神经网络的图分类方法进行总结和分析. 利用图神经网络进行图分类的过程如图5所示. 其中, 可选的操作和模块用虚线表示. 环形箭头表示操作可以选择重复 $1 - n$ 次.

在图级别的任务中, 图卷积操作主要是为了对图进行特征变换和特征提取. 在这个过程中需要尽可能多地利用图中节点特征和拓扑信息. 当前在图分类任务中, 主要的卷积方式有两种, 一种是信息传递(massage-passing)式的卷积, 即直接在原始图结构中定义由邻居聚合和迭代更新机制所组成的卷积算子. 例如图卷积神经网络GCN, 基于注意力机制的图卷积神经网络GAT等. 另一种是传统卷积神经网络(CNN)式的卷积, 先将非欧图转化为规则网格结构, 再应用传统卷积神经网络直接进行卷积操作.

(1)信息传递式卷积

Gilmer等人[47]提出了信息传递式(MPNN)的通用框架, 将卷积过程形式化为信息传递和节点信息更新两个函数. 信息传递是指各个节点将自己邻居的信息聚合到自身节点, 节点信息更新是将该节点上一层的节点表示与聚合后的邻居信息进行结合的过程. 本文把符合这种框架的卷积方式称为信息传递式 (MPNN)卷积. 早期的信息传递式卷积主要用于节点分类任务, 取得了很好的分类效果. 在图分类任务中, 信息传递式卷积用来进行特征变换, 得到图上节点的表示. 以Kipf等人[48]提出的图卷积网络GCN为例:

其中, ${H^{(l)}}$ 是 $l$ 层中节点的表示矩阵, ${W^{(l)}}$ 是可训练的参数矩阵, $\widetilde A = A + {I_N}$ 表示包含自连接的邻接矩阵, $\sigma $ 表示非线性激活函数.

采用MPNN式卷积的图分类模型通常先利用节点的特征和图的结构求得特征映射后的节点表示, 然后利用池化机制得到图的表示并进行分类. Ma等人[16]提出的谱池化(EigenPool)图分类模型, Gao等人[49]提出的Graph U-net模型, 和Lee等人[19]提出的自注意力池化(SAG)模型中均采用信息传递式卷积中的GCN进行节点表示学习. 此外, Zhang等人[4]提出的深度图卷积网络DGCNN和Yuan等人[50]提出的结构池化图分类模型StructurePool也采用了类似于GCN的信息传递式卷积, 具体卷积形式为 $Z = f({\widetilde D^{ - 1}}\widetilde AXW)$ , 其中, $\widetilde A$ 和GCN中定义相同, $\widetilde D$ 是度矩阵, 其中 ${\widetilde D_{ii}} =\displaystyle \sum\nolimits_j {{{\widetilde A}_{ij}}} $ . $W \in {R^{c \times c'}}$ 是可训练参数矩阵. Zhang等人[4]证明了这种卷积方式理论上比GCN更近似于WL算法. Ying等人[17]提出的可微分池化分类模型DiffPool中, 卷积部分可以采用任意MPNN式卷积.

以上提到的各模型中的MPNN式卷积, 都是基于第2.1节中介绍的1-WL算法提出的. 但Xu等人[24]指出, 基于1-WL的任何信息传递式的图卷积神经网络, 其表达能力都不会强于1-WL. 而1-WL本身的表达能力有限, 对很多非同构图并不能准确地分类. 也就是说, 当1-WL算法将两个非同构图判断为“可能同构”时, 信息传递式的图卷积网络输出的两个图的表示是相同的. 这样的弱区分能力, 对图分类的效果会产生负面的影响. 近年来, 有研究者提出了一些基于k-WL算法的图神经网络[25, 26]. k-WL算法是一种基于带标签子图的图同构判断算法. 在基于1-WL的GNNs中, 信息传递的基本单元是节点. 不同于此, k-WL算法中信息传递的基本单元是大小为k的子图结构. 其中, 基于集合的k-WL算法set k-WL表达能力弱于k-WL算法, 计算复杂度低于k-WL[21, 25]. 考虑到内存的限制, Morris等人[25]提出基于set k-WL算法的k-GNNs模型, 该模型的关键是信息传递在大小为 $k$ 的节点集合对应的子图结构之间进行. k-GNNs为每个大小为k的集合 $s \in {[V(G)]^k}$ 按照如下方式更新他们的特征向量:

其中, $N(s) = \{ t \in {[V(G)]^k}\left| {\left| {s \cap t} \right| = k - 1} \right.\} $ , 表示集合 $s$ 与邻居集合 $t$ 的交集元素个数为 $k - 1$ . k-GNNs的表达能力和set k-WL算法一样强大. 该模型需要枚举大小为 $k$ 的子图, 由于计算复杂度较高, 只考虑了 $k$ 为1, 2, 3的情况, 并提出一种层次化的1-2-3GNN网络. 该模型在图分类任务中, 取得了一致性好于1-GNN的效果. Maron 等人[26]提出通过矩阵相乘实现一种和3-WL有同样区分能力的GNN模型, 比k-GNNs[25]具有更低的空间复杂度和更容易部署的优点.

目前, 图卷积神经网络模型的表达能力都是通过对图是否同构的判断能力来衡量的[24, 51], 那么基于k-WL算法的图卷积神经网络的表达能力显然强于基于1-WL算法的图卷积神经网络. 然而, 基于k-WL算法的图卷积神经网络[25, 26]需要对带标签的子图结构进行枚举, 类似于对带标签信息的Graphlet的枚举, 因此带来了非常大的计算代价. 实际应用中, 我们仍需在表达能力和计算消耗之间进行权衡.

(2) CNN式卷积

图分类任务中, 还有一种卷积方式, 即先把图数据按照一定的规则变换为欧式数据, 然后按照传统卷积网络的方式进行卷积变换. 本文把他们称做CNN式卷积. 相比MPNN式卷积, 这类卷积在目前的图分类中应用不多, 但取得了较好的分类效果. 类比图像分类任务中的CNN, 图分类中的CNN式卷积网络, 可能也具备抽取图中关键结构的能力. Niepert等人[52]指出, 由于图像中像素存在隐式的空间顺序, 如图6(a), 因此可以为节点按照顺序从左到右从上到下生成邻居图, 也就是感受野. 接着, 3×3的感受野读到的值会被转化为序列然后送入卷积层中, 如图6(b)所示. 然而, 图数据中每个节点结构并不一致, 不存在这样统一的空间顺序.

Niepert等人[52]率先提出了PSCN模型将非欧图数据转换为欧式数据, 利用节点选择的方法解决了不同图数据中节点数不同的问题. 具体地, 用图标记算法按照某种排序标准对节点排序, 使得不同图中结构相似的节点可以处在序列中相似的位置, 然后选出指定个数的节点. 接着, PSCN利用图标准化解决了图中每个节点的邻居个数不同导致的节点感受野定义问题. 具体地, 该模型先用宽度优先的方式聚合邻居并进行排序, 将无序图空间映射到具有线性顺序的向量空间, 接着在该序列中选择指定个数的节点作为中心节点的感受野. 由于最优的图标准化是一个非确定性多项式难(NP-hard)问题, PSCN并未解决这个问题, 而是在众多图标记方法中选择了效果较好的方法并利用了辅助工具[53]对邻居图中节点进行定序. 得到统一的图表示后, 用一维卷积层进行卷积, 其中, 卷积核大小与节点感受野大小相同. 其余卷积和分类部分结构则可以任意选定.

由于PSCN模型为了解决不同图节点数不同的问题进行了节点的选择, 因此对于节点的卷积过程无法进行层堆叠, 只能抽取到一些局部的关键结构. 直观的解释就是, 如果进行第2次卷积, 节点的感受野中的邻居节点有可能在第一次卷积前的节点选择中未被选中, 因此没有这些节点的表达, 无法进行第2次卷积, 无法抽取一些全局的重要结构. 针对这个问题, Tzeng等人[54]提出了以自我为中心的卷积网络Ego-CNN, 可以发现图中的局部和全局关键结构. 如图7是Ego-CNN的模型框架图.

不同于PSCN, 以自我为中心的卷积网络Ego-CNN初始并没有进行节点的选择, 而是将输入图中的所有节点经过一个网络嵌入算法得到图节点的初始表达. 然后为每个节点选择指定个数的邻居并将邻居节点的表达拼接起来作为感受野. 接着用与感受野尺寸相同的卷积核进行多层卷积. 卷积过程可以公式化为:

其中, ${E^{(n,l)}}$ 是节点 $n$ 在 $l$ 层邻居的矩阵表示, 由节点 $n$ 及节点 $n$ 的 $K$ 个最近邻节点在上一层的表示连接形成, $Nbr(n,K)$ 表示节点 $n$ 的第K阶最近邻居, 它们是在模型开始前就确定好并且保持不变. $\sigma $ 是激活函数, ${b_d}$ 是偏置项. $ \circ $ 是Frobenius内积, 定义为 $X \circ Y = \displaystyle\sum\nolimits_{ij} {{X_{ij}}{Y_{ij}}} $ . 与PSCN相比, 它们的卷积方式相同, 主要的不同在于EgoCNN中节点 $k$ 阶邻居的固定定义方式和多次卷积的堆叠. $H_{Nbr(n,K),:}^{(l - 1)}$ 中已经包含了上一层的节点的表示, 由于没有进行节点的选择, 因此聚合K个最近邻时, 没有PSCN中邻居节点表示可能不存在的问题. 对 ${E^{(n,l)}}$ 进行卷积时, 可以重复地利用到上一层节点表示, 因此, $l$ 层的Ego-CNN可以在以节点为中心 $l$ -跳的网络内发现重要结构, 并可以通过反卷积的方式将关键结构可视化.

PSCN和EgoCNN都是在节点上进行卷积, 在卷积的过程中利用结构信息, 不同于此, Peng等人[21]提出的基于motif的子图注意力卷积网络MA-GCNN在将图表示为矩阵的过程中, 就充分利用了图的结构信息. 具体地, 在对图数据进行预处理时, 该模型先按照某种选择策略选出 $N$ 个节点, 并为每个选出的节点选择K个重要的邻居节点形成 $N$ 个子图. 然后将这些子图转换为基于motif匹配的矩阵表示, 这个矩阵里的基本单元是一个2-跳路径的motif, 经过匹配的多个motif形成子图表示, 多个子图的表示连接形成整个图的表示. 可以看出, 该模型在初始表示中用motif匹配的方式保留子图上的连边信息, 也就是子图结构信息. 基于此, MA-GCNN对这个矩阵进行2次感受野大小不同的卷积. 然后利用子图级别的注意力机制, 得到由重要子结构组成的图的表示进而进行分类. 直觉上来说, 在图分类中, 子图级别的注意力机制更具有可解释性. 通过验证表明, 基于子图的卷积取得了更好的图分类效果, 这也证明了该模型中对图数据的预处理过程更好地捕捉到了空间结构信息. 但与PSCN类似, MA-GCNN也对节点进行了排序和选择, 节点选择的过程相当于一次池化操作, 直接地丢掉了图中部分结构信息, 节点排序操作则使得后续卷积得到的图上重要结构可能是这种启发式排序规则下的重要结构, 而不是图分类任务所需要的重要结构.

对比这两类卷积方式, MPNN式的卷积假设相邻的节点标签相同, 因此采用了邻居信息传递机制, 这种机制从节点的角度出发, 更适合于图上节点级别的分类问题. CNN式卷积则具有发现关键结构的能力, 这对于生物化学信息学等领域的实际应用具有重要的意义, 但当前的CNN式卷积中也存在参数过多, 无法准确学习得到所有重要结构的问题. 到目前为止, 关于图分类中适合的卷积方式并无定论, 我们还不知道什么样的卷积方式可以最优地利用图中的结构信息帮助分类, 接下来仍然需要探索.

传统卷积网络中的池化也被称为下采样, 可以降低特征维度, 减少参数量并且扩大感受野. 作为欧式数据, 图像数据中不同像素点的结构统一, 因此传统卷积神经网络中的池化算子考虑结构信息时的方式会比较简单直观, 主要有最大池化、加和池化和均值池化等方法. 在图分类中, 池化操作主要是配合某些类型的卷积操作, 降低表示的维度, 得到整个图的表示. 不同于图像数据, 在图数据中, 每个节点的局部结构不同, 在对图数据节点表示进行池化时, 需要考虑每个节点不同的局部结构信息.

池化是图粗化的过程, 把相似的节点聚类在一起, 因此需要在图上定义有意义的邻居[55]. 池化一般包括两个步骤, 第1步求分配矩阵, 分配矩阵决定哪些邻居聚类在一起形成聚类簇. 分配矩阵 ${S^{(l)}} \in {R^{{n_l} \times {n_{l + 1}}}}$ 是第 $l$ 层节点分配到 $l + 1$ 层不同的聚类簇中的指示矩阵. 矩阵的行表示节点, 共有 ${n_l}$ 个. 列表示粗化后的聚类簇, 共有 ${n_{l + 1}}$ 个. 第2步按照分配矩阵进行聚合, 即选定聚类簇中节点的聚合方式并将每个聚类簇聚合为一个新的超节点, 所有的超节点构成新的图. 通常在最直接的聚合方式下, 新图的特征矩阵由 ${X^{(l + 1)}} = {S^{(l){\rm T}}}{X^{(l)}}$ 得到, 邻接矩阵由 ${A^{(l + 1)}} = {S^{(l){\rm T}}}{A^{(l)}}{S^{(l)}}$ 得到. 当然, 很多模型会提出新的更复杂的聚合方式[16]. 本小节将从分配矩阵的角度对图分类领域池化方法进行分类, 并对具体的分配和聚合方式进行介绍分析.

(1)节点硬分配与聚合

节点硬分配的方式是将图上的节点分为若干个无重叠的簇. 具体地, 硬分配矩阵是指从行的角度来说, 每一行有一个值为1, 其他值均为0的分配矩阵. 意味着每个节点属于且仅属于一个聚类簇. Ma等人[16]提出的谱池化(EigenPooling)利用谱聚类得到硬分配矩阵 ${S^{(l)}}$ , 并根据该矩阵进行子图划分. EigenPooling将整个图划分为一些没有重叠节点的子图(聚类簇), 并把每个子图当做一个超节点. 其中超节点之间的邻接矩阵通过 ${A^{(l + 1)}} = {S^{(l){\rm T}}}{A^{(l)}}{S^{(l)}}$ 得到. 子图中节点进行聚合时, EigenPooling并不是直接把分配矩阵 ${S^{(l)}}$ 当做池化算子, 而是将子图特征分解后得到的特征向量组合形成多个池化算子. 接着, 超节点的表示可以利用池化算子 ${\Theta _l}$ 通过 ${X_l} = \Theta _l^{\rm T}X$ 得到, 多个池化算子得到的多组超节点表示并进行拼接后, 得到最终的超节点表示. 从局域角度来看, 这样的池化过程是子图上图信号的傅里叶变换过程; 从全局的角度来看, 这样的池化算子相当于滤波器, 池化的过程就是对图上信号进行滤波, 这些池化算子保留了很好的性质, 如可以完好恢复图上信号, 最大程度保留图上信息. 图8展示了利用信息传递式的图卷积算子和EigenPooling的池化算子进行图分类的过程.

Wu等人[3]则认为度相同的节点可能有相似的结构信息, 为了保留度相关的节点结构信息, 他们提出了度特定的图神经网络模型(DEMO-Net). 该模型在池化过程中, 将度相同的节点聚合为一个新的超节点并采用了表示拼接的聚合方式, 也属于基于硬分配矩阵的池化. Diehl等人[56]提出的EdgePool通过学习边的分数来决定哪两个节点聚合在一起. 具体地, 在进行池化时, EdgePool先为边打分并排序, 然后选择分数最高的边将其两端的节点聚合在一起形成新的虚拟节点. EdgePool中没有显式给出分配矩阵, 但这个过程属于节点硬分配的池化. 此外, 值得注意的是, 一些简单的置换不变(permutation invariant)函数(例如加和池化、最大池化等), 也属于特殊的基于节点硬分配的池化方式.

基于节点硬分配的池化模型中, 在得到节点表示后, 一般按照图聚类[16]或者特定规则[3]将节点聚合为簇, 每个节点属于且仅属于一个簇. 这种池化方式得到的图表示很大程度上依赖于节点聚合规则, 在某些场景下, 可能存在节点聚合规则与分类任务适配不够好的情况, 从而影响图分类的效果.

(2)节点软分配与聚合

节点软分配的方式是将图上的节点分为若干个可能有重叠的簇, 也就是每个节点不仅属于一个簇. 具体地, 软分配矩阵是指从行的角度来看, 行中每个值的取值范围为 $0 \leqslant {p_{ij}} < 1$ , 表示节点 $i$ 以概率 ${p_{ij}}$ 属于第 $j$ 个簇. Ying等人[17]提出的可微分池化 (DiffPool)模型就是通过参数学习的方式得到软聚类分配矩阵 ${S^{(l)}}$ . 模型框架如图9所示. 模型中包含两个图神经网络, 一个嵌入图神经网络用来学习节点在 $l$ 层的表示:

另一个池化图神经网络用来学习软分配矩阵:

得到 $l$ 层的节点表示和软分配矩阵后, 通过 ${X^{(l + 1)}} = {S^{(l){\rm T}}}{X^{(l)}}$ 和 ${A^{(l + 1)}} = {S^{(l){\rm T}}}{A^{(l)}}{S^{(l)}}$ 分别得到粗化图的节点表示和邻接矩阵. 该模型通过学习的方式得到软分配矩阵, 仅使用图分类任务返回的梯度信号很难训练好可微分池化图神经网络, 因此很难学习到好的软分配矩阵. 为了克服这个问题, 该模型在训练过程中加入了一个辅助的链路预测任务, 假设邻近节点应该被池化在一起. 此外, 为确保每个聚类簇中的元素是确定的, 该模型还对学得的软分配矩阵进行限制, 使得每一行尽量靠近one-hot向量(每行只有一个1, 其他都是0的向量). 可微分池化模型第一次提出通过学习的方式利用结构信息和特征信息得到分配矩阵, 但实际应用中学习到好的分配矩阵难度较大, 且由于软分配矩阵比较稠密, 导致模型计算复杂度较高.

DiffPool的目标是学习得到一个软分配矩阵进行图分类, 不同于此, Amir等人[18]提出了基于记忆层的图神经网络, 目标是通过学习的方式得到多种分配方式, 然后利用卷积将多个分配矩阵聚合为一个最终的分配矩阵用于池化. 这种学习多个分配矩阵的方式有效地提升了模型能力, 取得了较好的分类效果.

对比前文介绍的基于节点硬分配的池化方法, 基于节点软分配的池化不要求每个节点唯一的属于一个簇, 这种宽松的限制更符合实际场景中的情况, 每个节点可能同时在多个簇中扮演角色. 此外, 在目前的基于节点软分配的池化方法中, 通常都采用了学习的方式来得到分配矩阵[17, 18], 通过端到端优化在任务依赖的场景中取得了较好的效果.

(3)节点选择与聚合

基于节点选择的池化方法是指从图中选择一些节点来代表整个图, 其中被选出的每个节点都代表一个簇. 一般来说, 节点选择型分配矩阵在每一列中有一个值为1, 其他均为0. 也就是在 ${n_l}$ 个节点中选择 ${n_{l + 1}}$ 个节点作为粗化后图节点. 这类方法的核心在于设计一种为节点打分和选择节点的方式. Lee等人[19]首先提出了基于自我注意力的池化(SAGPool)模型, 该模型在进行池化时, 同时考虑了节点特征和图拓扑信息. 具体地, SAGPool利用图卷积网络为每个节点学得一个自注意力分数, 这个分数表示节点在图中的重要性:

其中, $Z \in {R^{N \times 1}}$ , $\widetilde A$ 的定义和GCN中相同, ${\Theta _{att}} \in {R^{F \times 1}}$ 是SAGPool模型中唯一的参数. 得到节点重要性分数后降序排列, 按照排序结果保留一定比例的重要节点, 当作粗化图的节点:

其中, top-rank函数返回值最大的 $\left\lceil {kN} \right\rceil $ 个节点的标号 $idx$ , 在进行池化时, 保留被选择的重要节点的节点特征和它们之间的连接方式:

其中, ${X_{\rm{out}}}$ 和 ${A_{\rm{out}}}$ 是池化后图的节点特征矩阵和邻接矩阵. 图10给出SAGPool的结构示意图[19].

Gao等人[49]提出了GraphU-Net模型. 借鉴图像中的U-Net模型思想, 该模型包括图上的池化算子gPool和上采样算子gUnpool. 其中, 池化算子gPool也采用了节点选择的方式进行, 与SAGPool的主要不同在于节点的选择策略. 具体地, 该模型利用一个可训练的映射向量 $p$ , 把所有的节点特征映射到一个1维标量, 这个标量大小代表节点中可以保留下来的信息的多少. 为了尽可能多地保留原图中的信息, 模型选择了那些标量值较大的对应节点来组成新图. 计算过程如下:

其中, $y$ 向量的值表示每个节点在 $p$ 上可以保留的信息多少. $\widetilde y$ 中提取出了被选择节点中可以保留信息比例的值. $idx$ 表示被选择出的节点标号. 选出节点后, 用类似SAGPool的方式, 保留被选择节点的连接方式作为新图的邻接矩阵, 并按照比例保留节点特征作为新图的特征矩阵. Cangea等人[57]也利用了GraphU-Net的节点选择策略进行图池化. Ranjan等人[58]为了解决: (1) DiffPool不能应用于大图; (2) GraphU-Net等池化方法对结构信息的利用不够充分的问题, 提出了自适应的结构感知池化方法(ASAP), 该方法先将每个节点当做聚类中心进行局部聚类形成簇, 然后提出一种卷积方法对这些簇打分并排序, 选择分数最高的 $\left\lceil {kN} \right\rceil $ 个簇形成池化后的图. 实际上节点聚类形成簇的过程中, 簇的个数等于节点个数, 簇的表示相当于加入邻居信息的节点表示. 因此, 整体上来看, ASAP的池化过程属于基于节点选择的池化.

这些基于节点选择的图池化方法中存在一些问题: 第一, 节点选择策略的角度单一, 缺少目标性; 第二, 未被选中的节点特征直接被丢弃, 特征信息未利用充分. 针对这些问题, Zhang等人[59]提出了一种基于结构和特征的图自适应池化方法. 该方法提出了新的节点选择策略, 包括两个分别从结构, 特征方面对节点的重要性进行排序的模块和一个综合结构和特征信息的排序模块. 除此之外, 该模型在节点选择之前, 对所有节点信息进行聚合, 使得池化后的图中节点不仅包含被选中的节点信息, 也包含被丢弃节点的信息. 这个模型在一些生物数据集上取得了较好的分类效果. 不同于其他方法, Zhang等人[60]提出的结构学习的层次图池化方法中, 给出了意义明确的节点选择策略, 他们认为, 当一个节点可以由它的邻居节点们计算得到时, 意味着该节点在池化图中可以被删掉, 并且不会带来信息损失. 这个非参的池化算子在多个图分类数据集上取得了较好的分类效果, 证明了这种节点选择策略的有效性.

在目前的分类体系中, 我们将池化方法分成了基于节点硬分配, 基于节点软分配和基于节点选择的池化. 但从另一个角度来看, 本文中提到的所有图上的池化方法又可以分为两类, 一类是全局池化, 得到节点表示后, 做一次池化得到整个图的表示, 如DGCNN[4]. 另一类是层次池化, 在每个卷积层后面, 进行不同规模的池化以缩小图的尺寸, 最终得到整个图的表示, 如DiffPool[17], SAGPool[19]. 由于卷积中节点沿着图的边进行信息传递, 得到的节点表示是平的, 通过层次池化, 可以得到层次化的图的表示. 层次池化方法的效果在很多模型中得到了验证[16-18]. 表3对当前基于图神经网络的图分类方法进行总结和对比.

为了便于对图分类方法的效果进行对比分析, 本节首先介绍图分类领域常用数据集和评价指标, 然后对一些代表性图分类方法的实验结果进行对比分析.

目前图分类领域常用的数据集主要包括用于二分类/多分类的生物蛋白质数据集, 化学化合物数据集和社交网络类数据集, 以及用于多标签图分类的气味数据集. 数据集相关统计信息见表4.

化学化合物数据集中, 通常每个图表示一个化合物, 图中节点表示原子, 边表示原子之间真实存在的化学键.

(1) MUTAG数据集[61]由188个化学化合物结构图组成, 根据它们对细菌的诱变作用分为2个类别. 图中的节点表示原子, 节点标签表示原子种类, 包括C, N, O, F, I, Cl, Br. 边表示化学键, 边标签包括芳香键, 单键, 双键和三键.

(2) Mutagencity[62]是诱变剂化合物数据集, 图的标签分为诱变和非诱变2类. 图中节点表示原子, 节点标签表示原子种类, 包括C, O, Cl, H, N, F, Br, S, P, I, Na, K, Li, Ca. 有3个种类的边分别表示不同化学键.

(3) NCI1[63]是对非小细胞肺癌活性筛选的化合物数据集, 图的标签分为2类, 表示具有/不具有抗癌活性. 共包含4110个化合物图.

(4) NCI109[63]是对非小细胞卵巢癌活性筛选的化合物数据集, 图的标签分为2类, 表示具有/不具有抗癌活性. 包含4127个化合物图.

生物蛋白质数据集中, 通常每个图表示一个蛋白质的高级结构, 图中的节点表示一个氨基酸分子, 边表示氨基酸分子之间的结构邻近性, 当氨基酸之间距离小于某个阈值时, 节点之间有边存在.

(1) ENZYMES[64]是一个蛋白质三级结构数据集, 共包含600个酶, 每个图表示一个蛋白质结构, 图标签是6种酶的等级类别.

(2) PROTEINS数据集[64]中的1113个图表示蛋白质, 图的标签分为2类, 表示酶或者非酶. 节点是蛋白质的二级结构, 如果二级结构在氨基酸序列或者蛋白质三维空间中是邻居, 那么节点之间有边存在.

(3) D & D数据集 [65]由1178个蛋白质结构图组成, 图的标签分为2类, 表示酶或者非酶. 节点表示氨基酸, 如果两个节点间隔小于6埃, 它们之间有边存在.

社交网络数据集中, 一般每个图表示对象之间的互动关系, 节点表示一个对象, 边表示对象之间存在某种互动.

(1) COLLAB[39]是一个科学合作数据集, 包括从高能物理, 凝聚态物理, 和天文物理3个领域中生成的不同研究人员的自我中心网络图(Ego-network), 对应的标签是研究人员所属的研究领域. 分类的任务是判断这些自我中心网络图对应研究人员的研究领域.

(2) REDDIT-BINARY数据集[39]中包含2000个Reddit网站上用户的社交互动图, 每个图表示一个在线讨论线程, 节点表示用户, 如果两个用户之间有过消息回应, 则他们对应的节点之间有边相连. 这些互动图包括基于问题-答案互动图和讨论互动图2类, 图分类的任务就是判断给定社交图是来自基于问答的社区还是基于讨论的社区. 另外, REDDIT-MULTI-5K, REDDIT-MULTI-12K均是该数据集的更大的变体, 包含更多的来自不同社区的互动图, 任务也是将互动图分类到对应社区.

(3) IMDB-BINARY[39]是一个电影合作数据集, 数据来自于互联网电影数据库(IMDB). 每个图中节点表示演员, 如果两个演员出现在同一部电影中, 则他们对应的节点之间会有一条边. 这些合作图均来自动作和浪漫这2种类型, 在合作图中为每个演员衍生出自我中心网络图, 图分类的任务就是判断给定的自我中心网络图属于动作类型还是浪漫类型. 另外IMDB-MULTI是该数据集的多类型版本, 任务也是将演员子网络图分类到对应的电影类型.

气味数据集中, 一般每个图有多个标签, 属于多标签分类问题. 具体来说, 在计算机嗅觉中的气味数据集GoodScents[66]、Leffingwell PMP 2001[67]和Flavornet[68]中, 每个图表示一个化学分子, 节点表示原子, 边表示化学键, 图的标签表示该分子的一种或多种气味属性. 其中, GoodScents数据集[66]、Leffingwell PMP 2001数据集[67]和Flavornet数据集[68]中分别包含3786、3561、738个分子, 每个分子由嗅觉专家使用1个或多个气味描述符对分子进行标记, 也就是分子的多个类别标签. 分类任务是预测每个气味分子所具有的所有类别标签.

图分类方法的评价指标主要包括分类准确率, 精准率, 召回率, F1值和AUC, 下面分别介绍.

(1)分类准确率(Accuracy), 衡量了被正确分类的图在所有图中的占比.

(2)精准率(Precision), 衡量预测为正例的样本中, 真正的正例样本的比例.

(3)召回率(Recall), 衡量所有样本中的正例, 被正确预测出来的比例.

(4) F1值是精准率和召回率的调和平均数, 用来衡量当样本类别不均衡时的分类器性能.

(5) AUC (the area under the receiver operating characteristic). ROC (receiver operating characteristic)曲线用来衡量当分类阈值变化时, 分类器系统的判别能力. ROC曲线对样本是否平衡不敏感, 适用于样本类别不均衡时对分类器性能的评价. 而AUC指的是ROC曲线下的面积, 取值一般在0.5到1之间. 分类器的AUC等于将随机选择的正例排在随机选择的负例前面的概率[69].

由于本文提到的图匹配方法没有显式地进行图分类任务, 本小节只给出图核方法和图神经网络方法在图分类上的实验结果, 表5是部分具有代表性的图核方法在生物化学数据集和社交网络数据集上的分类结果. WL子树核方法在超过一半的数据集上取得了最高的分类准确率. 对于深度图核, 这里对比的是深度最短路径图核方法(deep SP graph kernel). 与最短路径图核方法相比, 取得了更好或者类似的结果. 此外, Graphlet图核方法在社交网络数据集REDDIT-B上取得了最好的分类结果. 对于在具体情境下对图核方法的选用需要理解其特点. 相比随机游走核, 最短路径核方法更适合出现路径回溯情况的场景中; 而当图的规模比较大或者复杂时, 更适合用基于子图和子树的图核方法. 但需要注意的是, 使用基于子图和子树的两类图核时需要确保语义信息不会在整个图上传播, 也就是, 这两类方法不适合图上距离较远的点之间有较大的语义重要性的情境[70]. 此外, 深度图核可以用于需要缓解核矩阵对角控制问题的场景.

由于当前基于图表示学习的图分类模型的实验设置和数据划分不同, 我们很难直接横向比较各个方法. 表6给出了部分具有代表性方法在统一的实验设置下的分类结果. 这些方法中模型都经过严格的模型评估和模型选择的过程, 模型的输入特征和数据划分都统一公平, 采用十折交叉检验的方式进行实验, 实验结果均可复现[23].

从表6可以看到, 在严格十折交叉验证、相同的实验场景下, GIN[24]在多数图分类数据集上取得了最好的效果, 在基于邻居信息传递的图卷积方法中, GIN的表达能力最接近WL算法. 实验表明GIN在获取图表示时, 使用加和池化的方式可以比平均池化及最大池化更好的捕获结构信息. DGCNN[4]和DiffPool[17]分别在D & D蛋白质数据集和PROTEINS蛋白质数据集上取得了最好的分类准确率. 但在实验中, DiffPool不容易优化, 需要一些辅助任务来帮助训练, 如链路预测. 此外, DiffPool学习得到的分配矩阵比较稠密, 在实验中存在超出内存的风险. 对于GraphSAGE方法 [71], 由于原文中并没有进行图分类任务, 这里的对比实验中采用的是最大池化的全局聚合方法得到图表示, 分类准确率低于那些专门为图分类设计的模型. 虽然现有的图神经网络模型在图分类任务上取得了不错的效果, 但Errica等人[23]在实验中发现, 当前这些基于图神经网络的分类方法对结构的利用仍不充分. 而在生物化学领域, 结构信息与某些分子属性类别紧密相关, 未来仍需更进一步探究图神经网络模型对图结构信息的利用.

图分类不仅在实验中取得了较好的结果, 而且在生物化学领域, 网络分析领域, 计算机安全等领域有着非常重要的应用和广阔的前景. 本节给出图分类的已有应用场景和一些未来可能的研究方向.

(1)化学信息学、生物信息学

传统的图分类主要应用于生物和化学领域. 它们天然地提供了很多图结构数据. 通过实验判断分子属性或蛋白质功能的方式代价较大, 因此机器学习的方法被广泛应用于生物化学信息学中. 在化学信息学中, 化合物被建模为图, 该领域常见的问题是判断化合物是否具有某些性质. 图分类方法已经被用于判断分子是否具有诱变性、抗癌活性、毒性等任务中[6, 7]. 图分类在药物开发领域, 也有着非常重要的应用, 通过图机器学习的方法对药物的安全性等性质进行判断, 同时帮助化学家深入理解不断增长的药物发现数据[72]. 此外, 在多标签图分类场景下, 图分类方法也被用于计算机嗅觉领域中定量结构气味关系(QSOR)建模问题. 此时, 分子有一个或多个气味属性标签, 任务是预测分子的气味属性标签[20, 68].

同样的, 在生物信息学领域, 对蛋白质的探索[9]也是一项重要任务. 蛋白质的高级结构被建模为图. 常见的应用包括蛋白质属性判断, 如蛋白质是酶或者非酶, 通过蛋白质交互网络预测疾病[8]等.

(2)社交网络分析

在社交网络分析领域, 最常见的数据之一是引用网络, 如第4.1节中描述的COLLAB数据集. 数据集中的图是研究人员的自我中心网络图, 也就是以研究人员为中心的引用关系图. 该场景下常见的分类任务是给定训练集中自我网络图的类别标签, 模型经训练后对测试集中自我网络图的类别进行判断.

(3)计算机安全

图分类常被应用于计算机安全领域，例如软件剽窃的检测、恶意软件检测、软件漏洞检测[73-75]等重要安全问题. 该场景下的图一般是经过一些转化方式得到的控制图, 通过控制图结构判断是否存在安全问题. 如在漏洞检测中, 当无权访问源代码时, 我们需要分析二进制文件, 结合反汇编程序和代码分析器, 提取代码的控制流图. 控制流图以结构化的形式包含二进制函数中所有信息[43]. 控制流图中的节点表示汇编指令的基本块, 当两个基本块之间有跳转, 循环或者返回等控制流时, 对应节点之间有边, 图标签是有无漏洞. 当前, 主要是基于图相似度计算的图分类方法应用于计算机安全领域, 这些方法的假设是, 当未知控制流图的结构和已知有漏洞的控制流图相似度较高时, 判断该未知程序可能存在漏洞.

(4)自然语言处理

图分类的方法应用于自然语言处理的第一步就是图的构建. 一种常见的方法是构建文本的单词共现图[76-78], 节点表示单词等有意义的语言实体, 边表示在固定大小的滑动窗口中的共现关系. 与传统的词袋表示文本的方法相比, 图不仅建模了单词等实体, 也对他们之间的远距离依赖关系进行了建模. 图分类的方法在自然语言处理领域已经被应用于文档相似性计算, 文本分类的重要任务中. 例如, Nikolentzos等人[77]用共现的方式将文档构建为无向无权图, 然后利用最短路径核计算文档的相似性, 取得了较好的效果. Peng等人[76]将文档构建为词共现图, 然后用对单词图进行图卷积操作, 提取单词图特征进而对文档进行分类, 相比于传统的文本分类方法, 该模型取得了较大的提升.

(5)计算机视觉

有些基于图核和基于图神经网络的方法被用于计算机视觉领域的图像分类, 语义分割, 点云图的形状分类等应用中[79-82]. 为了进行人体活动识别, Wu等人[79]首先构建了2个图模型建模人体活动的空间特征和时序关系, 然后提出了上下文相关的图核来衡量图之间的相似性, 进而对人体活动进行识别. Wang等人[80]在点云图上使用边卷积的方式提取几何特征, 然后利用全局池化的方式得到整个图的表示进而进行形状分类任务, 取得了较好的效果.

虽然图分类问题已有很长的研究历史, 并在近年取得了较大的进步. 但该领域仍然有很多需要注意的问题和值得继续探索的研究方向.

(1)图分类中图结构信息的充分利用

图中的结构信息, 即图上节点的连接信息, 如一阶连接信息, 二阶信息和其他高阶信息等, 对于图分类有着非常重要的作用, 例如生物信息数据集中, 某些结构模式与分子功能属性有着必然的联系. 但当前图分类领域中很多基于图神经网络的方法并没有有效地利用到图结构信息[23], 例如, 在基于信息传递的图神经网络中, 节点之间的连接关系仅用来指导节点之间的信息传递, 并没有直接对结构信息建模. 对于在图分类中如何更好地利用结构信息和判断模型对结构的利用程度上, 我们并无定论. 对于图结构信息的合理利用和对结构利用程度的表示是图分类领域重要的研究方向.

(2)图分类方法的可解释性

基于图神经网络的图分类方法的提出, 使得图的表示和分类过程可以统一地进行优化, 取得了较好的分类效果. 但是, 这类模型通常比较复杂且不够透明, 人类无法直观地理解它们的预测结果. 对图分类模型的预测能力进行直观解释, 探索这些模型中各个组件对图分类的作用不仅可以增加我们对GNN模型的信任, 促进GNN模型应用于涉及到公平, 隐私和安全的领域中, 也可以增进研究人员对于网络特征的理解, 进一步提升模型效果[27, 83]. 对图卷积神经网络的可解释性已有一些初步的尝试[24, 83], 但当它们应用于图分类问题时的可解释性, 仍然值得进一步探索.

(3)图分类模型表达能力的衡量

当前图分类模型主要是基于图神经网络的模型. 一方面, 基于图神经网络模型的表达能力都是用判断图是否同构的能力来衡量的[24, 51]. 但我们并不能保证在这样的衡量标准下, 对图是否同构的区分能力在图分类任务中可以泛化得好[27]. 在图分类问题中, 模型表达能力的衡量方法是一个重要的需要考虑的问题. 另一方面, 由于基于神经网络的模型依赖于充足数据, 需要通过大量的数据进行训练. 而当前图分类领域的常见数据集通常规模较小, 不能很好地体现出方法的优势, 限制了基于图神经网络的模型的表示能力. 构建更好的图分类数据集成为亟待解决的问题.

(4)图分类新技术

虽然已经有很多经典的图神经网络方法在图分类任务上取得了较好的效果, 但仍面临着标签数据获取昂贵、模型迁移能力不足等诸多挑战, 需要通过合理引入新技术来解决. 具体来说, 一方面, 图神经网络的训练过程需要大量的任务相关的标签数据, 标签数据的获取代价高昂[84]. 另一方面, 实际中, 有时我们需要具有迁移能力的模型应用于不同的场景中. 类比于自然语言处理和图像处理领域, 图上也可以通过先在数据丰富的任务上对模型预训练, 然后在目标任务上进行微调来解决这些问题. 目前已有一些图上预训练的初步尝试[84-86], 未来图上的预训练仍是值得探索的问题. 此外, 当前图分类主要关注同质图, 而实际场景中有很多异质图存在, 已有的关于异质图的研究主要集中在节点分类问题[87, 88]上, 未来, 关于异质图的分类也是值得关注的方向.

(5)实验可复现性和学术社区的健康发展

在机器学习领域, 实验的可复现一直是一个非常关键的议题[23]. 当前用图神经网络处理图分类的工作中, 实验程序通常不够严格且很难复现. 不同方法中的实验设置也不尽相同, 使得我们很难横向的对不同方法进行比较. Errica等人[23]对5个图分类模型在统一的评估框架下做了对比. 同样的数据划分和实验设置条件下, 用10折交叉验证的方法进行模型的评估和选择, 保证了实验的公平性. 未来图分类领域的工作, 应该延续这种做法, 详细地给出方法的实验设置, 方便公平对比和对问题的深入理解, 推进图分类学术社区的健康发展.

图分类问题不仅是很多研究领域的基础问题, 而且有着广泛的应用, 具有重要的研究价值. 本文总结了近年来图分类领域的进展. 将现有图分类的方法分为基于相似度计算的图分类和基于神经网络的图分类两大类. 第2节对基于图相似度计算的图分类方法进行梳理, 这类方法又包括图核方法和图匹配方法. 传统图核方法中特征表示和分类的过程分别进行, 存在无法根据任务进行优化, 且计算复杂度较高的问题. 而图匹配方法也不仅仅面向图分类任务. 最近几年, 随着神经网络在图领域的成功应用, 越来越多的基于图神经网络的方法被应用于图分类问题中并取得了较好的效果. 因此, 第3节对基于图神经网络的图分类方法进行总结和分析. 此外本文还总结了图分类的重要应用场景并讨论了存在的问题和未来可能的研究方向. 总的来说, 本文对近年来图分类领域的研究进行综述, 充分总结了已有方法并指出了存在的问题, 希望为进一步的研究提供一定的指导和帮助.