异构图GCN

异构图

异构图是由多种类型的节点（Node）和边（Edge）组成的复杂图结构。

比如：

节点类型：社交网络中的用户、帖子、标签

边类型：用户关注用户、用户发布帖子、帖子包含标签

异构图GCN

引入

传统GCN中假设图中所有节点和边类型相同，通过共享权重聚合邻居信息。这种方法在异构图中难以适用，会造成语义混淆：如果将异构图中所有的节点和边都当成同一种类型，由于不同类型的节点的特征空间差异极大，直接混合计算会丢失类型特异性信息，不同边类型（如“购买”和“浏览”）的权重无法区分，难以建模多样化的交互模式。

典型应用场景：

• 推荐系统：用户、商品、商家构成的异构图，通过“点击”、“购买”等边类型建模用户兴趣。
• 知识图谱推理：实体（人物、地点、事件）和关系（出生地、职业）构成的异构图，例如预测药物与疾病的潜在关联
• 社交网络分析：用户、帖子、评论、标签的多类型交互，识别社区或虚假账号

RGCN

引入

RGCN（Relational Graph Convolutional Network），关系图卷积网络，是针对异构图中多种关系类型设计的图卷积网络。

公式： \[ \mathbf{h}_i^{(l+1)} = \sigma\left( \sum_{r\in\mathcal{R}}\sum_{j\in\mathcal{N}_r(i)}\frac{1}{\sqrt{|\mathcal{N}_r(i)|\cdot|\mathcal{N}_r(j)|}}\mathbf{h}_j^{(l)}\mathbf{W}_r^{(l)} + \mathbf{h}_i^{(l)}\mathbf{W}_0^{(l)} \right) \]

• \(\mathbf{h}_i^{(l)}\)：节点\(i\)在第\(l\)层的特征向量
• \(\mathcal{N}_r(i)\)：节点\(i\)在关系\(r\)下的邻居集合，\(|\mathcal{N}_r(i)|\)表示的就是节点\(i\)在关系\(r\)下的度
• \(\mathbf{W}_r^{(l)}\)：关系\(r\)在第\(l\)层的权重矩阵
• \(\mathbf{W}_0^{(l)}\)：节点自身的在第\(l\)层的权重矩阵
• \(\sigma\)：激活函数（如ReLU）

上面这个公式是逐个节点进行计算的，下面给出矩阵形式：

设关系\(r\)下的邻接矩阵为\(\mathbf{A}_r\)，对应的关系\(r\)下的度矩阵为\(\mathbf{D}_r\)，则 \[ \mathbf{H}^{(l+1)} = \sigma\left( \sum_{r\in\mathcal{R}}\mathbf{D}_r^{-\frac{1}{2}}\mathbf{A}_r\mathbf{D}_r^{-\frac{1}{2}}\mathbf{H}^{(l)}\mathbf{W}_r^{(l)} + \mathbf{H}^{(l)}\mathbf{W}_0^{(l)} \right) \] 矩阵形式的优点是方便GPU并行运算，但是每一种关系都需要一个邻接矩阵和度矩阵，这样的缺点是内存占用量大。

由这个矩阵形式可以看出，RGCN实际上就是多个不带自环的GCN，再加上一个自环。其中每一种关系都可以看成一个单独的图（比如，用户与商品之间存在购买、点击、加购等关系，“用户-购买-商品”、“用户-点击-商品”、“用户-加购-商品”都可以看成是一张图，这些图中的节点都相同，只是边和每层的权重\(\mathbf{W}^{(l)}\)不同）

需要注意的是，RGCN中并未区分不同类型的节点，只区分了不同类型的边，因此，如果是像电商平台“用户”、“商品”这样不同类型的边，可以将它们放到同一个图中当成同一种类型的节点，比如有100个用户和200个商品，那么1~100就是用户节点，101~300就是商品节点，然后邻接矩阵\(\mathbf{A}_r\in\mathbb{R}^{300\times 300}\)即可。

正则化

当RGCN中的关系数量很大时，所需要的权重参数就会很多，并且对于不常见的关系，学习的时候容易出现过拟合的现象，为了解决这个问题，RGCN的作者提出了两种解决方案：

