the proof of privacy for the black-box framework described in Algorithm 5.

######  Lemma 4.3 (Properties of $\mathsf{DistToGraph}$).

$\mathsf{DistToGraph}_{D,\ell}$ has the following properties:

  1. 1.

$\mathsf{DistToGraph}_{D,\ell}$ has node-sensitivity 1.

  2. 2.

For an input graph $G$ with $|V|$ nodes and $|E|$ edges,
$\mathsf{DistToGraph}_{D,\ell}$ can be computed in time $O(|V|+|E|)$.

Furthermore, given a graph stream $\mathit{S}$, one can determine the sequence
of distances for all prefixes of the stream, online. With each node or edge
arrival, the distance can be updated in constant time.

  3. 3.

Let $G\in\mathcal{G}$ be a $(D,\ell)$-bounded graph (i.e., with at most $\ell$
nodes of degree greater than $D$). Then
$\mathsf{DistToGraph}_{D+k,\ell+k}(G)\geq k$ for all
$k\in\mathbb{N}\cup\\{0\\}$.

###### Proof of Lemma 4.3.

Proof of item (1). $\mathsf{DistToGraph}_{D,\ell}$ is defined in terms of the
minimum number of nodes to add, so changing the graph by one node will change
$\mathsf{DistToGraph}_{D,\ell}$ by at most 1.

Proof of item (2). We first describe a method for computing
$\mathsf{DistToGraph}_{D,\ell}$ and prove this method’s correctness, and then
describe an efficient implementation. Given a graph $G\in\mathcal{G}$,
$\mathsf{DistToGraph}_{D,\ell}(G)$ can be computed as follows: first, check if
$G$ is $(D,\ell-1)$-bounded. While that condition is satisfied, add a node to
$G$ with edges incident to all existing nodes and check
$(D,\ell-1)$-boundedness again. Return the number of nodes that have been
added to $G$ when the check first fails.

We prove that the quantity returned by this method is equal to
$\mathsf{DistToGraph}_{D,\ell}(G)$. First, observe that the method cannot
underestimate the distance since, for the number $\hat{k}$ it outputs, there
is actually a graph within node distance $\hat{k}$ of $G$ that is not
$(D,\ell)$-bounded. To see why the method never overestimates the distance,
suppose $\mathsf{DistToGraph}_{D,\ell}(G)=k$, and let $H$ be a graph with at
least $\ell$ nodes of degree greater than $D$ that is closest to $G$ in node
distance. $H$ can be formed by removing some set of nodes $B$ (and associated
edges) from $G$ and adding some set of nodes $A$ (and associated edges) such
that $|A|+|B|=k$. Now consider the graph $H^{\prime}$ which is formed by
taking $G$, adding all nodes in $A$ (along with the associated edges), and
adding edges from every node in $A$ to all other nodes in the graph that do
not already have an edge from that node. We do not delete the nodes and edges
that are in $B$. $H$ is a subgraph of $H^{\prime}$, so if $H$ has at least
$\ell$ nodes of degree greater than $D$, then $H^{\prime}$ also has at least
$\ell$ nodes of degree greater than $D$. Additionally, $H^{\prime}$ is exactly
the graph that will be formed by the method described above after at most $k$
steps. Finally, $H^{\prime}$ is node distance $|A|\leq k$ from $G$, and
$\hat{k}=|A|$ is the output returned by this method.

Naively, an algorithm for the above method can be implemented by storing a
graph in memory and manipulating this graph with every pass through the while
loop. However, storing the entire graph is not necessary. There is a linear-
time algorithm that computes the same quantity as the method described above.
To see why that is, let $|V|$ be the number of nodes in $G$. After adding $j$
nodes that have edges to all other nodes, the number of nodes with degree
greater than $D$ will be 0 if $D\geq|V|+j-1$ (a graph with $|V|+j$ nodes has
maximum degree $|V|+j-1$); and will otherwise be the number of nodes in $G$
with degree greater than $D-j$, plus $j$. Therefore, it suffices to maintain a
_cumulative degree histogram_ ${\mathsf{ch}_{G}{\left({\cdot}\right)}}$, which
we define below, and compute a value based on that.

Let ${\mathsf{ch}_{G}{\left({j}\right)}}$ hold the number of nodes in $G$ with
degree at least $j$, and let ${\mathsf{ch}_{G}{\left({\cdot}\right)}}$ have
buckets for $j\in{\left\\{{0,\ldots,D+1}\right\\}}$. Given this cumulative
degree histogram, we return _the smallest value of
$j\geq\max{\left\\{{D-|V|+2,0}\right\\}}$ such that_

$j+{\mathsf{ch}_{G}{\left({D-j+1}\right)}}\geq\ell\,.$ (3)

Call this smallest such value $k$. We now show that, when a new node or edge
arrives, we can update the value of $k$ in constant time. To do this, we
maintain the following data structures: a hash table $H$ for node degrees that
takes a node name as input and returns its degree (we assume unassigned values
in the hash table are set to 0); a hash table $C$ for the cumulative histogram
that takes an integer $i$ as input and returns the number of nodes with degree
at least $i$; a counter $n$ that tracks the number of nodes in the graph,
initialized to 0; and the current value $k$ of
$\mathsf{DistToGraph}_{D,\ell}(G)$, which we initialize to
$k=\max{\left\\{{D+2,\ell}\right\\}}$ when the graph is empty (since every
node in a complete graph on $D+2$ nodes has degree greater than $D$, but
$\ell$ nodes are needed for a non-$(D,\ell)$-bounded graph when $\ell>D+2$).

We first show that $H,C,n$ can be updated in constant time when a new node or
edge is added to $G$. When a new node $v$ arrives, set $H(v)=0$,
$C(0)\mathrel{+}=1$, and $n\mathrel{+}=1$. When a new edge
${\left\\{{u,v}\right\\}}$ arrives, set $H(u)\mathrel{+}=1$ and
$H(v)\mathrel{+}=1$, and then set $C(H(u))\mathrel{+}=1$ and
$C(H(v))\mathrel{+}=1$.

We next show that the value of $k$ (i.e., the smallest value of $j$ such that
(3) is satisfied) can be updated in constant time, assuming $H$ and $C$ are up
to date. Recall that $k$ is the value of $\mathsf{DistToGraph}_{D,\ell}$ that
we want to update, and that this function has node sensitivity 1. This means
that adding a node can change $k$ by at most 1, and that adding an edge can
change $k$ by at most 2 since every graph with an edge $e$ is node distance at
most 2 from a graph without $e$ (an edge $e$ has a vertex cover of size 1, so
to obtain an otherwise identical graph without that edge requires at most
removing a vertex incident to $e$ and then re-adding the vertex without $e$).
Moreover, the value of $k$ cannot increase as nodes and edges are added since
the old graph is a subgraph of the updated graph, so the new graph can be no
further from a non-$(D,\ell-1)$-bounded graph than the old graph. Therefore,
it suffices to check, for $k^{\prime}\in{\left\\{{k,k-1,k-2}\right\\}}$
whether $k^{\prime}+C(D-k^{\prime}+1)\geq\ell$ and
$k^{\prime}\geq\max{\left\\{{D-n+2,0}\right\\}}$, and then set $k$ to the
smallest value $k^{\prime}$ for which these conditions hold.

Since all of the updates to $H$, $C$, $n$, and $k$ in response to the arrival
of a node or edge are constant-time operations,
$\mathsf{DistToGraph}_{D,\ell}(G)$ can be computed in time $O(|V|+|E|)$ for a
graph $G=(V,E)$.666This linear-time algorithm assumes that the graph stream
does not contain duplicate edges; to remove this assumption, a check for
whether an edge is a duplicate can be performed in constant time (and that
edge can then be ignored).

Proof of item (3). We know from the proof of item (2) that the shortest
sequence of node-neighboring graphs, from $G$ to the closest graph with at
least $\ell$ nodes of degree greater than $D$, consists of sequentially adding
nodes to $G$ that have all possible edges. Adding one node $v^{+}$ to $G$
increases the degree of each node in $G$ by at most 1. Additionally, the added
node $v^{+}$ may have degree greater than $D$. Thus, if $G$ is
$(D,\ell)$-bounded, then adding one node yields a graph $G^{+}$ that is
$(D+1,\ell+1)$-bounded. The claim follows by induction on the number of added
nodes. ∎

###  4.2 PTR in the Continual Release Setting

The high-level idea of our general transformation is to use a novel, online
variant of the Propose-Test-Release framework (PTR) of [DL09]. To our
knowledge, PTR has not been used previously for designing algorithms in the
continual release setting. In this section, we show that PTR can, in fact, be
applied in the continual release setting when the algorithm checking the
safety condition is itself private under continual observation, as is the
sparse vector algorithm.

######  Theorem 4.4 (Privacy of PTR under Continual Observation).

Let $\mathsf{Base}:\mathcal{X}^{T}\to\mathcal{Y}^{T}$ be a streaming algorithm
and $\mathcal{Z}\subseteq\mathcal{X}^{T}$ a set of streams such that, for all
neighbors $\mathit{S},\mathit{S}^{\prime}\in\mathcal{Z}$,
$\mathsf{Base}(\mathit{S})\approx_{\varepsilon_{\mathsf{Base}},\delta_{\mathsf{Base}}}\mathsf{Base}(\mathit{S}^{\prime})$.

Let $\mathsf{Test}:\mathcal{X}^{T}\to\\{\bot,\top\\}$ be
$(\varepsilon_{\mathsf{Test}},\delta_{\mathsf{Test}})$-DP under continual
observation such that for every stream $\mathit{S}$, if there is a time $t$
such that $\mathit{S}_{[t]}$ does not equal the $t$-element prefix of any item
in $\mathcal{Z}$, then $\mathsf{Test}(\mathit{S})$ outputs $\bot$ w.p. at
least $1-\beta_{\mathsf{Test}}$ at or before time $t$.

If Algorithm 4 is initialized with $\mathsf{Test}$ and $\mathsf{Base}$, it
will satisfy $(\varepsilon,\delta)$-DP under continual observation on all
input streams $x\in\mathcal{X}^{T}$, for

$\varepsilon=\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}}\quad\text{and}\quad\delta=\delta_{\mathsf{Base}}+(1+e^{\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}}})\delta_{\mathsf{Test}}+(1+e^{\varepsilon_{\mathsf{Test}}})e^{\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}}}\beta_{\mathsf{Test}}.$

Algorithm 4 Algorithm $\mathsf{PTR}$ for propose-test-release under continual
observation.

1:Input: Stream $x\in\mathcal{X}^{T}$, streaming algorithms
$\mathsf{Test}:\mathcal{X}^{T}\to\\{\bot,\top\\}^{T}$ and
$\mathsf{Base}:\mathcal{X}^{T}\to\mathcal{Y}^{T}$.

2:Output: Stream in $(\\{\bot,\top\\}\times\\{\mathcal{Y},\bot\\})^{T}$.

3:$\mathsf{passed}\leftarrow\mathit{True}$

4:$b_{0}\leftarrow$ initial state of $\mathsf{Base}$

5:$s_{0}\leftarrow$ initial state of $\mathsf{Test}$

6:for all $t\in[T]$ do

7: $(\mathsf{verdict},s_{t})\leftarrow\mathsf{Test}(x_{t};s_{t-1})$
$\triangleright$ Send $x_{t}$ to $\mathsf{Test}$, and set $\mathsf{verdict}$
to be its output

8: Output $\mathsf{verdict}$

9: if $\mathsf{verdict}=\bot$ then $\mathsf{passed}\leftarrow\mathit{False}$

10: if $\mathsf{passed}=\mathit{True}$ then

11: $(y_{t},b_{t})\leftarrow\mathsf{Base}(x_{t};b_{t-1})$ $\triangleright$
Send $x_{t}$ to $\mathsf{Base}$ and output the result

12: Output $y_{t}$

13: else output $\bot$

While it is perhaps unsurprising that PTR applies to the continual release
setting, the proof of Theorem 4.4 does not follow immediately from the
standard PTR analysis: the standard analysis is binary (either release the
output of the base algorithm, or don’t), while the version we need releases a
dynamically chosen prefix of the base algorithm’s output.

Note that there is no completeness requirement for $\mathsf{Test}$. Whereas
completeness is useful for accuracy, our proof of privacy only requires
soundness of $\mathsf{Test}$. We now move to the proof of Theorem 4.4.

###### Proof of Theorem 4.4.

Fix two neighboring streams $x$ and $x^{\prime}$ in $\mathcal{X}^{T}$, and let
$t^{*}\in[T]$ be the smallest value such that either
$(x_{1},\ldots,x_{t^{*}})$ or $(x^{\prime}_{1},\ldots,x^{\prime}_{t^{*}})$
does not equal the $t^{*}$-element prefix of any item in $\mathcal{Z}$. (If
there is no such $t^{*}$, just set $t^{*}=T+1$.) We consider the behavior of
Algorithm 4 (denoted $\mathsf{PTR}$) on inputs $x$ and $x^{\prime}$.

To analyze privacy, we also consider the behavior of two hypothetical
algorithms $\widetilde{\widetilde{\mathsf{PTR}}}$ and
$\widetilde{\mathsf{PTR}}$, which we define below. (They are hypothetical
because they have access to the value of $t^{*}$, which is defined with
respect to a pair of neighboring input streams.) We show indistinguishability
relationships between $\mathsf{PTR}(x)$, $\widetilde{\mathsf{PTR}}(x)$,
$\widetilde{\mathsf{PTR}}(x^{\prime})$, and $\mathsf{PTR}(x^{\prime})$; we
then apply the weak triangle inequality for indistinguishability (Lemma 2.12)
to relate $\mathsf{PTR}(x)$ and $\mathsf{PTR}(x^{\prime})$.

Let $\widetilde{\widetilde{\mathsf{PTR}}}$ be the algorithm that releases the
outputs of $\mathsf{Test}$ and $\mathsf{Base}$ at all time steps less than
$t^{*}$, and releases the output of $\mathsf{Test}$ and the symbol $\bot$ at
all time steps at and after $t^{*}$. (In the case that $t^{*}=T+1$, the
algorithm will release the output from $\mathsf{Base}$ at all time steps.) We
see, by the indistinguishability properties of $\mathsf{Test}$ and
$\mathsf{Base}$, that

$\widetilde{\widetilde{\mathsf{PTR}}}(x)\approx_{(\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}},\delta_{\mathsf{Base}}+\delta_{\mathsf{Test}})}\widetilde{\widetilde{\mathsf{PTR}}}(x^{\prime}).$
(4)

We now define another (hypothetical) algorithm, $\widetilde{\mathsf{PTR}}$.
Let $t_{\bot}$ be the first time step at which $\mathsf{Test}$ returns $\bot$,
setting $t_{\bot}=T+1$ if there is no such time step. Note that, whereas
$t^{*}$ is defined with respect to a pair of neighboring inputs, $t_{\bot}$ is
a random variable defined with respect to an execution of $\mathsf{Test}$ on a
particular input. We define $\widetilde{\mathsf{PTR}}$ as the algorithm that
releases the outputs of $\mathsf{Test}$ and $\mathsf{Base}$ at all time steps
less than $\min\\{t^{*},t_{\bot}\\}$, and releases the output of
$\mathsf{Test}$ and the symbol $\bot$ at all time steps at and after
$\min\\{t^{*},t_{\bot}\\}$. Observe that $\widetilde{\mathsf{PTR}}$ is a post-
processed version of $\widetilde{\widetilde{\mathsf{PTR}}}$. By Expression
(4), we get

$\widetilde{\mathsf{PTR}}(x)\approx_{(\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}},\delta_{\mathsf{Base}}+\delta_{\mathsf{Test}})}\widetilde{\mathsf{PTR}}(x^{\prime}).$
(5)

We now compare $\mathsf{PTR}(x)$ and $\widetilde{\mathsf{PTR}}(x)$. Let
$\mathcal{B}$ be the (bad) event that the output from $\mathsf{Base}$ is
released at or after time step $t^{*}$. Without loss of generality, let $x$ be
the stream for which the first $t^{*}$ elements are not equal to the
$t^{*}$-element prefix of any item in $\mathcal{Z}$. Conditioned on
$\mathcal{B}$ not occurring, $\mathsf{PTR}(x)$ and
$\widetilde{\mathsf{PTR}}(x)$ have the same probability distribution of
outputs. The probability of $\mathcal{B}$ is at most $\beta_{\mathsf{Test}}$
for both algorithms $\mathsf{PTR}(x)$ and $\widetilde{\mathsf{PTR}}(x)$, so
$\mathsf{PTR}(x)\approx_{(0,\beta_{\mathsf{Test}})}\widetilde{\mathsf{PTR}}(x)$.
Similarly, by the DP guarantee, $\mathcal{B}$ occurs with probability at most
$e^{\varepsilon_{\mathsf{Test}}}\beta_{\mathsf{Test}}+\delta_{\mathsf{Test}}$
on input $x^{\prime}$, so
$\mathsf{PTR}(x^{\prime})\approx_{(0,e^{\varepsilon_{\mathsf{Test}}}\beta_{\mathsf{Test}})}\widetilde{\mathsf{PTR}}(x^{\prime})$.
Combining this with Expression (5) shows that

