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 |