AdaGraph：一种克服维度诅咒并实现科学发现的图原生聚类算法
AdaGraph是一种基于图原生的聚类算法，源自结构中心机器学习（SC-ML）范式。它通过k近邻图拓扑结构替代欧几里得距离度量，从根本上解决了高维数据中的维度诅咒问题。该算法无需预先指定聚类数量k，能原生处理噪声，并通过SLCD框架实现扩展。在10个合成基准测试（维度从10到5000）中，其配套的Graph-SCOPE指标平均ARI达0.900，在9/10数据集上正确选择k，优于传统指标。在肝细胞癌基因共表达、文本聚类和材料科学三个科学领域均取得了显著成果。
一种名为AdaGraph的新型聚类算法近日由研究人员提出，该算法基于结构中心机器学习（SC-ML）范式，完全在图拓扑结构内运行，旨在克服传统距离度量在高维空间中的失效问题。论文于2026年5月5日提交至arXiv，并计划投稿至KDD 2027。
AdaGraph的核心创新在于用k近邻（kNN）图拓扑取代欧几里得距离。在高维数据中，距离度量往往变得均匀且无信息，而kNN图保留了数据点间的相对邻近关系，使得聚类在高维下依然有效。算法无需用户预先指定聚类数量k，能够自动识别簇的数目，并原生地识别和处理噪声点。此外，通过SLCD（采样-学习-校准-部署）框架，AdaGraph具备了良好的扩展性，可应用于大规模数据集。
为了进行无监督调优，AdaGraph与Graph-SCOPE指标配对使用，后者是SC-ML领域提出的另一个基于拓扑的聚类有效性指数。在10个合成数据集（维度覆盖10至5000）上的测试中，Graph-SCOPE的平均调整兰德指数（ARI）达到0.900，并在9个数据集上正确选出了最优聚类数量k，明显优于Silhouette、Davies-Bouldin和Calinski-Harabasz等传统指标。Graph-SCOPE的Kendall tau与真实聚类质量的相关性超过0.92，而Silhouette仅为0.46左右。
研究人员在三个科学领域验证了AdaGraph的实际性能。在生物信息学中，针对肝细胞癌的基因共表达分析（GSE14520数据集，包含10,000个基因和488名患者），AdaGraph在不进行降维的情况下识别出了条件特异性基因模块，而这些模块是WGCNA、ICA、NMF和Spectral Biclustering等方法无法分辨的。在自然语言处理领域，对20NG-6cat数据集进行文本聚类时，AdaGraph取得了0.751的ARI，相比之下HDBSCAN仅为0.464，相对提升幅度达62%。在材料科学中，对超导体（145维Magpie特征）、钙钛矿和JARVIS-DFT材料的聚类测试中，AdaGraph在所有三个数据集上均获得了最高的Graph-SCOPE分数。
这些结果表明，AdaGraph通过图原生方法有效解决了维度诅咒问题，为高维数据聚类提供了强大工具，并在多个科学领域展现出推动发现的能力。论文包含12页、4张图和1张表格，目前尚为完整版本的前期准备工作。