图神经网络及其在通信网络领域应用综述

2021-08-05李硕朋齐思宇林绍福刘希亮陈华敏

北京工业大学学报 2021年8期

李硕朋，齐思宇，林绍福,3，刘希亮,3，陈华敏

(1.北京工业大学信息学部，北京 100124；2.北京未来网络科技高精尖创新中心，北京 100124；3.北京智慧城市研究院，北京 100124)

人工智能作为近年来科学研究的前沿领域，引发了社会全行业的重点关注，逐渐成为社会经济发展的新引擎.人工智能已经在社会各领域中得到广泛的实践与应用[1]，其中主要包括：自然语言处理、计算机视觉、智能机器人、数据挖掘、认知与推理等.

随着智能手机、智能汽车和智能家居等智能设备的快速增长，当今网络数据流量呈指数式增长.同时，边缘计算、虚拟化和网络切片等技术的应用，使得网络服务变得更加多样化，提升了用户体验，也催生出了更加复杂的网络环境.如何高效管理大量智能设备，并优化大规模复杂网络环境的资源分配，成为未来网络发展的一个重要问题.

未来网络需要全面拥抱人工智能.人工智能作为未来网络的大脑，用于网络的优化与决策.同时，网络节点算力的增强为网络带来了骨骼与肌肉，使得智能网络的计算成为可能.算法与算力的协同发展将使未来网络进入全新的智能化时代.

通信网络的基本结构是图.图数据是一种典型的非欧式空间数据，具有复杂的相关性和对象间依赖性.传统图论的方法难以适应未来网络中复杂的图形问题.因此，寻找解决复杂图数据的算法，用以指导通信网络的资源分配、管理调度，成为未来网络中的重要科学问题.

图神经网络作为近年来人工智能领域的新兴技术，为处理复杂图结构数据开辟了新空间.借助深度学习、强化学习等人工智能技术，图神经网络能够快速挖掘图结构中的拓扑信息和复杂特征，已经解决了计算机视觉、推荐系统、知识图谱等领域的许多重大问题.因此，图神经网络与未来网络的结合，是解决网络优化问题、增强网络可靠性、提升网络资源利用率的重要途径.

本文综述了图神经网络及其在通信网络领域的应用.表1给出了本文重复使用的术语简写形式及其含义.本文首先介绍了图神经网络的基本模型以及几种重要的图神经网络；其次介绍了图神经网络在通信网络各领域中的具体应用方法；在结论部分探讨了当前的研究现状并给出了未来的研究方向.

表1 术语简写及含义Table 1 Abbreviations and meanings of terms

1 图神经网络

图神经网络的概念由Gori等[2]于2005年最早提出，Scarselli等[3]对此模型进行了更详细的阐述.Gori等提出的图神经网络借鉴了神经网络领域的研究成果，能够直接处理图结构数据，其核心是局部转移函数和局部输出函数.局部转移函数生成节点的状态向量，该向量包含节点的邻域信息.转移函数在所有节点间共享，并根据输入的邻域更新节点的状态向量h，其表达式为

(1)

ov=g(hv,xv)

(2)

局部转移函数和局部输出函数应用于所有节点的堆叠形式构成了GNN结构.模型通过迭代最终将达到稳定状态.

早期的图神经网络存在很大的局限性，其效率较低，计算成本较大，同时节点特征难以影响多次更新后的状态.近年来，为了更高效地处理图结构数据，陆续有新型图神经网络及应用研究被提出.

1.1 图卷积网络

GCN将卷积运算引入图结构，是目前最主要的图神经网络之一，根据特征提取方式的不同，可划分为基于谱域的图卷积网络和基于空间域的图卷积网络.

基于谱域的图卷积网络源自于图信号处理，引入滤波器对图卷积进行定义，可将其理解为通过滤波器去除噪声从而得到输入信号的分类结果[4].Bruna等[5]基于谱图理论首次提出了定义谱域图卷积网络的卷积层函数.2016年，Kipf等[6]首次提出了GCN的概念，此处的GCN为基于谱域的图卷积网络.Kipf等将谱域图卷积定义为信号与滤波器函数的乘积，其表达式为

