More Like this

1. KNN-DBSCAN: a DBSCAN in high dimensions

   https://doi.org/10.1145/3701624  

   Chen, Youguang; Ruys, William; Biros, George (March 2025, ACM Transactions on Parallel Computing)

   Clustering is a fundamental task in machine learning. One of the most successful and broadly used algorithms is DBSCAN, a density-based clustering algorithm. DBSCAN requires ϵ-nearest neighbor graphs of the input dataset, which are computed with range-search algorithms and spatial data structures like KD-trees. Despite many efforts to design scalable implementations for DBSCAN, existing work is limited to low-dimensional datasets, as constructing ϵ-nearest neighbor graphs can be expensive in high-dimensions. This article introduces a modified DBSCAN, usingk-nearest neighbor (kNN) graphs to improve efficiency. We outline conditions forkNN-DBSCAN to match DBSCAN’s results and present a parallel implementation using OpenMP and MPI for shared and distributed memory systems. Testing on datasets up to 32 dimensions, we achieve remarkable scalability. Our implementation clusters one billion 3D points in under one second on 28K cores at TACC’s Frontera system. In a larger run, we cluster 65 billion points in 20 dimensions in under 40 seconds using 114,688 cores. Our method is up to 37× faster than state-of-the-art parallel DBSCAN on a 20-dimensional dataset with 4 million points. Code is available athttps://github.com/ut-padas/knndbscan. 

   more » « less
2. A Domain-Oblivious Approach for Learning Concise Representations of Filtered Topological Spaces for Clustering

   https://doi.org/10.1109/TVCG.2021.3114872  

   Qin, Yu; Fasy, Brittany Terese; Wenk, Carola; Summa, Brian (September 2021, IEEE Transactions on Visualization and Computer Graphics)

   Persistence diagrams have been widely used to quantify the underlying features of filtered topological spaces in data visualization. In many applications, computing distances between diagrams is essential; however, computing these distances has been challenging due to the computational cost. In this paper, we propose a persistence diagram hashing framework that learns a binary code representation of persistence diagrams, which allows for fast computation of distances. This framework is built upon a generative adversarial network (GAN) with a diagram distance loss function to steer the learning process. Instead of using standard representations, we hash diagrams into binary codes, which have natural advantages in large-scale tasks. The training of this model is domain-oblivious in that it can be computed purely from synthetic, randomly created diagrams. As a consequence, our proposed method is directly applicable to various datasets without the need for retraining the model. These binary codes, when compared using fast Hamming distance, better maintain topological similarity properties between datasets than other vectorized representations. To evaluate this method, we apply our framework to the problem of diagram clustering and we compare the quality and performance of our approach to the state-of-the-art. In addition, we show the scalability of our approach on a dataset with 10k persistence diagrams, which is not possible with current techniques. Moreover, our experimental results demonstrate that our method is significantly faster with the potential of less memory usage, while retaining comparable or better quality comparisons. 

   more » « less
3. Nearly-Doubling Spaces of Persistence Diagrams

   Sheehy, Donald R. (January 2022, 38th International Symposium on Computational Geometry (SoCG 2022))

   Goaoc, Xavier and (Ed.)

   The space of persistence diagrams under bottleneck distance is known to have infinite doubling dimension. Because many metric search algorithms and data structures have bounds that depend on the dimension of the search space, the high-dimensionality makes it difficult to analyze and compare asymptotic running times of metric search algorithms on this space. We introduce the notion of nearly-doubling metrics, those that are Gromov-Hausdorff close to metric spaces of bounded doubling dimension and prove that bounded $$k$$-point persistence diagrams are nearly-doubling. This allows us to prove that in some ways, persistence diagrams can be expected to behave like a doubling metric space. We prove our results in great generality, studying a large class of quotient metrics (of which the persistence plane is just one example). We also prove bounds on the dimension of the $$k$$-point bottleneck space over such metrics. The notion of being nearly-doubling in this Gromov-Hausdorff sense is likely of more general interest. Some algorithms that have a dependence on the dimension can be analyzed in terms of the dimension of the nearby metric rather than that of the metric itself. We give a specific example of this phenomenon by analyzing an algorithm to compute metric nets, a useful operation on persistence diagrams. 

   more » « less
4. Learning Hyperbolic Representations of Topological Features

   Panagiotis Kyriakis, Iordanis Fostiropoulos (May 2021, Proceedings of the International Conference on Learning Representations (ICLR))

   null (Ed.)

   Learning task-specific representations of persistence diagrams is an important problem in topological data analysis and machine learning. However, current state of the art methods are restricted in terms of their expressivity as they are focused on Euclidean representations. Persistence diagrams often contain features of infinite persistence (i.e., essential features) and Euclidean spaces shrink their importance relative to non-essential features because they cannot assign infinite distance to finite points. To deal with this issue, we propose a method to learn representations of persistence diagrams on hyperbolic spaces, more specifically on the Poincare ball. By representing features of infinite persistence infinitesimally close to the boundary of the ball, their distance to non-essential features approaches infinity, thereby their relative importance is preserved. This is achieved without utilizing extremely high values for the learnable parameters, thus the representation can be fed into downstream optimization methods and trained efficiently in an end-to-end fashion. We present experimental results on graph and image classification tasks and show that the performance of our method is on par with or exceeds the performance of other state of the art methods. 

   more » « less
5. Quantum distance approximation for persistence diagrams

   https://doi.org/10.1088/2632-072X/ad9fca  

   Ameneyro, Bernardo; Herrman, Rebekah; Siopsis, George; Maroulas, Vasileios (January 2025, Journal of Physics: Complexity)

   Abstract Topological data analysis (TDA) methods can be useful for classification and clustering tasks in many different fields as they can provide two dimensional persistence diagrams that summarize important information about the shape of potentially complex and high dimensional data sets. The space of persistence diagrams can be endowed with various metrics, which admit a statistical structure and allow to use these summaries for machine learning algorithms, e.g. the Wasserstein distance. However, computing the distance between two persistence diagrams involves finding an optimal way to match the points of the two diagrams and may not always be an easy task for classical computers. Recently, quantum algorithms have shown the potential to speedup the process of obtaining the persistence information displayed on persistence diagrams by estimating the spectra of persistent Dirac operators. So, in this work we explore the potential of quantum computers to estimate the distance between persistence diagrams as the next step in the design of a fully quantum framework for TDA. In particular we propose variational quantum algorithms for the Wasserstein distance as well as the $d_p^c$distance. Our implementation is a weighted version of the quantum approximate optimization Algorithm that relies on control clauses to encode the constraints of the optimization problem. 

   more » « less