Differentially private graph coloring

Differential Privacy is the gold standard in privacy-preserving data analysis. This paper addresses the challenge of producing a differentially edge-private vertex coloring. In this paper, we present two novel algorithms to approach this problem. Both algorithms initially randomly colors each vertex from a fixed size palette, then applies the exponential mechanism to locally resample colors for either all or a chosen subset of the vertices. Any non-trivial differentially edge private coloring of graph needs to be defective. A coloring of a graph is k defective if all vertices of the graph share it’s assigned color with at most k of its neighbors. This is the metric by which we will measure the utility of our algorithms. Our first algorithm applies to d-inductive graphs. Assume we have a d-inductive graph with n vertices and max degree $\mathrm{\Delta }$. We show that our algorithm provides a $3\epsilon$-differentially private coloring with $O(\frac{\log n}{\epsilon }+d)$ max defectiveness, given a palette of size $\mathrm{\Theta }(\frac{\mathrm{\Delta }}{\log n}+\frac{1}{\epsilon })$ Furthermore, we show that this algorithm can generalize to $O(\frac{\mathrm{\Delta }}{c\epsilon }+d)$ defectiveness, where c is the size of the palette and $c=O(\frac{\mathrm{\Delta }}{\log n})$. Our second algorithm utilizes noisy thresholding to guarantee $O(\frac{\log n}{\epsilon })$ max defectiveness, given a palette of size $\mathrm{\Theta }(\frac{\mathrm{\Delta }}{\log n}+\frac{1}{\epsilon })$, generalizing to all graphs rather than just d-inductive ones.