gθ*x=UgθUTx

(3)

式中：gθ为滤波器函数；x为图在节点上的信号；U为图归一化拉普拉斯矩阵的特征向量.gθ可以被理解为图拉普拉斯矩阵的特征值函数，即gθ(Λ)，Λ为图拉普拉斯矩阵的特征值组成的对角矩阵，θ为函数参数.为降低计算复杂度，可以对gθ(Λ)进行近似处理，其表达式为

(4)

(5)

(6)

式中：Tk为k阶切比雪夫多项式；θ′为切比雪夫系数向量；L为图拉普拉斯矩阵；λmax为L的最大特征值；IN为单位矩阵；D为对角度矩阵；A为邻接矩阵.当限制k=1时，卷积层可简化为

(7)

令

(8)

(9)

则图卷积网络的卷积层公式为

(10)

式中：σ(·)为非线性激活函数；W(l)为第l层图卷积网络的权重矩阵.

GCN的概念被提出后，陆续有新形式的基于谱域的图卷积网络模型被提出，如AGCN[7]、CayleyNet[8]、AGC[9]等.但基于谱域的图卷积网络无法处理有向图且扩展性较差，而基于空间域的GCN更加灵活与通用.

基于空间域的图卷积网络根据节点的空间关系定义图卷积.NN4G[10]是最早提出的基于空间域的图卷积网络，其通过对节点邻域特征信息的直接累加实现图卷积.Gilmer等[11]提出的MPNN可看作基于空间域的图卷积网络的通用框架.MPNN将空间域卷积分解为信息传递和状态更新2个过程，其将节点v的特征作为隐藏状态的初始态，即

(11)

式中xv为节点v的特征.MPNN的隐藏状态更新公式为

(12)

式中：l为层索引；Ul(·)为更新函数；Ml(·)为信息传递函数.得到图中所有节点的隐藏表示后，可通过readout函数生成整个图的表示.

(13)

式中R(·)为readout函数.通过定义不同形式的更新函数、信息传递函数和readout函数，MPNN可以表示多种基于空间域的图卷积网络.典型的基于空间域的图卷积网络还包括PATCHY-SAN[12]、GraphSage[13]和DCNN[14]等.

基于谱域的图卷积网络方法与基于空间域的图卷积网络方法的总结与对比如表2所示，表中时间复杂度为各方法进行图卷积计算的时间复杂度，n为节点数，m为边数.

表2 图卷积网络方法的比较与总结Table 2 Comparison and summary of graph convolutional networks methods

1.2 图注意力网络

GAT在图卷积网络的基础上引入了注意力机制，使模型能够专注于和当前任务最相关的信息，从而改进模型性能.基于谱域的GCN中，滤波器函数依赖于拉普拉斯矩阵，而拉普拉斯矩阵来源于图结构，这使得在特定图上训练的模型无法直接应用于其他图结构.为解决这一问题，Velikovi等[15]提出了一种新型的图神经网络结构，即GAT.

GAT学习图中每个节点的邻域特征的平均值，根据邻域的重要性进行稀释加权.图注意力层是GAT实现注意力机制的关键结构.图注意力层以图中节点的特征为输入，输出另一组可能具有不同基数的更高层次的节点特征.图注意力层通过注意力机制a得到的注意力系数实现输入与输出的转换，注意力系数表示节点j对于节点i的重要性，其表达式为

eij=a(Wxi,Wxj)

(14)

式中：W为应用于所有节点的权重矩阵，代表输入特征与输出特征间的关系；xi和xj分别为节点i和节点j的特征.模型通过只计算节点与其邻居节点的注意力系数将注意力机制引入图结构，而不需考虑图的结构信息.为简化运算和便于比较，对注意力系数进行正则化处理，并将其用于生成输出特征

(15)

