论文阅读01——《图卷积神经网络综述》

作者：徐冰冰、岑科廷、黄俊杰、沈华伟、程学旗发表时间：2020年5月《计算机学报》论文地址：https://cjc.ict.ac.cn/online/onlinepaper/xbb-2020514181350.pdf

论文阅读01——《图卷积神经网络综述》
写在前面
- 引言
- 图卷积神经网络
  - 谱方法
    - 卷积定理
    - 图上的傅里叶变换
    - 基于卷积定理的图卷积神经网络
    - 小波神经网络(Graph wavelet neural network)
    - 切比雪夫网络(ChebyNet)
    - 图上半监督学习一阶图卷积神经网络
    - 图热核网络(GraphHeat)
    - 基于个性化PageRank的图卷积神经网络(PPNP)
    - 简明一阶图卷积神经网络(SGC)
- 空间方法
  - 混合卷积网络(MoNet)
  - 消息传播网络(MPNNs)
  - 图神经网络(GNNs)
  - 图注意力网络(GAT)
  - 图采样聚合网络(GraphSAGE)
  - DCNN
  - 基于置信度的图卷积网络(ConfGCN)
  - 超图卷积网络(HGNN)
图池化操作
- 切比雪夫网络(ChebyNet)
- 微分池化模型(DIFFPOOL)
- 谱池化(EigenPooling)
- 基于注意力机制的池化算子(SAGPool)
图卷积神经网络的新进展
- 建模边上信息的图卷积网络
  - 子图拆解法
    - 关系图神经网络(R-GCNs)
    - 关系图注意力网络(R-GAT)
    - 符号图卷积网络(SGCN)
  - 对偶图构建法
    - 原始对偶图卷积神经网络(DPGCNN)
  - 权重重调法
    - 边注意力网络(EGAT)
    - 边约束卷积网络(ECC)
- 建模网络高阶信息的图卷积网络
  - 高阶图卷积神经网络(HA-GCN)
  - 模体卷积网络(Motif-CNN)
  - 异质注意力网络(HAN)
  - 模体卷积决策网络(MCN)

写在前面

由于博主已经本硕博连读，九月份即将开始研究生生涯，遂开启论文阅读这一系列博文，主要介绍一些文章的主要思想和创新点，可能会详细介绍一下模型，如果喜欢的话多多关注，另外其他系列也会不定时更新，记得来看~

引言

传统的卷积神经网络只能处理欧式空间数据（图像、文本和语音）这些领域的数据具有平移不变性——>从而可以在输入数据空间定义全局共享的卷积核，从而定义卷积神经网络。

图数据： 可以自然地表达实际生活中的数据结构，如交通网络、万维网和社交网络等。

平移不变性： 以图像数据为例，一张图片可以表示为欧式空间中一组规则散布的像素点，平移不变性则表示以任意像素点为中心，可以获取相同尺寸的局部结构

将卷积神经网络迁移到图数据分析处理中的核心在于图卷积算子的构建和图池化算子的构建。

图卷积神经网络的两类经典方法：谱方法和空间方法。谱方法借助卷积定理在谱域定义图卷积、空间方法通过在节点域定义节点相关性来实现图卷积。空间方法实现参数共享面临很大困难，因为邻域子节点不一定一样大。

最新进展： 异质连接、高阶连接、大规模图上的图卷积

相关应用： 推荐系统、交通预测

所面临的挑战来源：

图数据是非欧空间数据
图数据具有多样的特性（有向连接、异质连接、正负倾向带符号链接）
图数据的规模很大

图数据建模的发展历史：

起初，研究人员关注统计分析方法，图谱理论（用拉普拉斯矩阵的特征值和特征向量做社区分析或者人群聚类等；

随着深度学习的发展，网络嵌入（Network Embedding）：通过约束节点的邻近性为每个节点学习固定长度的表达，如DeepWalk、LINE、node2vec等，问题解决分为两个阶段：第一阶段为每个节点学习统一长度的表达，第二阶段将节点表达作为输入，训练分类模型。

