COMP5313 Week 08 Label Propagation 与 Feature Propagation 讲课总结

Posted on Edited on In Word count in article: 1.8k Reading time ≈ 6 mins.
COMP5313 Week 08 讲课总结，整理 label propagation、Correct and Smooth、PPR/APPNP、SGC 与 feature propagation 的考点重点。

COMP5313 Week 08 讲课总结：Label Propagation 与 Feature Propagation

本讲重点不是新 GNN 架构，而是把 label propagation / feature propagation 这类组合式思想和 GNN 结合。老师明确说 exact formulas 不重要，重点是 high-level ideas 和怎么使用。

1. 本讲主题

老师说本讲有四个主线：

  1. 没有 node features 时，只用 label propagation 做 node classification。
  2. 把 label propagation 作为 post-processing，提高已有模型预测。
  3. 把 label propagation / PageRank-style propagation 放进 GNN。
  4. 不传播 label，而是传播 node features，作为 preprocessing 提升效率。

这些思想都和 Week 06 的 PageRank / Personalized PageRank 很像。

2. GNN 与 Node Classification 回顾

输入设定：

  • 无向图 \(G=(V,E)\)。
  • 邻接矩阵 \(A\)。
  • 节点特征矩阵 \(X \in \mathbb{R}^{n \times q}\)。
  • 只有一部分节点有 ground-truth labels。
  • 目标：预测其他节点的 label。

GNN 的基本思想是 neighbourhood aggregation：预测节点 \(u\) 时，不只用 \(u\) 自己的 feature，也用邻居、邻居的邻居等局部结构信息。

3. Simple Label Propagation

核心假设：Homophily

label propagation 基于同质性假设：

边连接的两个节点通常属于相同类别或有相似特征。

也就是说，如果两个节点相连，它们的 label probability 应该相近。

二分类设定

假设每个节点属于 class 1 或 class 0。用 \(p_v\) 表示节点 \(v\) 属于 class 1 的概率。

初始化：

  • 已知 class 1 的训练节点：\(p_v=1\)
  • 已知 class 0 的训练节点：\(p_v=0\)
  • 未标注节点：\(p_v=0.5\)

更新规则：

[ p_v^{(k)}=_{uN(v)}p_u^{(k-1)} ]

也就是：节点 \(v\) 新一轮的概率 = 上一轮邻居概率的平均。

停止条件：

  • 迭代到收敛；或
  • 达到最大迭代次数。

最终预测：

  • 若 \(p_v>0.5\)，预测 class 1。
  • 若 \(p_v<0.5\)，预测 class 0。
  • 若相等，可以任意选一个，说明很难区分。

4. Label Propagation 与 PageRank 的区别

老师明确比较了它和 Basic PageRank。

相似点：

  • 都是 iterative update。
  • 都用上一轮的邻居信息更新当前值。
  • 每轮更新时只使用 \(k-1\) 轮结果，所以更新顺序不影响结果。

关键区别是 normalisation：

  • Label Propagation 是 pull average： [ p_v^{(k)}=_{uN(v)}p_u^{(k-1)} ] 用目标节点 \(v\) 的度数做平均。
  • PageRank 是 push flow： [ PR_v^{(k)}=_{uv} ] 每个源节点 \(u\) 把自己的分数按自己的出度分出去。

这是 Week 08 的一个非常明确考点。

5. 多分类与 One-hot Label Matrix

如果有 \(C\) 个类别，通常为每个节点维护 \(C\) 个概率，而不是只维护一个概率。

label matrix 每一行对应一个节点，每一列对应一个类别。

one-hot encoding：

  • 属于 class 1：\((1,0,0)\)
  • 属于 class 2：\((0,1,0)\)
  • 属于 class 3：\((0,0,1)\)

老师说理论推导里会出现 Laplacian、trace、矩阵逆等公式，但 exact formulas 不需要背。

需要理解两个 high-level constraints：

  • Smoothness：相连节点的预测结果应该相似。
  • Fitting：预测结果不要离已知 ground-truth labels 太远。

6. Correct and Smooth：把 Label Propagation 作为 Post-processing

老师讲了一个方法：先用任意 base predictor，再用 label propagation 修正结果。

base predictor 可以是：

  • MLP
  • GNN
  • 其他分类模型

Step 1：训练 base predictor

先用原来的训练集训练一个模型。

Step 2：得到 soft labels

模型对每个节点输出 class probabilities，这些预测概率叫 soft labels。

