Technical Summary: Dependency Triad (DT) for Quantifying Dependencies in Local Differential Privacy

1. Problem Statement

The collection of multidimensional user data under Local Differential Privacy (LDP) faces a critical challenge: Correlation-Induced Privacy Leakage (CPL). While LDP mechanisms (e.g., $\epsilon$-LDP) bound leakage for individual attributes, inter-attribute dependencies can inadvertently reveal correlated information, increasing privacy vulnerabilities beyond the intended budget.

Existing solutions for quantifying CPL suffer from two primary limitations that hinder their practical applicability:

1. Scalability and Mechanism Constraints: Many existing algorithms (e.g., ITS, CBP, HCC-1/2, LTM) are either restricted to specific LDP mechanisms (e.g., two-level perturbation) or suffer from high time and space complexities (e.g., $O(a^2b^2)$ or $O(a^2b \log b)$) relative to attribute alphabet sizes ($a, b$). This makes them intractable for high-cardinality attributes or iterative privacy budget calibration.
2. Reliance on Ground-Truth Distributions: Current methods assume access to the exact, ground-truth joint probability distribution between attributes. In real-world LDP scenarios, this distribution is rarely known; it is often estimated from prior data, public datasets, or subsets of the population. Discrepancies between the known prior and the actual distribution (due to demographic shifts, sampling bias, or staleness) can lead to underestimation of leakage, creating privacy vulnerabilities, or overestimation, reducing data utility.

The paper posits that there is a need for a metric that can estimate CPL in constant time, is compatible with sparse distributions, and remains robust to distributional uncertainty without requiring ground-truth knowledge.

2. Methodology: The Dependency Triad (DT)

The authors propose the Dependency Triad (DT), a novel metric that summarizes pairwise dependency information relevant to CPL using three parameters: $(\alpha, \beta, \delta)$.

A. Core Concept

Instead of storing the full $a \times b$ joint distribution, DT compresses the dependency structure into three scalar parameters. This allows for constant-time ($O(1)$) estimation of CPL for any privacy budget $\epsilon$.

B. Parameter Derivation

The derivation involves approximating the conditional probability vectors $G$ and $G'$ (representing $P(\hat{X}|X_k=x)$ and $P(\hat{X}|X_k=x')$) through their element-wise ratios.

