← 返回 PaperDaily
前沿研究
Apple Research最新论文 | UMAP的kNN图是金矿！3个经典图算法零成本挖掘深层结构
UMAP大家都很熟悉，但它的kNN图往往被忽略。苹果这项研究告诉你，这个中间图结构才是宝藏，三个经典图算法就能零成本挖出深层信息，值得所有做数据可视化和探索性分析的读者了解。
龙哥读论文
发布于 2026-08-14 09:11:49
阅读 3
查看原文
原论文信息如下：
被忽视的宝藏：UMAP的kNN图
UMAP（Uniform Manifold Approximation and Projection）是目前最流行的降维可视化工具之一，几乎成了探索高维数据的标配。大家打开工具、调调参数、看个二维散点图，看起来一切都很完美。
但龙哥告诉你，就像你绘制一张城市地图时，如果只关注最终的地图，就会忽略城市中复杂的道路网络——UMAP的二维可视化，其实只是它内部一个k-近邻图（k-Nearest Neighbor Graph, kNN图）
这个kNN图，才是宝藏！苹果的这项研究一语道破天机：绝大多数人都在盯着那团二维散点图发呆，却忽略了隐藏在其中的、更能反映数据原始结构的kNN图。
UMAP在生成二维散点图之前，第一步就是为每个数据点找到它的k个最近邻（通常k=15），然后构建一个加权有向图。这个图很好地保存了数据在高维空间中的流形（Manifold）结构。但是，在UMAP将点压缩到二维空间后，由于“降维扭曲”（Projection Distortion），很多原始结构信息就丢失了。具体来说，UMAP的优化目标是在低维空间中保持高维空间的局部邻域结构，但为了在二维平面上获得良好的可视化效果，它会对局部距离进行归一化，使得稀疏区域和密集区域在二维图上看起来具有相似的紧凑程度。这种归一化虽然让可视化更美观，却抹去了数据点之间在密度上的巨大差异。例如，一个在高维空间中非常稀疏的簇和一个非常密集的簇，在UMAP的二维投影中可能呈现出几乎相同的大小和形状，让人无法区分它们的原始密度特征。
苹果这篇论文的核心思想，就是不要把这个中间产物扔掉！它本身就是一个宝藏，可以当成网络科学中的图来分析。于是，他们将降维（Dimensionality Reduction） 网络科学（Network Science）
图算法三剑客：PageRank、k-核、聚类系数
既然kNN图是个图结构，那标准图论里的算法自然能派上用场。苹果的研究人员精准地挑选了三个经典算法，分别解决三个核心问题：哪些点最具代表性？哪些点处于核心区域、哪些在边缘？哪些点形成了紧密的小团体？这三个问题恰好对应了数据探索中最常见的三个分析需求：寻找典型样本、理解密度层次、发现微观结构。
玩过UMAP的朋友，拿到一张散点图后，自然而然会想问：“这些点里，哪个最能代表这个集群？”
你可能会想：选二维投影中心附近的点呗！但问题在于，UMAP的二维投影是“失真”的，中心点很可能并不是高维空间中的中心。例如，一个在高维空间中位于簇边缘但在二维投影中被拉伸到中心附近的点，会被错误地选为代表点。更糟糕的是，如果数据存在多个密度不同的簇，二维投影中几何中心附近的点可能来自密度最大的簇，而忽略了其他簇的代表性。
苹果的方法很简单，直接对kNN图使用PageRank
第二个问题：“哪些点属于密集的核心，哪些只是散落在边缘的‘孤星’？”
K-核分解（k-Core Decomposition）能完美解答这个问题。它将图中节点一层层“剥离”：先移除入度（即被多少其他点认为是邻居）最低的节点，然后重复这个过程，直到所有节点都有一个“核数”（coreness）。核数越高，就代表这个点嵌入在图中的核心区域越深。这里需要特别强调的是，为什么在kNN图上使用入度而不是总度数（入度+出度）来进行k-core分解。因为kNN图中的每个节点都有恰好k个出边（固定邻居数），所以节点的总度数至少是k。如果用总度数进行k-core分解，所有节点都会有一个基础下限k，导致所有节点至少属于k-核，无法将处于核心区域和边缘区域区分开。但入度在kNN图中是自然变化的，理论最小值是0（因为可能没有其他节点选它为邻居），最大值甚至可以远大于k。所以论文提出仅使用入度来进行k-core分解，这样才能揭示出一个连续且有区分度的“核心-边缘”层次结构。
举个例子，一个“8”的手写数字，如果它写得特别规范、特别像教科书上的标准形态，那么它就会有很多“近亲”，核数就会高；如果某个“8”写得七扭八歪，那它大概率就是个低核数的边缘点。在Fashion MNIST数据集中，k-core分解甚至可以揭示出同一类别（如“包包”）内部的不同子类别。例如，某些具有特定形状（如斜挎包、腰包、厚重纹理包）的样本会形成各自的高核数核心区域，而一些形状模糊或介于两种风格之间的样本则处于低核数的边缘区域。这种连续性的密度层次信息，是传统的硬聚类方法（如HDBSCAN）无法提供的。
最后一个问题：“在这些大集群里，有没有一些内部关系格外紧密的小圈子？”
聚类系数（Clustering Coefficient, CC）
比如在Fashion MNIST数据集中，针对“鞋”这个大类别，一个高聚类系数的微集群可能全部指向某种特定形状的“高跟靴”，另一个则可能是“运动鞋”。这在二维散点图上通常很难区分，因为所有“鞋”的样本在二维投影中可能混在一起，形成一个连续的团块。但通过聚类系数，我们可以发现这个团块内部存在着多个结构紧密的“小团体”，每个小团体对应一种特定的鞋类风格。论文中的实验显示，在MNIST数据集的数字“6”中，聚类系数成功分离出了“粗体6”、“斜体6”、“有环6”等多种书写风格的小群体，这些风格差异在原始的二维UMAP投影中是完全不可见的。
实验验证：代表性、密度层次、局部凝聚力
光说理论不够香，得看实操。苹果在MNIST和Fashion MNIST这两个经典数据集上，进行了一番详尽的量化与质性评估。结果颇有意思：
首先，稳定性检验
这意味着你不需要为了调参而焦头烂额——PageRank得到的“代表性点”是稳定的。具体来说，在MNIST数据集上，当k从5变化到100时，PageRank排名的Spearman秩相关系数均值高达0.95；在Fashion MNIST上，这个值也达到了0.94。这种高度的稳定性说明，PageRank识别出的代表性点是由数据本身的固有结构决定的，而不是对特定参数选择的偶然结果。同样，k-core分解和聚类系数的结果在相邻k值下也表现出高度的相关性，进一步证明了这些方法的鲁棒性。
接着看代表性效果
结果令人惊讶：尽管PageRank完全没有优化距离目标，它的表现却与k-medoids非常接近。在MNIST上，两种方法的平均余弦距离几乎完全重合；在Fashion MNIST上，PageRank甚至略微优于k-medoids。这意味着，通过图结构选出的代表性点，在几何距离上也同样具有代表性，实现了“拓扑”与“几何”的一致性。
更有意思的是在类别平衡
看这趋势，随着选取的点数增加，k-medoids的类别分布Jensen-Shannon散度（JSD）在大幅提升，而PageRank则是在稳步降低。这就好比选学生代表，k-medoids只选成绩最好的，不管全校哪个专业的人更少；而PageRank则考虑了全校学生的构成比例，选出来的代表更全面。在Fashion MNIST的10个类别中，k-medoids在预算为500时，JSD高达0.25，意味着它严重偏向于某些类别（如“T恤/上衣”和“连衣裙”这些在特征空间中分布更分散的类别），而完全忽略了其他类别（如“衬衫”）。相比之下，PageRank的JSD始终低于0.05，几乎完美地保持了与全局类别分布的一致性。
在分类任务中，研究人员将SVM（RBF核）训练在各方法选出的代表点上，然后对所有剩余点进行分类。结果显示，PageRank选出的代表点作为训练集时，分类准确率与k-medoids相当，甚至在某些预算下更高。更重要的是，PageRank只需进行一次全局排序，就可以根据预算从高到低选取任意数量的代表点；而k-medoids必须为每个预算重新运行算法，计算成本高得多。这在实际应用中是一个巨大的优势。
效果对比：超越专用方法
实验中最亮眼的部分，不是这三个方法“有用”，而是它们在很多地方“超越”了现有的专用方法。
比如，k-core分解和HDBSCAN
再比如，聚类系数。二维散点图上，MNIST的“6”字看起来只是一个巨大的团块。但通过聚类系数，你可以发现里面实际存在着“粗体6”、“斜体6”、“有环6”等多种风格的小群体。你可以理解成：一张百人大合照，表面上大家都长差不多，但聚类系数帮你精准锁定了那几个留着同款发型、戴着同款眼镜的小团体。论文中通过可视化展示了这些微集群的典型样本，证实了聚类系数确实能够捕捉到有意义的风格差异。例如，高聚类系数的“6”样本通常具有相似的倾斜角度和环的大小，而低聚类系数的“6”样本则在风格上更加多样化。
这里龙哥想插一句：对于做数据探索的分析师来说，这意味着可以零成本地获取更丰富的信息，而对结果的理解也更可靠。
展望与开源
苹果已经将PageRank集成到了开源可视化工具Embedding Atlas
龙哥认为，这项工作的潜力远不止于此。它可能带来以下几点变化：
第一，重新定义了UMAP的生态位。以前它只是个可视化工具，现在它成了数据分析的中转站。数据分析师不再只看一张图，还可以直接在这个图上做更深入的分析。这种转变类似于从“只看地图”到“利用地图上的道路网络进行导航”的升级。UMAP不再仅仅是降维的终点，而是网络科学分析的起点。
第二，可复现性和效率。相比于需要专门为每个任务训练模型的方法，这个方案几乎是零成本的。在60,000个点、k=15的MNIST上，PageRank、k-core和聚类系数的运行时间都不到1秒，非常高效。这意味着即使是在资源有限的笔记本电脑上，分析师也可以轻松地进行这种分析。此外，由于这些算法是确定性的（给定相同的输入，总是产生相同的输出），分析结果具有高度的可复现性。
第三，潜在的应用领域。对于单细胞基因组学（Single-cell Genomics）、音频处理、自然语言处理等需要处理高维数据的场景，这个思路可以无缝迁移，极大简化数据分析流程。例如，在单细胞RNA测序数据分析中，研究人员通常需要先使用UMAP对细胞进行降维可视化，然后再使用专门的聚类算法（如Leiden或Louvain）来识别细胞类型。而苹果的这项工作表明，直接在UMAP的kNN图上应用PageRank和k-core分解，就可以同时完成代表性细胞识别和密度层次分析，无需额外运行复杂的聚类算法。这有望显著简化单细胞数据分析的流程，并提高分析效率。
龙迷三问 问题一：这篇论文到底在解决什么问题？
问题二：本文中提到的“UMAP的kNN图”是什么？它的结构和通常的图有什么不同？
问题三：为什么k-core分解在kNN图上不能直接用总度数（入度+出度）？
如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评 论文创新性分数： ★★★★✰
这篇论文的创新不在于发明新的算法，而在于提出了一种全新的研究视角：将降维的中间产物（kNN图）作为分析对象，并运用经典图算法进行解读。这个思路极具巧思，打通了降维与网络科学两个领域，但单个模块本身并非全新，所以给4星。
实验合理度： ★★★★★
实验设计非常合理。从稳定性分析（k值的20倍变化）、与k-medoids和HDBSCAN的对比，到下游分类任务的检验，逻辑链条完整。采用MNIST和Fashion MNIST两个标准基准，对比实验的设置公平，论证充分。
学术研究价值： ★★★★★
高。这篇论文提出了一个值得深思的新方向：我们是否过于关注降维的“最终输出”而忽略了中间过程的价值？它启发了研究者去探索kNN图在其他降维方法（如TriMap、PaCMAP）中的应用，也为探索性数据分析（EDA）带来了新工具，学术价值极高。
稳定性： ★★★★✰
方法非常稳定。PageRank的排名对k值变化具有极强的鲁棒性，k-core和聚类系数的分析结果在相邻k值下也高度相关。算法的稳定基础较好，但在数据规模或维度剧烈变化时，边界条件仍需要进一步验证。
适应性以及泛化能力： ★★★★✰
该方法依赖于UMAP的kNN图，可以很自然地扩展到其他构建kNN图的降维方法。对于单细胞基因组学、音频分析等领域，潜力巨大。但在非常稀疏或非常稠密的数据上，其优势可能不如在图像数据集上突出，留有一定探索空间。
硬件需求及成本： ★★★★★
极低。所有算法（PageRank、k-core、聚类系数）的计算复杂度都非常友好，且复用UMAP的中间结果避免了重复计算。在60,000样本的数据集上，计算时间均小于1秒，对硬件几乎没有要求。
复现难度： ★★★★★
极易。使用的PageRank、k-core、聚类系数都是图论中的标准算法，有大量成熟的库支持（如NetworkX, igraph）。在UMAP工具包中也能直接获取kNN图。论文没有提出任何需要训练的额外模型。
产品化成熟度： ★★★★✰
部分成熟。该思想已集成到Embedding Atlas工具中，可以直接使用。但它是一种分析辅助工具，而非端到端的解决方案。依赖UMAP的中间产物，对于没有使用UMAP的流程则无法直接套用。
可能的问题： 论文主要验证了图像数据集（MNIST, Fashion MNIST），在非视觉、高噪声或高维度（如文本嵌入）数据上的泛化效果需要更多验证。另外，PageRank的排名与加权入度的相关系数高达0.93，其相对于简单加权入度的优势（能考虑到邀请者的重要性）在实际数据分析中是否足够显著，仍需更多复杂场景的对比。
主要参考文献 [1] McInnes, L., Healy, J., & Melville, J. (2020). UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv:1802.03426. [2] Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN systems, 30(1-7), 107-117. [3] Batagelj, V., & Zaversnik, M. (2003). An O(m) algorithm for cores decomposition of networks. arXiv:cs/0310049. [4] Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440-442. [5] McInnes, L., Healy, J., & Astels, S. (2017). hdbscan: Hierarchical density based clustering. Journal of Open Source Software, 2(11), 205. [6] Ren, D., Hohman, F., Lin, H., & Moritz, D. (2025). Embedding Atlas: Low-friction, interactive embedding visualization. IEEE VIS 2025. *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
