We determine the information-theoretic cutoff value on separation of cluster centers for exact recovery of cluster labels in a -component Gaussian mixture model with equal cluster sizes. Moreover, we show that a semidefinite programming (SDP) relaxation of the -means clustering method achieves such sharp threshol…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Cluster Recovery”
A new clustering method improves recovery guarantees by re-embedding data.
problem Improving recovery guarantees in clustering algorithms.
method Chaining four techniques: leapfrog distances, multidimensional scaling, spectral methods, and sum-of-norms clustering.
result Re-embedding data improves recovery guarantees of clustering.
Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guaranteescs.LG
Paper proposes a new clustering model that preserves cluster recovery with fewer dimensions.
problem Clustering high-dimensional data with limited embedding dimensions.
method Randomly projected convex clustering model with improved embedding dimension.
result Cluster recovery can be preserved with fewer dimensions, independent of data points.
Paper proposes efficient methods for clustering and signal recovery in high-dimensional data with block structures.
problem High-dimensional clustering and signal recovery under block signal structures.
method CFA-PCA and MA-PCA methods for sparse and dense block signals.
result Proposed methods achieve computational minimax optimality for clustering and signal recovery.
Paper explores limits of high-order clustering with planted structures.
problem Statistical and computational limits of high-order clustering with planted structures.
method Developed methods for detection and recovery of clusters, identified signal-to-noise ratio boundaries.
result Sharp boundaries of signal-to-noise ratio for statistical and computational feasibility.
BalLOT uses optimal transport for balanced k-means clustering.
problem Balanced -means clustering of data.
method BalLOT is an optimal transport approach to alternating minimization.
result BalLOT provides theoretical guarantees for exact and partial recoveries of planted clusters.
Exact cluster recovery with same-cluster queries for arbitrary ellipsoidal clusters.
problem Recovering clusters from same-cluster queries in arbitrary ellipsoidal clusters.
method Relaxing spherical -means assumption to arbitrary ellipsoidal clusters, designing an algorithm with logarithmic query complexity.
result Exact recovery of clusters using queries and time.
We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: -means and -median clustering. Motivations for focusing on convex relaxations are: (a) they come with a certificate of optimality, and…
Geometric framework links clustering accuracy to structural recovery.
problem Understanding the trade-off between robustness and sensitivity in clustering.
method Develops a clustering condition number to compare within-cluster scale to the minimum loss increase required to move a point across a cluster boundary.
result Sharp phase transitions for exact recovery under different objectives, providing geometric principle for interpreting low objective values.
KSS method converges and recovers correct clustering under certain conditions.
problem Subspace clustering for semi-randomly sampled data.
method Local convergence analysis and recovery guarantee for KSS method.
result KSS method converges superlinearly and finds correct clustering within loglog N iterations.
Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. The s…
New bounds for convex clustering under graph connectivity.
problem Understanding clustering performance under different graph connectivity structures.
method Random walks and concentration inequalities for random graph models.
result Improved rates of convergence for centroid recovery.
We propose a general modeling and algorithmic framework for discrete structure recovery that can be applied to a wide range of problems. Under this framework, we are able to study the recovery of clustering labels, ranks of players, signs of regression coefficients, cyclic shifts, and even group elements from a unified…
Diffusion -means clustering on manifolds: provable exact recovery via semidefinite relaxationsmath.ST
We introduce the {\it diffusion -means} clustering method on Riemannian submanifolds, which maximizes the within-cluster connectedness based on the diffusion distance. The diffusion -means constructs a random walk on the similarity graph with vertices as data points randomly sampled on the manifolds and edges as …
New algorithms recover clusters with minimal queries, connecting margins to recoverability.
problem Active cluster recovery with oracle queries for minimal cost.
method Introducing margin-based clustering, designing algorithms for various spaces.
result Achieve queries for general pseudometric spaces and convex clusters.
We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with blocks of equal size. More precisely, we consider a random -uniform hypergraph with vertices partitioned into clusters of size . Hyperedges are added independently with probability if is…
In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is …
New method recovers clusters in non-convex finite metric spaces with oracle queries.
problem Exact recovery of clusters in non-convex finite metric spaces.
method Introducing -convexity and a deterministic algorithm using oracle queries.
result Clusters can be recovered using same-cluster queries.
Spectral clustering for geometric graphs achieves strong consistency in community recovery.
problem Community recovery in dense geometric graphs.
method Spectral clustering algorithm using eigenvectors of adjacency matrix.
result Strong consistency in community recovery proved.
This paper tackles exact recovery of clusters in a stochastic Ising model on a SBM graph.
problem Recovering clusters in a stochastic Ising model on a SBM graph.
method Proposes a Stochastic Ising Block Model (SIBM) and establishes a sharp threshold for exact recovery.
result Sharp threshold for exact recovery of clusters in SIBM, with time complexity for .
Study exact partition recovery with same-cluster oracle, bounded error.
problem Exact recovery of partitions with same-cluster oracle in adversarial error.
method Novel connection to correlation clustering, Rényi-Ulam framework, upper and lower bounds, randomized algorithm analysis, adaptivity-query complexity study.
result Upper and lower bounds on worst-case query complexity, expected performance bounds of randomized algorithm.
We suggest using the max-norm as a convex surrogate constraint for clustering. We show how this yields a better exact cluster recovery guarantee than previously suggested nuclear-norm relaxation, and study the effectiveness of our method, and other related convex relaxations, compared to other clustering approaches.
The binary symmetric stochastic block model deals with a random graph of vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability within clusters and across clusters. In the asymptotic regime of and for fixe…
For a certain class of distributions, we prove that the linear programming relaxation of -medoids clustering---a variant of -means clustering where means are replaced by exemplars from within the dataset---distinguishes points drawn from nonoverlapping balls with high probability once the number of points drawn a…
New clustering method recovers hidden tree structure from data.
problem Recovering hidden hierarchical structure in data.
method Maximum average dot product for merging clusters in hierarchical clustering.
result The algorithm produces a tree that accurately represents the underlying generative hierarchical structure.
Spectral clustering achieves strong consistency in the stochastic block model under certain conditions.
problem Achieving strong consistency in spectral clustering for the stochastic block model.
method Entrywise analysis of the Fielder eigenvector of graph Laplacians.
result Spectral clustering achieves exact recovery of hidden communities under matching information-theoretic limits.
New spectral clustering method handles discrete covariates for better community detection.
problem Community detection in networks with discrete covariates.
method Spectral algorithm that separates latent network structure from observed covariates.
result Achieves perfect clustering with high probability in large, sparse networks.
There is a recent surge of interest in identifying the sharp recovery thresholds for cluster recovery under the stochastic block model. In this paper, we address the more refined question of how many vertices that will be misclassified on average. We consider the binary form of the stochastic block model, where ver…
Flexible model captures varying scales in data clusters.
problem Real-world data often exhibits varying scales or intensities, violating the homogeneity assumption of classical Gaussian mixture models.
method Individual-heterogeneous sub-Gaussian mixture model with an efficient spectral method for exact recovery.
result The method provably achieves exact recovery of true cluster labels under mild separation conditions.
Develops an ℓ_p theory for PCA and spectral clustering.
problem Lack of precise characterizations of PCA scores for low-dimensional embedding.
method An ℓ_p perturbation theory for PCA in Hilbert spaces, analyzing eigenvectors and Gram matrix.
result Optimal recovery results for Gaussian mixture and stochastic block models.
One-bit clustering method for two-component sub-Gaussian mixture models
problem Clustering in sub-Gaussian mixture models
method One-bit clustering using dithered quantization
result Decaying misclassification rate with exponential signal-to-noise ratio
Convex clustering is a recent stable alternative to hierarchical clustering. It formulates the recovery of progressively coalescing clusters as a regularized convex problem. While convex clustering was originally designed for handling Euclidean distances between data points, in a growing number of applications, the dat…
Functional neuroimaging can measure the brain?s response to an external stimulus. It is used to perform brain mapping: identifying from these observations the brain regions involved. This problem can be cast into a linear supervised learning task where the neuroimaging data are used as predictors for the stimulus. Brai…
New algorithm IAC recovers hidden communities in labeled SBM with optimal performance.
problem Recovering hidden communities in Labeled Stochastic Block Model with varying cluster sizes.
method IAC (Instance-Adaptive Clustering) algorithm, consisting of spectral clustering and iterative likelihood-based improvements.
result IAC achieves optimal performance matching instance-specific lower bounds in expectation and with high probability.
For the degree corrected stochastic block model in the presence of arbitrary or even adversarial outliers, we develop a convex-optimization-based clustering algorithm that includes a penalization term depending on the positive deviation of a node from the expected number of edges to other inliers. We prove that under m…
This work tackles community detection in networks with node attributes, achieving exact recovery.
problem Community detection in networks with correlated node attributes.
method Information-theoretic criterion and iterative clustering algorithm maximizing joint likelihood.
result Exact recovery of community labels under a general model for network and node attributes.
Solves complex clustering and rotation synchronization problem.
problem Challenges in classifying and synchronizing rotated objects into multiple categories.
method Semidefinite programming relaxations to solve the joint problem of community detection and synchronization.
result Exact recovery of community detection and synchronization when extending stochastic block model.
Bottom-up algorithms outperform top-down in hierarchical community detection at intermediate levels.
problem Finding the optimal hierarchical community structure in networks.
method A bottom-up algorithm for hierarchical clustering of networks.
result Bottom-up algorithms achieve the information-theoretic threshold for exact recovery at intermediate levels of the hierarchy.
Quick Shift is a popular mode-seeking and clustering algorithm. We present finite sample statistical consistency guarantees for Quick Shift on mode and cluster recovery under mild distributional assumptions. We then apply our results to construct a consistent modal regression algorithm.
New SDP algorithm recovers large clusters in SBM with small clusters of any size.
problem Graph clustering in SBM with large and small clusters.
method Semidefinite programming (SDP) with novel techniques to handle small clusters.
result Proves exact recovery of large clusters regardless of small cluster sizes.
The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in recovering communities in the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental information theoretic and computational l…
A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Modelsstat.ML
We propose and analyze a generic method for community recovery in stochastic block models and degree corrected block models. This approach can exactly recover the hidden communities with high probability when the expected node degrees are of order or higher. Starting from a roughly correct community partition …
In this paper we make two novel contributions to hierarchical clustering. First, we introduce an anomalous pattern initialisation method for hierarchical clustering algorithms, called A-Ward, capable of substantially reducing the time they take to converge. This method generates an initial partition with a sufficiently…
Proposes methods to recover labels from shuffled networks using graph averages.
problem Recovering labels from a shuffled network using graph averages.
method Cluster networks into classes, then match the new graph to cluster-averages, minimizing the graph matching objective function.
result Higher fidelity matching performance when clustering networks into different classes.
This paper investigates graph clustering in the planted cluster model in the presence of {\em small clusters}. Traditional results dictate that for an algorithm to provably correctly recover the clusters, {\em all} clusters must be sufficiently large (in particular, where is the number of nodes …
SMM improves signal recovery from noisy data.
problem Estimating signals from noisy and scaled observations.
method Spiked mixture model (SMM) with EM algorithm.
result SMM outperforms GMM in signal recovery.
Paper explores exact recovery of communities in weighted graphs using Gaussian and exponential distributions.
problem Exact recovery of communities in weighted graphs with Gaussian and exponential distributions.
method Introduces a new semi-metric to describe conditions for exact recovery and analyzes conditions for both complete and incomplete graphs.
result Necessary and sufficient conditions for exact recovery are asymptotically tight and applicable to both complete and incomplete graphs.
New method recovers matrices with nonlinear structures using optimization on Grassmann manifold.
problem Recovering high-rank matrices with nonlinear structures like subspaces or clusters.
method Formulated as rank minimization of a nonlinear feature map, approximated by constrained non-convex optimization on the Grassmann manifold, using Riemannian and alternating minimization schemes.
result Global convergence and worst-case complexity bounds for alternating minimization scheme, leading to unique limit point.