面向電力邊緣數(shù)據(jù)分析的圖分類算法研究進展

許愛東，胡志偉，蔣屹新，張宇南，吳濤

（1.南方電網(wǎng)技術(shù)研究院有限責(zé)任公司，廣州510670；2.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶400065；3.重慶郵電大學(xué)網(wǎng)絡(luò)空間安全與信息法學(xué)院，重慶400065）

0 引言

隨著圖數(shù)據(jù)在物聯(lián)網(wǎng)、智能電網(wǎng)等信息領(lǐng)域地標產(chǎn)生與廣泛存在，圖分類成為圖數(shù)據(jù)分析的關(guān)鍵問題之一。圖分類是一種試圖將整個圖用正標簽或負簽來標注的有監(jiān)督學(xué)習(xí)問題。這也是最早將機器學(xué)習(xí)和數(shù)據(jù)挖掘技術(shù)應(yīng)用于圖數(shù)據(jù)的任務(wù)。

在智能電網(wǎng)領(lǐng)域，隨著電力系統(tǒng)信息化水平的不斷提高和配用電相關(guān)數(shù)據(jù)量的廣泛采集，各類邊緣裝置都積累了大量的數(shù)據(jù)亟待處理與利用。電網(wǎng)中普遍存在通信故障、設(shè)備故障、電網(wǎng)波動以及用戶異常用電行為等事件，它們都可以通過監(jiān)控數(shù)據(jù)進行捕獲。對于設(shè)備故障及異常用電的檢測，早期普遍采用的是現(xiàn)場檢測方法。隨著人工智能的發(fā)展，人們致力于尋求基于監(jiān)控數(shù)據(jù)分析對電網(wǎng)故障和異常用電行為進行高效的發(fā)現(xiàn)、預(yù)防和處理。

圖作為復(fù)雜數(shù)據(jù)的代表性表達形式，許多學(xué)者對圖數(shù)據(jù)分類問題已經(jīng)做了大量的研究。在生物信息[1]、惡意軟件檢測[2]、文本分類[3]等領(lǐng)域，圖分類已經(jīng)得到了廣泛的應(yīng)用。為了介紹現(xiàn)有圖分類方法，促進智能電網(wǎng)領(lǐng)域邊緣數(shù)據(jù)分析技術(shù)的發(fā)展，本文對圖分類相關(guān)方法進行歸納與總結(jié)。

1 概述

分類是數(shù)據(jù)分析領(lǐng)域中的一個基本問題，是一種有監(jiān)督的機器學(xué)習(xí)方法。其目的是從一組已知類別的數(shù)據(jù)中發(fā)現(xiàn)分類模型，以預(yù)測出新的數(shù)據(jù)未知類別。然而，現(xiàn)在的數(shù)據(jù)存儲一般都是采用關(guān)系數(shù)據(jù)庫或圖，所以出現(xiàn)了圖分類方法的研究。

圖是表示系統(tǒng)中實體的節(jié)點以及實體之間關(guān)系的連邊的集合。圖數(shù)據(jù)是以圖為對象形式的表示。圖分類是圖數(shù)據(jù)分析中的一個重要研究分支，在物聯(lián)網(wǎng)、智能電網(wǎng)等信息領(lǐng)域有廣泛的應(yīng)用。目前，圖分類問題主要研究二分類問題（正類和負類）。即已知訓(xùn)練圖集和測試圖集，圖分類的目標是構(gòu)建一個分類模型，把兩者區(qū)分開。

本文根據(jù)基礎(chǔ)模型的不同，將現(xiàn)有圖分類的方法歸納為四類，分別是嵌入方法、基于圖的特征挖掘方法、核函數(shù)方法和深度學(xué)習(xí)方法，如圖1 所示。

圖1 圖分類的總框架

2 嵌入方法

本小節(jié)介紹基于嵌入方法的圖分類模型，并對這些模型進行比較分析。嵌入方法[4-5]為每個圖導(dǎo)出固定數(shù)量的特征，用作分類的矢量表示。嵌入方法的優(yōu)點是能夠兼容任何機器學(xué)習(xí)分類器。

2.1 算法模型

文獻[6]提出一種基于嵌入表示的圖分類方法。該方法采用基于類別信息的特征子圖選擇策略，不但考慮了子圖的結(jié)構(gòu)信息，而且在頻繁子圖挖掘過程中充分利用直接選擇特征子圖以及生成分類規(guī)則。

