论文标题
网络变更点在当地差异隐私下的本地化
Network change point localisation under local differential privacy
论文作者
论文摘要
网络数据在我们的日常生活中无处不在，其中包含丰富但通常敏感的信息。在本文中，我们通过考虑具有潜在变更点的一系列网络，将当前的私有化网络静态分析扩展到动态框架。我们研究了在节点和边缘隐私限制下始终定位变化点的基本限制，这表明了信噪比条件的有趣相变，并附有多项式时间算法。私人信噪比条件量化了变更点本地化问题的隐私成本，并且与非私人关系相比，稀疏参数的尺度不同。我们的算法在Edge LDP约束下对日志因素显示出最佳状态。在Node LDP约束下，我们的上限和下限之间存在差距，我们将其作为一个有趣的开放问题。
Network data are ubiquitous in our daily life, containing rich but often sensitive information. In this paper, we expand the current static analysis of privatised networks to a dynamic framework by considering a sequence of networks with potential change points. We investigate the fundamental limits in consistently localising change points under both node and edge privacy constraints, demonstrating interesting phase transition in terms of the signal-to-noise ratio condition, accompanied by polynomial-time algorithms. The private signal-to-noise ratio conditions quantify the costs of the privacy for change point localisation problems and exhibit a different scaling in the sparsity parameter compared to the non-private counterparts. Our algorithms are shown to be optimal under the edge LDP constraint up to log factors. Under node LDP constraint, a gap exists between our upper bound and lower bound and we leave it as an interesting open problem.
