Algorithms for partitioning well-clustered graphs
Luca Zanetti · Bristol Research (University of Bristol) · 2018
Graphs occurring in the real world usually exhibit a high level of order and organisation: higher concentration of edges within the same group of vertices, and lower concentration among different groups.A common way to analyse these graphs is to partition the vertex set of a graph into clusters according to some connectivity measure.Graph clustering has been widely applied to many fields of computer science, from machine learning to bioinformatics and social network analysis.The focus of this thesis is to design and analyse algorithms for partitioning graphs presenting a strong cluster-structure, which we call well-clustered.We first study the spectral properties of the Laplacian matrix of such graphs, and prove a structure theorem that relates the eigenvectors corresponding to the smallest eigenvalues of the Laplacian matrix of a graph to the structure of its clusters.We then harness this theorem to analyse Spectral Clustering, arguably the most popular graph clustering algorithm.We give for the first time approximation guarantees on the number of misclassified vertices by Spectral Clustering when applied to well-clustered graphs.Since Spectral Clustering needs to compute as many eigenvectors of the Laplacian matrix as the number of clusters in the graph, its performance deteriorates as this number grows.We present an algorithm that overcomes this issue without compromising its accuracy.This algorithm runs in time nearly linear in the number of the edges and independently of the number of clusters in the input graph.Finally, we tackle the problem of partitioning a graph whose description is distributed among many sites.We present a distributed algorithm that works in a few synchronous rounds, requires limited communication complexity, and achieves the same guarantees of Spectral Clustering as long as the clusters are balanced in size. is equal to one on S and zero everywhere else.A fundamental fact in spectral graph theory states that a vector χ is an eigenvector of eigenvalue zero for L G if and only if χ can be expressed as a linear combination of the indicator vectors of the connected components of G [17].Our structure theorem is a robust version of this fact 1 : let G be a well-clustered graph with optimal clusters S 1 , . . ., S k and let χ S 1 , . . ., χ S k be the indicator vectors of such clusters.Then, the k bottom eigenvectors of L G can be approximately expressed as linear combinations of χ S 1 , . . ., χ S k .Thanks to this structure theorem we are able to show that Spectral Clustering is able to approximately recover the optimal clusters of a well-clustered graph.Remarkably, we can show that even clusters of small size are well-approximated by Spectral Clustering, which is usually a very challenging problem.The efficiency of Spectral Clustering crucially depends on the number of clusters into which the graph needs to be partitioned.In particular, when the number of clusters k is large, there are two issues that need to be addressed: first of all, we need to compute the k bottom eigenvectors of the Laplacian, which necessarily takes Ω(n • k) time on a graph of n vertices.Secondly, we need to solve a k-means problem, which again usually takes at least Ω(n • k) time.Therefore, when k is large, Spectral Clustering becomes much less efficient.To overcome this drawback, we present an algorithm for partitioning well-clustered graphs whose running time is nearly-linear in the number of edges of the graph and independent of k.Instead of computing the spectral embedding, our algorithm uses an embedding based on the heat-kernel of the graph [59], which can be computed quickly by combining fast matrix-exponential algorithms [51] with Johnson-Lindestrauss random projections [31].Moreover, our algorithm exploits the geometry of the heat-kernel embedding to partition points in the embedding without having to resort to standard k-means algorithms.The final part of the thesis is devoted to the design and analysis of a distributed algorithm for partitioning a well-clustered graph.More precisely, we assume we have a distributed network in which each node is a computational unit and communication can occur only between neighbouring nodes.Our goal is to assign a label to each node of the network that indicates which cluster the node belongs to.We present a distributed algorithm that, assuming the topology of the network can be described by a well-clustered graphs with clusters of balanced size, computes an almost-optimal clustering.In other words, we are able to partition a network in a distributed way with almost the same guarantees of Spectral Clustering.Moreover, for reasonable