Weighted Graph Clustering with Non-Uniform Uncertainties

We study the graph clustering problem where each observation (edge or no-edge between a pair of nodes) may have a different level of confi-dence/uncertainty. We propose a clustering al-gorithm that is based on optimizing an appro-priate weighted objective, where larger weights are given to observations with lower uncertainty. Our approach leads to a convex optimization problem that is efficiently solvable. We analyze our approach under a natural generative model, and establish theoretical guarantees for recover-ing the underlying clusters. Our main result is a general theorem that applies to any given weight and distribution for the uncertainty. By optimiz-ing over the weights, we derive a provably opti-mal weighting scheme, which matches the infor-mation theoretic lower bound up to logarithmic factors and leads to strong performance bounds in several specific settings. By optimizing over the uncertainty distribution, we show that non-uniform uncertainties can actually help. In par-ticular, if the graph is built by spending a limited amount of resource to take measurement on each node pair, then it is beneficial to allocate the re-source in a non-uniform fashion to obtain accu-rate measurements on a few pairs of nodes, rather than obtaining inaccurate measurements on many pairs. We provide simulation results that validate our theoretical findings