2025-11-12T15:28:09.891883

Structure-Aware Spectral Sparsification via Uniform Edge Sampling

He, Drineas, Khanna
Spectral clustering is a fundamental method for graph partitioning, but its reliance on eigenvector computation limits scalability to massive graphs. Classical sparsification methods preserve spectral properties by sampling edges proportionally to their effective resistances, but require expensive preprocessing to estimate these resistances. We study whether uniform edge sampling-a simple, structure-agnostic strategy-can suffice for spectral clustering. Our main result shows that for graphs admitting a well-separated $k$-clustering, characterized by a large structure ratio $Υ(k) = λ_{k+1} / ρ_G(k)$, uniform sampling preserves the spectral subspace used for clustering. Specifically, we prove that uniformly sampling $O(γ^2 n \log n / ε^2)$ edges, where $γ$ is the Laplacian condition number, yields a sparsifier whose top $(n-k)$-dimensional eigenspace is approximately orthogonal to the cluster indicators. This ensures that the spectral embedding remains faithful, and clustering quality is preserved. Our analysis introduces new resistance bounds for intra-cluster edges, a rank-$(n-k)$ effective resistance formulation, and a matrix Chernoff bound adapted to the dominant eigenspace. These tools allow us to bypass importance sampling entirely. Conceptually, our result connects recent coreset-based clustering theory to spectral sparsification, showing that under strong clusterability, even uniform sampling is structure-aware. This provides the first provable guarantee that uniform edge sampling suffices for structure-preserving spectral clustering.
academic

Structure-Aware Spectral Sparsification via Uniform Edge Sampling

基本信息

  • 论文ID: 2510.12669
  • 标题: Structure-Aware Spectral Sparsification via Uniform Edge Sampling
  • 作者: Kaiwen He (Purdue University), Petros Drineas (Purdue University), Rajiv Khanna (Purdue University)
  • 分类: cs.LG cs.DS
  • 发表会议: 39th Conference on Neural Information Processing Systems (NeurIPS 2025)
  • 论文链接: https://arxiv.org/abs/2510.12669

摘要

谱聚类是图分割的基础方法，但其对特征向量计算的依赖限制了在大规模图上的可扩展性。经典的稀疏化方法通过按有效电阻比例采样边来保持谱性质，但需要昂贵的预处理来估计这些电阻。本文研究简单的均匀边采样策略是否足以用于谱聚类。主要结果表明，对于具有良好分离k聚类的图（由大的结构比Υ(k) = λk+1/ρG(k)刻画），均匀采样能保持用于聚类的谱子空间。具体地，均匀采样O(γ²n log n/ε²)条边（γ为拉普拉斯条件数）能产生一个稀疏化图，其顶部(n-k)维特征空间与聚类指示向量近似正交，确保谱嵌入保持忠实性且聚类质量得以保持。

研究背景与动机

核心问题

谱聚类虽然是发现图中社区结构的基础方法，但在处理大规模图时面临计算瓶颈。主要挑战在于：

  1. 计算复杂性：计算图拉普拉斯矩阵的特征向量在大规模图上计算代价极高
  2. 预处理开销：经典的谱稀疏化方法需要计算有效电阻，这本身就是一个昂贵的过程
  3. 可扩展性限制：现有方法难以处理百万级节点和边的图

研究动机

作者提出一个关键问题：在什么条件下，简单的均匀边采样（无需任何重预处理）就足以保持谱聚类所需的结构？

直观上，如果图中存在连贯的聚类结构，那么标准的基于有效电阻的采样器可能是过度的。在极端情况下，如果存在断开但连贯的聚类，均匀采样显然足以保持聚类结构。

现有方法局限性

  1. 有效电阻采样：虽然能产生高质量的谱稀疏化器，但估计有效电阻需要解大型拉普拉斯线性系统
  2. 计算开销：预处理的开销可能抵消稀疏化带来的计算收益
  3. 结构忽视：现有方法没有充分利用图的聚类结构信息

核心贡献

  1. 结构感知的稀疏化保证：证明了在标准可聚类假设下，均匀采样能产生保持聚类结构的谱稀疏化器
  2. 簇内边的电阻界限：为聚类图中边的有效电阻导出了新的界限，量化了强聚类结构如何约束边的"谱质量"
  3. 特征空间矩阵Chernoff分析：引入了针对顶部(n-k)特征向量子空间的矩阵Chernoff集中论证
  4. 理论连接：将最近的基于核心集的聚类理论与谱稀疏化连接起来

方法详解

任务定义

输入：无向图G = (V,E)，目标聚类数k 输出：稀疏化图G̃，保持原图的k-路聚类结构 目标：使用均匀边采样实现谱保持的图稀疏化

核心概念

结构比(Structure Ratio)

定义结构比Υ(k) = λk+1/ρG(k)，其中：

  • λk+1：归一化拉普拉斯矩阵的第(k+1)个特征值
  • ρG(k)：图的k-路扩展常数

大的Υ(k)表示图具有明显的k-聚类结构。

rank-(n-k)有效电阻

定义4.4：给定图G，设L = VΣV^T为非归一化拉普拉斯矩阵，定义：

Ln-k := Σ(i=k+1 to n) λi vi vi^T
Rn-k_eff(a,b) := ⟨δa - δb, L+n-k(δa - δb)⟩

主要理论结果

定理4.3（主要结果）

对于满足结构定理的无权图G，如果均匀采样O(κ²n log(n)/ε²)条边，其中κ = λn/λk+1为rank(n-k)条件数，则得到的稀疏化拉普拉斯矩阵L̃满足：

‖Ṽn-k Ṽ^T n-k C‖²F ≤ k(1/Υ(k) + ε/(1-ε) κ)

