Lightweight Graph Partitioning Enhanced by Implicit Knowledge

doi:10.1109/TC.2025.3612730

Lightweight Graph Partitioning Enhanced by Implicit Knowledge

2025-09-24

0

PRE

AI

DOI：10.1109/TC.2025.3612730

Original

Original request for help

Save

Abstract

En 中文

Graph partitioning as a classic NP-complete problem, is the most fundamental procedure that needs to be performed before parallel computations. Partitioners can be divided into vertex- and edge-based approaches. Recently, both approaches are employing a streaming heuristic to find approximate solutions. It is lightweight in space and time complexities, but suffers from suboptimal partitioning quality, especially for directed graphs where the explicit knowledge provided for heuristic is limited. This paper thereby proposes new heuristics for not only vertex-based but also edge-based partitioning. They improve quality by additionally utilizing implicit knowledge, which is embedded in the local streaming view and the global graph view. Memory reduction techniques are presented to extract this knowledge with negligible space costs. That preserves the lightweight advantages of streaming partitioning. Besides, we study parallel acceleration and restreaming, to further boost the partitioning efficiency and quality. Extensive experiments validate that our proposals outperform the state-of-the-art competitors.

Keywords:

Parallel graph processing

streaming graph partitioning

restreaming partitioning

directed graphs

Lightweight Graph Partitioning Enhanced by Implicit Knowledge

Abstract

Journal

Organization