Dimension Reduction with Locally Adjusted Graphs

Yingfan Wang, Yiyang Sun, Haiyang Huang, Cynthia Rudin · 2024

Read Dimension Reduction with Locally Adjusted Graphs by Yingfan Wang, Yiyang Sun, Haiyang Huang, Cynthia Rudin (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15426.txt.

Introduction

Wang and three co-authors shrink big data to maps with a graph that self-tunes by zone in this twenty twenty-four paper. Such maps help eyes find clumps in vast sets, like gene reads from one cell. The first graph built from raw gaps is oft flawed, since far gaps read false.

Inside, their tool pulls small sub-graphs, grades them, and re-weights the main graph live. That loop can split true clumps that past tools merged into one blur. Smaller, picked sets yield graphs that hold up far more in the loop. A case run on cell gene data shows the tool at work on real clumps. The team casts it as a help for clump hunts in big trial sets.

Catalog record

CREATORYingfan Wang, Yiyang Sun, Haiyang Huang, Cynthia Rudin
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15426

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dimension Reduction with Locally Adjusted Graphs Yingfan Wang, Yiyang Sun, Haiyang Huang, Cynthia Rudin Abstract Dimension reduction (DR) algorithms have proven to be extremely useful for gaining insight into large-scale high-dimensional datasets, particularly finding clusters in transcriptomic data. The initial phase of these DR methods often involves converting the original high-dimensional data into a graph. In this graph, each edge represents the similarity or dissimilarity between pairs of data points. However, this graph is frequently suboptimal due to unreliable high-dimensional distances and the limited information extracted from the high-dimensional data. This problem is exacerbated as the dataset size increases. If we reduce the size of the dataset by selecting points for a specific sections of the embeddings, the clusters observed through DR are more separable since the extracted subgraphs are more reliable. In this paper, we introduce LocalMAP, a new dimensionality reduction algorithm that dynamically and locally adjusts the graph to address this challenge. By dynamically extracting subgraphs and updating the graph on-the-fly, LocalMAP is capable of identifying and separating real clusters within the data that other DR methods may overlook or combine. We demonstrate the benefits of LocalMAP through a case study on biological datasets, highlighting its utility in helping users more accurately identify clusters for real-world problems. Code — https://github.com/williamsyy/LocalMAP 1 Introduction Dimension reduction (DR) is an important data visualization strategy for understanding the structure of complicated high-dimensional datasets. DR is used extensively in image, text, and biomedical datasets, particularly -omics ( Cao et al. 2019 ; Becht et al. 2019 ; Amezquita et al. 2020 ; Dries et al. 2021 ; Atitey, Motsinger-Reif, and Anchang 2024 ; Böhm, Berens, and Kobak 2023 ; Mu, Bhat, and Viswanath 2017 ; Raunak, Gupta, and Metze 2019 ) . Beginning in the original high-dimensional space, DR methods typically first abstract the data into a graph , with each edge representing either similarity (positive edge) or dissimilarity (negative edge). This graph is then used to optimize the low-dimensional embedding by applying attractive forces along the positive edges and repulsive forces along the negative edges. Clearly, the quality of the graph, which connects the original high-dimensional data to the low-dimensional embedding, is critical to this process. However, given the complex nature of high-dimensional data, it is challenging to construct a graph that accurately represents all patterns and structures within the data, and graphs are usually sub-optimal. In this work, we provide two key insights as to why the graphs could be flawed. First, we found that high-dimensional distances become less informative due to the curse of dimensionality, where measurements of similarity and dissimilarity determined using high-dimensional distances do not necessarily reflect similarities and dissimilarities along the data manifold. This issue is more pronounced in DR methods that select a small group of nearest neighbors (NNs) to form positive edges of the graph and apply strong attractive forces along these edges. When a “false” positive edge is constructed based on an inaccurate similarity measure between a pair of points that are actually dissimilar, strong attractive forces will pull them closer. If there are many such false positive edges, the DR method will generate overlapping clusters without clear boundaries, even if the data have distinct clusters. Since DR methods are unsupervised, the user would not be able to determine that distinct clusters exist – they would be blurred together in the DR result. As we show in this work, eliminating these false positive edges can dramatically improve DR projections. Our second insight is that missing edges (lack of negative “further pair” edges between far points in high-dimensional space) also contribute to unwanted overlapping of clusters, since such edges help to define boundaries between clusters. However, as the scale of the dataset increases, the set of negative edges become both insufficient and less effective, as discussed in Section 4.2 . Some of the most important applications of DR (single cell, transcriptomics) generate large high-dimensional datasets with many clusters, so it is important that there are enough further pair (FP) edges to separate them. Based on the two insights discussed above, we propose LocalMAP, a new DR algorithm that dynamically and locally adjusts the graph during dimension reduction to address the aforementioned issues with graph construction. LocalMAP detects false positive edges and removes them , using ideas similar to outlier detection in robust statistics. This allows clusters to separate. It also adds more further pair edges dynamically, allowing crisper cluster boundaries to appear. Together, these ideas within LocalMAP produce clear, crisp separated clusters where other methods fail. Figure 1 shows the results of several high-quality DR approaches, including t-SNE ( van der Maaten and Hinton 2008 ) , UMAP ( McInnes, Healy, and Melville 2018 ) and PaCMAP ( Wang et al. 2021 ) , on the MNIST dataset where there are 10 separated clusters in the high-dimensional space. Algorithms t-SNE, UMAP and PaCMAP generate DR embeddings without clear boundaries between clusters, while LocalMAP generates a high-quality DR embedding with well-defined boundaries that are visible even without class information provided to the algorithm. Figure 1: DR embeddings on MNIST dataset which contains 10 digit classes. Our LocalMAP method is on the right. The colored embeddings with true labels are shown in Figure 5 . In this work, we provide more evidence for the insights discussed above, in terms of both theory based on simple clustering models and empirical evidence. We also provide LocalMAP and a comprehensive evaluation of it, based on Huang et al. 2022 . We provide case studies showing that LocalMAP is able to find true clusters – and not false clusters – more reliably than other DR approaches. 2 Related Work While DR methods that preserve global structure date back to 1901 with PCA ( Pearson 1901 ) , multidimensional scaling ( Torgerson 1952 ) , and non-negative matrix factorization ( Lee and Seung 1999 ) , methods that preserve local structure have become indispensable and ubiquitous in numerous applications, particularly in -omics research. Local methods include Isomap ( Tenenbaum, de Silva, and Langford 2000 ) , Local Linear Embedding (LLE) ( Roweis and Saul 2000 ) , Laplacian Eigenmap ( Belkin and Niyogi 2001 ) , and more recent Neighborhood Embedding (NE) algorithms like t-SNE ( van der Maaten and Hinton 2008 ) , LargeVis ( Tang et al. 2016 ) , UMAP ( McInnes, Healy, and Melville 2018 ) , PaCMAP ( Wang et al. 2021 ) , TriMAP ( Amid and Warmuth 2019 ) , NCVis ( Artemenkov and Panov 2020 ) , h-NNE ( Sarfraz et al. 2022 ) , Neg-t-SNE ( Damrich et al. 2023 ) and InfoNC-t-SNE ( Damrich et al. 2023 ) and many others ( Van Assel et al. 2022 ; Zu and Tao 2022 ) . Global methods typically are not able to preserve separations between clusters or clearly display the data manifold, whereas local methods can sometimes do so; thus, they provide a unique perspective on the data that is difficult to gain in any other way. Because DR methods are unsupervised, there is no common objective function like there would be for supervised learning (e.g., classification error). However, there are principles that reliable DR loss functions typically obey ( Wang et al.

Read the complete text