Network change point localisation under local differential privacy
Authors: Mengchu Li
Thomas Berrett
Yi Yu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Local differential privacy
change point detection

Abstract: 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.

Network change point localisation under local differential privacy
Mengehu Li
Thomas Berrett
Department of Statistics University of Warwick
Department of Statistics
University of Warwick
mengchu. 11 di@warwickk.a. ac.uk
tom. www.etttwwrwiiieie.......a. ac uk
Yi Yu
Department of Statistics University of Warwick yi. 20warwic... ac. uk
Abstract
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 dynamic framework by considering sequence of networks with potential change points. We investigate the fundamental limits in consistently local- ising change points under both node and edge privacy constraints, demonstrating interesting phase transition in terms of the signal-to-noise ratio condition, accom- panied by polynomial-tine quantify the costs of the privacy for change point localisation problems and exhibit a different scaling the sparsity parameter compared to the non-private counter- parts. Our algorithms are shown to be optimal under the edge LDP constraint up log factors. Under node LDP constraint, a gap exists between our upper bound and lower bound and we leave in high-dimensional statistical inference under LDP constraints.
algorithms. The private sigmal-to-noise ratio conditions
interesting open problem, echoing the challenges
Introduction
Numerous application areas and everyday life routinely generate network data, which contain valuable but often sensitive information [c.g. 33, 31]. Understanding the underlying patterns of network data while preserving individuals' privacy is crucial modern data analysis. Several attempts have been made, but mostly focus studying single snapshots of networks (a.k.a. static networks) and/or subject to central differential privacy constraint, where a central data curator is allowed to handle raw information from all individuals [e.g. 21, 22, 23, 9, 30]. In this paper, with understanding the dynamics sequence of networks (a.k.a. dynamic networks). under local privacy constraints (LDP), where one is allowed to handle the raw data of other individuals [e.g. 13, 17, 26, 40, 34].
instead concerned
Dynamic networks are usually in the form of a sequence of static networks, along linear ordering, say time. the dynamic networks studies, it is vital to capture the ever changing nature. handy and useful way to model the changes is assume that there exists a sequence of unknown time points, where the underlying distributions change abruptly [e.g. 37, 38]. These unknown time points referred to as change points. Identifying change points helps pinpoint important events, and more accurately estimate underlying distributions, which can be regarded as stationary between two consecutive change points. Dynamic networks change point analysis has demonstrated its success in climatoloyy [e.g. 28], crime science(e.g. 6] and neuroscience [e.g. 10, 29], to name but few.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Despite the growing popularity in studying dynamic networks, we have witnessed vacuum in estimating change points while preserving data owners' privacy. Having said this, line of attack has been made to analyse static network data under LDP constraints, where only data owners have access to their individual raw data [e.g. 34, 40]. The private analysis of network data is complicated by the fact that different LDP conditions are required depending on the information that one wants to protect. For example, in a relationship network, users may want to protect their edge information, L... whether they are connected to someone else or not. As we argue in Section 2.1, formalisation to protect such information should require minimal trust between users due to the symmetric nature of network data. In a recommending system network, users may want to protect their entire connection portfolio, representing the purchase status of a user over a collection of products. In a brain imaging network, patient may even prefer protecting the entire network from adversarial inference attacks.
In view of the aforementioned state of the art, we list the contributions of this paper below.
To our best knowledge, this is the first time investigating change point localisation in dynamic networks, under LDP constraints. We consider two dynamic network models, where sequence of sensitive networks are generated from (a) inhomogeneous Bernoulli networks (IBN) (Definition I) and (b) bipartite networks with possibly dependent Bernoulli entries (Definition 2). Multiple change points of the raw network distributions are allowed. To tailor to the network models, we consider two forms of privacy requirements edge LDP and node LDP (See Section 2).
For dynamic IBNs under edge LDP, we show a phase transition in terms of the signal-to-non -o-se ratio, partitioning the whole parameter space into two parts: (1) the infeasibility regime where no algorithm is expected to provide consistent change point estimators and (2) the regime where a computationalll-effiiieee algorithm is shown output consistent estimators. The importance of this phase transition is twofold: (1) The transition boundary is different from its counterpart in the non-private case [38], quantifying the cost of preserving edge privacy in localising change points. (2) We show that a simple randomised response [39] based privacy mechanism is minimax rate-optimal for the purpose of change point localisation.
For bipartite networks under node LDP, we derive an infeasibility regime which is different from that under the edge LDP. This fundamental difference quantifies the difference between these two different IDP constraints, and can be used to help practitioners designing data collection mechanisms. We adopt privacy mechanism proposed in [13], together with change point estimation routine, providing a consistent change point estimator. Supported by a minimax lower bound result, our estimator is shown to be minimax rate optimal when the number of columns is of constant order. When the number of columns is allowed to diverge, a gap between our lower and upper bounds exists. This echos the well-identified challenges in the high-dimensional privacy research [e.g. 13, 14]. We contribute a high-dimensional network example along with in-depth discussions.
Notation For any matrix A E MM N let Ai be the (i, j) -th entry of A, A R be the i-th row of maxisisM M.S.MMM.SSS ISJEN [Ail and ||-A]] denote the operator norm EisKMMISEEN A.g Biy and ||A||F= V(A, A) be
A, A be the transpose of A, ||Al| of A. For any matrix B I. M let (4, the Frobenius norm of A. For any vector e E TR, let ||]| |e1|,, 2 ||||| xo be the E1, f2 and &ao vector norms respectively. For any set S, let |S] be the cardinality of S. Let S = S'US", if US" = S and S' S = 0. Let 1 J be the indicator function only taking values in (0, 1J. For two any functions of T, say F(T) and (T)), we write f(T) Z g(T) if there exists constants C' > 0 and To such that S(T)= Z (T) for any 2 To. and write [(T x (T) if J(T) Z (T) and S(T) S (TT).
1.1 Problem setup
We consider two parallel models of dynamic networks. The first one is built upon an IBN model, which covers a wide range of models for undirected networks, including the Rédös-Rényi random graph [16], the stochastic block model [18] and the random dot product graph [e.g. 3]. among others.
Definition 1 (Inhomogeneous Bernoulli network, IBN). A network with node set {1....,n} n) is an inhomogeneous Bernoulli network if its adjacency matrix A E Raxn satisfies that Aij = A₁: = modde i, are connected by an edge} and (Ag, i & j) are independent Bernoulli random variables with E A.g) = Dij-
The second model considered is a bipartite IBN with possibly correlated entries within each row of the biadjacency matrix. See [2] for more discussions on bipartite networks.

