wordpress 显示小工具,seo关键词排名优化软件怎么选,怎样做网站排名优化,记事本做网站文字居中文章目录 1. Why 图卷积网络GCN#xff1f;2. GCN的原理2.1 GCN的输入2.2 GCN的核心公式2.3 GCN 的核心公式推导的直观理解 3. Why 图注意力网络GAT#xff1f;4. GAT的原理4.1 GAT的输入4.2 GAT的流程及核心公式 References 1. Why 图卷积网络GCN#xff1f;
GCN(Graph Co… 文章目录 1. Why 图卷积网络GCN2. GCN的原理2.1 GCN的输入2.2 GCN的核心公式2.3 GCN 的核心公式推导的直观理解 3. Why 图注意力网络GAT4. GAT的原理4.1 GAT的输入4.2 GAT的流程及核心公式 References 1. Why 图卷积网络GCN
GCN(Graph Convolutional Networks) 首次提出于ICLR2017【https://openreview.net/forum?idSJU4ayYgl】 简单来说在图神经网络出现之前一般的神经网络只能对常规的欧式数据进行处理其特点就是节点有固定的排列规则和顺序如二维网格和一维序列。 在GCN之前CNN、RNN等神经网络模型在CV、NLP等领域都取得了优异的效果但是其都无法很好地解决图结构的数据问题。
【e.g. RNN 一维序列数据】 当对象是自然语言这样的序列信息时是一个一维的结构此时RNN系列被提出通过各种门的操作使得序列前后的信息相互影响从而很好地捕捉序列的特征。关于RNN系列的介绍可参考从RNN讲起(RNN、LSTM、GRU、BiGRU)——序列数据处理网络。
【e.g. CNN 二维图像数据】 对于图像数据是一个二维的结构于是有了CNN模型来提取图片的特征。CNN的核心在于它的kernel(卷积核)简单来说kernel是一个个小窗口在图片上平移通过卷积的方式来提取特征。这里的关键在于图片结构的平移不变形是指系统在输入图像平移后输出结果保持不变。这种特性使得CNN在处理图像时无论目标对象在图像中的位置如何变化都能保持一致的识别效果。因此CNN可以实现参数共享这就是CNN的精髓所在。 上面所提到的图片或者自然语言都是属于欧式空间的数据因此才有维度的概念欧式空间数据的特点就是数据结构很规则。然而在现实生活中其实有很多不规则的数据结构典型的就是图结构也称为拓扑结构。
图结构一般是不规则的可以认为是无限维的一种数据所以它没有平移不变形。每个节点周围的结构可能都是独一无二的因此像CNN、RNN这种模型就不能很好地发挥作用了。因此涌现出了很多处理图结构的方法例如GNN、GAT等。
GCN图卷积神经网络实际上跟CNN的作用一样就是一个特征提取器只不过它的对象是图数据。 GCN精妙地设计了一种从图数据中提取特征的方法从而让我们可以使用这些特征去对图数据进行节点分类node classification、图分类graph classification、边预测link prediction还可以顺便得到图的嵌入表示graph embedding 等等。 2. GCN的原理
2.1 GCN的输入
对于一个图结构数据 G G G其中有 N N N 个节点每个节点都有自己的一个特征表示。 假设这些节点的特征组成了一个特征矩阵 X ∈ R N × D X \in \mathbb R^{N \times D} X∈RN×D其中 D D D 为特征维数。 此外每个节点之间的关系也可以用一个关系矩阵 A ∈ R N × N A \in \mathbb R^{N \times N} A∈RN×N 表示这个矩阵也被称为邻接矩阵(adjaceney matrix)。
GCN模型输入就是节点特征 X X X 和 邻接矩阵 A A A (表示图结构即节点之间的关系).
2.2 GCN的核心公式 首先先给出GCN的核心公式 H ( l 1 ) σ ( D ~ − 1 2 A ~ D ~ − 1 2 H ( l ) W ( l ) ) H^{(l1)}\sigma(\tilde D^{-\frac{1}{2}} \tilde A \tilde D^{-\frac{1}{2}} H^{(l)} W^{(l)}) H(l1)σ(D~−21A~D~−21H(l)W(l)) 其中 A ~ A I N \tilde A A I_N A~AIN I N I_N IN是一个 N N N维单位阵。 之所以要加上一个单位阵是因为邻接矩阵 A A A 的对角线上都是0在更新节点特征表示时会忽略节点自身的特征。 D ~ \tilde D D~ 是 A ~ \tilde A A~ 的度矩阵 D ~ ∑ j A ~ i j \tilde D \sum_j \tilde A_{ij} D~∑jA~ij。 W ( l ) W^{(l)} W(l) 是第 l l l 层的权重矩阵。 H ( l ) ∈ R N × D H^{(l)} \in \mathbb R^{N \times D} H(l)∈RN×D 为第 l l l 层的特征矩阵 H ( 0 ) X H^{(0)}X H(0)X H ( L ) Z H^{(L)}Z H(L)Z。 σ \sigma σ 表示非线性激活函数例如ReLU等。
上图中的GCN输入一个图通过若干层GCN每个node的特征从 X X X变成了 Z Z Z但是无论中间有多少层node之间的连接关系即 A A A都是共享的。
2.3 GCN 的核心公式推导的直观理解
首先我们给出一个简单的图以及其对应的邻接矩阵 A A A、节点特征 X X X这里我们用一个值表示一个节点特征。 那么GCN所做的事情就是融合邻居节点来更新某一个节点。 以2号节点为例那么最直接的融合方式就是求和求平均。 【融合邻居节点信息更新2号节点的值step1 求和】
将2号节点的邻居求和 A g g r e g a t e ( X 2 ) X 0 X 1 X 3 X 4 Aggregate(X_2) X_0 X_1 X_3 X_4 Aggregate(X2)X0X1X3X4
写成所有节点特征与系数相乘的形式 A g g r e g a t e ( X 2 ) 1 ⋅ X 0 1 ⋅ X 1 0 ⋅ X 2 1 ⋅ X 3 1 ⋅ X 4 0 ⋅ X 5 Aggregate(X_2) 1\cdot X_0 1\cdot X_1 0\cdot X_2 1\cdot X_3 1\cdot X_4 0\cdot X_5 Aggregate(X2)1⋅X01⋅X10⋅X21⋅X31⋅X40⋅X5
可以发现这个特征前面的系数就是邻接矩阵的2号节点对应的那一行数据 A 2 [ 1 , 1 , 0 , 1 , 1 , 0 ] A_2 [1,1,0,1,1,0] A2[1,1,0,1,1,0]
因此融合表示为邻接矩阵对应元素与特征矩阵对应元素相乘: A g g r e g a t e ( X 2 ) 1 ⋅ X 0 1 ⋅ X 1 0 ⋅ X 2 1 ⋅ X 3 1 ⋅ X 4 0 ⋅ X 5 A 2 , 0 X 0 A 2 , 1 X 1 A 2 , 2 X 2 A 2 , 3 X 3 A 2 , 4 X 4 A 2 , 5 X 5 ∑ j 0 N A 2 j X j A 2 X \begin{aligned} Aggregate(X_2) 1\cdot X_0 1\cdot X_1 0\cdot X_2 1\cdot X_3 1\cdot X_4 0\cdot X_5 \\ A_{2,0} X_0 A_{2,1} X_1 A_{2,2} X_2 A_{2,3} X_3 A_{2,4} X_4 A_{2,5} X_5 \\ \sum_{j0}^N A_{2j}X_j \\ A_2 X \end{aligned} Aggregate(X2)1⋅X01⋅X10⋅X21⋅X31⋅X40⋅X5A2,0X0A2,1X1A2,2X2A2,3X3A2,4X4A2,5X5j0∑NA2jXjA2X
对于所有的节点都做聚合操作的话 存在问题没有考虑自身节点特征
在上面这个步骤我们聚合2号节点的邻居节点信息的时候 A g g r e g a t e ( X 2 ) X 0 X 1 X 3 X 4 Aggregate(X_2) X_0 X_1 X_3 X_4 Aggregate(X2)X0X1X3X4并没有考虑自己本身的节点信息这显然是不合理的应该为 A g g r e g a t e ( X 2 ) X 0 X 1 X 2 X 3 X 4 Aggregate(X_2) X_0 X_1 X_2 X_3 X_4 Aggregate(X2)X0X1X2X3X4。
因此在原有邻接矩阵的基础上加上了一个单位阵 I I I记为 A ~ A I \tilde A AI A~AI 那么融合结果表示为 A g g r e g a t e ( X 2 ) X 0 X 1 X 2 X 3 X 4 A ~ 2 X Aggregate(X_2) X_0 X_1 X_2 X_3 X_4 \tilde A_2 X Aggregate(X2)X0X1X2X3X4A~2X
同理对所有节点表示进行聚合表示为 A g g r e g a t e ( X ) A ~ X Aggregate(X) \tilde A X Aggregate(X)A~X 【融合邻居节点信息更新2号节点的值step2 求均值】 还是以2号节点为例其求和表示为 A g g r e g a t e ( X 2 ) 1 ⋅ X 0 1 ⋅ X 1 1 ⋅ X 2 1 ⋅ X 3 1 ⋅ X 4 0 ⋅ X 5 A ~ 2 , 0 X 0 A ~ 2 , 1 X 1 A ~ 2 , 2 X 2 A ~ 2 , 3 X 3 A ~ 2 , 4 X 4 A ~ 2 , 5 X 5 ∑ j 0 N A ~ 2 j X j \begin{aligned} Aggregate(X_2) 1\cdot X_0 1\cdot X_1 1\cdot X_2 1\cdot X_3 1\cdot X_4 0\cdot X_5 \\ \tilde A_{2,0} X_0 \tilde A_{2,1} X_1 \tilde A_{2,2} X_2 \tilde A_{2,3} X_3 \tilde A_{2,4} X_4 \tilde A_{2,5} X_5 \\ \sum_{j0}^N \tilde A_{2j}X_j \end{aligned} Aggregate(X2)1⋅X01⋅X11⋅X21⋅X31⋅X40⋅X5A~2,0X0A~2,1X1A~2,2X2A~2,3X3A~2,4X4A~2,5X5j0∑NA~2jXj
那么自然的求均值首先想到的就是用和除以节点数量。对于2号节点与其相临的节点有四个( X 0 X_0 X0 X 1 X_1 X1 X 3 X_3 X3 X 4 X_4 X4)再加上自身共有5个节点.。这个数量其实就是每个节点的邻居个数包括自身可以通过计算邻接矩阵对应的行中1的个数获得。 因此这里引入了度矩阵 D D D度矩阵是一个对角阵对角线上的元素为各个顶点的度定义为 D ~ ∑ j A ~ i j \tilde D \sum_j \tilde A_{ij} D~∑jA~ij。 所以融合邻居节点更新2号节点的值 A g g r e g a t e ( X 2 ) ∑ j 0 N A ~ 2 j X j 5 ∑ j 0 N A ~ 2 j X j D ~ 2 , 2 \begin{aligned} Aggregate(X_2) \sum_{j0}^N \frac{\tilde A_{2j} X_j}{5} \\ \sum_{j0}^N \frac{\tilde A_{2j} X_j}{\tilde D_{2,2}} \end{aligned} Aggregate(X2)j0∑N5A~2jXjj0∑ND~2,2A~2jXj 存在问题平均时未考虑被聚合节点的信息
以更新3号节点为例融合邻居节点更新3号节点的值 A g g r e g a t e ( X 3 ) ∑ j 0 N A ~ 3 j X j D ~ 3 , 3 A ~ 3 , 2 X 2 A ~ 3 , 3 X 3 A ~ 3 , 5 X 5 D ~ 3 , 3 A ~ 3 , 2 X 2 D ~ 3 , 3 A ~ 3 , 3 X 3 D ~ 3 , 3 A ~ 3 , 5 X 5 D ~ 3 , 3 A ~ 3 , 2 X 2 D ~ 3 , 3 D ~ 3 , 3 A ~ 3 , 3 X 3 D ~ 3 , 3 D ~ 3 , 3 A ~ 3 , 5 X 5 D ~ 3 , 3 D ~ 3 , 3 \begin{aligned} Aggregate(X_3) \sum_{j0}^N \frac{\tilde A_{3j} X_j}{\tilde D_{3,3}} \\ \frac{\tilde A_{3,2} X_2 \tilde A_{3,3} X_3 \tilde A_{3,5} X_5}{\tilde D_{3,3}} \\ \frac{\tilde A_{3,2} X_2}{\tilde D_{3,3}} \frac{\tilde A_{3,3} X_3}{\tilde D_{3,3}} \frac{\tilde A_{3,5} X_5}{\tilde D_{3,3}} \\ \frac{\tilde A_{3,2} X_2}{\sqrt{\tilde D_{3,3}\tilde D_{3,3}}} \frac{\tilde A_{3,3} X_3}{\sqrt{\tilde D_{3,3}\tilde D_{3,3}}} \frac{\tilde A_{3,5} X_5}{\sqrt{\tilde D_{3,3}\tilde D_{3,3}}} \end{aligned} Aggregate(X3)j0∑ND~3,3A~3jXjD~3,3A~3,2X2A~3,3X3A~3,5X5D~3,3A~3,2X2D~3,3A~3,3X3D~3,3A~3,5X5D~3,3D~3,3 A~3,2X2D~3,3D~3,3 A~3,3X3D~3,3D~3,3 A~3,5X5
通过公式我们可以看出在分子上考虑了自身节点和被融合节点而分母只考虑了3号节点本身。
因此分母加入对被融合节点的考虑优化更新操作 A g g r e g a t e ( X 3 ) A ~ 3 , 2 X 2 D ~ 3 , 3 D ~ 2 , 2 A ~ 3 , 3 X 3 D ~ 3 , 3 D ~ 3 , 3 A ~ 3 , 5 X 5 D ~ 3 , 3 D ~ 5 , 5 ∑ j 0 N A ~ 3 j X j D ~ 3 , 3 D ~ j , j \begin{aligned} Aggregate(X_3) \frac{\tilde A_{3,2} X_2}{\sqrt{\tilde D_{3,3}\tilde D_{2,2}}} \frac{\tilde A_{3,3} X_3}{\sqrt{\tilde D_{3,3}\tilde D_{3,3}}} \frac{\tilde A_{3,5} X_5}{\sqrt{\tilde D_{3,3}\tilde D_{5,5}}} \\ \sum_{j0}^N \frac{\tilde A_{3j}X_j}{\sqrt{\tilde D_{3,3}\tilde D_{j,j}}} \end{aligned} Aggregate(X3)D~3,3D~2,2 A~3,2X2D~3,3D~3,3 A~3,3X3D~3,3D~5,5 A~3,5X5j0∑ND~3,3D~j,j A~3jXj 推广到融合邻居节点的值来更新 i i i 号节点的值 A g g r e g a t e ( X i ) ∑ j 0 N A ~ i j X j D ~ i i D ~ j j ∑ j 0 N D ~ i i − 1 2 A ~ i j D ~ j j − 1 2 X j \begin{aligned} Aggregate(X_i) \sum_{j0}^N \frac{\tilde A_{ij}X_j}{\sqrt{\tilde D_{ii}\tilde D_{jj}}}\\ \sum_{j0}^N \tilde D_{ii}^{-\frac{1}{2}} \tilde A_{ij} \tilde D_{jj}^{-\frac{1}{2}} X_j \end{aligned} Aggregate(Xi)j0∑ND~iiD~jj A~ijXjj0∑ND~ii−21A~ijD~jj−21Xj
矩阵计算 A g g r e g a t e ( X ) ∑ i 0 N A g g r e g a t e ( X i ) ∑ i 0 N ∑ j 0 N D ~ i i − 1 2 A ~ i j D ~ j j − 1 2 X j ∑ i 0 N D ~ i i − 1 2 A ~ i D ~ − 1 2 X D ~ − 1 2 A ~ D ~ − 1 2 X \begin{aligned} Aggregate(X) \sum_{i0}^N Aggregate(X_i)\\ \sum_{i0}^N \sum_{j0}^N \tilde D_{ii}^{-\frac{1}{2}} \tilde A_{ij} \tilde D_{jj}^{-\frac{1}{2}} X_j \\ \sum_{i0}^N \tilde D_{ii}^{-\frac{1}{2}} \tilde A_{i} \tilde D^{-\frac{1}{2}} X \\ \tilde D^{-\frac{1}{2}} \tilde A \tilde D^{-\frac{1}{2}} X \end{aligned} Aggregate(X)i0∑NAggregate(Xi)i0∑Nj0∑ND~ii−21A~ijD~jj−21Xji0∑ND~ii−21A~iD~−21XD~−21A~D~−21X
至此我们就可以得出GCN的核心公式啦。 3. Why 图注意力网络GAT
由于之前的GCN网络平等的对待每一个节点于是就有人想到把attention引入来给每个邻居节点分配不同的权重从而能够识别出更加重要的邻居于是就有了GAT。
GAT的核心思想是在每个节点上计算注意力系数以确定节点与其邻居节点之间的重要性。这种注意力机制使得模型能够对不同节点之间的关系赋予不同的权重从而更好地捕捉图数据中的局部结构和全局信息。
4. GAT的原理
GAT网络由堆叠简单的图注意力层Graph Attention Layer来实现。
4.1 GAT的输入
GAT的输入是每个节点的向量表示 h { h 1 , h 2 , … , h N } , h i ∈ R F \mathbf{h} \{\mathbf{h}_1,\mathbf{h}_2,\ldots,\mathbf{h}_N\},\mathbf{h}_i \in \mathbb{R}^F h{h1,h2,…,hN},hi∈RF其中 N N N 是节点的数量。
4.2 GAT的流程及核心公式
【Step1 特征维度变换】
为了获得足够的表达能力利用(至少一个可学习的)线性变换将原始特征映射为一个 F ′ F F′ 维的特征向量 h ′ { h 1 ′ , h 2 ′ , … , h N ′ } , h i ′ ∈ R F ′ \mathbf{h} \{\mathbf{h}_1,\mathbf{h}_2,\ldots,\mathbf{h}_N\}, \mathbf{h}_i \in \mathbb{R}^{F} h′{h1′,h2′,…,hN′},hi′∈RF′. h i ′ W h i \mathbf{h}_i\mathbf{W} \mathbf{h}_i hi′Whi
其中权重矩阵 W ∈ R F ′ × F \mathbf{W} \in \mathbb{R}^{F \times F} W∈RF′×F 是所有节点共享的。
【Step2 计算注意力系数并归一化处理】
在节点上执行自注意力共享注意机制计算注意力系数 e i j e_{ij} eij。
所谓注意力机制就是一种映射 a : R F ′ × R F ′ → R a : \mathbb R^{F} \times \mathbb R^{F} \to \mathbb R a:RF′×RF′→R那么注意力系数 e i j a ( W h i , W h j ) LeakyReLU ( a T [ W h i ∥ W h j ] ) e_{ij} a(\mathbf{W} \mathbf{h}_i, \mathbf{W} \mathbf{h}_j)\text{LeakyReLU}(\mathbf{a}^T[\mathbf{W} \mathbf{h}_i \| \mathbf{W} \mathbf{h}_j]) eija(Whi,Whj)LeakyReLU(aT[Whi∥Whj])
表示节点 j j j 的特征对节点 i i i 的重要程度。
为了不同系数之间便于比较对系数进行 归一化(normalization) 处理 α i j softmax j ( e i j ) exp ( e i j ) ∑ k ∈ N i exp ( e i k ) \alpha_{ij} \text{softmax}_{j}(e_{ij}) \frac{\exp (e_{ij})}{\sum_{k \in \mathcal{N}_i} \exp (e_{ik})} αijsoftmaxj(eij)∑k∈Niexp(eik)exp(eij) 【Step 3 计算节点的向量表示输出】
得到归一化的权重系数后按照注意力机制加权求和的思路最终节点 i i i 新的特征向量为 h i ′ σ ( ∑ j ∈ N i α i j W h j ) \mathbf{h}_i \sigma(\sum_{j \in \mathcal{N}_i} \alpha_{ij} \mathbf{W} \mathbf{h}_j) hi′σ(j∈Ni∑αijWhj)
为了稳定自注意力的学习过程引入了多头自注意力。用 K K K 个独立注意机制执行上述变换然后将它们的特征拼接起来或计算平均值从而得到如下两种特征表示 h i ′ ∥ k 1 K σ ( ∑ j ∈ N i α i j k W k h j ) h i ′ σ ( 1 K ∑ k 1 K ∑ j ∈ N i α i j k W k h j ) \mathbf{h}_i \overset{K}{\underset{k1}{\parallel}} \sigma(\sum_{j \in \mathcal{N}_i} \alpha_{ij}^k \mathbf{W}^k \mathbf{h}_j) \\ \mathbf{h}_i \sigma(\frac{1}{K} \sum_{k1}^K\sum_{j \in \mathcal{N}_i} \alpha_{ij}^k \mathbf{W}^k \mathbf{h}_j) hi′k1∥Kσ(j∈Ni∑αijkWkhj)hi′σ(K1k1∑Kj∈Ni∑αijkWkhj)
其中 ∥ \parallel ∥ 表示向量拼接操作。 References
图神经网络系列讲解及代码实现何时能懂你的心——图卷积神经网络GCN图卷积网络Graph Convolution NetworkGCN图神经网络GAT(Graph Attention Network)理解