端到端的建模：图卷积神经网络：如何在图上构建卷积算子

2013年Bruna等人提出第一个图卷积神经网络，他们基于图谱理论从卷积定理出发，在谱空间定义图卷积，后来发展为谱方法。最初的谱方法弊端：时空复杂度较高

ChebNet和GCN对谱方法中的两个卷积核进行参数化，大大降低了时空复杂度。

在这两个方法的启发下，空间方法应运而生，开始考虑在节点域用注意力机制、序列化模型等建模节点间的权重。没有过多地考虑图特性。

池化算子作为卷积神经网络的重要组成部分，作用是扩大感受野，降低参数，图上池化算子主要用于图分类问题。目的是学习到图的层级结构。

卷积算子的目的是刻画节点的局部结构

节点级别的任务： 节点分类、链接预测等，如引文网络中的文章分类，推荐系统中用户对商品的偏好推断。

图级别的任务： 图生成、图分类等，如药物网络生成，蛋白质网络中的蛋白质分类。

图卷积神经网络

谱方法利用卷积定理从谱域定义图卷积，空间方法从节点域出发，通过聚合函数来聚合每个中心节点和其邻近节点。

输入：是一张图，包括节点集合、边集合和边上权重集合。

图上的拉普拉斯定义了图上的导数，刻画了信号在图上的平滑程度。L=D-W

归一化的拉普拉斯矩阵：L=I-D^{-tfrac{1}{2}}WD^{-tfrac{1}{2}}

谱方法需要显式地定义卷积核，空间方法不需要，只需要定义核函数

谱方法

卷积定理

信号卷积的傅里叶变换等价于信号傅里叶变换的乘积：F(ftimes g)=F(f)cdot F(g)对其两端做傅里叶逆变换，得到fast g=F^{-1}(F(f)cdot F(g))

通过卷积定理，避免了因图上不满足平移不变性而导致无法卷积的问题。间接地求出了卷积算子。

图上的傅里叶变换

图上傅里叶变换的定义依赖于拉普拉斯矩阵的特征向量

hat{x}=U^Tx 其中hat{x}表示信号x变换到谱域之后的表示，U^T表示特征向量矩阵的转置，用于做傅里叶变换。信号x的傅里叶逆变换为

x=Ux 利用图上傅里叶变换和逆变换我们可以基于卷积定理实现图卷积算子x_Gast y=U((U^Tx)odot(U^Ty))其中odot指哈达玛乘法，表示两个向量的对应元素相乘。我们用一个对角矩阵g_theta代替向量U^Ty，那么哈达玛乘法可以转化为矩阵乘法，将卷积核g_theta作用在信号上，图卷积可以表示成如下形式：Ug_theta U^Tx。

基于卷积定理的图卷积神经网络

谱卷积神经网络是最早提出在图上构建卷积神经网络的方法，该方法利用卷积定理在每一层定义图卷积算子，在损失函数指导下，通过梯度反向回传学习卷积核，并堆叠多层组成神经网络。

谱卷积神经网络第m层的结构如下：

X_j^{m 1}=h(Usumlimits_{i=1}^p{F_{i,j}^m U^T X_i^m}),j=1,...,q

其中p,q分别是输入特征和输出特征的维度，X_i^min R^n表示图上节点在第m层的第i个输入特征，F_{i,j}^m表示谱空间下卷积核，h表示非线性激活函数，在谱卷积神经网络中，这样一层结构将特征从p维转化为q维，且基于卷积定理通过学习卷积核实现了图卷积。存在的问题，谱卷积神经网络的局部性没有得到保证，产生信息聚合的节点并不一定是邻近节点。

缺点：

依赖于图的拉普拉斯矩阵的特征分解，复杂度高
稠密矩阵计算时复杂度O(n2)
非局部化

Henaff等人提出带有平滑性约束的差值卷积核，这种方法降低参数个数，并且实现了图卷积神经网络的局部化。

小波神经网络(Graph wavelet neural network)

GWNN小波神经网络提出用小波变换代替傅里叶变换实现卷积定理。