針對大型圖的嵌入，文獻[7]提出了學(xué)習(xí)圖卷積層（Learning Graph Convolutional Layer，LGCL）的模型框架，對于每個特征維，LGCL 方法中的每個節(jié)點都會從其鄰近的具有值排序的節(jié)點中選擇一定數(shù)量的特征。如圖2 所示，圖中的每個節(jié)點都有一個維數(shù)特征向量n=3。對于目標節(jié)點（3，7，8），它的六個鄰居的第一個特性組件的值為9，6，5，3，0，0。如果我們把窗口大小設(shè)為k=4，然后是選中左邊四個最大的值（即9，6，5，3）。同樣的過程在剩下的兩個有限元中重復(fù)。通過包含目標節(jié)點本身的特征向量，得到維數(shù)（k+1）×n 的數(shù)據(jù)矩陣。為了嵌入大規(guī)模圖，采用子圖選擇方法來減少內(nèi)存和資源需求。文獻[8]提出了圖劃分神經(jīng)網(wǎng)絡(luò)（Graph Partition Neural Networks，GPNN）的模型框架，GPNN 擴展了圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Networks，GNNs）來嵌入超大圖，它在局部（節(jié)點間的支撐信息）和全局信息傳播（子圖間的消息）之間交替進行，這種調(diào)度方法可以避免序列調(diào)度所需的深度計算圖。文獻[9]提出了LINE 模型框架，LINE 模型用于嵌入任意類型的圖，如無向圖、有向圖和加權(quán)圖。它利用正則抽樣來降低優(yōu)化復(fù)雜度。這三個模型框架均解決了可擴展性的問題。

圖2 可學(xué)習(xí)的圖卷積層方法[7]

2.2 小結(jié)

文獻[6]巧妙地將嵌入方法與頻繁子圖特征挖掘相結(jié)合的形式進行圖分類，性能較好。這一做法為嵌入方法與頻繁子圖特征挖掘提供了新的思路。

3 基于圖的特征挖掘方法

在本節(jié)中，本文介紹了有關(guān)基于圖的特征挖掘的圖分類模型，并對這些模型進行分析。圖的特征挖掘使用了類似于子圖發(fā)現(xiàn)的方法，因為圖的特征挖掘的一般做法是在圖實例中尋找所有頻繁或者有意義的子圖。這些子結(jié)構(gòu)被用于將圖數(shù)據(jù)表示成一個單表的數(shù)據(jù)表示，然后傳統(tǒng)的分類算法可以將圖實例進行分類。

3.1 算法模型

傳統(tǒng)的特征濾波方法不依賴于任何分類器來選擇特征。與選擇冗余特征的濾波方法相比，包裝器方法通過子集空間搜索，利用分類器對特征子集的分類能力進行評估，識別出最優(yōu)子集[10]，從而識別出高信息量的特征。最大邊際特征選擇[11]是一種包裝方法。在該方法中，它利用信息增益來衡量每個特征與類標簽之間的相關(guān)性，然后選擇冗余較少的特征，覆蓋新的訓(xùn)練樣本。

文獻[12]提出了一個多任務(wù)圖分類問題，其中多個圖分類任務(wù)被聯(lián)合規(guī)則化，以找到所有學(xué)習(xí)任務(wù)共享的判別子圖。文獻[13]提出了一種高效的圖特征選擇方法，該方法使用頻繁子圖作為圖分類的特征。兩者都是通過子圖特征的形式探索圖分類的性能。

為了對圖進行學(xué)習(xí)表示，需要一種既具有一定獨特性和穩(wěn)定性又能快速計算圖特征表示。文獻[14]發(fā)現(xiàn)了圖的譜距離簇及其基于圖的特征表示。通過將其應(yīng)用于圖分類問題，評估出圖的普距離簇生成的圖特征的質(zhì)量以及其實用性。為了建立更高精度的圖分類模型，文獻[15]提出了一種新的網(wǎng)絡(luò)分類方法，它獨立于網(wǎng)絡(luò)大小，并采用無對齊的網(wǎng)絡(luò)比較度量。該方法是基于監(jiān)督機器學(xué)習(xí)算法并且利用網(wǎng)絡(luò)的拓撲相似性來進行分類任務(wù)。