Step 3：Correct

在训练节点上计算 prediction error：

[ =- ]

未标注节点 error 初始化为 0。

然后把这些 error 沿图做 label propagation / diffusion。

直觉：如果一个节点预测有偏差，它邻居的预测也可能有类似偏差。

得到 diffused errors 后，把它加回 soft labels，得到 corrected soft labels。

Step 4：Smooth

把训练节点重新 reset 为 ground truth labels，然后再沿图传播 corrected labels。

直觉：相邻节点倾向同类，所以让 corrected labels 在图上平滑。

最终预测时比较各类别分数大小。老师提到 smoothing 后的两个“概率”不一定严格加和为 1；如果要当作概率分布，可以再 normalize，但分类时直接比较大小即可。

7. 在 GNN 中使用 Label / PageRank-style Propagation

普通 GNN 的限制：

  • \(K\) 层 GNN 只用 \(K\)-hop neighbours。
  • \(K\) 小：看到的信息范围有限。
  • \(K\) 大：容易 over-smoothing，节点表示变得过于相似，难以区分。

老师讲了用 Personalized PageRank 思想缓解这个问题：

  • 对节点 \(u\)，聚合全图其他节点的信息。
  • 权重由 Personalized PageRank 决定。
  • 和 \(u\) 更相关的节点权重大。

PPNP / APPNP 高层思路

PPNP 使用 PPR matrix 做传播，但直接矩阵逆太贵。

APPNP 使用近似迭代：

  1. 先用 MLP 对每个节点做预测。
  2. 此时还没有用图结构。
  3. 再用 PageRank-style propagation 把预测标签沿图传播 \(K\) 步。
  4. 得到最终预测。

这可以理解成把 PPR / Scaled PageRank 的传播思想放进 GNN。

8. PPRGo 高层思路

老师提到 PPR matrix 在大图上通常是 dense 的，即使原图很 sparse，PPR 中很多节点对也有非零相似度。

因此不能完整存储 PPR matrix。

PPRGo 的想法：

  • 预先计算 PPR matrix 的 sparse approximation。
  • 每行只保留最重要的若干 entries。
  • 训练时直接使用这个预计算传播矩阵，减少每次 forward/backward 的开销。

具体 forward push 近似细节不需要作为重点。

9. Feature Propagation：传播输入特征

最后一部分不是传播 label，而是传播 input node features。

SGC：Simplifying Graph Convolutional Network

老师说 GCN 训练慢，层数越多：

  • 参数越多。
  • 训练涉及的节点范围随 \(K\) 增大。
  • 实践中 \(K\) 通常只取 1、2、3。

SGC 的想法：

  • 去掉非线性 activation。
  • 多层 GCN 就变成对输入特征的线性传播。
  • 可以先预计算传播后的特征： [ A^K X ]
  • 然后再在这些特征上训练普通分类器 / MLP。

优点：

  • propagation 没有可训练参数。
  • 可以作为 preprocessing。
  • 不需要 GPU 也能预计算。
  • 实践中很多分类任务表现不错。

AGP：Approximate Graph Propagation

SGC 只取一个传播长度 \(K\) 的项。

AGP 更一般：对不同长度的传播结果做 weighted sum。

直觉：

  • 不同传播长度代表不同范围的 neighbourhood 信息。
  • AGP 用权重组合多个传播长度。
  • 精确公式不重要，理解它是 generalized feature propagation 即可。

10. 考点重点

  • Label propagation 基于 homophily。
  • 会写 simple label propagation 更新式： [ p_v^{(k)}=_{uN(v)}p_u^{(k-1)} ]
  • 知道 label propagation 和 PageRank 的区别：LP 按目标节点度数取邻居平均；PageRank 按源节点出度分流。
  • 知道更新顺序不重要，因为第 \(k\) 轮只用第 \(k-1\) 轮的值。
  • 知道 multi-class 用 one-hot / probability vector。
  • 理解 smoothness 和 fitting 两个 high-level constraints，不背矩阵推导。
  • 知道 Correct and Smooth：先预测 soft labels，再传播 errors 做 correction，再传播 labels 做 smoothing。
  • 知道 GNN 的 \(K\)-hop 限制和 over-smoothing。
  • 知道 APPNP 用 PageRank-style propagation 传播 MLP 输出。
  • 知道 SGC 是 feature propagation：先传播特征，再训练分类器。
  • exact formulas、Laplacian 推导、matrix inverse、forward push 细节不是重点。