Distributed Evolutionary Graph Partitioning
We present a novel distributed evolutionary algorithm, KaFFPaE, to solve the Graph Partitioning Problem, which makes use of KaFFPa (Karlsruhe Fast Flow Partitioner). The use of our multilevel graph partitioner KaFFPa provides new effective crossover and mutation operators. By combining these with a scalable communication protocol we obtain a system that is able to improve the best known partitioning results for many inputs in a very short amount of time. For example, in Walshaw's well known benchmark tables we are able to improve or recompute 76% of entries for the tables with 1%, 3% and 5% imbalance.
Code (1)
Tasks
graph partitioningSimilar Papers 제목 키워드 기반
An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training
Recently, graph neural networks (GNNs) have gained much attention as a growing area of deep learning capable of learning on graph-structured data. However, the computational and memory requirements for training GNNs on l…
Graph Neural Networkgraph partitioningEvolutionary Acyclic Graph Partitioning
Directed graphs are widely used to model data flow and execution dependencies in streaming applications. This enables the utilization of graph partitioning algorithms for the problem of parallelizing computation for mult…
graph partitioningSchedulingEmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
Graph Neural Networks (GNNs) are widely used for learning on graph-structured data, but scaling GNN training to massive graphs remains challenging. To enable scalable distributed training, graphs are divided into smaller…
Graph Neural Networkgraph partitioningRecent Progress on Graph Partitioning Problems Using Evolutionary Computation
The graph partitioning problem (GPP) is a representative combinatorial optimization problem which is NP-hard. Currently, various approaches to solve GPP have been introduced. Among these, the GPP solution using evolution…
Combinatorial Optimizationgraph partitioningSurveyWawPart: Workload-Aware Partitioning of Knowledge Graphs
Large-scale datasets in the form of knowledge graphs are often used in numerous domains, today. A knowledge graphs size often exceeds the capacity of a single computer system, especially if the graph must be stored in ma…
graph partitioningKnowledge Graphs