基于二階圖自編碼器的復(fù)雜網(wǎng)絡(luò)分析

摘" 要：為了充分利用復(fù)雜網(wǎng)絡(luò)中蘊(yùn)含的信息，增強(qiáng)圖自編碼器模型的表征能力，提出一種基于二階圖卷積網(wǎng)絡(luò)的自編碼器模型SeGCN-AE。先使用二階圖卷積網(wǎng)絡(luò)提取實(shí)體屬性和關(guān)系信息，生成低維特征表示；然后使用內(nèi)積解碼器重構(gòu)復(fù)雜網(wǎng)絡(luò)鏈接關(guān)系矩陣，并通過重構(gòu)損失對模型進(jìn)行優(yōu)化。在兩個基準(zhǔn)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)中，SeGCN-AE的性能始終優(yōu)于當(dāng)前較為先進(jìn)的基線模型，表明二階關(guān)系的引入能夠增強(qiáng)模型的表征能力，提升復(fù)雜網(wǎng)絡(luò)分析任務(wù)的表現(xiàn)。

關(guān)鍵詞：圖自編碼器；圖卷積網(wǎng)絡(luò)；標(biāo)簽預(yù)測；關(guān)系預(yù)測

中圖分類號：TP183" 文獻(xiàn)標(biāo)識碼：A" 文章編號：2096-4706（2024）10-0064-04

Analysis of Complex Network Based on Second-order Graph Autoencoder

YUAN Lining1，2， LIU Yijiang1， MO Jiaying2， LUO Hengyu2

（1.People's Public Security University of China， Beijing" 100038， China; 2.Guangxi Police College， Nanning" 530028， China）

Abstract： In order to make full use of the information contained in complex networks and enhance the representation ability of graph autoencoder models， we propose an autoencoder model SeGCN-AE based on second-order graph convolutional networks （SeGCN）. First， SeGCN is used to extract entity attributes and relationship information， and generate low-dimensional feature representations. Then， the inner product decoder is used to reconstruct the complex network link relationship matrix， and the model is optimized by reconstruction loss. On the two baseline complex network dataset experiments， the performance of SeGCN-AE is always better than current advanced baseline model， indicating that the introduction of second-order relationships can enhance representation ability of the model and improve the performance of complex network analysis tasks.

Keywords： graph autoencoder; graph convolutional network; label prediction; relationship prediction

0" 引" 言

復(fù)雜網(wǎng)絡(luò)是一種理解和表征現(xiàn)實(shí)世界復(fù)雜系統(tǒng)的方法，能夠?qū)?fù)雜系統(tǒng)中的實(shí)體表示為節(jié)點(diǎn)，實(shí)體之間的某種關(guān)系表示為鏈接（邊），例如社交網(wǎng)絡(luò)、犯罪網(wǎng)絡(luò)和交通網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)分析就是利用已有數(shù)據(jù)和算法模型對復(fù)雜網(wǎng)絡(luò)中某些未知信息進(jìn)行預(yù)測，例如對實(shí)體性質(zhì)進(jìn)行判斷的標(biāo)簽預(yù)測任務(wù)、不同實(shí)體之間是否存在鏈接的關(guān)系預(yù)測任務(wù)等。