$\mathsf{PTR}(x)\approx_{(0,\beta_{\mathsf{Test}})}\widetilde{\mathsf{PTR}}(x)\approx_{(\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}},\delta_{\mathsf{Base}}+\delta_{\mathsf{Test}})}\widetilde{\mathsf{PTR}}(x^{\prime})\approx_{(0,e^{\varepsilon_{\mathsf{Test}}}\beta_{\mathsf{Test}}+\delta_{\mathsf{Test}})}\mathsf{PTR}(x^{\prime})\,.$

Let $\varepsilon=\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}}$ and
$\delta=\delta_{\mathsf{Base}}+\delta_{\mathsf{Test}}+e^{\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}}}(\beta_{\mathsf{Test}}+e^{\varepsilon_{\mathsf{Test}}}\beta_{\mathsf{Test}}+\delta_{\mathsf{Test}})$.
By the weak triangle inequality (Lemma 2.12),
$\mathsf{PTR}(x)\approx_{(\varepsilon,\delta)}\mathsf{PTR}(x^{\prime}).$ Since
this relationship applies for all pairs of neighboring streams $x$ and
$x^{\prime}$, we see that $\mathsf{PTR}$ is
$(\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}},\delta_{\mathsf{Base}}+(1+e^{\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}}})\delta_{\mathsf{Test}}+(1+e^{\varepsilon_{\mathsf{Test}}})e^{\varepsilon_{\mathsf{Base}}+\varepsilon_{\mathsf{Test}}}\beta_{\mathsf{Test}})$-DP,
as desired. ∎

###  4.3 Accuracy and Privacy of Algorithm 5

In Algorithm 5, we present our method for obtaining node-DP algorithms from
restricted edge-DP and restricted node-DP algorithms.

Our algorithm works as follows. Where we set $D^{\prime}=D+\ell$ and
$\ell\approx\frac{\log(T/\delta)}{\varepsilon}$, we initialize $\mathsf{PTR}$
(Algorithm 4) with (1) a $\mathsf{Base}$ algorithm that offers
indistinguishability on neighbors from the set of $(D^{\prime},\ell)$-bounded
graphs and (2) a $\mathsf{Test}$ algorithm that uses sparse vector to ensure
that $\mathsf{DistToGraph}_{D^{\prime},\ell}$ is non-negative (i.e., that the
graph stream is $(D^{\prime},\ell)$-bounded), where $\ell$ is an additive
slack term to account for the error of the sparse vector technique.
Specifically, $\mathsf{Base}$ is the composition of $\text{\sf
RestrictedPrivAlg}_{D^{\prime}}$ with $\Pi^{\text{\tiny BBDS}}_{D^{\prime}}$,
where $\text{\sf RestrictedPrivAlg}_{D^{\prime}}$ satisfies
$D^{\prime}$-restricted edge- or node-DP.

If $\mathsf{Test}$ succeeds, the projection will be stable with high
probability, so we can safely release the result of running $\mathsf{Base}$ on
the projected graph; if $\mathsf{Test}$ fails, the symbol $\bot$ is released.
Algorithm 5 post-processes the outputs from $\mathsf{PTR}$, so it inherits the
privacy properties of $\mathsf{PTR}$. The privacy properties of Algorithm 5,
stated in Theorem 4.1, follow from Theorem 4.4.

Algorithm 5 BBRestrictedToNodePriv for transforming restricted-DP algorithms
to node-DP algorithms.

1:Input: Privacy params $\varepsilon_{\mathsf{Test}}>0$,
$\beta_{\mathsf{Test}}\in(0,1]$; accuracy param $\beta\in(0,1]$; degree bound
$D\in\mathbb{N}$; time horizon $T\in\mathbb{N}$; graph stream
$\mathit{S}\in\mathcal{S}^{T}$; alg RestrictedPrivAlg (see Theorem 4.1 for
possible assumptions on RestrictedPrivAlg).

2:Output: A stream, where each term is $\bot$ or an estimate from
RestrictedPrivAlg.

3:$\tau=-8\ln(1/\beta_{\mathsf{Test}})/\varepsilon_{\mathsf{Test}}$.

4:$\ell={\left\lceil{8\ln(T/(\beta\beta_{\mathsf{Test}}))/\varepsilon_{\mathsf{Test}}}\right\rceil}$.

5:$D^{\prime}=D+\ell$.

6:$\mathsf{Base}=\text{\sf
RestrictedPrivAlg}_{D^{\prime}}\circ\Pi^{\text{\tiny BBDS}}_{D^{\prime}}$
$\triangleright$ $\Pi^{\text{\tiny BBDS}}_{D^{\prime}}$ is Algorithm 1 with
$\mathsf{c}=\mathit{original}$

7:for all $t\in[T]$ do

8:
$q_{t}(\cdot)=-1\cdot\mathsf{DistToGraph}_{D^{\prime},\ell}(\mathsf{flatten}({\
\cdot\ }_{[t]}))$

9:$\mathsf{Test}=\begin{cases}\mathsf{SVT}\text{ with privacy param
$\varepsilon_{\mathsf{Test}}$,}\\\ \text{\ \ thresh $\tau$, queries
$q_{1},\ldots,q_{T}$}\end{cases}$

10:$s_{0}\leftarrow$ initial state for $\mathsf{PTR}$

11:Initialize $\mathsf{PTR}$ with algorithms $\mathsf{Test}$ and
$\mathsf{Base}$

12:for all $t\in[T]$ do

13:
$(\mathsf{Test\text{-}val},\mathsf{Base\text{-}val},s_{t})\leftarrow\mathsf{PTR}(\mathit{S}_{t};s_{t-1})$

14: Output $\mathsf{Base\text{-}val}$ $\triangleright$
$\mathsf{Base\text{-}val}$ will be $\bot$ once the test fails

We now prove Theorem 4.1, which we repeat below for convenience.

See 4.1

###### Proof of Theorem 4.1.

We prove each part below.

Proof of items (1) and (2) in Theorem 4.1. To prove items (1) and (2), we
break our proof into the following claims about $\mathsf{Test}$ and
$\mathsf{Base}$ as initialized in Algorithm 5, with the parameters specified
in the statement of Theorem 4.1. Once we have shown the claims, the privacy
properties follow immediately from Theorem 4.4.

Claim 4.5 deals with the indistinguishability properties of $\mathsf{Base}$.
Claim 4.6 deals with the privacy of $\mathsf{Test}$, as well as its failure
probability: where $t$ is the first time step for which the input is not
$(D^{\prime},\ell)$-bounded, $\mathsf{Test}$ outputs $\bot$ at or before time
step $t$ with probability at least $1-\beta_{\mathsf{Test}}$. Below, we use
the term _$(D^{\prime},\ell)$ -restricted privacy_ to refer to
indistinguishability for neighbors drawn from the set of graphs with at most
$\ell$ nodes of degree greater than $D^{\prime}$.

######  Claim 4.5 (Indistinguishability of $\mathsf{Base}$).

Let $\mathsf{Base}$ be parameterized as in Algorithm 5. If $\mathit{S}$ and
$\mathit{S}^{\prime}$ are node-neighboring datasets that are both
$(D^{\prime},\ell)$-bounded, then
$\mathsf{Base}(\mathit{S})\approx_{\varepsilon_{\mathsf{Base}},\delta_{\mathsf{Base}}}\mathsf{Base}(\mathit{S}^{\prime})$
for the following values of $\varepsilon_{\mathsf{Base}}$ and
$\delta_{\mathsf{Base}}$:

  1. 1.

If $\text{\sf RestrictedPrivAlg}_{D^{\prime}}$ satisfies
$D^{\prime}$-restricted $(\varepsilon^{\prime},\delta^{\prime})$-edge-DP, then

$\varepsilon_{\mathsf{Base}}=\varepsilon^{\prime}\cdot{\left({D^{\prime}+\ell}\right)}\quad\text{and}\quad\delta_{\mathsf{Base}}=\delta^{\prime}\cdot
e^{\varepsilon_{\mathsf{Base}}}\cdot{\left({D^{\prime}+\ell}\right)}.$

  2. 2.

If $\text{\sf RestrictedPrivAlg}_{D^{\prime}}$ satisfies
$D^{\prime}$-restricted $(\varepsilon^{\prime},\delta^{\prime})$-node-DP, then

$\varepsilon_{\mathsf{Base}}=\varepsilon^{\prime}\cdot{\left({2\ell+1}\right)}\quad\text{and}\quad\delta_{\mathsf{Base}}=\delta^{\prime}\cdot
e^{\varepsilon_{\mathsf{Base}}}\cdot{\left({2\ell+1}\right)}.$

###### Proof of Claim 4.5.

Let $\mathit{S}$ and $\mathit{S}^{\prime}$ be node-neighboring graph streams
that are $(D^{\prime},\ell)$-bounded. Group privacy (Lemma 2.11) tells us that
if a mechanism $\mathcal{M}$ is $(\varepsilon,\delta)$-DP, then its outputs on
a pair of datasets which differ in at most $k$ individuals are
$(k\cdot\varepsilon,k\cdot e^{k\varepsilon}\cdot\delta)$-indistinguishable.

Proof of item (1). By item (2a) of Theorem 3.3, the projections of
$\mathit{S}$ and $\mathit{S}^{\prime}$ will have maximum degree at most
$D^{\prime}$ and will be edge distance at most $D^{\prime}+\ell$ from each
other, so group privacy tells us that the outputs from $\text{\sf
RestrictedPrivAlg}_{D^{\prime}}$ on the projections with maximum degree at
most $D^{\prime}$ will be
$(\varepsilon_{\mathsf{Base}},\delta_{\mathsf{Base}})$-indistinguishable for

$\varepsilon_{\mathsf{Base}}=(D^{\prime}+\ell)\cdot\varepsilon^{\prime}\mathrm{\quad
and\quad}\delta_{\mathsf{Base}}=(D^{\prime}+\ell)\cdot
e^{\varepsilon_{\mathsf{Base}}}\delta^{\prime},$

which is what we wanted to show.

Proof of item (2). By item (3a) of Theorem 3.3, the projections of
$\mathit{S}$ and $\mathit{S}^{\prime}$ will have maximum degree at most
$D^{\prime}$ and will be node distance at most $2\ell+1$ from each other, so
group privacy tells us that the outputs from $\text{\sf
RestrictedPrivAlg}_{D^{\prime}}$ on the projections with maximum degree at
most $D^{\prime}$ will be
$(\varepsilon_{\mathsf{Base}},\delta_{\mathsf{Base}})$-indistinguishable for

$\varepsilon_{\mathsf{Base}}=(2\ell+1)\cdot\varepsilon^{\prime}\mathrm{\quad
and\quad}\delta_{\mathsf{Base}}=(2\ell+1)\cdot
e^{\varepsilon_{\mathsf{Base}}}\delta^{\prime},$

which is what we wanted to show. ∎

######  Claim 4.6 (Privacy and failure probability of $\mathsf{Test}$).

Let $\mathsf{Test}$ be parameterized as in Algorithm 5. $\mathsf{Test}$ has
the following properties:

  1. 1.

$\mathsf{Test}$ is $(\varepsilon_{\mathsf{Test}},0)$-node-DP under continual
observation.

  2. 2.

For every input stream $\mathit{S}$ and time $t\in[T]$, if $\mathit{S}_{[t]}$
is not $(D^{\prime},\ell)$-bounded, then $\mathsf{Test}(\mathit{S})$ outputs
$\bot$ w.p. at least $1-\beta_{\mathsf{Test}}$ at or before time $t$.

###### Proof of Claim 4.6.

We prove each item below.

Proof of item (1). By Lemma 4.3, for all $t\in[T]$ the query
$q_{t}=-1\cdot\mathsf{DistToGraph}_{D^{\prime},\ell}(\mathsf{flatten}(\mathit{S}_{[t]}))$
has node-sensitivity 1, so by Theorem A.1 the output of $\mathsf{SVT}$ is
$(\varepsilon_{\mathsf{Test}},0)$-node-DP under continual observation.

Proof of item (2). Let $\mathit{S}$ be a graph stream of length $T$, and let
$t^{*}\in[T]$ be the smallest value such that $\mathit{S}_{[t^{*}]}$ has at
least $\ell$ nodes of degree greater than $D^{\prime}$, and set $t^{*}=T+1$ if
there is no such value. (Note that this time $t^{*}$ is less than or equal to
the smallest value $t$ such that $S_{[t]}$ is not
$(D^{\prime},\ell)$-bounded.) By definition we have
$\mathsf{DistToGraph}_{D^{\prime},\ell}(\mathsf{flatten}(\mathit{S}_{[t^{*}]}))=0$,
so for
$q_{t^{*}}=-1\cdot\mathsf{DistToGraph}_{D^{\prime},\ell}(\mathsf{flatten}(\mathit{S}_{[t^{*}]}))$
we have $q_{t^{*}}=0$. Equivalently, where we set
$\tau=-8\ln(1/\beta_{\mathsf{Test}})/\varepsilon_{\mathsf{Test}}$ (as in
Algorithm 5), we have

$q_{t^{*}}=8\ln(1/\beta_{\mathsf{Test}})/\varepsilon_{\mathsf{Test}}+\tau.$

By item (1) of Theorem A.2, then, in Algorithm 5 $\mathsf{SVT}$ outputs $\bot$
at or before time step $t^{*}$ with probability at least
$1-\beta_{\mathsf{Test}}$, so we also have that Algorithm 5 outputs $\bot$ at
or before time $t^{*}$ (and at all subsequent time steps) with probability at
least $1-\beta_{\mathsf{Test}}$. ∎

From Claims 4.5 and 4.6, we see that $\mathsf{Base}$ and $\mathsf{Test}$ as
defined in Algorithm 5 satisfy the conditions on $\mathsf{Base}$ and
$\mathsf{Test}$ that are described in Theorem 4.4. Algorithm 5 is a post-
processed version of $\mathsf{PTR}$ initialized with $\mathsf{Base}$ and
$\mathsf{Test}$, so it shares the privacy properties of $\mathsf{PTR}$.
Therefore, by applying Theorem 4.4, we see that Algorithm 5 has the following
privacy guarantees:

  1. 1.

If $\text{\sf RestrictedPrivAlg}_{D^{\prime}}$ satisfies
$D^{\prime}$-restricted $(\varepsilon^{\prime},\delta^{\prime})$-edge-DP, then
Algorithm 5 is $(\varepsilon,\delta)$-DP for

$\varepsilon=\varepsilon_{\mathsf{Test}}+\varepsilon^{\prime}\cdot{\left({D^{\prime}+\ell}\right)}\quad\text{and}\quad\delta=(1+e^{\varepsilon_{\mathsf{Test}}})e^{\varepsilon}\beta_{\mathsf{Test}}+\delta^{\prime}\cdot
e^{\varepsilon^{\prime}\cdot(D^{\prime}+\ell)}\cdot{\left({D^{\prime}+\ell}\right)}.$

  2. 2.

If $\text{\sf RestrictedPrivAlg}_{D^{\prime}}$ satisfies
$D^{\prime}$-restricted $(\varepsilon^{\prime},\delta^{\prime})$-node-DP, then
Algorithm 5 is $(\varepsilon,\delta)$-DP for

$\varepsilon=\varepsilon_{\mathsf{Test}}+\varepsilon^{\prime}\cdot{\left({2\ell+1}\right)}\quad\text{and}\quad\delta=(1+e^{\varepsilon_{\mathsf{Test}}})e^{\varepsilon}\beta_{\mathsf{Test}}+\delta^{\prime}\cdot
e^{\varepsilon^{\prime}\cdot(2\ell+1)}\cdot{\left({2\ell+1}\right)}.$

These are the values for $\varepsilon$ and $\delta$ that we wanted to show. We
now solve for $\varepsilon^{\prime}$ and $\delta^{\prime}$ to complete the
proof for items (1) and (2) of Theorem 4.1. The asymptotic bounds that follow
use the assumptions $\varepsilon\leq 1$,
$\varepsilon_{\mathsf{Test}}=\varepsilon/2$, and
$\beta_{\mathsf{Test}}=\delta/30$; we work out these bounds in detail below.

