Towards Robust and Scalable Density-based Clustering via Graph Propagation

• URL: http://arxiv.org/abs/2605.00390v1
• Date: Fri, 01 May 2026 04:26:26 GMT
• Title: Towards Robust and Scalable Density-based Clustering via Graph Propagation
• Abstract summary: textitCluProp reimagines varied-density clustering in high-dimensional spaces as a label propagation process over neighborhood graphs.<n>We introduce a deterministic density-based propagation strategy to ensure scalable neighborhood identification.
• Score: 5.964436882344728
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We present \textit{CluProp}, a novel framework that reimagines varied-density clustering in high-dimensional spaces as a label propagation process over neighborhood graphs. Our approach formally bridges the gap between density-based clustering and graph connectivity, leveraging efficient propagation mechanisms from network science to mitigate the parameter sensitivity inherent in traditional density-based methods. Specifically, we introduce a deterministic density-based propagation strategy to ensure scalable neighborhood identification. The framework is agnostic to the choice of distance metric and exhibits superior performance on large-scale data, processing millions of points in minutes while consistently outperforming existing baselines in accuracy.

Related papers

• Scalable Uncertainty Quantification for Black-Box Density-Based Clustering [3.5808917363708743]
  We introduce a novel framework for uncertainty quantification in clustering.<n>By combining the martingale posterior paradigm with density-based clustering, uncertainty in the estimated density is naturally propagated to the clustering structure.
  arXiv  Detail & Related papers  (2026-03-03T17:46:49Z)
• Scalable Varied-Density Clustering via Graph Propagation [6.800113478497425]
  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.
  arXiv  Detail & Related papers  (2025-08-05T01:33:41Z)
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  We propose ReDiSC, a structured diffusion model for structured node classification.<n>We show that ReDiSC achieves superior or highly competitive performance compared to state-of-the-art GNN, label propagation, and diffusion-based baselines.<n> Notably, ReDiSC scales effectively to large-scale datasets on which previous structured diffusion methods fail due to computational constraints.
  arXiv  Detail & Related papers  (2025-07-19T04:46:53Z)
• Fast Geometric Embedding for Node Influence Maximization [49.84018914962972]
  We introduce an efficient force layout algorithm that embeds a graph into a low-dimensional space, where the radial distance from the origin serves as a proxy for centrality measures.<n>As an application, it turns out that the proposed embedding allows to find high-influence nodes in a network, and provides a fast and scalable alternative to the standard greedy algorithm.
  arXiv  Detail & Related papers  (2025-06-09T05:21:56Z)
• 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)
• Towards the Uncharted: Density-Descending Feature Perturbation for Semi-supervised Semantic Segmentation [51.66997548477913]
  We propose a novel feature-level consistency learning framework named Density-Descending Feature Perturbation (DDFP) Inspired by the low-density separation assumption in semi-supervised learning, our key insight is that feature density can shed a light on the most promising direction for the segmentation classifier to explore. The proposed DDFP outperforms other designs on feature-level perturbations and shows state of the art performances on both Pascal VOC and Cityscapes dataset.
  arXiv  Detail & Related papers  (2024-03-11T06:59:05Z)
• SEM-GAT: Explainable Semantic Pose Estimation using Learned Graph Attention [10.883346969896621]
  This paper proposes a Graph Neural Network(GNN)-based method for exploiting semantics and local geometry to guide the identification of reliable pointcloud registration candidates. Semantic and morphological features of the environment serve as key reference points for registration, enabling accurate lidar-based pose estimation. We test our method on the KITTI odometry dataset, achieving competitive accuracy compared to benchmark methods and a higher track smoothness while relying on significantly fewer network parameters.
  arXiv  Detail & Related papers  (2023-08-07T16:43:46Z)
• 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)
• 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)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.