AdaGraph：一种克服维度灾难、推动科学发现的图原生聚类算法

# 1. 引言
来源：https://arxiv.org/html/2605.16320
AdaGraph：一种克服维度灾难并实现科学发现的图原生聚类算法 Ahmed Elmahdi 独立研究员 [email protected] (https://arxiv.org/html/2605.16320v1/mailto:[email protected])

2026年5月 — arXiv 预印本。完整论文正在准备中，计划投稿 KDD 2027。

摘要

我们提出 **AdaGraph**，一种图原生聚类算法，源自 **以结构为中心的机器学习（SC-ML）** 范式——一个无监督学习的新领域，它用以结构为中心（基于拓扑）的计算取代以几何为中心（基于距离）的计算，从根本上消解了维度灾难。AdaGraph 完全在 $k$ 近邻（kNN）图拓扑内运行，这种表示法能在欧几里得距离度量失效的任意高维度中保留有意义的关联结构。AdaGraph 无需预先指定聚类数量 $k$，原生处理噪声，并借助 SLCD（采样–学习–校准–部署）原型-部署框架实现可扩展性——这本身就是 SC-ML 原生的可扩展性解决方案。作为其无监督评估与调优目标，AdaGraph 与 Graph-SCOPE 配对使用，后者是基于拓扑的聚类有效性指标（CVI），作为另一项 SC-ML 贡献单独引入[1 (https://arxiv.org/html/2605.16320#bib.bib1)]。在从 $d=10$ 到 $d=5000$ 的 10 个合成基准上，Graph-SCOPE 实现了平均 ARI=0.900，并在 9/10 个数据集上正确选择了 $k$——优于 Silhouette、Davies-Bouldin 和 Calinski-Harabasz——同时在所有测试维度上保持 Kendall $\tau \geq 0.92$ 与真实聚类质量的相关性（Silhouette: $\tau \approx 0.46$）。我们在三个独立的科学领域对 AdaGraph 进行了验证：(1) 肝细胞癌中的基因共表达发现（GSE14520，10,000 个基因，488 名患者，未降维），AdaGraph 识别出 WGCNA、ICA、NMF 和 Spectral Biclustering 未能解析的条件特异性基因模块；(2) 自然语言文本聚类，AdaGraph 在 20NG-6cat 上达到 ARI=0.751，而 HDBSCAN 为 0.464（相对提升 62%）；(3) 超导体（145 维 Magpie 特征）、钙钛矿和 JARVIS-DFT 材料的材料科学聚类，AdaGraph 在所有三个数据集上取得最高 Graph-SCOPE 分数。这些结果确立了 AdaGraph 作为 SC-ML 框架聚类引擎的地位，并表明 SC-ML 原生算法在揭示高维真实世界数据中的科学意义结构方面具有独特能力。

关键词：基于图的聚类，维度灾难，以结构为中心的机器学习，SC-ML，kNN 图，聚类有效性指标，Graph-SCOPE，SLCD，基因共表达，材料信息学，自然语言处理。

无监督聚类是机器学习和数据科学中最基础的任务之一。然而，在高维场景（基因组学、自然语言、材料信息学、天体物理学）中，其实用性因维度灾难[5 (https://arxiv.org/html/2605.16320#bib.bib5),6 (https://arxiv.org/html/2605.16320#bib.bib6)]而受到严重限制。随着维度增加，最大与最小成对距离之比趋近于 1.0，使得基于欧几里得距离的相似性失去意义。因此，几乎所有已建立的聚类算法——K-Means、DBSCAN、HDBSCAN、高斯混合模型——在 $d \approx 50$–$100$ 维度以上都会灾难性退化。

问题不仅仅是算法层面的，更是**计量学层面**的。即使算法假设性地产生正确的聚类分配，现有的 CVI（如 Silhouette）在高维中也无法可靠地评估它们。我们的实验证实了这一点：无论维度如何，当 $d \geq 50$ 时，Silhouette 与真实聚类质量的 Kendall $\tau$ 相关性稳定在大约 0.46，使其对于本应测量的质量差异视而不见。所有经典 CVI——Silhouette[17 (https://arxiv.org/html/2605.16320#bib.bib17)]、Davies-Bouldin[9 (https://arxiv.org/html/2605.16320#bib.bib9)]、Calinski-Harabasz[20 (https://arxiv.org/html/2605.16320#bib.bib20)]——都共享着对欧几里得成对距离的相同致命依赖。

两种失败的根源是相同的：传统无监督学习是**以几何为中心**的。它通过距离、体积和基于坐标的密度估计来定义聚类质量——这些量在高维空间中会失去意义。因此，解决方案必须是**范式层面的**：用基于结构的计算取代基于几何的计算。这一洞察催生了 **以结构为中心的机器学习** 范式，这是一个无监督机器学习的新领域，其中学习流水线的每个组成部分——表示、评估、采样和聚类——都被重新设计为在关系结构（kNN 图拓扑）上运行，而非在欧几里得几何上运行。

SC-ML 框架由一个连贯的、相互关联的创新生态系统组成，每个创新都作为单独的贡献引入（第2节 (https://arxiv.org/html/2605.16320#S2)）。本文介绍 **AdaGraph**，作为 SC-ML 生态系统顶点的图原生聚类算法。AdaGraph 将自适应图划分与 kNN 图构建相结合，在 SLCD[4 (https://arxiv.org/html/2605.16320#bib.bib4)] 可扩展部署框架内使用 Graph-SCOPE[1 (https://arxiv.org/html/2605.16320#bib.bib1)] 作为其优化信号，并产生由 Graph-SCOPE（无监督）和 SCOPE[2 (https://arxiv.org/html/2605.16320#bib.bib2)]（有监督，用于基准测试）共同评估的聚类分配。

我们在四个科学复杂性递增的领域验证了 AdaGraph：(i) 从 $d=10$ 到 $d=5000$ 的严格合成基准，隔离特定高维聚类挑战；(ii) 肝细胞癌（GSE14520）中的基因共表达发现，在完整的 488 维患者表达空间中运行，未进行任何降维；(iii) 使用 384 维句子嵌入对 20 Newsgroups 和 AG News 进行自然语言文本聚类；(iv) 超导体、钙钛矿和 JARVIS-DFT 材料的材料科学聚类，其中聚类分配映射到已知的材料族，噪声标记点代表新的发现候选。

#### 贡献。

1. **AdaGraph**：首个被设计为完全在 kNN 图拓扑内运行的图原生聚类算法，在图构建后无需几何计算，也无需预先指定 $k$。
2. **完整的 SC-ML 流水线**：一个经过验证的端到端系统（AdaBox + 密度感知采样 + SLCD + Graph-SCOPE），用于与维度无关的大规模无监督聚类。
3. **跨四个科学领域的实证验证**：合成基准、肝细胞癌基因组学、自然语言处理和材料信息学，每个都展示了 SC-ML 在揭示几何中心方法无法发现的结构方面的独特能力。

## 2. 以结构为中心的机器学习范式

以结构为中心的机器学习是一个新的无监督机器学习范式，其核心原则是：**聚类质量是关系结构的属性，而非几何距离的属性**。SC-ML 将传统聚类流水线中每个依赖几何的操作替换为基于结构的等价操作，后者在 kNN 图拓扑上运行。这使得 SC-ML 算法对维度灾难具有内在鲁棒性：kNN 图拓扑——与欧几里得距离统计不同——在任意高维度中仍保持信息量，因为它仅依赖于邻居的相对排序，这在 $d \to \infty$ 时得以保留。

自诞生以来，以几何为中心的范式一直主导着无监督学习：K-Means 最小化簇内欧几里得距离平方和；Silhouette 通过平均簇间和簇内距离来评估质量；DBSCAN 将密度定义为 epsilon 球内的点数；GMM 通过欧几里得协方差矩阵参数化聚类。所有这些表示法都因相同的几何原因在高维中崩溃。SC-ML 的基础洞察是，这种崩溃不是一个需要修补的实现细节——它是以几何中心范式本身的后果。

SC-ML 的基本表示转变是将数据编码为 kNN 图 $G=(V,E)$，其中每个点是一个节点，有向边将每个点连接到其 $k$ 个最近邻。然后通过图论属性来定义聚类质量：边划分的模块度、簇内边的凝聚度、图中聚类边界的锐利度，以及相对于图连通性的噪声分配的合法性。这些量都不依赖于绝对距离或坐标表示。

### 2.1. SC-ML 生态系统

SC-ML 框架是一个可互操作的组件生态系统，每个组件解决高维聚类流水线中的一个特定子问题。它们共同构成一个完整的、与维度无关的无监督学习系统：

1. **SCOPE[2 (https://arxiv.org/html/2605.16320#bib.bib2)]**：一种基于结构的**有监督**聚类评估指标，提供多维度的质量分解，包括核心纯度、边界召回率、聚类精确率、噪声 F1 和计数准确率。SCOPE 用可机制解释的质量信号取代 ARI/NMI（后者会压缩结构信息），并定义了所有 SC-ML 算法进行基准测试所依据的真实准则。
2. **AdaBox[3 (https://arxiv.org/html/2605.16320#bib.bib3)]**：SC-ML 的自适应密度估计引擎。AdaBox 通过在 kNN 图嵌入上叠加自适应网格来划分数据流形，基于局部图连接性而非欧几里得 epsilon 球计数来定义密度。AdaBox 是构建 AdaGraph 的低级划分原语。
3. **密度感知采样**：一种 SC-ML 原生的代表性采样策略，抽取固定大小的子样本，保证包含数据中每个密度模式（包括均匀随机采样系统遗漏的稀疏和边界区域）的代表。这确保了子样本上的超参数搜索能忠实地推广到整个数据集。
4. **SLCD[4 (https://arxiv.org/html/2605.16320#bib.bib4)]（采样–学习–校准–部署）**：SC-ML 的可扩展部署框架。SLCD 分四个阶段执行：(a) 对代表性子样本进行密度感知采样；(b) 标签化，当有标注可用时启用有监督校准；(c) 以 Graph-SCOPE 或 SCOPE 为目标函数进行超参数搜索；(d) 通过原型分配或参数转移部署到所有 $n$ 个数据点。SLCD 将复杂度从 $O(n \times \text{trials})$ 降低到 $O(n_s \times \text{trials} + n \times k)$，使得 SC-ML 能在任意大规模数据集上运行。
5. **Graph-SCOPE[1 (https://arxiv.org/html/2605.16320#bib.bib1)]**：SC-ML 的聚类有效性指标。Graph-SCOPE 完全从 kNN 图拓扑计算聚类质量，在图构建后无需欧几里得距离计算。它作为 SCOPE 的无监督代理，使得在没有真实标签的场景下也能进行调优和评估。
6. **AdaGraph（本文）**：顶点的 SC-ML 聚类算法。AdaGraph 将上述所有组件集成到一个可部署系统中：图原生表示、基于拓扑的密度估计、与维度无关的评估以及可扩展部署。

这个生态系统的概念一致性并非偶然。每个组件在设计上都与其他组件在结构上保持一致：SCOPE 定义正确性；Graph-SCOPE 提供无监督代理；AdaBox 提供划分原语；密度感知采样提供代表性保证；SLCD 提供可扩展性；而 AdaGraph 将一切整合为一个可部署的聚类系统。

## 3. AdaGraph 算法

### 3.1. 图原生自适应聚类

AdaGraph 是 SC-ML 聚类算法。给定数据集 $X \in \mathbb{R}^{n \times d}$，它在 SLCD 框架内完全在 kNN 图拓扑上运行，分为三个集成阶段：

**阶段 1：kNN 图构建。** 对于每个点 $x_i$，识别其 $k$ 个最近邻以形成有向边。生成的图 $G=(V,E)$ 捕获了 $X$ 的局部流形结构。与全局欧几里得距离统计（在高维中会集中）不同，局部 kNN 关系即使在 $d=5000$ 时仍保持信息量。这是 SC-ML 原生的表示步骤：后续计算完全是图论的。

**阶段 2：自适应盒子划分（AdaBox[3 (https://arxiv.org/html/2605.16320#bib.bib3)]）。** 通过 kNN 图嵌入，在数据流形上叠加自适应盒子网格。局部图密度低于自适应阈值的区域被标记为噪声；连接的密集区域形成候选聚类。划分参数通过在数据的密度感知子样本上进行多百次试验的随机搜索联合优化，以 Graph-SCOPE 作为无监督目标函数。由于 AdaBox 在图嵌入坐标而非欧几里得坐标上运行，划分在无论环境维度如何的情况下都保持有意义。

**阶段 3：SLCD 原型部署[4 (https://arxiv.org/html/2605.16320#bib.bib4)]。** 在超参数搜索通过密度感知样本（通常 $n_s \approx 1,000$ 个代表性点）确定最优配置后，通过 $k$ 投票原型分配将该配置部署到所有 $n$ 个数据点：每个点从其 $k$ 个最近原型点接收多数投票的标签。这使计算成本从 $O(n \times \text{trials})$ 降低到 $O(n_s \times \text{trials} + n \times k)$，从而实现在拥有数万或数十万个点的数据集上进行可扩展操作，且不降低聚类质量。

### 3.2. Graph-SCOPE：评估与调优目标

AdaGraph 使用 Graph-SCOPE（GS）[1 (https://arxiv.org/html/2605.16320#bib.bib1)] 作为其无监督超参数调优目标和最终聚类质量评估器。Graph-SCOPE 的完整推导、设计原理、组件分析以及针对所有经典 CVI 的全面基准测试在配套论文[1 (https://arxiv.org/html/2605.16320#bib.bib1)]中呈现；我们在此总结关键性质。

GS 是一种基于拓扑的 CVI，完全从 kNN 图结构计算，在图构建后无需任何成对距离计算。它结合了五个结构组件：图模块度（主要质量信号）、边界锐利度、内部一致性、噪声合法性和划分平衡性。关键在于，每个组件都是从 $G$ 中的边连接模式计算的——而非来自欧几里得距离。这使得 GS 在任何维度下都是可靠的质量信号，正如我们的实验所证实的那样（第4.1节 (https://arxiv.org/html/2605.16320#S4.SS1)）。

GS 的复杂度为 $O(nk \log n)$（图构建）和 $O(nk)$（每次评估），使其在多百次试验的超参数搜索中作为调优信号非常高效。AdaGraph 系统的一个关键设计属性是，调优目标（GS）和评估指标（GS）使用相同的拓扑语言。