{"id":"720b4cee-5059-4790-b1e5-73c4223c8f22","arxiv_id":"1908.10410","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"TMAP visualizes up to millions of high-dimensional points as an interactive 2D tree by computing an approximate nearest-neighbor graph and drawing its minimum spanning tree.","lead":"This paper introduces TMAP, a tree-based visualization method that uses locality-sensitive hashing, approximate nearest-neighbor graphs, and minimum spanning trees to map millions of high-dimensional data points into an interactive 2D tree. It matters because it offers a scalable alternative to t-SNE and UMAP for exploring very large chemical, biological, and physical data sets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MST of the approximate k-NNG has no fidelity guarantee, so the claimed local/global preservation at n ~ 10^7 is an unvalidated extrapolation; the paper's own disconnected-graph caveat makes the risk concrete.","rationale":"The reader's weakest assumption identifies the same load-bearing step: the c-approximate k-NNG built in phase II carries the entire fidelity burden, with no guarantees and with the paper's own admission that the graph can be disconnected. My stress-test agrees and adds that the disconnected case is not a minor edge case for 'arbitrary high-dimensional' data; hubs, outliers, and tight clusters are common in exactly the chemical and biological datasets the paper targets. The missing ground-truth evaluation at scale is what makes the central claim conditional rather than established. I credit the paper for releasing source code, providing interactive visualizations, and demonstrating reproducible outputs, and I do not see an internal inconsistency that invalidates the method. The concern is about the strength of the evidence, not the existence of the tool. The proposed exact-graph comparison is a single, feasible control experiment that would directly test whether the approximation step degrades the visualization quality that the paper claims. Therefore the appropriate verdict remains CONDITIONAL, unchanged from the reader's assessment.","tokens_in":13851,"tokens_out":4716,"duration_ms":51542,"concrete_test":"On a medium dataset such as MNIST or a 100,000-compound ChEMBL subset, run the published TMAP pipeline twice: once with the default LSHForest c-approximate k-NNG as phase-II input, and once with an exact k-NNG computed by brute-force nearest neighbors, keeping phases III–IV and all parameters fixed. Repeat 5 times and compare (a) 1-NN retention and trustworthiness/continuity in the original space, and (b) the number of connected components in the resulting MST. If the exact-graph TMAP improves 1-NN retention by more than 10 percentage points, or materially changes component structure, the approximate graph is the load-bearing bottleneck and the large-data quality claims require qualification; if not, the concern is mitigated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quality claim—that TMAP preserves both local and global structure at scale—rests on the minimum spanning tree computed in phase III from the c-approximate k-NNG built in phase II. The paper provides no error bound relating the MST of this approximate, Jaccard-weighted graph to the MST of the true distance graph, and no argument that the edges LSH happens to retrieve are the ones the MST needs. Methods, phase II, explicitly concedes that the c-k-NNG can be disconnected when outliers exist or when dense clusters of size at least k form connected components; in those cases phase III produces a minimum spanning forest, so the claimed 'tree' is not a single tree and the layout of disconnected components has no principled global arrangement. The favorable locality comparisons (Fig. 2, Fig. S6) are on datasets small enough to check exact k-NN neighborhoods, but the headline demonstrations at n = 11,261,085 are not checked against any ground truth. The empirical O(n^0.931) scaling is a power-law fit over a small range, not an asymptotic bound, and cannot justify the conclusion's 'sub-linear time complexity' phrasing, since any algorithm reading all n inputs is Omega(n). Together, these gaps mean the scalability and superiority claims are extrapolations from an unvalidated approximation step rather than established properties.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces TMAP, a four-phase pipeline — LSH forest indexing, construction of a c-approximate k-nearest-neighbor graph, minimum spanning tree extraction via Kruskal's algorithm, and force-based layout — for visualizing large high-dimensional data sets as two-dimensional trees. The method is demonstrated on toy benchmarks (MNIST, Fashion-MNIST, COIL20) and on chemical data sets up to 11,261,085 points, with additional examples from biology, physics, and text data. The authors claim that TMAP preserves local and global structure better than t-SNE or UMAP, scales to millions of points on commodity hardware, and exhibits an empirical sub-linear time complexity of O(n^0.931).","tokens_in":14151,"tokens_out":5114,"duration_ms":44462,"significance":"If the claims hold, TMAP fills a genuine gap: interactive, interpretable visualization of million-scale, high-dimensional data sets without specialized hardware. The paper's strengths include an open-source implementation, interactive online examples, evaluation against external benchmarks (MNIST, COIL20, ChEMBL, MoleculeNet), a modular phase design that permits alternative hashing schemes, and fully reproducible deterministic output. However, the headline scaling claim and the structure-preservation claims at the largest scales are currently extrapolations from a four-point runtime fit and from exact-nearest-neighbor checks performed only on small data sets. The paper also leaves open how the acknowledged possibility of a disconnected k-NNG affects the global-structure guarantees of the resulting forest.","major_comments":[{"comment":"The claim of an 'empirical sub-linear time complexity of O(n^0.931)' is not a valid asymptotic statement for the full pipeline: any implementation must read all n input points, which gives an Ω(n) lower bound, so a fitted exponent below 1 cannot describe the complete algorithm in the standard computational model. The exponent is obtained from only four runtime measurements (n = 10^4, 10^5, 5×10^5, 10^6) with no error bars or cross-validation, and it likely reflects the graph-layout phase rather than the whole pipeline. Please restrict the claim to 'observed roughly linear scaling in the tested range' and report per-phase timings at more granular values of n.","section":"Conclusion (also Fig. 2g–i)"},{"comment":"The paper explicitly notes that the c-approximate k-NNG can be disconnected when outliers have Jaccard distance 1.0 to all other points or when dense clusters of size at least k form connected components; in those cases phase III produces a minimum spanning forest rather than a single tree, and phase IV lays out the forest without a principled global arrangement for the separate components. None of the large-scale demonstrations (e.g., n = 11,261,085 in Fig. 3b) report the number of connected components, the size of the largest component, or where disconnections occur, so the central 'tree' visualization and its implied global-structure fidelity are not substantiated at scale. Please report connectivity statistics for the real data sets and either add a component-connecting step or restrict the global-structure claims accordingly.","section":"Methods, phase II and phase III"},{"comment":"The quantitative locality-preservation comparisons are limited to small data sets (n = 10,000 for ChEMBL and MNIST) where exact k-NN in the input space is computationally feasible. No ground-truth validation is provided for the headline n ≈ 10^7 cases, so the claim that TMAP preserves both global and local features at million scale is an extrapolation from the small-scale regime. In addition, the comparison is made against UMAP only, despite t-SNE appearing in the title and abstract; and because UMAP is stochastic — as the authors' own Fig. S8 demonstrates — single-run comparisons such as those in Fig. 2h,i should include error bars or repeated runs. Please add a subsampled exact-nearest-neighbor validation protocol for large data sets and quantify the variability of the runtime/memory comparison.","section":"Results, Fig. 2e/f and Fig. S6"}],"minor_comments":[{"comment":"Kruskal's algorithm complexity is stated as O(E + log V); the standard bound is O(E log E) with sorting, or near-linear O(E α(V)) when edges are already sorted by weight. Please correct this statement.","section":"Methods, phase III"},{"comment":"The statement that a query has time complexity sub-linear in n omits the dependence on k and k_c; for k growing with n, the phase II complexity O(n(k·k_c + log n)) is not necessarily sub-linear. Please state the parameter regime under which the claimed sub-linear behavior holds.","section":"Methods, phases I and II"},{"comment":"The runtime and memory comparisons appear to be single measurements; given the demonstrated run-to-run variability of UMAP in Fig. S8, please report repeated runs with variance or clearly mark the measurements as indicative single runs.","section":"Fig. 2h,i"},{"comment":"The phrase 'arbitrary high dimensionality' is stronger than what is demonstrated: the experiments emphasize very high-dimensional sparse/binary data, and the method's efficiency depends on the availability of a suitable LSH family for the chosen metric. The modularity point is acknowledged, but the wording could be softened.","section":"Abstract and Conclusion"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know about this paper if you care about practical visualization of very large high-dimensional data. The authors combine LSH forest indexing, c-approximate k-NN graph construction, MST, and multilevel graph layout into a pipeline that actually handles 11 million molecules and produces interactive trees. That is new: ChemTreeMap only managed ~10k points, and t-SNE/UMAP don't scale to this size with reasonable memory. The paper is honest about the method's modularity—you can swap in your own nearest-neighbor graph.\n\nWhat it does well: the engineering is solid, the demonstrations are broad (chemistry, PDB, text, particle physics), and they ship code and a public interactive site. The locality checks on MNIST and ChEMBL subsets show TMAP preserves 1-NN relationships better than UMAP on those examples. The stability point (deterministic output vs UMAP's run-to-run variation) is a real practical advantage.\n\nSoft spots, in proportion. The reported O(n^0.931) is a power-law fit to four runtime measurements, not an asymptotic bound; any algorithm that reads n inputs is Omega(n), so the \"sub-linear time complexity\" phrasing in the conclusion is overreach. More importantly, the quality of the million-point maps is not validated against any ground truth. The MST in phase III is built on a c-approximate k-NN graph, and the paper itself notes the graph can be disconnected (outliers, dense clusters of size >= k), yielding a minimum spanning forest rather than a single tree. That means the \"tree\" framing and the global layout of disconnected components are heuristic. The stress-test note is right that there is no error bound linking MST of the approximate graph to the true structure. I don't think this is fatal—the method is explicitly an approximation and the small-scale benchmarks give some evidence of fidelity—but the headline claims of \"preserving both global and local features\" at n=11M go beyond what is shown.\n\nThe comparison to UMAP also lacks error bars, and the chemistry fingerprint MHFP6 is the authors' own, so the chemical examples are somewhat in-house. Those are minor issues for a methods paper.\n\nWho is this for? Anyone working on large-scale chemical space exploration or interactive tree visualization. It deserves a serious referee; the complexity claims should be rewritten and the scale-up evidence should be framed as demonstrations, not formal guarantees.\n\nMy recommendation: engage with it, send it to review, and ask for a more careful statement about what is proven versus what is demonstrated.","headline":"TMAP is a genuine engineering contribution that scales tree-based visualization to millions of high-dimensional points, but the sub-linear complexity claim is an empirical fit, not a bound, and the faithfulness of the MST of an approximate k-NN graph at scale is not established.","tokens_in":14659,"tokens_out":1945,"would_cite":true,"duration_ms":15047,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"TMAP lays out very large, high-dimensional data sets as a two-dimensional minimum spanning tree, and the resulting tree preserves local and global structure at scales t-SNE and UMAP cannot reach.","keywords":["minimum spanning tree","high-dimensional data visualization","locality sensitive hashing","approximate nearest neighbor graph","chemical space","UMAP comparison","interactive visualization"],"falsifier":"Run TMAP on a labeled set such as MNIST with fixed parameters and measure the fraction of true 1-nearest neighbors that fall within topological distance 1 on the MST; the paper reports more than 80% for TMAP on MNIST. A replication that falls far below that with standard parameters would show the approximate k-NN graph is not carrying the neighborhood structure the MST is supposed to encode.","tokens_in":13632,"feed_emoji":"🌳","tokens_out":7477,"duration_ms":72576,"temperature":0.7,"pith_summary":"The paper introduces TMAP, a visualization method that represents data sets of up to millions of points and arbitrary dimensionality as a two-dimensional tree. Its claim is that this tree preserves both local and global structure far better than current tools such as t-SNE or UMAP, while being faster and using less memory. The central move is to replace manifold embedding with a minimum spanning tree built on an approximate nearest-neighbor graph, which removes cycles and makes the final layout computationally tractable. The authors demonstrate the method on molecular databases with over eleven million compounds, as well as images, text, proteins, and particle-physics data, and report an empirical sub-linear running time of $O(n^{0.931})$.","feed_headline":"TMAP maps millions of points onto one tree, beating t-SNE and UMAP","feed_subtitle":"The pipeline preserves local and global neighborhoods at sizes where t-SNE and UMAP hit time and memory walls.","key_machinery":"The load-bearing object is the minimum spanning tree (MST) of a Jaccard-weighted c-approximate k-nearest-neighbor graph. A minimum spanning tree is the set of edges that connects all points with the smallest total edge weight, so it removes every cycle while keeping the data connected. This tree is what makes the visualization interpretable: branches and sub-branches encode cluster structure, and because trees are far cheaper to lay out than general graphs, it is also what allows million-point visualizations to be computed on a single workstation.","core_discovery":"The paper's central claim is that a minimum spanning tree of a c-approximate k-nearest-neighbor graph is a faithful, scalable two-dimensional representation of very large high-dimensional data. The pipeline indexes the data with a locality-sensitive hash forest, builds a Jaccard-weighted approximate k-NN graph, extracts its MST with Kruskal's algorithm, and lays the tree out with a spring-electrical force model. Removing all cycles converts the data into a single tree whose branches and sub-branches expose both global cluster relationships and local neighborhood detail, at a reported empirical cost of $O(n^{0.931})$ and with peak memory that stays manageable for sets of millions of points. The authors argue this makes TMAP better suited than t-SNE or UMAP for exploring large data sets, and illustrate it on 11.26 million molecules, images, texts, proteins, and particle-physics events.","pith_inferences":["If the MST is built on top of an approximate graph, the tree topology should be read as one plausible organization of the data rather than the unique ground-truth hierarchy; changing the LSH parameters can change which edges survive cycle removal.","The same tree pipeline could be repurposed as a feature extractor: MST-based distances or tree paths could serve as input to machine-learning models that currently rely on raw high-dimensional vectors.","For data that genuinely lies on a closed manifold, such as the rotating-object images in COIL20, TMAP is forced to cut the manifold at some edge; a preprocessing step that detects and stitches such cuts could extend the method to manifold-structured data.","Because the paper notes that disconnected approximate graphs are possible when outliers exist or dense clusters of size at least k form isolated components, practical deployments should expose a connectivity warning or a fallback that reconnects tree components."],"forward_implications":["Molecule databases of millions of compounds become explorable as single interactive trees, with structurally related compounds grouped into the same branches.","For any data type with a locality-sensitive hashing scheme, including text, images, gene expression, and physics measurements, the same four-phase pipeline applies without changing the tree or layout phases.","TMAP's layouts are reproducible from run to run on identical inputs and parameters, unlike the stochastic embeddings produced by UMAP.","According to the paper's measurements, a one-million-point set can be visualized in about six minutes with roughly 8.5 GB of memory, where UMAP required about 11.5 hours and 48.5 GB.","Neighborhood quality is controlled mainly by the LSH hash count, while the nearest-neighbor count and query-expansion factor have only minor influence on the final visualization."],"supporting_citations":[{"why":"Supplies the LSH forest indexing scheme used in phase I for sub-linear approximate nearest-neighbor search.","marker":"[37]"},{"why":"Provides the earlier LSH forest self-tuning index formulation that the paper's phase I builds on.","marker":"[38]"},{"why":"Kruskal's minimum spanning tree algorithm, the central phase III that removes cycles from the approximate graph.","marker":"[39]"},{"why":"Supplies the spring-electrical multilevel layout engine used in phase IV to draw the MST.","marker":"[40]"},{"why":"Provides the augmented LSH query variant for efficient k-NN graph construction and the MHFP6 fingerprint used in the chemistry applications.","marker":"[45]"},{"why":"Defines UMAP, the main non-linear method TMAP is compared against on speed, memory, and neighborhood preservation.","marker":"[26]"},{"why":"Defines t-SNE, the standard visualization baseline the paper argues TMAP surpasses at scale.","marker":"[27]"},{"why":"Justifies the use of Jaccard/Tanimoto similarity for fingerprint-based chemical comparison, supporting the edge weights in the k-NN graph.","marker":"[44]"}],"fun_headline_variants":["TMAP turns millions of high-dim points into one tree","Millions of data points, one tree: TMAP beats t-SNE and UMAP","New tree layout handles millions of points, preserving structure","TMAP: minimum spanning tree visualization scales to millions","Scalable tree map for huge datasets outperforms t-SNE and UMAP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The visualization's fidelity rests on the c-approximate k-nearest-neighbor graph built from locality-sensitive-hashing queries: if that graph misses true neighbor edges, the minimum spanning tree that follows cannot recover them, and the paper itself notes the graph can be disconnected when outliers exist or dense clusters of size at least k form isolated components.","fun_headline_variants_meta":{"raw":{"variants":["TMAP turns millions of high-dim points into one tree","Millions of data points, one tree: TMAP beats t-SNE and UMAP","New tree layout handles millions of points, preserving structure","TMAP: minimum spanning tree visualization scales to millions","Scalable tree map for huge datasets outperforms t-SNE and UMAP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000222,"raw_usage":{"total_tokens":1443,"prompt_tokens":926,"completion_tokens":517,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":427}},"tokens_in":542,"tokens_out":517,"duration_ms":4602,"temperature":1.0,"reasoning_tokens":427,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:57:51.943466+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run TMAP on a labeled set such as MNIST with fixed parameters and measure the fraction of true 1-nearest neighbors that fall within topological distance 1 on the MST; the paper reports more than 80% for TMAP on MNIST. A replication that falls far below that with standard parameters would show the approximate k-NN graph is not carrying the neighborhood structure the MST is supposed to encode.","supporting_citations":[{"cited_title":"& Nosatzki, N","cited_arxiv_id":null,"evidence_quote":"Supplies the LSH forest indexing scheme used in phase I for sub-linear approximate nearest-neighbor search."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Kruskal's minimum spanning tree algorithm, the central phase III that removes cycles from the approximate graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the spring-electrical multilevel layout engine used in phase IV to draw the MST."},{"cited_title":"& Reymond, J.-L","cited_arxiv_id":null,"evidence_quote":"Provides the augmented LSH query variant for efficient k-NN graph construction and the MHFP6 fingerprint used in the chemistry applications."},{"cited_title":"van der & Hinton, G","cited_arxiv_id":null,"evidence_quote":"Defines t-SNE, the standard visualization baseline the paper argues TMAP surpasses at scale."},{"cited_title":"& Héberger, K","cited_arxiv_id":null,"evidence_quote":"Justifies the use of Jaccard/Tanimoto similarity for fingerprint-based chemical comparison, supporting the edge weights in the k-NN graph."}],"review_version":1}