和傅里叶变换相比，小波变换的基底具有几个很好的性质：

小波变换的基底可以通过切比雪夫多项式近似得到，避免拉普拉斯矩阵特征分解的高昂代价；
小波变换的基底具有局部性；
小波基底的局部性使得小波变换矩阵非常稀疏，这大大降低了Psi_s^{-1}x的计算复杂度，是计算过程更加高效；
热核函数中的超参数s用以表示热量扩散的范围，通过调节超参数s可以灵活地适应于不同任务场景。

小波神经网络的第m层的结构定义如下：

X_j^{m 1}=h(Psi_ssumlimits_{i=1}^pF_{i,j}^mPsi_s^{-1}X_i^m),j=1,...,q

切比雪夫网络(ChebyNet)

g_{theta}=sumlimits_{i=0}^{K-1}theta_kT_k(hatLambda)，其中theta_k是需要学的系数，hatLambda=tfrac{2Lambda}{lambda_{max}}-I_n.切比雪夫多项式是通过递归得到，递归表达式为T_k(x)=2xT_{k-1}-T_{k-2}(x)，其中T_0(x)=1，T_1(x)=x.令hat L=tfrac{2L}{lambda_{max}}-I_n，切比雪夫网络第m层的结构定义如下： X_j^{m 1}=h(Usumlimits_{i=1}^p(sumlimits_{k=0}^{K-1}theta_kT_k(hatLambda))U^TX_i^m)=h(sumlimits_{i=1}^p(sumlimits_{k=0}^{K-1}theta_kT_k(hat L))X_i^m)，j=1,...,q。切比雪夫网络利用特征值矩阵的多项式参数化卷积核，实现谱卷积神经网络，且巧妙地利用L=ULambda U^T引入拉普拉斯矩阵，从而避免了拉普拉斯矩阵的特征分解，同时参数复杂度从O(ntimes ptimes q)下降到O(Ktimes ptimes q)。此外，在拉普拉斯矩阵中，当且仅当节点i,j满足K跳可达时。L_{i,j}^Kne0，这一性质使得当K较小时，切比雪夫网络具有局部性。

图上半监督学习一阶图卷积神经网络

令K=2且lambda_{max}=2，则切比雪夫网络可以写成 X_j^{m 1}=h(sumlimits_{i=1}^{p}(theta_0 - theta_1(L-I_n))X_i^m) ,j=1,...,q 。在图上半监督学习场景下，带标签的数据非常少，为了避免模型过拟合，Kipf等人约束theta=theta_0=-theta_1来降低模型参数，并对权重矩阵做归一化处理，最终得到如下的一阶图卷积神经网络：X_j^{m 1}=h(sumlimits_{i=1}^pthetahat D^{-tfrac{1}{2}}hat Ahat D^{-tfrac{1}{2}}X_i^m)，j=1,...,q，其中，hat A=A I_n且hat D_{ii}=sumlimits_jhat A_{i,j}.

图热核网络(GraphHeat)

图热核网络从滤波器的角度，对以上谱方法进行分析，指出谱卷积神经网络都是高通滤波器，而切比雪夫网络和一阶图卷积神经网络都是高通滤波器，但这与图半监督学习任务中的平滑性先验不一致，基于此，图热核网络利用热核函数参数化卷积核，进而实现低通滤波器。

基于个性化PageRank的图卷积神经网络(PPNP)

PPNP从深层网络的搭建出发，指出随着模型层数加深，网络拟合能力增强，但是在一阶图卷积神经网络中会引起节点表达过于平滑，进而导致节点不可区分的问题。基于此，PPNP解耦维度变换和特征传播，并引入个性化PageRank，对输入数据先完成较少层数的维度变换，然后基于个性化PageRank进行特征传播，特征传播过程不进行参数学习，因此可以用在半监督学习任务中。

简明一阶图卷积神经网络(SGC)

非线性变换在一阶图卷积神经网络中无足轻重，使得GCN发挥作用的是每一层的特征传播机制。基于此，SGC抛弃层之间的非线性变换，将多个层的特征传播融合到一个层内，在完成特征传播后，SGC对样本做一次维度变换。

