Estimating Power-Law Exponent with Edge Differential Privacy* Adam Tan
Mohamed Hefny
Keval Vora
[email protected] Simon Fraser University Burnaby, BC, Canada
[email protected] Simon Fraser University Burnaby, BC, Canada
[email protected] Simon Fraser University Burnaby, BC, Canada
arXiv:2604.20274v1 [cs.DB] 22 Apr 2026
Abstract
high-degree nodes are rare while low-degree nodes are much more common. Estimating the scaling parameter 𝛼 of a power-law distribution helps tailor graph algorithms and systems that rely on degree information [1, 7, 17, 22, 33, 35]. Practitioners typically estimate 𝛼 by maximum likelihood, either through a closed-form discrete approximation or through numerical optimization [8]. For graphs containing sensitive relationship data, however, we must perform this estimation under privacy constraints so that the released parameter does not reveal sensitive information about individual edges or graph structure. To estimate 𝛼 while protecting sensitive graph information, we use differential privacy (DP) [11], which provides the formal framework for this goal by enabling data analysis while protecting sensitive graph information. Existing DP methods for graph analysis [10, 15, 28, 36, 39, 40] provide privacy guarantees for structural information in graphs. However, they do not study private estimation of the power-law scaling parameter 𝛼 directly. To address this gap, we develop algorithms for estimating the power-law scaling parameter 𝛼 under edge differential privacy (edge-DP), which protects individual edges. A common baseline for private 𝛼 estimation, used for example by Hay et al. [13], is to first release a DP degree-distribution histogram, that is, counts of how many nodes have degree 0, 1, 2, . . ., and then fit a power-law model to the privatized histogram via MLE. However, when the goal is to estimate a single scalar parameter, this pipeline of releasing a histogram and then fitting a model is inefficient. The noise added to each degree count, together with smoothing, binning, and projection steps, can distort the tail of the degree distribution before fitting, which leads to inaccurate 𝛼 estimates with high variance. Instead, we privatize only the low-dimensional statistics needed for the 𝛼 estimation. We start from the discrete approximation estimator for the power-law scaling parameter [8], decompose it into low-sensitivity sub-components, and apply the Laplace mechanism to each component before recombining them into a private estimate. We then show how the same privatized statistics can also support maximum likelihood estimation via numerical optimization, allowing us to obtain both discrete-approximation and numericaloptimization variants under edge-DP. Because the released quantities have low sensitivity, the Laplace mechanism adds relatively small noise. We develop differentially private algorithms under both the centralized and local models. In the centralized model, a trusted curator has access to the entire graph and releases noisy estimates of the required low-dimensional statistics. In the local model, there is no trusted curator, and each node perturbs its own edge-related statistics
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.
1 Introduction Graph databases are useful in domains where relationships are central to the data, enabling efficient structure-based information retrieval. However, graphs often contain sensitive information, and there is a need to develop privacy-preserving graph analysis techniques that prevent sensitive information from being leaked. Among the structural properties studied in graphs, degree distributions are especially important. Many real-world graphs exhibit scale-free behavior, in which a small number of nodes act as highly connected hubs while most nodes have relatively few connections. This pattern appears across domains such as the web, social networks, and online retail, among many others [30]. Such behavior is often modeled by a power-law distribution [8, 27, 30], typically expressed as 𝑃 (𝑑) ∝ 𝑑 −𝛼 , meaning that the probability 𝑃 (𝑑) that a node has degree 𝑑 decreases polynomially, with 𝛼 being a constant parameter of the distribution known as the scaling parameter, also referred to as the power-law exponent. This means * This version adds an appendix to the published paper.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. SeQureDB ’26, Bengaluru, India © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 979-8-4007-2219-6/2026/05 https://doi.org/10.1145/3807894.3810274 1
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
Adam Tan, Mohamed Hefny, and Keval Vora
Table 1: Notations. Symbols
Description
𝐺 = (𝑉 , 𝐸 ) 𝑑𝑣 𝑑 min , 𝑑 max 𝐷′ 𝑇𝑑𝑖𝑠𝑐 , 𝑁 𝑑˜𝑣 , 𝑇˜𝑑𝑖𝑠𝑐 , 𝑁˜ 𝛼ˆ CENTRAL , 𝛼ˆ LOCAL
Graph with nodes 𝑉 and edges 𝐸 Degree of node 𝑣 ∈ 𝑉 Degree range of MLE fit (𝑑 min , 𝑑 max ) Degrees in 𝐺 between 𝑑 min and 𝑑 max Statistics for 𝛼 estimation DP estimates of 𝑑 𝑣 ,𝑇𝑑𝑖𝑠𝑐 and 𝑁 Centralized DP and local DP 𝛼 estimates
for 𝑑 ∈ {𝑑 min, . . . , 𝑑 max } where 𝑑 max represents a known upper bound on the node degrees and 𝑍 (𝛼) is the normalizing constant based on Hurwitz-𝜁 -function [4]. The tail degrees with power-law distribution are captured in the multiset 𝐷 ′ = [𝑑 𝑣 : 𝑣 ∈ 𝑉 ∧ 𝑑 min ≤ 𝑑 𝑣 ≤ 𝑑 max ], and 𝑁 = |𝐷 ′ | is the number of degrees in the multiset 𝐷 ′ . Maximum Likelihood Estimation for 𝛼. A common way to estimate 𝛼 is through Maximum Likelihood Estimation (MLE). Clauset et al. [8] showed that a closed-form discrete approximation estimator for observed degrees 𝑑𝑖 ∈ 𝐷 ′ can be defined as follows: 𝑁 ∑︁ 𝑁 𝑑𝑖 𝛼ˆdisc = 1 + 𝑇disc = ln (2) 𝑇disc 𝑑 min − 0.5 𝑖=1
before release. We study two local release strategies: degree release and log-statistic release. Together, these choices give two centralized edge-DP algorithms, one based on discrete approximation and another based on numerical optimization, and four local edge-DP variants obtained by combining degree release or log-statistic release with discrete approximation or numerical optimization. We evaluate the accuracy of these methods on 6 publicly available graph datasets and 3 synthetic datasets. Our results show that directly privatizing the sufficient statistics needed to estimate 𝛼 is more accurate and more stable than histogram-based fitting in the centralized model. Among the methods that privatize the sufficient statistics directly, numerical optimization is overall more accurate than discrete approximation.
This discrete approximation provides a closed-form estimate which may generally be good enough for most practical purposes. Alternatively, 𝛼ˆdisc can be obtained by numerical optimization as described next. The likelihood function for the discrete power-law model in Eq. 1 with 𝑑𝑖 ∈ 𝐷 ′ is [4, 8]: 𝑁 𝑁 ∑︁ ∑︁ ℓ (𝛼; 𝐷 ′ ) = log 𝑃 (𝑑𝑖 | 𝛼) = −𝛼 ln 𝑑𝑖 − 𝑁 ln 𝑍 (𝛼) 𝑖=1
2 Background and Setup
ℓ (𝛼;𝑇 , 𝑁 ) = −𝛼𝑇 − 𝑁 ln 𝑍 (𝛼)
This section introduces the graph model, the power-law estimation setup, and the privacy definitions used throughout the paper. Table 1 summarizes the main notations.
𝛼 >0
Graph. We consider a simple undirected graph 𝐺 = (𝑉 , 𝐸), where 𝑉 denotes the set of nodes and 𝐸 the set of edges. The degree of a node 𝑣 ∈ 𝑉 is denoted by 𝑑 𝑣 .
In graph data where sensitive information lies in connections between entities, edge differential privacy (edge-DP) [19] ensures analyses do not reveal individual edges. Similar to the original DP formulation by Dwork et al. [11], with edge-DP each edge is treated as an individual entry in a database (or graph) 𝐺. Edge Differentially Private 𝛼 Estimation. A randomized 𝛼 estimation algorithm A (𝐺) that takes input graph 𝐺 and outputs some 𝛼ˆdisc value from output space R is 𝜀 edge differentially private (𝜀-edge-DP) if for all 𝑅 ⊆ R, and neighboring graphs 𝐺 and 𝐺 ′ , 𝑃𝑟 (A (𝐺) ∈ 𝑅) ≤ 𝑒 𝜀 𝑃𝑟 (A (𝐺 ′ ) ∈ 𝑅) Here, neighboring graphs 𝐺 and 𝐺 ′ share the same set of nodes but differ in one edge (i.e., the size of the symmetric difference of their edge sets is 1). The 𝜀 is referred to as the privacy budget as it governs the amount of random noise added to the 𝛼ˆdisc value.
Discrete Power-Law Distribution. Since node degrees are integers, the degree distribution of tail nodes follows a discrete power-law distribution with parameter 𝛼. The node degrees in the tail are independent and identically distributed according to a truncated discrete power-law distribution with probability mass function 𝑃 (𝑑 | 𝛼): 𝑍 (𝛼) =
𝑑∑︁ max
𝑑 −𝛼
𝛼 >0
2.2 Privacy Model
Power-Law Degree Distribution. The degree distribution of a graph 𝐺 is the probability distribution 𝑃 (𝑑) that a randomly selected node 𝑣 ∈ 𝑉 has degree 𝑑 𝑣 = 𝑑. Many real-world graphs are scale-free, with a small number of highly connected nodes and many low-degree nodes. A power-law degree distribution models scale-free graphs by 𝑃 (𝑑) ∝ 𝑑 −𝛼 for 𝑑 ≥ 𝑑 min , indicating the coexistence of a few highly connected nodes and many sparsely connected ones. Nodes with degrees 𝑑 𝑣 ≥ 𝑑 min are called tail nodes. The scaling parameter 𝛼 is a single parameter that governs the heaviness of the distribution’s right tail. It is typically below 3, with occasional exceptions [8]. Smaller values of 𝛼 correspond to heavier tails and a higher likelihood of extreme high-degree nodes, whereas larger values imply a more rapid decay and consequently a more homogeneous connectivity structure within the network.
𝑑 −𝛼 𝑍 (𝛼)
(3)
where the sufficient statistics for 𝛼 are the pair (𝑇 , 𝑁 ), since 𝑍 (𝛼) does not depend on observed 𝑑𝑖 . Therefore, the maximum likelihood estimator is: 𝛼ˆdisc = arg max ℓ (𝛼;𝑇 , 𝑁 ) = arg max −𝛼𝑇 − 𝑁 ln 𝑍 (𝛼) (4)
2.1 Power-Law Degree Distribution
𝑃 (𝑑 | 𝛼) =
𝑖=1
Í𝑁 With the aggregated statistic 𝑇 = 𝑖=1 ln 𝑑𝑖 , we can express the log-likelihood in terms of 𝑇 as follows:
Centralized and Local Edge-DP Models. Edge differential privacy can be realized under two models based on data visibility: the central model and the local model. In the centralized model, a trusted curator maintains the entire graph and applies a randomized algorithm to ensure that the presence or absence of any single edge cannot be inferred. This is suitable for traditional database scenarios like a curator-managed social network, where the entire graph is safely accessible.
(1)
𝑑=𝑑 min
2
Estimating Power-Law Exponent with Edge Differential Privacy
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
Algorithm 1 DP 𝛼ˆ CENTRAL via Discrete Approximation
However, a trusted curator of data store having access to the entire graph can become impractical in modern systems that rely on decentralized or federated architectures. In local edge differential privacy (LEDP) [10, 12, 15, 28, 31], each node retains ground truth to their associated data, and aggregations on the graphs are constructed using 𝜀-edge-DP queries to the nodes. Hence, the 𝛼ˆdisc computed under LEDP is based on the degree estimates that must be computed from individually perturbed edges.
Input: Graph 𝐺, Minimum Degree 𝑑 min , Maximum Degree 𝑑 max , Privacy Budget 𝜀 = 𝜀𝑡 + 𝜀𝑛 Output: DP Estimate of 𝛼 1: 𝐷 ′ = [𝑑 𝑣 : ∀𝑣 ∈ 𝐺 .𝑉 ∧ 𝑑 min ≤ 𝑑 𝑣 ≤ 𝑑 max ] Í 2: 𝑇𝑑𝑖𝑠𝑐 ← ln 𝑑 𝑑−0.5 min
𝑑 ∈𝐷 ′
3: 𝑇˜𝑑𝑖𝑠𝑐 ← 𝑇𝑑𝑖𝑠𝑐 + L AP (
𝑑 +1 2×𝑙𝑛 ( 𝑑min ) min
𝜀𝑡
)
4: 𝑁˜ ← |𝐷 ′ | + L AP ( 𝜀2 ) 𝑛
2.3 Our Goal
˜
5: return 1 + ˜ 𝑁
𝑇𝑑𝑖𝑠𝑐
Our goal is to design 𝜀-edge-DP algorithms that estimate the powerlaw scaling parameter of a graph 𝐺 over its fitted tail 𝐷 ′ while preserving high utility under privacy constraints. In the centralized model, the algorithm accesses the entire graph and produces a private estimate 𝛼ˆ CENTRAL . In the LEDP model, each node ensures 𝜀-edge-DP locally on its own edge-related information, and the reports are aggregated to produce private estimate 𝛼ˆ LOCAL .
When a node’s degree crosses from being below 𝑑 min to above 𝑑 min (or vice versa), then its contribution changes from 0 to 𝑑 min ln 𝑑min −0.5 . The absolute value of this quantity is also no larger +1 than ln 𝑑𝑑min when 𝑑 min ≥ 1. min +1 Therefore, the sensitivity of 𝑡 𝑣 (𝐺) is no larger than ln 𝑑𝑑min for min any node, and since a single edge affects at most two nodes, the total Í sensitivity of 𝑇disc = 𝑣 𝑡 𝑣 (𝐺) is bounded by: 𝑑 min + 1 Δ𝑇disc = max ′ |𝑇disc (𝐺) − 𝑇disc (𝐺 ′ )| ≤ 2 ln neighbors 𝐺,𝐺 𝑑 min □
3 Centralized Algorithms We develop two DP algorithms in centralized model to estimate scaling parameter 𝛼ˆ CENTRAL : one using discrete approximation and other via numerical optimization. Both algorithms first compute noisy statistics for 𝑇disc and 𝑁 as defined in Eq. 2 using Laplace mechanism. And then, we use these to compute 𝛼ˆ CENTRAL using two approaches (Section 3.2 and Section 3.3). To compute the noisy statistics using Laplace mechanism, we first analyze their sensitivities as described next.
The above 𝑑 min dependent bound on the global sensitivity of 𝑇disc is important because it remains small for all relevant choices of 𝑑 min . Even at the smallest value, 𝑑 min = 1, the sensitivity is only 2 ln 2 ≈ 1.386. As 𝑑 min increases, this bound decreases, so for a fixed privacy budget the released value 𝑇˜disc stays closer to the true statistic. The overall effect of 𝑑 min on final estimation accuracy, however, depends on additional factors and is evaluated in Section 5.
3.1 Sensitivity Analysis +1 Lemma 3.1. Global sensitivity of 𝑇disc is bounded by O ln( 𝑑𝑑min ) . min
Lemma 3.2. Global sensitivity of 𝑁 is at most 2.
P ROOF. Consider neighboring graphs 𝐺 and 𝐺 ′ that differ in exactly one edge (𝑢, 𝑤). Only degrees of 𝑢 and 𝑤 change across ′ be respectively the degrees of nodes these two graphs. Let 𝑑𝑢′ and 𝑑 𝑤 ′ ′ = 1. 𝑢 and 𝑤 in 𝐺 . Without loss of generality, 𝑑𝑢 −𝑑𝑢′ = 1 and 𝑑 𝑤 −𝑑 𝑤 Define the per-node contribution 𝑡 𝑣 (𝐺) as: ( 𝑑 (𝐺 ) 𝑣 ln 𝑑min 𝑑 𝑣 (𝐺) ≥ 𝑑 min −0.5 𝑡 𝑣 (𝐺) = 0 𝑑 𝑣 (𝐺) < 𝑑 min
P ROOF. Consider neighboring graphs 𝐺 and 𝐺 ′ that differ in exactly one edge. The only nodes that can have their tail membership changed are the endpoints of the edge. Each endpoint can either enter the tail (if previously out of the tail) or exit the tail (if previously in the tail). Since only two nodes are affected, the total change in the number of nodes in the tail is: Δ𝑁 =
The change in a node’s contribution will depend on whether its degree remains in the tail. If it does (i.e., 𝑑 𝑣 ≥ 𝑑 min and 𝑑 𝑣′ ≥ 𝑑 min ), then the change in the contribution is: 𝑑 𝑣′ 𝑑𝑣 𝑡 𝑣 (𝐺) − 𝑡 𝑣 (𝐺 ′ ) = ln − ln 𝑑 min − 0.5 𝑑 min − 0.5 𝑑𝑣 𝑑 +1 = ln ′ = ln 𝑑𝑣 𝑑
max
neighbors 𝐺,𝐺 ′
|𝑁 (𝐺) − 𝑁 (𝐺 ′ )| ≤ 2 □
3.2 𝛼ˆ CENTRAL via Discrete Approximation Using global sensitivities Δ𝑇disc and Δ𝑁 , the DP estimate 𝛼ˆ CENTRAL is computed using the Laplace mechanism [11]. Algorithm 1 computes 𝛼ˆ CENTRAL using the discrete approximation estimator from Eq. 2. Lines 1-2 compute 𝐷 ′ and 𝑇disc using node degrees. Lines 3-4 add Laplace noise proportional to the global sensitivities to compute noisy 𝑇˜disc and 𝑁˜ . The 𝜀 budget is split into 𝜀𝑡 and 𝜀𝑛 while adding Laplace noise for 𝑇˜disc and 𝑁˜ respectively. Finally, line 5 inserts the noisy estimates into Eq. 2 to obtain the DP estimate 𝛼ˆ CENTRAL ; by post-processing, this step has no privacy loss.
where 𝑑 is an arbitrary integer such that 𝑑 ≥ 𝑑 min . Because this expression is strictly decreasing in 𝑑, the largest possible difference will occur when 𝑑 = 𝑑 min : 𝑑 min + 1 |𝑡 𝑣 (𝐺) − 𝑡 𝑣 (𝐺 ′ )| ≤ ln 𝑑 min
Lemma 3.3. Using the Laplace Mechanism and Sequential Composition [11], 𝛼ˆ CENTRAL computed by Algorithm 1 is (𝜀𝑡 + 𝜀𝑛 )-edge differentially private.
When 𝑑 min = 1, this difference becomes ln 2. The difference de+1 creases as 𝑑 min grows, because 𝑑𝑑min decreases as 𝑑 min increases. min 3
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
Adam Tan, Mohamed Hefny, and Keval Vora
Algorithm 2 DP 𝛼ˆ CENTRAL via Numerical Optimization
graphs is often visible or reported), it can directly be used without adding noise. On the other hand, 𝑑 max is just a single scalar number, so its private estimation requires much less 𝜀 budget than that for the entire degree distribution. Furthermore for power-law distributions, setting 𝑑 max conservatively high enough (e.g., 𝑑 max = |𝑉 |) has very little impact on the MLE with no privacy cost.
Input: Graph 𝐺, Minimum Degree 𝑑 min , Maximum Degree 𝑑 max , Privacy Budget 𝜀 = 𝜀𝑡 + 𝜀𝑛 Output: DP Estimate of 𝛼 1: 𝐷 ′ = [𝑑 𝑣 : ∀𝑣 ∈ 𝐺 .𝑉 ∧ 𝑑 min ≤ 𝑑 𝑣 ≤ 𝑑 max ] Í 2: 𝑇𝑑𝑖𝑠𝑐 ← ln 𝑑 𝑑−0.5 𝑑 ∈𝐷 ′
min
3: 𝑇˜𝑑𝑖𝑠𝑐 ← 𝑇𝑑𝑖𝑠𝑐 + L AP (
𝑑 +1 2×𝑙𝑛 ( 𝑑min ) min
𝜀𝑡
4 Local Algorithms
)
4: 𝑁˜ ← |𝐷 ′ | + L AP ( 𝜀2 )
In the local model, each node perturbs its own information before releasing. Hence, the aggregator would never see the raw node degrees, and instead operate on noisy per-node statistics produced by local DP mechanisms. We explore two approaches in this model, both with Laplace mechanism. The first approach computes LEDP degrees and uses them for 𝛼ˆ LOCAL estimation. The second approach is consistent with the central model; here, each node releases the noisy log-function statistic required to compute 𝑇˜disc . These approaches result in four algorithms depending on the use of closed form discrete approximation versus numerical optimization using noisy statistics.
𝑛
5: return argmax L OG L IKELIHOOD (𝑇˜𝑑𝑖𝑠𝑐 , 𝑁˜ , 𝑑 min , 𝑑 max , 𝛼 )
⊲ Algo. 3
𝛼 >0
Algorithm 3 Log-likelihood score Input: 𝑇disc , 𝑁 , Minimum Degree 𝑑 min , Maximum Degree 𝑑 max , Alpha 𝛼 Output: Log-Likelihood score for 𝛼 𝑑Í max 1: 𝑍 ← 𝑑 −𝛼 𝑑=𝑑 min
2: if 𝑍 ≤ 0 then 3: return −∞ 4: end if 5: 𝑆 ← 𝑇disc + 𝑁 × 𝑙𝑛 (𝑑 min − 0.5) 6: return −𝛼 × 𝑆 − 𝑁 × 𝑙𝑛 (𝑍 )
Approach 1: Release Degree Statistic. LEDP degree is computed with each node releasing its noisy degree [31]. Hence, the contribution from each node 𝑣 is simply its DP degree estimate 𝑑˜𝑣 . Hence, 𝑇˜disc and 𝑁˜ are defined as: ! ∑︁ ∑︁ 𝑑˜𝑣 ˜ 𝑇disc = ln 𝑁˜ = 1 (6) 𝑑 − 0.5
3.3 𝛼ˆ CENTRAL via Numerical Optimization Instead of the above closed-form estimation, we can estimate 𝛼ˆ CENTRAL by numerically optimizing the discrete log-likelihood. The key idea is to reuse the same noisy 𝑇˜disc and 𝑁˜ estimates, as described next. From the definition of 𝑇disc in Eq. 2: ∑︁ 𝑁 𝑁 ∑︁ 𝑑𝑖 = ln 𝑑𝑖 − 𝑁 ln(𝑑 min − 0.5) 𝑇disc = ln 𝑑 min − 0.5 𝑖=1 𝑖=1 Therefore,
𝑁 ∑︁
𝑑˜𝑣 ≥𝑑 min
min
𝑑˜𝑣 ≥𝑑 min
Approach 2: Release Log Statistic. Here, the contribution from each node 𝑣 is modeled as 𝑐˜𝑣 : 𝑑𝑣 e ln 𝑑˜𝑣 ≥ 𝑑 min 𝑑 min − 0.5 𝑐˜𝑣 = (7) 0 𝑑˜𝑣 < 𝑑 min 𝑑𝑣 e where 𝑑˜𝑣 is the DP estimate of 𝑑 𝑣 , and ln 𝑑 min −0.5 denotes the DP estimate of ln 𝑑min𝑑 𝑣−0.5 . Hence, 𝑇˜disc and 𝑁˜ are defined as: ∑︁ ∑︁ 𝑐˜𝑣 1 𝑇˜disc = 𝑁˜ = (8) 𝑑 min 𝑣
ln 𝑑𝑖 = 𝑇disc + 𝑁 ln(𝑑 min − 0.5)
𝑖=1
Hence, we can compute the DP estimate of this sum using the noisy statistics 𝑇˜disc and 𝑁˜ : ∑︁ (5) ln 𝑑𝑖 = 𝑇˜disc + 𝑁˜ ln(𝑑 min − 0.5)
𝑐˜𝑣 ≥ ln 𝑑 −0.5 min
Hence, based on Eq. 4, our central DP MLE is:
4.1 Sensitivity Analysis
h ∑︁ i 𝛼ˆ CENTRAL = arg max −𝛼 ln 𝑑𝑖 − 𝑁˜ ln 𝑍 (𝛼)
We analyze the global sensitivity of the degree statistic and log statistic to guide the Laplace noise addition.
𝛼 >0
Algorithm 2 computes 𝛼ˆ CENTRAL by maximizing this DP loglikelihood objective. The computation of noisy statistics 𝑇˜disc and 𝑁˜ in lines 1-4 is same as in that in the previous algorithm, using Laplace noise with split budgets. In our experiments, we set 𝜀𝑡 = 𝜀𝑛 = 𝜀/2 for simplicity. Using these DP estimates, MLE is numerically computed as post-processing step on line 5, with the log-likelihood computation shown in Algorithm 3.
Lemma 4.1. Global sensitivity of node degree is 1. P ROOF. Adding or removing one edge can only change the degree of the endpoints of that edge by 1. □ Lemma 4.2. Global sensitivity of log statistic from Eq. 7 is at most +1 ln( 𝑑𝑑min ). min
Lemma 3.4. Using the Laplace Mechanism and Sequential Composition [11], 𝛼ˆ CENTRAL computed by Algorithm 2 is (𝜀𝑡 + 𝜀𝑛 )-edge differentially private.
P ROOF. The proof follows a similar argument to that for Lemma 3.1 proof. Consider neighboring graphs 𝐺 and 𝐺 ′ that differ in exactly one edge (𝑢, 𝑤). Only degrees of 𝑢 and 𝑤 change ′ be respectively the degrees across these two graphs. Let 𝑑𝑢′ and 𝑑 𝑤 ′ of nodes 𝑢 and 𝑤 in 𝐺 . Without loss of generality, 𝑑𝑢 − 𝑑𝑢′ = 1 and ′ = 1. 𝑑𝑤 − 𝑑𝑤
Discussion. The normalization constant 𝑍 (𝛼) needs to know 𝑑 max . In practice, if the maximum degree of the graph is known or can be assumed to be public knowledge (e.g., maximum degree in social 4
Estimating Power-Law Exponent with Edge Differential Privacy
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
Algorithm 4 DP 𝛼ˆ LOCAL via Degree Release
Algorithm 5 DP 𝛼ˆ LOCAL via Log Statistic Release
Input: Graph 𝐺, Minimum Degree 𝑑 min , Maximum Degree 𝑑 max , Privacy Budget 𝜀 Output: DP Estimate of 𝛼 /* Step 1: Release local degree statistic */ 1: for each 𝑣 ∈ 𝐺 .𝑉 do 2: 𝑑˜𝑣 ← 𝑑 𝑣 + 𝐿𝑎𝑝 ( 𝜀2 ) ⊲ 𝜀2 budget split 3: R ELEASE 𝑑˜𝑣
Input: Graph 𝐺, Minimum Degree 𝑑 min , Maximum Degree 𝑑 max , Privacy Budget 𝜀 Output: DP Estimate of 𝛼 /* Step 1: Release local log statistic */ 1: for each 𝑣 ∈ 𝐺 .𝑉 do 𝑐˜𝑣 ← ln( 𝑑 𝑑 𝑣−0.5 ) + 𝐿𝑎𝑝 ( min 3: R ELEASE 𝑐˜𝑣 4: end for 2:
4: end for
/* Step 2: Aggregate local statistics */
𝑑 +1 2×ln( 𝑑min ) min
𝜀
)
⊲ 𝜀2 budget split
/* Step 2: Aggregate local statistics */
5: 𝑇˜disc ← 0; 𝑁˜ ← 0 6: for 𝑣 ∈ 𝐺 .𝑉 do 7: 𝑑˜ ← D EGREE S TATISTIC (𝑣) 8: if 𝑑˜ ≥ 𝑑 min then
5: 𝑇˜disc ← 0; 𝑁˜ ← 0 6: for 𝑣 ∈ 𝐺 .𝑉 do 7: 𝑐˜ ← L OG S TATISTIC (𝑣) 𝑑
if 𝑐˜ ≥ ln( 𝑑 min ) then min −0.5 9: 𝑇˜disc ← 𝑇˜disc + 𝑐˜ 10: 𝑁˜ ← 𝑁˜ + 1 11: end if 12: end for 8:
˜ 𝑇˜disc ← 𝑇˜disc + ln( 𝑑 𝑑−0.5 ) min 10: 𝑁˜ ← 𝑁˜ + 1 11: end if 12: end for
9:
/* Step 3: Estimate 𝛼 */ /* Option A: Discrete Approximation */ ˜ 13: 𝛼ˆ LOCAL ← 1 + ˜𝑁 𝑇disc /* Option B: Numerical Optimization */ 14: 𝛼ˆ LOCAL ← argmax L OG L IKELIHOOD (𝑇˜disc , 𝑁˜ , 𝑑 min , 𝑑 max , 𝛼 )
/* Step 3: Estimate 𝛼 */ /* Option A: Discrete Approximation */ ˜ 13: 𝛼ˆ LOCAL ← 1 + ˜𝑁 𝑇disc /* Option B: Numerical Optimization */ 14: 𝛼ˆ LOCAL ← argmax L OG L IKELIHOOD (𝑇˜disc , 𝑁˜ , 𝑑 min , 𝑑 max , 𝛼 )
𝛼 >0
𝛼 >0
15: return 𝛼ˆ LOCAL
15: return 𝛼ˆ LOCAL
The change in a node’s contribution 𝑐 𝑣 will depend on whether its degree remains in the tail. If it does (i.e., 𝑑 𝑣 ≥ 𝑑 min and 𝑑 𝑣′ ≥ 𝑑 min ), then the change in the contribution is: 𝑑 𝑣′ 𝑑𝑣 ′ 𝑐 𝑣 (𝐺) − 𝑐 𝑣 (𝐺 ) = ln − ln 𝑑 min − 0.5 𝑑 min − 0.5 𝑑𝑣 𝑑 +1 = ln ′ = ln 𝑑𝑣 𝑑
proportional to sensitivity 1. The 𝜀 privacy budget is divided by 2 as each edge is used twice to compute the degree estimates of its two endpoints. The second step (lines 5-12) aggregates the local releases to compute noisy statistics 𝑇˜𝑑𝑖𝑠𝑐 and 𝑁˜ as defined in Eq. 6. This aggregation is post-processing using the DP degree estimates and has no privacy loss. Finally, these noisy statistics are used to estimate 𝛼ˆ LOCAL in step 3. This results in the following two options. Option A: 𝛼ˆ LOCAL via Discrete Approximation. As shown on line 13, the noisy estimates are plugged into Eq. 2 for discrete approximation of the DP estimate 𝛼ˆ LOCAL . Option B: 𝛼ˆ LOCAL via Numerical Optimization. Numerical optimization is performed using noisy 𝑇˜𝑑𝑖𝑠𝑐 and 𝑁˜ based on the same analysis for Eq. 5. Our local DP MLE is: h ∑︁ i 𝛼ˆ LOCAL = arg max −𝛼 ln 𝑑𝑖 − 𝑁˜ ln 𝑍 (𝛼) (9)
where 𝑑 is an arbitrary integer such that 𝑑 ≥ 𝑑 min . Because this expression is strictly decreasing in 𝑑, the largest possible difference will occur when 𝑑 = 𝑑 min : 𝑑 min + 1 |𝑐 𝑣 (𝐺) − 𝑐 𝑣 (𝐺 ′ )| ≤ ln 𝑑 min When 𝑑 min = 1, this difference becomes ln 2. The difference decreases as 𝑑 min grows, because the logarithm function is monotonically increasing. When a node’s degree crosses from being below 𝑑 min to above 𝑑 min (or vice versa), then its contribution changes from 0 to 𝑑 min ln 𝑑min −0.5 . The absolute value of this quantity is also no larger +1 than ln 𝑑𝑑min when 𝑑 min ≥ 1. min +1 Thus in all cases the sensitivity of 𝑐 𝑣 is at most ln 𝑑𝑑min . □ min
𝛼 >0
which is shown on line 14 in Algorithm 4. Lemma 4.3. Using the Laplace Mechanism and Sequential Composition [11], 𝛼ˆ LOCAL computed by Algorithm 4 is 𝜀-edge differentially private.
4.3 𝛼ˆ LOCAL via Log Statistic Release Algorithm 5 shows the LEDP computation for 𝛼ˆ LOCAL using Laplace mechanism for log statistic release. In the first step (lines 1-4), each node releases its DP estimate of the log statistic using Laplace noise +1 proportional to global sensitivity ln( 𝑑𝑑min ) with the privacy budget min split between two edge endpoints. The second step (lines 5-12) aggregates local contributions as post-processing to compute noisy statistics 𝑇˜𝑑𝑖𝑠𝑐 and 𝑁˜ as defined in Eq. 8. These noisy statistics are used to estimate 𝛼ˆ LOCAL in step 3, resulting in following two options.
The global sensitivity of 𝑐 𝑣 benefits from the similar 𝑑 min -dependent bound as in the central model.
4.2 𝛼ˆ LOCAL via Degree Release Algorithm 4 shows the LEDP computation for 𝛼ˆ LOCAL using Laplace mechanism for degree release. In the first step (lines 1-4), each node releases its DP degree estimate 𝑑˜𝑣 computed using Laplace noise 5
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
Adam Tan, Mohamed Hefny, and Keval Vora
Table 2: Graph datasets & their power-law scaling parameter 𝛼. Graph
Nodes
Edges
wiki enron brightkite ego-twitter gplus stanford syn-power-0 syn-power-1 syn-power-2
7,115 36,692 58,228 81,306 107,614 281,903 100,000 100,000 100,000
100,761 183,830 214,078 1,342,296 12,238,285 1,992,635 1,477,208 4,010,327 997,299
Table 4: Summary for centralized model. Mean 𝑙 1 is averaged over all runs and datasets, max 𝑙 1 is the worst case, and std. range gives the per-dataset standard deviation range over 20 runs. Bold marks the lowest mean and max for each 𝑑 min .
Power-law 𝛼 𝑑 min = 1 𝑑 min = 3 1.176 1.494 1.551 1.187 1.126 1.459 2.000 2.500 3.000
1.474 1.918 1.982 1.372 1.222 2.218 2.000 2.500 3.000
Option A: 𝛼ˆ LOCAL via Discrete Approximation. Eq. 2 is used for discrete approximation of the DP estimate 𝛼ˆ LOCAL using the noisy estimates (line 13 in Algorithm 5). Option B: 𝛼ˆ LOCAL via Numerical Optimization. Numerical optimization is performed (line 14 in Algorithm 5) using noisy 𝑇˜𝑑𝑖𝑠𝑐 and 𝑁˜ for local DP MLE defined in Eq. 9. Lemma 4.4. Using the Laplace Mechanism and Sequential Composition [11], 𝛼ˆ LOCAL computed by Algorithm 5 is 𝜀-edge differentially private.
Method
Mean 𝑙 1 (%)
BASE DA NO
15.88 9.57 0.0049
BASE DA NO
21.79 5.28 0.0066
wiki enron brightkite ego-twitter gplus stanford syn-power-0 syn-power-1 syn-power-2
Max 𝑙 1 (%) 𝑑 min = 1 76.70 17.69 0.0989 𝑑 min = 3 89.80 9.47 0.1115
BASE
10 6
10 4 10 2 l1 Error
DA
100
Release
Estimator
– – Degree Log-Statistic Degree Log-Statistic
Discrete Approx. Numerical Opt. Discrete Approx. Discrete Approx. Numerical Opt. Numerical Opt.
100
(b) 𝑑 min = 3
5.1 Centralized Algorithms To answer RQ1 for 𝛼ˆ CENTRAL estimates, we compare DA and NO with BASE. Figure 1 and Table 4 summarize the results. Detailed results are available in Table 6 in Appendix A. NO is the strongest central method. Its mean 𝑙 1 error is roughly three orders of magnitude lower than DA at both 𝑑 min = 1 and 𝑑 min = 3, and its worst-case error is about two orders of magnitude lower. This advantage holds on every individual dataset (Table 6). On average, DA is more accurate than BASE, at both 𝑑 min values, though BASE outperforms DA on the three synthetic power-law datasets at 𝑑 min = 1. The gap between NO and DA is because DA uses a closed-form approximation of 𝛼, while NO optimizes the exact discrete log-likelihood.
Table 3: Algorithm labels used in the evaluation. Model
10 4 10 2 l1 Error
Methodology. We set 𝜀 privacy budget to 1.0 for our experiments. We also conducted experiments where the 𝜀 value is varied between 0.1 and 5 to study performance across different privacy budgets. We report results for 𝑑 min values of 1 and 3; while we also considered with 𝑑 min values 5 and 10, the non-private MLE of 𝛼 was outside of the [0, ∞] range which is semantically invalid. For accuracy metric, we measure the 𝑙 1 error compared to the non-private 𝛼 parameter of each dataset. Each experiment was repeated 20 times and we report the mean and standard deviation.
Datasets. We test our algorithms on 9 graph datasets: 6 publiclyavailable datasets from SNAP [21] and 3 synthetic datasets. Table 2
Centralized Centralized Local Local Local Local
10 6
summarizes the datasets. The power-law scaling parameter 𝛼 values are mostly below 3 for 𝑑 min between 1 and 3; this is consistent with previous observations [8] where 𝛼 is typically below 3. The synthetic datasets are generated using I NC -P OWERLAW generator [2] that produces a simple random graph conforming with a degree sequence corresponding to the given scaling parameter 𝛼.
Algorithms. With different combinations for estimation methods (discrete approximation versus numerical optimization) and local statistic release (degree versus log statistic), we evaluate the centralized edge DP and LEDP algorithms listed in Table 3. We compare against the 𝜀-edge-DP degree distribution based power-law fitting approach from Hay et al. [13] which is developed for central model. This is called BASE.
DA NO DA/DR DA/LR NO/DR NO/LR
6.962–16.850 0.00111–0.02877 0.00079–0.03200
Figure 1: Performance of centralized DP algorithms. 𝑙 1 errors of NO, DA, and BASE.
In this section, we evaluate the accuracy of our 𝜀-edge-DP 𝛼 estimation algorithms and answer the following research questions: RQ1. Does adding noise directly to sub-components of 𝛼 estimator provide better estimates compared to the degree distribution based power-law fitting? RQ2. How does the accuracy compare for numerical optimization using noisy estimates instead of directly using the closed form discrete approximation? RQ3. Does degree release based approach in local model provide higher accuracy compared to solutions based on local log statistic release? RQ4. How does the choice of 𝑑 min affect the accuracy and stability of private 𝛼 estimation?
Label
5.249–16.443 0.00063–0.01459 0.00075–0.02512
NO
(a) 𝑑 min = 1
5 Experimental Evaluation
Std. range
Reference Algorithm 1 Algorithm 2 Algorithm 4 (A) Algorithm 5 (A) Algorithm 4 (B) Algorithm 5 (B) 6
Estimating Power-Law Exponent with Edge Differential Privacy
wiki enron brightkite ego-twitter gplus stanford syn-power-0 syn-power-1 syn-power-2
NO/LR
10 3
DA/LR
10 2 l1 Error
NO/DR
10 1
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
DA/DR
10 3
(a) 𝑑 min = 1
10 2 l1 Error
Table 5: Summary for local model. Mean 𝑙 1 is averaged over all runs and datasets, max 𝑙 1 is the worst case, and std. range gives the per-dataset standard deviation range over 20 runs. Bold marks the lowest mean and max for each 𝑑 min .
10 1
(b) 𝑑 min = 3
Figure 2: Performance of local DP algorithms. 𝑙 1 errors across different combinations for MLE (discrete approximation versus numerical optimization) and local statistic release (degree versus log statistic). Increasing 𝑑 min worsens performance for BASE on every dataset and for NO on most datasets; DA, in contrast, improves at 𝑑 min = 3 on every dataset.
Mean 𝑙 1 (%)
DA/LR DA/DR NO/LR NO/DR
8.72 9.14 6.26 1.03
DA/LR DA/DR NO/LR NO/DR
4.61 5.94 3.06 1.63
Max 𝑙 1 (%) 𝑑 min = 1 16.27 17.76 11.93 3.31 𝑑 min = 3 8.88 9.62 7.21 7.91
Std. range 0.01644–0.10478 0.00295–1.07710 0.03661–0.30503 0.00817–0.18210 0.01388–0.12399 0.00528–0.85213 0.02496–0.22257 0.00927–0.99561
Figure 4b (local, 𝑑 min = 1) shows that local error decreases overall as 𝜀 increases. The direct estimation helps the degree-release family across the full 𝜀 range, while in the log-statistic family the two estimators are close and trade places across 𝜀, overall, DA/DR is the lowest error local method at every 𝜀 value shown. At smaller 𝜀, both degree-release variants (NO/DR, DA/DR) sit below the log-statistic release variants (NO/LR, DA/LR), this advantage narrows with larger 𝜀 and NO/DR rises above the log-statistic curves at 𝜀 = 5. DA/DR, however, remains the best local option throughout. Finally, comparing across the two models, the same pattern as Figure 3 holds: central curves are less sensitive to 𝜀, while local curves improve as 𝜀 increases. In absolute error, central variants remain below all local variants across the full range.
5.2 Local Algorithms To answer RQ2 and RQ3 for 𝛼ˆ LOCAL estimates, we compare NO/LR, DA/LR, NO/DR and DA/DR. Figure 2 and Table 5 summarize the results. Detailed results are available in Table 7 in Appendix A. NO/DR is the strongest local variant overall. Mean 𝑙 1 error follows NO/DR < NO/LR < DA/LR < DA/DR at both 𝑑 min = 1 and 𝑑 min = 3 (Table 5), and NO/DR has the lowest per-dataset error on 6 of 9 datasets at each 𝑑 min (Table 7). Release mode interacts with the estimator: NO prefers degree release, while DA prefers log-statistic release, on most datasets at both 𝑑 min values. All four local variants have lower worst-case error than BASE. Increasing 𝑑 min helps all local variants except NO/DR; at 𝑑 min = 3, DA/LR improves on 8 of 9 datasets, NO/LR on 7 of 9, and DA/DR on 6 of 9, while NO/DR worsens on 7 of 9 (Table 7).
Ego-twitter. Figure 5a (central, 𝑑 min = 1) shows a similar trend as previous datasets. Figure 5b (local, 𝑑 min = 1) shows a stronger dependence on 𝜀, with all local curves decreasing as privacy budget increases. Within the degree-release family, NO/DR has lower error than DA/DR at every 𝜀. Within the log-statistic release family, NO/LR has no valid estimate at 𝜀 = 0.1 because all runs hit the 𝛼ˆ < 0 clamp, but for 𝜀 ≥ 0.3 it is consistently lower error than DA/LR. Overall, NO/DR is the lowest-error local method at every 𝜀 value shown, and by 𝜀 ≥ 1 both numerical-optimization variants outperform their discrete-approximation counterparts. Finally, comparing across two models, the same pattern as previous datasets holds: central curves are less sensitive to 𝜀, while local curves improve overall as 𝜀 increases. In absolute error, central NO remains below all reported local estimates across the entire range.
5.3 Sensitivity to Privacy Budget We analyze how 𝑙 1 error changes with privacy budget 𝜀 at fixed 𝑑 min = 1. Figure 3, Figure 4, and Figure 5 show results for three datasets. Detailed 𝑙 1 values are available in Table 8 in Appendix A. Syn-power-1. Figure 3a (central, 𝑑 min = 1) shows a nearly flat trend for mean 𝑙 1 error across varying 𝜀, with both central variants changing very little as privacy budget increases. In this dataset, NO has far lower error than DA at every 𝜀. DA stays nearly same throughout while NO drops as 𝜀 increases. Figure 3b (local, 𝑑 min = 1) shows all four local curves decreasing as 𝜀 increases. Within the log-statistic release family, DA/LR is better at low privacy budgets (𝜀 ≤ 0.5), but NO/LR becomes better for 𝜀 ≥ 1. Within the degree-release family, DA/DR is slightly better at 𝜀 = 0.1, while NO/DR has lower error for 𝜀 ≥ 0.3. Overall, degree-release variants (NO/DR, DA/DR) remain below logstatistic-release variants (NO/LR, DA/LR), and the best local accuracy is obtained by NO/DR. Comparing across the two models, central variants are less sensitive to 𝜀, while local variants benefit more from larger 𝜀. In absolute error, central NO is below all local variants across the plotted range. Brightkite. Figure 4a (central, 𝑑 min = 1) shows a nearly flat trend as 𝜀 increases from 0.1 to 5, with small variation across the full range. In this dataset, NO has far lower error than DA at every 𝜀.
Method
5.4 Summary of Findings Across all datasets, privacy budgets, and both privacy models, we highlight four overall observations. Observation 1: Direct Sub-Component Privatization Outperforms Degree-Distribution Fitting. To answer RQ1, our results show that adding noise directly to the 𝛼-estimator sub-components is consistently better than degree-distribution based fitting. In the centralized setting, NO achieves lower error and better stability than BASE on every dataset, and DA does so in aggregate mean and on all real-world networks. The main reason is that our method perturbs 7
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
5.0
(a) Centralized.
2.0
(b) Local.
Figure 3: Syn-power-1: 𝑙 1 vs 𝜀.
5.0
DA/LR
0.49 0.42 0.36 0.29 0.22 0.16 0.1
NO/DR
5.0
(a) Centralized.
2.0
(b) Local.
Figure 4: Brightkite: 𝑙 1 vs 𝜀.
only low-dimensional sufficient statistics (𝑇disc, 𝑁 ), while degreedistribution based fitting injects noise into many histogram bins and can distort the tail used to estimate 𝛼.
DA/DR
0.000249 0.000127 0.000004 0.110201 0.110181 0.1101610.1 2.0
5.0
1.17 0.94 0.70 0.47 0.23 0.00 0.1
l1 Error
Local: NO/LR
0.000401 0.000203 0.000005 0.026015 0.025946 0.0258770.1 2.0
l1 Error
DA
l1 Error
l1 Error
0.09 0.07 0.06 0.05 0.04 0.02 0.1
l1 Error
Centralized: NO
l1 Error
0.000168 0.000086 0.000004 0.144331 0.144328 0.1443240.1 2.0
Adam Tan, Mohamed Hefny, and Keval Vora
5.0
(a) Centralized.
2.0
5.0
(b) Local.
Figure 5: Ego-twitter: 𝑙 1 vs 𝜀.
(or a synthetic graph) [23, 31, 38, 40–42], whereas the second style is releasing DP estimations for specific graph queries [6, 10, 14– 16, 19, 20, 28]. Our work relates follows the second style where we aim to release only the private estimate of a single parameter 𝛼.
Observation 2: Numerical Optimization is More Accurate Than Direct Approximation Under DP Noise. To answer RQ2, NO has lower 𝑙 1 error than DA in both models. In the centralized model, NO’s mean 𝑙 1 error is more than two orders of magnitude lower than that of DA on every dataset, and nearly three orders of magnitude lower on aggregate (Table 6). In the local model, NO/DR is far lower than DA/DR, and NO/LR is lower than DA/LR on average (Table 5). The difference in accuracy is because DA uses a closed-form approximation of 𝛼, while NO optimizes the exact discrete log-likelihood.
Differentially Private Likelihood Optimization. Many likelihoodbased estimators can be written as an optimization problem, e.g., 𝜃ˆ = arg max𝜃 ℓ (𝜃 ; 𝐷). There are ways to make such estimators private in the central DP model. One approach is to privatize the optimization itself, for example by perturbing the objective or by adding noise to the optimizer before release [5]. Another way is the McSherry-Talwar selection mechanism 𝐸𝑞𝜀 [26] which is used to select one output from candidates with quality scores (e.g., loglikelihood). 𝐸𝑞𝜀 samples probabilistically, favoring higher-quality candidates, and providing differential privacy while selecting nearoptimal outputs. More generally, DP M-Estimators can be computed by noisy iterative methods (e.g., adding noise to gradients or Newton steps) that approximately solve the same estimation problem [3]. These DP ideas are relevant here because 𝛼 is defined through a likelihood maximization problem, and our approach is to privately release only the few summary numbers for the estimation.
Observation 3: In Local DP, Degree Release Helps Numerical Optimization but Log-Statistic Release Helps Direct Approximation. To answer RQ3, the effect of release mode depends on the estimator family. NO/DR has lower mean 𝑙 1 error than NO/LR on most datasets, while DA/LR has lower mean 𝑙 1 error than DA/DR on most datasets (Table 7). Observation 4: Effect of 𝑑 min is Method-Dependent. To answer RQ4, the effect of increasing 𝑑 min from 1 to 3 is method-dependent. In the centralized setting, DA improves on every dataset, while NO worsens on most (Table 6). In the local setting, DA/LR, DA/DR, and NO/LR improve on most datasets, while NO/DR worsens on most (Table 7). The preferred 𝑑 min therefore depends on which estimator is used.
7 Conclusion and Future Work We proposed methods to estimate the power-law exponent 𝛼 of a graph’s degree distribution under edge differential privacy. Our approach privatizes only the small set of sufficient statistics needed for the estimation, aiming to reduce tail distortion and error. We developed both centralized and local edge-DP algorithms with discreteapproximation and numerical-optimization variants, and our experiments showed our direct sufficient-statistic privatization approach is more accurate and stable than histogram-based fitting.
6 Related Work Differentially Private Degree Distribution Release. A common approach for privately estimating 𝛼 is to fit a power-law model to the privatized degree distribution histogram. Hay et al. [13] propose an efficient edge-DP method for releasing the degree distribution and show the fitting power-law estimate. Similarly, works like [13, 14, 32, 37, 38] develop edge-DP degree distribution techniques. DP degree distribution release has also been studied under node-DP [9, 14, 24, 25, 34]. Compared to DP degree distribution use for 𝛼 estimation, we approach the problem by adding noise only to the few statistics used for 𝛼 estimation, hence avoiding inaccuracies from binning/smoothing/projection for noisy degree histograms.
Interesting directions for future work remain, as discussed next. Randomized-Response Tail Counts. Randomized response [18] is a local DP method for estimating counts of binary attributes. In our setÍ ting, it could be used to estimate the tail size 𝑁 = 𝑣 1{𝑑 𝑣 ≥ 𝑑 min } by having each node privatize and send only the 1-bit tailmembership indicator, rather than sending noisy degrees and estimating 𝑁 by thresholding the noisy values. Friendship-Paradox Sampling under LDP. Although our current estimators assume one privatized report per node, an open direction is to study settings with partial participation or limited communication. Friendship-paradox sampling [29] provides an alternative way to obtain degree observations that over-represent high-degree nodes, integrating this with LDP would require designing a protocol that collects the necessary neighbor-sampled degree information privately and understanding the privacy/utility tradeoff.
Differentially Private Graph Algorithms. Beyond private degree distribution, several DP graph algorithms have been developed. They broadly fall into two styles covering both centralized and local models. The first style involves publishing private version of the graph 8
Estimating Power-Law Exponent with Edge Differential Privacy
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
Acknowledgements
[21] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data, June 2014. [22] Ye Li, Leong Hou U, Man Lung Yiu, and Ngai Meng Kou. An Experimental Study on Hub Labeling Based Shortest Path Algorithms. Proceedings of the VLDB Endowment, 11(4):445–457, 2017. [23] Zhetao Li, Yong Xiao, Haolin Liu, Xiaofei Liao, Ye Yuan, and Junzhao Du. Dynamic Graph Publication With Differential Privacy Guarantees for Decentralized Applications. IEEE Transactions on Computers, 74(5):1771–1785, 2025. [24] Ganghong Liu, Xuebin Ma, and Wuyungerile Li. Publishing Node Strength Distribution With Node Differential Privacy. IEEE Access, 8:217642–217650, 2020. [25] Shang Liu, Yang Cao, Takao Murakami, and Masatoshi Yoshikawa. A CryptoAssisted Approach for Publishing Graph Statistics with Node Local Differential Privacy. In IEEE International Conference on Big Data (Big Data), Osaka, Japan, December 17–20, 2022, pages 5765–5774, 2022. [26] Frank McSherry and Kunal Talwar. Mechanism Design via Differential Privacy. In Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, October 2007. [27] Michael Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet mathematics, 1(2):226–251, 2004. [28] Pranay Mundra, Charalampos Papamanthou, Julian Shun, and Quanquan C Liu. Practical and Accurate Local Edge Differentially Private Graph Algorithms. Proceedings of the VLDB Endowment, 18(11):4199–4213, 2025. [29] Buddhika Nettasinghe and Vikram Krishnamurthy. Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox-based Sampling. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(6), May 2021. [30] M. E. J. Newman. Power Laws, Pareto Distributions and Zipf’s Law. Contemporary Physics, 46(5):323–351, 2005. [31] Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating Synthetic Decentralized Social Graphs with Local Differential Privacy. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 425–438, 2017. [32] Jenni Reuben. Towards a Differential Privacy Theory for Edge-Labeled Directed Graphs. In SICHERHEIT 2018, pages 273–278. Gesellschaft für Informatik e.V., Bonn, 2018. [33] Wai Teng Tang, Ruizhe Zhao, Mian Lu, Yun Liang, Huynh Phung Huyng, Xibai Li, and Rick Siow Mong Goh. Optimizing and Auto-tuning Scale-free Sparse Matrix-vector Multiplication on Intel Xeon Phi. In IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 136–145. IEEE, 2015. [34] Jonathan Ullman and Adam Sealfon. Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. [35] Keval Vora. Lumos: Dependency-Driven Disk-based Graph Processing. In USENIX Annual Technical Conference (USENIX ATC 19), pages 429–442, 2019. [36] Songlei Wang, Yifeng Zheng, Xiaohua Jia, and Haibo Hu. PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs. Proceedings of the VLDB Endowment, 18(11):4682–4694, July 2025. [37] Yue Wang and Xintao Wu. Preserving Differential Privacy in Degree-Correlation based Graph Generation. Transactions on Data Privacy, 6(2):127–145, August 2013. [38] Chengkun Wei, Shouling Ji, Changchang Liu, Wenzhi Chen, and Ting Wang. AsgLDP: Collecting and Generating Decentralized Attributed Graphs With Local Differential Privacy. IEEE Transactions on Information Forensics and Security, 15:3239–3254, 2020. [39] Minze Xu, Zhentai Xie, Zhibin Wang, Guangzhan Wang, Longbin Lai, Yuan Zhang, Chen Tian, and Sheng Zhong. Sectric: Towards Accurate, PrivacyPreserving and Efficient Triangle Counting. Proceedings of the VLDB Endowment, 18(10):3382–3395, June 2025. [40] Quan Yuan, Zhikun Zhang, Linkang Du, Min Chen, Peng Cheng, and Mingyang Sun. PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information. In 32nd USENIX Security Symposium (USENIX Security 23), pages 3241–3258, 2023. [41] Sen Zhang, Haibo Hu, Qingqing Ye, and Jianliang Xu. PrivDPR: Synthetic Graph Publishing with Deep PageRank under Differential Privacy. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1, KDD ’25, page 1936–1947, 2025. [42] Yuxuan Zhang, Jianghong Wei, Xiaojian Zhang, Xuexian Hu, and Wenfen Liu. A Two-Phase Algorithm for Generating Synthetic Graph Under Local Differential Privacy. In Proceedings of the 8th International Conference on Communication and Network Security, ICCNS ’18, page 84–89, 2018.
This work is supported by the National Cybersecurity Consortium and the Natural Sciences and Engineering Research Council of Canada.
References [1] Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast Exact Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’13, page 349–360, 2013. [2] Daniel Allendorf, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Nick Wormald. Engineering Uniform Sampling of Graphs with a Prescribed Powerlaw Degree Sequence. In 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 27–40. SIAM, 2022. [3] Marco Avella-Medina, Casey Bradshaw, and Po-Ling Loh. Differentially Private Inference via Noisy Optimization. The Annals of Statistics, 51(5):2067 – 2092, 2023. [4] Heiko Bauke. Parameter Estimation for Power-law Distributions by Maximum Likelihood Methods. The European Physical Journal B, 58(2):167–173, July 2007. [5] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially Private Empirical Risk Minimization. Journal of Machine Learning Research, 12(29):1069–1109, 2011. [6] Shixi Chen and Shuigeng Zhou. Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’13, page 653–664, 2013. [7] Fan Chung and Linyuan Lu. Connected Components in Random Graphs with Given Expected Degree Sequences. Annals of combinatorics, 6(2):125–145, 2002. [8] Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-Law Distributions in Empirical Data. SIAM Review, 51(4):661–703, November 2009. [9] Wei-Yen Day, Ninghui Li, and Min Lyu. Publishing Graph Degree Distribution with Node Differential Privacy. In Proceedings of the International Conference on Management of Data, SIGMOD ’16, page 123–138, 2016. [10] Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. In IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 754–765, 2022. [11] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, August 2014. [12] Talya Eden, Quanquan C Liu, Sofya Raskhodnikova, and Adam Smith. Triangle Counting with Local Edge Differential Privacy. Random Structures & Algorithms, 66(4):e70002, 2025. [13] Michael Hay, Chao Li, Gerome Miklau, and David Jensen. Accurate Estimation of the Degree Distribution of Private Networks. In Ninth IEEE International Conference on Data Mining, pages 169–178, 2009. [14] Yihua Hu, Hao Ding, and Wei Dong. N2E: A General Framework to Reduce NodeDifferential Privacy to Edge-Differential Privacy for Graph Analytics. Proceedings of the ACM on Management of Data, 3(6), December 2025. [15] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally Differentially Private Analysis of Graph Statistics. In 30th USENIX Security Symposium (USENIX Security 21), pages 983–1000. USENIX Association, August 2021. [16] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. CommunicationEfficient Triangle Counting under Local Differential Privacy. In 31st USENIX Security Symposium (USENIX Security 22), pages 537–554, Boston, MA, August 2022. USENIX Association. [17] Minhao Jiang, Ada Wai-Chee Fu, Raymond Chi-Wing Wong, and Yanyan Xu. Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks. Proceedings of the VLDB Endowment, 7(12), 2014. [18] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal Mechanisms for Local Differential Privacy. Advances in Neural Information Processing Systems, 27, 2014. [19] Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private Analysis of Graph Structure. Proceedings of the VLDB Endowment, 4(11):1146–1157, August 2011. [20] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing Graphs with Node Differential Privacy. In Theory of Cryptography, pages 457–476, Berlin, Heidelberg, 2013.
9
SeQureDB ’26, May 31-June 05, 2026, Bengaluru, India
Adam Tan, Mohamed Hefny, and Keval Vora
Table 8: Mean 𝑙 1 error for 𝜀 with 𝑑 min = 1 for Syn-power-1, Brightkite, and Ego-twitter. Bold marks the best method within the Central and Local blocks for each 𝜀 within each dataset. The Ego-twitter NO/LR entry at 𝜀 = 0.1 is marked – because all runs optimized to 𝛼ˆ < 0; with the minimum 𝛼ˆ clamped to 0, no valid estimates remained.
A Detailed Results This appendix reports the detailed per-dataset and per-𝜀 results that support the main experimental comparisons in the paper. Table 6: Mean 𝑙 1 (%) in centralized model, averaged over 20 runs. Bold marks the lowest mean within each each dataset and 𝑑 min block. Dataset wiki enron brightkite ego-twitter gplus stanford syn-power-0 syn-power-1 syn-power-2
BASE 23.90 25.14 15.86 15.15 18.53 24.14 7.55 6.53 6.10
𝑑 min = 1 DA NO 13.44 0.0248 3.43 0.0057 2.59 0.0038 9.82 0.0021 9.15 0.0013 0.58 0.0006 15.02 0.0022 14.43 0.0022 17.69 0.0017
BASE 36.25 29.45 20.00 23.66 20.98 34.60 10.93 10.10 10.08
𝑑 min = 3 DA NO 6.97 0.0315 2.29 0.0091 2.09 0.0073 6.61 0.0029 7.26 0.0013 0.25 0.0009 6.36 0.0021 6.05 0.0017 9.46 0.0026
Table 7: Mean 𝑙 1 (%) in local model, averaged over 20 runs. Bold marks the lowest mean within each dataset and 𝑑 min block. Dataset
DA/LR
wiki enron brightkite ego-twitter gplus stanford syn-power-0 syn-power-1 syn-power-2
11.09 2.14 3.78 8.26 8.26 3.63 12.86 12.29 16.20
wiki enron brightkite ego-twitter gplus stanford syn-power-0 syn-power-1 syn-power-2
2.86 0.26 0.86 5.90 7.00 6.30 4.83 4.51 8.81
DA/DR 𝑑 min = 1 13.18 1.94 1.05 9.54 8.94 0.07 15.18 14.59 17.75 𝑑 min = 3 4.42 5.00 5.26 6.80 7.45 1.85 6.69 6.36 9.61
NO/LR
NO/DR
6.25 10.49 11.80 3.62 2.10 6.44 5.76 5.61 4.30
0.64 2.63 3.20 0.61 0.46 0.74 0.40 0.39 0.17
6.86 3.23 3.71 1.14 0.47 6.50 2.30 2.28 1.11
4.13 3.30 3.81 0.31 0.33 1.70 0.48 0.46 0.24
10
Central
𝜀
DA
NO
0.1 0.3 0.5 1.0 2.0 5.0
0.14433 0.14433 0.14433 0.14432 0.14432 0.14432
0.00017 0.00007 0.00004 0.00002 0.00001 0.00000
0.1 0.3 0.5 1.0 2.0 5.0
0.02601 0.02592 0.02590 0.02588 0.02588 0.02588
0.00040 0.00011 0.00006 0.00004 0.00002 0.00001
0.1 0.3 0.5 1.0 2.0 5.0
0.11020 0.11018 0.11018 0.11017 0.11016 0.11016
0.00025 0.00010 0.00006 0.00003 0.00001 0.00000
Local DA/LR DA/DR NO/LR Syn-power-1 0.08033 0.05712 0.08701 0.06993 0.04822 0.07936 0.06265 0.04373 0.06593 0.05229 0.03818 0.05135 0.04455 0.03407 0.04130 0.04023 0.03127 0.03570 Brightkite 0.48725 0.25672 0.48313 0.38401 0.22502 0.39038 0.32831 0.19449 0.32760 0.25118 0.17476 0.24886 0.18919 0.16231 0.19887 0.16078 0.15683 0.15816 Ego-twitter 1.17006 0.25609 – 0.70188 0.20976 0.29952 0.43090 0.19537 0.13465 0.19093 0.18131 0.04065 0.09852 0.17279 0.01045 0.06864 0.16830 0.00118
NO/DR 0.05784 0.04605 0.04025 0.03301 0.02752 0.02368 0.43505 0.32023 0.27859 0.22218 0.18508 0.18328 0.04877 0.02217 0.01429 0.00675 0.00225 0.00010