基于二阶图自编码器的复杂网络分析

摘" 要：为了充分利用复杂网络中蕴含的信息，增强图自编码器模型的表征能力，提出一种基于二阶图卷积网络的自编码器模型SeGCN-AE。先使用二阶图卷积网络提取实体属性和关系信息，生成低维特征表示；然后使用内积解码器重构复杂网络链接关系矩阵，并通过重构损失对模型进行优化。在两个基准复杂网络数据集实验中，SeGCN-AE的性能始终优于当前较为先进的基线模型，表明二阶关系的引入能够增强模型的表征能力，提升复杂网络分析任务的表现。

关键词：图自编码器；图卷积网络；标签预测；关系预测

中图分类号：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" 引" 言

复杂网络是一种理解和表征现实世界复杂系统的方法，能够将复杂系统中的实体表示为节点，实体之间的某种关系表示为链接（边），例如社交网络、犯罪网络和交通网络。复杂网络分析就是利用已有数据和算法模型对复杂网络中某些未知信息进行预测，例如对实体性质进行判断的标签预测任务、不同实体之间是否存在链接的关系预测任务等。

当前，复杂网络分析方法主要分为基于监督信息进行端到端训练的图卷积网络模型（Graph Convolutional Network， GCN）[1]和基于无监督自编码器[2]进行表征学习的图表示学习[3]算法。GCN以复杂网络的实体属性和链接关系为输入，通过实体间信息传递和聚合，生成用于下游任务的特征向量。例如，GCN引入了图上的一阶谱卷积近似，能够通过叠加多个GCN层实现远距离节点信息的传递和保留；图注意力网络（Graph Attention Network， GAT）[4]使模型在信息聚合过程中能够保留关键实体的特征信息；Ye等人在GAT的基础上提出了稀疏图注意力网络[5]，能够识别噪声以及与任务无关的链接，从而对信息量最大的邻居执行特征聚合。图表示学习是将复杂网络中的实体表示为一组低维的特征向量，并在向量中保留复杂网络的相关信息，进而应用于下游图分析任务。例如，变分图自编码器[6]是一类重要的图表示学习方法，采用变分自编码器为基础架构，利用GCN提取复杂网络特征生成均值和方差向量并计算实体向量表示，最后通过重建实体之间的链接关系进行关系预测任务。

本文在已有研究的基础上，使用能够传递和聚合二阶邻域信息的二阶图卷积网络（Second-Order Graph Convolutional Network， SeGCN）[7]和自编码器构建图表示学习模型。综上，本文主要贡献如下：

1）利用保留二阶相似度的SeGCN构建自编码器模型SeGCN-AE，使模型能够传递和聚合复杂网络中一阶和二阶邻域的特征信息。

2）在两个基准复杂网络数据集上的标签预测和关系预测任务中，SeGCN-AE的性能始终优于当前较为先进的基线模型，表明二阶信息的引入增强了模型对复杂网络中特征信息的表征能力。

1" 理论基础

1.1" 图卷积网络

GCN利用实体之间的链接关系实现信息传递和聚合，捕捉实体间存在的某种依赖关系和潜在特征。对于多层GCN，其层间传播公式为：

式中，， 为" 的度矩阵，σ（·）为激活函数，H（·）为各层激活矩阵，H（0）为X。GCN实质上就是通过关系矩阵A直接聚合邻域中实体的特征信息。为了增强对高阶结构特征的表征能力，在GCN的基础上提出了引入二阶信息的SeGCN：

式中，A12为同时保留一阶和二阶关系的实体关系矩阵，即在关系矩阵的基础上增加对称归一化的关系矩阵平方进行计算。

1.2" 自编码器

自编码器是一种处理高维数据的神经网络模型，通常由两部分组成：将输入压缩成潜在空间的隐变量编码器和利用隐变量重构输入的解码器。为了使输入与输出相接近，自编码器的训练过程可以转化为最小化重构误差。为了使自编码器能够学习原始数据中的潜在特征，通常会添加不同的优化函数来增强模型的表征能力。

2" 算法与模型结构

本文基于SeGCN和自编码器构建图表示学习模型SeGCN-AE，模型整体框架如图1所示。SeGCN-AE以实体属性矩阵X和实体关系矩阵A为输入，通过SeGCN编码器对进行特征提取和降维，生成低维向量表示，解码器通过特征向量内积重构关系矩阵，训练时使用重构损失对参数进行优化。

编码器部分，SeGCN-AE使用双层SeGCN进行构建，编码过程的表达式为：

式中，σ（·）使用ReLU激活函数，W （l）为参数矩阵，Y为复杂网络中实体特征向量。解码器部分使用特征向量内积重构关系矩阵：

SeGCN-AE通过计算重构损失以及防止参数过拟合的正则化项进行优化：

最终，SeGCN-AE通过上述“编码—解码”的过程，实现无监督表示学习，生成用于标签预测和关系预测的实体特征向量表示。

3" 实验与结果分析

3.1" 实验设置

