EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Basit Ali, Jia Dongning, Muhammad Essa, Muhammad Mazhar

International Journal of Scientific Research in Computer Science, Engineering and Information Technology · 13.07.2026 · 12 (4) · 77-86

DOI: 10.32628/cseit261243 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Scientific Research in Computer Science, Engineering and Information Technology, online erschienen am 13.07.2026. Verfasst von Basit Ali und 3 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Ali, B., Dongning, J., Essa, M., & Mazhar, M. (2026). Accelerating Multilevel Graph Partitioning for Skewed-Degree Graphs via Lazy Gain Updates. International Journal of Scientific Research in Computer Science, Engineering and Information Technology, 12(4), 77-86. https://doi.org/10.32628/cseit261243

Vancouver

Ali B, Dongning J, Essa M, Mazhar M. Accelerating Multilevel Graph Partitioning for Skewed-Degree Graphs via Lazy Gain Updates. International Journal of Scientific Research in Computer Science, Engineering and Information Technology. 2026;12(4):77-86. doi:10.32628/cseit261243

BibTeX
@article{Ali2026,
  author = {Ali, Basit and Dongning, Jia and Essa, Muhammad and Mazhar, Muhammad},
  title = {Accelerating Multilevel Graph Partitioning for Skewed-Degree Graphs via Lazy Gain Updates},
  journal = {International Journal of Scientific Research in Computer Science, Engineering and Information Technology},
  year = {2026},
  volume = {12},
  number = {4},
  pages = {77--86},
  doi = {10.32628/cseit261243}
}
Kostenlos starten →