Differential Privacy for Markov Chain State Trajectories

技术摘要：马尔可夫链状态轨迹的差分隐私

问题陈述
数据驱动系统经常依赖于由马尔可夫链生成的状态轨迹来建模行为，例如信用风险迁移、城市交通模式和互联网浏览。虽然这些轨迹非常有用，但共享它们会带来显著的隐私风险，因为短序列通常被用于重建用户身份。现有的马尔可夫链轨迹私有化方法通常将该链视为非确定性有限状态自动机，通过忽略转移概率的均匀随机游走来选择私有状态。这种方法经常生成缺乏底层马尔可夫链结构属性的“非典型”轨迹，从而降低了私有化数据用于下游分析的效用。此外，先前的工作通常是离线进行轨迹私有化，或者未能利用特定的转移动态来维持结构相似性。

方法论
作者提出了一个新框架，用于在线生成 $\epsilon$-差分隐私状态轨迹，这意味着私有轨迹是与敏感轨迹同时生成的。该方法的核心是将马尔可夫链视为一个加权有向图，其中边的权重为转移概率的负对数（$W_{ij} = -\log(P_{ij})$）。

1. 图归纳与距离： 作者在该图中定义了一个最短路径距离 $G(i, j)$。命题 1 确立了该图中的最短路径对应于马尔可夫链中两个状态之间最可能的路径。
2. 邻接定义： 引入了一种新的轨迹邻接概念（定义 4）。如果两条轨迹的对应状态之间的对称最短路径距离之和被参数 $\rho$ 所限制，则认为这两条轨迹是相邻的。这不同于先前基于汉明距离（计算差异条目数量）的工作，它允许根据转移的可能性更细致地定义相似性。
3. 机制设计（机制 1）： 所提出的机制使用受置换与翻转（permute-and-flip）机制启发的策略在线生成私有状态。在每个时间步 $t$，给定前一个私有状态 $s'_{t-1}$ 和当前敏感状态 $s_t$，该机制从可行邻域 $N(s'_{t-1})$ 中选择下一个私有状态 $s'_t$。选择概率受效用函数 $u(w, w') = -\sum G(s'_t, s_t)$ 的偏置影响，该函数会惩罚那些在图距离上远离真实状态的状态。
4. 漂移分析： 作者将敏感状态与私有状态的联合过程建模为隐马尔可夫模型。他们利用 Foster-Lyapunov 漂移分析来证明私有轨迹表现出“负漂移”，这意味着如果发生偏差，它在统计上很有可能返回到敏感轨迹的邻域内。

核心贡献
本文主要有四项贡献：

• 新的隐私定义与机制： 作者引入了一种基于最短路径距离的马尔可夫链状态轨迹邻接新定义，并开发了针对该定义的在线 $\epsilon$-差分隐私机制 1。
• 误差界限： 他们提供了关于私有轨迹显著偏离敏感轨迹概率的集中不等式（定理 2），表明大误差发生的概率随之呈指数级下降。
• 典型性与熵界限： 作者界定了私有轨迹的期望经验熵（定理 3），并提供了一个集中不等式（定理 4），表明私有轨迹以高概率位于底层马尔可夫链的 $\eta$-典型集中。这确保了私有化数据保留了原始过程的统计特性。
• 实证验证： 该机制在三个真实世界数据集上进行了测试：信用迁移、城市交通（佛罗里达州盖恩斯维尔）和互联网流量（Wikispeedia）。

结果
数值模拟表明，在保持相同隐私水平的前提下，机制 1 在效用方面显著优于现有最先进的机制（Chen 等人，2023b）：

• 熵的减少： 在 3-差分隐私下，机制 1 与之前的最先进方法相比，熵减少了高达 80%。这表明生成的私有轨迹更接近马尔可夫链的真实统计分布。
• 误差概率： 与现有方法相比，该机制将大误差（最短路径距离的偏差）的概率降低了多达 4 个数量级。例如，在信用迁移示例中，大误差（$v=15$）的概率从 0.003 降至 $2 \times 10^{-7}$。
• 结构相似性： 不同于以往方法往往退化为随机游走（随着轨迹长度增加熵也随之增加），机制 1 在达到一定轨迹长度后能保持恒定的熵水平，从而保留了数据的结构完整性。

意义
本文声称其框架解决了马尔可夫链数据中隐私与效用之间的关键权衡。通过利用转移概率来定义距离和邻接，该机制确保了私有化轨迹保持“典型性”并与敏感数据保持结构相似。这使得下游系统能够有效地利用私有化数据，而不会损害用户隐私。作者强调，他们的方法不需要神经网络或特定上下文的距离函数，因此可以直接应用于任何已知转移概率的马尔可夫链场景。这项工作确立了生成既尊重底层动力学又符合在线实时性的私有轨迹是可能的，这相对于将状态空间视为无结构集合的方法是一个显著的进步。