1. 权值共享（基分解）：基分解（Basis Decomposition）的核心思想是，通过共享一组基础变换矩阵，将每个关系的权重矩阵表示为这些基矩阵的线性组合。这实现了以下目标：

   • 参数共享：不同关系共享同一组基矩阵，显著减少参数量。
   • 稀疏关系泛化：稀疏关系的权重矩阵由基矩阵组合生成，其参数更新可受益于高频关系的训练信号
   • 语义相似性建模：语义相近的关系可能共享相似的基矩阵组合模式，增强模型表达能力

   基分解的公式：

   设第\(l\)层的权重矩阵为\(\mathbf{W}_r^{(l)}\in\mathbb{R}^{d\times d}\)（\(d\)为特征维度，\(r\)为关系类型），基分解将其表示为： \[ \mathbf{W}_r^{(l)} = \sum_{b=1}^B a_{rb}^{(l)}\mathbf{V}_b^{(l)} \] 其中:

   • \(\mathbf{V}_b^{(l)}\in\mathbb{R}^{d\times d}\)，是第\(l\)层的第\(b\)个基矩阵，共\(B\)个基矩阵（\(B\)为超参数，通常\(B<<|\mathcal{R}|\)，\(|\mathcal{R}|\)为关系总数）
   • \(a_{rb}^{(l)}\in\mathbb{R}\)，是关系\(r\)对基矩阵\(\mathbf{V}_b^{(l)}\)的系数

   \(\mathbf{V}_b^{(l)}\)和\(a_{rb}^{(l)}\)都是可学习的参数

2. 块对角分解（Block-Diagonal Decomposition）：将每个关系的权重矩阵\(\mathbf{W}_r^{(l)}\)分解为块对角矩阵，仅保留局部的特征交互，降低参数复杂度

   公式：

   设第\(l\)层的关系权重矩阵\(\mathbf{W}_r^{(l)}\in\mathbb{R}^{d\times d}\)，块对角分解将其表示为： \[ \mathbf{W}_r^{(l)} = \bigoplus_{b=1}^B\mathbf{Q}_{rb}^{(l)} \] 其中：

   • \(\mathbf{Q}_{rb}^{(l)}\in\mathbb{R}^{\frac{d}{B}\times\frac{d}{B}}\)是第\(b\)个低维子矩阵，总块数\(B\)是超参数

   • \(\bigoplus\)表示块对角拼接，最终\(\mathbf{W}_r^{(l)}\)的结构如下： \[ \mathbf{W}_r^{(l)} = \left[ \begin{matrix} \mathbf{Q}_{r1}^{(l)}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{Q}_{r2}&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{Q}_{rB} \end{matrix} \right] \]

提升并行度

矩阵形式有一个缺点，就是如果\(r\)的种类数较多，那么一层需要计算的次数也会比较多，并行度不够，下面给出并行度更高的计算形式：

1. 邻接矩阵拼接：

将不同关系的邻接矩阵拼接位块对角稀疏矩阵\(\mathbf{A}_\mathrm{block}\)，假设关系\(r\)一共有\(|\mathcal{R}|\)种 \[ \mathbf{A}_\mathrm{block} = \left[ \begin{matrix} \mathbf{A}_1&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{A}_2&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{A}_{|\mathcal{R}|} \end{matrix} \right] \] 每个子块\(\mathbf{A}_r\)对应一种关系的邻接矩阵。

同理，对于度矩阵，也将其进行拼接： \[ \mathbf{D}_\mathrm{block} = \left[ \begin{matrix} \mathbf{D}_1&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{D}_2&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{D}_{|\mathcal{R}|} \end{matrix} \right] \] 每个子块\(\mathbf{D}_r\)对应一种关系的度矩阵，并且： \[ \mathbf{D}_\mathrm{block}^{-\frac{1}{2}} = \left[ \begin{matrix} \mathbf{D}_1^{-\frac{1}{2}}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{D}_2^{-\frac{1}{2}}&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}} \end{matrix} \right] \] 则： \[ \begin{aligned} \mathbf{D}_\mathrm{block}^{-\frac{1}{2}}\mathbf{A}_\mathrm{block}\mathbf{D}_\mathrm{block}^{-\frac{1}{2}} &= \left[ \begin{matrix} \mathbf{D}_1^{-\frac{1}{2}}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{D}_2^{-\frac{1}{2}}&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}} \end{matrix} \right]\cdot\left[ \begin{matrix} \mathbf{A}_1&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{A}_2&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{A}_{|\mathcal{R}|} \end{matrix} \right]\cdot\left[ \begin{matrix} \mathbf{D}_1^{-\frac{1}{2}}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{D}_2^{-\frac{1}{2}}&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}} \end{matrix} \right]\\ &= \left[ \begin{matrix} \mathbf{D}_1^{-\frac{1}{2}}\mathbf{A}_1\mathbf{D}_1^{-\frac{1}{2}}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{D}_2^{-\frac{1}{2}}\mathbf{A}_2\mathbf{D}_2^{-\frac{1}{2}}&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}}\mathbf{A}_{|\mathcal{R}|}\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}} \end{matrix} \right] \end{aligned} \]

