Related papers: Scalable Varied-Density Clustering via Graph Propagation

Scalable Varied-Density Clustering via Graph Propagation

URL: http://arxiv.org/abs/2508.02989v1
Date: Tue, 05 Aug 2025 01:33:41 GMT
Title: Scalable Varied-Density Clustering via Graph Propagation
Authors: Ninh Pham, Yingtao Zheng, Hugo Phibbs,
Abstract summary: We propose a novel perspective on varied-density clustering for high-dimensional data by framing it as a label propagation process in neighborhood graphs.<n>Our method formally connects density-based clustering with graph connectivity, enabling the use of efficient graph propagation techniques.
Score: 6.800113478497425
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: We propose a novel perspective on varied-density clustering for high-dimensional data by framing it as a label propagation process in neighborhood graphs that adapt to local density variations. Our method formally connects density-based clustering with graph connectivity, enabling the use of efficient graph propagation techniques developed in network science. To ensure scalability, we introduce a density-aware neighborhood propagation algorithm and leverage advanced random projection methods to construct approximate neighborhood graphs. Our approach significantly reduces computational cost while preserving clustering quality. Empirically, it scales to datasets with millions of points in minutes and achieves competitive accuracy compared to existing baselines.

Related papers

Clustering Based on Density Propagation and Subcluster Merging [92.15924057172195]
We propose a density-based node clustering approach that automatically determines the number of clusters and can be applied in both data space and graph space. Unlike traditional density-based clustering methods, which necessitate calculating the distance between any two nodes, our proposed technique determines density through a propagation process.
arXiv Detail & Related papers (2024-11-04T04:09:36Z)
Addressing Data Heterogeneity in Decentralized Learning via Topological Pre-processing [0.9645196221785693]
We show the advantages of constructing a proxy-based locally heterogeneous DL topology to enhance convergence and maintain data privacy. We propose a novel peer clumping strategy to efficiently cluster peers before arranging them in a final training graph.
arXiv Detail & Related papers (2022-12-16T22:46:38Z)
GraphFit: Learning Multi-scale Graph-Convolutional Representation for Point Cloud Normal Estimation [31.40738037512243]
We propose a precise and efficient normal estimation method for unstructured 3D point clouds. We learn graph convolutional feature representation for normal estimation, which emphasizes more local neighborhood geometry. Our method outperforms competitors with the state-of-the-art accuracy on various benchmark datasets.
arXiv Detail & Related papers (2022-07-23T10:29:26Z)
Optimal Propagation for Graph Neural Networks [51.08426265813481]
We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
arXiv Detail & Related papers (2022-05-06T03:37:00Z)
Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
arXiv Detail & Related papers (2022-04-13T15:54:35Z)
Density-Based Clustering with Kernel Diffusion [59.4179549482505]
A naive density corresponding to the indicator function of a unit $d$-dimensional Euclidean ball is commonly used in density-based clustering algorithms. We propose a new kernel diffusion density function, which is adaptive to data of varying local distributional characteristics and smoothness.
arXiv Detail & Related papers (2021-10-11T09:00:33Z)
A Regularized Wasserstein Framework for Graph Kernels [32.558913310384476]
We propose a learning framework for graph kernels grounded on regularizing optimal transport. This framework provides a novel optimal transport distance metric, namely Regularized Wasserstein (RW) discrepancy. We have empirically validated our method using 12 datasets against 16 state-of-the-art baselines.
arXiv Detail & Related papers (2021-10-06T07:54:04Z)
Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation [0.0]
We build a unifying framework to interpolate between density-driven and geometry-based algorithms for data clustering. We seek this connection through the introduction of Fokker-Planck equations on data graphs. We provide new theoretical insights on the behavior of the family of diffusion maps in the large sample limit.
arXiv Detail & Related papers (2021-08-18T02:00:33Z)
Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
arXiv Detail & Related papers (2021-04-24T08:09:27Z)
Local Graph Clustering with Network Lasso [90.66817876491052]
We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
arXiv Detail & Related papers (2020-04-25T17:52:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.