式中：σ(·)为非线性激活函数；αij为正则化后的注意力系数.GAT中还引入了与Transformer架构[16]类似的多头注意力机制，能够针对相邻节点对进行并行计算，稳定学习过程.

GAT方法的复杂度较低且只关注相邻节点，无须整张图的信息，其应用于新的图结构时不需重复训练模型.针对复杂的图结构，有研究提出了新型的图注意力网络，如异构图注意力网络[17]和动态图注意力网络[18]，这些模型能够在更加复杂、信息量更大的网络中取得更好的效果.

1.3 图自编码器

GAE是一种无监督的学习框架，能够将图结构转化为低维向量，并利用编码信息重建图结构，常用于图嵌入(graph embedding,GE)和图结构生成.

图嵌入是一种图表示学习 (graph representation learning,GRL)方法，其目的是在保留节点信息的同时将图结构数据映射为低维稠密向量.图嵌入使图结构数据能够被更高效地应用于传统机器学习算法，从而在推荐、分类等任务中取得更好的结果，典型方法包括基于随机游走的图嵌入，如DeepWalk[19]和Node2Vec[20]，以及基于矩阵分解的图嵌入，如奇异值分解(singular value decomposition,SVD)、局部线性嵌入(locally linear embedding,LLE)和非负矩阵分解(nonnegative matrix factorization,NMF).相比基于随机游走和基于矩阵分解的图嵌入，图自编码器能够应用于高度非线性的图结构，保留图的非线性结构与复杂特征.

2014年，Tian等[21]首次将自动编码器(autoencoder)应用于图数据，该模型将图的邻接矩阵或其变体作为原始节点特征，通过堆叠稀疏自编码器(sparse autoencoder,SAE)生成了图的非线性嵌入，即低维节点表示.SDNE[22]是一种同样采用堆叠自动编码器结构的重要的图自编码器模型，其分别通过节点间的一阶相似性和二阶相似性保持图的局部网络结构和全局网络结构，利用多层非线性函数生成图嵌入向量.SDNE的隐藏层表达式为

(16)

(17)

式中xv为节点v的特征；W(l)为第l层权重矩阵；b(l)为第l层偏差.得到最后的隐藏层输出后，可通过反转编码器的计算过程获得输出表示x′.SDNE包含2个损失函数，其中第一损失函数采用拉普拉斯特征映射的思想，用以保留一阶相似性，其表达式为

(18)

式中：si,j表示图中节点的连接关系，当且仅当节点i与节点j相连时，si,j>0.第二损失函数用以保持二阶相似性，并引入惩罚向量对非零元素的重构误差施加相比零元素更大的惩罚，其表达式为

(19)

Lmix=L2nd+αL1st+νLreg

(20)

式中Lreg为正则化L2范数，用于防止过拟合.

另一类图自编码器利用变分自编码器(variational autoencoders,VAE)[23]实现图嵌入，变分自编码器是一种重要的生成模型，能够提高模型的泛化能力.VGAE[24]首先将变分自编码器应用于图结构，其推理模型，即编码器，利用了一个2层的GCN[6]结构，其表达式为

(21)

(22)

式中：μ为编码器的均值矩阵；log(σ)为方差矩阵；X为特征矩阵；A为邻接矩阵；zi为随机潜在变量.VGAE的生成函数，即解码器，由隐藏变量的内积得出，其表达式为

(23)

除VGAE外，使用变分自动编码器的图自编码器还包括RGVAE[25]、DVNE[26]、ARVGA[27]等.

1.4 其他图神经网络

除图卷积网络和图注意力网络外，常用的图神经网络还包括门控图神经网络(gated graph neural networks,GGNN)和时空图神经网络(spatial-temporal graph neural networks,STGNN)等.

门控图神经网络是对传统图神经网络架构的改进，通过将门控循环单元(gated recurrent unit,GRU)引入图神经网络，提高了模型在信息长期传播时的性能.Li等[28]提出的门控图序列神经网络将门控循环单元引入到信息传播过程，将迭代循环控制在固定的步数，不再需要进行参数约束以保证收敛.除该模型外，门控图神经网络模型还包括GAAN[29]等.

