Timezone: »
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, echoing the challenges in high-dimensional statistical inference under LDP constraints.
Author Information
Mengchu Li (University of Warwick)
Tom Berrett (University of Warwick)
Yi Yu (The university of Warwick)
More from the Same Authors
-
2023 Poster: Change point detection and inference in multivariate non-parametric models under mixing conditions »
Carlos Misael Madrid Padilla · Haotian Xu · Daren Wang · OSCAR HERNAN MADRID PADILLA · Yi Yu -
2022 Poster: Change-point Detection for Sparse and Dense Functional Data in General Dimensions »
Carlos Misael Madrid Padilla · Daren Wang · Zifeng Zhao · Yi Yu -
2021 Poster: Lattice partition recovery with dyadic CART »
OSCAR HERNAN MADRID PADILLA · Yi Yu · Alessandro Rinaldo -
2021 Poster: Locally private online change point detection »
Tom Berrett · Yi Yu -
2021 Poster: Adversarially Robust Change Point Detection »
Mengchu Li · Yi Yu