图是纯关系数据——只有「谁挨着谁」，没有坐标、没有距离，肉眼看不出结构。谱图论的招数是：把图变成矩阵，然后问它的特征值。
为什么管用？想象每条边是一根弹簧把两端往一起拉，给每个节点一个数（想成高度），整张图就成了一面能振动的鼓。特征向量是振动模式，特征值是频率。低频是缓慢变化的大尺度形状，高频是相邻节点反号的锯齿。于是「图的粗结构」被翻译成「图的低频」。
$L = D - A$。$A$ 是邻接矩阵（$i,j$ 相邻则 $A_{ij}=1$），$D$ 是对角度矩阵（$D_{ii}=d_i$ 即节点 $i$ 的邻居数）。作用在赋值向量 $x$ 上：$(Lx)_i=\sum_{j\sim i}(x_i-x_j)$——我的值减去每个邻居的值，正是连续拉普拉斯算子 $\nabla^2$ 的离散版。关键恒等式：
右边是「沿每条边的落差平方和」，衡量这个赋值有多不平滑。由此立得：$L$ 半正定，特征值 $0=\lambda_1\le\cdots\le\lambda_n$；$\lambda_1=0$ 对应全 1 向量——处处相等，落差为零。
这个恒等式把三样东西压成同一个式子：线性代数的二次型、微分几何的 Dirichlet 能量、组合结构的边集。连续世界的拉普拉斯算子要靠极限与光滑性才能定义；图上不需要，它就是减法。更精妙的是 0 特征值的重数恰好等于连通分支数——纯代数的量精确数出纯拓扑的量。至于 Kac 那个「能否听出鼓的形状」，图上的答案是「几乎能」：存在同谱却不同构的图，最小的一对只有 6 个节点。谱是有损、却极高效的图指纹。
PageRank 是随机游走矩阵的主特征向量；图形学用 $L$ 解调和映射把三维曲面摊平；电路里 $L$ 就是基尔霍夫矩阵，伪逆给出两点间的有效电阻；矩阵树定理说生成树数目等于 $L$ 任一余子式的行列式——数组合对象，只需算行列式。
要判断一个真实网络「有结构」，先得知道「没有结构长什么样」。Erdős–Rényi 模型 $G(n,p)$ 给出这条基线：$n$ 个节点，每一对独立地以概率 $p$ 连边，别无规则。
惊人之处：把平均度 $c=p(n-1)$ 从 0 慢慢调大，网络不是平滑变密，而是在 $c=1$ 处突然凝结。$c<1$ 时只有 $O(\log n)$ 大小的碎片；$c>1$ 时，一个含常数比例节点的巨型分支瞬间出现。像水结冰——是相变，不是渐变。
巨型分支占全图的比例 $S$ 满足自洽方程：
逐项解释：$S$ 是「随机抓一个节点，它落在巨型分支里」的概率，$c$ 是平均度。推导靠反面论证——一个节点不在巨型分支，当且仅当它的每个邻居都不在；邻居数近似服从 Poisson($c$)，于是「全都不在」的概率是 $e^{-cS}$。$c\le 1$ 时方程只有 $S=0$；$c>1$ 时突然多出一个正解——这叫分岔。
纯粹局部的规则（每对节点各自掷硬币，谁也不知道全局）竟产生一个全局的、尖锐的阈值。而 $c=1$ 有极干净的解释：分支过程的临界点——每个节点平均「生出」1 个新邻居，正是灭绝与爆炸的分界。同一个 1 出现在核裂变链式反应、流行病的 $R_0$、随机 SAT 的可满足性阈值里。
谱上也有对应：随机图的特征值分布收敛到 Wigner 半圆律，而真实网络的谱总有几个甩出半圆之外的离群值——那正是结构的信号。噪声有形状，偏离噪声才叫信息。
网络鲁棒性：随机删边到什么比例网络会碎掉，就是渗流阈值，用于电网与互联网骨干的抗毁评估；流行病学的 $R_0=1$ 是同一个临界点。随机图作为零模型，让「模块度」这类指标有了参照系——否则「这里连得比较密」无从判断。
把网络切成两块，要求切断的边尽量少、两块又不能太不平衡。这是组合优化，穷举 $2^n$ 种切法，NP 难。
谱方法的招数是松弛：把「非左即右」的 0/1 硬约束放松成「取一个实数」。约束一松，问题立刻变成求特征向量。$\lambda_2$ 对应的 Fiedler 向量给每个节点一个实数坐标，把节点排在一条直线上——同一社区的自然挤成一堆，在中间剪一刀即可。连续化把指数级搜索变成一次矩阵计算。
在 $\|x\|=1$、$x\perp\mathbf{1}$（排除平凡的常数解）下最小化 $x^{\top}Lx$，由 Courant–Fischer 定理，最小值就是 $\lambda_2$，取到它的就是 Fiedler 向量。$\lambda_2$ 因此叫代数连通度。松弛靠不靠谱？Cheeger 不等式给出定量回答：
$h(G)=\min_{S}\frac{|\partial S|}{\min(|S|,|S^{c}|)}$ 是最稀疏割：把节点分成 $S$ 与补集，$|\partial S|$ 是被切断的边数，分母取较小那半边（防止「切下一个孤立点」作弊）。$h(G)$ 是组合量、要穷举；$\lambda_2$ 是连续量、可以算。
Cheeger 不等式是一句「松弛不会错得太离谱」的定量保证——能算的连续量从两侧夹住算不动的组合量。这不是启发式，是定理；而且它在黎曼流形上有一模一样的形式（Cheeger 原本就是为流形证的）。
反过来读更精彩：$\lambda_2$ 大 $\Rightarrow$ 不存在稀疏割 $\Rightarrow$ 这是扩张图——边很少却极难切开，处处四通八达。它的存在性用随机图两行就证完，要显式写出一个却得动用数论与群论的重武器（Ramanujan 图，Lubotzky–Phillips–Sarnak 1988）。存在性易、构造难，这是组合数学反复上演的张力。
谱聚类是图像分割（Normalized Cuts）、单细胞 RNA 测序细胞分型、社区发现的标准工具。$\lambda_2$ 直接控制马尔可夫链的混合时间——谱间隙越大，随机游走越快忘掉起点，这决定 MCMC 采样效率与分布式共识的收敛速度。扩张图则用于构造纠错码与去随机化算法；数据中心的拓扑设计同样在追求大谱间隙。
CNN 之所以强，是因为图像铺在规则网格上，同一个卷积核可以到处平移。图没有平移对称性——「左边那个邻居」无从谈起。怎么办？
回到谱：在图上做卷积，就是在拉普拉斯的特征基里逐频率缩放——挑一个 $g(\lambda)$，把信号分解到各频率，各乘 $g(\lambda)$，再变回来。可惜完整特征分解要 $O(n^3)$。突破在于只用 $L$ 的多项式 $g(L)=\sum_k\theta_k L^k$：$L^k$ 只连接 $k$ 步以内的节点，所以多项式滤波器天然是局部的，稀疏矩阵乘法就能算。抽象的「谱域滤波」于是落地成具体的「消息传递」：每层把邻居的信息聚合到自己身上。
最常用的 GCN 层（Kipf & Welling, 2017）：
逐项拆解：$\tilde{A}=A+I$ 是加了自环的邻接矩阵（让节点也听得见自己）；$\tilde{D}$ 是对应的度矩阵，两侧的 $\tilde{D}^{-1/2}$ 做对称归一化，防止高度节点把数值冲爆；$H^{(l)}$ 是第 $l$ 层的节点特征矩阵（一行一个节点）；$W^{(l)}$ 是可学参数；$\sigma$ 是非线性。括号里的算子恰好等于 $I-\tilde{L}$——$g(\lambda)=1-\lambda$ 的一阶多项式，一个低通滤波器。
它把「卷积」从欧氏网格解放出来，同时暴露出卷积的本质不是滑窗，而是「与对称性作用可交换的线性算子」——网格上这个对称性是平移，图上则是拉普拉斯的特征基。这是几何深度学习的纲领：先问数据有什么对称性，再由对称性推出该用什么算子。
更漂亮的是它精确预言了工程界人尽皆知的毛病：过平滑。堆 $k$ 层等于反复施加低通滤波，等效增益 $g(\lambda)^k$ 除 $\lambda\approx 0$ 附近全被指数压死，最后所有节点的特征收敛到同一个向量——正是 $\lambda_1=0$ 那个常数模态。一个纯谱论的事实，解释了深层 GNN 为何训练不出来。
分子性质预测与药物发现（GNN 已是标配）；AlphaFold 的结构模块在残基图上传递信息；Google Maps 用 GNN 做 ETA 预测；推荐系统（PinSage）、芯片布局、粒子模拟也都在图上。而对抗过平滑的手段——残差连接、图注意力（GAT）——本质是同一件事：让滤波器不再是纯低通。