时空图(spatio-temporal graph)[30]是一种刻画实体间在空间与时间维度上交互的图结构，其拥有节点、时空边(spatio-temporal edge)和时间边(temporal edge)3个基本要素，高维特征空间中的特征矩阵会随时间而变化.时空图神经网络能够学习时空图中的隐藏模式，同时获取图结构中时间域和空间域的特征信息.时空图神经网络可以被分为基于循环神经网络(recurrent neural network,RNN)的方法和基于卷积神经网络(convolutional neural networks,CNN)的方法.基于RNN的STGNN通过图卷积捕获时空相关性，如文献[31-32].基于CNN的STGNN相比基于RNN的方法，以非递归的方式处理时空图，能够进行并行计算且可以避免梯度爆炸或梯度消失问题，如CGCN[33].

2 图神经网络在通信网络领域应用

上述图神经网络方法具有处理复杂通信网络问题的能力，已经被应用到网络功能虚拟化、无线网络资源分配、网络建模与性能分析等方面.已有研究成果的应用领域与实现方法如表3所示.

表3 图神经网络在通信网络领域应用总结Table 3 Summary of GNN in communication networks

2.1 软件定义网络和网络功能虚拟化

软件定义网络(software defined network,SDN)和网络功能虚拟化(network functions virtualization,NFV)是近年来通信网络领域的研究热点，SDN将网络的控制平面与转发平面分离，通过中央控制器，获得整个网络的拓扑结构和资源信息.NFV借助虚拟化技术将网络功能从传统硬件设备中剥离出来，提升了网络配置的灵活性.

GNN可以用于解决SDN和NFV中需要探索图结构的问题，例如动态资源分配、服务功能链(service function chain,SFC)建立和虚拟网络映射(virtual network embedding,VNE).

2.1.1 SFC动态资源分配

图神经网络于2017年首次用于NFV动态资源分配.Mujumbi等[34]提出一种用于SFC流量预测的监督学习方法.该方法利用GNN将输入的历史流量映射为输出的预测流量，并据此调节资源分配.此模型的图神经网络训练2个函数：点的转移函数和输出函数.节点n的转移函数输入n的特征、所有邻接边特征、所有相邻节点特征及状态，输出节点n的状态.输出函数根据点的状态和特征计算节点输出.

Jaliodia等[35]使用与文献[34]同样的图神经网络，但采用异步深度强化学习(deep reinforcement learning,DRL)模型解决SFC资源需求预测问题.此类问题的本质是传统的基于机器学习的回归模型.

Liu等[36]利用GNN预测NFV资源需求，从而获得请求即将到来的预先信息，并提高基于深度强化学习的SFC重构算法的有效性.

网络流量迁移也是动态资源配置的一个重要分支问题.Sun等[37-38]提出一种利用GNN和深度强化学习实现NFV网络流量迁移的方法，该方法将输入的网络拓扑结构映射为输出的迁移后网络拓扑结构，用于实现网络流量的扩增、缩减和负载均衡.

SFC动态资源分配问题的本质是拓扑结构的变换，优化目标为端到端总延迟，且不存在复杂限制条件，易于利用GNN求解.

2.1.2 服务功能链建立

不同于SFC动态资源分配，SFC建立问题需要根据输入的网络请求，通过算法按次序求得输出的网络拓扑结构.SFC建立问题包含虚拟网络功能(virtual network function,VNF)的放置和链接的建立.解决该问题通常需要借助自然语言处理中的序列模型.

Heo等[39]提出了一种针对该问题的图神经网络序列模型.该模型由编码器和解码器组成，编码器用于表示网络的拓扑结构，解码器用于计算相邻节点的概率和执行VNF的概率.在编码器中，拓扑结构由标记矩阵和邻接矩阵表示.标记矩阵用于标记节点可接收的VNF类型，邻接矩阵用于表示延迟.编码器使用GGNN将拓扑结构进行编码，解码器每次选择一个节点直到完成整个路径选择.解码器的状态编码包含完整VNF请求、下一个需执行的VNF和当前所在物理节点.解码器输出选择下一个节点的概率以及是否要在此节点上执行VNF.

