图分割，针对一种图分割方法进行具体介绍？｜阿里巴巴算法面经解析

60 秒回答模板

我会用 Normalized Cut 具体介绍图分割。给定加权无向图 G=(V,E)，边权表示两个点的相似度或连接强度，目标是把点集划分为 A 和 B，使 A、B 之间的割边权重较小，同时 A、B 本身不能过小或过弱。普通 min-cut 只最小化 cut(A,B)，容易把一个孤立点切出去；Normalized Cut 使用 cut(A,B)/assoc(A,V)+cut(A,B)/assoc(B,V) 作为目标，其中 assoc(A,V) 表示 A 与全图的总连接强度。由于直接求离散最优通常很难，常用谱松弛：构造度矩阵 D 和邻接矩阵 W，得到图拉普拉斯矩阵 L=D-W，求广义特征值问题 Ly=λDy 的较小特征向量，再根据特征向量的符号或阈值把节点划分。多类分割时取前 k 个特征向量形成低维嵌入，再用 k-means 聚类。这个方法适合相似度图、社交网络、图像区域、用户聚类等场景，优点是能捕捉全局结构，缺点是特征分解成本高、对边权构造和 k 值敏感。

考点 问题定义

主线 为什么不用普通最小割

易错点 只说最小割，不说明普通 min-cut 会产生小集合退…

深入解析

问题定义

图分割的输入通常是一个图 G=(V,E)，节点代表对象，边代表关系，边权代表相似度、距离的反函数、交互强度或关联置信度。目标不是随意切开图，而是让同一分区内的节点关系紧密，不同分区之间的连接稀疏。形式化地说，若把 V 划分为 A 和 B，希望 cut(A,B)=Σ W_ij 尽量小，其中 i 属于 A、j 属于 B。

为什么不用普通最小割

普通 min-cut 只关心跨分区边权最小，因此很容易产生不平衡划分。例如某个节点只有一条很弱的边连接到大图，min-cut 会倾向于把这个单点切出去，因为代价最小，但这通常不是我们想要的语义分割。实际任务更希望得到规模和连接强度相对合理的区域，所以需要对 cut 做归一化。

Normalized Cut 目标

Normalized Cut 的目标是 Ncut(A,B)=cut(A,B)/assoc(A,V)+cut(A,B)/assoc(B,V)。其中 assoc(A,V) 是 A 中所有节点与全图节点之间边权之和，可以理解为 A 的总体连接体量。这个目标惩罚把很小、很孤立的集合切出去，因为小集合的 assoc 较小，导致分母小、比值大。它同时考虑跨区边弱和区内体量合理。

谱松弛与拉普拉斯矩阵

直接优化离散划分变量通常是组合优化问题，复杂度很高。谱方法把离散的 0/1 划分变量放松为连续向量。设 W 是加权邻接矩阵，D 是度矩阵，D_ii=Σ W_ij，L=D-W 是图拉普拉斯矩阵。二分场景下，可以通过求 Ly=λDy 的较小特征值对应特征向量来获得节点的一维连续表示，再用 0、均值、中位数或搜索阈值进行切分。

具体算法流程

第一步，根据数据构造相似度图，例如 k 近邻图或半径邻域图，并定义边权。第二步，构造 W、D、L。第三步，求解归一化拉普拉斯相关的特征向量。第四步，若是二分，根据特征向量阈值划分节点；若是 k 分割，取前 k 个较小特征值对应的特征向量，把每个节点映射成 k 维向量，再做 k-means。第五步，用 Ncut 值、模块度、下游任务指标或人工业务指标评估分割质量。

复杂度与工程优化

谱分解是主要成本。对于 n 个节点的稠密矩阵，完整特征分解成本很高；实际大图通常使用稀疏图表示，只求前几个特征向量，并使用 Lanczos、LOBPCG 等迭代方法。工程上还会限制边数、做近似近邻、先粗化再细化、多级划分，或者使用 METIS 这类多级图划分算法来提升可扩展性。

适用场景与局限

Normalized Cut 适合边权能表达相似性的任务，比如用户群体划分、文本或商品相似图聚类、图像区域分割、知识图谱局部结构发现等。它的优势是全局性强，比贪心局部切分更稳定；局限是对相似度构造敏感，对 k 值敏感，处理超大规模动态图成本较高，并且谱嵌入后的聚类步骤可能引入额外不确定性。

与其他方法的关系

min-cut 更适合有明确源点和汇点、带容量约束的二分类切割问题；Normalized Cut 更强调平衡性和全局结构；Louvain、Leiden 等社区发现方法常优化模块度，更适合网络社区结构；METIS 侧重高效多级划分，常用于并行计算、负载均衡和超大图；GNN-based segmentation 则通过节点特征、边特征和监督信号学习分割边界。

易错点

只说最小割，不说明普通 min-cut 会产生小集合退化问题。
把 Normalized Cut 解释成简单按节点数平均，而忽略 assoc 表示连接体量。
只背公式，不说明 W、D、L 分别代表什么以及为什么特征向量能用于划分。
默认图一定是无权无向图，没有讨论边权构造、有向图处理和稀疏化。
把谱聚类说成一定能找到全局离散最优，忽略它使用了连续松弛和后续聚类。
不讨论复杂度，给人感觉方法可以直接套到任意超大规模图上。

面试官追问

为什么 Normalized Cut 能避免把单个点切出去？

因为它不是只看 cut(A,B)，还要除以 assoc(A,V) 和 assoc(B,V)。如果 A 是一个很小的集合，虽然 cut(A,B) 可能很小，但 assoc(A,V) 也很小，导致 cut(A,B)/assoc(A,V) 不一定小。因此单点切割不会天然占优。

第二小特征向量为什么重要？

图拉普拉斯矩阵最小特征值通常对应常数向量，不能提供划分信息。第二小特征向量也常叫 Fiedler 向量，它反映网络结构最主要的低频分离方向。相邻且强连接的节点在该向量上取值接近，弱连接区域之间取值差异更明显，因此可用于二分。

Normalized Cut 和 Ratio Cut 有什么区别？

Ratio Cut 使用 cut(A,B)/|A|+cut(A,B)/|B|，按节点数量做归一化；Normalized Cut 使用 cut(A,B)/assoc(A,V)+cut(A,B)/assoc(B,V)，按连接体量做归一化。若节点度差异很大，Normalized Cut 通常更合理，因为它考虑了节点连接强弱，而不只是节点个数。

如果图是有向图怎么办？

经典谱分割多假设无向加权图。有向图可以先对称化，例如 W'=(W+W^T)/2；也可以使用随机游走视角、PageRank 类转移矩阵、directed Laplacian 或基于流量的分割目标。选择方式取决于边方向是否有语义，例如关注互相关系还是传播路径。

如何选择分区数量 k？

常见方法包括观察特征值间隔，若第 k 个和第 k+1 个特征值差距较大，说明 k 个簇结构可能较明显；也可以用轮廓系数、模块度、Ncut 值、稳定性测试或下游任务指标选择。生产场景还要考虑每个分区的最小规模和解释性。