Scalable Graph Coloring Optimization Based on Spark GraphX Leveraging Partition Asymmetry

Yihang Shen, Xiang Li, Tao Yuan, Shanshan ChenSymmetry 2025 · DOI

TL;DR

This paper introduces Spardex, a novel parallel and distributed graph coloring algorithm designed for massive graphs. By cleverly exploiting the inherent asymmetry in graph partitioning within Spark GraphX, Spardex significantly reduces the number of colors needed and speeds up computation compared to existing methods, making large-scale graph coloring more efficient.

What Problem Does This Paper Address?

Graph coloring, the problem of assigning colors to vertices such that no adjacent vertices share the same color, is fundamental to many real-world applications like frequency allocation and task scheduling. However, coloring large, real-world graphs (often with millions or billions of edges) is computationally challenging. Existing parallel approaches, like those based on Pregel-like frameworks (e.g., Apache Giraph), struggle with communication bottlenecks and sequential execution stages. GPU-based methods face limitations with data transfer costs and memory constraints. Furthermore, many algorithms assume graph symmetry, which is rarely present in real-world networks, leading to degraded performance and increased color usage. This paper aims to address these limitations by developing a scalable, distributed algorithm that efficiently handles asymmetric graph structures.

Methods

Spardex is built upon Apache Spark's GraphX and employs a novel, symmetry-driven optimization strategy. Key components include:

  • EdgePartition1D Strategy: The input graph is partitioned using GraphX's EdgePartition1D, which inherently creates asymmetric partitions. Instead of fighting this asymmetry, Spardex leverages it.
  • Symmetry-Aware Initialization: Vertices are pre-colored based on local degree ranking within each partition, creating a high-quality initial configuration that accounts for structural symmetries and densities.
  • Partitioned Repaint Stage: Each partition independently reassigns its vertices to the smallest available colors in parallel. This avoids costly global iterations and minimizes inter-partition communication.
  • Minimum-Based Merge for Boundary Resolution: Vertices spanning multiple partitions exchange only the minimal valid color during merge operations, avoiding full-graph synchronization.
  • Two-Stage MapReduce Conflict Detection and Correction: A final MapReduce job identifies and corrects residual conflicts in a single pass, focusing only on key conflicts and avoiding a full graph traversal.
  • Spark-Specific Optimizations: Techniques like Adaptive Query Execution (AQE) skew join optimization are integrated to further enhance performance, particularly for imbalanced workloads.

Datasets

The experiments were conducted on seven real-world graph datasets obtained from the Stanford Network Analysis Project (SNAP):

  • amazon0302
  • cit-HepPh
  • com-Youtube
  • email-Enron
  • wiki-Vote
  • web-Stanford
  • web-Google

These datasets vary in size, degree, and directionality (directed/undirected).

Key Insights and Ideas

  • Exploiting Asymmetry is Key: The paper demonstrates that instead of trying to mitigate the asymmetry introduced by partitioning strategies like EdgePartition1D, it can be strategically exploited to improve coloring efficiency.
  • Local Optimization Drives Global Improvement: By focusing on locally optimal color assignments within partitions and then resolving conflicts efficiently, Spardex achieves better overall results than methods that aim for global optimality from the start.
  • Reduced Search Space: The combination of asymmetric partitioning and symmetric reassembly effectively reduces the search space for coloring, leading to faster convergence and fewer colors.
  • Targeted Conflict Resolution: The two-stage pipeline for conflict detection and correction avoids the need for full graph traversals, significantly improving performance.

Key Results

Spardex demonstrates significant improvements over existing algorithms:

  • Chromatic Number Reduction: Achieves an 8–72% reduction in the number of colors used compared to competitive algorithms (LLDF, LSLDF, and DistG).
  • Speedup: Provides a speedup of 1.13–10.27 times over concurrent algorithms.
  • Scalability: The algorithm is shown to be highly scalable, handling large-scale graph processing tasks effectively.
  • Optimization Impact: Data locality, memory management, and AQE optimization collectively reduce execution times by 35-46% and average RAM per node by 5-17% compared to the unoptimized version.

Limitations and Future Work

The authors acknowledge the following limitations:

  • Static Graphs: Spardex is designed for static graphs and requires full re-computation for dynamic or streaming graphs.
  • Unweighted/Unlabeled Graphs: The current algorithm assumes unweighted and unlabeled graphs, limiting its applicability in scenarios where vertex or edge attributes (like priorities or capacities) are crucial.

Future work includes:

  • Optimizing communication between executors.
  • Dynamically adjusting parallelism during runtime.
  • Extending the algorithm to support other graph-processing tasks.
  • Testing Spardex on a wider variety of datasets from different domains.

Summary updated

BibTeX
@article{shen2025scalable,
  author = {Yihang Shen and Xiang Li and Tao Yuan and Shanshan Chen},
  title = {{Scalable Graph Coloring Optimization Based on Spark GraphX Leveraging Partition Asymmetry}},
  journal = {Symmetry},
  year = {2025},
  doi = {10.3390/sym17081177},
}
Figure