文獻[16]提出了一種基于特征的網(wǎng)絡(luò)分類方法。通過建立網(wǎng)絡(luò)動力學(xué)模型，計算多個時間尺度下不同網(wǎng)絡(luò)屬性的協(xié)方差，并定義了廣義分類特征。文獻[17]提出了一種基于圖的多尺度時間序列表示方法和一種特征提取方法。圖的多尺度時間序列表示方法將時間序列轉(zhuǎn)換為不同尺度的可見性圖集合，通過研究小序列的概率分布、分類性和程度統(tǒng)計等統(tǒng)計圖特征，并進行特征提取，然后利用這些特征通過泛型分類器建立高精度的分類模型。

3.2 小結(jié)

在圖數(shù)據(jù)分類中，最直接的方法是基于頻繁子圖特征挖掘的算法進行分類，而該方法的缺點是利用挖掘算法產(chǎn)生的頻繁子圖的數(shù)目巨大，甚至達到指數(shù)級，計算量大。

4 核函數(shù)方法

在本節(jié)中，本文介紹了有關(guān)核函數(shù)的圖分類模型，并對這些模型進行分析。尋找頻繁子圖在計算上是不可行的，一個替代算法使用了核方法。文獻[18]和文獻[19]基于在圖上的游走度量來描述圖核函數(shù)。文獻[19]計數(shù)起點和終點有相同標簽的游走。文獻[19]則考慮了有著相同標簽序列的隨機游走的概率。文獻[20]綜述了結(jié)構(gòu)數(shù)據(jù)中的核方法。

4.1 算法模型

近年來，各種圖核函數(shù)被提出。在文獻[21]和文獻[22]中，提出了基于隨機游動的圖核，計算了兩種圖共有的游動數(shù)。從那時起，隨機游動核得到深入的研究，如文獻[23-26]。在文獻[27]中，首先提出了基于樹模式的核函數(shù)。這兩種方法最初應(yīng)用于帶有離散標簽的圖?；谧疃搪窂絒28]的內(nèi)核是通過對轉(zhuǎn)換后的輸入圖執(zhí)行1 步遍歷來計算的，其中邊用最短路徑長度標注。上述方法的一個缺點是計算成本高。

為使用經(jīng)典的集成學(xué)習(xí)框架在流上實現(xiàn)大規(guī)模圖分類，這就要求不同塊中的數(shù)據(jù)位于同一個特征空間中，為此，文獻[29]提出了一種嵌套子樹哈希（Nested Subtree Hashes，NSH）算法及其派生的NSH 核函數(shù)，通過遞歸方式將不同塊的多分辨率子樹模式投影到一組常見的低維特征空間上，其中NSH 核函數(shù)可以在流上支持大規(guī)模的圖分類。

一般來說，最優(yōu)賦值會產(chǎn)生不定函數(shù)，這使得其在內(nèi)核方法中的使用變得復(fù)雜。文獻[30]提出了一類基核用于保證正半定最優(yōu)分配核的方法。這些基核通過直方圖相交在線性時間內(nèi)計算最優(yōu)分配核形成層次結(jié)構(gòu)。雖然計算簡化的直方圖相交，類似于金字塔匹配內(nèi)核[31]，但文獻[30]提出的方法并不局限于特定的對象。通過基于最優(yōu)賦值推導(dǎo)出新的圖核，而這些圖核比基于卷積的圖核有了更大改進。

文獻[32]提出了采用眾所周知的圖上消息傳遞機制的圖內(nèi)核設(shè)計的一般框架。該框架的主要思想是使用迭代過程隱式地更新頂點的表示形式。由于該框架采用了復(fù)雜的置換不變內(nèi)核函數(shù)，該框架比神經(jīng)消息傳遞體系結(jié)構(gòu)更具表現(xiàn)力。

4.2 小結(jié)

文獻[28]提出的方法在分類的實驗中表現(xiàn)明顯優(yōu)于基于隨機游動的內(nèi)核。對于大規(guī)模的圖數(shù)據(jù)分類，文獻[29]與文獻[30]所提出的方法都有非常好的表現(xiàn)。

5 深度學(xué)習(xí)方法

在本節(jié)中，本文介紹了有關(guān)深度學(xué)習(xí)的圖分類模型，并對這些模型進行分析。本節(jié)從基本方法和池化方法兩方面進行敘述圖分類的模型。

5.1 基本方法

本小節(jié)主要介紹的基本方法是運用神經(jīng)網(wǎng)絡(luò)的方法將圖數(shù)據(jù)進行分類，接下來主要介紹卷積神經(jīng)網(wǎng)絡(luò)、門控圖神經(jīng)網(wǎng)絡(luò)、圖膠囊網(wǎng)絡(luò)和膠囊圖神經(jīng)網(wǎng)絡(luò)四個模型。

