Improved Graph Clustering
Authors:
- 7 August 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (10) , 6440-6455
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 semirandom graphs, heterogeneous degree distributions, unequal cluster sizes, unaffiliated nodes, partially observed graphs, planted clique/coloring, and so on. 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.Keywords
All Related Versions
Funding Information
- National Science Foundation (EECS-1056028)
- Defense Threat Reduction Agency (HDTRA 1-08-0029)
- DTRA Young Investigator Award
- NSF (1302435, 1017525, 0954059)
- Ministry of Education of Singapore through Academic Research Fund Tier 2 (R-265-000-443-112)
This publication has 34 references indexed in Scilit:
- Low-Rank Matrix Recovery From Errors and ErasuresIEEE Transactions on Information Theory, 2013
- Compressed Sensing and Matrix Completion with Constant Proportion of CorruptionsConstructive Approximation, 2012
- How Hard Is It to Approximate the Best Nash Equilibrium?SIAM Journal on Computing, 2011
- Correlation Clustering with Noisy Input2010
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- Spectral techniques applied to sparse random graphsRandom Structures & Algorithms, 2005
- Max Cut for Random Graphs with a Planted PartitionCombinatorics, Probability and Computing, 2004
- Hiding Cliques for Cryptographic SecurityDesigns, Codes and Cryptography, 2000
- A Spectral Technique for Coloring Random 3-Colorable GraphsSIAM Journal on Computing, 1997
- Algorithmic theory of random graphsRandom Structures & Algorithms, 1997