Pith. sign in

REVIEW 3 major objections 6 minor 24 references

UMAP's internal kNN graph, normally discarded after projection, is a first-class analytical resource: PageRank finds representatives, k-core reveals density hierarchy, clustering coefficient finds cohesive neighborhoods.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 01:41 UTC pith:J7KXUKFE

load-bearing objection UMAP's discarded kNN graph is a genuinely useful analytical resource, and the paper's empirical case is solid—but the density-adaptive normalization is never tested against a control, leaving a real gap in the central claim. the 3 major comments →

arxiv 2607.08746 v3 pith:J7KXUKFE submitted 2026-07-09 cs.LG cs.AIcs.DScs.HC

Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

Duen Horng Chau , Donghao Ren , Fred Hohman , Dominik Moritz This is my paper
classification cs.LG cs.AIcs.DScs.HC MSC 68R1062H30
keywords UMAPk-nearest-neighbor graphPageRankk-core decompositionclustering coefficientdimensionality reductionsensemakingexemplar selection
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper argues that UMAP's intermediate k-nearest-neighbor graph — built in the original high-dimensional space before the 2D projection is optimized — should be kept and analyzed, not thrown away. Applying three classical graph algorithms to this graph yields answers to sensemaking questions the scatter plot cannot: PageRank identifies representative data points, k-core decomposition separates dense cores from sparse peripheries, and clustering coefficient detects tight-knit micro-neighborhoods. On MNIST and Fashion MNIST, these methods are competitive with or complementary to purpose-built tools: PageRank matches k-medoids on representativeness while giving substantially better class balance at budgets above 200 points; k-core gives a graduated within-cluster hierarchy that HDBSCAN's discrete labels cannot; top clustering-coefficient points have 98% neighborhood label purity on MNIST.

Core claim

The central claim is that the weighted directed kNN graph UMAP constructs — with fixed out-degree k, variable in-degree, and density-adaptive edge strengths — faithfully encodes the data manifold before projection distortion, and therefore standard graph algorithms on it produce insight. Specifically, PageRank's transitive centrality selects points that are representative and class-balanced, rivaling k-medoids even though it never optimizes the distance objective; k-core decomposed by in-degree yields a core-periphery hierarchy that HDBSCAN membership probabilities cannot distinguish; and clustering coefficient isolates micro-clusters with high label purity. The discovery is that the interna

What carries the argument

The UMAP kNN graph: a weighted directed graph where each point has exactly k outgoing edges to its nearest neighbors, with edge weights given by density-adaptive membership strengths (per-point bandwidth normalized so total outgoing weight is constant), and variable in-degree reflecting how many points nominate a given point. PageRank, k-core (defined on in-degree), and clustering coefficient are applied to this graph; the graph's fixed out-degree and density-adaptive weights are what make the three algorithms' outputs meaningful rather than scale artifacts.

Load-bearing premise

The results assume UMAP's density-adaptive membership-strength graph faithfully captures the high-dimensional data manifold, so that PageRank, k-core, and clustering-coefficient scores reflect real data structure rather than artifacts of UMAP's per-point bandwidth normalization.

What would settle it

