Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2602.13460 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912904284995584 |
|---|---|
| author | Xie, Michael Wu, Jiayi Nguyen, Dung Srinivasan, Aravind |
| author_facet | Xie, Michael Wu, Jiayi Nguyen, Dung Srinivasan, Aravind |
| contents | 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 $Δ$. We show that our algorithm provides a \(3ε\)-differentially private coloring with \(O(\frac{\log n}ε+d)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$ Furthermore, we show that this algorithm can generalize to $O(\fracΔ{cε}+d)$ defectiveness, where c is the size of the palette and $c=O(\fracΔ{\log n})$. Our second algorithm utilizes noisy thresholding to guarantee \(O(\frac{\log n}ε)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$, generalizing to all graphs rather than just d-inductive ones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_13460 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Differentially private graph coloring Xie, Michael Wu, Jiayi Nguyen, Dung Srinivasan, Aravind Data Structures and Algorithms 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 $Δ$. We show that our algorithm provides a \(3ε\)-differentially private coloring with \(O(\frac{\log n}ε+d)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$ Furthermore, we show that this algorithm can generalize to $O(\fracΔ{cε}+d)$ defectiveness, where c is the size of the palette and $c=O(\fracΔ{\log n})$. Our second algorithm utilizes noisy thresholding to guarantee \(O(\frac{\log n}ε)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$, generalizing to all graphs rather than just d-inductive ones. |
| title | Differentially private graph coloring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.13460 |