空间方法

混合卷积网络(MoNet)

MoNet着眼于图上平移不变性的缺失，通过定义映射函数将每个节点的局部结构映射为相同尺寸的向量，进而在映射的结果上学习共享的卷积核。

平移不变性的缺失给图卷积神经网络的定义带来困难。混合卷积网络在图上定义坐标系，并将节点之间的关系表示为新坐标系下的一个低维向量。同时，混合卷积网络定义一簇权重函数，权重函数作用在以一个节点为中心的所有邻近节点上，其输入为节点间的关系表示(一个低维向量)，输出为一个标量值。通过这簇权重函数，混合卷积网络为每个节点获得相同尺寸的向量表示：D_j(x)f=sumlimits_{yin N(x)}omega_j(u(x,y))f(y),j=1,...,J 。其中，N(x)表示x的邻近节点集合，f(y)表示节点y在信号f上的取值，u(x,y)指坐标系u下节点关系的低维向量表示，omega_j表示第j个权重函数，J表示权重函数的个数。这步操作使得每个节点都得到一个J维的表示，且这个表示融合了节点的局部结构信息，而混合卷积模型正是在这个J维表示上定义共享卷积核，(f_G^{star}g)(x)=sumlimits_{j=1}^J g(j)D_j(x)f，其中{g(j)}_{j=1}^J指卷积核。

消息传播网络(MPNNs)

MPNNs立足于节点之间的信息传播聚合，通过定义聚合函数的通用形式提出框架。

消息传播网络指出图卷积的核心在于定义节点之间的聚合函数，基于聚合函数，每个节点可以表示为周围节点和自身的信息叠加。消息传播网络分为两个步骤，首先将聚合函数作用在每个节点及其邻近节点上，得到节点的局部结构表达；然后，将更新函数作用在自身和局部结构表达上，得到当前节点的新表达。m_x^{t 1}=sumlimits_{yin N(x)}M_t(h_x^t,h_y^t,e_{x,y}),h_x^{t 1}=U_t(h_x^t,m_x^{t 1})，其中h_x^t表示第t步节点x的隐层表示，e_{x,y}表示节点x,y的连边特征，M_t表示第t步的聚合函数，m_x^{t 1}表示节点x通过聚合函数得到的局部结构表达，U_t表示第t步的更新函数，通过将神经网络的每一层设计成上述的聚合函数和更新函数，每个节点可以不断以自身和邻近节点为原信息更新自身，进而得到依赖于节点局部结构的新表达。

在以上空间框架下，一些方法不在依赖于拉普拉斯矩阵，而是设计神经网络来学习聚合函数。这些方法学到的聚合函数可以自适应于任务和具体的结构，有更大的灵活性。

图神经网络(GNNs)

图神经网络是最早提出在图上搭建神经网络的模型。在图神经网络中，聚合函数被定义成循环递归函数的形式，每个节点以周围节点和连边作为来源信息更新自身的表达，h_x=f_w(l_x,l_{c0[x]},l_{ne[x]},h_{ne[x]})，其中，l_x,l_{c0[x]},l_{ne[x]},h_{ne[x]}分别表示节点x的标签，与节点x相连的边的标签，x的邻居节点的标签，以及x的邻居节点上一个时间步的表达，f_w是聚合函数，其在文章中被定义成递归函数，根据f_w迭代更新节点x的表达直到收敛。图神经网络定义全局输出函数并作用在收敛后每个节点的表达上得到输出结果，我们用g_w表示全局输出函数，最终结果为o_x=g_w(h_x,l_x)。

图注意力网络(GAT)

图注意力网络通过注意力机制定义聚合函数，但是和以往关心边上信息的模型不同，在图注意力网络中，邻接矩阵仅被用来定义相关节点，而关联权重的计算则是依赖节点的特征表达。图注意力网络以节点的特征表达作为输入，计算注意力权重并归一化，利用注意力权重将周围节点的表达以加权和的形式聚合到自身，对于多种注意力机制下的计算结果，图注意力网络提供了拼接和均值两种计算方式。