Run PageRank on the same kNN topology but with raw distances as edge weights (no density-adaptive normalization), and compare the top-s selections' class balance and label purity to the paper's reported results; if the advantage over k-medoids disappears, the reported benefit is an artifact of UMAP's density normalization rather than of graph topology. Equivalently, randomize the edge weights while preserving degrees and check whether PageRank/CC scores still track label purity.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Data analysts can reuse the graph UMAP already builds, at near-zero extra cost (each algorithm runs in under a second on 60k points), to get representativeness, density, and cohesion views.
  • PageRank offers a continuous ranking that can be thresholded at any budget s without recomputation, unlike k-medoids which must be re-run per budget.
  • k-core adds a within-cluster centrality axis to complement HDBSCAN's cluster labels, distinguishing core from periphery members that share a label.
  • The same graph-based perspective transfers to other dimensionality-reduction methods that build kNN graphs, such as TriMap and PaCMAP.
  • Clustering coefficient can be used as an unsupervised filter to surface micro-styles within a class, as shown for digit '6' handwriting variants.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A direct comparison of PageRank on UMAP's density-normalized weights versus raw-distance kNN weights would isolate whether the reported class-balance advantage comes from the graph topology or from UMAP's per-point calibration; the paper does not provide this baseline.
  • The claim that the kNN graph 'faithfully' encodes the manifold is only indirectly supported; one could test it by checking whether PageRank representatives align with human-labeled prototypical examples on a dataset with known ground-truth exemplars.
  • Because k-core and clustering coefficient are computed on an unweighted version of the graph, they may inherit different artifacts than PageRank; combining all three scores could yield a richer per-point summary for interactive tools.
  • The approach suggests a general design pattern: keep the intermediate representations of ML pipelines and treat them as first-class analysis objects, not just internal machinery.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper argues that UMAP's internal kNN graph—the weighted directed graph constructed before the 2D embedding—should be treated as a first-class analytical resource. It applies three standard graph algorithms to this graph for sensemaking: PageRank to select representative exemplars, k-core decomposition to expose core/periphery density structure, and clustering coefficient to identify cohesive micro-neighborhoods. On MNIST and Fashion MNIST, PageRank is compared to k-medoids on representativeness, class balance, and downstream SVM accuracy; k-core is compared conceptually and quantitatively to HDBSCAN membership probabilities; CC is validated via label purity against random neighborhoods. The paper reports that PageRank achieves superior class balance at s≥200, k-core yields a hierarchy absent from HDBSCAN labels, and high-CC neighborhoods are semantically purer than random. The authors also report runtime and integration into Embedding Atlas.

Significance. If the claims hold, the paper makes a useful conceptual contribution: it reuses UMAP's already-computed graph to answer representativeness/density/cohesion questions, avoiding additional neighbor searches. The work is strong in reusing off-the-shelf algorithms, reporting robustness checks across k (Fig. 3), and using a label-purity control with random neighborhoods (Sec. 3.3.1). The PageRank vs. k-medoids comparison is practical even though k-medoids optimizes a different objective. The main gap is attribution: whether results reflect manifold geometry or UMAP's density-adaptive normalization.

major comments (3)
  1. [Sec. 3.1.1, footnote 4] The central premise that the kNN graph faithfully reflects the high-dimensional manifold is not tested against UMAP's density-adaptive normalization. Because PageRank correlates 0.93 with weighted in-degree and k-core uses in-degree, both algorithms are vulnerable to artificial hubs or periphery introduced by per-point σ_i calibration. The stability checks across k (Fig. 3) and the label-purity control (Sec. 3.3.1) do not isolate this construction choice. Please add a control using unweighted or raw-distance kNN graphs on the same neighbor indices, or a synthetic manifold with known geometry, to show the reported PageRank class-balance and k-core hierarchy are not primarily artifacts of σ_i/ρ_i smoothing.
  2. [Sec. 3.1.1, Figs. 4–6] The quantitative comparisons report single trajectories with no error bars or significance tests. k-medoids is approximate and may carry initialization variability, while PageRank is deterministic for a fixed graph. To support the claims 'superior class balance' and 'competitive representativeness/classification,' report multiple restarts or bootstrap confidence intervals and perform a statistical test on the class-balance advantage. As written, a reader cannot assess the variability of the reported gaps.
  3. [Sec. 3.2.1] The claim that k-core captures structure HDBSCAN cannot is supported only by correlation with HDBSCAN membership probabilities, which are not a hierarchical density estimate. Membership probability answers 'which cluster?' rather than 'where in the cluster?', so the comparison is conceptually useful but does not show superiority over HDBSCAN's full capability. A stronger comparison would use HDBSCAN's condensed tree or another density-hierarchy baseline. As written, the 'complementary to purpose-built methods' conclusion rests on a restricted baseline.