當(dāng)前，復(fù)雜網(wǎng)絡(luò)分析方法主要分為基于監(jiān)督信息進(jìn)行端到端訓(xùn)練的圖卷積網(wǎng)絡(luò)模型（Graph Convolutional Network， GCN）[1]和基于無監(jiān)督自編碼器[2]進(jìn)行表征學(xué)習(xí)的圖表示學(xué)習(xí)[3]算法。GCN以復(fù)雜網(wǎng)絡(luò)的實(shí)體屬性和鏈接關(guān)系為輸入，通過實(shí)體間信息傳遞和聚合，生成用于下游任務(wù)的特征向量。例如，GCN引入了圖上的一階譜卷積近似，能夠通過疊加多個GCN層實(shí)現(xiàn)遠(yuǎn)距離節(jié)點(diǎn)信息的傳遞和保留；圖注意力網(wǎng)絡(luò)（Graph Attention Network， GAT）[4]使模型在信息聚合過程中能夠保留關(guān)鍵實(shí)體的特征信息；Ye等人在GAT的基礎(chǔ)上提出了稀疏圖注意力網(wǎng)絡(luò)[5]，能夠識別噪聲以及與任務(wù)無關(guān)的鏈接，從而對信息量最大的鄰居執(zhí)行特征聚合。圖表示學(xué)習(xí)是將復(fù)雜網(wǎng)絡(luò)中的實(shí)體表示為一組低維的特征向量，并在向量中保留復(fù)雜網(wǎng)絡(luò)的相關(guān)信息，進(jìn)而應(yīng)用于下游圖分析任務(wù)。例如，變分圖自編碼器[6]是一類重要的圖表示學(xué)習(xí)方法，采用變分自編碼器為基礎(chǔ)架構(gòu)，利用GCN提取復(fù)雜網(wǎng)絡(luò)特征生成均值和方差向量并計算實(shí)體向量表示，最后通過重建實(shí)體之間的鏈接關(guān)系進(jìn)行關(guān)系預(yù)測任務(wù)。

本文在已有研究的基礎(chǔ)上，使用能夠傳遞和聚合二階鄰域信息的二階圖卷積網(wǎng)絡(luò)（Second-Order Graph Convolutional Network， SeGCN）[7]和自編碼器構(gòu)建圖表示學(xué)習(xí)模型。綜上，本文主要貢獻(xiàn)如下：

1）利用保留二階相似度的SeGCN構(gòu)建自編碼器模型SeGCN-AE，使模型能夠傳遞和聚合復(fù)雜網(wǎng)絡(luò)中一階和二階鄰域的特征信息。

2）在兩個基準(zhǔn)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上的標(biāo)簽預(yù)測和關(guān)系預(yù)測任務(wù)中，SeGCN-AE的性能始終優(yōu)于當(dāng)前較為先進(jìn)的基線模型，表明二階信息的引入增強(qiáng)了模型對復(fù)雜網(wǎng)絡(luò)中特征信息的表征能力。

1" 理論基礎(chǔ)

1.1" 圖卷積網(wǎng)絡(luò)

GCN利用實(shí)體之間的鏈接關(guān)系實(shí)現(xiàn)信息傳遞和聚合，捕捉實(shí)體間存在的某種依賴關(guān)系和潛在特征。對于多層GCN，其層間傳播公式為：

式中，， 為" 的度矩陣，σ（·）為激活函數(shù)，H（·）為各層激活矩陣，H（0）為X。GCN實(shí)質(zhì)上就是通過關(guān)系矩陣A直接聚合鄰域中實(shí)體的特征信息。為了增強(qiáng)對高階結(jié)構(gòu)特征的表征能力，在GCN的基礎(chǔ)上提出了引入二階信息的SeGCN：

式中，A12為同時保留一階和二階關(guān)系的實(shí)體關(guān)系矩陣，即在關(guān)系矩陣的基礎(chǔ)上增加對稱歸一化的關(guān)系矩陣平方進(jìn)行計算。

1.2" 自編碼器

自編碼器是一種處理高維數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)模型，通常由兩部分組成：將輸入壓縮成潛在空間的隱變量編碼器和利用隱變量重構(gòu)輸入的解碼器。為了使輸入與輸出相接近，自編碼器的訓(xùn)練過程可以轉(zhuǎn)化為最小化重構(gòu)誤差。為了使自編碼器能夠?qū)W習(xí)原始數(shù)據(jù)中的潛在特征，通常會添加不同的優(yōu)化函數(shù)來增強(qiáng)模型的表征能力。

2" 算法與模型結(jié)構(gòu)