alpha_{i,j}=frac{exp(LeakyReLU(a[Wh_i | Wh_j]))}{sumlimits_{kin N(i)}exp(LeakyReLU(a[Wh_i|Wh_k]))}

h_i=sigma(sumlimits_{jin N(i)}alpha_{i,j}Wh_i)，其中参数W用于完成每个节点的特征维度变换，参数alpha用于计算节点间的注意力权重，|表示向量拼接，alpha_{i,j}表示在alpha下计算得到的i,j节点间的权重，sigma表示非线性激活函数。缺点：模型处理时需要加载整个网络的节点特征，不适合于大规模网络。

图采样聚合网络(GraphSAGE)

图采样聚合网络对邻近节点做随机采样，使得每个节点的临近节点都小于给定的采样个数。

图采样聚合网络给出多种聚合函数的形式，分别是基于最大值的聚合，基于均值的聚合和长短时记忆网络(LSTM)。

最大值聚合和均值聚合分别取相关节点的最大值和均值作为聚合结果，长短时记忆网络指将相关节点输入LSTM，并把输出作为聚合结果。图采样聚合网络也提出了用分批量(Mini-batch)处理数据的方法训练模型，在每个批量输入数据下只需要加载对应节点的局部结构，避免了整张网络的加载。

DCNN

DCNN利用随机行走后得到的K跳转移概率定义节点间的权重，第m层的结构如下：H^{m 1}=h(P^KH^mW)，其中P^K表示两个节点在随机行走下K跳可达概率，W是需要学习的参数。此类模型刻画了节点之间的高阶信息，但是由于P^K的计算复杂度为O(n^2K)，难以扩大到大图上。

基于置信度的图卷积网络(ConfGCN)

ConfGCN认为节点是以一定的置信度为一个标签，因此ConfGCN给每个节点学习置信度函数，并将其作用在节点相关性上，修正聚合函数。

超图卷积网络(HGNN)

HGNN认为节点间的相关性不应该是节点两两之间产生，而是一组节点相互影响进而构建组内节点相关性。基于此想法，HGNN将边拓展到连接多个节点的超边，在超边上定义聚合函数进行节点特征传播。

以上基于聚合函数的空间方法着眼于空间方法中的根本问题，即聚合函数的构造。

当一个模型满足以下性质时：仅当两个节点的特征一致且局部结构一致时，这两个节点才会被映射到相同的位置，该模型被称为能力最强的图卷积网络。基于这种定义，均值聚合的能力大于最大值聚合的能力，小于求和聚合的能力。均值聚合关心节点的特征分布，当节点特征各异时，均值聚合能力等同于求和聚合。

所有的谱方法都是空间方法，只是有显式变换空间的方法。

Spectral CNN

y=Ug_theta U^Tx=(theta_1u_1u_1^T theta_2u_2u_2^T ... theta_nu_nu_n^T)x

ChebNet

y=(theta_0I theta_1L theta_2L^2 ... theta_{K-1}L^{K-1})x

GCN

y=theta(I-L)x

图上信号x的平滑性通过x^TLx=sumlimits_{(u,v)in E}A_{uv}big(tfrac{x_u}{sqrt{d_u}}-tfrac{x_v}{sqrt{d_v}}big)^2 lambda_i=u_i^TLu_i

图池化操作

池化算子一方面能减少学习的参数，另一方面能反映输入数据的层次结构。在图卷积神经网络中，在解决节点级别的任务如节点分类、链接预测时，池化算子并非必要。在图操作中使用池化算子，主要目的是刻画出网络的等级结构。

切比雪夫网络(ChebyNet)

ChebyNet利用完全二叉树实现池化算子，其提出基于Graclus贪婪准则为每个节点计算最为匹配的节点，并将此对节点池化为一个节点。同时，ChebyNet通过增加虚假节点保证池化过程是一个完全二叉树。

微分池化模型(DIFFPOOL)