minor comments (6)
  1. [Sec. 3.1.1] 'k (UMAP's n neighbors)' should use n_neighbors to avoid confusion with the sample size n.
  2. [Fig. 3 caption] Specify how the mean pairwise Jaccard values are computed: over which k pairs and whether the 0.62–0.71 range is across budgets or datasets.
  3. [Sec. 3.3.1] Clarify whether the ± values for random-sample purity are standard deviations or standard errors, and over how many random samples.
  4. [Fig. 1A] Specify whether the 'top 500' are the global top PageRank points or selected per class; the current caption is ambiguous.
  5. [Sec. 3.3] The directed clustering coefficient is defined verbally; a formal equation would improve precision, especially because the Watts–Strogatz coefficient is normally undirected.
  6. [Sec. 3.1.1] The damping factor is fixed at 0.85; a brief sensitivity check would strengthen the claim that PageRank results are not sensitive to this parameter.

Circularity Check

0 steps flagged

No significant circularity: the graph algorithms are off-the-shelf and all claimed sensemaking benefits are validated against external labels and external baselines.

full rationale

The paper's derivation chain is: UMAP constructs an internal kNN graph with density-adaptive weights; standard PageRank, k-core, and clustering coefficient are then applied; outputs are evaluated against external ground-truth class labels and external methods (k-medoids, HDBSCAN, SVM). None of these steps fits a parameter to the quantity being predicted. PageRank is not fit to class balance or representativeness; k-core is not fit to HDBSCAN labels; clustering coefficient is not fit to label purity. The only self-citation, [19] Embedding Atlas, is a statement that PageRank was integrated into a visualization tool; it is not load-bearing for any derivation. The UMAP density-adaptive normalization is imported from external work [15] and is a modeling assumption; even if it could create artifacts in the graph, that is a validity risk rather than a circular reduction, because the paper's quantitative claims are tested against independent labels and baselines rather than being entailed by the graph construction. The paper also stress-tests the main free parameter (k) across a 20x range, mitigating the concern that results are forced by a particular graph-construction choice.

Axiom & Free-Parameter Ledger

4 free parameters · 4 axioms · 0 invented entities

The paper adds no new entities or fitted constants of its own; it reuses UMAP's data-fitted normalization (per-point σ_i and local connectivity ρ_i), user-set hyperparameters (k=15, PageRank damping 0.85, HDBSCAN min_cluster_size=500/min_samples=10), and domain assumptions about MNIST/Fashion-MNIST labels and cosine-distance representativeness. The load-bearing graph-faithfulness assumption is unvalidated.

free parameters (4)
  • UMAP neighborhood size k = 15
    Defines the kNN graph structure; chosen as UMAP's default. Rankings stable across k=5–100 (Spearman ≥0.82), so the headline results are not tuned to one k, but the specific graphs analyzed all use k=15.
  • PageRank damping factor = 0.85
    Standard PageRank default; not varied; affects edge-weight propagation but not the stability claim.
  • UMAP per-point bandwidth σ_i / local connectivity ρ_i (smooth_knn_dist) = computed per point by UMAP binary search [16]
    PageRank edge weights are UMAP's membership strengths derived from these; the paper re-derives them from raw distances. The paper does not validate the graph against an un-normalized alternative, so the results inherit this data-fitted normalization.
  • HDBSCAN min_cluster_size / min_samples = 500 / 10
    Used for the baseline comparison pipeline; chosen per 'recommended' UMAP+HDBSCAN pipeline, not derived. Affects the baseline's cluster assignment and the 'complementary' comparison.
axioms (4)
  • domain assumption UMAP's kNN graph with density-adaptive membership strengths faithfully encodes high-dimensional manifold connectivity before projection distortion
    Invoked in Section 1 and 3.1 to justify why graph algorithms on this graph yield meaningful sensemaking; not directly validated (e.g., no comparison against raw-distance kNN graphs or ground-truth manifold geometry).
  • domain assumption Representativeness is measured by mean cosine distance to nearest selected representative in the original feature space
    Section 3.1.1, Figure 4: the evaluation of both PageRank and k-medoids uses this metric; if cosine distance in pixel space is not the right notion of representativeness, the quantitative comparison is moot.
  • domain assumption Class labels of MNIST/Fashion MNIST are the ground truth for semantic coherence (label purity) and class balance
    Used in Figures 5 and 7 and the label-purity control; assumes human-defined classes are the semantics users care about.
  • standard math PageRank with damping 0.85 on a weighted directed graph with constant out-degree and possible disconnected components converges to a meaningful centrality
    Standard Markov-chain theory with teleportation, as in [7]; the graph is not necessarily strongly connected and dangling nodes exist, so the standard PageRank formulation is assumed well-defined.

