Deep Clustering via Probabilistic Ratio-Cut Optimization

• URL: http://arxiv.org/abs/2502.03405v1
• Date: Wed, 05 Feb 2025 17:47:53 GMT
• Title: Deep Clustering via Probabilistic Ratio-Cut Optimization
• Authors: Ayoub Ghriss, Claire Monteleoni,
• Abstract summary: We propose a novel approach for optimizing the graph ratio-cut by modeling the binary assignments as random variables. We provide an upper bound on the expected ratio-cut, as well as an unbiased estimate of its gradient, to learn the parameters of the assignment variables in an online setting.
• Score: 0.7366405857677227
• License:
• Abstract: We propose a novel approach for optimizing the graph ratio-cut by modeling the binary assignments as random variables. We provide an upper bound on the expected ratio-cut, as well as an unbiased estimate of its gradient, to learn the parameters of the assignment variables in an online setting. The clustering resulting from our probabilistic approach (PRCut) outperforms the Rayleigh quotient relaxation of the combinatorial problem, its online learning extensions, and several widely used methods. We demonstrate that the PRCut clustering closely aligns with the similarity measure and can perform as well as a supervised classifier when label-based similarities are provided. This novel approach can leverage out-of-the-box self-supervised representations to achieve competitive performance and serve as an evaluation method for the quality of these representations.

Related papers

• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Robust Consensus Clustering and its Applications for Advertising Forecasting [18.242055675730253]
  We propose a novel algorithm -- robust consensus clustering that can find common ground truth among experts' opinions. We apply the proposed method to the real-world advertising campaign segmentation and forecasting tasks.
  arXiv  Detail & Related papers  (2022-12-27T21:49:04Z)
• A parallelizable model-based approach for marginal and multivariate clustering [0.0]
  This paper develops a clustering method that takes advantage of the sturdiness of model-based clustering. We tackle this issue by specifying a finite mixture model per margin that allows each margin to have a different number of clusters. The proposed approach is computationally appealing as well as more tractable for moderate to high dimensions than a full' (joint) model-based clustering approach.
  arXiv  Detail & Related papers  (2022-12-07T23:54:41Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• Learning Structured Gaussians to Approximate Deep Ensembles [10.055143995729415]
  This paper proposes using a sparse-structured multivariate Gaussian to provide a closed-form approxorimator for dense image prediction tasks. We capture the uncertainty and structured correlations in the predictions explicitly in a formal distribution, rather than implicitly through sampling alone. We demonstrate the merits of our approach on monocular depth estimation and show that the advantages of our approach are obtained with comparable quantitative performance.
  arXiv  Detail & Related papers  (2022-03-29T12:34:43Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• Contrastive Clustering [57.71729650297379]
  We propose Contrastive Clustering (CC) which explicitly performs the instance- and cluster-level contrastive learning. In particular, CC achieves an NMI of 0.705 (0.431) on the CIFAR-10 (CIFAR-100) dataset, which is an up to 19% (39%) performance improvement compared with the best baseline.
  arXiv  Detail & Related papers  (2020-09-21T08:54:40Z)
• Robust Grouped Variable Selection Using Distributionally Robust Optimization [11.383869751239166]
  We propose a Distributionally Robust Optimization (DRO) formulation with a Wasserstein-based uncertainty set for selecting grouped variables under perturbations. We prove probabilistic bounds on the out-of-sample loss and the estimation bias, and establish the grouping effect of our estimator. We show that our formulation produces an interpretable and parsimonious model that encourages sparsity at a group level.
  arXiv  Detail & Related papers  (2020-06-10T22:32:52Z)
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning [48.42916680063503]
  We propose a novel adaptive preconditioning strategy for proximal algorithms on this problem class. We show that nested-forest decomposition of the inactive edges yields a guaranteed local linear convergence rate. Our results suggest that local convergence analysis can serve as a guideline for selecting variable metrics in proximal algorithms.
  arXiv  Detail & Related papers  (2020-02-27T16:33:09Z)

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.