Exact clustering of weighted graphs via semidefinite programming
(2019) In Journal of Machine Learning Research 20. p.134 Abstract
As a model problem for clustering, we consider the densest kdisjointclique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized. We establish that such subgraphs can be recovered from the solution of a particular semidefinite relaxation with high probability if the input graph is sampled from a distribution of clusterable graphs. Specifically, the semidefinite relaxation is exact if the graph consists of k large disjoint subgraphs, corresponding to clusters, with weight concentrated within these subgraphs, plus a moderate number of nodes not belonging to any cluster. Further, we establish that if noise is weakly obscuring these clusters, i.e, the... (More)
As a model problem for clustering, we consider the densest kdisjointclique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized. We establish that such subgraphs can be recovered from the solution of a particular semidefinite relaxation with high probability if the input graph is sampled from a distribution of clusterable graphs. Specifically, the semidefinite relaxation is exact if the graph consists of k large disjoint subgraphs, corresponding to clusters, with weight concentrated within these subgraphs, plus a moderate number of nodes not belonging to any cluster. Further, we establish that if noise is weakly obscuring these clusters, i.e, the betweencluster edges are assigned very small weights, then we can recover significantly smaller clusters. For example, we show that in approximately sparse graphs, where the betweencluster weights tend to zero as the size n of the graph tends to infinity, we can recover clusters of size polylogarithmic in n under certain conditions on the distribution of edge weights. Empirical evidence from numerical simulations is also provided to support these theoretical phase transitions to perfect recovery of the cluster structure.
(Less)
 author
 Pirinen, Aleksis ^{LU} and Ames, Brendan
 organization
 publishing date
 2019
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Clustering, Densest subgraph, Semidefinite programming, Sparse graphs, Stochastic block models
 in
 Journal of Machine Learning Research
 volume
 20
 pages
 1  34
 publisher
 Microtome Publishing
 external identifiers

 scopus:85072637509
 ISSN
 15324435
 language
 English
 LU publication?
 yes
 id
 0d20fe2869144ad98eba65a0620181f8
 alternative location
 http://jmlr.org/papers/v20/16128.html
 date added to LUP
 20191007 13:51:31
 date last changed
 20200113 02:27:11
@article{0d20fe2869144ad98eba65a0620181f8, abstract = {<p>As a model problem for clustering, we consider the densest kdisjointclique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized. We establish that such subgraphs can be recovered from the solution of a particular semidefinite relaxation with high probability if the input graph is sampled from a distribution of clusterable graphs. Specifically, the semidefinite relaxation is exact if the graph consists of k large disjoint subgraphs, corresponding to clusters, with weight concentrated within these subgraphs, plus a moderate number of nodes not belonging to any cluster. Further, we establish that if noise is weakly obscuring these clusters, i.e, the betweencluster edges are assigned very small weights, then we can recover significantly smaller clusters. For example, we show that in approximately sparse graphs, where the betweencluster weights tend to zero as the size n of the graph tends to infinity, we can recover clusters of size polylogarithmic in n under certain conditions on the distribution of edge weights. Empirical evidence from numerical simulations is also provided to support these theoretical phase transitions to perfect recovery of the cluster structure.</p>}, author = {Pirinen, Aleksis and Ames, Brendan}, issn = {15324435}, language = {eng}, pages = {134}, publisher = {Microtome Publishing}, series = {Journal of Machine Learning Research}, title = {Exact clustering of weighted graphs via semidefinite programming}, url = {http://jmlr.org/papers/v20/16128.html}, volume = {20}, year = {2019}, }