本文基于SeGCN和自編碼器構(gòu)建圖表示學(xué)習(xí)模型SeGCN-AE，模型整體框架如圖1所示。SeGCN-AE以實(shí)體屬性矩陣X和實(shí)體關(guān)系矩陣A為輸入，通過SeGCN編碼器對進(jìn)行特征提取和降維，生成低維向量表示，解碼器通過特征向量內(nèi)積重構(gòu)關(guān)系矩陣，訓(xùn)練時使用重構(gòu)損失對參數(shù)進(jìn)行優(yōu)化。

編碼器部分，SeGCN-AE使用雙層SeGCN進(jìn)行構(gòu)建，編碼過程的表達(dá)式為：

式中，σ（·）使用ReLU激活函數(shù)，W （l）為參數(shù)矩陣，Y為復(fù)雜網(wǎng)絡(luò)中實(shí)體特征向量。解碼器部分使用特征向量內(nèi)積重構(gòu)關(guān)系矩陣：

SeGCN-AE通過計算重構(gòu)損失以及防止參數(shù)過擬合的正則化項進(jìn)行優(yōu)化：

最終，SeGCN-AE通過上述“編碼—解碼”的過程，實(shí)現(xiàn)無監(jiān)督表示學(xué)習(xí)，生成用于標(biāo)簽預(yù)測和關(guān)系預(yù)測的實(shí)體特征向量表示。

3" 實(shí)驗(yàn)與結(jié)果分析

3.1" 實(shí)驗(yàn)設(shè)置

本文使用當(dāng)前較為先進(jìn)的基線模型SGC-AE [6]、GC-GAE [8]、GAT-AE [9]以及MGAE [10]與SeGCN-AE進(jìn)行比較，并通過兩個基準(zhǔn)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集[6] Cora和CiteSeer上的標(biāo)簽預(yù)測和關(guān)系預(yù)測進(jìn)行評估。為保證實(shí)驗(yàn)的公平性，各模型采用相同的數(shù)據(jù)集劃分，同時采用相同的參數(shù)設(shè)置進(jìn)行初始化，其中編碼器隱藏層維度和嵌入維度分別設(shè)置為32和16，訓(xùn)練過程中使用Adam優(yōu)化器更新模型參數(shù)，學(xué)習(xí)率設(shè)為0.01，迭代次數(shù)設(shè)為200。

在標(biāo)簽預(yù)測實(shí)驗(yàn)中使用常見分類指標(biāo)Micro-F1和Macro-F1進(jìn)行比較。Micro-F1在計算過程中考慮了每個類別中實(shí)體的數(shù)量，適用于數(shù)據(jù)分布不平衡的情況，而Macro-F1計算過程中沒有考慮到實(shí)體的數(shù)量，即平等地看待每一類，因此受高P值和高R值類的影響較大。關(guān)系預(yù)測是一種二分類任務(wù)，對復(fù)雜網(wǎng)絡(luò)中實(shí)體之間的鏈接和非鏈接進(jìn)行預(yù)測，因此采用常見二分類指標(biāo)AUC（Area Under the Curve）和AP（Average Precision）進(jìn)行評估。AUC的計算方法同時考慮了分類器對于正例和負(fù)例的分類能力，在樣本不平衡的情況下，依然能夠?qū)Ψ诸惼髯鞒龊侠淼脑u價。AP則用于衡量模型在每個類別上的分類性能。

3.2" 實(shí)驗(yàn)結(jié)果

對于標(biāo)簽預(yù)測任務(wù)以10%為間隔，隨機(jī)抽取10%到40%的實(shí)體作為訓(xùn)練數(shù)據(jù)，剩余實(shí)體中抽取30%作為測試集，各模型采用相同的數(shù)據(jù)集劃分，記錄Micro-F1（%）和Macro-F1（%）。標(biāo)簽預(yù)測實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

從結(jié)果看有以下分析：