1. $\alpha$ (Upper Bound of Ratios): Represents the maximum likelihood ratio, governing leakage behavior in the low privacy regime (large $\epsilon$). It is defined as:
   $$\alpha = \ln \left( \max_{\hat{x}, x, x'} \frac{p(\hat{x}|x) + \Delta_{\hat{x},x}}{p(\hat{x}|x') - \Delta_{\hat{x},x'}} \right)$$
   where $\Delta$ represents the uncertainty matrix.

2. $\delta$ (Sparsity Correction): Accounts for cases where the distribution is sparse (i.e., denominators become zero). It captures the mass concentration in edge cases where $p(\hat{x}|x') = 0$.

3. $\beta$ (Calibrated Lower Bound): Originally, a parameter $\gamma$ (minimum ratio) was used. However, the authors found that $(\alpha, \gamma, \delta)$ could lead to overestimation errors. To improve accuracy while maintaining a conservative upper bound, they introduce a calibration step. $\beta$ is derived by calibrating the lower bound at a specific privacy budget $\epsilon_0$ (typically $\epsilon_0 \to 0$) to match the exact CPL ($CPL^\star$) of the known distribution. This ensures the estimator is a tight upper bound for all $\epsilon \geq \epsilon_0$.

C. Handling Distributional Uncertainty

To address the lack of ground-truth data, DT explicitly incorporates an uncertainty set $\Delta$ around the known distribution $P_K$. The parameters $(\hat{\alpha}, \hat{\beta}, \hat{\delta})$ are computed by optimizing over the feasible region defined by $P_K \pm \Delta$. This ensures the resulting CPL estimate is a conservative upper bound even if the actual distribution $P_A$ deviates from $P_K$ within the uncertainty bounds.

D. Algorithms

• Algorithm 1: Computes the $(\alpha, \beta, \delta)$ parameters from a known distribution and uncertainty matrix. It involves iterating over attribute pairs and solving a relaxed Linear Program (LP) to find $\phi$ (used for $\beta$), resulting in a pre-computation complexity of $O(a^2b^{3.5})$.
• Algorithm 2: Estimates the CPL using the pre-computed DT parameters and the privacy budget $\epsilon$ in constant time $O(1)$.

3. Key Contributions

1. Novel Metric (DT): The first metric specifically designed to summarize pairwise dependencies for LDP leakage analysis using only three parameters. It serves as a conservative surrogate for the full joint distribution.
2. Theoretical Guarantees:
   • Upper Bound: The authors prove that the DT-based estimator is a tight upper bound on the true CPL ($CPL^\star$), ensuring that reported leakage never understates the true privacy loss.
   • Uncertainty Robustness: The metric is proven to remain valid and conservative even when the prior distribution is uncertain or mismatched.
   • Complexity: It reduces the space complexity from $O(ab)$ to $O(1)$ and the evaluation time from polynomial to constant time.
3. Calibration Mechanism: A method to calibrate the parameter $\beta$ to minimize estimation error while preserving the privacy guarantee, addressing the accuracy gaps of simple ratio approximations.
4. Empirical Validation: Extensive experiments on five real-world datasets (SPM, CelebA, Adult, CVD, DSS) and synthetic data demonstrate that DT consistently estimates CPL with low Normalized Mean Square Error (NMSE < 0.025) across diverse dependency regimes and privacy budgets.

4. Experimental Results

• Accuracy: DT achieves very low estimation errors compared to the optimal $CPL^\star$ (computed by baselines like HCC-2 and LTM) across real datasets. In high-privacy regimes ($\epsilon \in (0, 1]$), the NMSE is exceptionally low (< 0.003).
• Scalability: Unlike baselines that require re-computation for every privacy budget, DT allows for rapid evaluation. In a budget calibration scenario, DT completed the task in 7 seconds compared to 61 seconds for the LTM baseline.
• Robustness to Uncertainty: When tested with distributional shifts (simulated by varying error margins up to 10%–20%), DT maintained a tight upper bound on the actual leakage, whereas methods ignoring uncertainty risked underestimation.
• Structural Regimes: DT performed well across various dependency structures (low-entropy, sparse, one-to-many, etc.). It was extremely tight for concentrated dependencies and conservatively accurate for sparse or tail-sensitive distributions.
• Privacy-Utility Trade-off: In attribute inference attacks and k-marginal estimation tasks, DT-enabled budget calibration achieved comparable or better utility (lower Total Variation Distance) than standard splitting (SPL) or random sampling (RS) methods, particularly for higher-order marginals, while maintaining robust resistance to inference attacks.

5. Significance and Claims

The paper claims that Dependency Triad (DT) bridges the gap between theoretical privacy analysis and practical deployment in multidimensional LDP settings.

• Practical Applicability: By removing the requirement for ground-truth distributions and enabling constant-time estimation, DT makes rigorous CPL analysis feasible for real-world data collection pipelines where distributions are uncertain and high-dimensional.
• Safety: The conservative nature of the estimator ensures that privacy guarantees are not compromised by distributional mismatches, a critical requirement for deploying LDP in untrusted environments.
• Efficiency: The ability to perform constant-time leakage estimation allows for dynamic and iterative privacy budget calibration, optimizing the privacy-utility trade-off without incurring prohibitive computational costs.

The authors conclude that while DT does not fully characterize the underlying joint distribution, it provides a sufficient, tractable, and theoretically sound building block for assessing total privacy leakage in multidimensional settings, overcoming the scalability and data availability limitations of existing methods.