2. 特征矩阵扩展：

将节点特征矩阵\(\mathbf{H}\)沿行方向复制\(|\mathcal{R}|-1\)次，得到扩展矩阵\(\mathbf{H}_\mathrm{extended}\in\mathbb{R}^{|\mathcal{R}|N\times d}\)，\(N\)表示节点个数，\(d\)为特征维度 \[ \mathbf{H}_\mathrm{extended} = \left. \left[ \begin{matrix} \mathbf{H}\\ \mathbf{H}\\ \vdots\\ \mathbf{H} \end{matrix} \right] \right\}N个\mathbf{H} \] 则： \[ \begin{aligned} \mathbf{D}_\mathrm{block}^{-\frac{1}{2}}\mathbf{A}_\mathrm{block}\mathbf{D}_\mathrm{block}^{-\frac{1}{2}}\mathbf{H}_\mathrm{extended} &= \left[ \begin{matrix} \mathbf{D}_1^{-\frac{1}{2}}\mathbf{A}_1\mathbf{D}_1^{-\frac{1}{2}}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{0}&\mathbf{D}_2^{-\frac{1}{2}}\mathbf{A}_2\mathbf{D}_2^{-\frac{1}{2}}&\cdots&\mathbf{0}\\ \vdots&\vdots&&\vdots\\ \mathbf{0}&\mathbf{0}&\cdots&\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}}\mathbf{A}_{|\mathcal{R}|}\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}} \end{matrix} \right]\cdot\left[ \begin{matrix} \mathbf{H}\\ \mathbf{H}\\ \vdots\\ \mathbf{H} \end{matrix} \right]\\ &= \left[ \begin{matrix} \mathbf{D}_1^{-\frac{1}{2}}\mathbf{A}_1\mathbf{D}_1^{-\frac{1}{2}}\mathbf{H}\\ \mathbf{D}_2^{-\frac{1}{2}}\mathbf{A}_2\mathbf{D}_2^{-\frac{1}{2}}\mathbf{H}\\ \vdots\\ \mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}}\mathbf{A}_{|\mathcal{R}|}\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}}\mathbf{H} \end{matrix} \right]\in\mathbb{R}^{N|\mathcal{R}|\times d} \end{aligned} \]

3. 矩阵切分：

将\(\mathbf{D}_\mathrm{block}^{-\frac{1}{2}}\mathbf{A}_\mathrm{block}\mathbf{D}_\mathrm{block}^{-\frac{1}{2}}\mathbf{H}_\mathrm{extended}\)按关系维度切分并堆叠为三维张量： \[ \mathbf{H}_\mathrm{prop\_reshaped} = \left[ \begin{matrix} \left[\mathbf{D}_1^{-\frac{1}{2}}\mathbf{A}_1\mathbf{D}_1^{-\frac{1}{2}}\mathbf{H}\right]\\ \left[\mathbf{D}_2^{-\frac{1}{2}}\mathbf{A}_2\mathbf{D}_2^{-\frac{1}{2}}\mathbf{H}\right]\\ \vdots\\ \left[\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}}\mathbf{A}_{|\mathcal{R}|}\mathbf{D}_{|\mathcal{R}|}^{-\frac{1}{2}}\mathbf{H}\right] \end{matrix} \right]\in\mathbb{R}^{|\mathcal{R}|\times N\times d} \]

4. 权重张量堆叠：

将各关系权重矩阵\(\mathbf{W}_r\)堆叠为三维张量\(\mathbf{W}\in\mathbb{R}^{|\mathcal{R}|\times d\times d}\)： \[ \mathbf{W} = \left[ \begin{matrix} \left[\mathbf{W}_1\right]\\ \left[\mathbf{W}_2\right]\\ \vdots\\ \left[\mathbf{W}_{|\mathcal{R}|}\right] \end{matrix} \right] \]

5. 使用批量矩阵乘法：

使用torch.bmm()加速计算：

H_out = torch.bmm(H_prop, W)

问题：torch.bmm()好像无法处理稀疏矩阵。