Source-linked AI summary
LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure
Jiawei Dong, Zhikun Zhang, Quan Yuan, Zhe Liu, Yunjun Gao
TL;DR
Graph synthesis under local differential privacy must preserve useful structure despite limited local views and the trade-off between information loss and noise. LDPGraph estimates and jointly refines degree-triangle targets, then reconstructs a graph; experiments on four real-world datasets report superiority over baselines.
Problem
Existing LDP graph methods face a trade-off between adjacency-list noise and structural information loss, while users lack direct access to connections among their neighbors.
Source: §I · pp. 1–2Method
LDPGraph combines a noisy global view with projected local connections to estimate triangle counts, jointly refines them with degrees, and reconstructs the graph using a triangle-first strategy.
Source: §I · p. 2, §16 · p. 7Results
Experiments on four real-world datasets demonstrate LDPGraph’s superiority compared with baselines.
Source: §VII · p. 12Takeaways & Limitations
The paper presents locally private graph synthesis from degree and triangle statistics as a route toward privacy-preserving graph analysis in local-view settings.
Source: §VII · p. 12
Abstract
from arXiv · showhide
The widespread application of graph data inevitably brings significant privacy risks, as its unprotected use can lead to the leakage of sensitive information. These risks are particularly acute in the setting with an untrusted curator, where the data remains decentralized and each user only holds the connections to their neighbors. To mitigate such privacy risks, we adopt local differential privacy (LDP) to collect users' private information and generate a synthetic graph. However, existing methods suffer from either excessive noise injection by perturbing the local adjacency lists or significant structural information loss due to the simplistic graph encoding process. To address these issues, we propose LDPGraph, an effective graph synthesis algorithm that takes one step further by exploiting neighborhood structures under LDP. To obtain neighborhood statistics beyond degrees, LDPGraph aggregates a noisy global view from perturbed adjacency lists and combines it with projected local connections to estimate node-level triangle counts. To correct the structural inconsistency caused by separately perturbing degree and triangle count, LDPGraph jointly refines them into feasible degree-triangle targets. To reconstruct a global graph from these estimated targets, LDPGraph adopts a triangle-first strategy that first preserves local clustering structures and then fulfills remaining degree requirements. Extensive experiments on four real-world datasets and multiple commonly used graph metrics validate the superiority of LDPGraph. Source code is available at https://github.com/ZJU-TrustAID/LDPGraph.
I. INTRODUCTION
Graph synthesis under an untrusted curator must protect decentralized user connections while retaining enough structure for useful synthetic graphs. LDPGraph targets neighborhood structure beyond one-hop statistics and reports stronger results than prior methods in most settings.
I. INTRODUCTION
- Existing degree-only generation loses connectivity detail, while adjacency-list perturbation introduces excessive noise under practical privacy budgets.LDPGen uses intermediate clustering, but its perturbed clustering accuracy is typically low and degree sequences still discard structural information.Source: §I · pp. 1–2
- LDPGraph targets neighborhood structure through degree and triangle count, capturing neighborhood size and the connections among a node’s neighbors.This extends the paper’s focus from one-hop statistics toward richer two-hop neighborhood structure.Source: §I · p. 2
- Estimating neighborhood structure is difficult because users lack access to edges among their neighbors, and separate perturbations can make degree and triangle targets infeasible.The paper identifies joint refinement and graph reconstruction satisfying degree and triangle constraints as further challenges.Source: §I · p. 2
- LDPGraph combines a noisy global view with projected local connections to estimate triangle counts, then jointly corrects noisy degrees and triangle counts before reconstruction.Its hierarchical reconstruction aims to preserve local neighborhood structures and reproduce topological properties.Source: §I · p. 2
- Across four real-world datasets, LDPGraph outperforms state-of-the-art methods in most settings; at privacy budget 1.0 on Facebook, modularity relative error is 65% lower and transitivity relative error is 80% lower than the best baseline.The paper also reports ablations validating threshold optimization and consistency restoration.Source: §I · p. 2
A. Local Differential Privacy
- LDP lets each user perturb data on their device before transmission, so sensitive raw information stays under user control rather than being sent to a trusted curator.The paper describes LDP graph synthesis as a way to generate a synthetic graph that preserves essential properties for downstream analyses.Source: §I · p. 1, A. Local Differential Privacy · p. 3
B. LDP Graph Analysis
The paper formulates graph synthesis with edge-LDP as collecting privatized node information and reconstructing a useful synthetic graph. Existing methods trade structural detail against noise, while LDPGraph’s overview adds neighborhood statistics and staged reconstruction.
A. Problem Definition
- The core problem is to let an untrusted curator reconstruct a high-fidelity synthetic graph from data collected under edge-LDP.Synthetic-graph utility may be assessed through degree distribution, transitivity, or community structure.Source: A. Problem Definition · p. 3, B. LDP Graph Analysis · p. 3
B. Existing Solutions
- DBG perturbs degrees and can match degree distribution but loses local and global structure, whereas ALBG perturbs adjacency lists and adds excessive noise at ordinary privacy budgets.ALBG could approach perfect reconstruction only with sufficiently large, often impractical privacy budgets.Source: B. Existing Solutions · pp. 3–4
- LDPGraph’s overview proceeds from perturbed degrees and adjacency lists to refined degree-triangle statistics, then builds within-group edges before adding cross-group edges for remaining degrees.The figure describes three phases: initial statistics collection, refined statistics estimation, and global graph reconstruction.Source: Figure 1 · p. 4
- LDPGen uses iterative clustering and noisy node-to-group connectivity, but its low-dimensional connectivity and degree information remain insufficient to capture richer structures.The cited discussion says these approaches exploit one-hop information and struggle to generate realistic neighborhood structure.Source: B. Existing Solutions · p. 4
IV. OUR PROPOSAL: LDPGraph
LDPGraph addresses the accuracy–privacy trade-off by targeting neighborhood structure through degree and triangle count. Its initial phase collects perturbed degrees and adjacency lists, then optimizes projection thresholds for triangle estimation.
A. Motivation
- Graph synthesis under LDP trades accuracy against privacy: basic degree statistics lose information, while high-dimensional structure can require noise that destroys utility.Neighborhood structure is represented by degree and the number of triangles in which a node participates.Source: A. Motivation · pp. 4–5
B. Overview
- The overview divides the privacy budget among degree collection, adjacency-list perturbation, and refined-statistics estimation, followed by graph reconstruction from consistent targets.Reconstruction groups nodes by triangle counts, builds intra-group edges for triangle targets, then adds inter-group edges for remaining degree requirements.Source: B. Overview · p. 5
C. Initial Statistics Collection
- Users perturb degrees and adjacency lists; the curator aggregates the reports into noisy degrees and a global noisy adjacency matrix.The noisy adjacency view helps users infer connections among their neighbors in the next phase.Source: C. Initial Statistics Collection · p. 5
- A projection threshold bounds triangle-count sensitivity, but a low threshold prunes information while a large threshold increases noise and estimate variance.Using the theoretical maximum degree as a universal bound adds substantial noise, while directly using a noisy degree can violate the LDP guarantee.Source: C. Initial Statistics Collection · p. 5
- LDPGraph parameterizes each user’s threshold as θ_i = ˜d_i + τ_i and chooses τ_i to minimize the combined projection and noise error.The threshold optimizer produces the suitable thresholds used for each user.Source: C. Initial Statistics Collection · p. 5
D. Refined Statistics Estimation
LDPGraph estimates node-level triangle counts from users’ projected local connections and a noisy global view, then jointly refines them with noisy degrees into feasible reconstruction targets.
D. Refined Statistics Estimation
- Degree captures neighborhood size and triangle count captures connectivity among neighbors, but separate perturbations can yield statistics inconsistent with any feasible local structure.The paper contrasts its node-level consistency goal with prior triangle-counting work focused mainly on total triangle counts.Source: §6 · p. 6
6 Step 2: Threshold Optimization
- Each user combines pruned local connections with noisy connections between neighbors to estimate triangles, then perturbs the estimate with Laplace noise before calibration and reporting.The hybrid view’s raw triangle count is biased by randomized response on edges between neighbors.Source: §6 · p. 6
- Consistency restoration finds degree-triangle pairs minimizing weighted ℓ2 error from noisy estimates within the feasible domain 0 ≤ d < N and 0 ≤ t ≤ d(d−1)/2.The weights are inversely proportional to the scales of their respective noise distributions; the refined statistics serve as feasible reconstruction targets.Source: §6 · p. 6
E. Global Graph Reconstruction
LDPGraph reconstructs the graph from estimated degree and triangle targets using a triangle-first strategy. It groups nodes and then constructs within-group and between-group edges in three steps.
E. Global Graph Reconstruction
- Triangle-first reconstruction builds the higher-order triangle structure before adding edges to meet remaining degree requirements.The section motivates this ordering because later edge additions can disrupt degrees and local clustering, while the remaining degree task is more manageable after triangles are formed.Source: E. Global Graph Reconstruction · p. 6
- The reconstruction proceeds through node grouping, intra-group construction, and inter-group construction.Source: E. Global Graph Reconstruction · p. 6
2 Step 1: Initial Assignment
Nodes are grouped by target triangle counts to make triangle formation tractable while respecting degree constraints. Within-group edges build triangles; between-group edges then address remaining degree deficits.
2 Step 1: Initial Assignment
- Groups are formed around similar target triangle counts, with minimum and maximum size bounds tied to triangle feasibility and the smallest degree target.The minimum size must permit the required within-group degree; the maximum prevents intra-group edges from exceeding a node’s degree target.Source: §16 · p. 7
- Nodes are initially assigned sequentially according to their required intra-group degree, and incomplete groups are sorted before further processing.Source: §16 · p. 7, §2 · p. 7
16 Sort the incomplete group S′ in ascending order of d′
- Underfilled groups are merged with adjacent groups after sorting by target triangle counts, preserving similarity in triangle targets.Source: §16 · p. 7
- Within each group, an Erdős–Rényi model samples edges with probability set from group size and the expected triangle count, approximating nodes’ triangle targets.Nodes in a group are treated as equivalent for triangle formation.Source: §16 · pp. 7–8
- Between-group edges fulfill remaining degree requirements while largely avoiding new triangles; weighted sampling prioritizes nodes with larger degree deficits.A Fenwick tree supports weighted selection and dynamic deficit updates in logarithmic time.Source: §16 · p. 8
F. Algorithm Analysis
The analysis establishes LDPGraph’s privacy guarantee and reports its computation and communication costs.
F. Algorithm Analysis
- The three data releases satisfy (ε1 + ε2 + ε3)-edge LDP by sequential composition.The curator’s reconstruction uses only perturbed data and consumes no additional privacy budget through post-processing.Source: F. Algorithm Analysis · p. 8
- User-side complexity is O(d^2N), curator-side complexity is O(dNlogN), and communication workload is O(dN).N is the number of users and d is their average degree.Source: F. Algorithm Analysis · p. 8
V. EVALUATION
LDPGraph is evaluated on four real-world datasets using node-level, local-clustering, and global-topology metrics. It generally performs better than the baselines, while ablations show complementary strengths in the two reconstruction components.
A. Experimental Setup
- The evaluation covers four real-world datasets and node-level, local-clustering, and global-topology metrics, with ten repetitions per setting.The global metrics include density, transitivity, and modularity; motif and diameter results are reported in Appendix C.1.Source: A. Experimental Setup · pp. 8–9
B. End-to-End Evaluation
- Across node, clustering, and global-topology metrics, LDPGraph generally leads baselines, with a small-ε Twitter node-level exception and strong Facebook transitivity and modularity results.The end-to-end figure organizes datasets by column and metrics by row, with privacy budget ε on the x-axis; lower performance values are better.Source: B. End-to-End Evaluation · p. 9, Figure 2 · p. 10
- LDPGraph has the lowest node-level errors on Facebook, Chameleon, and CA-HepPh, while DBG is slightly better on Twitter at small privacy budgets.The node-level measures are eigenvector-centrality MAE and degree-distribution KL divergence.Source: B. End-to-End Evaluation · p. 9
- Across most settings, LDPGraph has lower triangle-count relative error and clustering-coefficient MSE than all baselines.The paper attributes this local-clustering advantage to collecting triangle-count information.Source: B. End-to-End Evaluation · p. 9
C. Ablation Studies
- A4, integrating threshold optimization and consistency restoration, performs best in most ablation cases; A2 is stronger on clustering coefficient, while A3 is stronger on modularity.A3 has poor triangle-count performance at low privacy budgets, and A4 offers the most robust and balanced performance overall.Source: C. Ablation Studies · p. 10, Figure 3 · p. 11
D. Scalability
LDPGraph is reported to outperform baselines across four real-world datasets, with runtime scaling linearly in graph size and remaining feasible for sparse graphs. The section also examines privacy-budget trade-offs and situates the method among graph-synthesis and LDP-analysis approaches.
D. Scalability
- Runtime grows linearly with N and increases with average degree d, but remains feasible for most sparse real-world graphs.Execution time is comparable to ALBG and slower than DBG or LDPGen, alongside higher structural fidelity.Source: D. Scalability · p. 11, Figure 4 · p. 11
A. DP Graph Synthesis
- Centralized DP graph synthesis includes direct adjacency-matrix perturbation and generative-model approaches such as DER and PrivGraph.DER uses a noisy quadtree to find dense regions, while PrivGraph uses privately detected communities.Source: A. DP Graph Synthesis · pp. 11–12
E. Impact of Privacy Budget Allocation
- An unbalanced allocation favoring sensitive structural components yielded the best overall performance: ε1:ε2:ε3 = 0.2ε:0.4ε:0.4ε; very small ε1 degrades degree distribution, while insufficient ε3 when ε1 + ε2 is large degrades clustering coefficient and modularity.Source: E. Impact of Privacy Budget Allocation · p. 11
B. LDP Graph Analysis
- LDP graph-analysis work has addressed specific tasks, including subgraph counting, clustering-coefficient derivation, and triangle counting.The cited approaches use an extended local view, a one-round framework, or an additional interaction round, respectively.Source: B. LDP Graph Analysis · p. 12
VII. CONCLUSION
- Experiments on four real-world datasets report that LDPGraph outperforms the baselines.The conclusion describes its balance between privacy protection and data fidelity.Source: §VII · p. 12
APPENDIX A THEORETICAL ANALYSIS
The analysis chooses a projection threshold by balancing projection error against noise error in triangle-count estimation. It uses a noisy degree as a practical proxy and analyzes how the correction factor τ affects the two errors.
Threshold objective
- The threshold objective minimizes the combined projection and noise error for the triangle-count estimator, using heuristic approximations because a universal closed-form bound is challenging under LDP.Projection error captures information loss when θ < d, while noise error comes from Laplace noise.Source: Appendix A · p. 14
Projection-error approximation
- The analysis uses g(d) = d(d−1)/2 as a differentiable proxy for triangle count, representing its theoretical maximum for a node of degree d.The curator uses noisy degree ˜d because the true degree is unavailable.Source: Appendix A · p. 14
Effect of τ
- Increasing τ reduces projection error exponentially by making ego-graph pruning less likely, but increases sensitivity and Laplace noise.The threshold is θ = ˜d + τ; the objective selects τ to balance the two error terms.Source: Appendix A · p. 14
APPENDIX B ALGORITHM ANALYSIS
LDPGraph’s privacy analysis composes the guarantees for degree, adjacency-list, and triangle-count reporting. The curator’s reconstruction uses only perturbed data and consumes no additional privacy budget under post-processing.
Privacy guarantee
- LDPGraph satisfies (ε1 + ε2 + ε3)-edge LDP by sequentially composing the guarantees for its three data-collection phases.The total budget is ε = ε1 + ε2 + ε3.Source: §B.1 · pp. 14–15
Initial statistics collection
- Initial collection satisfies (ε1 + ε2)-edge LDP by composing Laplace-noised degree reporting with randomized-response adjacency-list reporting.The two mechanisms are applied to different statistics in the initial collection phase.Source: §B.1 · pp. 14–15
Refined statistics estimation
- Triangle-count estimation satisfies ε3-edge LDP by projecting each local ego-graph to a threshold θ that bounds its degree and sensitivity.A single change to a user's connections can change its triangle count by at most that user's degree.Source: §B.1 · p. 15
B.2 Complexity Analysis
The analysis gives worst-case O(N^2) user- and curator-side computation, while noting that sparse graphs and typical thresholds make execution feasible. It also reports sparse communication encoding and evaluates expanded graph metrics and budget allocation.
B.2 Complexity Analysis
- User-side and curator-side computation each have worst-case O(N^2) complexity, though typical thresholds and sparse graphs make the processes feasible in practice.The user-side worst case depends on the largest pruned degree; curator reconstruction can avoid a single large group in practice.Source: §B.2 · p. 15
B.3 Communication Overhead
- Sparse encoding reduces the curator's broadcast of the aggregated adjacency matrix to O(dN) communication overhead.Users first upload perturbed degrees and adjacency lists, then upload one perturbed triangle count.Source: §B.3 · p. 15
C.1 Evaluation on Expand Metrics
- LDPGraph reports the highest cosine similarity for 3- and 4-node motifs and consistently lower diameter relative error than baselines across the evaluated datasets and privacy budgets.The results attribute preservation of local structures and global connectivity to the consistency-restoration module and generation mechanism.Source: Figure 6 · p. 16, §C.1 · p. 16
C.2 Results of Privacy Budget Allocation
- Budget allocation has non-uniform effects: clustering coefficient and degree distribution are sensitive, while eigenvalue centrality is relatively robust.The adopted allocation prioritizes the sensitive features while maintaining reasonable performance on more stable metrics.Source: §C.2 · p. 16, Figure 7 · p. 17