pith-pipeline@v1.3.0-alltime-deepseek · 7785 in / 17643 out tokens · 204665 ms · 2026-08-04T01:41:22.272183+00:00 · methodology

0 comments
read the original abstract

While UMAP is widely used for exploring high-dimensional data, typical workflows focus on its lower-dimensional embedding, largely overlooking the rich k-nearest-neighbor (kNN) graph that UMAP constructs internally. This graph encodes the data manifold in its original high-dimensional space, before the distortion that UMAP's 2D projection introduces. We demonstrate the untapped potential of this internal representation, showing how standard graph algorithms applied to this graph enhance data sensemaking: (1) PageRank identifies representative data points, (2) k-core decomposition reveals dense core regions versus sparse periphery, and (3) clustering coefficient detects tight-knit neighborhoods with highly-similar data points. Through quantitative and qualitative evaluation on MNIST and Fashion MNIST, we show that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods (e.g., k-medoids for exemplar selection, HDBSCAN for density-based clustering).

Figures

Figures reproduced from arXiv: 2607.08746 by Dominik Moritz, Donghao Ren, Duen Horng Chau, Fred Hohman.

Figure 1
Figure 1. Figure 1: Standard graph algorithms applied to UMAP’s internal [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Data points’ PageRank rankings achieve high Spear [PITH_FULL_IMAGE:figures/full_fig_p002_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: PageRank rivals k-medoids on representativeness despite not optimizing the distance objective. Representativeness measured as mean cosine distance from each data point to its nearest selected representative (lower is better). factor: 0.85). Because each point’s bandwidth σi is calibrated so that its total outgoing weight is approximately constant regard￾less of local density [15], PageRank reflects topolog… view at source ↗
Figure 5
Figure 5. Figure 5: PageRank’s representatives achieve superior class bal [PITH_FULL_IMAGE:figures/full_fig_p003_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: Clustering coefficient (CC) isolates tight-knit handwriting [PITH_FULL_IMAGE:figures/full_fig_p004_7.png] view at source ↗

Review history (3 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 1 linked inside Pith

  1. [1]

    Allaoui, M

    M. Allaoui, M. L. Kherfi, and A. Cheriet. Considerably improving clustering algorithms using umap dimensionality reduction technique: A comparative study. InImage and Signal Processing: 9th Interna- tional Conference, ICISP 2020, Marrakesh, Morocco, June 4–6, 2020, Proceedings, p. 317–325. Springer-Verlag, Berlin, Heidelberg, 2020. doi: 10.1007/978-3-030-...

    doi:10.1007/978-3-030-51935-3 2020

  2. [2]

    Amid and M

    E. Amid and M. K. Warmuth. Trimap: Large-scale dimensionality reduction using triplets.CoRR, abs/1910.00204, 2019. 4

    Pith/arXiv arXiv 1910

  3. [3]

    Batagelj and M

    V . Batagelj and M. Zaversnik. An o(m) algorithm for cores decompo- sition of networks.CoRR, cs.DS/0310049, 2003. 2, 3

    arXiv 2003

  4. [4]

    Becht, L

    E. Becht, L. McInnes, J. Healy, C.-A. Dutertre, I. W. Kwok, L. G. Ng, F. Ginhoux, and E. W. Newell. Dimensionality reduction for visualiz- ing single-cell data using umap.Nature biotechnology, 37(1):38–44,

  5. [5]

    Belkin and P

    M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation.Neural computation, 15(6):1373– 1396, 2003. 2

    2003

  6. [6]

    V . D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks.Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008. 4

    2008

  7. [7]

    Brin and L

    S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine.Computer Networks and ISDN Systems, 30(1):107– 117, 1998. Proceedings of the Seventh International World Wide Web Conference. doi: 10.1016/S0169-7552(98)00110-X 2

    doi:10.1016/s0169-7552(98)00110-x 1998

  8. [8]

    Charikar, M

    M. Charikar, M. Henzinger, L. Hu, M. V ¨otsch, and E. Waingarten. Simple, scalable and effective clustering via one-dimensional projec- tions. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, eds.,Advances in Neural Information Processing Systems, vol. 36, pp. 64618–64649. Curran Associates, Inc., 2023. 2

    2023

  9. [9]

    Coenen and A

    A. Coenen and A. Pearce. Understanding UMAP.https:// pair-code.github.io/understanding-umap. Accessed: 2026- 04-16. 1, 2

    2026

  10. [10]

    Espadoto, R

    M. Espadoto, R. M. Martins, A. Kerren, N. S. T. Hirata, and A. C. Telea. Toward a quantitative survey of dimension reduction tech- niques.IEEE Transactions on Visualization and Computer Graphics, 27(3):2153–2173, 2021. doi: 10.1109/TVCG.2019.2944182 1, 2, 3

    arXiv 2021

  11. [11]

    H. Jeon, J. Park, S. Shin, and J. Seo. Stop misusing t-sne and umap for visual analytics, 2025. 1, 2, 3

    2025

  12. [12]

    Y . Kwon, S. Park, S. Park, and H. Lee. Benchmarking of dimensional- ity reduction methods to capture drug response in transcriptome data. Scientific Reports, 15(1):32173, 2025. 2

    2025

  13. [13]

    Lecun, L

    Y . Lecun, L. Bottou, Y . Bengio, and P. Haffner. Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998. doi: 10.1109/5.726791 2

    doi:10.1109/5.726791 1998

  14. [14]

    McInnes, J

    L. McInnes, J. Healy, and S. Astels. hdbscan: Hierarchical density based clustering.Journal of Open Source Software, 2(11):205, 2017. doi: 10.21105/joss.00205 2, 3

    doi:10.21105/joss.00205 2017

  15. [15]

    McInnes, J

    L. McInnes, J. Healy, and J. Melville. Umap: Uniform manifold ap- proximation and projection for dimension reduction, 2020. 1, 2, 3

    2020

  16. [16]

    McInnes, J

    L. McInnes, J. Healy, N. Saul, and L. Großberger. Umap: Uniform manifold approximation and projection.Journal of Open Source Soft- ware, 3(29):861, 2018. doi: 10.21105/joss.00861 4

    doi:10.21105/joss.00861 2018

  17. [17]

    L. G. Nonato and M. Aupetit. Multidimensional projection for visual analytics: Linking techniques with distortions, tasks, and layout en- richment.IEEE Transactions on Visualization and Computer Graph- ics, 25(8):2650–2673, 2019. doi: 10.1109/TVCG.2018.2846735 2

    arXiv 2019

  18. [18]

    Park and C.-H

    H.-S. Park and C.-H. Jun. A simple and fast algorithm for k-medoids clustering.Expert systems with applications, 36(2):3336–3341, 2009. 2

    2009

  19. [19]

    D. Ren, F. Hohman, H. Lin, and D. Moritz. Embedding atlas: Low- friction, interactive embedding visualization. In2025 IEEE Visual- ization and Visual Analytics (VIS), pp. 191–195. IEEE, 2025. doi: 10. 1109/VIS60296.2025.00044 4

    arXiv 2025

  20. [20]

    V . A. Traag, L. Waltman, and N. J. Van Eck. From louvain to lei- den: guaranteeing well-connected communities.Scientific reports, 9(1):5233, 2019. 2, 4

    2019

  21. [21]

    Y . Wang, H. Huang, C. Rudin, and Y . Shaposhnik. Understanding how dimension reduction tools work: an empirical approach to deciphering t-sne, umap, trimap, and pacmap for data visualization.Journal of Machine Learning Research, 22(201):1–73, 2021. 3, 4

    2021

  22. [22]

    D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small- world’networks.nature, 393(6684):440–442, 1998. 2, 4

    1998

  23. [23]

    F. A. Wolf, P. Angerer, and F. J. Theis. Scanpy: large-scale single-cell gene expression data analysis.Genome biology, 19(1):15, 2018. 2

    2018

  24. [24]

    H. Xiao, K. Rasul, and R. V ollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017. 2

    2017