Improved Graph Clustering
Graph clustering involves the task of dividing nodes into clusters, so that the edge density is higher within clusters as opposed to across clusters. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this paper we present a new algorithm--a convexified version of Maximum Likelihood--for graph clustering. We show that, in the classic stochastic block model setting, it outperforms existing methods by polynomial factors when the cluster size is allowed to have general scalings. In fact, it is within logarithmic factors of known lower bounds for spectral methods, and there is evidence suggesting that no polynomial time algorithm would do significantly better. We then show that this guarantee carries over to a more general extension of the stochastic block model. Our method can handle the settings of semi-random graphs, heterogeneous degree distributions, unequal cluster sizes, unaffiliated nodes, partially observed graphs and planted clique/coloring etc. In particular, our results provide the best exact recovery guarantees to date for the planted partition, planted k-disjoint-cliques and planted noisy coloring models with general cluster sizes; in other settings, we match the best existing results up to logarithmic factors.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringGraph ClusteringStochastic Block ModelSimilar Papers 제목 키워드 기반
Spectral Modification of Graphs for Improved Spectral Clustering
Spectral clustering algorithms provide approximate solutions to hard optimization problems that formulate graph partitioning in terms of the graph conductance. It is well understood that the quality of these approxima…
Clusteringgraph partitioningThe Cluster Graphical Lasso for improved estimation of Gaussian graphical models
We consider the task of estimating a Gaussian graphical model in the high-dimensional setting. The graphical lasso, which involves maximizing the Gaussian log likelihood subject to an l1 penalty, is a well-studied approa…
ClusteringModel SelectionGraph-based data clustering via multiscale community detection
We present a graph-theoretical approach to data clustering, which combines the creation of a graph from the data with Markov Stability, a multiscale community detection framework. We show how the multiscale capabilities …
ClusteringCommunity Detectiongraph constructionSensitivityChameleon 2: An Improved Graph-Based Clustering Algorithm
Traditional clustering algorithms fail to produce human-like results when confronted with data of variable density, complex distributions, or in the presence of noise. We propose an improved graph-based clustering algori…
ClusteringHybrid Ensemble Deep Graph Temporal Clustering for Spatiotemporal Data
Classifying subsets based on spatial and temporal features is crucial to the analysis of spatiotemporal data given the inherent spatial and temporal variability. Since no single clustering algorithm ensures optimal resul…
ClusteringDiversityGraph Attention