其中Ṽn-k为L̃的顶部n-k个特征向量矩阵。

技术创新点

1. 簇内边电阻界限（引理4.5）

对于同一聚类内的顶点对{a,b}，其rank-(n-k)有效电阻满足：

2/λk+1 ≥ R^n-k_eff(a,b) ≥ (1/κ)(1-k/Υ(k)) · 2/λk+1

2. 杠杆分数分布近似（引理4.7）

在良好聚类假设下，杠杆分数概率分布pe与均匀分布punif满足：

(1-k/Υ(k))(1-ρG(k))/κ · punif ≤ pe ≤ κ/((1-k/Υ(k))(1-ρG(k))) · punif

3. 矩阵Chernoff分析（定理4.8）

通过均匀采样O(κ²n log(n)/ε²)条边，可以保证：

(1-ε)x^T Lx ≤ x^T LH x ≤ (1+ε)x^T Lx

对所有x ∈ span(vk+1,...,vn)成立。

实验设置

数据集

  1. 随机块模型(SBM)：k=4个聚类，每个聚类200个节点
  2. 层次随机块模型：4个顶层聚类和子聚类，共16个聚类
  3. LFR基准图：800个节点的网络基准图

评价指标

使用底部k=4个特征向量与真实聚类指示向量之间的最大主角：‖sin Θ(Ṽk, C)‖∞ 较小的角度表示谱嵌入中聚类结构保持更好。

对比方法

  • 均匀边采样：本文提出的方法
  • 有效电阻采样：经典的基于重要性采样的方法

实验设置

  • 良好聚类图：大的簇内-簇间边概率比
  • 弱聚类图：小的簇内-簇间边概率比
  • 每个实验运行20次，报告均值和标准差

实验结果

主要结果

  1. 良好聚类图：均匀采样在强聚类结构上表现与有效电阻采样相当，甚至略优
  2. 弱聚类图：即使在弱聚类设置下，均匀采样仍遵循与有效电阻采样相似的误差轨迹
  3. 层次结构：在层次随机块模型上，均匀采样同样表现良好
  4. LFR基准：在真实网络基准上验证了方法的有效性

关键发现

  • 在良好聚类的图上，均匀采样实际上略优于有效电阻采样
  • 作者假设这是因为均匀采样偏向于欠采样跨聚类边，从而产生与聚类成员向量更强的子空间对齐

相关工作

可聚类图与谱聚类

  • 结构定理：Peng等人证明了当Υ(k) = Ω(k²)时，底部k个拉普拉斯特征向量的子空间接近k个聚类指示向量的子空间
  • 弱化假设：Macgregor和Sun证明了在更弱的Υ(k)假设下仍能保证谱聚类成功

谱图稀疏化

  • 经典结果：Spielman引入了通过有效电阻比例采样产生ε-谱稀疏化器的算法
  • 线性大小稀疏化器：Batson等人证明了O(n/ε)边的线性大小谱稀疏化器的存在性

聚类核心集的均匀采样

  • 元定理：Braverman等人展示了在数据结构良好时，均匀采样可以产生与重要性采样同样有效的聚类核心集
  • 平衡聚类：Huang和Vishnoi研究了平衡聚类中均匀采样的作用

结论与讨论

主要结论

  1. 理论保证：首次为均匀边采样在结构保持谱聚类中的充分性提供了可证明的保证
  2. 实用价值：为谱聚类提供了简单且可扩展的预处理步骤
  3. 理论连接：连接了核心集理论与谱稀疏化

局限性

  1. 假设条件：需要图具有良好的聚类结构（大的Υ(k)）
  2. 条件数依赖：采样复杂度依赖于条件数κ，在某些图上可能较大
  3. 无权图限制：当前分析主要针对无权图

未来方向

  1. 电阻界限优化：收紧电阻界限，特别是改善对κ和Υ(k)的依赖
  2. 加权图扩展：将分析扩展到加权图或重叠聚类
  3. 其他图问题：探索类似的结构感知均匀采样结果是否适用于半监督学习等其他图问题

深度评价

优点

  1. 理论创新：首次证明了在结构条件下均匀采样的充分性，填补了理论空白
  2. 实用价值：消除了昂贵的电阻计算需求，显著提高了可扩展性
  3. 技术贡献：引入了rank-(n-k)有效电阻等新的分析工具
  4. 实验验证：在多种图模型上验证了理论结果

不足

  1. 采样复杂度：虽然避免了预处理，但采样复杂度仍然较高，特别是当κ较大时
  2. 结构假设：对图结构的假设相对严格，限制了适用范围
  3. 常数因子：理论界限中的常数可能不够紧致

影响力

  1. 学术价值：为谱稀疏化理论提供了新的视角，连接了不同研究领域
  2. 实用意义：为大规模图分析提供了更简单有效的工具
  3. 启发性：可能启发更多关于结构感知采样的研究

适用场景

  1. 社交网络分析：具有明显社区结构的社交网络
  2. 生物网络：蛋白质相互作用网络等具有模块化结构的生物网络
  3. 推荐系统：用户-物品交互图中的协同过滤

参考文献

本文引用了谱图理论、矩阵扰动理论、聚类分析等多个领域的重要工作，包括：

  • Spielman & Srivastava关于谱稀疏化的开创性工作
  • Peng等人关于可聚类图结构定理的研究
  • Davis-Kahan定理等矩阵扰动理论的经典结果

总结：本文在谱图稀疏化领域做出了重要的理论贡献，证明了在特定结构条件下简单均匀采样的有效性。虽然存在一些局限性，但为大规模图分析提供了新的理论基础和实用工具，具有重要的学术和应用价值。