DIFFPOOL提出将图神经网络应用于节点嵌入和池化操作，模型在第l层学习到一个类别分配矩阵S^{(l)}in R^{n_ltimes n_{l 1}}，S^{(l)}的每一行对应于l层次n_l类，每一列对应于l层的n_{l 1}节点。对于给定l层，输入的节点表达矩阵为Z^{(l)}，产生新的粗粒度的l层邻接矩阵A^{(l 1)}和新的表达矩阵X^{(l 1)}，即A^{(l 1)},X^{(l 1)}=DIFFPOOL(A^{(l)},Z^{(l)})，具体的计算过程如下：

X^{(l 1)}=S^{(l)T}Z^{(l)},A^{(l 1)}=S^{(l)T}A^lS^{(l)},

Z^{(l)}=GNN_{l,embed}(A^{(l)},X^{(l)}),

S^{(l)}=softmax(GNN_{l,pool}(A^{(l)},X^{(l)}))

该模型被用来做软聚类和网络节点表示学习，其需要存储分配矩阵，因此空间复杂度为O(kV^2),k为池化比例。Cangea等人提出丢掉N-kN个节点代替聚合这些节点表达，该方法能够减少内内存的开销，从而可以建模更大规模的网络结构。

谱池化(EigenPooling)

谱池化利用谱聚类将整个图划分成几个不存在重叠的子图，而每个子图即作为池化后的一个新节点，新节点间的连边则基于原子图连边产生。EigenPooling可以控制每次划分后的子图个数，进而控制每一层的池化比例。

基于注意力机制的池化算子(SAGPool)

在池化过程中考虑节点属性信息和结构信息，SAGPool基于注意力机制通过结构和属性信息为每个节点学到一个标量，以此标量表征对应节点在整个图上的重要性，并对此标量进行排序，根据排序结果保留最重要的一部分节点及其连边进而完成池化操作。

图卷积神经网络的新进展

部分的空间方法忽略了边上的属性，高阶网络结构等信息。

建模边上信息的图卷积网络

边是网络重要的组成部分，刻画了节点之间的关联关系。实际中不同网格的边包含的信息也大不相同：低维离散的类型信息、低维连续的权重信息、高维连续的属性信息等。

子图拆解法

将包含复杂额外信息的网格化数据拆解成多个不同的子图，拆解后每个子图只包含单一的连边类型，对拆解后的每个子图利用传统的图卷积神经网络建模，最后将不同子图上得到的结果按特定方式进行聚合。

关系图神经网络(R-GCNs)

关系图神经网络根据连边的方向、边上的标签类型将原来的网络拆分成不同的子网络，在每个子图上独立地进行邻居特征的聚合，每一层在聚合操作结束后，将节点在不同子图上得到的结果相加，作为下一层网络的输入。关系图神经网络的卷积操作可以形式化成：h_i^{l 1}=sigma(sumlimits_{rin R}sumlimits_{jin N_i^r}tfrac{1}{c_{i,r}}W_r^{(l)}h_j^{(l)} W_0^{(l)}h_i^{(l)}),其中c_{i,r}是归一化因子，可以根据不同任务进行选择，常见方式是用邻居个数作为归一化因子。R表示不同的边类型，W_r^l表示第l层对于边类型为r的子图需要学习的参数。

关系图注意力网络(R-GAT)

关系图注意力网络在关系图神经网络的基础上引入了注意力机制，作者提出了两种引入注意力机制的邻居聚合函数替换关系图神经网络中只利用网络结构的聚合函数，进一步提升了实验结果。关系图神经网络和关系图注意力网络更适用于具有离散类型的边特征的网络。

符号图卷积网络(SGCN)

符号网络(signed network)是一种特殊的边上包含类型信息的网络，除了包括“朋友关系”，“敌对关系”两种类型的连边，符号网络还具有结构平衡等特殊的社会学性质。例如：敌人的敌人是朋友。

符号图卷积网络针对符号网络的特殊性质进行设计。在符号图卷积网络中，每个节点包含“朋友表达”和“敌人表达”两部分，分别利用“朋友”聚合器和“敌人”聚合器学习得到。

对偶图构建法

