面向电力边缘数据分析的图分类算法研究进展

许爱东，胡志伟，蒋屹新，张宇南，吴涛

（1.南方电网技术研究院有限责任公司，广州510670；2.重庆邮电大学通信与信息工程学院，重庆400065；3.重庆邮电大学网络空间安全与信息法学院，重庆400065）

0 引言

随着图数据在物联网、智能电网等信息领域地标产生与广泛存在，图分类成为图数据分析的关键问题之一。图分类是一种试图将整个图用正标签或负签来标注的有监督学习问题。这也是最早将机器学习和数据挖掘技术应用于图数据的任务。

在智能电网领域，随着电力系统信息化水平的不断提高和配用电相关数据量的广泛采集，各类边缘装置都积累了大量的数据亟待处理与利用。电网中普遍存在通信故障、设备故障、电网波动以及用户异常用电行为等事件，它们都可以通过监控数据进行捕获。对于设备故障及异常用电的检测，早期普遍采用的是现场检测方法。随着人工智能的发展，人们致力于寻求基于监控数据分析对电网故障和异常用电行为进行高效的发现、预防和处理。

图作为复杂数据的代表性表达形式，许多学者对图数据分类问题已经做了大量的研究。在生物信息[1]、恶意软件检测[2]、文本分类[3]等领域，图分类已经得到了广泛的应用。为了介绍现有图分类方法，促进智能电网领域边缘数据分析技术的发展，本文对图分类相关方法进行归纳与总结。

1 概述

分类是数据分析领域中的一个基本问题，是一种有监督的机器学习方法。其目的是从一组已知类别的数据中发现分类模型，以预测出新的数据未知类别。然而，现在的数据存储一般都是采用关系数据库或图，所以出现了图分类方法的研究。

图是表示系统中实体的节点以及实体之间关系的连边的集合。图数据是以图为对象形式的表示。图分类是图数据分析中的一个重要研究分支，在物联网、智能电网等信息领域有广泛的应用。目前，图分类问题主要研究二分类问题（正类和负类）。即已知训练图集和测试图集，图分类的目标是构建一个分类模型，把两者区分开。

本文根据基础模型的不同，将现有图分类的方法归纳为四类，分别是嵌入方法、基于图的特征挖掘方法、核函数方法和深度学习方法，如图1 所示。

图1 图分类的总框架

2 嵌入方法

本小节介绍基于嵌入方法的图分类模型，并对这些模型进行比较分析。嵌入方法[4-5]为每个图导出固定数量的特征，用作分类的矢量表示。嵌入方法的优点是能够兼容任何机器学习分类器。

2.1 算法模型

文献[6]提出一种基于嵌入表示的图分类方法。该方法采用基于类别信息的特征子图选择策略，不但考虑了子图的结构信息，而且在频繁子图挖掘过程中充分利用直接选择特征子图以及生成分类规则。

针对大型图的嵌入，文献[7]提出了学习图卷积层（Learning Graph Convolutional Layer，LGCL）的模型框架，对于每个特征维，LGCL 方法中的每个节点都会从其邻近的具有值排序的节点中选择一定数量的特征。如图2 所示，图中的每个节点都有一个维数特征向量n=3。对于目标节点（3，7，8），它的六个邻居的第一个特性组件的值为9，6，5，3，0，0。如果我们把窗口大小设为k=4，然后是选中左边四个最大的值（即9，6，5，3）。同样的过程在剩下的两个有限元中重复。通过包含目标节点本身的特征向量，得到维数（k+1）×n 的数据矩阵。为了嵌入大规模图，采用子图选择方法来减少内存和资源需求。文献[8]提出了图划分神经网络（Graph Partition Neural Networks，GPNN）的模型框架，GPNN 扩展了图神经网络（Graph Neural Networks，GNNs）来嵌入超大图，它在局部（节点间的支撑信息）和全局信息传播（子图间的消息）之间交替进行，这种调度方法可以避免序列调度所需的深度计算图。文献[9]提出了LINE 模型框架，LINE 模型用于嵌入任意类型的图，如无向图、有向图和加权图。它利用正则抽样来降低优化复杂度。这三个模型框架均解决了可扩展性的问题。

图2 可学习的图卷积层方法[7]

2.2 小结

文献[6]巧妙地将嵌入方法与频繁子图特征挖掘相结合的形式进行图分类，性能较好。这一做法为嵌入方法与频繁子图特征挖掘提供了新的思路。

3 基于图的特征挖掘方法

在本节中，本文介绍了有关基于图的特征挖掘的图分类模型，并对这些模型进行分析。图的特征挖掘使用了类似于子图发现的方法，因为图的特征挖掘的一般做法是在图实例中寻找所有频繁或者有意义的子图。这些子结构被用于将图数据表示成一个单表的数据表示，然后传统的分类算法可以将图实例进行分类。

3.1 算法模型

