Graph clustering is a fundamental problem in graph mining with important applications ranging from social networks analysis and entity resolution to computer vision and semi-supervised learning. In this talk I will discuss two novel variations of graph clustering. In the first part of the talk I will discuss the following clustering problem: there exist two latent clusters, and we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability less than 1/2. Can we recover the clusters with high probability and what is the minimum number of queries needed? I will present two state-of-the-art algorithms and a closely related application on predicting signs in online social networks. Our results improve recent results by Mazumdar and Saha [NIPS’17]. In the second part of the talk, I will discuss how to exploit motifs to uncover communities. Specifically, I will introduce the concept of motif-expanders that serves as the basis for motif-based clustering. I will present efficient algorithms and a well-performing heuristic that outperforms some of the most popular graph clustering tools. I will conclude with some experimental results that show the effectiveness of our methods to multiple applications in machine learning and graph mining.
09/12/2019