Improved Graph Clustering

DOI10.1109/TIT.2014.2346205zbMATH Open1360.94499arXiv1210.3335MaRDI QIDQ2986111FDOQ2986111

Authors: Yudong Chen, Sujay Sanghavi, Huan Xu 

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1210.3335

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15)

Cited In (16)

• Recovering nonuniform planted partitions via iterated projection
• On semidefinite relaxations for the block model
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• Exact Clustering of Weighted Graphs via Semidefinite Programming
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Graph Clustering using Effective Resistance
• Convex relaxation methods for community detection
• Clustering heterogeneous financial networks
• A simple spectral algorithm for recovering planted partitions
• Estimating Mixed Memberships With Sharp Eigenvector Deviations
• A Class of Random Matrices
• Graph clustering
• Clustering probabilistic graphs using neighbourhood paths
• Convex optimization for the densest subgraph and densest submatrix problems
• Title not available (Why is that?)
• \(k\)-median: exact recovery in the extended stochastic ball model

This page was built for publication: Improved Graph Clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986111)