I am pleased to invite you to attend the PhD Final Defense for Frank Wanye, as articulated below. When: Monday, February 17 at 3:00 p.m. Where: Torgersen 2050 or via Zoom @ https://virginiatech.zoom.us/my/wfeng What: Fast and Accurate Graph Clustering Graph clustering, also known as community detection, is a fundamental problem in graph analytics with applications across a wide variety of domains including bioinformatics, social media analysis, and anomaly detection. Graph clustering algorithms can be grouped into two categories: inferential and descriptive. While inferential algorithms deliver high accuracy, they also deliver poor performance and poor scalability, particularly on large graphs. Conversely, descriptive algorithms are fast and scalable but significantly less accurate. We focus on accelerating the performance and improving the scalability of stochastic block partitioning (SBP), an inferential graph-clustering algorithm based on sequential Bayesian inference. Like other inferential algorithms, SBP is highly accurate even on graphs with a complex community structure, but it does not scale well to large real-world graphs that can contain upwards of a million vertices. Our contributions center around developing novel approaches for accelerating SBP, namely data reduction via sampling, shared-memory parallelization, and distributed-memory parallelization. We then integrate these approaches into a unified, accelerated SBP implementation, which exhibits up to 322-fold speedup over sequential SBP on a one-million vertex graph when processed on 64 compute nodes with 128 cores each. Importantly, our approach accelerates SBP without sacrificing the algorithm’s accuracy on both real-world and synthetic graph datasets. ~~ Wu FENG | Synergy Lab | Depts. of CS, ECE, BEAM | NSF SHREC Center & SEEC Center at Virginia Tech | Professor, Turner Faculty Fellow, and Director | 2050 Torgersen Hall | 620 Drillfield Drive | VT | Blacksburg VA 24061 | 540-231-1192 | wfeng@vt.edu