Kim等[40-41]利用GNN学习代表物理网络的图结构中节点的状态嵌入，再通过附加输出层对节点上的VNF类型和最优VNF实例数进行预测，能够得到更具体的VNF管理策略，该模型同时适用于物理网络动态变化的场景.

Sun等[42]提出了与文献[39-41]相似的强化学习模型用于解决VNF放置问题，区别在于使用GNN抽取节点和链接资源.

上述SFC建立方法关注于VNF放置问题.此类方法借助于GNN可用于图节点分类的特性，但并未涉及链接建立，因此具有一定的局限性.

2.1.3 虚拟网络映射

虚拟网络映射问题类似SFC建立问题，但网络请求、资源限制条件更为复杂.VNE问题分为节点映射和链接映射.已有的GNN解决VNE问题的方法主要集中在节点映射方面.

Habibi等[43]提出一种利用GAE辅助VNE物理节点分类的方法.该模型的输入是邻接矩阵和资源特征矩阵，通过图神经网络训练出可以重建网络拓扑结构的监督学习模型.

Yan等[44]提出利用GCN结合深度强化学习完成节点分类任务.该方法采用actor-critic强化学习，其中GCN用于抽取物理节点特征，从物理节点抽取出的特征与虚拟网络请求通过前馈神经网络(feed forward neural networks,FF)融合，最终得到映射节点的概率分布.

事实上，针对大规模复杂网络的SFC建立和VNE问题，考虑到节点和链接资源以及优化目标的复杂性，图神经网络是提取拓扑信息的有力工具，具有提供更快速、更优化的解的潜力.

2.2 无线资源分配

随着5G、物联网、边缘计算等技术的快速发展与应用，无线网络的资源分配问题变得越来越重要.无线接入网可以抽象为图拓扑结构，其中用户和基站为点，无线信道为链接.用户、基站、无线信道需要通力协作，通过资源的有效配置，在不同应用场景下实现多样化的优化目标，提升网络资源的利用率.

2.2.1 功率控制

无线功率控制问题是如何确定各发送端的发射功率，使网络达到整体最优的信噪比的问题.其基本模型是一个带有限制条件的优化问题，优化目标是信号与干扰加噪声比的加权和，限制条件是基站或设备的发射功率.

Shen等[45]提出将多用户无线信道用一个完全图来表示，并利用GNN解决功率控制问题.该完全图的节点是一个收发对，节点特征包含直接信道状态和权重；图的链接是干扰信道，链接特征为干扰信道状态.该方法通过GCN训练转移函数和输出函数，用于输出每个发射器最优化的发射功率.

考虑到实际问题中基站和用户的情况，Guo等[47]提出一种解决异构网络功率控制问题的方法.该模型的节点包含基站和用户2种异构节点，异构节点采用不同的转移函数，并用参数共享得到输出结果.

无线功率控制问题并不是一个直观的图结构问题，因此需要通过建模将问题转化为图结构，随后利用GNN模型求解.

2.2.2 其他资源分配问题

无线功率控制问题的GNN模型可以被扩展，用以解决其他无线资源分配问题，例如波束成形[46]、设备间通信[48]、信道选择[49-50]、拓扑控制[51]等.

Lee等[48]提出一种基于图嵌入解决设备间通信无线连接调度问题的方法.该问题的图抽象模型与文献[45]相同，区别在于优化问题的变量是二元的，即收发对是否开启.该方法采用Structure2Vec图嵌入模型将图结构转化为低维向量，并通过FF解决二元分类问题从而得到输出结果.

考虑到信道状态难以获得的情况，Zhao等[49]提出利用强化学习结合GCN解决认知无线电中信道选择和功率控制问题.智能体观测网络状态，通过GCN生成动作，执行动作后根据网络的反馈学习优化GCN参数.

