Abstract
The Maximal Information Coefficient (MIC) is a powerful statistic to identify dependencies between variables. However, it may be applied to sensitive data, and publishing it could leak private information. As a solution, we present algorithms to approximate MIC in a way that provides differential privacy. We show that the natural application of the classic Laplace mechanism yields insufficient accuracy. We therefore introduce the MICr statistic, which is a new MIC approximation that is more compatible with differential privacy. We prove MICr is a consistent estimator for MIC, and we provide two differentially private versions of it. We perform experiments on a variety of real and synthetic datasets. The results show that the private MICr statistics significantly outperform direct application of the Laplace mechanism. Moreover, experiments on real-world datasets show accuracy that is usable when the sample size is at least moderately large.
Introduction
The Maximal Information Coefficient (MIC) serves as a "Swiss Army knife" for modern statisticians. Unlike Pearson’s correlation, which is limited to capturing linear relationships, MIC can identify complex, non-linear dependencies across high-dimensional data. However, as datasets increasingly involve sensitive information—such as medical records or economic indicators—the risk of leaking individual data points through published statistics becomes a critical concern.
Differential Privacy (DP) is the gold standard for addressing such risks, requiring that a statistic remain relatively stable regardless of whether any single individual's data is included in the set. This paper addresses the inherent incompatibility between standard MIC approximations and DP, proposing a new statistic, MICr, designed for high-utility private dependency detection.
The Sensitivity Problem in MIC
Standard efficient approximations of MIC, such as MICe, rely on "mass equipartitions." These are grids where the boundaries shift dynamically based on the density of the data points. While computationally efficient, this data-dependence is a privacy nightmare. Because the grid "jiggles" in response to a single point's movement, the sensitivity of the statistic is extremely high. To satisfy DP requirements, one would have to add so much noise to a standard MICe calculation that the resulting value would lose all practical meaning.
Methods: Introducing MICr
The authors propose MICr (Range-based MIC) to solve the sensitivity issue. The core innovation lies in moving from data-dependent grids to range equipartitions. In MICr, grid boundaries are fixed based on the total possible range of the data rather than the data's internal distribution.
By fixing these boundaries, the sensitivity of the statistic is reduced from $O(B \log n / n)$ to $O(\log n / n)$, where $B$ is the grid size. The authors mathematically prove that MICr is a consistent estimator, meaning it converges to the true underlying relationship strength as the sample size increases.
Differentially Private Mechanisms
Building on the MICr foundation, the paper introduces two private mechanisms:
- MICr-Lap (Output Perturbation): This mechanism calculates the non-private MICr value and adds noise sampled from a Laplace distribution. Due to the lower sensitivity of MICr, the required noise is small enough to preserve utility.
- MICr-Geom (Input Perturbation): This approach adds noise directly to the "count matrix" (the number of points within each grid cell) using a Truncated Geometric mechanism prior to calculating the coefficient.
Experimental Evaluation
The researchers evaluated these mechanisms using a combination of synthetic benchmarks and real-world datasets:
- Synthetic Distributions: 189 joint distributions based on 21 functional relationships (e.g., linear, sinusoidal, step functions) with varying noise levels ($R^2$ from 0.1 to 0.9).
- Spellman Yeast Data: A bioinformatics dataset tested at two scales: small ($n=23$) and large ($n=4381$).
- Baseball Data: Performance statistics for 337 MLB players from the 2008 season.
Key Findings
- Accuracy Gains: Both MICr-based mechanisms significantly outperformed the naive application of noise to standard MICe approximations.
- Scalability: The mechanisms reach a "usability threshold" as sample sizes grow. For the Spellman4381 dataset with a privacy budget of $\epsilon=1$, MICr-Lap achieved a median bias of nearly zero (-0.01) and extremely low variance ($4 \times 10^{-4}$).
- Practical Utility: On the Baseball dataset ($n=337$), the average error was approximately 0.068. Given that MIC values range from 0 to 1, this level of error allows researchers to reliably distinguish between strong and weak relationships while maintaining privacy.
Discussion and Limitations
While MICr represents a significant step forward, it introduces a new requirement: prior knowledge of the data range ($L$). If the range must be estimated from the data itself, that estimation must also be performed privately, adding a layer of complexity. Furthermore, while the mechanisms excel at moderate to large scales, detecting dependencies in very small datasets (e.g., $n < 30$) remains a challenge, as the noise required for DP can still overwhelm the signal.
Future work may involve exploring local sensitivity to further minimize noise and developing "de-biasing" techniques for the MICr-Geom mechanism to improve accuracy in sparse data regions.
Summary updated