（1）算法模型

圖片是排列成網(wǎng)格形狀，因此，圖片可以直接運用卷積操作。但是對于圖數(shù)據(jù)來說，需要一個從圖到向量的映射的一個預(yù)處理過程。文獻[33]提出一種方法可以基于任意的圖結(jié)構(gòu)的卷積神經(jīng)網(wǎng)絡(luò)。該方法通過從圖中選擇一個固定長度的節(jié)點序列，并對序列中的每個節(jié)點收集固定大小的鄰居集合，最后對由當(dāng)前節(jié)點及其對應(yīng)的鄰居構(gòu)成的子圖進行規(guī)范化，作為卷積結(jié)構(gòu)的輸入三步構(gòu)建卷積分片，并利用卷積結(jié)構(gòu)分別對每個分片進行操作。

在文獻[34]關(guān)于圖神經(jīng)網(wǎng)絡(luò)的研究基礎(chǔ)上，文獻[35]研究了圖形結(jié)構(gòu)輸入的特征學(xué)習(xí)技術(shù)，并提出一種新的模型門控圖神經(jīng)網(wǎng)絡(luò)（Gating Graph Neural Networks，GGNNs），該模型采用門控遞歸單元作為遞歸函數(shù)[36]，將遞歸次數(shù)減少到一定的步長。與圖神經(jīng)網(wǎng)絡(luò)不同，GGNNs 使用時間反向傳播來學(xué)習(xí)參數(shù)，它不再需要約束參數(shù)來保證收斂性。

文獻[37]利用文獻[38]提出的膠囊概念，提出了一種新的基于基本膠囊思想的圖膠囊網(wǎng)絡(luò)模型，解決了現(xiàn)有圖卷積神經(jīng)網(wǎng)絡(luò)（Graph Convolutional Neural Network，GCNN）模型無法獲取更多局部結(jié)構(gòu)信息的問題。而文獻[39]受到文獻[40]提出的膠囊網(wǎng)絡(luò)的啟發(fā)，提出膠囊圖神經(jīng)網(wǎng)絡(luò)。它采用了膠囊的概念來解決現(xiàn)有基于圖神經(jīng)網(wǎng)絡(luò)的圖嵌入算法的不足。通過以膠囊的形式抓取節(jié)點的特征，利用路由機制來捕獲圖級別的重要信息。

（2）小結(jié)

文獻[33]提出的方法在多個數(shù)據(jù)集上優(yōu)于圖內(nèi)核方法，美中不足的是容易在較小的數(shù)據(jù)集上過度擬合。對于大規(guī)模的圖數(shù)據(jù)，文獻[35]提出的門控圖神經(jīng)網(wǎng)絡(luò)的缺點是需要在所有節(jié)點上多次運行遞歸函數(shù)，從而重新查詢要存儲在內(nèi)存中的所有節(jié)點的中間狀態(tài)，將會增加運算量。

5.2 池化方法

本小節(jié)主要介紹運用圖卷積神經(jīng)網(wǎng)絡(luò)的方法將圖數(shù)據(jù)分類，圖卷積神經(jīng)網(wǎng)絡(luò)中的池化層在不斷的改進中，表現(xiàn)效果不斷提升。接下來主要敘述了可微圖池模塊、自注意力機制圖池、圖的傅里葉變換的特征池的卷積網(wǎng)絡(luò)和關(guān)系池四個模型。

（1）算法模型

目前的圖神經(jīng)網(wǎng)絡(luò)方法本質(zhì)上是扁平的，并且不能學(xué)習(xí)圖的層次表示，這一限制對于圖分類任務(wù)來說尤其成問題，其目標是預(yù)測與整個圖相關(guān)的標簽。在此，文獻[41]提出了一個可微圖池模塊。該模型可以生成圖的層次表示，并且可以以端到端的方式與各種圖神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)相結(jié)合。受自注意機制的影響，文獻[42]提出了一種基于自注意力機制的圖池化。該方法可以使用相對較少的參數(shù)以端到端方式學(xué)習(xí)分層的語句表示。利用自我注意機制來區(qū)分應(yīng)該刪除的節(jié)點和應(yīng)該保留的節(jié)點，并考慮了節(jié)點特征和圖的拓撲結(jié)構(gòu)。

在傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）中，層次化學(xué)習(xí)圖表示類似于池化步驟。然而，局部結(jié)構(gòu)信息在匯聚過程中很大程度上仍然被忽略。文獻[43]提出了一種基于圖的傅里葉變換的特征池的卷積網(wǎng)絡(luò)，它能充分利用池過程中的節(jié)點特征和局部結(jié)構(gòu)。然后基于池操作符設(shè)計池層，并與傳統(tǒng)的圖卷積網(wǎng)絡(luò)的卷積層相結(jié)合，形成一個用于圖分類的圖神經(jīng)網(wǎng)絡(luò)框架。文獻[44]提出了用于圖分類和回歸的關(guān)系池（RP）框架。該框架借鑒了有限部分交換性理論，為圖提供了一個具有最大表示能力的框架。

（2）小結(jié)

池化層之所以設(shè)計在卷積層后面，目的是通過池化來降低卷積層輸出的特征向量，同時改善結(jié)果達到不易出現(xiàn)過擬合現(xiàn)象。

6 歸納與探索

在本節(jié)中，我們先總結(jié)出文獻中經(jīng)常使用的基準數(shù)據(jù)集。然后，我們介紹了常用數(shù)據(jù)集的基準性能，并列出了圖分類的可用開源實現(xiàn)代碼。

如表1 所示，在各數(shù)據(jù)集中列舉了每個數(shù)據(jù)集的圖的個數(shù)、特征數(shù)以及標簽數(shù)，并統(tǒng)計了數(shù)據(jù)集在文獻中出現(xiàn)的頻率。這些數(shù)據(jù)集大多是化學(xué)、生物圖數(shù)據(jù)集，如NCI-1、NCI-109、MUTAG、D&D 和ENZY-MES[45]五個數(shù)據(jù)集。在表1 中列出的數(shù)據(jù)集是常用的數(shù)據(jù)集。

表1 圖分類中的常用數(shù)據(jù)集

在表2 中，我們提供了前面所述的圖分類模型的開放源代碼的超鏈接。值得注意的是，文獻[46]在Py-Torch 中發(fā)布了一個名為PyTorch Geometric 的幾何學(xué)習(xí)庫，實現(xiàn)了多個圖神經(jīng)網(wǎng)絡(luò)用于圖分類的任務(wù)。

文獻[47]提出了基于神經(jīng)網(wǎng)絡(luò)的異常用電檢測模型，利用有監(jiān)督的多隱藏層的神經(jīng)網(wǎng)絡(luò)算法，對大量用戶數(shù)據(jù)進行模型訓(xùn)練，可用于自動檢測用戶用電量是否正常，根據(jù)檢測結(jié)果區(qū)分出異常用戶。該模型通過逐層初始化解決了深度神經(jīng)網(wǎng)絡(luò)在訓(xùn)練上的難度。該方法為電力公司減少成本，提高了查處異常用電情況的效率。

表2 圖分類的開源代碼

文獻[48]提出了一種將時間序列轉(zhuǎn)化為網(wǎng)絡(luò)結(jié)構(gòu)的可視化圖算法，該算法以柱狀圖的形式進行構(gòu)圖，進而將時序數(shù)據(jù)表示成圖數(shù)據(jù)，受此啟發(fā)，我們將電力數(shù)據(jù)表示成圖數(shù)據(jù)進行處理。受文獻[45]的啟發(fā)，我們將運用圖神經(jīng)網(wǎng)絡(luò)中的分類方法對由電力數(shù)據(jù)表示成的圖數(shù)據(jù)進行分析，試圖區(qū)分出電力數(shù)據(jù)中的異常用電情況。在接下來的研究中，我們嘗試把圖分類任務(wù)應(yīng)用到電力系統(tǒng)中。針對電力系統(tǒng)中出現(xiàn)用戶的正常用電與異常用電運用圖神經(jīng)網(wǎng)絡(luò)中的圖卷積池化方法進行分類篩選出異常用電的情況。

7 結(jié)語

在本文中，我們對圖分類進行了全面的概述。根據(jù)基礎(chǔ)模型的不同，將現(xiàn)有圖分類的方法歸納為四類，分別是嵌入方法、基于圖的特征挖掘方法、核函數(shù)方法和度學(xué)習(xí)方法。我們提供了對各方法的全面比較和總結(jié)，然后對圖分類進行歸納與探索，并概述了應(yīng)用于圖分類任務(wù)的數(shù)據(jù)集和開放源代碼。但是，對于圖分類方法在各領(lǐng)域中的應(yīng)用還很少，仍需要更多的科研人員不懈為之努力。