3. 图神经网络 GNN

3.1 GNN 基础结构 ***

常见架构：$Y=\sigma(\hat D^{-1}\hat A XW)$

• 图谱（Graph Spectrum）和图傅里叶变换（GFT）

  • 拉普拉斯矩阵 $L=D-A$，其中 $A$ 为邻接矩阵，$D$ 为对角度矩阵

  • 特征值分解 $L=U\Lambda U^T$，其中 $\Lambda$ 是从小到大的特征值，是 G 的 图谱

    • 特征值 - 频域频率，特征向量 - 基波

    • 特征值越小，特征向量（波）越平缓

  • 图傅里叶变换（GFT） $\hat x=U^Tx$，图逆傅里叶变换（IGFT） $x=U\hat x$

• 基于 频域 的 GNN：GCN

  • 卷积定理：两个函数卷积后的 FT，是他们各自 FT 后的乘积

  • 卷积：$x*h=U\cdot diag(\hat h)\cdot U^Tx$，各自 FT 乘积的 IFT

  • $y=\sigma(U\cdot(\sum_{k=0}^K \alpha_k \Lambda^k)\cdot U^T x)=\sigma(\sum_{k=0}^K \alpha_k L^k x)$

  • 本质：将每个节点的 K 步范围内的邻居特征融合起来

• 基于 空域 的 GNN：GAT，GraphSAGE

  • GAT：基于多头注意力机制的邻域卷积，$y_i=\sigma(\frac1M \sum_{m=1}^M \sum_{j\in \mathcal N_i}\alpha_{ij}^{(m)}(x_j \cdot W^{(m)}))$

  • GraphSAGE：K 度邻居特征融合（max-pooling, average-pooling, LSTM）

    • 融合目标节点邻域的特征 $h_{\mathcal N_i}=aggregate(\{x_j|j\in\mathcal N_i\})$

    • 使用 邻域+自身 拼接特征更新 $y_i=\sigma(concat(x_i,h_{\mathcal N_i})\cdot W)$

3.2 GNN 在推荐系统中的应用 PinSage

• 网络构建

  • 二部图：图片 - 图板

  • 图片特征：视觉、文本标注、流行度

• 模型结构（GraphSAGE）

  • 节点邻域定义：随机游走，K 度邻居中，抽出 T 个重要节点

  • aggregate 操作：按照重要性，加权平均

  • 负样本抽取：课程学习，每轮选取难以分辨的负样本

• 任务总结

  • 点分类 $p(v_i)=Softmax(h_i)$

  • 边预测 $p(A_{ij})=\sigma(h_ih_j^T)$

  • 图分类 $p(G)=Softmax(\sum_{i\in V}h_i)$

3.3 GNN 的推理能力 ****

• 推理能力

  • 关系推理（Relational Reasoning）：根据实体间关系，做出逻辑判断

  • 组合泛化（Combinational Generalization）：组合零碎知识，解决新问题

• GNN 基本计算框架

  • 更新 e 向量表示

  • 聚合，更新 v 向量表示

  • 聚合所有 e 的向量表示，聚合所有 v 的向量表示，更新 G 向量表示

• 有何优势

  • 具备推断关系的能力：关系的强度、方向可以学习

  • 充分利用训练数据：建模图中任意一对邻接节点之间的关系，泛化能力强

  • 模型输出与节点标号顺序无关

• 推理机制 在其他领域的应用

  • 自注意力机制：$z_i=\sum_{j=1}^n \alpha_{ij} (x_jW^V)$，$\alpha_{ij}=softmax(e_{ij})$

    • 其中 $e_{ij}=\frac{(x_iW^Q)(x_jW^K)^T}{\sqrt{d_z}}$，代表元素 i, j 之间的相关性

    • 完全图，$Z$ 视为节点向量，$e_{ij}$ 视为边，自注意力机制 = 完全图神经网络

    • 层次结构 Transformer 多个自注意力累计 = 图神经网络多层卷积

  • 基于度量的元学习：$y=\sum_i k_\theta (x,x_i)\cdot y_i$，其中 $k_\theta(\cdot,\cdot)$ 是衡量相似性的核函数

  • 分解机：$y(x)=w_0+\sum_{i=1}^n w_ix_i +\sum_{i=1}^n \sum_{j=i+1}^n \langle v_i,v_j\rangle \cdot x_ix_j$，其中 v 是辅助表示向量

• GNN 推理能力重点：对关系建模