Dissertation defense Monday

CSE Graduate Defenses
CSE Graduate Defenses

Dissertation Defense: "Scalable Parallel Community Detection for Large-Scale Graphs"

Jianping Zeng
Committee Members: Dr. Hongfeng Yu (Advisor)
Dr. Hong Jiang, Dr. Lisong Xu, and Dr. Min Han

Monday, November 13, 2017, 9:30 a.m.
211 Schorr Center

Community detection, also named as graph clustering, is essential to various graph analysis applications and can help researchers in a wide range of fields (such as computer science, biology, sociology, and so on) gain deep insights of graphs. As we enter the era of big data, community detection becomes a severely challenging task due to the ever-increasing sizes of graphs. A large graph can contain billions or even trillions of vertices and edges, which is difficult to be processed efficiently using a single machine. Parallel clustering, which uses parallel machines with distributed memory, provides a natural solution to cope with large data. However, it remains an open problem to design scalable and accurate parallel community detection algorithms, which is mainly due to the two challenges. First, traditional graph partitioning schemes cannot well preserve the global structure information of a graph on a processor, which can lower the cluster quality of local community detection and impair the accuracy of final aggregated results. Second, for real-world graphs (for example, scale-free graphs), it is difficult to create a balanced graph partitioning, which can incur severe workload and communication imbalance among processors and impair the scalability of parallel community detection. In this dissertation, we holistically address these two challenges and develop a set of scalable solutions for presentative graph clustering algorithms as well as a unified end-to-end optimized graph clustering framework.
The first contribution of this dissertation is a new parallel hierarchical graph clustering algorithm that uses modularity as clustering criteria to effectively extract community structures in large graphs of different types. We design our algorithm based on the Louvain algorithm by investigating graph partitioning and distribution schemes on distributed memory architectures and conducting clustering in a divide-and-conquer manner. We study the relationship between graph structure property and clustering quality, carefully deal with ghost vertices between graph partitions, and propose a workload estimation model and a heuristic partition method suitable for the Louvain algorithm. Compared to the existing distributed Louvain algorithms, our solution can achieve nearly well-balanced workload among processors and higher accuracy of graph clustering on real-world large graph datasets.
Second, we exploit the vertex delegates partitioning, originally designed for distributed graph traversal, to further improve the scalability of distributed Louvain algorithms. Through the vertex delegates partitioning, our new distributed algorithm can achieve balanced workload and communication among massive processors with large graphs. We use a collective operation to synchronize the information on delegated vertices, and design a new heuristic strategy to ensure the convergence of the algorithm. Through different intensive experiments, we analyze and compare the correctness, the workload, and the communication of our algorithm to the other methods. Our algorithm clearly shows a superior scalability and parallel efficiency over the existing work.
Third, we analyze the Infomap algorithm, and explore the similarity between the distributed Infomap algorithm and the distributed Louvain algorithm. By taking advantage of the vertex delegates partitioning, we design and implement a new distributed Infomap algorithm that has scaled up to 4,096 cores and showed the significant performance improvement over the previous state-of-the-art distributed Infomap algorithm.
The last but not least contribution is that, by studying the common computation and communication patterns in the distributed Louvain algorithms and the distributed Infomap algorithms, we design a unified end-to-end optimized graph clustering framework based on asynchronous graph visitor queue. Our framework can not only ensure the balanced workload and communication, but also improve accuracy through immediately updated information than existing synchronized algorithms.