传统的特征滤波方法不依赖于任何分类器来选择特征。与选择冗余特征的滤波方法相比，包装器方法通过子集空间搜索，利用分类器对特征子集的分类能力进行评估，识别出最优子集[10]，从而识别出高信息量的特征。最大边际特征选择[11]是一种包装方法。在该方法中，它利用信息增益来衡量每个特征与类标签之间的相关性，然后选择冗余较少的特征，覆盖新的训练样本。

文献[12]提出了一个多任务图分类问题，其中多个图分类任务被联合规则化，以找到所有学习任务共享的判别子图。文献[13]提出了一种高效的图特征选择方法，该方法使用频繁子图作为图分类的特征。两者都是通过子图特征的形式探索图分类的性能。

为了对图进行学习表示，需要一种既具有一定独特性和稳定性又能快速计算图特征表示。文献[14]发现了图的谱距离簇及其基于图的特征表示。通过将其应用于图分类问题，评估出图的普距离簇生成的图特征的质量以及其实用性。为了建立更高精度的图分类模型，文献[15]提出了一种新的网络分类方法，它独立于网络大小，并采用无对齐的网络比较度量。该方法是基于监督机器学习算法并且利用网络的拓扑相似性来进行分类任务。

文献[16]提出了一种基于特征的网络分类方法。通过建立网络动力学模型，计算多个时间尺度下不同网络属性的协方差，并定义了广义分类特征。文献[17]提出了一种基于图的多尺度时间序列表示方法和一种特征提取方法。图的多尺度时间序列表示方法将时间序列转换为不同尺度的可见性图集合，通过研究小序列的概率分布、分类性和程度统计等统计图特征，并进行特征提取，然后利用这些特征通过泛型分类器建立高精度的分类模型。

3.2 小结

在图数据分类中，最直接的方法是基于频繁子图特征挖掘的算法进行分类，而该方法的缺点是利用挖掘算法产生的频繁子图的数目巨大，甚至达到指数级，计算量大。

4 核函数方法

在本节中，本文介绍了有关核函数的图分类模型，并对这些模型进行分析。寻找频繁子图在计算上是不可行的，一个替代算法使用了核方法。文献[18]和文献[19]基于在图上的游走度量来描述图核函数。文献[19]计数起点和终点有相同标签的游走。文献[19]则考虑了有着相同标签序列的随机游走的概率。文献[20]综述了结构数据中的核方法。

4.1 算法模型

近年来，各种图核函数被提出。在文献[21]和文献[22]中，提出了基于随机游动的图核，计算了两种图共有的游动数。从那时起，随机游动核得到深入的研究，如文献[23-26]。在文献[27]中，首先提出了基于树模式的核函数。这两种方法最初应用于带有离散标签的图。基于最短路径[28]的内核是通过对转换后的输入图执行1 步遍历来计算的，其中边用最短路径长度标注。上述方法的一个缺点是计算成本高。

为使用经典的集成学习框架在流上实现大规模图分类，这就要求不同块中的数据位于同一个特征空间中，为此，文献[29]提出了一种嵌套子树哈希（Nested Subtree Hashes，NSH）算法及其派生的NSH 核函数，通过递归方式将不同块的多分辨率子树模式投影到一组常见的低维特征空间上，其中NSH 核函数可以在流上支持大规模的图分类。

一般来说，最优赋值会产生不定函数，这使得其在内核方法中的使用变得复杂。文献[30]提出了一类基核用于保证正半定最优分配核的方法。这些基核通过直方图相交在线性时间内计算最优分配核形成层次结构。虽然计算简化的直方图相交，类似于金字塔匹配内核[31]，但文献[30]提出的方法并不局限于特定的对象。通过基于最优赋值推导出新的图核，而这些图核比基于卷积的图核有了更大改进。

文献[32]提出了采用众所周知的图上消息传递机制的图内核设计的一般框架。该框架的主要思想是使用迭代过程隐式地更新顶点的表示形式。由于该框架采用了复杂的置换不变内核函数，该框架比神经消息传递体系结构更具表现力。

4.2 小结

文献[28]提出的方法在分类的实验中表现明显优于基于随机游动的内核。对于大规模的图数据分类，文献[29]与文献[30]所提出的方法都有非常好的表现。

5 深度学习方法

在本节中，本文介绍了有关深度学习的图分类模型，并对这些模型进行分析。本节从基本方法和池化方法两方面进行叙述图分类的模型。

5.1 基本方法

本小节主要介绍的基本方法是运用神经网络的方法将图数据进行分类，接下来主要介绍卷积神经网络、门控图神经网络、图胶囊网络和胶囊图神经网络四个模型。

（1）算法模型

图片是排列成网格形状，因此，图片可以直接运用卷积操作。但是对于图数据来说，需要一个从图到向量的映射的一个预处理过程。文献[33]提出一种方法可以基于任意的图结构的卷积神经网络。该方法通过从图中选择一个固定长度的节点序列，并对序列中的每个节点收集固定大小的邻居集合，最后对由当前节点及其对应的邻居构成的子图进行规范化，作为卷积结构的输入三步构建卷积分片，并利用卷积结构分别对每个分片进行操作。

