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)$

网络构建
- 二部图：图片 - 图板
- 图片特征：视觉、文本标注、流行度
模型结构（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)$

推理能力
- 关系推理（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 推理能力重点：对关系建模

Last updated 3 years ago