本文使用当前较为先进的基线模型SGC-AE [6]、GC-GAE [8]、GAT-AE [9]以及MGAE [10]与SeGCN-AE进行比较，并通过两个基准复杂网络数据集[6] Cora和CiteSeer上的标签预测和关系预测进行评估。为保证实验的公平性，各模型采用相同的数据集划分，同时采用相同的参数设置进行初始化，其中编码器隐藏层维度和嵌入维度分别设置为32和16，训练过程中使用Adam优化器更新模型参数，学习率设为0.01，迭代次数设为200。

在标签预测实验中使用常见分类指标Micro-F1和Macro-F1进行比较。Micro-F1在计算过程中考虑了每个类别中实体的数量，适用于数据分布不平衡的情况，而Macro-F1计算过程中没有考虑到实体的数量，即平等地看待每一类，因此受高P值和高R值类的影响较大。关系预测是一种二分类任务，对复杂网络中实体之间的链接和非链接进行预测，因此采用常见二分类指标AUC（Area Under the Curve）和AP（Average Precision）进行评估。AUC的计算方法同时考虑了分类器对于正例和负例的分类能力，在样本不平衡的情况下，依然能够对分类器作出合理的评价。AP则用于衡量模型在每个类别上的分类性能。

3.2" 实验结果

对于标签预测任务以10%为间隔，随机抽取10%到40%的实体作为训练数据，剩余实体中抽取30%作为测试集，各模型采用相同的数据集划分，记录Micro-F1（%）和Macro-F1（%）。标签预测实验结果如图2和图3所示。

从结果看有以下分析：

1）在两个复杂网络数据集上，SeGCN-AE的标签预测性能均优于当前较为先进的基线模型。上述结果表明，SeGCN-AE能够同时提取一阶邻域和二阶邻域中实体的特征信息，并将其保留在生成的低维嵌入中，进而提升标签预测任务的实验表现。

2）在两个数据集上，使用线性编码的SGC-AE表现不佳，上述结果表明线性编码虽然能够加快模型运算速度，但是提取复杂网络属性和拓扑结构信息的能力有限，未能有效保留复杂网络相关信息。

3）在不同数据集上，同一基线模型的分类表现差异明显。例如，GC-GAE在CiteSeer数据集上表现出色，但在同类型的Cora上表现不佳。上述结果表明，基线模型在处理不同数据集时，泛化能力有限。与基线模型相反，SeGCN-AE在两个数据集上均取得了良好的实验性能，证明了SeGCN-AE强大的泛化能力。

4）与基线模型相比，SeGCN-A仅使用20%的数据进行训练，便可显著提升标签预测任务的实验结果。表1为使用20%数据训练时各模型的Micro-F1（%）和Macro-F1（%）分数。上述结果表明，使用聚合二阶邻域特征的SeGCN，能够增强模型对复杂网络信息的表征能力，进而提高标签预测任务的实验表现。

对于关系预测任务，各模型采用相同的数据集划分，保留所有实体属性信息，移除复杂网络中10%的链接，同时随机采样数量与移除链接数相同的非链接（无链接关系的实体对），构建关系预测任务的测试集，使用剩余90%的链接对模型进行训练，记录AUC（%）和AP（%）。关系预测实验结果如表2所示。

在两个复杂网络数据集上的分析结果如下：

1）SeGCN-AE的AUC和AP分数始终高于基线模型。上述结果表明，SeGCN-AE能够有效提取复杂网络的属性信息和高阶结构特征，并将其编码到低维实体特征表示中，提升关系预测任务的实验表现。

2）使用线性编码器的SGC-AE和使用注意力机制的GAT-AE表现不佳。限制SGC-AE原因仍是无法有效提取和保留原始图的属性信息和高阶结构特征，而GAT-AE在运算过程中仅对存在链接关系的实体分配权重，更加关注邻域中实体的信息，缺少对无链接实体的关注。

实际上，SeGCN-AE的高性能主要得益于引入二阶关系作为一阶关系的补充，进一步增强了模型对复杂网络拓扑结构的表征能力，能够在低维特征向量中保留更丰富的复杂网络信息。因此，在标签预测和关系预测任务中，基于二阶图卷积自编码器的SeGCN-AE能够实现更为准确的预测结果。

4" 结" 论

本文提出了一种引入二阶邻域信息的图自编码器模型SeGCN-AE，增强模型对复杂网络中高阶结构特征的表征能力。实验结果表明，二阶关系的引入能够在低维特征向量中保留更丰富的复杂网络信息，提升标签预测和关系预测任务的实验表现。在未来工作中，除了采用更先进的自编码器结构，将引入更为高效的邻域信息传递和聚合的编码器进行复杂网络特征提取，如基于多视角的属性和拓扑信息提取方法。此外，在后续工作中，还将针对图自编码器模型的复杂度、泛化能力进一步量化和分析。

参考文献：

[1] CHEN Z C，FU 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—），男，汉族，河北唐山人，博士研究生在读，研究方向：图神经网络；刘义江（1994—），男，汉族，四川达州人，博士研究生在读，研究方向：国家安全理论；通讯作者：莫嘉颖（1997—），女，汉族，广西玉林人，助教，硕士，研究方向：教育技术；罗恒雨（2003—），女，汉族，广西玉林人，本科在读，研究方向：刑事科学技术。