Estimating Power-Law Exponent with Edge Differential Privacy
This work addresses privacy concerns in graph analysis for domains with sensitive relationship data, offering a more accurate and efficient solution compared to traditional approaches.
The paper tackles the problem of estimating the power-law exponent of graph degree distributions while preserving edge differential privacy, proposing a method that privatizes low-dimensional sufficient statistics to reduce distortion and enabling efficient parameter estimation across centralized and local privacy models.
Many real-world graphs have degree distributions that are well approximated by a power-law, and the corresponding scaling parameter $α$ provides a compact summary of that structure which is useful for graph analysis and system optimization. When graphs contain sensitive relationship data, $α$ must be estimated without revealing information about individual edges. This paper studies power-law exponent estimation under edge differential privacy. Instead of first releasing a noisy degree distribution and then fitting a power-law model, we propose privatizing only the low-dimensional sufficient statistics needed to estimate $α$, thereby avoiding the high distortion introduced by traditional approaches. Using these released statistics, we support both discrete approximation and likelihood-based numerical optimization for efficient parameter estimation. We develop edge-DP algorithms for both centralized and local DP models, compare degree release and log-statistic release in the local setting, and evaluate the resulting methods on various graph datasets across multiple privacy budgets and tail-cutoff settings.