---

Definition 2 (Bipartite IBN), A network with node set {l...., + n2) = V [Vi nn and [V/] n2. is a bipartite IBN if its biadjacency matrix A 1 x satisfies the following. (1) For i E V1 and j E V2, Aij nnodes i, are connected }. (2) For any i1, 12 E V1, in * i2, (A j = 1.....
10:0 ;......,. ,22) and {Aiz.j: J 1, .......,, m2) are independent. (3) For any E V1, j E V2. Ag is Bernoulli random variable with B(A,) i.
Bipartite IBNs are often used in the recommending system, where each i E V1 represents user and each j E 1/2 represents a product [e.g. 27, 20]. An important difference between Definitions and 2 is that, in Definition all entries assumed to be independent, while in Definition 2, entries within the same row are allowed to be arbitrarily dependent. Dependence in networks are common in practice, for example the control-flor graph considered in [42] where V1 corresponds to the set of users and each node in 1/2 corresponds to component within some software application and the dependencies therein due to the causality between nodes.
The change points are defined formally Assumption 1 where the magnitude of the distributional change is measured by the normalised Frobenius norm. The choice of Frobenius norm captures both dense and sparse changes in the network structure, see [38].
Assumption 1. Let {A(1))=1 C {0, 1 1 be an independent sequence of adjacency matrices of IBNs defined in Definition (in which case n2 = f2 n) or biadjacency matrices of bipartite IBNs defined in Definition 2, with [{A(t)} } = (()). Assume that there exist {m..... .TK J C .2..... ,Th,
with 1 = 17u 171 <... `K- S T πバ+1 T 1, such that ( # O(t 1). if and only if t E {M) :0.. TK]
Let A = ming-1 K+1 (mh Tk-1) ) be the minimal spacing and Kn = ming [[O(m)) O(T 1)ll //ll//(//nn (//mn2p)) be the minimal jump size, where = max?=1 [[O(1)] ol denotes the entry-wise sparsity.
For both models, under privacy constraints to be discussed in Section 2, our goal is to construct K consistent estimators {7h ) of {nH H To be specific, { is said to be consistent if A max 17 Thel + 0 and K- K holds with probability tending to 1, as the sample size T grows unbounded.
Lastly, we note that in statistical network analysis, when allowing for entry-wise sparsity, it is usually assumed that p 2 log(n)/n [e.g. 38] ensure there are sufficiently many observed edges. However, We do not impose lower bounds on p in Assumption I, since to preserve privacy, the expectations of privatised network entries are inflated by a factor of the privacy level a E (0, 1). Let p' be the sparsity parameter of the privatised networks. Such inflation automatically ensures that p' 2 log(n)/ng n, for any p E [0, 1] and n > (See the proof of Theorem 3).
2 Network local differential privacy
To formalise different network LDP notions, we first recall general definition of LDP. A private mechanism a conditional distribution, which conditional on raw data, outputs privatised data. For pre-specified privacy level a 2 0, random object Zi taking values in Z is non- non-interactive! a-LDP version of raw data X,, if for any raw data and x'. any measurable set C Z, it holds that
Qi(Z, E S|X, x) (Z, S|X; 2e)
(1)
A privacy mechanism is a-LDP if all output Z; 's are LDD. We focus on the regime a E (0. 1), where the effect of privacy is the strongest and is often the regime of primary interest [e.g. 12, 13, 5, 36).
In view of (1), the LDP constraint ensures that each individual i only has access to their own raw data. To be specific, the privatised Z, only depends the data X;. As for network data, to impose LDP, it is crucial to formalise what a unit of information includes and who are the owners of each unit of information. In the rest of this section, we consider two cases arising from different application backgrounds.
In this paper, we only consider non non-interactive privacy mechanisms throughout and will call it privacy mechanism when there is no concern of ambiguity. For more general interactive privacy mechanisms, see [13].
3

---

2.1 Edge local differential privacy in inhomogeneous Bernoulli networks
In epidemiological studies on sexually transmitted diseases, network data are formed by edges linking sexual partners [e.g. 35]. A natural choice of information unit is the existence of sexual relationship among subjects. Due to the sensitivity of such data, one may wish to consider all parties involved to be the owners of potential link. Inspired by such applications, we formalise the edge LDP in Definition 3.
Definition 3 (Edge a-LDP), We say that the privacy mechanism Q = {Qii Isisisn, 1 t I T is edge L-LDP, for any integer 1 S t S T, any integer pair 1 1 Siijj n, any measurable set S C Z and any x, x' E {0. 1). it holds that
2 (z) E ()) = = (0) (2n(1) E ([))() = =x) 5
(2)
Definition 3 is seemingly stricter than some existing edge LDP notions [e.g. 34, 40], where, instead of (2), it is required that for any E {l....,.) _.} and any x, x' E IR" with || x'111 I,
2.00 (z.(t) E ()A((t) =
e S)A((t) = 2e)
is clear that applying any mechanisms that satisfy (2) to each entry of (t) guarantees (3). While appropriate for some settings, the edge LDP defined in (3) possesses some caveats [19], listed below.
The same piece of information is recorded in the adjacency matrix twice, i.e. A, (4) = (!) and these two records are treated as being potentially different. The same quantity is thus randomised twice, leading to some inefficiency.
As a more damning issue, mechanisms satisfying (3) may require trust between nodes. If node does not follow the protocol correctly, or their data are intercepted, they may reveal information on other nodes in the network. This is not the case with LDP mechanisms in other settings, where the privacy of an individual is guaranteed regardless of the behaviour of other individuals.
Our definition (2) does not suffer either of these drawbacks since we only privatise the upper triangular part of the adjacency matrix, and privatise each edge between two nodes, (2) implicitly requires that both parties to agree on their status and the privatised result so that the trust issue can be prevented.
2.2 Node local differential privacy in bipartite inhomogeneous Bernoulli networks
In a Netflix data set, one may model the viewing history by a dynamic bipartite IBN, where each row represents user, each column represents movie and each snapshot of network gathers the viewing information within a short time frame. is reasonable to consider an information unit to be the viewing history of user within time frame, which is row in biadjacency matrix. Inspired by such applications, we formalise the bipartite node LDP in Definition 4.
Definition 4 (Bipartite node a-LDP), We say that the privacy mechanism Q = (0] 1 sis
71, 1 TT is bipartite node a- a-LDP, if for any integer 1 I < T. any integer S n1, any measurable set S c. Z and any x, x' E {0,1) it holds that
(Z,(t) E SIA,(t) = (Z,() E S(A,(t) = 5e
(4)
Different notions of node LDP have been studied in the literature. Our definition (4) is consistent with [e.g. 34, 40] while some adopt the definition inherited from central DP allowing the neighbouring networks to have different dimension by either inclusion and deletion of one node [23, 11]. Several works consider the same constraint as (4) under the name user-level LDP [c.g. 24, 43] for different learning tasks.
One appealing feature of bipartite graphs when considering node LDP is that the neighbouring data sets x, can be protected independently for each node Vı1 whereas in a general graph, node LDP should account for the intrinsic symmetry of the adjacency matrix when defining neighbouring data sets [19]. Comparing the two LDP definitions we considered in this section, we see that in Definition 3 level a privacy is imposed to protect one edge, and in Definition 4 level a privacy imposed to protect n2 edges. For the same privacy parameter o, node privacy is a much more stringent constraint than edge privacy [e.g. 34, 40, 19].

---

Fundamental limits in consistent change point localisation
Recall that our task is to understand how the underlying distributions of dynamic networks change, especially provide consistent change point estimators defined in Section 1.1, under certain form of LDP constraints. Without the concern of privacy, dynamic IBN change point localisation is investigated in [38], where a scaling (namely the signal-to-noise ratio) is proposed partition the whole parameter space into two regimes: a low signal-to-noise ratio regime (infeasibility regime) where no consistent estimator is guaranteed in minimax sense, and high signal-to-noise ratio regime where computationally-effiiio
algorithms are shown to produce consistent estimators. Recall the model parameters Ko the minimal jump size, p the entry-wise sparsity of networks, the network size and A the minimal spacing. Without the presence of privacy constraints, the infeasibility regime [38]
Aipn& S 1,
(5)
which will serve the benchmark for to quantify the cost of privacy.
The first model we study is dynamic IBN model (Definition and Assumption 1), which is identical to the one studied in [38]. Lemma I demonstrates an infeasiblity regime of localising change points in such a model under the edge a-LDP defined in Definition 3.
Lemma 1 (Edge a-LDP). Let {A(t)] {0. 1]mxn be a sequence of adjacency matrices satisfying Assumption with K = 1 and ler P K..A. denote their joint distribution. Consider the class of distribations
P= PP KĀ min A(e 1/44, (144),510 A/3)).
Let Qudge denote the set of all im-iinteractive privacy mechanisms that satisfy the edge o-LDP constraint in Definition 3, for E (0, min (2p) (2p)-1}). We have that
inf inf sup Er.q - mP) A/12, QE " PEP
where n(P) denotes the change point location specified by distribution P. the first infinum taken over all possible non son-interactive privacy mechanisms, the second infinum is taken over all measurable functions of the privatised data and the supremum is taken over all raw data's 's distributions in the class P.
Lemma studies an LDP minimax lower bound in the framework put forward by [13]. It shows
that for dynamic IBNs under edge a-LDP, provided 2 1) x 2gp2nAa X 1, the
localisation error A - - (n() 2 1/12. This leads to the infeasiblity regime
nda $
(6)
Comparing (5) and (6), any distribution in the regime (5) also falls in the regime (6), implying that imposing edge a-LDP enlarges the infeasibility regime and makes the localisation task harder. To be specific, the cost of preserving edge LDP comes from two fronts.
The effective sample size is decreased from A to 2 LDP's impact on the effective sample size commonly observed in the literature over a wide range of problems [e.g. 13, 7, 5, 25].
more interesting and proclem-specific cost of LDP is reflected by the role of the sparsity parameter p. which power is raised to p² in (6) from p in (5). Despite that networks have been studied under LDP constraints, such result is the first time seen. Similar effects have been observed in different problems under LDP constraint, including the impacts dimensionality [c.g. 5] and smoothness levels [e.g. 25]. It is interesting to see that in high-dimensional sparse network problem, this problem-specific cost of LDP appears on the sparsity parameter.
The second model we consider is a dynamic bipartite IBN model (Definition 2 and Assumption 1), the change point analysis of which is not seen in the literature, even without privacy concerns. In addition to the rows and columns bipartite IBNs denoting different entities, which is different from well-studied network models, we also allow potentially arbitrary within-rov dependence. Lemma 2 establishes an infeasiblity regime of localising change points in such model under the bipartite node a-LDP defined in Definition 4.
5

---

Lemma 2 (Bipartite node a-LDP). Ler {A(t)]t=] C {0, 10,1]m1xa3 be a sequence of biadjaceney matrices satisfying Assumption I with K and let P Consider the class of distributions
"a. m2, denote their joint distribution.
p= P= km,
Kg m 1/2 (2 1)91-1 1/4), A T/3).
Let Quode denote the set of all non- non-interactive privacy mechanisms that satisfy the bipartite node a-LDP constraint Definition for a E (0, min (4p) 3)). We have that
inf inf sup E.Q î ny P)] 4/12,
QEQ
PEP
where n(P) denotes the change point location specified by distribution P.
In an LDP minimax framework, Lemma 2 shows that provided kōp²n) error A - In (P)] 2 1/12. This leads the infeasibility regime
1/2 Aaa 2 the localisation
2 2 1/2 Aa² S 1.
To compare (6) and (7), first let n1
n22 in Lemma 2 for convenience. The infeasibility regime under the node LDP reads as 2/2 Aa² S I, which compared to (6) implies that the cost of node LDP is higher than the edge LDP. further understand the difference between node LDP and edge LDP, we let
/R Lemma 1. The infeasibility regime under the edge LDP reads
as 2 x (n)n)) m2) /2/3 Aa² $ 1, which compared to (7) highlights the difference of n2 1/2 an extra cost of dimensionality. The extra cost captures the difference between privatising vectors with possibly correlated entries under node LDP and privatising discrete values under edge LDP.
Lastly, note that both proofs of Lemma and Lemma 2 follow the convex Le Cam method [e.g. 41] where the key step is bounding the chi square distance between a privatised product distribution and mixture of privatised product distributions. For the node LDP case, the hard distributions exploit the dependence within rows of the biadjancency matrices.
Consistent private network change point algorithms
We have established infeasibility regimes of change point localisation tasks under different network LDP constraints in Section 3 and have understood how the privacy preservation makes the tasks fundamentally harder. In this section, we provide polynomial-time private algorithms obtain consistent change point estimators outside of the infeasibility regimes. A private algorithm has two key ingredients: (1) a privacy mechanism and (2) an algorithm with privatised data as inputs. For the two models we consider in this paper, we adopt the same change point localisation algorithm, while using different privacy mechanisms.
The change point localisation algorithm we consider is the network binary segmentation (NBS) algorithm proposed and studied in [38]. is shown that NBS provides consistent change point estimators without privacy concerns, under minimax optimal conditions. For completeness, we include NBS Algorithm and introduce the CUSUM statistic below. For any form of data (X,) and any integer triplet 0 < < <<t S. T, the CUSUM statistic is defined as
X (()0()))
(e s)(( 1= -
c e-t
X Σ
Σ X
(e s)
1=
As pointed out in [38], two sequences of independent networks are required as inputs of Algorithm in order to estimate the Frobenius norm of IBN. In practice, one can split the data to even and odd indices to obtain two sequences of networks.
4.1 Edge o-LDP
To privatise a dynamic IBN (Definition 1) under the edge a-LDP, we apply the randomised response mechanism [39] independently to every edge. The privacy guarantee follows by virtue of the the randomised response mechanism [15]. To be specific, given data {A(t)) C {0, 10,11a0 1)axn, let

---

Algorithm 1 Network Binary Segmentation. (BS((s, e), {amm 9m }m)) 1 m==
INPUT: (U(1))= (V(1))== C Ruix {(am, 9m m=1 C [0, T 71
for m =1,..,, p....,,M M do
Is'm mm] t [s |amm Bml, (5ms em) + 1s + 64 64 s em 64 (cm mm)
if cm Sm 2 then
bm 1.++ag arg maxt=sm= + + (U (5m (t), [ (8)
Om < (mm))memm) (Im), Vmm (bm))
else
O.m --1 end if
end for
mn"" arg maxmm=l...... Om
if am- > T then
add bm- to the set of estimated change points
NBS( bmx), [amm: }m)} 1:
NBS( (Bm. + 1, e), [[0m: 8m m==1: end if
OUtPuT: The set of estimated change points.
(Uraj,1 siso S n) be independent Unif[O, random variables that are independent of (A())T For any / E (l...., 1
......? T} and any integer pair sisj S n, let the privatised data be (A'(t))= c [0, nnn with
11-4, 11 (A,00) Ai((),
Uti S see/(1 + e%)
A,,(1) = A/,00)
(8)
otherwise.
Note that due the symmetry of the networks, each edge is only privatised once. Despite that we are dealing with high-dimensional, sparse dynamic IBN model, with potentially multiple change points, Theorem below shows that this, arguably simplest privacy mechanism not only provides consistent change point estimators, but also is optimal in terms of the signal-to-noie noise ratio condition required. Theorem 3. Let {A(t))== and (B(t) be two independent sequences of adjacency matrices satisfying Assumption I. For an arbitvarily small & > O and an absolute constant Co > O, assume that
2gpp² 2n 2 co solog2+ (og2+((T)
Let HiR be the output of the NBS algorithm, with inputs:
AA(1)) and (B'(I))= privatised version of {A(1) and (B()) obtained through (8);
((0mm 3m) JM random intervals whose end points are drawn independently and uniformly
from (l...., T} such that max (8m am I CRA. for some constant CR 3/2; and
tuning parameter T satisfying ein log 3/23/2(T) < < 02kăn" Da?, where C₁, 02 > are absolute constants.
It holds with probability least exp (lp((og(T c3MA/T] - that k= and lije mal S cs (o) ( ( (Tog(T)/((300nan)
where C3 C4, C5, Co O are absolute constants.
Theorem 3 shows that, provided M 2 TA-1 log (Tog(T//A0
A), it holds with probability tending to one,
max TM 7h S A log (og(T) (og(T)(V///mnnnpd)) + Vlog(T))/(a)) (k)pp 1 na na²)) + 0, (10)
where the second inequality is due to (9). Recalling the consistency definition in Section 1.1, (10) implies the consistency of NBS with randomised response privacy mechanism under edge a-LDP.
In view of the condition (9) and the edge LDP infeasibility regime (6), up to a logarithmic factor, we unveil phase transition with boundary x 2 = and show that the randomised response mechanism is optimal the minimax sense. This is conceptually interesting since, as pointed out in [34], the privatised network obtained by (8) leads to dense graph even though the original graph may be sparse and therefore does not represent the original graph well. However, our result shows that this is the best one can do for change point localisation, at least among non-interactive mechanisms.
7

---

4.2 Bipartite node a-LDP
To privatise dynamic bipartite IBN (Definition 2) under the bipartite node a-LDP, we apply the privacy mechanism developed in Duchi et al. [12, 13] for privatising vectors with bounded & norm to each row of the biadjacency matrices. This privacy mechanism has been used in the analysis of mean estimation (e.g. 13], nonparametric density estimation [e.g. 13, 25J and exact support recovery (e.g. 8] problems under L.P.
T.n1 Given data {A(1){=1 C {0, 1) X let (U1,1St11imm be independent Unif[O, 1] random variables that are independent of {A(())== and let {Aig (t) ( T
1,ا- be random variables satisfying
(t) = 114,(()) = Pf (f) 11A = +1+ Ang (t))/2
Let
1 2n2 (n2 1)
122 mod 2 =
B == 11)(6= with Cz
12
12 momd? 2 = 0.
2
(2222)
The privatised data (A'(t)) {0, 10m1 are obtained by sampling
Unif E (B. BB) Σド= 2, (1)())) 2 0), Un (e,se((1te)))
(t(t)
(1I)
- Unil E ( -B) プド= A:5(() < 50); otherwise.
Note that (t)loo = 1 for any i= I...., and t = L.... T. Applying (26) in [13] with d = n2 guarantees that (t( is an a-private version (t) and therefore satisfies the bipartite node a-LDP constraint. In Theorem 4, we demonstrate that NBS with inputs obtained through (11) is consistent in localising change points under bipartite node a-LDP constraint.
Theorem 4. Let {A(t))T= and (B(t)) be two independent sequences of biadjacency matrices satisfying Assumption I. For an arbitvarily small & > O and an absolute constant Co > O, assume that
xap² min /n//////nnn n1/122 nı na/n))Aa² 2 log (Tning).
(12)
Let {Nk R be the output of the NBS algorithm with inputs:
A'tt)] and (B) privatised version of { [A(t) and (B(t))T=1 obtained through (11);
(am pm M mm random intervals whose end points are drawn independently and uniformly from
{1..... T} such that Max (8m am) S CRA, for some constant CR >> 3/2; and tuning
parameter т satisfying nnzaa log (Tn1n2) max { /1n12, n2] < T c2ngurn2p A, where C1,02 > 0 are absolute constants.
It holds with probability at least 1 - exp(log(T/A) - -xp(log(7/A)-cMMAA/ - TT
that R = K and
K max TM mhl S co (og((1)22))
VA
log log(Tnin2)
122
n2
max
Kopa
ni
where c3 C4, C5, Co > are absolute constants.
Theorem 4 shows that, provided M 2 TA- log(//A), NBS with privatised inputs through channel (11) is consistent. When 72 x 1, the signal-to-noies ratio condition (12) and the infeasibility regime (7) demonstrate phase transition with boundary 2 Aa 1, up to logarithmic factor. When 12 is allowed to diverge, a gap between the infeasibility regime (7) and (12) - the regime where proposed method is deemed to be consistent emerges. The larger n2 is, the larger the gap is. It is interesting to understand further what happens within the gap and we leave this as an open problem, which echos the challenging problems in high- figgh-dmensional statistical inference under LDP.
1/2
Despite this open problem, we would like to point out that the condition (12) already exhibits some fundamental difference between change point localisation and mean estimation problems. To make this clear, we simplify the model by considering only one change point occurs A and set 71 n2 n. Then, for each E (I....,n), {t)
can be regarded as A i.id random vectors
8

---

satisfying that Aty(t) ~ Ber(O,y). Let 8, = [8,)),ー1 E [0, 10. The fundamental limit of estimating 0e is studied in [14]. With A iid samples, their Corollary gives
inf privacy mechanism Q
inf sup B|@ 0:112 ž n n²/(aa²); Po.
(13)
when a < 1. Now, write {0 for the row means of the distribution after the change point and we have [E{A(A)} - E{A(A + .2 natural expect one needs Σi=1 0 0, n² /Aaa)) in order detect the change point at A. However, under the same setup, Theorem 4 shows that consistent change point localisation can be achieved under (12), read - 10, 0,11 Z n²² ((/(a)), up logarithmic factors.
H - |0 0..12. Aggregating (13) over 1,... it is
This discrepancy between n² and n² suggests that the gap between our upper bound and lower bound cannot be closed by straightforwardly applying techniques designed for establishing lower bounds in mean estimation problems. It also illustrates the general wisdom in the change point literature that, one may afford sacrifice some accuracy in estimating the underlying distributions, if the goal is just to estimate the change points [c.g. 32].
To conclude this section, would like to present
result of independent interest. It is studied in the existing literature [Appendix I.3 13] that the privatised output from (11) is unbiased, Le. (t) = (t), while the covariance structure of the privatised output is unknown. In Lemma 5, we carefully analyse the covariance matrix of the privatised output and provide an upper bound its operator norm. Due to its independent interest, we denote the raw data vector as
V = (V:) E R2 and denote its privatised output obtained through (11) as Z = (Z+) E Rdd
Lemma 5. For any random vector V E Idd with ||V| S 1, we have that
Var (Z.) = B² {E(V))? i = 1=....d; d;
(14)
and
Cov( 22) = - B(V.)E(3)) Cao BVV))
mod 2 = 1,
Vi
(15)
2013 CAC B(VV,),
d mod 2 0,
where where Ca |Co, Ci) for some absolute constants C1 Co 0. Letting Ez be the covariance matrix of Z, it holds that
B² + E(V)
d mod? 1
E2 S
(16)
B2 BBV
oVd /maxi, IV(VV)))
d mod 2 = 0,
oF where c is absolute constant.
5 Conclusion
In this paper, we studied network change point localisation problems under two forms of LDP constraints. New signal-to-noise conditions (9) and (12) are derived and by comparing with the non private counterpart, we quantify the cost of privacy as discussed in Sections 3 and 4. A change in the scaling of sparsity parameter the private signal noise conditions reveals a new challenge of learning dynamic networks with possibly sparse and correlated entries. The results are summarised the table below, where for clarity we ignored logarithmic factors and consider ni = 112 = the bipartite node LDP case.
No privacy [38] Edge LDP ((6)&(9))
Node LDP lower bound (7)
Node LDP upper bound (12)
<302
NZP S Vmdaa
ripp 2 An
As for limitations, we have only considered non-interactive privacy mechanisms so far, and it would be interesting to further consider interactive ones. This could take two possible routes by including interactive mechanisms in the lower bound considerations and/or designing interactive mechanism

---

that improves on the current upper bound. Both directions present some challenges. From the lower bound perspective, even in our analysis of non-interactive mechanisms. we identify technical challenge in controlling the <<-divergence between mixtures of private distributions. Although some techniques have been developed for discrete distributions [e.g. 4, 1], the counterpart for high- dimensional discrete distributions is still largely unexplored. As for the upper bound, different entries in our network model follow different distributions, which is in sharp contrast to the usual i.i.d. case where interactive methods may be helpful. We therefore expect that allowing interaction within networks cannot improve the signal to noise ratio condition, while interaction across time points requires novel methodology that handle temporal dependence, account for the decay of privacy and is suitable for the task of change point localisation. We leave that as our future work.
Acknowledgements and Disclosure of Funding
The authors would like thank Harry Giles for helpful discussion and suggesting the idea behind the proof of Theorem 3. TBB acknowledges the support of an Engineering and Physical Sciences Reseach Council (EPSRC) New Investigator Award EP/W016117/1. YY acknowledges the support of an EPSRC Standard Grant EP/VO13432/1.
10

---

References
[1] Acharya, J., Canonne, C. L. and Tyagi, H. [2020]. 'Inference under information constraints i: Lower bounds from chi-square contraction', IEEE Transactions Information Theory 66(12), 7835-7855.
[2] Asratian, S., Denley, T. M. and Häggkvist, R. [1998), Bipartite graphs and their applications, Vol. 131, Cambridge university press.
[3] Athreya, A., Fishkind, D. E., Tang. M., Priebe, C. E., Park, Y., Vogelstein, J. T., Levin, K., Lyzinski, V. and Qin, Y. [2017], 'Statistical inference random dot product graphs: a survey', The Journal of Machine Learning Research 18(1), 8393-8484.
[4] Berrett, T. B. and Butucea, C. [2020], 'Locally private non conasymptotic testing of discrete distributions is faster using interactive mechanisms', Advances Neural Information Processing Systems 33, 3164-3173.
[5] Berrett, T. B. and Yu, Y. [2021], 'Locally private online change point detection', Advances in Neural Information Processing Systems 34, to appear.
[6] Bright, D. A. and Delaney, J. J. [2013], 'Evolution of a drug trafficking network: Mapping changes in network structure and function across time', Global Crime 14(2-3), 238-260.
[7] Butucea, C., Dubois, A., Kroll, M. and Saumard, A. [2020], 'Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids' BBernoulli 26(3), 1727- 1764.
[8] Butucea, C., Dubois, A. and Saumard, A. [2020], 'Sharp phase transitions for exact support recovery under local differential privacy', arXiv preprint arX11:2011.14881
[9] Chang, J., Hu, Q., Kolaczyk, E. D., Yao, Q. and Yi, F. [2021]. 'Edge differentially private estima- tion in the beta -model via jittering and method of moments', arXivv preprint arXiv:21
[10] Cribben, I. and Yu, Y. [2017], "Estimating whole-brain dynamics by using spectral clustering', Journal of the Royal Statistical Society: Series C (Applied Statistics) 66(3), 607-627.
[11] Day, W.-Y., Li, N. and Lyu, M. [2016), Publishing graph degree distribution with node differ- ential privacy, in "Proceedings of the 2016 International Conference Management of Data', pp. 123-138.
[12) Duchi, J. C., Jordan, M. I. and Wainwright, M. J. [2013], 'Local privacy, data processing inequalities, and statistical minimax rates", arXiv preprint arXiv: 1302.3203.
[13] Duchi, J. C., Jordan, M. I. and Wainwright, M. J. [2018]. 'Minimax optimal procedures for locally private estimation', Journal of the American Statistical Association 113(521), 182-201.
[14] Duchi, and Rogers, [2019], Lower bounds for locally private estimation via communication complexity, in "Conference on Learning Theory', PMLR, pp. 1161-1191.
[15] Dwork, C., Roth, A. al. [2014], "The algorithmic foundations of differential privacy.', Found. Trends Theor. Comput. Sci. 9(3-4), 211-407.
[16] Erdös, P. and Rényi, A. [1959], 'On random graph', Publicationes Mathematicate 6, 290-297.
[17] Erlingsson, Ú. Pihur, V. and Korolova, A. [2014], 'Rappor: Randomized aggregatable privacy- preserving ordinal response', Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security pp. 1054-1067.
[18] Holland, P. W., Laskey, K. B. and Leinhardt, S. [1983], 'Stochastic blockmodels: First steps', Social networks 5(2), 109-137.
[19] Imola, J., Murakami, and Chaudhuri, [2021], Locally differentially private analysis of graph statistics, in '30th USENIX Security Symposium (USENIX Security 21)', pp. 983-1000.
11

---

[20] Ju, C. and Xu, C. [2014], 'Personal recommendation via heterogeneous diffusion on bipartite
network', International Journal on Artificial Intelligence Tools 23(03), 1450003.
[21] Karwa, V., Raskhodnikova, S., Smith, A. and Yaroslavtsev, G. [2014], 'Private analysis of graph structure', ACM Transactions on Databuse Systems (TODS) 39(3). 1-33.
[22] Karwa, V. and Slavković, A. [2016], 'Inference using noisy degrees: Differentially private 3-model and synthetic graphs', The Annals of Statistics 44(1), 87-112.
[23] Kasiviswanathan. S. P., Nissim, K., Raskhodnikova, S. and Smith, A. [2013], Analyzing graphs with node differential privacy, 'Theory of Cryptography Conference', Springer, pp. 457-476.
[24] Levy, D., Sun, Z., Amin, K., Kale, S., Kulesza, A., Mohri, M. and Suresh, A. T. [2021], 'Learning with user-level privacy', Advances in Neural Information Processing Systems 34.
[25] Li, M., Berrett, T. B. and Yu, Y. [2022], 'On robustness and local differential privacy', arXiv preprint arXiv:2201.00775
[26] Lin, W., Li, B. and Wang, C. [2022], "Towards private learning on decentralized graphs with local differential privacy', arXiv preprint arXiv:2201.09338.
[27] Liu, J., Shang, M. and Chen, D. [2009], Personal recommendation based on weighted bipartite networks, in '2009 sixth international conference on fuzzy systems and knowledge discovery'. Vol. 5, IEEE, pp. 134-137.
[28] Malik, N., Bookhagen, B., Marwan, N. and Kurths, J. [2012], 'Analysis of spatial and tempo- ral extreme monsoonal rainfall over south asia using complex networks', Climate dynamics 39)3,, 971-987.
[29] Mancho-Fora, N., Montalå-Flaquerr M., Perman-errm,nyer, L.., Haraaooo- D., Gallardo- Moreno, G. B., Gudayol-Farre F.,, Peró-Cebollero, M. and Guàrdia-Olmos, J. [2020], 'Network change point detection in resting-state functional connectivity dynamics of mild cognitive impairment patients', International Journal of Clinical and Health Psychology 20(3), 200-212.
[30] Mohamed, M. S., Nguyen, D., Vullikanti, A. and Tandon, [2022], Differentially private community detection for stochastic block models, in 'International Conference on Machine Learning', PMLR, pp. 15858-15894.
[31] Onnela, J.PP., Saramäki, J., Hyvönen, J., Szabó, G., Lazer, D., Kaski, K., Kertész, J. and Barabási, A.-L. [2007], 'Structure and tie strengths in mobile communication networks". Proceedings of the national academy of sciences 104(18), 7332-7336.
[32] Padilla, O. H. M., Yu, Y., Wang, D. and Rinaldo, A. [2021], 'Optimal nonparametrie multivariate change point detection and localization', IEEE Transactions on Information Theory. -
[33] Potterat, J., Phillip-Pluummer, L., Muth, S. Q., Rothenberg, R., Woodhouse, D., Maldonado- Long, T., Zimmerman, H. and Muth, J. [2002]. 'Risk network structure in the early epidemic phase of hiv transmission in colorado springs'. Sexually transmitted infections 78(suppl 1), i159... i163.
[34] Qin, Z., Yu, T., Yang. Y., Khalil, I., Xiao, X. and Ren, K. [2017], Generating synthetic decentralized social graphs with local differential privacy, in 'Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security', pp. 425-438.
[35] Rocha, L. E., Liljeros, F. and Holme, P. [2010], 'Information dynamics shape the sexual networks of internet-mediated prostitution', Proceedings of the National Academy of Sciences 107(13), 5706-5711.
[36] Rohde, A. and Steinberger, L. [2020], 'Geometrizing rates of convergence under local differen- tial privacy constraints', The Annals of Statistics 48(5), 2646-2670.
[37] Tao, J. and Michailidis, G. [2019], 'A statistical framework for detecting electricity theft activi- ties in smart grid distribution networks", IEEE Journal on Selected Areas Communications 38(1) 1), 205-216.
12

---

[38] Wang, D., Yu, Y. and Rinaldo, A. [2021], 'Optimal change point detection and localization in sparse dynamic networks', The Annals of Statistics 49( 203-232.
[39] Warner, S. L. [1965], 'Randomized response: A survey technique for eliminating evasive answer bias', Journal of the American Statistical Association 60, 63-69.
[40] Wei, C.,, Ji, S., Liu, C., Chen, W. and Wang, T. [2020], 'Asgldp: collecting and generating de- centralized attributed graphs with local differential privacy', IEEE Transactions on Information Forensics and Security 15, 2239-3255
[41] Yu, [1997], Assouad, Fano, and Le Cam, 'Festschrift for Lucien Le Cam', Springer, 423-435.
[42] Zhang. H., Latif, S., Bassily, R. and Rountev, A. [2020], Differentially-private control-flow node coverage for software usage analysis, 'USENIX Security Symposium (USENIX Security)'
[43] Zhou, M., Wang, T., Chan, H., Fanti, G. and Shi, E. [2021], 'Locally differentially private sparse vector aggregation', arXiv preprint arXiv:2112.03449
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See e.g. Section 3 and Section 4.
(b) Did you describe the limitations of your work? [Yes] See e.g. Section 4.2 and Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All theoretical results are stated with clear assumptions including Lemma 1, Lemma 2, Theorem 3, Theorem and Lemma 5.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are collected in supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] Code is available on openreview.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A in the supplementary material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We report the median
substitute.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The computation is not intensive and therefore we do not see the need specify the details.
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
13

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "_O_8NHs8Y6", "reviewer": "Reviewer_jC5X", "summary": "In this paper, the authors consider consistently localizing change points under both node and edge local differential privacy (LDP). The authors proposed an algorithm under edge LDP that is shown to be optimal. For node LDP, the authors show there is a gap exists between upper and lower bounds.", "questions": "Q1. Is it possible to provide some empirical evaluation since you have provided an algorithm?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nS1. The work seems solid. I didn't check for all the technical details, but the formal definitions and results seem to be finished well.\nS2. The authors provide theoretical results to the problems.\n\nWeaknesses:\nW1. I did not fully get the reason why we should focus on these problems. I can understand network data is important, but I do not see why we focus on these two network models. The paper could benefit from better motivating why these problems are important in practice, more concrete examples of the two network definitions, and how close these two definitions model real-world scenarios.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VCIBL4GbXDu", "reviewer": "Reviewer_u65C", "summary": "The paper looks the problem of finding change point of networks sequences for two networks under edge and node LDP. For each setting, it shows the feasible regime and an algorithm that guarantee LDP.", "questions": "I mainly have some questions regarding the setup.\n\n- I'm a bit confused by Assumption 1 & 2. I think they define the change point and some properties of the change point for the two networks. But isn't there a unified definition for any network? Why would we need two? (And, why are they \"assumption\" not \"definition\"?)\n\n- Line 118 says we want the estimated change points to be close to the actual change points as sample size T grows. Is that under the assumption that the number of change points K does not grow with T?\n\n- I think $A$ is used for both the adjacency matrix and the set $A \\subset Z$. Maybe you can considering change the notation.\n\n- For the privacy definitions in Section 2\n  - what is Q? If it is a mechanism (as is stated in Line 144), I feel like its should be a function that operate on the input so the expression should be something like Z = Q(X)? But the way it is used in the formula make it seems like some probability measure.\n  - what is X? Is that the adjacency matrix (so the same as A in Section 1)? And what is $X_i$? Is that one row of the adjacency matrix?\n  - Regarding the edge-LDP definition:\n    - You mentioned that some prior work is looking at $X_i$ instead of $X_{ij}$ and it requires trust between nodes. I didn't follow that part. Does that refer to the case where user $i$ is supposed to privatize the edge (or lack of edge) between $i$ and $j$? But if so, wouldn't (3) also have the same problem?\n    - I don't quite follow the definition. I think what you mean is that for user i, even if every {i, j} changes, we would still be able to hide the change. But if so, isn't that the same as node-LDP?", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper looks at an important problem which hasn't been worked on before.\n\nWeakness: The privacy definitions is a bit hard to follow.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ls1YITo1ECa", "reviewer": "Reviewer_3623", "summary": "This paper studies the problem of change detection (or change point localization as mentioned by the authors) in dynamically evolving graphs subject to differential privacy. Focusing on two generative models, namely, inhomogeneous Bernoulli networks (IBNs) and bipartite IBNs, conditions are provided under which change localization is infeasible. Subsequently, a simple randomized response mechanism is studied (applied together with CUSUM type statistic for change detection) and analyzed. ", "questions": "See comments above", "limitations": "Yes, limitations were appropriately discussed. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ This is a technically strong and very well written paper, which I enjoyed reading. I very much appreciated the care taken by the authors in describing the similarities/differences in techniques which they borrowed/adapted from prior works. In addition, some of the discussions along with the technical results (such as impact of privacy constraints on the graph sparsity) were quite intriguing. Overall, I believe this could be a useful contribution to the broader ML community working on the area of privacy preserving graph based algorithms. \n\nSome minor weaknesses and suggestions for the authors:\n\n- While I understand that this is a theoretically oriented paper, and the technical results are solid, I would have still liked to see some numerical results to actually see the finite sample performance of the proposed algorithm (RR + CUSUM) on some dynamic networks in practice.  \n\n- I would like to point out a somewhat related work on \"Differentially Private Community Detection For Stochastic Block Models\", ICML 2022, which also derives some tradeoffs between privacy and the phase-transition boundary (for community recovery). In contrast to the conclusions of this submission (which show that RR is almost optimal for edge LDP), the above reference shows that RR may not be a good choice for private community detection with edge DP, as it significantly increases the average node degree (and other mechanisms, such as exponential, and stability based methods can fare better and provide a better privacy-recovery tradeoff). This is a complementary viewpoint, which authors may wish to discuss in the paper, i.e., what (if any) are the limitations of RR based perturbations. \n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0TLJBwgDntU", "reviewer": "Reviewer_vH7B", "summary": "This paper studies the problem of change point detection in sequences of networks/graphs with respect to local differential privacy constraints (respectively edge and node LDP). Under assumptions on the random structure of the graphs (IBN for instance), the authors establish minimax rates for change point detection using Le Cam’s method. Then, the authors show that using randomized response to obtain edge privacy alongside the NBS algorithm obtains the minimax rate for change point detection. The authors show similar results for node LDP for bipartite IBNs.", "questions": "As aforementioned, it may be valuable to introduce an informal theorem for your main results in the introduction of the paper. Other questions and comments can be found above.", "limitations": "The authors discuss the limitations of their paper in the conclusion. In particular, they point out that their paper and arguments do not go through in the setting of interactive LDP. Investigating the problem in this setting seems important, especially for network data where one would expect the edge/node inclusion probabilities to be correlated.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: To the best of my knowledge this problem has not been attempted before. Moreover, the need for edge/node LDP is clearly presented in the paper with practical examples. The problem is concisely contained, as both lower and upper bounds rates are presented for the change point estimation. The paper was clearly presented, although presenting the key results/rates as an informal theorem e.g. in the introduction may be useful. There is also thorough discussion in the conclusion of why the techniques do not generalize to the interactive setting.\n\nWeaknesses: The problem discussed and approaches used in the paper are not particularly novel, as the paper is concerned with taking existing statistical procedures and studying them in through the lens of (local) privacy. Moreover, it would be interested to have some experimentation to demonstrate the empirical performance of these estimators when being run on privatized networks. Lastly, the random structure assumed on the families of graphs (IBN, bipartite IBN) seems somewhat restrictive, especially when considering practical network data (e.g. is it realistic to assume that networks connections are independently generated?). Is there a way to incorporate correlation between the network edge indicators into this result (outside of that included in the bipartite IBN)?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept