Acyclic Graph Pattern Counting under Local Differential Privacy

Summary: First general LDP framework for counting arbitrary acyclic graph patterns beyond triangles and stars. Recursive subpattern construction and random node marking prevent duplication, achieving Õ(√(N d(G)^k)) error with substantial utility and communication gains. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 7379
Venue: SIGMOD
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,188 | 30.11%
DOI: 10.1145/3802006

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. Kuncan Wang (Nanyang Technological University)
3. Wei Dong (Nanyang Technological University)

BibTeX Citation

@inproceedings{hu_sigmod26,
        title = {{Acyclic Graph Pattern Counting under Local Differential Privacy}},
        author = {Hu, Yihua and Wang, Kuncan 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/3802006},
        url = {https://dl.acm.org/doi/10.1145/3802006},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
281	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.00022445849
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
596	Private Analysis of Graph Structure	2011	VLDB	0.00015926024
836	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013715654
1,960	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	9.4058693e-05
2,542	Privacy at Scale: Local Differential Privacy in Practice	2018	SIGMOD	8.4460386e-05
4,394	R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys	2022	SIGMOD	6.7274063e-05
6,367	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD	5.8981989e-05
6,666	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD	5.8086805e-05
7,292	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS	5.653597e-05
8,158	Continual Observation of Joins under Differential Privacy	2024	SIGMOD	5.4756587e-05
10,385	N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics	2026	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,557	Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy	2024	SIGMOD
2	10,921	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB
3	836	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD
4	596	Private Analysis of Graph Structure	2011	VLDB
5	1,960	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD
6	10,970	Continuous Publication of Weighted Graphs with Local Differential Privacy	2025	VLDB
7	6,083	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD
8	10,446	Efficient and Effective Biclique Counting with Local Differential Privacy	2026	SIGMOD
9	6,367	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD
10	9,552	Practical and Accurate Local Edge Differentially Private Graph Algorithms	2025	VLDB