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

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

關鍵詞：圖自編碼器；圖卷積網(wǎng)絡；標簽預測；關系預測

中圖分類號：TP183" 文獻標識碼：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" 引" 言

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

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

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

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

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

1" 理論基礎

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

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

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

式中，A12為同時保留一階和二階關系的實體關系矩陣，即在關系矩陣的基礎上增加對稱歸一化的關系矩陣平方進行計算。

1.2" 自編碼器

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

2" 算法與模型結構

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

編碼器部分，SeGCN-AE使用雙層SeGCN進行構建，編碼過程的表達式為：

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

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

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

3" 實驗與結果分析

3.1" 實驗設置

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

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

3.2" 實驗結果

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

從結果看有以下分析：

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

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

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

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

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

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

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

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

實際上，SeGCN-AE的高性能主要得益于引入二階關系作為一階關系的補充，進一步增強了模型對復雜網(wǎng)絡拓撲結構的表征能力，能夠在低維特征向量中保留更豐富的復雜網(wǎng)絡信息。因此，在標簽預測和關系預測任務中，基于二階圖卷積自編碼器的SeGCN-AE能夠實現(xiàn)更為準確的預測結果。

4" 結" 論

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

參考文獻：

[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] 來杰，王曉丹，向前，等.自編碼器及其應用綜述 [J].通信學報，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].計算機科學與探索，2022，16（1）：59-87.

[7] 袁立寧，蔣萍，莫嘉穎，等.基于二階圖卷積自編碼器的圖表示學習 [J/OL].計算機工程與應用，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)絡；劉義江（1994—），男，漢族，四川達州人，博士研究生在讀，研究方向：國家安全理論；通訊作者：莫嘉穎（1997—），女，漢族，廣西玉林人，助教，碩士，研究方向：教育技術；羅恒雨（2003—），女，漢族，廣西玉林人，本科在讀，研究方向：刑事科學技術。