Research map / Federated learning and privacy / Differential privacy

Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Differentially private clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a two-round local weight differential privacy protocol for counting below-threshold triangles in public-topology weighted graphs, with a flow-based triangle-to-node assignment and an O(d² log² d) smooth-sensitivity computation.

Problem

Counting triangles whose total edge weight is below a threshold under local differential privacy, where graph topology is public and only edge weights are sensitive.

Approach

Introduces local weight differential privacy (only weights protected, topology public) and exploits public topology to assign each triangle to one node via min-cost max-flow to minimize covariance from shared noisy weights; adds biased and unbiased estimators and an efficient smooth-sensitivity computation.

Key results

• Unbiased estimator with smooth sensitivity achieves up to two orders of magnitude smaller relative error than the baseline on ML-Tele-278 (relative error below 0.1 across almost all settings).
• Smooth-sensitivity variant gives about one order of magnitude smaller relative error than global-sensitivity variant.
• For planar graphs, the optimal assignment yields zero covariance and the biased estimator is asymptotically optimal with O(n^2/eps^2) error matching an Omega(n^2) lower bound.

Surprising findings

• On a sparse GAM graph the naive baseline outperforms the two-step approach.
• For large thresholds the baseline performs nearly as well as the unbiased smooth-sensitivity method.

Limitations

• Unbiased estimator has stronger dependence on privacy budget (1/eps1^4 terms), worse than biased for small epsilon.
• Biased estimator error grows quadratically with the number of triangles, causing constant relative error on triangle-rich graphs.
• Two-step approach underperforms naive baseline on sparse graphs.

Experimental setup

Datasets: ML-Tele-278 (Milan telecommunication graph) GAM biological network Google web graph synthetic complete and planar graphs

Benchmarks: ML-Tele-278

Metrics: relative error squared l2 error

Baselines: baseline (Laplace-noised edge weights then count triangles) global-biased global-unbiased smooth-biased smooth-unbiased

Builds on: two-round LDP triangle counting smooth sensitivity unbiased histogram estimator under LDP

Closest papers by meaning

• Faster approximate subgraph counts with privacy (NeurIPS 2023 · similarity 0.93)
• On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.87)
• Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.86)
• Differentially Private Gomory-Hu Trees (NeurIPS 2025 · similarity 0.85)
• Differentially Private Graph Diffusion with Applications in Personalized PageRanks (NeurIPS 2024 · similarity 0.85)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.84)