在谱聚类中，我们找不到图的特征向量（图不是矩阵），而是与图的邻接矩阵相关的拉普拉斯矩阵的特征值/特征向量：

图 => 邻接矩阵 => 拉普拉斯矩阵 => 特征值（谱）。

邻接矩阵描述了两个图顶点之间的“相似性”。在最简单的情况下（无向无权简单图），矩阵中的值“1”表示由边连接的两个顶点，值“0”表示这些顶点之间没有边。

因此，邻接矩阵下的空间是连通性空间，列向量的行“i”是与顶点“i”的连通性的度量。换句话说，邻接和拉普拉斯矩阵从顶点映射到顶点连接。

例子

假设一个具有 3 个顶点 {1,2,3} 和边 (1,2) 和 (2,3) 的简单图。相应的拉普拉斯矩阵为：

$$A=\begin{pmatrix} 1 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 1 \end{pmatrix}$$

a) 顶点 1，比在顶点空间是 (1,0,0) 映射到：

$$A\begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix} = \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix}$$

如果我们逐个组件分析产品结果，则意味着：

• 顶点 1 连接到 1 个节点。
• 顶点 2 连接到顶点 1
• 顶点 3 未连接到顶点 1。

b) 顶点 1 和 2 的集合，在顶点空间中表示为 (1,1,0)，映射到：

$$A\begin{pmatrix} 1\\ 1\\ 0 \end{pmatrix} = \begin{pmatrix} 0\\ 1\\ -1 \end{pmatrix}$$

意思是：

• 顶点 1 在集合 {1,2} 的内部或外部，而不是边界（在这种具体情况下，它是内部的：属于集合并且与集合外的任何节点都没有边）。
• 顶点 2 是集合中的一个顶点，并连接到集合外的一个顶点（内部边界）。
• 顶点 3 是一个不在集合中但与其相连的顶点（外部边界）。

最后，看看如果再次将（内/标量积）先前的结果乘以顶点向量会发生什么：

$$\begin{pmatrix} 1 & 1 & 0 \end{pmatrix} A\begin{pmatrix} 1\\ 1\\ 0 \end{pmatrix} = 1$$

它给出了将节点集 {1,2} 与剩余图连接起来的边数。