Doubly-Unlinked Regression for Dependent Data

1. Problem Definition

The paper addresses a novel statistical challenge termed Doubly-Unlinked Regression within the context of dependent data. Standard regression assumes that covariates ($X$) and responses ($Y$) are correctly paired. However, in many modern applications (e.g., privacy-sensitive data integration, spatial transcriptomics, sensor networks), two types of correspondence failures can occur simultaneously:

1. Covariate-Response Misalignment: The pairing between $X$ and $Y$ is unknown (Shuffled Regression).
2. Response-Domain Misalignment: The responses $Y$ are detached from the latent domain (spatial, temporal, or geometric) that induces their dependence structure.

The Model:
The authors propose a Data Generating Process (DGP) where both links are broken by unknown permutation matrices:
$$Y = \Pi_X X \beta + \Pi_S W + \epsilon$$
Where:

• $X$ is the covariate vector.
• $Y$ is the response vector.
• $\beta$ is the unknown regression coefficient.
• $W$ is a latent stochastic process (e.g., a Gaussian Process) inducing dependence based on an unobserved domain.
• $\Pi_X$ is the unknown permutation matrix shuffling $X$ relative to $Y$.
• $\Pi_S$ is the unknown permutation matrix shuffling the domain indices of $W$ relative to $Y$.
• $\epsilon$ is independent Gaussian noise.

The goal is to estimate $\beta$ and recover the latent permutations ($\Pi_X, \Pi_S$) despite the joint loss of correspondence and the presence of structured dependence in $W$.

2. Methodology

The paper tackles the problem through theoretical analysis and a computational algorithm.

A. Theoretical Framework

• Block-Structured Permutation: To make the problem tractable (as the search space is $(n!)^2$), the authors impose a block structure. The data is partitioned into $B$ blocks of size $K$. Permutations occur within blocks but not across blocks. This models localized scrambling (e.g., batch processing) while preserving coarse-scale ordering.
• Reparameterization: The problem is reparameterized into a Generalized Least Squares (GLS) form by defining $\Pi_1 = \Pi_S^\top \Pi_X$ and $\Pi_2 = \Pi_S^\top$, transforming the DGP into $\Pi_2 Y = \Pi_1 X \beta + W^*$, where $W^*$ has a known covariance structure $\Sigma$.
• Signal-to-Noise Ratio (SNR): The authors define a new SNR metric tailored for dependent data:
  $$SNR = \frac{\beta^2}{\lambda_{\max}(\Sigma)\kappa(\Sigma)}$$
  where $\lambda_{\max}$ is the largest eigenvalue and $\kappa$ is the condition number of the covariance matrix. This accounts for the complexity introduced by the latent dependence.

B. Computational Algorithm: REPAIR

To solve the combinatorial optimization problem (which is NP-hard), the authors develop REPAIR (Regression with Permutation Alignment via Variational Inference).

• Variational Bayes (VB): Instead of searching the discrete permutation space, REPAIR treats permutations as latent random variables and approximates the posterior distribution using a mean-field variational approach.
• Continuous Relaxation: The discrete permutation matrices are relaxed into the Birkhoff polytope (the space of doubly stochastic matrices) using a continuous relaxation technique (based on Linderman et al., 2018). This allows for gradient-based optimization.
• Iterative Updates: The algorithm alternates between updating the variational parameters for the regression coefficient ($\beta$), the latent process ($W$), covariance parameters ($\sigma^2, \tau^2, \phi$), and the permutation matrices ($\pi_X, \pi_S$).
• Post-Processing: The final estimated matrices are projected back to the nearest valid permutation matrices using the Sinkhorn-Knopp algorithm and the Hungarian algorithm.

3. Key Contributions

1. Unified Framework: The paper provides the first systematic treatment of regression where both the covariate-response link and the response-domain link are unknown, unifying shuffled regression and latent-domain permutation models.
2. Theoretical Recovery Guarantees:
   • Permutation Recovery: The authors establish conditions under which the permutation matrices can be exactly recovered. They show that exact recovery requires the SNR to scale polynomially with the block size $K$.
   • Regression Consistency (Crucial Insight): They prove that consistent estimation of the regression coefficient $\beta$ is achievable under strictly weaker conditions than exact permutation recovery. Specifically, $\beta$ can be estimated consistently even if the permutations are not perfectly recovered, provided the SNR is sufficiently high. This implies that accurate scientific inference is possible even when full data alignment is information-theoretically impossible.
3. Scalable Inference (REPAIR): The development of a computationally feasible variational Bayes method that handles the combinatorial complexity of joint permutation and parameter estimation in dependent data settings.

4. Results

Simulation Studies

• Setup: Experiments were conducted with varying block sizes ($K$) and numbers of blocks ($B$) under different SNR regimes.
• Regression Performance: REPAIR consistently outperformed a naive aggregation method (ArealGP) and approached the performance of an "oracle" method (FullGP, which knows the true permutations) as the number of blocks $B$ increased.
• Permutation Recovery: The probability of recovering the exposure permutation ($\Pi_X$) was generally higher than recovering the latent domain permutation ($\Pi_S$).
• Key Finding: Even when $\Pi_S$ was only partially recovered, the estimation of $\beta$ remained accurate, validating the theoretical result that regression inference does not require perfect permutation recovery.

Real Data Application

• Dataset: The Meuse soil dataset (heavy metal concentrations vs. elevation).
• Experiment: The authors artificially created a doubly-unlinked scenario by permuting exposure and spatial coordinates within blocks.
• Outcome: REPAIR successfully recovered the negative relationship between elevation and zinc concentration, producing estimates close to the oracle benchmark, particularly when the block size was small relative to the total sample size.

5. Significance and Implications

• Privacy-Preserving Inference: The framework demonstrates that meaningful statistical inference (estimating effect sizes) is possible even when data is heavily anonymized or scrambled at the individual level, provided the data retains some structural dependence (e.g., spatial or temporal correlation).
• Dependent Data Handling: It extends the theory of shuffled regression from independent and identically distributed (i.i.d.) settings to complex dependent data (spatial, temporal), which is more realistic for modern scientific datasets.
• Computational Feasibility: By introducing the block-structure assumption and the REPAIR algorithm, the paper makes a previously intractable NP-hard problem solvable for moderate-to-large datasets.
• Future Directions: The authors suggest extending the framework to multivariate covariates, relaxing the block-structure assumption, and applying it to graph-indexed latent domains (network matching).

In summary, this paper establishes that in the presence of double unlinking and dependent data, one can reliably estimate regression effects without needing to perfectly reconstruct the underlying data alignment, offering a robust solution for privacy-sensitive and data-integration challenges.