Graph Clustering: Algorithms, Analysis and Query Design

Citation

Korlakai Vinayak, Ramya (2018) Graph Clustering: Algorithms, Analysis and Query Design. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9RR1WFK. https://resolver.caltech.edu/CaltechTHESIS:09222017-130217881

Abstract

A wide range of applications in engineering as well as the natural and social sciences have datasets that are unlabeled. Clustering plays a major role in exploring structure in such unlabeled datasets. Owing to the heterogeneity in the applications and the types of datasets available, there are plenty of clustering objectives and algorithms. In this thesis we focus on two such clustering problems: Graph Clustering and Crowdsourced Clustering.

In the first part, we consider the problem of graph clustering and study convex-optimization-based clustering algorithms. Datasets are often messy -- ridden with noise, outliers (items that do not belong to any clusters), and missing data. Therefore, we are interested in algorithms that are robust to such discrepancies. We present and analyze convex-optimization-based clustering algorithms which aim to recover the low-rank matrix that encodes the underlying cluster structure for two clustering objectives: clustering partially observed graphs and clustering similarity matrices with outliers. Using block models as generative models, we characterize the performance of these convex clustering algorithms. In particular, we provide explicit bounds, without any large unknown constants, on the problem parameters that determine the success and failure of these convex approaches.

In the second part, we consider the problem of crowdsourced clustering -- the task of clustering items using answers from non-expert crowd workers who can answer similarity comparison queries. Since the workers are not experts, they provide noisy answers. Further, due to budget constraints, we cannot make all possible comparisons between items in the dataset. Thus, it is important to design queries that can reduce the noise in the responses and design algorithms that can work with noisy and partial data. We demonstrate that random triangle queries (where three items are compared per query) provide less noisy data as well as greater quantity of data, for a fixed query budget, as compared to random edge queries (where two items are compared per query). We extend the analysis of convex clustering algorithms to show that the exact recovery guarantees hold for triangle queries despite involving dependent edges. In addition to random querying strategies, we also present a novel active querying algorithm that is guaranteed to find all the clusters regardless of their sizes and without the knowledge of any parameters as long as the workers are better than random guessers. We also provide a tight upper bound on the number of queries made by the proposed active querying algorithm. Apart from providing theoretical guarantees for the clustering algorithms we also apply our algorithms to real datasets.

Thesis Files