在文献[34]关于图神经网络的研究基础上，文献[35]研究了图形结构输入的特征学习技术，并提出一种新的模型门控图神经网络（Gating Graph Neural Networks，GGNNs），该模型采用门控递归单元作为递归函数[36]，将递归次数减少到一定的步长。与图神经网络不同，GGNNs 使用时间反向传播来学习参数，它不再需要约束参数来保证收敛性。

文献[37]利用文献[38]提出的胶囊概念，提出了一种新的基于基本胶囊思想的图胶囊网络模型，解决了现有图卷积神经网络（Graph Convolutional Neural Network，GCNN）模型无法获取更多局部结构信息的问题。而文献[39]受到文献[40]提出的胶囊网络的启发，提出胶囊图神经网络。它采用了胶囊的概念来解决现有基于图神经网络的图嵌入算法的不足。通过以胶囊的形式抓取节点的特征，利用路由机制来捕获图级别的重要信息。

（2）小结

文献[33]提出的方法在多个数据集上优于图内核方法，美中不足的是容易在较小的数据集上过度拟合。对于大规模的图数据，文献[35]提出的门控图神经网络的缺点是需要在所有节点上多次运行递归函数，从而重新查询要存储在内存中的所有节点的中间状态，将会增加运算量。

5.2 池化方法

本小节主要介绍运用图卷积神经网络的方法将图数据分类，图卷积神经网络中的池化层在不断的改进中，表现效果不断提升。接下来主要叙述了可微图池模块、自注意力机制图池、图的傅里叶变换的特征池的卷积网络和关系池四个模型。

（1）算法模型

目前的图神经网络方法本质上是扁平的，并且不能学习图的层次表示，这一限制对于图分类任务来说尤其成问题，其目标是预测与整个图相关的标签。在此，文献[41]提出了一个可微图池模块。该模型可以生成图的层次表示，并且可以以端到端的方式与各种图神经网络结构相结合。受自注意机制的影响，文献[42]提出了一种基于自注意力机制的图池化。该方法可以使用相对较少的参数以端到端方式学习分层的语句表示。利用自我注意机制来区分应该删除的节点和应该保留的节点，并考虑了节点特征和图的拓扑结构。

在传统的卷积神经网络（Convolutional Neural Network，CNN）中，层次化学习图表示类似于池化步骤。然而，局部结构信息在汇聚过程中很大程度上仍然被忽略。文献[43]提出了一种基于图的傅里叶变换的特征池的卷积网络，它能充分利用池过程中的节点特征和局部结构。然后基于池操作符设计池层，并与传统的图卷积网络的卷积层相结合，形成一个用于图分类的图神经网络框架。文献[44]提出了用于图分类和回归的关系池（RP）框架。该框架借鉴了有限部分交换性理论，为图提供了一个具有最大表示能力的框架。

（2）小结

池化层之所以设计在卷积层后面，目的是通过池化来降低卷积层输出的特征向量，同时改善结果达到不易出现过拟合现象。

6 归纳与探索

在本节中，我们先总结出文献中经常使用的基准数据集。然后，我们介绍了常用数据集的基准性能，并列出了图分类的可用开源实现代码。

如表1 所示，在各数据集中列举了每个数据集的图的个数、特征数以及标签数，并统计了数据集在文献中出现的频率。这些数据集大多是化学、生物图数据集，如NCI-1、NCI-109、MUTAG、D&D 和ENZY-MES[45]五个数据集。在表1 中列出的数据集是常用的数据集。

表1 图分类中的常用数据集

在表2 中，我们提供了前面所述的图分类模型的开放源代码的超链接。值得注意的是，文献[46]在Py-Torch 中发布了一个名为PyTorch Geometric 的几何学习库，实现了多个图神经网络用于图分类的任务。

文献[47]提出了基于神经网络的异常用电检测模型，利用有监督的多隐藏层的神经网络算法，对大量用户数据进行模型训练，可用于自动检测用户用电量是否正常，根据检测结果区分出异常用户。该模型通过逐层初始化解决了深度神经网络在训练上的难度。该方法为电力公司减少成本，提高了查处异常用电情况的效率。

表2 图分类的开源代码

文献[48]提出了一种将时间序列转化为网络结构的可视化图算法，该算法以柱状图的形式进行构图，进而将时序数据表示成图数据，受此启发，我们将电力数据表示成图数据进行处理。受文献[45]的启发，我们将运用图神经网络中的分类方法对由电力数据表示成的图数据进行分析，试图区分出电力数据中的异常用电情况。在接下来的研究中，我们尝试把图分类任务应用到电力系统中。针对电力系统中出现用户的正常用电与异常用电运用图神经网络中的图卷积池化方法进行分类筛选出异常用电的情况。

7 结语

在本文中，我们对图分类进行了全面的概述。根据基础模型的不同，将现有图分类的方法归纳为四类，分别是嵌入方法、基于图的特征挖掘方法、核函数方法和度学习方法。我们提供了对各方法的全面比较和总结，然后对图分类进行归纳与探索，并概述了应用于图分类任务的数据集和开放源代码。但是，对于图分类方法在各领域中的应用还很少，仍需要更多的科研人员不懈为之努力。