To solve for $\varepsilon^{\prime}$ and $\delta^{\prime}$, we begin with the
exact expressions for $\varepsilon$ and $\delta$ in item (1). Using our
assumed bounds on $\varepsilon$, $\varepsilon_{\mathsf{Test}}$, and
$\beta_{\mathsf{Test}}$, we obtain

$\varepsilon=\Theta\left(\varepsilon^{\prime}\cdot(D^{\prime}+\ell)\right),$

so we have

$\varepsilon^{\prime}=\Theta\left(\frac{\varepsilon}{D^{\prime}+\ell}\right).$
(6)

We also have

$\displaystyle\delta$
$\displaystyle=(1+e^{\varepsilon_{\mathsf{Test}}})e^{\varepsilon}\beta_{\mathsf{Test}}+\delta^{\prime}\cdot
e^{\varepsilon^{\prime}\cdot(D^{\prime}+\ell)}\cdot{\left({D^{\prime}+\ell}\right)}$
$\displaystyle\leq 2e^{2\varepsilon}\beta_{\mathsf{Test}}+\delta^{\prime}\cdot
e^{\varepsilon^{\prime}\cdot(D^{\prime}+\ell)}\cdot{\left({D^{\prime}+\ell}\right)}$
$\displaystyle=\Theta\left(\delta^{\prime}\cdot(D^{\prime}+\ell)\right),$

with the final line following from $\varepsilon\leq 1$ and
$\beta_{\mathsf{Test}}=\delta/30$, so we have

$\delta^{\prime}=\Theta\left(\frac{\delta}{D^{\prime}+\ell}\right).$ (7)

We can expand $D^{\prime}+\ell$ as

$\displaystyle D^{\prime}+\ell$ $\displaystyle=D+\Theta(\ell)$
$\displaystyle=D+\Theta\left(\frac{\log(T/(\beta\beta_{\mathsf{Test}}))}{\varepsilon_{\mathsf{Test}}}\right).$

By combining this with Expressions 6 and 7, we indeed obtain

$\varepsilon^{\prime}=\Theta\left(\frac{\varepsilon}{B}\right)\mathit{\quad
and\quad}\delta^{\prime}=\Theta\left(\frac{\delta}{B}\right),\mathit{\quad
where\quad}B=D+\frac{\log(T/(\beta\delta))}{\varepsilon}.$

From the exact expressions in item (2), we can similarly obtain
$\varepsilon^{\prime}=\Theta\left(\varepsilon/\ell\right)$ and
$\delta^{\prime}=\Theta\left(\delta/\ell\right)$. We can then write
$\ell=\Theta\left(\log(T/(\beta\beta_{\mathsf{Test}}))/\varepsilon_{\mathsf{Test}}\right)$,
which gives us

$\varepsilon^{\prime}=\Theta\left(\frac{\varepsilon}{B}\right)\mathit{\quad
and\quad}\delta^{\prime}=\Theta\left(\frac{\delta}{B}\right),\mathit{\quad
where\quad}B=\frac{\log(T/(\beta\delta))}{\varepsilon}.$

This completes the proof of items (1) and (2).

Proof of item (3) in Theorem 4.1. Let $\mathit{S}$ be a graph stream of length
$T$, and let $t^{\prime}\in[T]$ be the largest value such that
$\mathit{S}_{[t^{\prime}]}$ has maximum degree at most $D$, setting
$t^{\prime}=0$ if there is no such value. This proof mostly follows from item
(2) of Theorem A.2. Let $\ell$ and $D^{\prime}$ be defined as in Algorithm 5,
so
$\ell={\left\lceil{8\ln(T/(\beta\beta_{\mathsf{Test}}))/\varepsilon_{\mathsf{Test}}}\right\rceil}$
and $D^{\prime}=D+\ell$. By Lemma 4.3, we have
$\mathsf{DistToGraph}_{D^{\prime},\ell}(\mathsf{flatten}(\mathit{S}_{[t]}))\geq\ell$,
so for
$q_{t}=-1\cdot\mathsf{DistToGraph}_{D^{\prime},\ell}(\mathsf{flatten}(\mathit{S}_{[t]}))$
we have $q_{t}\leq-\ell$.

Equivalently, where we set
$\tau=-8\ln(1/\beta_{\mathsf{Test}})/\varepsilon_{\mathsf{Test}}$ (as in
Algorithm 5), we have

$\displaystyle q_{t}$ $\displaystyle\leq-\ell$
$\displaystyle\leq-8\ln(T/(\beta\beta_{\mathsf{Test}}))/\varepsilon_{\mathsf{Test}}$
$\displaystyle=-8\ln(T/\beta)/\varepsilon_{\mathsf{Test}}+\tau$
$\displaystyle=8\ln(\beta/T)/\varepsilon_{\mathsf{Test}}+\tau.$

By item (2) of Theorem A.2, then, in Algorithm 5 $\mathsf{SVT}$ outputs $\top$
on $q_{1},\ldots,q_{t^{\prime}}$ with probability at least $1-\beta$, so we
also have that Algorithm 5 outputs the result from $\text{\sf
RestrictedPrivAlg}_{D^{\prime}}$ for all $t\leq t^{\prime}$ with probability
at least $1-\beta$.

Proof of item (4) in Theorem 4.1. On a given input stream $\mathit{S}$, let
$R_{[t]}$ be the runtime of $\text{\sf RestrictedPrivAlg}_{D^{\prime}}$
through time $t$ (on $\mathit{S}_{[t]}$), and let $n_{[t]}$ and $m_{[t]}$ be
the number of nodes and edges in the graph stream through time step $t$. At
each time step, Algorithm 5 does several constant-time operations, an update
to the projection, a call to $\text{\sf RestrictedPrivAlg}_{D^{\prime}}$, and
a call to $\mathsf{Test}$. The projection algorithm in Algorithm 1 has runtime
linear in the number of (new) nodes and edges, so the runtime of this through
$t$ time steps is $O(n_{[t]}+m_{[t]})$. The $t$ calls to $\text{\sf
RestrictedPrivAlg}_{D^{\prime}}$ have runtime $R_{[t]}$. By Lemma 4.3,
$\mathsf{DistToGraph}$ can be updated in time linear in the number of new
nodes and edges, so each call to $\mathsf{SVT}$ takes either constant time or
time linear in the number of new nodes and edges. Therefore, the overall
runtime of Algorithm 5 through time $t\in[T]$ is
$R_{[t]}+O(n_{[t]}+m_{[t]}+t)$.

We now compute the space complexity. The projection algorithm need only track
the degree of each node, which takes space $O(n_{[t]})$; the new nodes and
edges that are added to the projection can be passed to the base algorithm
$\text{\sf RestrictedPrivAlg}_{D^{\prime}}$ at each time step, so this does
not take additional space. By the proof of Lemma 4.3, we see that the
algorithm for computing $\mathsf{Test}$ only requires a constant number of
counters, along with two hash tables each with at most $O(n_{[t]})$ entries.
Therefore, our algorithm requires $O(n_{[t]})$ additional space as compared to
$\text{\sf RestrictedPrivAlg}_{D^{\prime}}$. ∎

##  5 Optimal Algorithms for $f_{\mathsf{edges}}$, $f_{\mathsf{triangles}}$,
$f_{\mathsf{CC}}$, $f_{\mathsf{k\text{-}stars}}$

We now use our transformation in Algorithm 5 to convert restricted edge- and
node-DP algorithms for several fundamental problems into node-DP algorithms
that achieve the same asymptotic error as the analogous restricted node-DP
algorithms given by [SLM+18, FHO21], up to lower-order terms. Section 1.1
shows the additive error for privately counting edges ($f_{\mathsf{edges}}$),
triangles ($f_{\mathsf{triangles}}$), $k$-stars
($f_{\mathsf{k\text{-}stars}}$), and connected components ($f_{\mathsf{CC}}$),
and privately releasing degree histograms777The degree histogram
$f_{\mathsf{degree\text{-}hist}}(G)$ for a graph $G$ with maximum degree at
most $D$ is the $(D+1)$-element vector
$(a_{0},\ldots,a_{D})\in\mathbb{R}^{D+1}$, where $a_{i}$ is the number of
nodes with degree $i$ in $G$. ($f_{\mathsf{degree\text{-}hist}}$) of the input
graph stream. Moreover, for $f_{\mathsf{edges}}$, $f_{\mathsf{triangles}}$,
$f_{\mathsf{k\text{-}stars}}$, and $f_{\mathsf{CC}}$, the accuracy of our
algorithms is asymptotically optimal, up to lower order terms and
polylogarithmic factors. We prove the upper bounds on error in Section 5.1 and
the lower bounds in Section 5.2.

For $f_{\mathsf{edges}},f_{\mathsf{triangles}},f_{\mathsf{k\text{-}stars}},$
and $f_{\mathsf{degree\text{-}hist}}$, the errors for our transformation
follow from substituting the $\varepsilon^{\prime}$ term from Theorem 4.1 into
the error bounds for the restricted edge-DP algorithms of [FHO21] (algorithms
with slightly worse lower-order terms follow from using restricted node-DP
algorithms). The bound for $f_{\mathsf{CC}}$ follows from a new edge-DP
algorithm based on the binary tree mechanism.

By item (1a) of Theorem 3.3, we can also immediately obtain
$(\varepsilon,0)$-edge-DP algorithms from restricted edge-private algorithms
by using the projection $\Pi^{\text{\tiny BBDS}}_{D}$ and running the
corresponding restricted edge-private algorithm with
$\varepsilon^{\prime}=\varepsilon/3$ on the projection. This technique gives
the first algorithms for $f_{\mathsf{triangles}}$,
$f_{\mathsf{k\text{-}stars}}$, and $f_{\mathsf{CC}}$ that are edge-private
under continual observation for all graphs and, for graph streams with maximum
degree at most $D$, have asymptotically optimal accuracy (up to
polylogarithmic factors).

The lower bounds in Section 5.2 follow by reductions from a version of the
$\Omega(\log T/\varepsilon)$ lower bound for binary counting from [DNPR10],
modified by us for the approximate-DP setting (Theorem 5.7).

###  5.1 Upper Bounds on Error

We first present our upper bounds on additive error. For $f_{\mathsf{edges}}$,
$f_{\mathsf{triangles}}$, $f_{\mathsf{k\text{-}stars}}$, and
$f_{\mathsf{degree\text{-}hist}}$, the errors for our transformation roughly
follow by substituting the $\varepsilon^{\prime}$ term from Theorem 4.1 into
the error bounds for restricted edge-DP algorithms of [FHO21] (with slight
modifications for the $\ell_{\infty}$ error setting). For $f_{\mathsf{CC}}$,
the error follows from a new edge-DP algorithm based on the binary tree
mechanism; this algorithm and the accompanying proof are described in Lemmas
5.4 and 5.3.

The errors for our edge-private algorithms follow from item (1a) of Theorem
3.3, which says we can achieve $(\varepsilon,0)$-edge-DP by roughly running
the algorithms of [FHO21] for
$f_{\mathsf{triangles}},f_{\mathsf{k\text{-}stars}},f_{\mathsf{degree\text{-}hist}}$
and $f_{\mathsf{triangles}}$ (modified for the $\ell_{\infty}$ error setting),
and our algorithm for $f_{\mathsf{CC}}$, with privacy parameter
$\varepsilon^{\prime}=\varepsilon/3$ on the output of $\Pi^{\text{\tiny
BBDS}}_{D}$.

######  Theorem 5.1 (Accuracy of node-private algorithms).

Let $\varepsilon\in(0,1]$, $\delta>0$, $D\in\mathbb{N}$, $T\in\mathbb{N}$
where $T\geq 2$, and $\mathit{S}$ be a length-$T$, insertion-only graph
stream. There exist $(\varepsilon,\delta)$-node-DP algorithms for the
following problems whose error is at most $\alpha$, with probability $0.99$,
for all times steps $t\in[T]$ where $\mathit{S}_{[t]}$ has maximum degree at
most $D$:

  1. 1.

$f_{\mathsf{edges}}$,
$\alpha=O\left(\left(D+\tfrac{1}{\varepsilon}\log\frac{T}{\delta}\right)\frac{\log^{5/2}T}{\varepsilon}\right).$

  2. 2.

$f_{\mathsf{triangles}}$,
$\alpha=O\left(\left(D^{2}+\tfrac{1}{\varepsilon^{2}}\log^{2}\frac{T}{\delta}\right)\frac{\log^{5/2}T}{\varepsilon}\right).$

  3. 3.

$f_{\mathsf{CC}}$,
$\alpha=O\left(\left(D+\tfrac{1}{\varepsilon}\log\frac{T}{\delta}\right)\frac{\log^{5/2}T}{\varepsilon}\right).$

  4. 4.

$f_{\mathsf{k\text{-}stars}}$,
$\alpha=O\left(\left(D^{k}+\tfrac{1}{\varepsilon^{k}}\log^{k}\frac{T}{\delta}\right)\frac{\log^{5/2}T}{\varepsilon}\right).$

  5. 5.

$f_{\mathsf{degree\text{-}hist}}$,
$\alpha=\widetilde{O}\left(\left(D^{2}+\tfrac{1}{\varepsilon^{2}}\log^{2}\frac{T}{\delta}\right)\frac{\log^{5/2}T}{\varepsilon}\right)$
(maximum error over histogram entries and time steps).

As is standard, the $\widetilde{O}$ notation suppresses terms that are
logarithmic in the argument—in this case, it suppresses $\log D$ and
$\log(\frac{1}{\varepsilon}\log\frac{T}{\delta})$.

######  Theorem 5.2 (Accuracy of edge-private algorithms).

Let $\varepsilon>0$, $D\in\mathbb{N}$, $T\in\mathbb{N}$ where $T\geq 2$, and
$\mathit{S}$ be a length-$T$, insertion-only graph stream. There exist
$(\varepsilon,0)$-edge-DP algorithms for the following problems whose error is
at most $\alpha$, with probability $0.99$, for all times steps $t\in[T]$ where
$\mathit{S}_{[t]}$ has maximum degree at most $D$:

  1. 1.

$f_{\mathsf{triangles}}$,
$\alpha=O\left(\dfrac{D\log^{5/2}T}{\varepsilon}\right).$

  2. 2.

$f_{\mathsf{CC}}$, $\alpha=O\left(\dfrac{\log^{5/2}T}{\varepsilon}\right).$

  3. 3.

$f_{\mathsf{k\text{-}stars}}$,
$\alpha=O\left(\dfrac{D^{k-1}\log^{5/2}T}{\varepsilon}\right).$

  4. 4.

$f_{\mathsf{degree\text{-}hist}}$,
$\alpha=\widetilde{O}\left(\dfrac{D\log^{5/2}T}{\varepsilon}\right)$ (maximum
error over histogram entries and time steps).

As is standard, the $\widetilde{O}$ notation suppresses terms that are
logarithmic in the argument—in this case, it suppresses $\log D$.

As described above, these upper bounds rely on the accuracy of restricted
edge-private algorithms for the associated problems, all of which are based on
the binary tree mechanism of [DNPR10, CSS11] and result from Lemmas 5.4 and
5.3.

These binary tree-based algorithms all follow from bounding the $\ell_{1}$
sensitivity of the sequence of _increments_ of a given function $f$ over the
stream $\mathit{S}$, first considered explicitly by [SLM+18]. Let
$x\in\mathcal{X}^{T}$. Where $f:\mathcal{X}^{T}\to(\mathbb{R}^{d})^{T}$
returns an output in $\mathbb{R}^{d}$ at each time step, let $\text{\sf
inc}_{f}(\mathit{S}):\mathcal{X}^{T}\to(\mathbb{R}^{d})^{T}$ return, for each
time step $t\in[T]$, the increment $f(x)_{t}-f(x)_{t-1}$, where we define
$f(x)_{0}=0^{d}$. We define $\text{\sf IncEdgeSens}_{D}(f)$ as the $\ell_{1}$
Lipschitz constant of $\text{\sf inc}_{f}$ when restricted to $D$-bounded,
edge-neighboring graph streams:

$\text{\sf
IncEdgeSens}_{D}(f)=\sup_{\begin{subarray}{c}\mathit{S}\simeq_{\mathit{edge}}\mathit{S}^{\prime}\,\text{with}\\\
\text{max degree }\leq D\end{subarray}}\|\text{\sf
inc}_{f}(\mathit{S})-\text{\sf inc}_{f}(\mathit{S}^{\prime})\|_{1}\,.$

We let $\text{\sf IncEdgeSens}(f)$ (without a value for $D$) denote the
sensitivity of $\text{\sf inc}_{f}$ over all neighboring graphs streams.