1）在兩個復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上，SeGCN-AE的標(biāo)簽預(yù)測性能均優(yōu)于當(dāng)前較為先進(jìn)的基線模型。上述結(jié)果表明，SeGCN-AE能夠同時提取一階鄰域和二階鄰域中實(shí)體的特征信息，并將其保留在生成的低維嵌入中，進(jìn)而提升標(biāo)簽預(yù)測任務(wù)的實(shí)驗(yàn)表現(xiàn)。

2）在兩個數(shù)據(jù)集上，使用線性編碼的SGC-AE表現(xiàn)不佳，上述結(jié)果表明線性編碼雖然能夠加快模型運(yùn)算速度，但是提取復(fù)雜網(wǎng)絡(luò)屬性和拓?fù)浣Y(jié)構(gòu)信息的能力有限，未能有效保留復(fù)雜網(wǎng)絡(luò)相關(guān)信息。

3）在不同數(shù)據(jù)集上，同一基線模型的分類表現(xiàn)差異明顯。例如，GC-GAE在CiteSeer數(shù)據(jù)集上表現(xiàn)出色，但在同類型的Cora上表現(xiàn)不佳。上述結(jié)果表明，基線模型在處理不同數(shù)據(jù)集時，泛化能力有限。與基線模型相反，SeGCN-AE在兩個數(shù)據(jù)集上均取得了良好的實(shí)驗(yàn)性能，證明了SeGCN-AE強(qiáng)大的泛化能力。

4）與基線模型相比，SeGCN-A僅使用20%的數(shù)據(jù)進(jìn)行訓(xùn)練，便可顯著提升標(biāo)簽預(yù)測任務(wù)的實(shí)驗(yàn)結(jié)果。表1為使用20%數(shù)據(jù)訓(xùn)練時各模型的Micro-F1（%）和Macro-F1（%）分?jǐn)?shù)。上述結(jié)果表明，使用聚合二階鄰域特征的SeGCN，能夠增強(qiáng)模型對復(fù)雜網(wǎng)絡(luò)信息的表征能力，進(jìn)而提高標(biāo)簽預(yù)測任務(wù)的實(shí)驗(yàn)表現(xiàn)。

對于關(guān)系預(yù)測任務(wù)，各模型采用相同的數(shù)據(jù)集劃分，保留所有實(shí)體屬性信息，移除復(fù)雜網(wǎng)絡(luò)中10%的鏈接，同時隨機(jī)采樣數(shù)量與移除鏈接數(shù)相同的非鏈接（無鏈接關(guān)系的實(shí)體對），構(gòu)建關(guān)系預(yù)測任務(wù)的測試集，使用剩余90%的鏈接對模型進(jìn)行訓(xùn)練，記錄AUC（%）和AP（%）。關(guān)系預(yù)測實(shí)驗(yàn)結(jié)果如表2所示。

在兩個復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上的分析結(jié)果如下：

1）SeGCN-AE的AUC和AP分?jǐn)?shù)始終高于基線模型。上述結(jié)果表明，SeGCN-AE能夠有效提取復(fù)雜網(wǎng)絡(luò)的屬性信息和高階結(jié)構(gòu)特征，并將其編碼到低維實(shí)體特征表示中，提升關(guān)系預(yù)測任務(wù)的實(shí)驗(yàn)表現(xiàn)。

2）使用線性編碼器的SGC-AE和使用注意力機(jī)制的GAT-AE表現(xiàn)不佳。限制SGC-AE原因仍是無法有效提取和保留原始圖的屬性信息和高階結(jié)構(gòu)特征，而GAT-AE在運(yùn)算過程中僅對存在鏈接關(guān)系的實(shí)體分配權(quán)重，更加關(guān)注鄰域中實(shí)體的信息，缺少對無鏈接實(shí)體的關(guān)注。

實(shí)際上，SeGCN-AE的高性能主要得益于引入二階關(guān)系作為一階關(guān)系的補(bǔ)充，進(jìn)一步增強(qiáng)了模型對復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的表征能力，能夠在低維特征向量中保留更豐富的復(fù)雜網(wǎng)絡(luò)信息。因此，在標(biāo)簽預(yù)測和關(guān)系預(yù)測任務(wù)中，基于二階圖卷積自編碼器的SeGCN-AE能夠?qū)崿F(xiàn)更為準(zhǔn)確的預(yù)測結(jié)果。

