# Network change point localisation under local differential privacy

arXiv: https://arxiv.org/abs/2205.07144 · HTML: https://mlsanity.com/paper/2205.07144/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2022.

## Built on by (most cited first, 5 of 5)

- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [Segmenting Human-LLM Co-authored Text via Change Point Detection](https://mlsanity.com/paper/2605.03723/) (2026)
- [Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions](https://mlsanity.com/paper/2312.07055/) (2023)
- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Locally Private Parametric Methods for Change-Point Detection](https://mlsanity.com/paper/2602.13619/) (2026)

## Abstract (arXiv)

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.