The tree mechanism of [DNPR10, CSS11] produces an edge-DP approximation to the
sequence of values of $f$ when the noise is scaled to $\text{\sf
IncEdgeSens}_{D}(f)$, and produces an algorithm with $D$-restricted edge-
privacy when its noise is scaled to $\text{\sf IncEdgeSens}_{D}(f)$. The
following lemma is folklore; our formulation is a variation on statements in
[DNPR10, CSS11, SLM+18, FHO21].

######  Lemma 5.3 (following [DNPR10, CSS11, SLM+18, FHO21]).

Let $\varepsilon>0$, $D\in\mathbb{N}$, $T\in\mathbb{N}$ where $T\geq 2$, and
$d\in\mathbb{N}$. Let $f:\mathcal{S}^{T}\to(\mathbb{R}^{d})^{T}$ return a
($d$-dimensional) output in $\mathbb{R}^{d}$ at each time step $t\in[T]$.

There exists a $D$-restricted $(\varepsilon,0)$-edge-DP algorithm that, with
probability at least $1-\beta$, has $\ell_{\infty}$ error

$\text{\sf IncEdgeSens}_{D}(f)\cdot
O{\left({\frac{\log^{3/2}T}{\varepsilon}\cdot\log(dT/\beta)}\right)}$

on every dimension of the output.

The analogous statement holds for (unrestricted) differential privacy when its
noise scaled to $\text{\sf IncEdgeSens}(f)$. Additionally, analogous
statements hold for restricted and unrestricted node sensitivity and node-DP.

###### Proof of Lemma 5.3.

By [FHO21, Corollary 14], which uses the binary tree mechanism of [CSS11,
DNPR10] and the technique of difference sequences introduced by [SLM+18],
there exists a $D$-restricted $(\varepsilon,0)$-edge-DP algorithm that, with
probability at least $1-\beta^{\prime}$, has error at most $\text{\sf
IncEdgeSens}_{D}(f)\cdot
O{\left({\frac{\log^{3/2}T}{\varepsilon}\cdot\log(1/\beta^{\prime})}\right)}$
per dimension at each time step.

By substituting $\beta^{\prime}=\frac{\beta}{dT}$ and taking a union bound
over all $d$ coordinates and $T$ time steps, with probability at least
$1-\beta$ the $\ell_{\infty}$ error over all $d$ coordinates and $T$ time
steps is at most $\text{\sf IncEdgeSens}_{D}(f)\cdot
O{\left({\frac{\log^{3/2}T}{\varepsilon}\cdot\log(dT/\beta)}\right)}$, which
is what we wanted to show (with analogous statements for $\text{\sf
IncEdgeSens}(f)$ and unrestricted $(\varepsilon,0)$-edge-DP; and for node-DP).
∎

######  Lemma 5.4 (Edge sensitivity bounds).

For all $D\in\mathbb{N}$, the following bounds on incremental edge-sensitivity
$\text{\sf IncEdgeSens}_{D}$ and IncEdgeSens hold (with some due to [SLM+18,
FHO21]):

  1. 1.

$\text{\sf IncEdgeSens}(f_{\mathsf{edges}})=1=O(1)$.

  2. 2.

$\text{\sf IncEdgeSens}_{D}(f_{\mathsf{triangles}})=D-1=O(D)$.

  3. 3.

$\text{\sf IncEdgeSens}(f_{\mathsf{CC}})=2=O(1)$.

  4. 4.

$\text{\sf
IncEdgeSens}_{D}(f_{\mathsf{k\text{-}stars}})=2\binom{D-1}{k-1}=O{\left({D^{k-1}}\right)}$.

  5. 5.

$\text{\sf IncEdgeSens}_{D}(f_{\mathsf{degree\text{-}hist}})=8D-4=O(D)$.

Except for $f_{\mathsf{degree\text{-}hist}}$, these equalities hold even if we
restrict our attention to streams of length $T=1$. For
$f_{\mathsf{degree\text{-}hist}}$, the lower bound requires $T\geq 2D$ (but
the upper bound holds regardless of $T$).

###### Proof.

With the exception of item (3), proofs of items similar to those listed above
can be found in [FHO21, Lemma 15], though we tighten some of the sensitivities
(analyses for $D$-restricted node sensitivity first appear in [SLM+18]).
Specifically, for items (2) and (5) we tighten the exact sensitivities and
provide strict equalities (the asymptotics are unchanged), and for item (4) we
tighten the asymptotic expression by a factor of $D$ (the exact expression in
fact remains unchanged). We prove item (3) last since its proof is new and the
most involved.

Item (1). The addition or removal of an edge changes the increment sequence of
edge counts $\text{\sf inc}_{f_{\mathsf{edges}}}$ by at most one [FHO21].

Item (2). Each edge is part of at most $D-1$ triangles (and can, in fact, be
part of $D-1$ triangles), so adding or removing an edge will change the
sequence of increments by at most $D-1$.

Item (4). Each edge is part of at most $2\binom{D}{k}$ different $k$-stars
(and, if the edge is between two nodes with degree $D$, will be part of
exactly $2\binom{D}{k}$ different $k$-stars) so removing the edge will instead
result in $2\binom{D-1}{k}$ different $k$-stars. Therefore, the sequence of
increments will change by at most
$2{\left({\binom{D}{k}-\binom{D-1}{k}}\right)}$ [FHO21]. We additionally
observe
$2{\left({\binom{D}{k}-\binom{D-1}{k}}\right)}=2\binom{D-1}{k-1}=O{\left({D^{k-1}}\right)}$.

Item (5). We first consider how an additional edge
$e^{+}={\left\\{{u,v}\right\\}}$ in $\mathit{S}^{\prime}$ (as compared to an
edge-neighboring stream $\mathit{S}$) affects the degree of $u$; we then apply
a similar argument for the degree of $v$. At each time step, the degree of $u$
is higher by at most one in $\mathit{S}^{\prime}$ as compared to $\mathit{S}$.
In general, this means that the increment to each bucket due to a change in
the degree of $u$ will be earlier, and the decrement to each bucket due to a
change in the degree of $u$ will also be earlier. There are several exceptions
to this idea: the increment to the bucket for degree 0 cannot be earlier, and
there cannot be a decrement to the bucket for degree $D$. Additionally, there
cannot be an increment in $\mathit{S}$ for the bucket for degree $D$ (since
otherwise $u$ would have degree $D+1$ in $\mathit{S}^{\prime}$); similarly,
there cannot be a decrement for the bucket for degree $D-1$ in $\mathit{S}$.

Therefore, considering buckets not equal to $0$, $D-1$, or $D$, there are
$(D-2)$ differently positioned increments and decrements—that is, the
$\ell_{1}$ sensitivity of the sequence of increments for these buckets is
$4(D-2)$; and for $D$ there is $1$ change, for 0 there are $2$ changes (when
$D-1>0$), and for $D-1$ there is one less change than it would otherwise have
(i.e., $1$ change for $D-1=0$ and $3$ changes otherwise). Therefore, the
$\ell_{1}$ sensitivity of the sequence of increments is $4D-2$ due to the
change in the degree of $u$. A similar argument applies for changes due to the
degree of $v$, which gives us a sensitivity of $2\cdot(4D-2)=8D-4$.

Note that this argument is tight when $e^{+}$ arrives at a time step that is
both (1) after $u$ and $v$ and (2) before all other edges, and when at most
one edge incident to $u$ arrives at each time step (likewise for $v$).

Item (3). Let $f_{\mathsf{CC}}^{+}$ denote $\text{\sf inc}_{f_{\mathsf{CC}}}$.
Without loss of generality, let $\mathit{S}^{\prime}$ be a graph stream that,
as compared to $\mathit{S}$, has one additional edge $e^{+}=\\{u,v\\}$ that is
inserted at time $t_{1}$.

When bounding
$||f_{\mathsf{CC}}^{+}(\mathit{S})-f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})||_{1}$,
we have to consider the following three cases. In $\mathit{S}$:

  1. 1.

(Case 1) there is never a path between $u$ and $v$.

  2. 2.

(Case 2) $t_{0}\leq t_{1}$ is the first time step at which there exists a path
between $u$ and $v$.

  3. 3.

(Case 3) $t_{3}>t_{1}$ is the first time step at which there exists a path
between $u$ and $v$.

We prove each case below.

Case 2: The outputs from $f_{\mathsf{CC}}(\mathit{S})$ and
$f_{\mathsf{CC}}(\mathit{S}^{\prime})$ are identical, so the outputs from
$f_{\mathsf{CC}}^{+}(\mathit{S})$ and
$f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})$ are also identical, so we have
$||f_{\mathsf{CC}}^{+}(\mathit{S})-f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})||_{1}=0$.
We now consider the remaining cases.

Case 1: For all $t_{0}<t_{1}$ (that is, prior to the time step at which the
graph streams differ) we have
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{0}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{0}}$.
When the difference in graph streams occurs at $t_{1}$, we have
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{1}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{1}}+1$.
Only the components containing $u$ and $v$ are affected by this edge. By the
assumption that there is never a path between $u$ and $v$ in $\mathit{S}$, no
future edges affect the components containing $u$ and $v$, so for all
$t_{2}>t_{1}$ we have
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{2}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{2}}$.
Therefore, in case 1 we have

$||f_{\mathsf{CC}}^{+}(\mathit{S})-f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})||_{1}\leq
1.$

Case 3: As above, for all $t_{0}<t_{1}$ we have
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{0}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{0}}$.
When the difference in graph streams occurs at $t_{1}$, we have
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{1}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{1}}+1$.
Only the components containing $u$ and $v$ are affected by the inclusion of
edge $e^{+}$. By the assumption that, for all $t_{2}\in[t_{1},t_{3})$, there
is never a path between $u$ and $v$ in $\mathit{S}$, no edges arriving at such
times $t_{2}$ affect the components containing $u$ and $v$, so we have
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{2}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{2}}$.

At time $t_{3}$, the edge forming a path between $u$ and $v$ arrives, which
causes the number of connected components in $\mathit{S}$ to decrease by 1 as
compared to $\mathit{S}^{\prime}$, so
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{3}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{3}}$.
For all $t_{4}>t_{3}$, the changes in counts will be the same for both graph
streams, so
$f_{\mathsf{CC}}^{+}(\mathit{S})_{t_{4}}=f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})_{t_{4}}$.
Therefore, in case 3 we have

$||f_{\mathsf{CC}}^{+}(\mathit{S})-f_{\mathsf{CC}}^{+}(\mathit{S}^{\prime})||_{1}\leq
2,$

which completes the proof. ∎

We now move to the proofs of Theorems 5.1 and 5.2. Theorem 5.2 quickly follows
from running the restricted edge-private algorithms that result from the
sensitivities in Lemma 5.4 and the binary tree mechanism in Lemma 5.3 on the
projection returned by $\Pi^{\text{\tiny BBDS}}_{D}$, and either running the
algorithm directly on the input for the problems with unrestricted sensitivity
bounds, or running the algorithm with $\varepsilon^{\prime}=\varepsilon/3$ on
the projection of $\Pi^{\text{\tiny BBDS}}_{D}$ for problems with restricted
sensitivity bounds. Theorem 5.1 follows from running Algorithm 5 with access
to the relevant restricted edge-private algorithm that results from Lemmas 5.4
and 5.3, and then determining the associated accuracy of that algorithm given
the value of $\varepsilon^{\prime}$ specified by Theorem 4.1.

###### Proof of Theorem 5.2.

This proof follows immediately from combining item (1a) of Theorem 3.3, which
describes the edge-to-edge stability of Algorithm 1 that includes edges in the
projection according to original degrees (we use $\Pi^{\text{\tiny BBDS}}_{D}$
to denote this projection), with the bounds on accuracy for edge-private
algorithms that follow from the sensitivities in Lemma 5.4 and the binary tree
mechanism in Lemma 5.3. More specifically, to obtain $(\varepsilon,0)$-edge-DP
under continual observation for the problems with $D$-restricted edge
sensitivity, we run the $D$-restricted edge-private algorithms yielding these
accuracy bounds with $\varepsilon/3$ on the graph stream output by the
projection algorithm $\Pi^{\text{\tiny BBDS}}_{D}$; and to obtain
$(\varepsilon,0)$-edge-DP under continual observation for the problems with
unrestricted edge sensitivity, we run the resulting algorithm with
$\varepsilon$. ∎

###### Proof of Theorem 5.1.

We begin by calculating the value of $\varepsilon^{\prime}$ with which
Algorithm 5 will run the (restricted) edge-private algorithm. For these
calculations, set $\varepsilon_{\mathsf{Test}}=\varepsilon/2$ and
$\beta_{\mathsf{Test}}=\delta/30$. We also assume constant $\beta$. To have
$(\varepsilon,\delta)$-node-DP, Theorem 4.1 tells us that Algorithm 5 will set

$\displaystyle\varepsilon^{\prime}$
$\displaystyle=\Theta\left(\frac{\varepsilon}{D+\frac{\log(T/(\beta\delta))}{\varepsilon}}\right)$
$\displaystyle=\Theta\left(\frac{\varepsilon}{D}+\frac{\varepsilon^{2}}{\log(T/(\beta\delta))}\right).$

For constant $\beta$, we can simplify this further to

$\varepsilon^{\prime}=\Theta\left(\frac{\varepsilon}{D}+\frac{\varepsilon^{2}}{\log(T/\delta)}\right).$

To compute accuracy, we will also need to know the value of $D^{\prime}$.
Using the conditions stated above on our variables, we can simplify
$D^{\prime}$ as follows:

$\displaystyle D^{\prime}$ $\displaystyle=D+\ell$
$\displaystyle=D+\Theta{\left({\dfrac{\log(T/(\beta\beta_{\mathsf{Test}}))}{\varepsilon}}\right)}$
$\displaystyle=D+\Theta{\left({\frac{\log(T/\delta)}{\varepsilon}}\right)}.$

Proof of items (1) and (3). We substitute the above value of
$\varepsilon^{\prime}$ into the accuracy bounds that follow from Lemmas 5.4
and 5.3. We note that the accuracy expressions for $f_{\mathsf{edges}}$ and
$f_{\mathsf{CC}}$ are the same, so we begin by proving the upper bounds on
accuracy for these functions. By Lemmas 5.4 and 5.3, with probability
$1-\beta$, the edge-private algorithms for $f_{\mathsf{edges}}$ and
$f_{\mathsf{CC}}$ have additive error at most $O((\log^{3/2}T)\cdot(\log
T+\log(1/\beta))/\varepsilon^{\prime})$. Since $\beta$ is constant we can
ignore the $\log(1/\beta)$ term, so substituting for $\varepsilon^{\prime}$
gives us

$\displaystyle\frac{\log^{5/2}T}{\varepsilon^{\prime}}$
$\displaystyle=\Theta\left(\left(\frac{D}{\varepsilon}+\frac{\log(T/\delta)}{\varepsilon^{2}}\right)\cdot\log^{5/2}T\right)$
$\displaystyle=\Theta\left(\left(D+\frac{\log(T/\delta)}{\varepsilon}\right)\cdot\frac{\log^{5/2}T}{\varepsilon}\right),$

which is the additive error we wanted to show.

Proof of item (2). By Lemmas 5.4 and 5.3, with probability $1-\beta$, the
edge-private algorithm for $f_{\mathsf{triangles}}$ has additive error at most
$O(D^{\prime}\cdot(\log^{3/2}T)\cdot(\log
T+\log(1/\beta))/\varepsilon^{\prime})$. Since $\beta$ is constant we can
ignore the $\log(1/\beta)$ term. Substituting for $\varepsilon^{\prime}$ and
$D^{\prime}$ gives us

$\displaystyle\frac{D^{\prime}\log^{5/2}T}{\varepsilon^{\prime}}$
$\displaystyle=\Theta{\left({{\left({D+\frac{\log(T/\delta)}{\varepsilon}}\right)}\cdot\log^{5/2}T\cdot{\left({\frac{D}{\varepsilon}+\frac{\log
T/\delta}{\varepsilon^{2}}}\right)}}\right)}$
$\displaystyle=\Theta{\left({{\left({D+\frac{\log(T/\delta)}{\varepsilon}}\right)}^{2}\cdot\frac{\log^{5/2}T}{\varepsilon}}\right)}$
$\displaystyle=\Theta{\left({{\left({D^{2}+\frac{\log^{2}(T/\delta)}{\varepsilon^{2}}}\right)}\cdot\frac{\log^{5/2}T}{\varepsilon}}\right)},$

which is the additive error we wanted to show.

Proof of item (4). By Lemmas 5.4 and 5.3, with probability $1-\beta$, the
edge-private algorithm for $f_{\mathsf{k\text{-}stars}}$ has additive error at
most $O(D^{\prime k-1}\cdot(\log^{3/2}T)\cdot(\log
T+\log(1/\beta))/\varepsilon^{\prime})$. Since $\beta$ is constant we can
ignore the $\log(1/\beta)$ term. Substituting for $\varepsilon^{\prime}$ and
$D^{\prime}$ gives us

$\displaystyle\frac{D^{\prime k-1}\log^{5/2}T}{\varepsilon^{\prime}}$
$\displaystyle=\Theta{\left({{\left({D+\frac{\log(T/\delta)}{\varepsilon}}\right)}^{k-1}\cdot\log^{5/2}T\cdot{\left({\frac{D}{\varepsilon}+\frac{\log
T/\delta}{\varepsilon^{2}}}\right)}}\right)}$
$\displaystyle=\Theta{\left({{\left({D+\frac{\log(T/\delta)}{\varepsilon}}\right)}^{k}\cdot\frac{\log^{5/2}T}{\varepsilon}}\right)}$
$\displaystyle=\Theta{\left({{\left({D^{k}+\frac{\log^{k}(T/\delta)}{\varepsilon^{k}}}\right)}\cdot\frac{\log^{5/2}T}{\varepsilon}}\right)},$

which is the additive error we wanted to show.

Proof of item (5). By Lemmas 5.4 and 5.3, with probability $1-\beta$, the
edge-private algorithm for $f_{\mathsf{degree\text{-}hist}}$ has additive
error at most $O(D^{\prime}\cdot(\log^{3/2}T)\cdot(\log T+\log(1/\beta)+\log
D^{\prime})/\varepsilon^{\prime})$ on every bin of the histogram. Since
$\beta$ is constant we can ignore the $\log(1/\beta)$ term. Substituting for
$\varepsilon^{\prime}$ and $D^{\prime}$ gives us

$\displaystyle\frac{D^{\prime}\cdot(\log^{3/2}T)\cdot(\log T+\log
D^{\prime})}{\varepsilon^{\prime}}$
$\displaystyle=\widetilde{\Theta}{\left({{\left({D+\frac{\log(T/\delta)}{\varepsilon}}\right)}\cdot\log^{5/2}T\cdot{\left({\frac{D}{\varepsilon}+\frac{\log
T/\delta}{\varepsilon^{2}}}\right)}}\right)}$
$\displaystyle=\widetilde{\Theta}{\left({{\left({D+\frac{\log(T/\delta)}{\varepsilon}}\right)}^{2}\cdot\frac{\log^{5/2}T}{\varepsilon}}\right)}$
$\displaystyle=\widetilde{\Theta}{\left({{\left({D^{2}+\frac{\log^{2}(T/\delta)}{\varepsilon^{2}}}\right)}\cdot\frac{\log^{5/2}T}{\varepsilon}}\right)},$

where, as is standard, the $\widetilde{\Theta}$ notation suppresses terms that
are logarithmic in the argument—in this case, it suppresses $\log D$ and
$\log(\frac{1}{\varepsilon}\log\frac{T}{\delta})$. This is the additive error
we wanted to show. ∎

###  5.2 Lower Bounds on Error

We now present several lower bounds on the error necessary for privately
releasing graph statistics in the approximate DP setting, for $\delta=O(1/T)$.
The proofs of these bounds are based on a reduction from binary counting. For
$f_{\mathsf{edges}}$ and $f_{\mathsf{degree\text{-}hist}}$, our reductions
from binary counting are similar to the constructions used by [FHO21]. Our
reductions for $f_{\mathsf{triangles}},f_{\mathsf{CC}}$, and
$f_{\mathsf{k\text{-}stars}}$ are different from those of [FHO21] and yield
stronger lower bounds.

######  Theorem 5.5 (Lower bounds for node-private algorithms).

For sufficiently large $T\in\mathbb{N}$, and all
$\varepsilon>0,\delta=O(1/T)$, and $D\in\mathbb{N}$ (with $D\geq 2$ for
$f_{\mathsf{triangles}}$),888A graph with maximum degree $D=1$ contains no
triangles. consider a mechanism $\mathcal{M}$ for each of the problems below
that runs on length-$T$ graph streams with maximum degree at most $D$. If
$\mathcal{M}$ satisfies $(\varepsilon,\delta)$-node-DP and
$(\alpha,T)$-accuracy for the specified task, then its additive error must be
lower bounded in the following way:

  1. 1.

$f_{\mathsf{edges}}$, $\alpha=\Omega{\left({\min{\left\\{{\dfrac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}.$

  2. 2.

$f_{\mathsf{triangles}}$, $\alpha=\Omega{\left({\min{\left\\{{\dfrac{D^{2}\log
T}{\varepsilon},D^{2}T}\right\\}}}\right)}.$

  3. 3.

$f_{\mathsf{CC}}$, $\alpha=\Omega{\left({\min{\left\\{{\dfrac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}.$

  4. 4.

$f_{\mathsf{k\text{-}stars}}$,
$\alpha=\Omega{\left({\min{\left\\{{\dfrac{D^{k}\log
T}{\varepsilon},D^{k}T}\right\\}}}\right)}.$

  5. 5.

$f_{\mathsf{degree\text{-}hist}}$,
$\alpha=\Omega{\left({\min{\left\\{{\dfrac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}$ (maximum error over histogram entries
and time steps).

######  Theorem 5.6 (Lower bounds for edge-private algorithms).

For sufficiently large $T\in\mathbb{N}$, and all
$\varepsilon>0,\delta=O(1/T)$, and $D\in\mathbb{N}$ (with $D\geq 2$ for
$f_{\mathsf{triangles}}$), consider a mechanism $\mathcal{M}$ for each of the
problems below that runs on length-$T$ graph streams with maximum degree at
most $D$. If $\mathcal{M}$ satisfies $(\varepsilon,\delta)$-edge-DP and
$(\alpha,T)$-accuracy for the specified task, then its additive error must be
lower bounded in the following way:

  1. 1.

$f_{\mathsf{edges}}$, $\alpha=\Omega{\left({\min{\left\\{{\dfrac{\log
T}{\varepsilon},T}\right\\}}}\right)}.$

  2. 2.

$f_{\mathsf{triangles}}$, $\alpha=\Omega{\left({\min{\left\\{{\dfrac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}.$

  3. 3.

$f_{\mathsf{CC}}$, $\alpha=\Omega{\left({\min{\left\\{{\dfrac{\log
T}{\varepsilon},T}\right\\}}}\right)}.$

  4. 4.

$f_{\mathsf{k\text{-}stars}}$,
$\alpha=\Omega{\left({\min{\left\\{{\dfrac{D^{k-1}\log
T}{\varepsilon},D^{k-1}T}\right\\}}}\right)}.$

  5. 5.

$f_{\mathsf{degree\text{-}hist}}$,
$\alpha=\Omega{\left({\min{\left\\{{\dfrac{\log
T}{\varepsilon},T}\right\\}}}\right)}$ (maximum error over histogram entries
and time steps).

We now present a lower bound on the error needed to privately release a binary
count under continual observation. Note that, although this lower bound has
previously been stated only for pure DP [DNPR10], we show that it also holds
for the approximate-DP setting where $\delta=O(1/T)$. To prove Theorem 5.7, we
use a packing argument, introduced by [HT10, BBKN14]. We use the version given
by [Vad17].

######  Theorem 5.7 (Approximate-DP lower bound for binary counting).

Let $f:\\{0,1\\}^{T}\to\mathbb{R}^{T}$ take a $T$-element binary stream
$\mathit{S}=\mathit{S}_{1},\ldots,\mathit{S}_{T}$ as input and release, at
each time step $t\in[T]$, the sum $\sum_{i\in[t]}\mathit{S}_{i}$. Let
$\mathcal{M}$ be $(\alpha,T)$-accurate for $f$ and $(\varepsilon,\delta)$-DP
under continual observation. If $\varepsilon>0$, $\delta=O(1/T)$, and $T$ is
sufficiently large, then $\mathcal{M}$ must have additive $\ell_{\infty}$
error at least

$\alpha=\Omega{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}.$

######  Lemma 5.8 (Packing lower bound [HT10, BBKN14, Vad17]).

Let $\mathcal{C}\subseteq\mathcal{X}^{n}$ be a collection of datasets all at
Hamming distance at most $m$ from some fixed dataset
$x_{0}\in\mathcal{X}^{n}$, and let
${\left\\{{\mathcal{G}_{x}}\right\\}}_{x\in\mathcal{C}}$ be a collection of
disjoint subsets of $\mathcal{Y}$. If there is an $(\varepsilon,\delta)$-DP
mechanism $\mathcal{M}:\mathcal{X}^{n}\to\mathcal{Y}$ such that
$\Pr[\mathcal{M}(x)\in\mathcal{G}_{x}]\geq p$ for every $x\in\mathcal{C}$,
then

$\frac{1}{|\mathcal{C}|}\geq p\cdot e^{-m\cdot\varepsilon}-m\delta.$

###### Proof of Theorem 5.7.

For the packing argument, we construct a collection of datasets similar to
those used by [DNPR10]. Let $f:{\left\\{{0,1}\right\\}}^{T}\to\mathbb{R}^{T}$
be the function for binary counting described in Theorem 5.7.

We first construct a collection $\mathcal{C}$ of $k={\lfloor{T/m}\rfloor}$
datasets in ${\left\\{{0,1}\right\\}}^{T}$. We will construct all of these
datasets to be at Hamming distance $m$ from the all 0s dataset $x_{0}=0^{T}$.

The collection $\mathcal{C}$ contains the following $k$ datasets. For each
$i\in[k]$, construct the ${i}^{\mathrm{th}}$ dataset
$x_{i}=0^{m\cdot(i-1)}\circ 1^{m}\circ 0^{T-m\cdot i}$. That is, each dataset
is a set of $k-1$ blocks of $m$ consecutive 0s,999The end of the stream may be
padded with additional 0s to ensure it has length $T$. and one block of $m$
consecutive 1s, where dataset $i$ has its ${i}^{\mathrm{th}}$ block contain
the consecutive 1s.

We see that all of these datasets are Hamming distance $m$ from the all 0s
dataset $x_{0}$. We also see that, for all $x\neq x^{\prime}\in\mathcal{C}$,

$||f(x)-f(x^{\prime})||_{\infty}>m/2.$ (8)

Let $\mathcal{G}_{x_{i}}$ be the closed $\ell_{\infty}$ ball of radius
$\alpha=m/2$ around $f(x_{i})$. By (8) we see that the collection of sets
${\left\\{{\mathcal{G}_{x_{i}}}\right\\}}_{x_{i}\in\mathcal{C}}$ is disjoint.

If $\mathcal{M}$ is $(\varepsilon,\delta)$-DP and $(\alpha,T)$-accurate for
the binary counting function $f$, then on input $x_{i}$ it must give an answer
in $\mathcal{G}_{x_{i}}$ with probability $p\geq 0.99$. We can now use a
packing argument to solve for $\alpha$. Lemma 5.8 tells us

$\displaystyle\frac{1}{|\mathcal{C}|}$ $\displaystyle\geq p\cdot
e^{-m\varepsilon}-m\delta$ $\displaystyle\frac{1}{k}$
$\displaystyle\geq\frac{e^{-m\varepsilon}}{2}-m\delta$ ($|\mathcal{C}|=k$,
$p\geq 0.5$) $\displaystyle\frac{e^{-m\varepsilon}}{2}$
$\displaystyle\leq\frac{1}{k}+m\delta.$

Recall $k={\lfloor{T/m}\rfloor}$, so $k\geq(T-m)/m$. Additionally, recall
$\alpha=m/2$ and by assumption $\delta=O(1/T)$. This gives us

$\displaystyle e^{-\alpha\varepsilon/2}$
$\displaystyle=O{\left({\frac{m}{T-m}+m\cdot\frac{1}{T}}\right)}$
$\displaystyle=O{\left({\frac{\alpha}{T-\alpha}}\right)}.$

Taking the reciprocal of each side gives us

$\displaystyle e^{\alpha\varepsilon/2}$
$\displaystyle=\Omega{\left({\frac{T-\alpha}{\alpha}}\right)},$

and taking the log gives us

$\alpha\varepsilon=\Omega{\left({\log T-\log\alpha}\right)}.$

We want to solve for $\alpha$ such that
$\alpha\varepsilon+\log\alpha=\Omega(\log T)$. This leaves us with two cases:
$\alpha\varepsilon=\Omega(\log\alpha)$ and $\alpha\varepsilon=O(\log\alpha)$.
In the first case, $\alpha\varepsilon$ dominates, so we need
$\alpha=\Omega(\log T/\varepsilon)$. In the second case, $\log\alpha$
dominates, so we need $\alpha=\Omega(T)$. Therefore,

$\alpha=\Omega{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)},$

which is what we wanted to show. ∎

We now prove Theorems 5.5 and 5.6 through reductions from binary counting.

###### Proof of Theorem 5.5.

Let $x\in{\left\\{{0,1}\right\\}}^{T}$ be a binary stream. Below, we describe
functions that take $x$ as input and return a graph stream where the count of
some feature (e.g., triangles) at each time step $t$ can be used to compute
the corresponding prefix sum of the binary stream through time step $t$.
Crucially, the functions described below map neighboring binary streams to
node-neighboring $(D,0)$-bounded graph streams (i.e., graph streams with
maximum degree at most $D$).

We use the following notation: let $x_{i}$ and $\mathit{S}_{i}$ denote the
${i}^{\mathrm{th}}$ index of the binary stream and graph stream, respectively.
Additionally, the statements below assume $\delta=O(1/T)$. Note that our
mappings from binary streams to $f_{\mathsf{edges}}$ and
$f_{\mathsf{degree\text{-}hist}}$ are similar to the mappings used by [FHO21],
though our other mappings are different and yield stronger lower bounds.

  1. 1.

(Edges.) For each time step $t\in[T]$, let $\mathit{S}_{t}$ contain $D$
isolated nodes. If $x_{t}=1$, also include a node $v_{t}$ with edges to all
other nodes that arrived in that time step. Therefore, each time step contains
either $0$ new edges or $D$ new edges.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-node-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{edges}}$ with
$(\alpha,T)$-accuracy where $\alpha=o{\left({\min{\left\\{{\frac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}$. Then applying the transformation
described above to a binary stream, running $\mathcal{M}$ on the resulting
stream, and dividing the output at each time step by $D$ will solve binary
counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  2. 2.

(Triangles.) For each time step $t\in[T]$, let $\mathit{S}_{t}$ contain a
complete graph on $D$ nodes. If $x_{t}=1$, also include a node $v_{t}$ with
edges to all other nodes. Therefore, each time step contains either
$\binom{D}{3}$ new triangles or $\binom{D+1}{3}=\binom{D}{3}+\binom{D}{2}$ new
triangles.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-node-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{triangles}}$ with
$(\alpha,T)$-accuracy where $\alpha=o{\left({\min{\left\\{{\frac{D^{2}\log
T}{\varepsilon},D^{2}T}\right\\}}}\right)}$. Then applying the transformation
described above to a binary stream, running $\mathcal{M}$ on the resulting
stream, subtracting $\binom{D}{3}$ from the output at each time step and
dividing this result by $\binom{D}{2}=\Theta(D^{2})$ will solve binary
counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  3. 3.

(Connected components.) For each time step $t\in[T]$, let $\mathit{S}_{t}$
contain $D$ isolated nodes. If $x_{t}=1$, also include a node $v_{t}$ with
edges to all other nodes that arrived in that time step. Therefore, each time
step contains either $1$ new connected component or $D$ new connected
components.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-node-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{CC}}$ with
$(\alpha,T)$-accuracy where $\alpha=o{\left({\min{\left\\{{\frac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}$. Then applying the transformation
described above to a binary stream, running $\mathcal{M}$ on the resulting
stream, and dividing the output at each time step by $D-1$ will solve binary
counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  4. 4.

($\bm{k}$-stars.) For each time step $t\in[T]$, let $\mathit{S}_{t}$ contain
$D$ isolated nodes. If $x_{t}=1$, also include a node $v_{t}$ with edges to
all other nodes that arrived in that time step. Therefore, each time step
contains either $0$ new $k$-stars or $\binom{D}{k}$ new $k$-stars.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-node-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{k\text{-}stars}}$ with
$(\alpha,T)$-accuracy where $\alpha=o{\left({\min{\left\\{{\frac{D^{k}\log
T}{\varepsilon},D^{k}T}\right\\}}}\right)}$. Then applying the transformation
described above to a binary stream, running $\mathcal{M}$ on the resulting
stream, and dividing the output at each time step by
$\binom{D}{k}=\Theta(D^{k})$ will solve binary counting with error
$\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  5. 5.

(Degree histograms.) For each time step $t\in[T]$, let $\mathit{S}_{t}$
contain $D$ isolated nodes. If $x_{t}=1$, also include a node $v_{t}$ with
edges to all other nodes that arrived in that time step. Therefore, the
histogram bin for nodes of degree $1$ increases each time step by either 0 new
nodes or $D$ new nodes.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-node-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{degree\text{-}hist}}$ that has
$(\alpha,T)$-accuracy for some bin with
$\alpha=o{\left({\min{\left\\{{\frac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}$. Without loss of generality, let it be
the bin for nodes of degree $1$. Then applying the transformation described
above to a binary stream, running $\mathcal{M}$ on the resulting stream, and
dividing the output for the bin for degree 1 at each time step by $D$ will
solve binary counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7. ∎

The reductions from binary counting that we use to prove Theorem 5.6 are
similar to the reductions above for proving Theorem 5.5, though they instead
map neighboring binary streams to edge-neighboring graph streams.

###### Proof of Theorem 5.6.

As above, let $x\in{\left\\{{0,1}\right\\}}^{T}$ be a binary stream. We
describe functions that take $x$ as input and return a graph stream where the
count of some feature (e.g., triangles) at each time step $t$ can be used to
compute the corresponding prefix sum of the binary stream through time step
$t$. Crucially, the functions described below map neighboring binary streams
to edge-neighboring $(D,0)$-bounded graph streams (i.e., graph streams with
maximum degree at most $D$).

We use the following notation: let $x_{i}$ and $\mathit{S}_{i}$ denote the
${i}^{\mathrm{th}}$ index of the binary stream and graph stream, respectively.
Additionally, the statements below assume $\delta=O(1/T)$. Note that our
mappings from binary streams to $f_{\mathsf{edges}}$ and
$f_{\mathsf{degree\text{-}hist}}$ are similar to the mappings used by [FHO21],
though our other mappings are different and yield stronger lower bounds.

  1. 1.

(Edges.) For each time step $t\in[T]$, let $\mathit{S}_{t}$ contain two
isolated nodes $u_{t},v_{t}$. If $x_{t}=1$, also include an edge
${\left\\{{u_{t},v_{t}}\right\\}}$. Therefore, each time step contains either
$0$ new edges or $1$ new edge.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-node-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{edges}}$ with
$(\alpha,T)$-accuracy on each bin where
$\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$. Then applying the transformation
described above to a binary stream, running $\mathcal{M}$ on the resulting
stream, and releasing the result will solve binary counting with error
$\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  2. 2.

(Triangles.) For each time step $t\in[T]$, let $\mathit{S}_{t}$ contain the
following structure: $D-1$ nodes $w^{1}_{t},\ldots w^{D-1}_{t}$, and two nodes
$u_{t},v_{t}$, each with an edge to every node of the form $w^{i}_{t}$. If
$x_{t}=1$, also include an edge ${\left\\{{u_{t},v_{t}}\right\\}}$. Therefore,
each time step contains either $0$ new triangles or $D-1$ new triangles.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-edge-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{triangles}}$ with
$(\alpha,T)$-accuracy where $\alpha=o{\left({\min{\left\\{{\frac{D\log
T}{\varepsilon},DT}\right\\}}}\right)}$. Then applying the transformation
described above to a binary stream, running $\mathcal{M}$ on the resulting
stream, and dividing the output at each time step by $D-1$ will solve binary
counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  3. 3.

(Connected components.) For each time step $t\in[T]$, let $\mathit{S}_{t}$
contain two isolated nodes $u_{t},v_{t}$. If $x_{t}=1$, also include an edge
${\left\\{{u_{t},v_{t}}\right\\}}$. Therefore, each time step contains either
$1$ new connected component or $2$ new connected components.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-edge-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{CC}}$ with
$(\alpha,T)$-accuracy where $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$. Then applying the transformation
described above to a binary stream, running $\mathcal{M}$ on the resulting
stream, and subtracting 1 from the output at each time step will solve binary
counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  4. 4.

($\bm{k}$-stars.) For each time step $t\in[T]$, let $\mathit{S}_{t}$ contain a
$(D-1)$-star with center node $c_{t}$, plus one isolated node $v_{t}$. If
$x_{t}=1$, also include the edge ${\left\\{{c_{t},v_{t}}\right\\}}$.
Therefore, each time step contains either $\binom{D-1}{k}$ new $k$-stars or
$\binom{D}{k}=\binom{D-1}{k}+\binom{D-1}{k-1}$ new $k$-stars.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-edge-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{k\text{-}stars}}$ with
$(\alpha,T)$-accuracy where $\alpha=o{\left({\min{\left\\{{\frac{D^{k-1}\log
T}{\varepsilon},D^{k-1}T}\right\\}}}\right)}$. Then applying the
transformation described above to a binary stream, running $\mathcal{M}$ on
the resulting stream, subtracting $\binom{D-1}{k}$ from the output at each
time step and dividing this result by $\binom{D-1}{k-1}=\Theta(D^{k-1})$ will
solve binary counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.

  5. 5.

(Degree histograms.) For each time step $t\in[T]$, let $\mathit{S}_{t}$
contain two isolated nodes $u_{t},v_{t}$. If $x_{t}=1$, also include an edge
${\left\\{{u_{t},v_{t}}\right\\}}$. Therefore, the histogram bin for nodes of
degree $1$ increases each time step by either $0$ new nodes or $2$ new nodes.

Assume for contradiction that there exists an $(\varepsilon,\delta)$-node-DP
mechanism $\mathcal{M}$ for solving $f_{\mathsf{degree\text{-}hist}}$ that has
$(\alpha,T)$-accuracy for some bin with
$\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$. Without loss of generality, let it be
the bin for nodes of degree $1$. Then applying the transformation described
above to a binary stream, running $\mathcal{M}$ on the resulting stream, and
dividing the output for the bin for degree 1 at each time step by $2$ will
solve binary counting with error $\alpha=o{\left({\min{\left\\{{\frac{\log
T}{\varepsilon},T}\right\\}}}\right)}$, which contradicts Theorem 5.7.∎

## References

  * [BBDS13] Jeremiah Blocki, Avrim Blum, Anupam Datta and Or Sheffet  “Differentially private data analysis of social networks via restricted sensitivity”  In _Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013_ ACM, 2013, pp. 87–96  DOI: 10.1145/2422436.2422449
  * [BBKN14] Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan and Kobbi Nissim  “Bounds on the sample complexity for private learning and private data release”  In _Mach. Learn._ 94.3, 2014, pp. 401–437  DOI: 10.1007/S10994-013-5404-1
  * [BCSZ18] Christian Borgs, Jennifer T. Chayes, Adam D. Smith and Ilias Zadik  “Private Algorithms Can Always Be Extended”  In _CoRR_ abs/1810.12518, 2018  arXiv: http://arxiv.org/abs/1810.12518
  * [BCSZ18a] Christian Borgs, Jennifer T. Chayes, Adam D. Smith and Ilias Zadik  “Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation”  In _Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS)_ , 2018, pp. 533–543  DOI: 10.1109/FOCS.2018.00057
  * [BS10] Jennifer Badham and Rob Stocker  “The impact of network clustering and assortativity on epidemic behaviour”  In _Theor. Popul. Biol._ 77.1 Elsevier BV, 2010, pp. 71–75  URL: https://pubmed.ncbi.nlm.nih.gov/19948179/
  * [CD20] Rachel Cummings and David Durfee  “Individual Sensitivity Preprocessing for Data Privacy”  In _Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2020, pp. 528–547  DOI: 10.1137/1.9781611975994.32
  * [CSS11] T.-H. Chan, Elaine Shi and Dawn Song  “Private and Continual Release of Statistics”  In _ACM Trans. Inf. Syst. Secur._ 14.3, 2011, pp. 26:1–26:24  DOI: 10.1145/2043621.2043626
  * [CSS18] Beidi Chen, Anshumali Shrivastava and Rebecca C Steorts  “Unique entity estimation with application to the Syrian conflict”  In _The Annals of Applied Statistics_ 12.2, 2018, pp. 1039–1067  DOI: 10.1214/18-AOAS1163
  * [CZ13] Shixi Chen and Shuigeng Zhou  “Recursive mechanism: towards node differential privacy and unrestricted joins”  In _Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013_ ACM, 2013, pp. 653–664  DOI: 10.1145/2463676.2465304
  * [DL09] Cynthia Dwork and Jing Lei  “Differential privacy and robust statistics”  In _Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009_ ACM, 2009, pp. 371–380  DOI: 10.1145/1536414.1536466
  * [DLL16] Wei-Yen Day, Ninghui Li and Min Lyu  “Publishing Graph Degree Distribution with Node Differential Privacy”  In _Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016_ ACM, 2016, pp. 123–138  DOI: 10.1145/2882903.2926745
  * [DMNS16] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam D. Smith  “Calibrating Noise to Sensitivity in Private Data Analysis”  In _J. Priv. Confidentiality_ 7.3, 2016, pp. 17–51  DOI: 10.29012/jpc.v7i3.405
  * [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi and Guy N. Rothblum  “Differential privacy under continual observation”  In _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ ACM, 2010, pp. 715–724  DOI: 10.1145/1806689.1806787
  * [DNR+09] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum and Salil P. Vadhan  “On the complexity of differentially private data release: efficient algorithms and hardness results”  In _Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009_ ACM, 2009, pp. 381–390  DOI: 10.1145/1536414.1536467
  * [DRV10] Cynthia Dwork, Guy N. Rothblum and Salil P. Vadhan  “Boosting and Differential Privacy”  In _51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA_ IEEE Computer Society, 2010, pp. 51–60  DOI: 10.1109/FOCS.2010.12
  * [FHO21] Hendrik Fichtenberger, Monika Henzinger and Wolfgang Ost  “Differentially Private Algorithms for Graphs Under Continual Observation”  In _CoRR_ abs/2106.14756, 2021  arXiv: https://arxiv.org/abs/2106.14756
  * [Goo49] Leo A. Goodman  “On the Estimation of the Number of Classes in a Population”  In _The Annals of Mathematical Statistics_ 20.4 Institute of Mathematical Statistics, 1949, pp. 572–579  URL: http://www.jstor.org/stable/2236312
  * [HLMJ09] Michael Hay, Chao Li, Gerome Miklau and David D. Jensen  “Accurate Estimation of the Degree Distribution of Private Networks”  In _ICDM 2009, The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA, 6-9 December 2009_ IEEE Computer Society, 2009, pp. 169–178  DOI: 10.1109/ICDM.2009.11
  * [HR10] Moritz Hardt and Guy N. Rothblum  “A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis”  In _51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA_ IEEE Computer Society, 2010, pp. 61–70  DOI: 10.1109/FOCS.2010.85
  * [HT10] Moritz Hardt and Kunal Talwar  “On the geometry of differential privacy”  In _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ ACM, 2010, pp. 705–714  DOI: 10.1145/1806689.1806786
  * [JM09] Carter Jernigan and Behram F.. Mistree  “Gaydar: Facebook Friendships Expose Sexual Orientation”  In _First Monday_ 14.10, 2009  URL: https://doi.org/10.5210/fm.v14i10.2611
  * [JRSS23] Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar and Adam D. Smith  “The Price of Differential Privacy under Continual Observation”  In _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ 202, Proceedings of Machine Learning Research  PMLR, 2023, pp. 14654–14678  URL: https://proceedings.mlr.press/v202/jain23b.html
  * [KNRS13] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova and Adam D. Smith  “Analyzing Graphs with Node Differential Privacy”  In _Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings_ 7785, Lecture Notes in Computer Science  Springer, 2013, pp. 457–476  DOI: 10.1007/978-3-642-36594-2˙26
  * [KRST23] Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith and Charalampos E. Tsourakakis  “Node-Differentially Private Estimation of the Number of Connected Components”  In _Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023, Seattle, WA, USA, June 18-23, 2023_ ACM, 2023, pp. 183–194  DOI: 10.1145/3584372.3588671
  * [LSL17] Min Lyu, Dong Su and Ninghui Li  “Understanding the Sparse Vector Technique for Differential Privacy”  In _Proc. VLDB Endow._ 10.6, 2017, pp. 637–648  DOI: 10.14778/3055330.3055331
  * [NRS07] Kobbi Nissim, Sofya Raskhodnikova and Adam D. Smith  “Smooth sensitivity and sampling in private data analysis”  In _Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007_ ACM, 2007, pp. 75–84  DOI: 10.1145/1250790.1250803
  * [RR10] Aaron Roth and Tim Roughgarden  “Interactive privacy via the median mechanism”  In _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ ACM, 2010, pp. 765–774  DOI: 10.1145/1806689.1806794
  * [RS16] Sofya Raskhodnikova and Adam D. Smith  “Differentially Private Analysis of Graphs”  In _Encyclopedia of Algorithms_ , 2016, pp. 543–547  DOI: 10.1007/978-1-4939-2864-4“˙549
  * [RS16a] Sofya Raskhodnikova and Adam D. Smith  “Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism”  In _Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS)_ , 2016, pp. 495–504  DOI: 10.1109/FOCS.2016.60
  * [SLM+18] Shuang Song, Susan Little, Sanjay Mehta, Staal A. Vinterbo and Kamalika Chaudhuri  “Differentially Private Continual Release of Graph Statistics”  In _CoRR_ abs/1809.02575, 2018  arXiv: http://arxiv.org/abs/1809.02575
  * [Upa13] Jalaj Upadhyay  “Random projections, graph sparsification, and differential privacy”  In _ASIACRYPT (1)_ 8269, 2013, pp. 276–295  DOI: 10.1007/978-3-642-42033-7“˙15
  * [UUA21] Jalaj Upadhyay, Sarvagya Upadhyay and Raman Arora  “Differentially Private Analysis on Graph Streams”  In _The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event_ 130, Proceedings of Machine Learning Research  PMLR, 2021, pp. 1171–1179  URL: http://proceedings.mlr.press/v130/upadhyay21a.html
  * [Vad17] Salil P. Vadhan  “The Complexity of Differential Privacy”  In _Tutorials on the Foundations of Cryptography_ Springer International Publishing, 2017, pp. 347–450  DOI: 10.1007/978-3-319-57048-8˙7
  * [YJM+13] A M Young, A B Jonas, U L Mullins, D S Halgin and J R Havens  “Network structure and the risk for HIV transmission among rural drug users”  In _AIDS Behav._ 17.7 Springer ScienceBusiness Media LLC, 2013, pp. 2341–2351  URL: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3600060/

##  Appendix A The Sparse Vector Technique

In this section, we describe the sparse vector technique, introduced by
[DNR+09] and refined by [RR10, HR10, LSL17], and some of its standard
properties. We use the sparse vector technique to continually check that the
input graph satisfies the conditions of Theorem 3.3. In Algorithm 6, we
provide a version of the sparse vector technique described in [LSL17,
Algorithm 1], and throughout the rest of Appendix A, we prove some useful
properties of this algorithm. Theorem A.2 presents accuracy properties of
Algorithm 6 that we use in our construction of the general transformation
described in Section 4.3 from (restricted) private algorithms to node-private
algorithms. To prove this statement, we use Lemmas A.4 and A.5, which present
slight variations on standard theorems about accuracy guarantees for the
sparse vector technique.

Algorithm 6 Mechanism $\mathsf{SVT}$ for answering threshold queries with the
sparse vector technique.

1:Input: Stream $\mathit{S}\in\mathcal{S}^{T}$; queries $q_{1},q_{2},\ldots$
of sensitivity 1; cutoff $c\in\mathbb{N}$; privacy parameter $\varepsilon>0$;
threshold $\tau\in\mathbb{R}$.

2:Output: Stream of answers in $\\{\bot,\top\\}$.

3:$\varepsilon_{1}=\varepsilon_{2}=\varepsilon/2$

4:$\mathsf{count}=0$

5:Draw $Z\sim\mathit{Lap}(1/\varepsilon_{1})$

6:for each time $t\in 1,2,\dots,T$ do

7: Draw $Z_{t}\sim\mathit{Lap}(2c/\varepsilon_{2})$

8: if $q_{t}(\mathit{S})+Z_{t}\geq\tau+Z$ and $\mathsf{count}<c$ then

9: Output $\bot$

10: $\mathsf{count}\mathrel{+}=1$

11: else output $\top$

We now give some properties of Algorithm 6. We first provide a theorem on the
privacy of Algorithm 6.

######  Theorem A.1 (Privacy of $\mathsf{SVT}$ [LSL17]).

Algorithm 6 is $(\varepsilon,0)$-DP under continual observation.

We next provide a statement on the accuracy of Algorithm 6.

######  Theorem A.2 (Separation needed for accurate answers).

Consider Algorithm 6, and let $\mathit{S}\in\mathcal{S}^{T}$,
$c\in\mathbb{N}$, $\varepsilon>0$, $\tau\in\mathbb{R}$.

  1. 1.

(True answer is above the threshold.) Fix $\delta\in(0,1]$. To ensure that
Algorithm 6 outputs $\bot$ at or before time step $t$ with probability at
least $1-\delta$, it suffices to have

$q_{t}(\mathit{S})\geq 8c\ln(1/\delta)/\varepsilon+\tau.$

  2. 2.

(True answer is below the threshold.) Fix $t^{\prime}\in[T]$ and
$\beta\in(0,1]$. To ensure that Algorithm 6 outputs $\top$ on all queries
$q_{1},\ldots,q_{t^{\prime}}$ with probability at least $1-\beta$, it suffices
to have

$q_{t}(\mathit{S})\leq 8c\ln(\beta/T)/\varepsilon+\tau$

for all $t\leq t^{\prime}$.

To prove Theorem A.2, we use several lemmas presented below. The proof of
Theorem A.2 appears at the end of this section.

######  Lemma A.3.

Let $\mathit{S}\in\mathcal{S}^{T}$, $c\in\mathbb{N}$, $\varepsilon>0$,
$\tau\in\mathbb{R}$, and $\varepsilon_{1}=\varepsilon_{2}=\varepsilon/2$.
Additionally, let $Z\sim\mathit{Lap}(1/\varepsilon_{1})$ and
$Z_{t}\sim\mathit{Lap}(2c/\varepsilon_{2})$. For all $x\in\mathbb{R}$ and
queries $q_{t}$,

  1. 1.

if $x\geq 0$ and $q_{t}(\mathit{S})\geq x+\tau$, then

$\Pr\left[{q_{t}(\mathit{S})+Z_{t}\leq\tau+Z}\right]\leq\exp\left(\frac{-|x|\cdot\varepsilon}{8c}\right).$

  2. 2.

if $x\leq 0$ and $q_{t}(\mathit{S})\leq x+\tau$, then

$\Pr\left[{q_{t}(\mathit{S})+Z_{t}\geq\tau+Z}\right]\leq\exp\left(\frac{-|x|\cdot\varepsilon}{8c}\right).$

###### Proof of Lemma A.3.

We begin by proving item (1). Assume that $x\geq 0$ and $q_{t}(\mathit{S})\geq
x+\tau$. We have the following expressions:

$\displaystyle\Pr\left[{q_{t}(\mathit{S})+Z_{t}\leq\tau+Z}\right]$
$\displaystyle\leq\Pr\left[{x+\tau+Z_{t}\leq\tau+Z}\right]$ (given
$q_{t}(\mathit{S})\geq x+\tau$) $\displaystyle=\Pr\left[{x\leq
Z-Z_{t}}\right]$ $\displaystyle=\Pr\left[{x\leq Z+Z_{t}}\right]$ ($Z_{t}$ and
$Z$ are independent, symmetric r.v.s) $\displaystyle\leq\Pr\left[{x/2\leq
Z\cup x/2\leq Z_{t}}\right]$ (at least one must occur for the line above)
$\displaystyle\leq\Pr\left[{x/2\leq Z}\right]+\Pr\left[{x/2\leq Z_{t}}\right]$
(union bound)
$\displaystyle=\frac{1}{2}\exp\left(\frac{-x}{2}\cdot\varepsilon/2\right)+\frac{1}{2}\exp\left(\frac{-x}{2}\cdot\frac{\varepsilon/2}{2c}\right)$
(Laplace CDF, r.v.s are continuous)
$\displaystyle\leq\exp\left(\frac{-x\varepsilon}{8c}\right),$
($\exp\left(\dfrac{-x}{2}\cdot\dfrac{\varepsilon/2}{2c}\right)\geq\exp\left(\dfrac{-x}{2}\cdot\varepsilon/2\right)$,
for $x\geq 0$)

which complete the proof of item (1).

The proof of item (2) follows from item (1), and from the symmetry of Laplace
r.v.s and the fact that $Z$ and $Z_{t}$ are independent. ∎

Lemma A.4 uses Lemma A.3 to show a lower bound on the probability that
Algorithm 6 returns $\bot$ when the true answer to the query $q_{t}$ is (at
least) some value $x\geq 0$ above the threshold $\tau$. Similarly, Lemma A.5
uses Lemma A.3 to show a lower bound on the probability that Algorithm 6
exclusively outputs values of $\top$ when the threshold $\tau$ is (at least)
some value $-x\geq 0$ above the true answer to each query
$q_{1},\ldots,q_{t^{\prime}}$.

######  Lemma A.4 (Probability of $\bot$ for $q_{t}(\mathit{S})\geq x+\tau$).

Consider Algorithm 6, and let $\mathit{S}\in\mathcal{S}^{T}$,
$c\in\mathbb{N}$, $\varepsilon>0$, $\tau\in\mathbb{R}$. For all $x\geq 0$ and
queries $q_{1},q_{2},\ldots$, if $q_{t}(\mathit{S})\geq x+\tau$, then
Algorithm 6 outputs $\bot$ at or before time step $t$ with probability at
least

$1-\exp\left(\frac{-x\varepsilon}{8c}\right).$

###### Proof of Lemma A.4.

Consider the event that we have $q_{t}(\mathit{S})+Z_{t}\geq\tau+Z$. If this
event occurs, either $\bot$ will be output, or $\bot$ was output at some
earlier time step. When the conditions in the theorem statement above hold, by
item (1) of Lemma A.3 this event occurs with probability at least

$1-\exp\left(\frac{-x\varepsilon}{8c}\right),$

which completes the proof. ∎

######  Lemma A.5 (Probability of $\top$ for stream
$q_{1}(\mathit{S}),\ldots,q_{t^{\prime}}(\mathit{S})\leq x+\tau$).

Consider Algorithm 6, and let $\mathit{S}\in\mathcal{S}^{T}$,
$c\in\mathbb{N}$, $\varepsilon>0$, $\tau\in\mathbb{R}$. Fix
$t^{\prime}\in[T]$. For all $x\leq 0$ and query streams $q_{1},q_{2},\ldots$,
if for all $t\leq t^{\prime}$ we have $q_{t}(\mathit{S})\leq x+\tau$, then
Algorithm 6 outputs $\top$ for all time steps $t\leq t^{\prime}$ with
probability at least

$1-T\cdot\exp\left(\frac{x\varepsilon}{8c}\right).$

###### Proof of Lemma A.5.

Consider the event that, for all $t\leq t^{\prime}$, we have
$q_{t}(\mathit{S})+Z_{t}<\tau+Z$. If this event occurs, the output at each
time step $t\leq t^{\prime}$ is $\top$. We now consider the complement of this
event. When the conditions in the theorem statement above hold, by item (2) of
Lemma A.3 and the union bound, this complement occurs with probability at most

$T\cdot\exp\left(\frac{x\varepsilon}{8c}\right).$

Therefore, the event in which we’re interested occurs with probability at
least

$1-T\cdot\exp\left(\frac{x\varepsilon}{8c}\right),$

which completes the proof. ∎

Parts (1) and (2) of Theorem A.2 follow from Lemmas A.4 and A.5, respectively,
and show how far above or below the threshold $\tau$ it suffices to have the
true query answers to ensure that Algorithm 6 outputs $\bot$ or $\top$ with
some user-specified probability.

###### Proof of Theorem A.2.

We prove each item below.

(Item 1.) Let $A$ be the event that Algorithm 6 outputs $\bot$ at or before
time step $t$. We observe that we want $\Pr\left[{A}\right]\geq 1-\delta$.
Consider the case where we have $q_{t}(\mathit{S})\geq
8c\ln(1/\delta)/\varepsilon+\tau$. By Lemma A.4, where we set
$x=8c\ln(1/\delta)/\varepsilon$, we have

$\Pr\left[{A}\right]\geq 1-\exp\left(\frac{-x\varepsilon}{8c}\right).$ (9)

Substituting $x=8c\ln(1/\delta)/\varepsilon$ into Expression 9 gives us

$\displaystyle\Pr\left[{A}\right]$ $\displaystyle\geq
1-\exp\left(\frac{-\varepsilon\cdot 8c\ln(1/\delta)/\varepsilon}{8c}\right)$
$\displaystyle=1-\exp(-\ln(1/\delta))$ $\displaystyle=1-\delta.$

Therefore, we have $\Pr\left[{A}\right]\geq 1-\delta$ when we have
$q_{t}(\mathit{S})\geq 8c\ln(1/\delta)/\varepsilon+\tau$, which is what we
wanted to show.

(Item 2.) Let $B$ be the event that Algorithm 6 outputs $\top$ on all queries
$q_{1},\ldots,q_{t^{\prime}}$. We observe that we want
$\Pr\left[{B}\right]\geq 1-\beta$. Consider the case where, for all $t\leq
t^{\prime}$, we have $q_{t}(\mathit{S})\leq 8c\ln(\beta/T)/\varepsilon+\tau$.
By Lemma A.5,

$\Pr\left[{B}\right]\geq 1-T\cdot\exp\left(\frac{x\varepsilon}{8c}\right).$
(10)

Substituting $x=8c\ln(\beta/T)/\varepsilon$ into Expression 10 gives us

$\displaystyle\Pr\left[{B}\right]$ $\displaystyle\geq
1-T\cdot\exp\left(\frac{\varepsilon\cdot
8c\ln(\beta/T)/\varepsilon}{8c}\right)$
$\displaystyle=1-T\cdot\exp(\ln(\beta/T)$ $\displaystyle=1-T\cdot\beta/T$
$\displaystyle=1-\beta.$

Therefore, we have $\Pr\left[{B}\right]\geq 1-\beta$ when we have
$q_{t}(\mathit{S})\leq 8c\ln(\beta/T)/\varepsilon+\tau$ for all
$t\in[t^{\prime}]$, which is what we wanted to show. ∎

##  Appendix B Tightness of Stabilities in Theorem 3.3

In Lemma B.1, we show that the upper bounds on stability in Theorem 3.3 are
tight: the worst-case lower bounds on stability are tight up to small additive
constants for $\Pi^{\text{\tiny BBDS}}_{D}$, and are tight up to constant
multiplicative factors for $\Pi^{\text{\tiny DLL}}_{D}$. The lower bounds
given in Lemma B.1 are for input graphs. Recall from Remark 3.1 that Algorithm
1 treats an input graph as a length-$1$ graph stream, so graphs can be viewed
as a special case of graph streams.

######  Lemma B.1 (Tightness of Theorem 3.3).

Let $D\in\mathbb{N}$, $\ell\in\mathbb{N}\cup\\{0\\}$, and let
$\Pi^{\text{\tiny BBDS}}_{D},\Pi^{\text{\tiny DLL}}_{D}$ be Algorithm 1 with
inclusion criterion $\mathsf{c}=\mathit{original}$ and
$\mathsf{c}=\mathit{projected}$, respectively.

  1. 1.

(Edge-to-edge stability.) There exist

    1. (a)

edge-neighboring graphs $G,G^{\prime}$ such that
$d_{\mathit{edge}}\Big{(}\Pi^{\text{\tiny BBDS}}_{D}(G)\ ,\ \Pi^{\text{\tiny
BBDS}}_{D}(G^{\prime})\Big{)}=3.$

    2. (b)

edge-neighboring, $(D,\ell)$-bounded graphs $G,G^{\prime}$ such that
$d_{\mathit{edge}}\Big{(}\Pi^{\text{\tiny DLL}}_{D}(G)\ ,\ \Pi^{\text{\tiny
DLL}}_{D}(G^{\prime})\Big{)}=\ell+1.$

  2. 2.

(Node-to-edge stability.) There exist

    1. (a)

node-neighboring, $(D,\ell)$-bounded graphs $G,G^{\prime}$ such that
$d_{\mathit{edge}}\Big{(}\Pi^{\text{\tiny BBDS}}_{D}(G)\ ,\ \Pi^{\text{\tiny
BBDS}}_{D}(G^{\prime})\Big{)}=D+\ell-1.$

    2. (b)

node-neighboring, $(D,\ell)$-bounded graphs $G,G^{\prime}$ such that, for $D$
and $\ell$ sufficiently large,

$d_{\mathit{edge}}\Big{(}\Pi^{\text{\tiny DLL}}_{D}(G)\ ,\ \Pi^{\text{\tiny
DLL}}_{D}(G^{\prime})\Big{)}=\begin{cases}D+\Omega(\ell^{3/2})&\text{if
}D\geq\ell,\ \text{and}\\\ D+\Omega(\ell\sqrt{D})&\text{if }D<\ell.\\\
\end{cases}$

  3. 3.

(Node-to-node stability.) There exist

    1. (a)

node-neighboring, $(D,\ell)$-bounded graphs $G,G^{\prime}$ such that
$d_{\mathit{node}}\Big{(}\Pi^{\text{\tiny BBDS}}_{D}(G)\ ,\ \Pi^{\text{\tiny
BBDS}}_{D}(G^{\prime})\Big{)}=2\ell-1.$

    2. (b)

node-neighboring, $(D,\ell)$-bounded graphs $G,G^{\prime}$ such that
$d_{\mathit{node}}\Big{(}\Pi^{\text{\tiny DLL}}_{D}(G)\ ,\ \Pi^{\text{\tiny
DLL}}_{D}(G^{\prime})\Big{)}=\ell+1.$

For the proof below, we construct pairs of graphs (each of which can be viewed
as a length-$1$ graph stream) with the above-specified distances between their
projections. Note that, for all $T\in\mathbb{N}$, the examples can be expanded
to length-$T$ graph streams by having no nodes or edges arrive in the
remaining $T-1$ time steps.

###### Proof of Lemma B.1.

We prove each item below. We begin by proving the statements for
$\Pi^{\text{\tiny BBDS}}_{D}$ (i.e., the “a” items) and then prove the
statements for $\Pi^{\text{\tiny DLL}}_{D}$ (i.e., the “b” items, with (2b)
proved last since its proof is the most involved).

(Item 1a.) Consider a pair of edge-neighboring graphs $G,G^{\prime}$, where
$G$ consists of two separate $D$-stars with centers $u$ and $v$, and where
$G^{\prime}$ is the same plus an additional edge $e^{+}$ between $u$ and $v$.
Additionally, let $e^{+}$ be the first edge in the consistent ordering. All
edges in $\mathit{S}$ are in $\Pi^{\text{\tiny BBDS}}_{D}(G)$. However,
$e^{+}$ is in $\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$ but is not in
$\Pi^{\text{\tiny BBDS}}_{D}(G)$. Additionally, one edge incident to $u$ is
not in $\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$, and one edge incident to $v$
is not in $\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$—otherwise, the projection
would have added new edges to $u$ and $v$ despite having counter values
$d(u)\geq D$ and $d(v)\geq D$.

(Item 2a.) We construct a pair of node-neighboring graphs $G,G^{\prime}$.
Graph $G$ consists of a set of $D$ nodes with no edges, and $\ell-1$ separate
$D$-stars. $G^{\prime}$ is the same, plus an additional node $v^{+}$ with an
edge to each of the $D$ empty nodes and each center of the $D$-stars.
Additionally, let all of the edges incident to $v^{+}$ appear before all other
edges in the consistent ordering, and let the $D$ edges incident to empty
nodes appear before all the other edges incident to $v^{+}$.

All edges in $G$ are in $\Pi^{\text{\tiny BBDS}}_{D}(G)$. However, all of the
first $D$ edges incident to $v^{+}$ are in $\Pi^{\text{\tiny
BBDS}}_{D}(G^{\prime})$ and are not in $\Pi^{\text{\tiny BBDS}}_{D}(G)$.
Additionally, one edge incident to the center of each $D$-star is not in the
projection because their counters are each at $D$ prior to the projection
stage of the final edge incident to each $D$-star’s center. There are $D$
edges incident to $v^{+}$ that appear in $\Pi^{\text{\tiny
BBDS}}_{D}(G^{\prime})$ and not $\Pi^{\text{\tiny BBDS}}_{D}(G)$; and there
are $\ell-1$ centers of $D$-stars, each of which is missing an edge in
$\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$ as compared to $\Pi^{\text{\tiny
BBDS}}_{D}(G)$. We see, then, that the projections differ on $D+\ell-1$ edges.

(Item 3a.) Consider the same example used for the proof of item (2a). To
obtain $\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$ from $\Pi^{\text{\tiny
BBDS}}_{D}(G)$, we see that it is necessary to add $v^{+}$. We also see that
it is necessary to change the edges incident to one node in each of the
$D$-stars. To change a node, it must be removed and then re-added with
different edges. Since there are $\ell-1$ separate $D$-stars, there are
$2\ell-2$ additions and removals of nodes in the $D$-stars, plus the addition
of $v^{+}$. Therefore, we see that $\Pi^{\text{\tiny BBDS}}_{D}(G)$ and
$\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$ are at node distance $2\ell-1$.

(Item 1b.) Consider the following pair of edge-neighboring graphs
$G,G^{\prime}$. Graph $G$ is constructed by taking two empty nodes $v$ and
$w$, and a set of $\ell$ separate $(D-1)$-stars, enumerating their centers
$u_{1},\ldots,u_{\ell}$, and then adding edges between $u_{i}$ and $u_{i+1}$
for all $i\in[\ell-1]$. Additionally, these edges should appear last in the
consistent ordering, and they should appear such that, for all $i\in[\ell-2]$,
edge $\\{u_{i},u_{i+1}\\}$ precedes $\\{u_{i+1},u_{i+2}\\}$. There should also
be an edge $\\{u_{\ell},w\\}$ that appears last in the consistent ordering.
Graph $G^{\prime}$ is constructed in the same way, except there is also an
edge $\\{v,u_{1}\\}$ that appears first in the consistent ordering.

In $\Pi^{\text{\tiny BBDS}}_{D}(G)$, the edge $\\{u_{1},u_{2}\\}$ appears
because $d(u_{1})=D-1$ and $d(u_{2})=D-1$ at the projection stage of the edge.
By contrast, $\\{u_{2},u_{3}\\}$ does not appear because $d(u_{2})=D$ at the
projection stage of the edge. By similar logic $\\{u_{3},u_{4}\\}$ appears,
$\\{u_{4},u_{5}\\}$ does not, and so on in this alternating fashion, with
$\\{u_{\ell},w\\}$ appearing if and only if $\ell$ is odd. On the other hand,
for $\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$ the edge $\\{v,u_{1}\\}$ appears
since $d(v)=D-1$ and $d(u_{1})=D-1$ at the projection stage of this edge. By
contrast, $\\{u_{1},u_{2}\\}$ does not appear since $d(u_{1})=D$ at the
projection stage of this edge. Similarly, $\\{u_{2},u_{3}\\}$ appears,
$\\{u_{3},u_{4}\\}$ does not, and so on, with $\\{u_{\ell},w\\}$ appearing if
and only if $\ell$ is even. We see that $\ell+1$ edges differ between
$\Pi^{\text{\tiny BBDS}}_{D}(G)$ and $\Pi^{\text{\tiny
BBDS}}_{D}(G^{\prime})$, which is what we wanted to show.

(Item 3b.) Consider the same example used for the proof of item (1b), with the
modification that $v$ does not appear in $G$. We see that to obtain
$\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$ from $\Pi^{\text{\tiny
BBDS}}_{D}(G)$ we need to—starting with $v$—remove every other node in the
path $v,u_{1},\ldots,u_{\ell},w$, and then add a modified version of each of
these nodes (except for $v$). There are $\ell+2$ nodes in the path, so we need
to remove $\lceil(\ell+2)/2\rceil\geq\ell/2+1$ nodes and add
$\lceil(\ell+1)/2\rceil\geq\ell/2$ nodes, so the node distance between
$\Pi^{\text{\tiny BBDS}}_{D}(G)$ and $\Pi^{\text{\tiny BBDS}}_{D}(G^{\prime})$
is at least $\ell+1$.

(Item 2b.) Let $k=\min\\{D,\ell\\}$. Before describing $G$ and $G^{\prime}$,
we construct a graph $P$ that is a collection of paths and contains
$\Omega(\ell\sqrt{k})$ edges, and we then show how to construct $G$ and
$G^{\prime}$ such that all edges in $P$ differ between the projections of $G$
and $G^{\prime}$. The high-level idea for $P$ is to construct $m=\lfloor
k/4\rfloor$ simple paths on $\ell$ nodes, such that this collection of paths
contains $\Omega(\ell\sqrt{k})$ edges.

For the sake of exposition, we use directed edges to construct these paths;
they can be replaced with undirected edges. Let $(u_{1},\ldots,u_{\ell})$ be
some left-to-right ordering of an arbitrary set of $\ell$ nodes, and let
$v^{+}$ be some additional node that is ordered to the left of $u_{1}$. All of
the edges in our constructed paths will go from left to right. Let the _hop
length_ of an edge $(u_{i},u_{i^{\prime}})$, where $i^{\prime}>i$, refer to
the value $i^{\prime}-i$.

We build $m=\lfloor k/4\rfloor$ simple paths on these nodes as follows; we
denote by $P$ the resulting graph of simple paths. Let
$p\in{\left\\{{1,\ldots,m}\right\\}}$ enumerate these paths. For all paths
$p$, the first edge is from $v^{+}$ to some node $u_{s_{p}}$, where we define
$s_{p}=2p-1$. We now describe the remaining edges in each path. For each odd
integer $h\in{\left\\{{1,3,5,7,\ldots}\right\\}}$, construct $(h+1)/2$ paths,
where we start with path $p=1$, then path $p=2$, and so on, up to and
including path $p=m$. For a path $p$ being made with value $h$, the first edge
is from $v^{+}$ to $u_{2p-1}$; and the remaining edges are edges of hop length
$h$, except for the final edge which goes to a special node $v_{p}$. That is,
where $s_{p}=2p-1$, path $p$ with hop length $h$ is the path $v^{+}\to
u_{s_{p}}\to u_{s_{p}+h}\to u_{s_{p}+2h}\to\cdots\to
u_{s_{p}+h\cdot\lfloor(\ell-s_{p})/h\rfloor}\to v_{p}$.

We now color the edges of $P$ in the following way. On each path, make the
edges alternate between red and blue edges: color all edges leaving $v^{+}$
with blue, color the next edge on each path red, color the following edge
blue, and so on. Because hops and start indices are odd, we maintain the
following invariants:

  1. 1.

all blue edges $(u_{i},u_{i^{\prime}})$ have even $i$ and odd $i^{\prime}$,
and

  2. 2.

all red edges $(u_{i},u_{i^{\prime}})$ have odd $i$ and even $i^{\prime}$.

These invariants mean that, for a given node $u_{i}$, all of its in-edges have
the same color, and all of its out-edges have the same color (which is the
opposite of the in-edges’ color). We also note that, for all nodes $u_{i}$,
the number of in-edges to $u_{i}$ is equal to the number of out-edges from
$u_{i}$. Additionally, all nodes $v_{p}$ have one in-edge and zero out-edges.

We now show that $G$ and $G^{\prime}$ can be constructed such that all edges
in $P$ will differ between projections of $G$ and $G^{\prime}$. More
specifically, we describe a construction where all blue edges and no red edges
will be in $G^{\prime}$; and all red edges and no blue edges will be in $G$.
Below, we describe how to construct $G^{\prime}$; the graph $G$ is constructed
identically, except $v^{+}$ and all edges from $v^{+}$ are removed from the
stream.

We construct $G^{\prime}$ by taking $P$ and adding some additional nodes and
edges, and imposing a consistent ordering on these edges. We first describe
the additional nodes and edges to add. Let $\deg_{u}(P)$ denote the degree of
$u$ in $P$. Add a set of $D-\deg_{v^{+}}(P)$ isolated nodes, and add an edge
between $v^{+}$ and each of these nodes. For all $i\in[\ell]$, add a set of
$D-\deg_{u_{i}}(P)/2$ isolated nodes, and add an edge between $u_{i}$ and each
node in this set. Let all of these edges appear before all other edges in the
consistent ordering.

We now describe how to order the remaining edges. For all $i\in[\ell]$, let
all in-edges to $u_{i}$ appear in the consistent ordering appear before all
in-edges to $u_{i^{\prime}}$ for $i^{\prime}>i$, and after all in-edges to
$u_{i^{\prime\prime}}$ for $i^{\prime\prime}<i$. Additionally, let all in-
edges to nodes of the form $v_{p}$ appear in the consistent ordering after all
of the edges already described.

We next use the following claim; we prove it at the end of this proof.

######  Claim B.2.

For all $u_{i}$ in $P$, $\Pi^{\text{\tiny DLL}}_{D}(G^{\prime})$ contains the
following edges in $P$:

  1. 1.

if $i$ is odd, then the projection contains all in-edges to $u_{i}$ in $P$,
and no out-edges from $u_{i}$ in $P$.

  2. 2.

if $i$ is even, then the projection contains no in-edges to $u_{i}$ in $P$,
and all out-edges from $u_{i}$ in $P$.

By Claim B.2, we see that all edges from $u_{i}$ with even $i$, and all edges
to $u_{i}$ with odd $i$ are in $\Pi^{\text{\tiny DLL}}_{D}(G^{\prime})$, and
that no other edges in $P$ are in $\Pi^{\text{\tiny DLL}}_{D}(G^{\prime})$.
This means that, by the two invariants provided above, all blue edges are in
$\Pi^{\text{\tiny DLL}}_{D}(G^{\prime})$ and no red edges are in
$\Pi^{\text{\tiny DLL}}_{D}(G^{\prime})$. A symmetric claim and argument can
be used to show that all red edges are in $\Pi^{\text{\tiny DLL}}_{D}(G)$ and
no blue edges are in $\Pi^{\text{\tiny DLL}}_{D}(G)$. This means that all
edges in $P$ differ between the projections.

To prove the theorem, we use the following claim about the number of edges in
$P$; we prove it at the end of this proof.

######  Claim B.3.

The graph $P$ contains $\Omega(\ell\sqrt{k})$ edges.

Recall from above that all edges in $P$ differ between the projections. Note
that, in addition to the edges in $P$, all of the additional
$D-\deg_{v^{+}}(P)$ edges from $v^{+}$ appear in the projection of
$G^{\prime}$ and do not appear in the projection of $G$. By this observation
and Claim B.3, $G$ and $G^{\prime}$ project to graph streams which differ in
at least $D-\deg_{v^{+}}(P)+\Omega(\ell\sqrt{k})$ edges.

We now show $D-\deg_{v^{+}}(P)+\Omega(\ell\sqrt{k})=D+\Omega(\ell\sqrt{k})$.
Recall that $\deg_{v^{+}}(P)=m$, where $m={\lfloor{k/4}\rfloor}$. We have two
cases: $D\geq\ell$ and $D<\ell$. For $D<\ell$, we have $k=D$, so $m=\lfloor
D/4\rfloor=o(\ell\sqrt{D})$, which means
$D-\deg_{v^{+}}(P)+\Omega(\ell\sqrt{k})=D+\Omega(\ell\sqrt{k})$. For
$D\geq\ell$, we have $m=\lfloor\ell/4\rfloor$, so $m=o(\ell^{3/2})$, which
means $D-\deg_{v^{+}}(P)+\Omega(\ell\sqrt{k})=D+\Omega(\ell\sqrt{k})$.

Therefore, the projections of the graph streams differ in at least
$D+\Omega(\ell\sqrt{k})=D+\Omega(\ell\sqrt{\min\\{D,\ell\\}})$ edges, which is
what we wanted to show and completes the proof.

We now provide proofs of the two claims used in the proof.

###### Proof of Claim B.2.

To prove the claim, we induct on $i$. We prove the base case for $i=1$ and
$i=2$. For the base case, we see that the in-edge to $u_{1}$, namely
$(v^{+},u_{1})$, is in the projection. Additionally, we see that the out-edge
from $u_{1}$, namely $(u_{1},u_{2})$, is not in the projection since $u_{1}$
already has degree $D$ prior to considering $(u_{1},u_{2})$ for inclusion in
the projection. For $u_{2}$, we see that the in-edge to $u_{2}$, namely
$(u_{1},u_{2})$, is not in the projection. Additionally, we see that the out-
edge from $u_{2}$, namely $(u_{2},u_{3})$, is in the projection since $u_{2}$
has degree $D-1$ prior to considering $(u_{2},u_{3})$ for inclusion in the
projection and $u_{3}$ has at most $D-1$ edges that are considered for
addition prior to $(u_{2},u_{3})$.

Assume the claim is true for all $i<j$. We now show the claim is true for $j$.
One useful fact from the construction of $G^{\prime}$ is that, for all
$u_{j}$, the number of in-edges to $u_{j}$ in $P$ is equal to the number of
out-edges from $u_{j}$ in $P$, and there are $D-\deg_{u_{j}}(P)/2$ additional
edges from $u_{j}$ in $G^{\prime}$.

We first consider the case where $j$ is odd. The only in-edges to $u_{j}$ are
from $v^{+}$ and from nodes $u_{i}$ where $i<j$ and $i$ is even. By
assumption, all out-edges from nodes of the form $u_{i}$ for $i<j$ where $i$
is even are in the projection. Additionally, $v^{+}$ has degree at most $D$ by
construction, so all of its edges can be in the projection; since there are
$D-\deg_{u_{j}}(P)/2$ edges from $u_{j}$ to isolated nodes, and there are
$\deg_{u_{j}}(P)/2-1$ in-edges to $u_{j}$ that are already included in the
projection, the edge from $v^{+}$ can also be included in the projection
without exceeding the degree bound. However, once these edges are included in
the projection, adding any more edges would cause the degree of $u_{j}$ to $D$
in the projection, so none of the remaining out-edges are included in the
projection.

We next consider the case where $j$ is even. The only in-edges to $u_{j}$ are
from nodes $u_{i}$ where $i<j$ and $i$ is odd. By assumption, all out-edges
from nodes of the form $u_{i}$ for $i<j$ where $i$ is odd are _not_ in the
projection. Therefore, none of the in-edges to $u_{j}$ are in the projection.
We next show that all of the out-edges from $u_{j}$ are in the projection.
First, note that the $D-\deg_{u_{j}}(P)/2$ edges from $u_{j}$ to isolated
nodes are all in the projection. Next, note that there are $\deg_{u_{j}}(P)/2$
remaining out-edges from $u_{j}$, so they can all be included in the
projection without exceeding the degree bound. We now consider the nodes to
which they are in-edges. There are two cases for these edges. If the edge is
an in-edge to some node of the form $v_{p}$, including this edge will not
cause $v_{p}$ to exceed its degree bound, so it will be included in the
projection. Otherwise, it is an in-edge to a node of the form $u_{i^{\prime}}$
where $i^{\prime}>i$. At most $D-\deg_{u_{i^{\prime}}}(P)/2$ edges are edges
to the isolated nodes (all of these edges appear in the consistent ordering
prior to the edge we are considering). At most $\deg_{u_{i^{\prime}}}(P)/2-1$
other edges (i.e., the other in-edges to $u_{i^{\prime}}$) appear in the
consistent ordering prior to this edge. Therefore, including this edge will
not cause $u_{i^{\prime}}$ to exceed its degree bound, so it will be included
in the projection. ∎

Proof of Claim B.3. We now show that there are $\Omega(\ell\sqrt{k})$ edges in
$P$. To do this, we show the set of paths can be divided into
$\Omega(\sqrt{m})$ disjoint sets of $\Omega(\ell)$ edges. We first show that,
for all values of $h$ where we make $(h+1)/2$ paths, there are at least
$\ell/4$ edges in the set of paths with length $h$. There are $m=\lfloor
k/4\rfloor$ paths, so for all $p$ we have $s_{p}=2p-1\leq\ell/2$. This means a
path $p$ with hop length $h$ contains at least $\ell/(2h)$ edges, since there
are at least $\ell/(2h)-2$ edges between nodes of the form $u_{i},u_{j}$ for
$i,j\geq s_{p}$, and there is one edge $v^{+}\to u_{s_{p}}$ and one edge
$u_{s_{p}+h\cdot\lfloor(\ell-s_{p})/h\rfloor}\to v_{p}$. Since there are
$(h+1)/2$ paths with hop length $h$, there are at least $\ell/4$ edges in the
set of paths with length $h$. We next show, roughly, that we create $(h+1)/2$
paths for all odd natural numbers $h\leq\sqrt{m}$. In other words, we
determine the biggest value of $h$ that is used in the procedure for making
$m={\lfloor{k/4}\rfloor}$ paths. Since there are at most $m$ paths, we solve
for $x$ in

$\sum_{h\in{\left\\{{1,3,5,\ldots}\right\\}}}\frac{h+1}{2}=\sum_{i\in[x]}i=m$

and, using the identity $\sum_{i\in[n]}i=n(n+1)/2$, find $x\approx\sqrt{2m}$.
Therefore, the largest value of $h$ is (roughly) $\sqrt{8m}$. Since there are
$h=\Omega(\sqrt{m})$ disjoint sets of $\Omega(\ell)$ edges, we see that there
are $\Omega(\ell\sqrt{m})=\Omega(\ell\sqrt{k})$ edges in the graph. (In this
case, there are roughly $\ell/4\cdot\sqrt{2k}$ edges in the described
graph.)∎∎