N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics

Summary: N2E reduces node-DP graph analytics to edge-DP via distance-preserving clipping and a node-DP max-degree estimator, so error scales with the graph's true max degree instead of a conservative worst-case bound. Instantiations yield first node-DP solutions (e.g., max-degree, degree distribution), match optimal edge-count error, and show up to 2.5× (edge count) and 80× (degree distribution) empirical error reductions. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: hfb3b13ab4a0fcbc4
Venue: SIGMOD
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,581 | 28.86%
DOI: 10.1145/3769808

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yihua Hu (Nanyang Technological University)
2. Hao Ding (Nanyang Technological University)
3. Wei Dong (Nanyang Technological University)

BibTeX Citation

@inproceedings{hu_sigmod26,
        title = {{N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics}},
        author = {Hu, Yihua and Ding, Hao and Dong, Wei},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3769808},
        url = {https://dl.acm.org/doi/10.1145/3769808},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,404	Acyclic Graph Pattern Counting under Local Differential Privacy	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
276	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.0002234348
558	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016470707
609	Private Analysis of Graph Structure	2011	VLDB	0.00015591971
854	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013441869
1,838	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.5315245e-05
2,009	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	9.1951579e-05
4,028	Shortest Paths and Distances with Differential Privacy	2016	PODS	6.8424244e-05
4,496	R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys	2022	SIGMOD	6.5764614e-05
6,495	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD	5.7658592e-05
6,661	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD	5.717454e-05
6,803	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD	5.6783493e-05
7,439	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS	5.5267455e-05
8,334	Continual Observation of Joins under Differential Privacy	2024	SIGMOD	5.3527996e-05
9,230	Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise	2025	VLDB	5.2056825e-05
11,685	Universal Private Estimators	2023	PODS	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,008	Towards Identity Anonymization on Graphs	2008	SIGMOD
2	10,634	Efficient and Effective Biclique Counting with Local Differential Privacy	2026	SIGMOD
3	854	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD
4	6,963	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS
5	7,483	DPGraph: A Benchmark Platform for Differentially Private Graph Analysis	2021	SIGMOD
6	6,210	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD
7	9,729	Practical and Accurate Local Edge Differentially Private Graph Algorithms	2025	VLDB
8	1,838	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD
9	6,495	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD
10	9,735	Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy	2024	SIGMOD