Accelerating Multilevel Graph Partitioning for Skewed-Degree Graphs via Lazy Gain Updates

Graph partitioning sits underneath a lot of parallel computing, graph machine learning, and large-scale data analytics work. The basic idea is simple: split a big graph into roughly equal-sized pieces while cutting as few edges between them as possible. Tools like METIS and KaHIP do this well on “normal” graphs, but they slow down badly on skewed-degree graphs, where a handful of hub vertices have enormous connectivity and everything else is sparse. During refinement, these hubs force a lot of gain values to be recalculated even when nothing near them has actually changed. This report proposes a faster refinement strategy built around lazy gain updates: instead of recomputing every vertex's gain after every move, only the vertices whose neighbourhood actually changed get recomputed, and everything else just reuses a cached value. Compared to the original proposal, this version goes further it lays out a concrete system architecture for the lazy update engine, implements the full coarsen / initial-partition / refine pipeline, and runs it on synthetic power-law graphs to see what actually happens. Across graphs from 1,000 to 16,000 vertices, the lazy strategy cut the number of gain evaluations by 98–99% and made refinement 66 to over 800 times faster than an eager baseline, without changing the final edge-cut at all. In other words, the speed comes for free quality is not being traded away.