Nakashima等[50]利用基于深度强化学习的GCN提取具有拓扑信息的信道向量的特征，进而生成信道部署策略.该方法能够在密集部署的无线局域网中进行信道分配，从而提高系统吞吐量.

Yan等[51]提出了一种基于GCN的节能拓扑控制算法，利用GCN模仿最大生成树算法，进行链路预测，并根据概率图向拓扑中引入新的边，优化了5G和B5G环境下无线自组织物联网生命周期.

Eisen等[52]提出一种解决无线资源分配的统一模型：随机边图神经网络(random edge graph neural networks,REGNN).REGNN和已有方法相比具有可扩展性和可转化性，可以用于解决功率控制、带有用户请求的多接入以及随机接入无线控制系统等问题.

GNN解决无线资源分配问题的基本原理是抽取并学习节点特征、链接特征和拓扑结构，在每个节点上输出一个最优化数值.

2.3 网络建模与性能分析

网络建模与性能分析是实现高效通信网络的一个基础问题.如上文所述，GNN可以用于有线、无线等网络的资源优化，网络中的各种资源通过优化策略被分配到设备上，因此急需一个高效的网络模型用以评价资源分配的好坏.

2.3.1 网络性能指标分析

网络性能指标分析需要根据现有网络的拓扑结构和资源状态，通过算法计算出评价当前网络的一个指标.该指标可以是简单的端到端延迟，也可以是针对特定情况的复杂指标.

Rusek等[53]提出RouteNet，利用GNN精确评估网络路径的端到端延迟与丢包.RoutNet将网络拓扑结构、流量矩阵和端到端路径作为输入，根据网络状态输出性能评价指标(延迟、抖动、丢包等).RouteNet内部包含一个多层的信息传递神经网络，采用RNN作为转移函数，将链接和路径信息压缩到隐藏状态向量，最终通过输出函数得到路径的评价指标值.RouteNet被用于以下2种示例问题：1)基于网络延迟丢包的路由优化；2)有预算限制的网络拓扑升级.

针对数据中心网络，Li等[54]提出一种利用GNN推断网络流完成时间的方法.每一个网络流作为GNN的输入，由5个特征组成：原地址、目标地址、网络流大小、起始时间、服务类型.该方法采用基于GNN的监督学习，神经网络结构由编码器、核心、解码器构成.编码器将节点和连接特征编码；核心执行多层信息传递；解码器输出完成时间特征.

网络演算是一种基于非线性代数的确定性排队理论，目前已广泛应用于网络建模与性能分析，特别是为计算延迟和积压等端到端性能参数的确界提供了有效工具.Geyer等[55-56]提出利用GNN构建网络演算模型，用于推断网络延迟、辅助判定多协议标签交换(multi-protocol label switching,MPLS)配置合理性.

2.3.2 路由选择与评价

路由选择是通信网络领域古老且核心的优化问题.人工智能算法已经被用于网络的路由选择.在光传输网络中，Almasan等[57]采用基于Q学习的DRL推断端到端路径.为提升算法效果，GNN代替传统神经网络，被用于计算Q学习中的Q值.

在多径路由中，Zhu等[58]利用RouteNet模型，根据给定的网络拓扑和多径路由，预测多径传输控制协议(transmission control protocol,TCP)吞吐量，并以此指导TCP路径选择.

值得注意的是，为了减小动作数据集空间，以上路由选择方法[57-58]，均将备选路径限定在K条最短路径范围内，因此限制了方法的应用场景与拓展性.事实上，随着通信网络复杂性的增加，对最优路由策略的要求也不断提高，GNN的拓扑信息感知能力允许算法根据流量分布动态地调整路由策略.

Geyer等[59]提出利用GNN学习分布式路由算法.该方法将路由器接口抽象为拓扑结构中的点，并使用GNN训练出隐藏节点信息，使得每一个节点都有对于图拓扑结构的本地表示.该方法是少有的面向分布式的GNN应用.