4" 結(jié)" 論

本文提出了一種引入二階鄰域信息的圖自編碼器模型SeGCN-AE，增強(qiáng)模型對復(fù)雜網(wǎng)絡(luò)中高階結(jié)構(gòu)特征的表征能力。實(shí)驗(yàn)結(jié)果表明，二階關(guān)系的引入能夠在低維特征向量中保留更豐富的復(fù)雜網(wǎng)絡(luò)信息，提升標(biāo)簽預(yù)測和關(guān)系預(yù)測任務(wù)的實(shí)驗(yàn)表現(xiàn)。在未來工作中，除了采用更先進(jìn)的自編碼器結(jié)構(gòu)，將引入更為高效的鄰域信息傳遞和聚合的編碼器進(jìn)行復(fù)雜網(wǎng)絡(luò)特征提取，如基于多視角的屬性和拓?fù)湫畔⑻崛》椒?。此外，在后續(xù)工作中，還將針對圖自編碼器模型的復(fù)雜度、泛化能力進(jìn)一步量化和分析。

參考文獻(xiàn)：

[1] CHEN Z C，F(xiàn)U L L，YAO J，et al. Learnable Graph Convolutional Network and Feature Fusion for Multi-View Learning [J].Information Fusion，2023，95：109-119.

[2] 來杰，王曉丹，向前，等.自編碼器及其應(yīng)用綜述 [J].通信學(xué)報，2021，42（9）：218-230.

[3] XIA W，WANG T X，GAO Q X，et al. Graph Embedding Contrastive Multi-Modal Representation Learning for Clustering [J].IEEE Transactions on Image Processing，2023，32：1170-1183.

[4] VELICKOVIC P，CUCURULL G，CASANOVA A，et al. Graph Attention Networks [J/OL].arXiv：1710.10903 [stat.ML].[2023-09-20].https：//arxiv.org/abs/1710.10903.

[5] YE Y，JI S H. Sparse Graph Attention Networks [J].IEEE Transactions on Knowledge and Data Engineering，2023，35（1）：905-916.

[6] 袁立寧，李欣，王曉冬，等.圖嵌入模型綜述 [J].計算機(jī)科學(xué)與探索，2022，16（1）：59-87.

[7] 袁立寧，蔣萍，莫嘉穎，等.基于二階圖卷積自編碼器的圖表示學(xué)習(xí) [J/OL].計算機(jī)工程與應(yīng)用，2023：1-9[2023-09-11].http：//kns.cnki.net/kcms/detail/11.2127.TP.20230626.1839.016.html.

[8] GUO L，DAI Q. Graph Clustering via Variational Graph Embedding [J/OL].Pattern Recognition，2022，122：108334[2023-09-19].https：//doi.org/10.1016/j.patcog.2021.108334.

[9] HE L，BAI L，YANG X，et al. High-order graph attention network [J].Information Sciences，2023，630：222-234.

[10] HY T S，KONDOR R. Multiresolution Equivariant Graph Variational Autoencoder [J/OL].Machine Learning：Science and Technology，2023，4（1）：015031[2023-09-19].https：//iopscience.iop.org/article/10.1088/2632-2153/acc0d8.

作者簡介：袁立寧（1995—），男，漢族，河北唐山人，博士研究生在讀，研究方向：圖神經(jīng)網(wǎng)絡(luò)；劉義江（1994—），男，漢族，四川達(dá)州人，博士研究生在讀，研究方向：國家安全理論；通訊作者：莫嘉穎（1997—），女，漢族，廣西玉林人，助教，碩士，研究方向：教育技術(shù)；羅恒雨（2003—），女，漢族，廣西玉林人，本科在讀，研究方向：刑事科學(xué)技術(shù)。