专题一——有监督图神经网络的经典架构

图神经网络 专题一——有监督图神经网络常见框架

[参考资料]《图神经网络》，吴凌飞等 著，人民邮电出版社
符号约束：
·图\(G = (V, E)\)
·邻接矩阵：\(A \in \mathbb{R}^{N \times N}\)
·结点属性矩阵：\(X \in \mathbb{R}^{N \times C}\)（\(C\)表示结点原始属性的维度）
·GNN层总数：\(K\)
·第\(k\)层的结点表征：\(H^k \in \mathbb{R}^{N \times F}\)（\(F\)表示结点表征的维度）

一、图神经网络的一般框架

初始结点表征：\(H^0 = X\)
1.聚合函数AGGREGATE
·形式：\(a_v^k = AGGREGATE^k\{H_u^{k - 1}: u \in N(v)\}\)
·功能：对邻居结点的信息进行聚合。
2.连接函数COMBINE
·形式：\(H_v^k = COMBINE^k\{H_v^{k - 1}, a_v^k\}\)
·功能：对来自邻域的聚合信息，以及当前结点在上一层的表征进行结合，以获得当前结点更新后的表征。
3.使用结点表征进行结点分类
·对于结点\(v\)在最后一层（第\(K\)层）的结点表征\(H_v^K \in \mathbb{R}^{N \times F}\)，可使用softmax函数进行结点分类预测，输出结点属于各个类别的概率。
·设\(|L|\)为输出标签的数量，则预测结果公式为：\(\hat{y}_v = Softmax(WH^T)\)
·损失函数：\(O = \frac{1}{n_l}\sum_{i = 1}^{n_l}loss(\hat{y}_i, y_i)\)，其中\(n_l\)为监督结点的个数。

二、图卷积神经网络(GCN, Graph Convolution Network)基本框架

1.结点表征更新公式（合并形式）
·公式：\(H_{k + 1} = \sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^kW^k)\)
·\(\tilde{A} = A + I\)。
·\(\tilde{D}\)是对角矩阵，其中\(\tilde{D}_{ii} = \sum_j\tilde{A}_{ij}\)。
·事实上：\(H_{k + 1} = \sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^kW^k) \newline = \sigma(\tilde{D}^{-\frac{1}{2}}A\tilde{D}^{-\frac{1}{2}}H^kW^k) + \sigma(\tilde{D}^{-\frac{1}{2}}I\tilde{D}^{-\frac{1}{2}}H^kW^k)\)，前者是对各邻居结点的表征汇聚，后者是对本结点在上一层表征的线性变换处理。
2.结点表征更新公式（拆分形式）
①聚合函数AGGREGATE：\(\sum_{j \in N(i)}\frac{A_{ij}}{\sqrt{\tilde{D}_{ii}\tilde{D}_{jj}}}H_{j}^{k - 1}W^k\)
②连接函数COMBINE：\(H_i^k = \sigma(\sum_{j \in N(i)}\frac{A_{ij}}{\sqrt{\tilde{D}_{ii}\tilde{D}_{jj}}}H_{j}^{k - 1}W^k + \frac{1}{\tilde{D}_i}H_i^{k - 1}W^k)\)
3.问题
·本质上，各邻居节点\(v_j\)表征的权重，是由本结点\(v_i\)与之相连的边\(e_{ij}\)的权重决定的。
·但是，输入图往往存在不同程度的噪声，边的权重不一定能反映邻居结点的重要性。

三、图注意力网络(GAT, Graph Attention Network)基本框架

1.基本思想
·GCN使用边\(e_{ij}\)的权重，决定各邻居节点\(v_j\)表征进行汇聚的权重；但是，输入图往往存在不同程度的噪声，边的权重不一定能反映邻居结点的重要性。
·GAT根据注意力机制，自动学习每个邻居结点的重要性。
2.注意力系数计算
·设当前结点为\(v_i\)，邻居结点\(v_j \in N(i)\)，则该对结点的注意力系数为：\(e_{ij} = a(WH_i^{k - 1}, WH_j^{k - 1})\)
·实质上，先分别对\(H_i^{k - 1}\)和\(H_j^{k - 1}\)进行线性投影，再计算相似度；\(WH_i^{k - 1}\)对应于注意力机制中的query，\(WH_j^{k - 1}\)对应于注意力机制中的key。
3.注意力系数归一化
·对于同一结点，使用softmax，对各邻居结点的注意力系数进行归一化：\(\alpha_{ij} = Softmax_j(\{e_{ij}\}) = \frac{exp(e_{ij})}{\sum_{l \in N(i)}exp(e_{il})}\)
4.结点表征更新
\(H_i^k = \sigma(\sum_{j \in N(i)}\alpha_{ij}WH_j^{k - 1})\)
[注]GAT中，线性投影矩阵\(Q, K, V\)相同，在上述公式中均记为\(W\)。

四、消息传递神经网络(MPNN, Message-Passing Neural Network)基本框架

1.消息函数计算
[注]“消息函数”即GNN一般框架中的聚合函数AGGREGATE。
·公式：\(m_i = \sum_{i \in N(j)}M_k(H_i^{k - 1}, H_j^{k - 1}, e_{ij})\)
·消息：由当前结点表征、一个邻居（一阶邻域）结点的表征，及连接二者的边的表征，计算得到一条消息。
·某节点的所有“消息”通过加性方式进行聚合。
2.连接函数COMBINE
·公式：\(H_{i}^k = U_k(H_i^{k - 1}, m_i^k)\)
·将加性汇总的消息与当前结点在上一层的表征结合起来，计算得到更新后的结点表征。