【图神经⽹络】图神经⽹络（GNN）学习笔记：图分类 图神经⽹络GNN学习笔记：图分类
图分类问题是⼀个重要的图层⾯的学习任务，需要关注图数据的全局信息，包括图的结构信息以及各个节点的属性信息。 给定多张图，以及每张图对应的标签，图分类任务需要通过学习得出⼀个由图到相应标签的图分类模型，重点在于如何通过学习得出⼀个优秀的全图表⽰向量。 在图分类任务中实现层次化池化的机制，是GNN需要解决的基础问题。 1. 基于全局池化的图分类 在MPNN中，除了为图中节点的表⽰学习提供了⼀般框架外，作者也涉及了⼀个读出（readout）机制对经过K轮迭代的所有结点进⾏⼀次性聚合操作，从⽽输出图的全局表⽰： y = R ( { h i ( k ) ∣ ∀ v j ∈ V } ) y=R(\{h_i^{(k)|\forall v_j\in V}\}) y=R({hi(k)∣∀vj∈V}) 读出机制与CNN模型中常⽤的紧跟最后⼀个卷积层的全局池化（Global Pooling）操作如出⼀辙。都是通过对所有输⼊的⼀次性聚合得到全局表达，且与池化的常见类型⼀样，读出机制也可以取Sum、Mean、Max等类型的函数。 另⼀种⽅式是引⼊⼀个与所有结点都相连的虚拟节点，将全图的表⽰等价于这个虚拟节点的表⽰。这种思虑也在GN中全局表⽰ u u u的更新过程中得到了体现。 显然，读出机制丢失了图数据⾥丰富的结构信息，其本质是将输⼊数据看作⼀种平整且规则的结构数据，所有的结点都被同等看待，这与图数据本⾝相违背。因此，读出机制更适应对⼩图数据的学习，⼀⽅⾯是因为⼩图数据结构信息单⼀，另⼀⽅⾯是经过K轮消息传播机制的迭代之后，图中各个结点的表达会更加接近全局表达，此时读出机制也能较好地提取全局信息，⽽且，读出机制易于实现，⾮常适合作为 蛇形线
图分类的基准模型。 2. 基于层次化池化的图分类 列举3中不同的思路介绍能够实现图数据层次化池化的⽅案： （1）基于图坍缩（Graph Coarsening）的池化机制：图坍缩是将图划分为不同的⼦图，然后将⼦图视为超级节点，从⽽形成⼀个坍缩的图。 （2）基于TopK的池化机制：对图中每个节点学习出⼀个分数，基于这个分数的排序丢弃⼀些低分数的节点，这类⽅法借鉴了CNN中最⼤池化操作的思路：将更重要的信息筛选出来。不同的是，图数据难以实现局部滑窗操作，因此需要依据分数进⾏全局筛选。 （3）基于边收缩（Edge Contraction）的池化机制：边收缩是指并⾏地将图中的边移除，并将被移除边的两个节点合并，同时保持被移除节点的连接关系，该思虑是⼀种通过归并操作来逐步学习图的全局信息的⽅法。 2.1 基于图坍缩的池化机制 1 图坍缩 假设对于图G，通过某种划分策略得到K个⼦图 { G ( k ) } k = 1 K \{G^{(k)}\}_{k=1}^K {G(k)}k=1K， N k N_k Nk 表⽰⼦图 G ( k ) G^{(k)} G(k)中的节点数， Γ ( k ) \Gamma^{(k)} Γ(k)表⽰⼦图 G ( k ) G^{(k)} G(k)的节点列表。 图坍缩就是将图中的节点划分为⼏个节点簇，每个节点簇作为下⼀次图坍缩的节点。下⾯给出图坍缩中的两个⽐较重要的矩阵： 第⼀个是簇分配矩阵 S ∈ R N × K S\in R^{N\times K} S∈RN×K，其定义如下： S i j = 1 S_{ij}=1 Sij=1当且仅当 v i ∈ Γ ( j ) v_i\in \Gamma^{(j)} vi∈Γ(j)。令 A c o a r = S T A S A_{coar}=S^TAS Acoar=STAS，描述了图坍缩之后的超级节点之间的连接强度，设置 A c o a r [ i , i ] = 0
A_{coar}[i,i] = 0 Acoar[i,i]=0。第⼆个是采样算⼦ C ∈ R N × N k C\in R^{N\times N_k} C∈RN×Nk，其定义为 C i j ( k ) = 1
供水控制器C_{ij}^{(k)}=1 Cij(k)=1，当且仅当 Γ j ( k ) = v i \Gamma_j^{(k)}=v_i Γj(k)=vi。其中， Γ j ( k ) \Gamma_j^{(k)} Γj(k)表⽰列表 Γ( k ) \Gamma^{(k)} Γ(k)中的第j个元素。C是节点在原图和⼦图中顺序关系的⼀个指⽰矩阵。 假设定义在G上的⼀维图信号为 x ∈ R N
x\in R^N x∈RN，下列两式分别完成了对图信号的下采样于上采样操作： x ( k ) = ( C ( k ) ) T x ， x ˉ = C ( k ) x ( k ) x^{(k)}=
(C^{(k)})^Tx，\bar{x}=C^{(k)}x^{(k)} x(k)=(C(k))Tx，xˉ=C(k)x(k)，上述左式完成了对图信号在⼦图 G ( k ) G^{(k)} G(k)上的采样（切⽚）功能；右式完成了⼦图信号 x ( k ) x^{(k)} x(k)在全图的上采样功能。该操作保持⼦图中节点的信号值不变，同时将不属于该⼦图的其他节点的值设置为0。显然，该采样算⼦也适⽤于多维信号矩阵 X ∈ R N × d X\in R^{N\times d} X∈RN×d。 有了采样算⼦的定义，对于⼦图 G ( k ) G^{(k)} G(k)的邻接矩阵 A ( k ) ∈ R N k × N k A^{(k)}\in R^{N_k\times N_k} A(k)∈RNk×Nk，可以通过下式获得（事实上， A ( k ) A^{(k)} A(k)也可以通过对A进⾏矩阵的双向切⽚操作获得）： A ( k ) = ( C ( k ) ) T A C ( k ) A^{(k)}=
(C^{(k)})^TAC^{(k)} A(k)=(C(k))TAC(k) 通过 A c o a r = S T A S A_{coar}=S^TAS Acoar=STAS和 A ( k ) = ( C ( k ) ) T A C ( k ) A^{(k)}=(C^{(k)})^TAC^{(k)} A(k)=(C(k))TAC(k)可以确定簇内的邻接关系以及簇间的邻接关系。进⼀步讲，如果能够确定簇内信号的融合⽅法，将结果表⽰为超级节点上的信号，那
么迭代地重复上述过程，就能够获得越来越全局的图信号了。 上图即为图塌缩与GNN结合的过程：该图展⽰了⼀个经过3个池化层最后坍缩成⼀个超级节点，然后进⾏图分类任务的GNN模型。在得到最后⼀个超级节点的特征向量之后，使⽤了⼀个三层的MLP⽹络进⾏图分类任务的学习。 ⽬前DIFFOOL和EigenPooL是两种基于图坍缩的图神经⽹络算法。 2 DIFFPOOL DIFFPOOL是⾸个将图坍缩过程与GNN结合起来进⾏图层⾯任务学习的算法。DIFFPOOL提出了⼀个可学习的簇分配矩阵。具体来说，⾸先通过⼀个GNN对每个节点进⾏特征学习，然后通过另⼀个GNN为每个节点学习出所属各个簇的概率分布： Z ( l ) = G N N l , e m b e d ( A ( l ) , H ( l ) ) Z^{(l)}=GNN_{l,embed}(A^{(l)},H^{(l)}) Z(l)=GNNl,embed(A(l),H(l)) S ( l ) = s o f t m a x ( G N N l , p o o l ( A ( l ) , H ( l ) ) ) S^{(l)}=softmax(GNN_{l,pool}(A^{(l)},H^{(l)})) S(l)=softmax(GNNl,pool(A(l),H(l))) 其中 A ( l ) ∈ R n ( l )× n ( l ) , S ( l ) ∈ R n ( l ) × n ( l + 1 ) A^{(l)}\in R^{n^{(l)}\times n^{(l)}}, S^{(l)}\in R^{n^{(l)}\times n^{(l+1)}}
A(l)∈Rn(l)×n(l),S(l)∈Rn(l)×n(l+1)， n ( l ) n^{(l)} n(l)表⽰第 l l l层的节点数， n ( l + 1 ) n^{(l+1)} n(l+1)表⽰第 ( l + 1 ) (l+1)
(l+1)层的节点（簇）数，相较于上⽂ S S S矩阵的硬分配，这⾥学习出来的 S S S矩阵是⼀个软分配器，其值表⽰节点被分配到任意⼀个簇的概率，由于概率值不为0，因此这是⼀个下层超级节点到上层所有节点之间的全连接结构。 G N N l , e m b e d GNN_{l,embed} GNNl,embed, G N N l , p o o l GN
N_{l,pool} GNNl,pool是两个独⽴的GNN层，⼆者的输⼊相同，但是参数不同，学习的⽬的不同。需要强调⼀点的是，对于最后⼀层的簇分配矩阵，需要直接将该矩阵固定成⼀个全“1”的矩阵，这是因为，此时需要将图坍缩成⼀个超级节点，由此获得图的全局表⽰。 有了上述两个式⼦的输出结果，可以对图进⾏坍缩： H ( l + 1 ) = S ( l ) T Z ( l )
三基光源H^{(l+1)}=S^{(l)^T}Z^{(l)} H(l+1)=S(l)TZ(l) A ( l + 1 ) = S ( l ) T A ( l ) S ( l ) A^{(l+1)}=S^{(l)^T}A^{(l)}S^{(l)}
A(l+1)=S(l)TA(l)S(l) 这⾥将上述两个公式成为DIFFPOOL层（ ( A ( l ) , Z ( l ) ) → ( A ( l + 1 ) , H ( l + 1 ) )
(A^{(l)},Z^{(l)})\rightarrow (A^{(l+1)}, H^{(l+1)}) (A(l),Z(l))→(A(l+1),H(l+1))）。 H ( l + 1 ) = S ( l ) T Z ( l )
H^{(l+1)}=S^{(l)^T}Z^{(l)} H(l+1)=S(l)TZ(l)是对簇内的信息执⾏融合操作， S ( l ) T Z ( l ) S^{(l)^T}Z^{(l)} S(l)TZ(l)表⽰的是对簇内所有节点的特征向量进⾏加和处理。 A ( l + 1 ) = S ( l ) T A ( l ) S ( l ) A^{(l+1)}=S^{(l)^T}A^{(l)}S^{(l)} A(l+1)=S(l)TA(l)S(l)为簇间的邻接矩阵的计算。 DIFFPOOL具有排列不变性：假设 P ∈ { 0 , 1 } n × n P\in \{0,1\}^{n\times n} P∈{0,1}n×n是⼀个任意的排列矩阵，只需要保证前⾯⽤到的GNN层是排列不变的，DIFFPOOL层就具有排列不变性，即 D I F F P O O L ( A , Z )
= D I F F P O O L ( P A P T , P X ) DIFFPOOL(A,Z)=DIFFPOOL(PAP^T, PX) DIFFPOOL(A,Z)=DIFFPOOL(PAPT,PX)，排列矩阵的作⽤是对图中节点进⾏重排序，⽐如⼀个仅有两个节点向量的图，如果我们需要将两个节点的编号进⾏对调，则对应的排列矩阵 P = [ 0 1 1 0 ] P=[0110] [0110] P=[0110]，排列矩阵是正交的，即 P T P = I P^TP=I PTP=I。可以通过 P X , P A P T PX, PAP^T PX,PAPT来分别获得重排序之后的特征矩阵与邻接矩阵。 总的来说，节点是否重新排序并不应该影响节点聚合成簇的结果。 有了上述DIFFPOOL层的定义，就可以模仿CNN分类模型的结构设计，不断组合堆叠GNN层与DIFFPOOL层，实现⼀种可导的、层次化池化的学习机制，并逐渐获得图的全局表⽰。 3. EigenPooling EigenPooling是⼀种基于图坍缩的池化机制。它没有对图分类模型引⼊任何需要学习的参数，这种⾮参的池化机制与视觉模型中的各类池化层具有很⾼的类⽐性。 表1 EigenPooling与视觉模型中的池化⽐较 性质EigenPooling视觉模型中的Pooling前置层类型GNNCNN作⽤域⼦图滑窗作⽤域的选取图分区算法（⽐如⽤谱聚类对图划分⼦图）设定超参数，⽐如2×2的窗⼝⼤⼩具体池化操作基于⼦图的傅⾥叶变换取最⼤值或均值池化层是否带参否否 EigenPooling的具体过程中，其核⼼步骤在于作⽤域的选取以及池化操作，作⽤域是通过划分⼦图的⽅式对图进⾏分区得到的，这等价于图坍缩的过程，通过这⼀步可以得到新的超级节点之间的邻接矩阵。池化操作需要考虑的是对作⽤域内的信息进⾏融合，通过这⼀步可以得到关于新的超级节点的特征矩阵。 注意：在视觉模型中池化操作的作⽤域都是规则的栅格结构，⽽在图坍缩的⼦图上，作⽤域内的信息包含了结构信息与属性信息，特别是结构信息，不同的⼦图间有⽐较⼤的区
别，EigenPooling就同时考虑了这两种信息并进⾏了融合。 （1）图坍缩 EigenPooling中的图坍缩并没有给图分类模型引进任何需要学习的参数，其思路是借⽤⼀些图分区的算法来实现图的划分，⽐如谱聚类算法。 谱聚类是⼀类⽐较典型的聚类算法，其基本思路是先将数据变换到特征空间以凸显更好的区分度，然后执⾏聚类操作，⽐如选⽤Kmeans算法进⾏聚类，算法的输⼊是邻接矩阵以及簇数K，输出的是每个节点所属的簇。 注意：如果选⽤Kmeans算法进⾏聚类，那么簇的分配就是⼀种硬分配，每个节点仅能从属于⼀个簇，这种硬分配保持了图坍缩之后的超级节点之间连接的稀疏性。⽽DIFFPOOL中的是软分配机制，节点以概率的形式分配到每⼀个簇中，导致超级节点之间以全连接的形式彼此相连，增加了模型的空间复杂度和时间复杂度。 将图进⾏划分之后，调⽤ A c o a r = S T A S A_{coar}=S^TAS Acoar=STAS就可以得到超级节点间的邻接关系，当然，EigenPooling在这⼀步没有考虑超级节点簇内的连接强度。 （2）池化操作 在确定了⼦图划分以及相应的邻接矩阵之后，需要对每个⼦图内的信息进⾏整合抽取。在DIFFPOOL中选择了对节点特征进⾏加和，这种⽅式损失了⼦图的结构信息，⽽EigenPooling⽤⼦图上的信号在盖⼦图上的图傅⾥叶变换来代表结构信息与属性信息的整合输出。 图信号的频谱展⽰了图信号在各个频率分量上的强度，它是将图的结构信息与信号本⾝的信息统⼀考虑进去，⽽得到的⼀种关于图信号的标识信息。因此，EigenPooling选⽤了频谱信息来表⽰⼦图信息的统⼀整合。 假设⼦图 G ( k ) G^{(k)} G(k)的拉普拉斯矩阵为 L ( K ) L^{(K)} L(K)，对应的特征向量为 u 1 ( k ) , u 2 ( k ) , . . . , u N k ( k ) \vec{u}_1^{(k)}, \vec{u}_2^{(k)},..., \vec{u}_{N_k}^{(k)} u 1(k),u 2(k),...,u Nk(k)，然后，使⽤上采样算⼦ C ( k ) C^{(k)} C(k)将该特征向量
（⼦图上的傅⾥叶基）上采样到整个图： u ˉ l ( k ) = C ( k ) u l ( k )， l = 1 , . . . , N k \bar{\vec{u}}_l^{(k)}=C^{(k)}\vec{u}_l^{(k)}，l=1,...,N_k u ˉl(k)=C(k)u l(k)，l=1,...,Nk为了将上述操作转换为矩阵形式，以得到池化算⼦ Θ l ∈ R N × K \Theta _l\in R^{N\times K} Θl∈RN×K，将所有⼦图的第 l l l个特征向量按⾏⽅向组织起来形成矩阵 Θ \Theta Θ，即 Θ l = [ u ˉ l ( 1 ) , . . . , u ˉ l ( k ) ] \Theta_l=[\bar{\vec{u}}_l^{(1)}, ..., \bar{\vec{u}}_l^{(k)}] Θl=[u ˉl(1),...,u ˉl(k)] 注意，⼦图的节点数量是不同的，所以特征向量的数量也不同。⽤ N m a x = max k = 1 , . . . , K N k
锻打刀N_{max}=\max_{k=1,...,K} N_k Nmax=maxk=1,...,K N k表⽰⼦图中的最⼤节点数。然后，若⼦图 G ( k ) G^{(k)} G(k)的节点数⼩于 N
m a x N_{max} Nmax，可以将 u ˉ l ( k ) ( N k < l < N m a x ) \bar{\vec{u}}_l^{(k)}(N_k<l<N_{max}) u ˉl(k)(Nk<l<Nmax)设置为 0∈ R N k × 1 0\in R^{N_k\times 1} 0∈RNk×1。 有了池化算⼦的矩阵形式，池化过程可描述为： X l = Θ l T X X_l=\Theta_l^TX
Xl=ΘlT X X l ∈ R K × d X_l\in R^{K\times d} Xl∈RK×d是池化的结果。 X l X_l Xl的第 k k k⾏表⽰的是第 k k k个超级节点在 Θ l \Theta_l Θl作⽤下的表⽰向量。按照该机制，共需要设计 N m a x N_{max} Nmax个池化算⼦。为了结合不同池化算⼦收集到的信息，可以采⽤按列⽅向拼接的⽅式，将各个结果连接起来： X p o o l e d = [ X 0 , . . . , X N m a x ] X_{pooled}=[X_0,...,X_{N_{max}}] Xpooled=[X0,...,
网络分配器
XNmax] 其中 X p o o l e d ∈ R K × ( d ⋅ N m a x ) X_{pooled}\in R^{K\times (d\cdot N_{max})} Xpooled
∈RK×(d⋅Nmax)是EigenPooling最终的池化结果。 为了提⾼计算效率，选择使⽤前H个特征向量对应的池化结果，⼀般为 H < < N m a x H<<N_{max} H<<Nmax： X c o a r = X p o o l e d = [ X 0 , . . . , X H ] X_{coar}=X_{pooled}=[X_0,...,X_H] Xcoar=Xpooled=[X0 ,...,XH] 上述计算都在矩阵层⾯上进⾏，如果将计算回到向量形式上，可以清楚地看到EigenPooling是怎么利⽤图傅⾥叶变换对⼦图信息进⾏整合的。不失⼀般性，设全图上的信号为 x \vec{x} x ，则 X l = Θ l T X X_l=\Theta_l^TX Xl=ΘlT X可描述为： ( u ˉ l ( k ) ) T x = ( u ˉ l ( k ) ) T ( C ( k ) ) T x = ( u l ( k ) ) T x ( k ) (\bar{\vec{u}}_l^{(k)})^Tx=(\bar{\vec{u}}_l^{(k)})^T(C^{(k)})^Tx=
(\vec{u}_l^{(k)})^Tx^{(k)} (u ˉl(k))Tx=(u ˉl(k))T(C(k))Tx=(u l(k))Tx(k) 其输出表⽰⼦图上的信号在⼦图上对应的第 l l l个特征向量上的傅⾥叶系数。 同DIFFPOOL⼀样，如果EigenPooling的前置GNN层选⽤GCN的话，EigenPooling整体也将具有排列不变性。总的来说，EigenPooling作为⼀种不带任何学习参数的池化机制，可以⾮常⽅便地整合到⼀般的GNN模型中，实现对图信息的层次化抽取学习。与DIFFPOOL相⽐，主要优势在保持了超级节点之间连接的稀疏性，同时提⾼了计算效率，在进⾏池化操作时，兼顾了⼦图的结构信息与属性信息，相⽐DIFFPOOL具有更⾼的价值。 2.2 基于TopK的池化机制 基于TopK的池化机制，是⼀个不断丢弃节点的过程，其抓住的是图不同尺度的信息。和CNN中
基于局部滑窗的池化操作不同的是，TopK池化将作⽤域放到全图节点上。具体来说，⾸先设置⼀个表⽰池化率的超参数 k , k ∈ ( 0 , 1 ) k,k\in (0,1) k,k∈(0,1)，接着学习出⼀个表⽰节点重要度的值 z z z并对其进⾏降排序，然后将全图中N个节点下采样⾄ k N kN kN个节点。⽤公式表⽰如下： i = t o p − r a n k ( z , k N ) \vec{i} = top-rank(z,kN) i =top−rank(z,kN) X ′ = X i ,
: X'=X_i,: X′=Xi,: A ′ = A i , j A'=A_{i,j} A′=Ai,j X i , ; X_{i,;} Xi,；表⽰按照向量 i \vec{i} i 的值对特征矩阵进⾏⾏切⽚， A i , j A_{i,j} Ai,j表⽰按照向量 i \vec{i} i 的值对邻接矩阵同时进⾏⾏切⽚与列切⽚。 不同于DIFFPOOL，若将N个节点分配给 k N kN kN个簇，会使得模型需要 k N 2 kN^2 kN2的空间复杂度来分配簇信息，⽽基于TopK的池化机制，每次只需要从原图中丢弃 ( 1 − k ) N (1-k)N (1−k)N 个节点即可。 如何学习节点的重要度？作者为图分类模型设置了⼀个全局的基向量 p \vec{p} p ，将节点特征向量在该基向量上的投影当作重要度： z = X p ∣ ∣ p ∣ ∣ z=\frac{X\vec{p}}{||\vec{p}||} z=∣∣p ∣∣Xp 其中 X X X为节点特征向量。该投影机制具有双重作⽤：（1）可以以投影的⼤⼩来确定TopK的排序；（2）投影⼤⼩还起到了⼀个梯度门限的作⽤，投影较⼩的节点仅有较⼩的梯度更新幅度，相对地，投影较⼤的节点会获得更加充分的梯度信息。 论⽂中给出的TopK的模型结构为： 定义gpool层为: z = X p ∣ ∣ p ∣ ∣ , i = t o p − r a n k ( z , k N ) z=\frac{X\vec{p}}{||\vec{p}||}, \vec{i}=top-rank(z,kN) z=∣∣p ∣∣Xp ,i =top−rank(z,kN) X ′ = ( X ⊙ t a n h ( z ) ) i , : X'=(X\odot tanh(z))_{\vec{i},:} X′=(X⊙tanh(z))i ,:A ′ = A i , i A'=A_{i,i} A′=Ai,i其中， z \vec{z} z 为重要度值（节点分数），⽤于进⾏降序排序，计算⽅法是将节点的特征向量在基向量 p \vec{p} p 上进⾏投影。top-rank函数根据 z
\vec{z} z 值选出重要度前 k k k名的节点的下表。然后依据 i \vec{i} i 对原先的特征矩阵X和邻接矩阵A进⾏切⽚操作，相当于丢弃⼀些节点。 在特征矩阵的更新中点乘⼀个 t a n h ( z ) tanh(z) tanh(z)，这相当于利⽤节点的重要度对节点特征做了⼀次收缩变换，进⼀步强化了对重要度⾼的节点的梯度学习。 与基于图坍缩的池化机制相⽐，gpool层采取了层层丢弃节点的做法来提⾼远距离节点的融合效率，但是这种做法会使得其缺乏对所有节点进⾏有效信息融合的⼿段。因此，为了实现有效融合，在gpool层后⾯再加上⼀个readout层实现对该尺度下的图的全局信息的⼀次性聚合。readout层的具体实现⽅式是将全局平均池化与全局最⼤池化拼接起来： s ( l ) = ( 1 N ∑ i = 1 N x i ( l ) ) ∣ ∣ ( max i = 1 N x i ( l ) ) s^{(l)}=(\frac{1}{N}\sum_{i=1}^N x_i^{(l)})||(\max_{i=1}^N x_i^{(l)}) s(l)=(N1i=1∑N x i(l)
)∣∣(i=1maxN x i(l)) 最终，为了得到全图的表⽰，将各层的 s s s相加： s = ∑ l = 1 L s ( l ) s=\sum_{l=1}^L s^{(l)} s=l=1∑L s(l) 其中读出层将平均池化与最⼤池化拼接起来，最终的全局池化是每⼀层池化结果的加和。 如上图所⽰的模型结构中，使⽤了两层gpool层，相应地设置了两层readout层，之后对两层readout层的输出进⾏相加得到全图的向量表⽰，然后送到⼀个MLP⾥⾯进⾏图分类的任务学习。关于丢弃节点的池化机制，⼀种新的⽅式是：⾃注意⼒图池化（SAGPool），该⽅法使⽤了⼀个GNN对节点的重要度进⾏学习，与gpool 全局基向量的设计相⽐，这种基于GNN的⽅式更好地利⽤图的结构信息对节点的重要度进⾏学习。 2.3 基于边收缩的池化机制 EdgePool 核⼼思想是迭代式地将每条边上的节点进⾏两两归并形成⼀个新的节点，同时保留合并前两个节点的连接关系到新节
点上，最终得到全图的特征表⽰。 存在的⼀个问题是：每个节点有多条边，但是每个节点只能从属于⼀条边进⾏收缩，那么该如何选择每个节点所丛属的边
假牙清洁剂
呢？EdgePool对每条边设计了⼀个分数，依据该分数进⾏⾮重复式的挑选与合并。具体操作如下： 对每条边，计算原始分数 r i , j r_{i,j} ri,j： r i , j = w T [ h i ∣ ∣ h j ] + b r_{i,j}=\vec{w}^T[\vec{h}_i||\vec{h}_j]+b ri,j=w T[h i∣∣h j]+b 由于每个节点选择哪条边，需要从其局部邻居出发进⾏考虑，所以，我们对原始分数沿邻居节点进⾏归⼀化： s i j = s o f t m a x j ( r i j ) s_{ij}=softmax_j(r_{ij}) sij =softmaxj(rij) 其中 r i j r_{ij} rij为每条边的原始分数， s i j s_{ij} sij为原始分数沿着邻居节点归⼀化后的分数。得到上述分数后，对所有的 s i j s_{ij} sij进⾏排序，依次选择该分数最⾼的且未被选中的两个节点进⾏合并操作。 上图中，图a计算了图中每条边的原始分数 r
\vec{r} r ，对于⽆向图，将⽅向进⾏双向复制，对于有向图则仅需按照⽅向进⾏后续操作，图b计算了 e r e^r er，节点分数为边⼊度边分数之和。例如图中的节点 D D D的值就是 e 0.5 = 1.6 e^{0.5}=1.6 e0.5=1.6， C C C的值为 e 0.5 + e 1 + e 3 = 1.6 + 2.7 + 20 = 24.5 e^{0.5}+e^{1}+e^{3}=1.6+2.7+20=24.5 e0.5+e1+e3=1.6+2.7+20=24.5。图c沿着⼊边⽅向对每个结点进⾏归⼀化操作，图中的加⿊的边表⽰被选中的进⾏合并的边。注意，在确定 < B , A > <B,A> <B,A>边的时候，尽管 < B , C > <B,C> <B,C>边上具有更⾼的分数0.8，但是C结点已经被选择与D节点合并，因此选择分数次⾼的 < B , A > <B,A> <B,A>边进⾏合并，图d表⽰合并之后的结果。 合并之后新
节点的特征向量 h i j \vec{h}_{ij} h ij为： h i j = max { s i j , s j i } ⋅ ( h i + h j ) \vec{h}_{ij}=\max\{s_{ij},s_{ji}\}\cdot
(\vec{h}_i+\vec{h}_j) h ij=max{sij,sji}⋅(h i+h j) EdgePool与DIFFPOOL⼀样，都是不断对图中所有节点进⾏融合学习，不同的是DIFFPOOL需要⾃⾏设置聚类簇数，⽽EdgePool利⽤边收缩的原理，仅将邻居节点进⾏归并，并将归并⽐率严格控制在0.5，既保留了图的结构信息，有保证了图中连接的稀疏性，空间复杂度更低。 参考资料 [1] [2] 《深⼊理解图神经⽹络：GNN原理解析》 [3] [4] [5] Gilmer J, Schoenholz S S, Riley P F, et al. Neural message passing for quantum chemistry[J]. arXiv preprint
arXiv:1704.01212, 2017. [6] Pham T, Tran T, Dam H, et al. Graph classification via deep learning with virtual nodes[J]. arXiv preprint arXiv:1708.04357, 2017. [7] Ying Z, You J, Morris C, et al. Hierarchical graph representation learning with differentiable pooling[C]//Advances in neural information processing systems. 2018: 4800-4810. [8] Cangea C, VeličkovićP, Jovanović N, et al. [J]. arXiv preprint arXiv:1811.01287, 2018. [9] Diehl F. Edge contraction pooling for graph neural networks[J]. arXiv preprint arXiv:1905.10990, 2019.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议