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

Basit Ali, Jia Dongning, Muhammad Essa and Muhammad Mazhar

International Journal of Scientific Research in Computer Science, Engineering and Information Technology, 2026, vol. 12, issue 4, 77-86

Abstract: 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.

Keywords: graph partitioning; multilevel partitioning; skewed-degree graphs; power-law graphs; lazy evaluation; gain update; refinement; GPU acceleration; PyTorch; sparse tensors; METIS; KaHIP (search for similar items in EconPapers)
Date: 2026
Note: Article URL: https://ijsrcseit.com/home/article/view/CSEIT261243
References: Add references at CitEc
Citations:

Downloads: (external link)
https://ijsrcseit.com/home/article/view/CSEIT261243 Article URL (text/html)
https://ijsrcseit.com/home/article/download/CSEIT261243/CSEIT261243 Full text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jbh:ijsrcs:v12:y2026:i4:id:2113

DOI: 10.32628/CSEIT261243

Access Statistics for this article

More articles in International Journal of Scientific Research in Computer Science, Engineering and Information Technology from International Journal of Scientific Research in Computer Science, Engineering and Information Technology
Bibliographic data for series maintained by Pankaj Sharma (USA) ().