Differentially Private Graph Coloring

Differential Privacy is the gold standard in privacy-preserving data analysis. This paper addresses the challenge of computing an edge-differentially private vertex coloring. In this paper, we present two novel algorithms for this problem. Both algorithms begin by coloring each vertex uniformly at random from a fixed-size palette, and then apply the exponential mechanism to locally resample colors for either all vertices or a selected subset of vertices. Any non-trivial edge differentially private coloring of a graph needs to be defective, as a proper coloring exposes the non-existence of an edge between two vertices of the same color. A coloring is $k$-defective if each vertex shares its color with at most $k$ of its neighbors. Our goal is to design coloring algorithms that use the minimum number of colors, while achieving the smallest possible defect under the edge-differential privacy. Our first algorithm applies to $d$-inductive graphs with maximum degree $Δ$. We show that it yields a \(3ε\)-differentially private coloring with \(O(\frac{\log n}ε+d)\) maximum defect, using a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$. Our second algorithm utilizes noisy thresholding to guarantee \(O(\frac{\log n}ε)\) maximum defect, using a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$, generalizing the results to all graphs rather than just $d$-inductive ones.