CS267 · 第 14 课

机器学习（无监督）

从聚类到降维，从图神经网络到分布式 SpMM：Aydin Buluc 深入讲解无监督学习算法的数学原理与大规模并行实现。

---

聚类方法概览

聚类是无监督学习的核心任务：将数据划分为若干组（cluster），使得组内相似度高、组间相似度低。Aydin Buluc 将聚类方法分为五大类：

方法	核心思想	代表算法
Centroid-based	用中心点代表簇，迭代优化中心位置	K-Means, K-Medoids
Flow-based	基于图流/网络流的最大流最小割	MCL (Markov Cluster)
Spectral	利用图拉普拉斯矩阵的特征向量	Normalized Cut, NJW
Density-based	高密度区域形成簇，低密度区域为边界	DBSCAN, OPTICS
Agglomerative	自底向上合并最近簇	单链接、全链接、WARD

两大聚类标准：Compactness vs Connectivity

标准	含义	适用方法	示意图
Compactness（紧凑性）	簇内点到中心的距离最小化	K-Means, K-Medoids	球形簇
Connectivity（连通性）	簇内点在图中"连通"即可	Spectral, DBSCAN, Agglomerative	任意形状簇

---

谱聚类（Spectral Clustering）

谱聚类是一类基于图拉普拉斯矩阵（Graph Laplacian）特征分解的强大聚类方法，能够发现任意形状的簇。

第一步：构建相似图

将数据点视为图的顶点，点之间的相似度作为边权重。三种经典构图方式：

方法	边的定义	特点
ε-neighborhood	距离 < ε 的点对连边	图可能不连通
k-Nearest Neighbor (kNN)	每个点连最近的 k 个邻居	图稠密，需对称化
Fully Connected	所有点对都连边，权重用高斯核	最稠密，\(W_{ij} = \exp(-\|x_i - x_j\|^2 / 2\sigma^2)\)

第二步：拉普拉斯矩阵

定义相似矩阵 \(W\)（权重矩阵），度矩阵 \(D = \text{diag}(d_i)\)，其中 \(d_i = \sum_j W_{ij}\)：

矩阵	定义	性质
非归一化拉普拉斯	\(L = D - W\)	特征值 ≥ 0
归一化拉普拉斯（对称）	\(L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}\)	特征值 ∈ [0, 2]
归一化拉普拉斯（随机游走）	\(L_{rw} = D^{-1} L = I - D^{-1} W\)	与 \(L_{sym}\) 特征值相同

第三步：归一化谱聚类算法（Ng et al. 2002）

特征值求解：大规模并行算法

当 n 达到百万/亿级时，需要高效的大规模特征值求解器：

算法	核心操作	适用场景
Lanczos	Krylov 子空间迭代 + SpMV	稀疏矩阵，求少量极端特征值
SpMV	稀疏矩阵-向量乘法	Lanczos 的底层原语
LOBPCG	Locally Optimal Block Preconditioned CG	比 Lanczos 更稳定，可并行
PARPACK	并行 ARPACK	分布式内存 SpMV + 隐式重启

---

马尔可夫聚类算法（MCL）

MCL（Markov Cluster Algorithm）是一种基于随机游走的流聚类方法，由 Stijn van Dongen 提出。其核心思想：在随机游走的"流"中，簇内流动强、簇间流动弱。

MCL 迭代：Expansion + Inflation

MCL 交替执行两个操作，作用于随机矩阵 \(M\)（列随机矩阵）：

操作	数学	作用
Expansion	\(M \leftarrow M \cdot M\)（SpGEMM）	模拟随机游走的 k 步传播，增强连通性
Inflation	\(M_{ij} \leftarrow M_{ij}^r / \sum_k M_{kj}^r\)（Hadamard power）	强化强边、弱化弱边，参数 r 控制粒度

MCL 实现优化：Pruning + Recovery + Selection

技术	作用
Pruning	将极小元素置零，保持稀疏性，避免稠密化
Recovery	补偿被剪枝的重要元素，控制误差
Selection	每列只保留 top-k 元素，控制每行/列密度

HipMCL：分布式 MCL 实现

HipMCL 是 Aydin Buluc 团队开发的分布式 MCL 实现，使用 Sparse SUMMA 算法进行分布式 SpGEMM：

