This page gives an overview of the differentially private graph algorithms for releasing degree distribution or subgraph counts.

Paper | Authors | DP Guarantee | Query Type | Algorithm Name | Short Name |
---|---|---|---|---|---|

ICDM'09 | Hay et al. | Edge/Node DP | Degree Distribution | Naive Laplace Mechanism over Degree Histogram | degHis(*) |

Laplace Mechanism over Degree Sequence | degSeq(*) | ||||

TCC'13 | Kasiwiswanathan et al. | Node DP | Degree Distribution | Naive Node Truncation based Mechanism | nodeTrun |

Degree Distribution & Subgraph Counting | Flowgraph based Mechanism | flowgraph | |||

SIGMOD'16 | Day et al. | Node DP | Degree Distribution | Edge Addition based Mechanism over Partitioned Histogram | edgeAddHist |

Edge Addition based Mechanism over Cumulative Histogram | edgeAddCum | ||||

VLDB'11 | Karwa et al. | Edge DP | Subgraph Counting | Smooth Sensitivity Mechanism | smoothSens |

k-Triangle Counting | Noisy Local Sensitivity Mechanism | noisyLocalSens | |||

SIGMOD'13 | Chen & Zhou | Edge/Node DP | Subgraph Counting | Recursive Mechanism | recursive(*) |

ITCS'13 | Blocki et al. | Edge/Node DP | Subgraph Counting | Restricted Sensitivity Mechanism | restricted(*) |

SIGMOD'15 | Zhang et al. | Edge DP | Subgraph Counting | Ladder Mechanism | ladder |

WOSN'12 | Proserpio et al. | Edge DP | Synthetic Graph | wPINQ queries | wpinq |

PSD'14 | Karwa et al. | Edge DP | Synthetic Graph | Randomized Response ERGM Synthesis | ergmSyn |

CCS'17 | Qin et al. | Local Edge DP | Synthetic Graph | Local DP Graph Generation | ldpGen |

PoPets'20 | Chen et al. | Edge/Node attribute DP | Synthetic Graph | CAGM Graph Synthesis | cagmSyn |

NeurIPS'19 | Sealfon & Ullman | Node DP | Synthetic Graph | Erdos-Renyi Estimator | erdosRenyiSyn |