Abstract:Subgraph counting is a fundamental primitive for graph analytics, with applications ranging from social recommendation to anomaly detection. Private subgraph counting under edge local differential privacy (edge-LDP) is challenging without a trusted server or shuffler. We propose two abstractions: the \textbf{Noisy Adjacency Matrix (NAM)} framework, which reformulates private subgraph counting as algebraic estimation over unbiased randomized matrices, and \textbf{Differential Privacy on Randomized Data (DPRD)}, which gives a composition rule for calibrating later-round noise when auxiliary inputs are randomized. Using these tools, we design one-round and two-round estimators for triangle and quadrangle (4-cycle) counting, including TriOR, TriTR, TriMTR, QuaTR, and $\text{TriTR}^*$. We provide the first exact closed-form MSE for the RR-based one-round triangle estimator class and the first relative-error bounds for two-round triangle counting, showing error independent of graph size when the clustering coefficient and average degree are stable. Experiments on two real graphs show that the proposed two-round algorithms outperform all evaluated edge-LDP and shuffle-model baselines in terms of relative error.
From: Ying Zhou [view email]
[v1]
Wed, 9 Jul 2025 03:13:15 UTC (2,175 KB)
[v2]
Wed, 26 Aug 2026 08:24:14 UTC (1,985 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。