特性	HipMCL 实现
SpGEMM 算法	Sparse SUMMA（2D 块循环）
数据结构	分布式 CSR 稀疏矩阵
可扩展性	支持百万级顶点、十亿级边
典型结果	1024 节点、10 亿边图上，数分钟内完成聚类

---

降维方法

降维是将高维数据投影到低维空间，同时保留尽可能多的信息。两种经典方法：PCA 和 NMF。

PCA 通过 SVD

PCA（主成分分析）通过奇异值分解实现：

• 对数据矩阵 \(X \in \mathbb{R}^{n \times d}\) 中心化
• 计算 SVD：\(X = U \Sigma V^T\)
• 前 k 个右奇异向量 \(V_k\) 即为 k 个主成分方向
• 降维结果：\(X_k = X V_k = U_k \Sigma_k\)

非负矩阵分解（NMF）

NMF 要求分解后的矩阵元素非负，适用于图像、文本等天然非负数据：

\[X \approx WH, \quad W \geq 0, H \geq 0\]

其中 \(X \in \mathbb{R}^{m \times n}\)，\(W \in \mathbb{R}^{m \times k}\)，\(H \in \mathbb{R}^{k \times n}\)。

交替更新框架

NMF 是非凸问题，通常使用交替优化策略：固定一个矩阵，优化另一个：

算法	更新规则	特点
MU（Multiplicative Update）	\(W \leftarrow W \circ \frac{XH^T}{WHH^T}\)（Hadamard 除法）	简单，自动保持非负，收敛慢
ALS（Alternating Least Squares）	\(W = \arg\min_{W \geq 0} \|X - WH\|_F\)（NNLS）	每步解非负最小二乘
ANLS（Alternating NNLS）	精确求解 NNLS 子问题	比 ALS 更稳定，支持正则化

MPI-FAUN：分布式 NMF

MPI-FAUN（Fast and distributed NMF）使用 MPI 实现分布式 NMF：

• 数据按行分块分布在各节点
• 使用 ANLS 算法，每步并行求解局部 NNLS
• 通过 AllReduce 聚合 \(H H^T\) 和 \(X H^T\)
• 支持大规模文本/推荐系统矩阵分解

---

半监督学习

半监督学习结合少量标注数据和大量未标注数据，核心假设：

• Smoothness assumption：相似点应有相似标签
• Cluster assumption：同一簇的点很可能同标签
• Manifold assumption：高维数据位于低维流形上

---

图神经网络（GNN）

图神经网络将深度学习推广到图结构数据。最经典的 GCN（Graph Convolutional Network）每一层的计算可以表示为：

分布式 SpMM 算法

大规模 GNN 训练需要分布式 SpMM。Aydin Buluc 介绍了几种经典并行策略：

算法	数据分布	通信模式
1D SpMM	按行分块	AllGather 特征矩阵
1.5D SpMM	行分块 + K 副本	ReduceScatter + AllGather（K 折通信量）
2D SpMM	2D 块循环	行/列 AllGather（Cannon 风格）
3D SpMM	3D 处理器网格	K 维度上 Reduce（最小通信）

CAGNET：分布式 GCN 训练

CAGNET（Communication-Avoiding GNN）是 3D SpMM 的具体实现：

• 将邻接矩阵和特征矩阵分布在 3D 处理器网格上
• 在 K 维度上执行 Reduce-Scatter
• 通信量比 2D 减少 \(O(\sqrt[3]{P})\) 倍
• 在超大规模图上展示近线性扩展

---

采样方法：GraphSAGE 与 LADIES

全图 SpMM 在大规模图上仍太贵。采样方法通过 mini-batch 降低计算量：

方法	采样策略	并行实现
GraphSAGE	每层均匀采样固定数目的邻居	采样 = 稀疏矩阵索引（SpGEMM 变体）
LADIES	按权重采样，优先选重要邻居	采样 + 稀疏矩阵乘法

分布式采样：1.5D SpGEMM

分布式采样可以通过 1.5D SpGEMM 高效实现：

• 将采样矩阵复制 K 份，每份按行分块
• 每个节点独立采样本地邻居
• 通过 AllGather 收集邻居特征
• 通信量降为 1D 的 1/K

---

本课要点

---

知识检查