此类方法通过构建对偶网络的方式，将原网络中的边转换成对偶网络中的节点，将原图中边上的特征转移到了对偶图的节点上，对偶图的连边不再具有特征，因此可以在对偶图上直接应用传统图卷积神经网络，同时原图中边上特征变成了对偶图中节点上的特征，可以通过在对偶图上定义的图卷积刻画。

原始对偶图卷积神经网络(DPGCNN)

原始对偶图卷积神经网络提出了一种构建对偶网络的方法。原始对偶图卷积神经网络将原网络中的边映射成对偶网络中的节点，同时，如果原网络中的两条边有共同节点，那么着两条边对应的对偶网络中的节点存在一条连边，此外，原网络上的边的特征被保存在对偶网络的节点上。

原始对偶图卷积神经网络分别在对偶网络和原始网络上定义了对应的卷积操作，对偶卷积形式如下：

widetilde{f}{ij}^{'}=xi_d(sumlimits{rin N_i}widetilde{alpha}{ij,ir}widetilde{f}{ir}widetilde{W} sumlimits_{tin N_j}widetilde{alpha}{ij,tj}widetilde{f}{tj}widetilde{W})

widetilde{alpha}{ij,ik}=tfrac{e^{eta(widetilde{alpha}([widetilde{f}{ij}widetilde{W},widetilde{f}{ik}widetilde{W}]))}}{sumlimits{rin N_i}e^{eta(widetilde{alpha}([widetilde{f}{ij}widetilde{W},widetilde{f}{ir}widetilde{W}]))} sumlimits_{tin N_j}e^{eta(widetilde{alpha}([widetilde{f}{ij}widetilde{W},widetilde{f}{tj}widetilde{W}]))}}

其中，xi_d表示对偶网络中的激活函数，例如ReLU，f_i表示原图中节点i的特征，widetilde{f}{ij}^{'}表示对偶网络中节点(i,j)的特征（对应原网络中边<i,j>widetilde{f}{ij}^{'}=[f_i,f_j]，也可以同时使用两者。其中widetilde{W}表示要学习的参数，eta表示LeaklyReLU激活函数，N_i表示源网络中节点i的邻居节点构成的集合。

原始卷积与传统图注意力网络的形式类似，唯一的区别在于计算注意力系数时输入特征采用的是由对偶卷积计算得到的边上的特征，f_i^{'}=xi_P(sumlimits_{rin N_i}alpha_{ij}f_iW),alpha_{ij}=tfrac{e^{eta(alpha(widetilde{f}{ij}^{'}))}}{sumlimits{kin N_i}e^{eta(alpha(widetilde{f}_{ik}^{'}))}}

直观上理解，对偶图上的图卷积网络，为原始图中每一条边学到了一个表示，该表示能反映节点特征沿着这条边传播的权重，而原始图中的图卷积网络依据边的传播权重，进行特征的传播，为节点学习表达。该方法适用于具有高维边特征的场景，但是需要将原网络转换为对偶网络。实际中，边数大于节点数往往会使得对偶网络规模大于原网络。

权重重调法

此类方法认为边上的特征信息只会影响中心节点聚合邻居节点特征的权重，因此这类方法在计算聚合权重时引入了边上的特征信息。

边注意力网络(EGAT)

EGAT定义卷积操作如下：x_{i}^{'}=sigma[|{p=1}^P(sumlimits{jin N_i}alpha(x_i,x_j,e_{ijp})g(x_j))],g(x_j)=Wx_j，其中P表示边上特征的维度，e_{ijp}表示连边<i,j>p维上的值，g(x_i)=Wx_i表示节点i经过线性变换后的特征。W是要学习的参数，x_j是输入特征。边注意力网络改变了传统图注意力网络计算节点之间注意力权重的方式，将边上的特征也作为一个重要的输入参与权重的计算。具体形式如下：alpha(x_i,x_je_{ijp}=tfrac{1}{C_{ip}}f(x_i,x_j)e_{ijp},C_{ip}=sumlimits_{jin N_i}f(x_i,x_j)e_{ijp})，其中C_{ip}是归一化因子

边约束卷积网络(ECC)

ECC 将图上连边的类型用低维向量表示，并将这些向量通过单层线性神经网络转化为该连边对应两个节点间的聚合权重。该方法仅考虑了边上特征各个维度之间的关系，忽略了两端节点特征之间的相似性。

建模网络高阶信息的图卷积网络

高阶图卷积神经网络(HA-GCN)

HA-GCN用k阶邻接矩阵hat{A}k替换GCN中的hat{A}。同时为了区分每个节点的重要性，HA-GCN引入了元素级的自适应权重矩阵，高阶图卷积神经网络的卷积层形式化如下：hat{L}{HA}^{(k)}=(widetilde{W}_kodothat{A}^k)X B_k，其中，hat{A}^k表示k阶邻接矩阵，B_k表示第k阶的偏置矩阵，widetilde{W}^k表示自适应权重矩阵，根据节点的特征、邻接关系以及原始权重矩阵计算得到，widetilde{W}k=godot W_k,g==f{adp}=(hat{A}^k,X)，其中，g是非线性算子（单层神经网络），输入特征由节点的特征和高阶邻接矩阵的拼接得到。

模体卷积网络(Motif-CNN)

模体卷积网络通过显示定义模体，来区分邻居节点对中心节点不同的语义作用。模体卷积网络利用模体来定义网络上的卷积算子，根据节点的语义角色信息来共享参数，其卷积形式如下：h^M(v_i)=sigma(w_0x_i tfrac{1}{D_{ii}^M}sumlimits_{j=1}^Nsumlimits_{k=1}^{K_M}w_k(A){kij}^Mx_j)，其中D^M是对角矩阵，对角元素表示每个节点参与的不同的模体的个数。A^M是邻接模体张量，A{k,i,j}^M表示节点j以k角色出现在以节点i为中心的模体实例M的次数。w_k是共享参数，相同语义角色的节点之间共享参数。模体卷积网络采用注意力机制给不同的模体学习重要程度的权重，形式如下：e_{k,i}=a(h^k(v_i),z_k)=tfrac{z_k^Th^k(v_i)}{sqrt{|z_k|}}, a_{k,i}=softmax_k(e_{k,i}=tfrac{exp(e_{k,i})}{sumlimits_{j=1}^Uexp(e_{j,i})})，模体卷积网络采用点积计算注意力权重，其中z_K表示模体M_K的共享注意力向量，不同的模体独立计算注意力权重，不共享参数。a_{k,i}表示节点i在模体k下的注意力权重，h(v_i)=sumlimits_{k=1}^Ualpha_{k,i}h^k(v_i)，最终目标节点的表达由不同模体下表达的加权和得到。

异质注意力网络(HAN)

HAN用元路径来定义卷积操作，对于同一种元路径共享参数。

模体卷积决策网络(MCN)

MCN认为选择邻居节点集合就是为每个节点选择最合适的模体关系，而共同在模体中出现的频率作为聚合权重。与之前的方法类似，模体卷积决策网络也通过定义k步模体矩阵的方式构建候选的邻居节点集合。模体决策网络采用T种不同的模体结构，每一种模体计算K个不同步长的模体矩阵。k阶模体定义和k阶邻接矩阵类似，为k个相同模体矩阵的乘积。Psi(A_t^k)=Psi(A_tcdots A_t)。

模体卷积决策网络的决策过程分为两步：第一步选择与目标节点最相关的模体，第二步选择最相关的步长。才用注意力机制计算模体被选中的概率以及各个步长的相关程度。模体卷积决策网络目标函数包含两个部分：分类的损失函数以及决策的损失函数。分类的损失函数使用交叉熵度量节点分类的准确性，而决策的损失函数用来衡量决策的准确性，对于每个节点v，如果分类准确则回报为正，否则为负。由于每一层决策的结果都会影响最终的结果，此方法通过为每一层的所有节点都计算回报来约束每一层都作出正确的决策。

卷积神经网络神经网络

0 人点赞

论文阅读01——《图卷积神经网络综述》