# Node and Edge Differential Privacy for Graph Laplacian Spectra: Mechanisms
and Scaling Laws

Calvin Hawkins, Bo Chen, Kasra Yazdani, Matthew Hale∗ ∗Department of
Mechanical and Aerospace Engineering at the University of Florida,
Gainesville, FL USA. Emails:
<EMAIL_ADDRESS>This work was
supported in part by NSF under CAREER Grant #1943275, by AFOSR under Grant
#FA9550-19-1-0169, and by ONR under Grant #N00014-21-1-2502.

(November 2022)

###### Abstract

This paper develops a framework for privatizing the spectrum of the Laplacian
of an undirected graph using differential privacy. We consider two privacy
formulations. The first obfuscates the presence of edges in the graph and the
second obfuscates the presence of nodes. We compare these two privacy
formulations and show that the privacy formulation that considers edges is
better suited to most engineering applications. We use the bounded Laplace
mechanism to provide $(\epsilon,\delta)$-differential privacy to the
eigenvalues of a graph Laplacian, and we pay special attention to the
algebraic connectivity, which is the Laplacian’s the second smallest
eigenvalue. Analytical bounds are presented on the accuracy of the mechanisms
and on certain graph properties computed with private spectra. A suite of
numerical examples confirms the accuracy of private spectra in practice.

##  I Introduction

Graphs are used to model a wide range of interconnected systems, including
multi-agent control systems [1], social networks [2], and others [3]. Various
properties of these graphs have been used to analyze controllers and dynamical
processes over them, such as reaching a consensus [4], the spread of a virus
[5], robustness to connection failures [6], and others. Graphs in these
applications may contain sensitive information, e.g., one’s close friendships
in the case of a social network, and it is essential that these analyses do
not inadvertently leak any such information.

Unfortunately, it is well-established that even graph-level analyses may
inadvertently reveal sensitive information about individuals in them, such as
the absence or presence of individual nodes in a graph [7] and the absence or
presence of specific edges between them [8]. Similar privacy threats have
received attention in the data science community, where graphs represent
datasets and the goal is to enable data analysis while safeguarding the data
of individuals in those datasets.

Differential privacy is one well-studied tool for doing so. Differential
privacy is a statistical notion of privacy that has several desirable
properties: (i) it is robust to side information, in that learning additional
information about data-producing entities does not weaken privacy by much [9],
and (ii) it is immune to post-processing, in that arbitrary post-hoc
computations on private data do not weaken privacy [10]. There exist numerous
differential privacy implementations for graph properties, including counts of
subgraphs [8], degree distributions [11], and other frequent patterns in
graphs [12]. These privacy mechanisms generally follow the pattern of
computing the quantity of interest, adding carefully calibrated noise to it,
and releasing its noisy form. Although simple, this approach strongly protects
data with a suite of guarantees provided by differential privacy [10].

The need for privacy for the aforementioned graph properties comes from the
inferences that one can draw about a graph from these quantities, as detailed
in [13, 14, 15]. Decades of research in algebraic graph theory have quantified
connections between the Laplacian spectrum and a myriad of other graph
properties; see [16] for a summary. Accordingly, the Laplacian spectrum,
especially the algebraic connectivity $\lambda_{2},$ implicates the same
ability to draw inferences as other graph properties and hence gives rise to
the same types of privacy concerns.

We therefore protect the values the graph Laplacian spectrum using two notions
of privacy: edge and node differential privacy [17]. Edge privacy obfuscates
the absence and/or presence of a pre-specified number of edges, while node
privacy obfuscates the absence or presence of a single node. In this paper we
show that the differences in guarantees of these two notions of privacy result
in drastic differences in the accuracy of the private values of the Laplacian
spectrum. Specifically, in Section IV we show that the variance of noise
required to obfuscate the presence of one node in a graph of size $n$ scales
with $n^{2}$, which rapidly grows large. For this reason, Sections V and VI
focus on edge privacy and obfuscating the connections in a network. We note
that while differential privacy has been applied to protect various quantities
in multi-agent systems [18, 19, 20, 21], privacy for properties of a multi-
agent network itself has received less attention, and that is what we focus
on.

In this paper we pay special attention to the algebraic connectivity. A
graph’s algebraic connectivity (also called its Fiedler value [22]) is equal
to the second-smallest eigenvalue of its Laplacian. This value plays a central
role in the study of multi-agent systems because it sets the convergence rates
of consensus algorithms [23], which appear directly or in modified form in
formation control [24], connectivity control [25], and many distributed
optimization algorithms [26].

Our implementation uses the recent bounded Laplace mechanism [27], which
ensures that private scalars lie in a specified interval. The algebraic
connectivity of a graph is bounded below by zero and above by the number of
nodes in a graph, and we confine private outputs to this interval by applying
the mechanism in [27] to the privatization of Laplacian spectra.

_Contributions:_ We provide closed-form values for the sensitivity and other
constants needed to define edge and node differential privacy mechanisms for
the Laplacian spectrum, and this is the first contribution of this paper. The
second contribution is showing the detrimental scaling of node privacy and the
benefits of edge privacy. Our third contribution is the use of the private
values of algebraic connectivity to analytically bound other graph properties,
namely the diameter of graphs and the mean distance between their nodes. Our
fourth contribution is providing guidelines on using these mechanisms by
providing a series of examples to demonstrate how to use the mechanisms and
the accuracy of information they provide.

We note that [28] has developed a different approach to privacy for the
eigendecomposition of a graph’s adjacency matrix. Given our motivation by
multi-agent systems, we focus on a graph’s Laplacian, which commonly appears
in multi-agent controllers, and we derive simpler forms for the distribution
of noise required, as well as a privacy mechanism that does not require any
post-processing.

A preliminary version of this paper appeared in [29]. This paper extends the
edge privacy mechanism for $\lambda_{2}$ to the rest of the Laplacian
spectrum, develops the node privacy mechanism for $\lambda_{2},$ compares the
scaling of the edge and node privacy mechanisms, and provides further
applications and uses of the private Laplacian spectrum.

The rest of the paper is organized as follows. Section II provides background
and problem statements. Section III develops the differential privacy
mechanisms for the Laplacian spectrum. Next, Section IV compares the scaling
of edge and node differential privacy and as a result we shift our attention
to edge privacy exclusively. Then, we use the output of the edge mechanism to
bound other graph properties in Section V. Section VI provides guidelines and
examples and Section VII concludes.

Notation We use $\mathbb{R}$ and $\mathbb{N}$ to denote the real and natural
numbers, respectively. We use $|S|$ to denote the cardinality of a finite set
$S$, and we use $S_{1}\Delta S_{2}=(S_{1}\backslash S_{2})\cup(S_{2}\backslash
S_{1})$ to denote the symmetric difference of two sets. For $n\in\mathbb{N}$,
we use $\mathcal{G}_{n}$ to denote the set of graphs on $n$ nodes.

##  II Preliminaries and Problem Statement

###  II-A Graph Theory Background

We consider an undirected, unweighted graph $G=(V,E)$ defined over a set of
nodes $V=\\{1,\dots,n\\}$ with edge set $E\subset V\times V$. The pair $(i,j)$
belongs to $E$ if nodes $i$ and $j$ share an edge, and $(i,j)\notin E$
otherwise. We let $d_{i}=|\\{j\in V\mid(i,j)\in E\\}|$ denote the degree of
node $i\in V$. The degree matrix $D(G)\in\mathbb{R}^{n\times n}$ is the
diagonal matrix $D(G)=\operatorname{diag}\big{(}d_{1},\ldots,d_{n}\big{)}$.
The adjacency matrix of $G$ is

$(H(G))_{ij}=\begin{cases}1&(i,j)\in E\\\ 0&\text{ otherwise }\end{cases}.$
(1)

We denote the Laplacian of graph $G$ by ${L(G)=D(G)-H(G)}$, which we simply
write as $L$ when the associated graph is clear from context.

Let the eigenvalues of $L$ be ordered according to
${\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}}$. The matrix $L$ is
symmetric and positive semidefinite, and thus $\lambda_{i}\geq 0$ for all $i$.
All graphs $G$ have $\lambda_{1}=0$, and a seminal result shows that
$\lambda_{2}>0$ if and only if $G$ is connected [30]. Thus, $\lambda_{2}$ is
often called the _algebraic connectivity_ of a graph. Throughout this paper,
we consider connected graphs with $n\geq 3$.

The value of $\lambda_{2}$ specifically encodes a great deal of information
about $G$: its value is non-decreasing in the number of edges in $G$, and
algebraic connectivity is closely related to graph diameter and various other
algebraic properties of graphs [16]. The value of $\lambda_{2}$ also
characterizes the performance of consensus algorithms. Specifically, worst-
case disagreement in a consensus protocol decays proportionally to
$e^{-\lambda_{2}t}$ [31]. Thus, we will privatize the full spectrum of $L$ and
pay special attention to $\lambda_{2}$ as we do so.

###  II-B Privacy Background

We follow the differential privacy definition in [10]. Differential privacy is
enforced by a _mechanism_ , which is a randomized map. Given “similar” inputs,
a differential privacy mechanism produces outputs that are approximately
indistinguishable from each other. Formally, a mechanism must obfuscate
differences between inputs that are _adjacent_ 111The word “adjacency” appears
in two forms in this paper: for the adjacency matrix $H$ above, and for the
adjacency relation used by differential privacy. The adjacency matrix appears
only in this section and only to define the graph Laplacian, and all
subsequent uses of “adjacent” and “adjacency” pertain to differential privacy
(not the adjacency matrix).. In this work, we analyze two different notions of
adjacency for a given graph $G$: an adjacency relation defined with respect to
the edges of $G$, $E(G)$, and an adjacency relation defined with respect to
the nodes of $G$, $V(G)$. When adjacency is defined with respect to the edge
set, we will calibrate our privacy to obfuscate the absence or presence of one
or more edges in $G$. When adjacency is defined with respect to the node set,
we will obfuscate the absence or presence of a single node. Mathematically,
this is done as follows.

######  Definition 1.A (_Edge Adjacency relation_).

Let $A\in\mathbb{N}$ be given, and fix a number of nodes $n\in\mathbb{N}$. Two
graphs $G,G^{\prime}\in\mathcal{G}_{n}$ are adjacent if they differ by $A$
edges. We express this mathematically via

$\textnormal{Adj}_{e,A}(G,G^{\prime})=\begin{cases}1&|E(G)\Delta
E(G^{\prime})|\leq A\\\ 0&\textnormal{otherwise}\end{cases}.$ $\lozenge$

######  Definition 1.B (_Node Adjacency relation_).

Fix $n\in\mathbb{N}$. Two graphs, $G,G^{\prime}\in\mathcal{G}_{n}$ are
adjacent if they differ by one node with the corresponding edges added or
deleted. We express this mathematically via

$\text{Adj}_{n}(G,G^{\prime})=\begin{cases}1&|V(G)\Delta V(G^{\prime})|\leq
1\\\ 0&\text{otherwise}\end{cases}.$ $\lozenge$

In Definition 1.A, $A$ is the number of edges whose absence or presence must
be concealed by privacy, while Definition 1.B specifies that the absence or
presence of a single node must be concealed by privacy. In Section III-B, we
show that a mechanism that obfuscates the absence or presence of only a single
node is not practical for large networks and engineering examples, and
therefore we do not consider obfuscating the presence of arbitrary numbers of
nodes.

Next, we briefly review differential privacy; see [10] for a complete
exposition. A privacy mechanism $\mathcal{M}$ for a function $f$ can be
obtained by first computing the function $f$ on a given input $x$, and then
adding noise to $f(x)$. The distribution of noise depends on the sensitivity
of the function $f$ to changes in its input, described below. It is the role
of a mechanism to approximate functions of sensitive data with private
responses, and we next state this formally. The guarantees of privacy are
defined with respect to the adjacency relation. Since we consider two notions
of adjacency, we define two types of privacy: (i) edge differential privacy
using the standard definition of differential privacy equipped with the edge
adjacency relation, $\textnormal{Adj}_{e,A},$ appearing in Defintion 1.A, and
(ii) node differential privacy using the standard definition of differential
privacy equipped with $\textnormal{Adj}_{n}$ in Definition 1.B.

######  Definition 2.A (_Edge differential privacy;[10]_).

Let $\epsilon>0$, $\delta\in[0,1)$ be given, use $\textnormal{Adj}_{e,A}$ from
Definition 1.A, and fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$.
Then a mechanism
$\mathcal{M}:\Omega\times\mathcal{G}_{n}\rightarrow\mathbb{R}$ is
$(\epsilon,\delta)$-differentially private if, for all adjacent graphs
$G,G^{\prime}\in\mathcal{G}_{n}$,

$\mathbb{P}\big{[}\mathcal{M}(G)\in
S\big{]}\leq\exp(\epsilon)\cdot\mathbb{P}\big{[}\mathcal{M}\left(G^{\prime}\right)\in
S\big{]}+\delta$ (2)

for all sets $S$ in the Borel $\sigma$-algebra over $\mathbb{R}$. $\lozenge$

######  Definition 2.B (_Node differential privacy;[10]_).

Let $\epsilon>0$, $\delta\in[0,1)$ be given, use $\textnormal{Adj}_{n}$ from
Definition 1.B, and fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$.
Then a mechanism
$\mathcal{M}:\Omega\times\mathcal{G}_{n}\rightarrow\mathbb{R}$ is
$(\epsilon,\delta)$-differentially private if, for all adjacent graphs
$G,G^{\prime}\in\mathcal{G}_{n}$,

$\mathbb{P}\big{[}\mathcal{M}(G)\in
S\big{]}\leq\exp(\epsilon)\cdot\mathbb{P}\big{[}\mathcal{M}\left(G^{\prime}\right)\in
S\big{]}+\delta$ (3)

for all sets $S$ in the Borel $\sigma$-algebra over $\mathbb{R}$. $\lozenge$

The value of $\epsilon$ controls the amount of information shared, and typical
values range from $0.1$ to $\log 3$ [10]. The value of $\delta$ can be
regarded as the probability that more information is shared than $\epsilon$
should allow, and typical values range from $0$ to $0.05$. Smaller values of
both imply stronger privacy. Given $\epsilon$ and $\delta$, a privacy
mechanism must enforce Definition 2.A or 2.B for all graphs adjacent in the
sense of Definition 1.A or 1.B, respectively.

We next define the sensitivity of $\lambda_{i}$, which will be used later to
calibrate the variance of privacy noise. With a slight abuse of notation, we
treat $\lambda_{i}$ as a function $\lambda_{i}:\mathcal{G}_{n}\to\mathbb{R},$
and we will develop differential privacy mechanisms to approximate each
$\lambda_{i}$. The sensitivity will depend on which adjacency relation is
used, and this is made explicit in the following definitions.

######  Definition 3.A (_Edge Sensitivity_).

The edge sensitivity of $\lambda_{i}$ is the greatest difference between its
values on Laplacians of graphs that are adjacent with respect to
$\textnormal{Adj}_{e,A}$ in Defintion 1.A. Formally, for a fixed $A,$ the edge
sensitivity of $\lambda_{i}$ is given as

$\Delta\lambda_{i,e}=\max_{\begin{subarray}{c}G,G^{\prime}\in\mathcal{G}_{n}\\\
\textnormal{Adj}_{e,A}(G,G^{\prime})=1\end{subarray}}\big{|}\lambda_{i}(L)-\lambda_{i}(L^{\prime})\big{|},$
(4)

where $L$ and $L^{\prime}$ are the Laplacians of $G$ and $G^{\prime}$.
$\lozenge$

######  Definition 3.B (_Node Sensitivity_).

The node sensitivity of $\lambda_{i}$ is the greatest difference between its
values on Laplacians of graphs that are adjacent with respect to
$\textnormal{Adj}_{n}$ in Defintion 1.B. Formally, the node sensitivity of
$\lambda_{i}$ is given as

$\Delta\lambda_{i,n}=\max_{\begin{subarray}{c}G,G^{\prime}\in\mathcal{G}_{n}\\\
\textnormal{Adj}_{n}(G,G^{\prime})=1\end{subarray}}\big{|}\lambda_{i}(L)-\lambda_{i}(L^{\prime})\big{|},$
(5)

where $L$ and $L^{\prime}$ are the Laplacians of $G$ and $G^{\prime}$.
$\lozenge$

Noise is added by a mechanism, which is a randomized map used to implement
differential privacy. The Laplace mechanism is widely used, and it adds noise
from a Laplace distribution to sensitive data (or functions thereof). The
standard Laplace mechanism has support on all of $\mathbb{R}.$ For graphs on
$n$ nodes, $\lambda_{i}\in[0,n]$ for all $i.$ To generate a private output,
one can add Laplace noise and then project the result onto $[0,n]$ (which is
differentially private because the projection is post-processing), though
similar approaches have been shown to produce highly inaccurate private data
[32]. Instead, we use the bounded Laplace mechanism in [27]. We state it in a
form amenable to use with $\lambda_{i}$.

######  Definition 4.

Let $b>0$ and let $D=[0,n]$. Then the bounded Laplace mechanism
$W_{\lambda_{i}}:\Omega\rightarrow D$, for each $\lambda_{i}\in D$, is given
by its probability density function $f_{W_{\lambda_{i}}}$ as

$f_{W_{\lambda_{i}}}(x)=\begin{cases}0&\text{if }x\notin D\\\
\frac{1}{C(\lambda_{i},b)}\frac{1}{2b}e^{-\frac{|x-\lambda_{i}|}{b}}&\text{if
}x\in D\end{cases},$ (6)

where $C(\lambda_{i},b)=\int_{D}\frac{1}{2b}e^{-\frac{|x-\lambda_{i}|}{b}}dx.$
$\lozenge$

###  II-C Problem Statements

We now give formal problem statements. The first two pertain to the
development of privacy mechanisms.

######  Problem 1.

Develop a mechanism to provide $(\epsilon,\delta)$-edge differential privacy
in the sense of Definition 2.A for the spectrum of the graph Laplacian $L(G)$
of a graph $G.$

######  Problem 2.

Develop a mechanism to provide $(\epsilon,\delta)$-node differential privacy
in the sense of Definition 2.B for the algebraic connectivity of a graph $G$.

We note that Problem 2 considers the algebraic connectivity specifically
because that will be used to show the poor scaling of node privacy for the
full Laplacian spectrum. Comparisons of the two mechanisms are the subject of
the next problem.

######  Problem 3.

Given a graph $G$ on $n$ nodes and two privacy mechanisms, $\mathcal{M}_{n}$
and $\mathcal{M}_{e}$, that provide $(\epsilon,\delta)$-node privacy and
$(\epsilon,\delta)$-edge privacy for the spectrum of $L(G),$ respectively,
analyze how the variances of the two mechanisms scale with respect to the size
of the network $n.$

The final two problem statements pertain to the accuracy of graph properties
when bounded using private spectra.

######  Problem 4.

Given a private algebraic connectivity, develop bounds on the expectation of
the graph diameter and mean distance between nodes in the graph.

######  Problem 5.

Given private values of the Laplacian spectrum, provide examples to
numerically quantify the accuracy of using these private values to estimate
the trace of the Laplacian, Kemeny’s constant, and Cheeger’s inequality.

##  III Privacy Mechanisms

In this section, we solve Problems 1 and 2. Specifically, we develop two
mechanisms to provide $(\epsilon,\delta)-$differential privacy to eigenvalues
of a graph Laplacian $L.$ In Section III-A, we use edge differential privacy
to privatize each of the Laplacian eigenvalues, $\lambda_{i}$ for $i\in[n].$
Then in Section III-B, we use node differential privacy to privatize
$\lambda_{2}.$ In both subsections we first bound the sensitivity appearing in
Definition II-B and then use these sensitivity bounds to develop the privacy
mechanisms.

###  III-A Edge Privacy

We now design a mechanism to implement $(\epsilon,\delta)-$edge differential
privacy. We first bound the sensitivity $\Delta\lambda_{i,e}$ appearing in
Definition 3.A.

######  Lemma 1 (Edge sensitivity bound).

Fix an adjacency parameter $A\in\mathbb{N}$. Then for the edge sensitivity
$\Delta\lambda_{i,e}$ in Definition 3.A, we have

$\Delta\lambda_{i,e}\leq 2A$ (7)

for $i\in\\{1,\dots,n\\}.$

_Proof:_ See Appendix A. $\blacksquare$

Next, we establish an algebraic relation for $b_{e}$, which lets the bounded
Laplace mechanism satisfy the theoretical guarantees of
$(\epsilon,\delta)$-edge differential privacy in Definition 2.A.

######  Theorem 1.

Let $\epsilon>0$ and $\delta\in(0,1)$ be given. Fix $n\in\mathbb{N}$ and
consider graphs in $\mathcal{G}_{n}$. Then for the bounded Laplace mechanism
$W_{\lambda_{i}}$ in Definition 4, choosing $b_{e}$ according to

$b_{e}\geq\frac{2A}{\epsilon-\log\left(\frac{2-e^{-\frac{2A}{b_{e}}}-e^{-\frac{n-2A}{b_{e}}}}{1-e^{-\frac{n}{b_{e}}}}\right)-\log(1-\delta)}$
(8)

satisfies $(\epsilon,\delta)$-edge differentially privacy with respect to
$\textnormal{Adj}_{e,A}$ as defined in Definition 2.A.

_Proof:_ By [27, Theorem 3.5], the bounded Laplace mechanism provides
$(\epsilon,\delta)-$differential privacy if

$b_{e}\geq\frac{\Delta\lambda_{i,e}}{\epsilon-\log\Delta
C(b_{e})-\log(1-\delta)},$ (9)

where, given that $\lambda_{i}\in[0,n]$, $\Delta C(b_{e})$ is defined as

$\Delta C(b_{e}):=\frac{C(\Delta\lambda_{i,e},b_{e})}{C(0,b_{e})},$ (10)

where $C$ is from Definition 4. Next, we find

$\displaystyle C(\lambda_{i},b_{e})$
$\displaystyle=\int_{0}^{n}\frac{1}{2b_{e}}e^{-\frac{|x-\lambda_{i}|}{b_{e}}}dx$
(11)
$\displaystyle=\frac{1}{2b_{e}}\int_{0}^{\lambda_{i}}e^{\frac{x-\lambda_{i}}{b_{e}}}dx+\frac{1}{2b_{e}}\int_{\lambda_{i}}^{n}e^{-\frac{x-\lambda_{i}}{b_{e}}}dx$
(12)
$\displaystyle=1-\frac{1}{2}\left(e^{-\frac{\lambda_{i}}{b_{e}}}+e^{-\frac{n-\lambda_{i}}{b_{e}}}\right).$
(13)

Using (13) to compute $C(\Delta\lambda_{i,e},b_{e})$ and $C(0,b_{e})$ in (10)
gives

$\Delta
C(b_{e})=\frac{1-\frac{1}{2}\left(e^{-\frac{\Delta\lambda_{i,e}}{b_{e}}}+e^{-\frac{n-\Delta\lambda_{i,e}}{b_{e}}}\right)}{1-\frac{1}{2}\left(1+e^{-\frac{n}{b_{e}}}\right)}.$
(14)

Using the sensitivity bound in Lemma 1, we put $\Delta\lambda_{i,e}=2A$, which
completes the proof. $\blacksquare$

Theorem 1 solves Problem 1, and we now have an $(\epsilon,\delta)-$edge
differential privacy mechanism for the spectrum of a graph Laplacian $L$. We
now shift our attention to node privacy and the algebraic connectivity,
$\lambda_{2}.$

###  III-B Node Privacy

Here we develop an $(\epsilon,\delta)-$node differential privacy mechanism for
$\lambda_{2}.$ We will use the same process as the last subsection: we first
bound $\Delta\lambda_{2,n}$ from Definition 3.B for a graph
$G\in\mathcal{G}_{n}$, then use this sensitivity to find an algebraic relation
for the bounded Laplace mechanism to satisfy Definition 2.B. In Lemma 1, we
were able to derive a common bound on the sensitivity of each eigenvalue of
$L$ when edge sensitivity is used. There is no common bound when node
sensitivity is used. In Section IV, we show that the node privacy scales
poorly with the size of the network and will not be usable in most engineering
problems. Thus, in this section we focus on $\lambda_{2}$ rather than the
entire spectrum, as this is sufficient to illustrate the poor scaling of node
privacy in this context.

Definition 1.B considers adjacent graphs as graphs that have an additional or
absent node from $G.$ Thus, for a $G^{\prime}$ satisfying
$\textnormal{Adj}_{n}(G,G^{\prime})=1,$ it is possible that
${G^{\prime}\in\mathcal{G}^{n-1}}$ or ${G^{\prime}\in\mathcal{G}^{n+1}}.$
Because of this, we require $n\geq 3$ and the two cases will be handled
separately in our analysis. We have the following result.

######  Lemma 2.

Fix $n\in\mathbb{N}$ and consider graphs in $\mathcal{G}_{n}$. Then the node
sensitivity of $\lambda_{2}$ in Definition 3.B is bounded as

$\Delta\lambda_{2,n}\leq n-1.$

_Proof:_ See Appendix B. $\blacksquare$

With this sensitivity bound, we now establish an algebraic relation for
$b_{n}$, which lets the bounded Laplace mechanism satisfy the theoretical
guarantees of $(\epsilon,\delta)$-node differential privacy in Definition 2.B.

######  Theorem 2.

Let $\epsilon>0$ and $\delta\in(0,1)$ be given. Fix $n\in\mathbb{N}$ and
consider graphs in $\mathcal{G}_{n}$. Then for the bounded Laplace mechanism
$W_{\lambda_{2}}$ in Definition 4, choosing $b_{n}$ according to

$b_{n}\geq\frac{n-1}{\epsilon-\log\left(\frac{2-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}}{1-e^{-\frac{n}{b_{n}}}}\right)-\log(1-\delta)}$
(15)

satisfies $(\epsilon,\delta)$-node differential privacy with respect to
$\text{Adj}_{n}$ from Definition 1.B.

_Proof:_ By [27, Theorem 3.5], the bounded Laplace mechanism satisfies
differential privacy if

$b_{n}\geq\frac{\Delta\lambda_{2,n}}{\epsilon-\log\Delta
C(b_{n})-\log(1-\delta)},$ (16)

where, given that $\lambda_{2}\in[0,n]$, $\Delta C(b_{n})$ is defined as

$\Delta C(b_{n}):=\frac{C(\Delta\lambda_{2,n},b_{n})}{C(0,b_{n})},$ (17)

where $C$ is from Definition 4. Next, we find

$C(\lambda_{2},b_{n})=1-\frac{1}{2}\left(e^{-\frac{\lambda_{2}}{b_{n}}}+e^{-\frac{n-\lambda_{2}}{b_{n}}}\right).$
(18)

Using (18) to compute $C(\Delta\lambda_{2,n},b_{n})$ and $C(0,b_{n})$ in (17)
gives

$\Delta
C(b_{n})=\frac{1-\frac{1}{2}\left(e^{-\frac{\Delta\lambda_{2,n}}{b_{n}}}+e^{-\frac{n-\Delta\lambda_{2,n}}{b_{n}}}\right)}{1-\frac{1}{2}\left(1+e^{-\frac{n}{b_{n}}}\right)}.$
(19)

Using the sensitivity bound in Lemma 2, we set $\Delta\lambda_{2,n}=n-1$,
which completes the proof. $\blacksquare$

Theorem 2 solves Problem 2 and gives an $(\epsilon,\delta)-$node differential
privacy mechanism for the algebraic connectivity, $\lambda_{2}$, of the graph
Laplacian $L$. The algebraic relationships given in Theorems 1 and 2 are
defined implicitly since $b$ appears on both sides of the expression, and they
do not yield an analytical expression for the minimum $b$ required for
privacy. In [27], the authors provide an algorithm to solve for $b$ using the
bisection method, and we use this in the remainder of this paper. However, the
lack of an analytical expression for the required $b$ prevents us from
immediately comparing the amounts of noise required by the two notions of
privacy. The next section derives necessary conditions for the variances of
noise required for edge and node privacy, which will allow us to compare how
the two notions of privacy scale with the size of the network $n$.

##  IV Scaling Laws

In this section we will compare the notions of edge and node differential
privacy to solve Problem 3. More specifically, we will analyze how the
required variance of each privacy notion scales with the size of the network
$n.$ Here, we focus on the algebraic connectivity $\lambda_{2}$ to draw
accurate comparisons between edge and node privacy. However, the edge privacy
results can immediately be applied to the rest of the Laplacian’s spectrum and
the scaling trends found here persist for each value of the Laplacian
spectrum.

Figure 1: Fix $\epsilon=0.4,\delta=0.05,A=2,$ and $\lambda_{2}=2.5$. We set
$b_{n}$ equal to its lower bound in Corollary 1 and $b_{e}$ equal to its lower
bound in Corollary 2. The variances of the Laplace mechanisms are proportional
to $b_{e}^{2}$ and $b_{n}^{2}$, and we plot $b_{e}^{2}$ and $b_{n}^{2}$ here
for $n=3$ to $n=100$ nodes. This figure shows that the variance of noise
required for edge privacy has no dependence on $n$, while it is necessary for
the variance of noise for node privacy to grow quadratically in $n$.

To compare the two mechanisms, we fix a graph $G\in\mathcal{G}_{n}$ and
privacy parameters $\epsilon$ and $\delta.$ Then we define an edge and node
privacy mechanism to provide $(\epsilon,\delta)-$differential privacy with
parameters $b_{e}$ and $b_{n},$ respectively. Then we will analyze and compare
the required values of $b_{e}$ and $b_{n}$ given this $\epsilon$ and $\delta.$

###  IV-A Comparison of Mechanisms

Recall that the requirements for the bounded Laplace mechanism to achieve
$(\epsilon,\delta)-$differential privacy appearing in Theorems 1 and 2 are
defined implicitly in $b_{e}$ and $b_{n}$ and the minimal values must be found
numerically. To compare the two notions of privacy we find weaker, necessary
conditions for $(\epsilon,\delta)-$edge and node differential privacy, which
give an analytical expression for the growth of $b$. The following results
will show that the required parameter for the bounded Laplace mechanism to
achieve $(\epsilon,\delta)-$differential privacy is strictly larger than the
parameter required for the standard, unbounded Laplace mechanism from [10] to
achieve the same level of privacy. This recovers a general-purpose result of
the same kind presented in [27, Theorem 3.5]. The next two corollaries give
these necessary conditions for edge and node privacy, respectively.

######  Corollary 1.

Fix a graph $G\in\mathcal{G}^{n},$ $\epsilon>0,$ and $\delta\in(0,1).$ Let
$W^{n}_{\lambda_{2}}$ be a bounded Laplace mechanism with parameter $b_{n}.$
Then

$b_{n}>\frac{n-1}{\epsilon-\log(1-\delta)}$ (20)

is a necessary condition for $W^{n}_{\lambda_{2}}$ to provide
$(\epsilon,\delta)-$node differential privacy.

_Proof:_ See Appendix C. $\blacksquare$

######  Corollary 2.

Fix a graph $G\in\mathcal{G}^{n},$ $\epsilon>0,$ and $\delta\in(0,1).$ Let
$W^{e}_{\lambda_{2}}$ be a bounded Laplace mechanism with parameter $b_{e}.$
Then

$b_{e}>\frac{2A}{\epsilon-\log(1-\delta)}$ (21)

is a necessary condition for $W^{e}_{\lambda_{2}}$ to provide
$(\epsilon,\delta)-$edge differential privacy.

_Proof:_ See Appendix D. $\blacksquare$

######  Remark 1.

In Corollary 1, the necessary condition on $b_{n}$ for
$(\epsilon,\delta)$-node differential privacy scales linearly with $n$. A
standard Laplace distribution with parameter $b$ has variance $2{b}^{2}.$ This
means that as the size of the network $n$ grows, the variance required for
$(\epsilon,\delta)-$node differential privacy grows quadratically in $n.$
Simultaneously, in Corollary 2, $b_{e}$ has no dependence on the size of the
network. Thus, $b_{e}$ and the variance of privacy noise needed for edge
differential privacy remain constant as a network grows.

Corollaries 1 and 2 allow us to make further comparisons between edge and node
privacy. For example, fix an $\epsilon,\delta,$ and $n.$ For the edge privacy
mechanism $W_{\lambda_{2}}^{e}$ to have larger variance than the node privacy
mechanism $W_{\lambda_{2}}^{n}$ according to the necessary conditions, we
would need $A\geq\frac{n-1}{2}.$ This implies that the noise required to
obfuscate the presence of a single node is proportional to the noise required
to obfuscate the presence of $\frac{n-1}{2}$ edges. In applications where many
connections need to obfuscated, specifically on the order of half the
connections in the network, node privacy can provide similar accuracy to edge
privacy. However, in applications where less than half the connections in the
network need to be obfuscated, edge privacy can provide greater accuracy than
node privacy.

The aforementioned scaling laws are further illustrated by numerical results
shown in Figure 1. These results show that the minimal $b_{n}$ required for
node privacy grows quickly, while $b_{e}$ remains constant.

One of the appealing features of differential privacy is that it provides a
means to share private information that can still can still be useful.
However, in most applications, variance on the order of $n^{2}$ will render
the private information useless. Thus, we focus on edge privacy for the rest
of the paper.

###  IV-B Accuracy of Edge Privacy

The edge privacy mechanism has the following accuracy.

######  Theorem 3.

For a fixed $G\in\mathcal{G}_{n}$, $\epsilon>0$, $\delta\in(0,1)$, and
$A\in\mathbb{N}$, the accuracy of a private eigenvalue $\tilde{\lambda}_{i}$
generated using the bounded Laplace mechanism with parameter $b_{e}$ is given
by

$E\left[\tilde{\lambda}_{i}-\lambda_{i}\right]=\frac{1}{2C(\lambda_{i},b_{e})}\left(2\lambda_{i}+b_{e}e^{-\frac{\lambda_{i}}{b_{e}}}-(n+b_{e})e^{-\frac{n-\lambda_{i}}{b_{e}}}\right)-\lambda_{i}.$
(22)

_Proof:_ See Appendix E $\blacksquare$

Theorem 3 provides an analytical expression for the accuracy of the edge
privacy mechanism. Since differential privacy is immune to post-processing, we
can use private spectra to estimate other graph properties without harming
privacy guarantees. The rest of the paper focuses on estimating othering graph
properties using the edge privacy mechanism. Specifically, in Section V we
develop statistical bounds on other graph properties given a private
$\lambda_{2},$ and in Section VI we provide a series of examples that
demonstrate the accuracy of the edge privacy mechanism and illustrate how
these private values of the Laplacian spectrum can be used to estimate other
graph properties.

##  V Bounding Other Graph Properties

In this section we solve Problem 4. There exist numerous inequalities relating
$\lambda_{2}$ to other quantitative graph properties [16, 31], and one can
therefore expect that the private $\lambda_{2}$ will be used to estimate other
quantitative characteristics of graphs. To illustrate the utility of doing so,
in this section we bound the graph diameter $d$ and mean distance $\rho$ in
terms of the private value $\tilde{\lambda}_{2}$.

###  V-A Analytical bounds

Both $d$ and $\rho$ measure graph size and provide insight into how easily
information can be transferred across a network [33]. We estimate each one in
terms of the private $\lambda_{2}$ and bound the error induced in these
estimates by privacy. These bounds represent the types of calculations one can
do with $\tilde{\lambda}_{2}$, and similar bounds can be easily derived, e.g.,
on minimal/maximal degree, edge connectivity, etc., because their bounds are
proportional to $\lambda_{2}$ [22].

We first recall bounds from the literature.

######  Lemma 3 (Diameter and Mean Distance Bounds[34]).

For an undirected, unweighted graph $G$ on $n$ nodes, define

$\displaystyle\overline{d}(\lambda_{2},\alpha)=\left(2\sqrt{\frac{\lambda_{n}}{\lambda_{2}}}\sqrt{\frac{\alpha^{2}-1}{4\alpha}}+2\right)\left(\log_{\alpha}\frac{n}{2}\right)$
$\displaystyle\overline{\rho}(\lambda_{2},\alpha)=\left(\\!\sqrt{\frac{\lambda_{n}}{\lambda_{2}}}\sqrt{\frac{\alpha^{2}-1}{4\alpha}}\\!+\\!1\\!\right)\left(\\!\frac{n}{n-1}\\!\right)\left(\frac{1}{2}\\!+\\!\log_{\alpha}\frac{n}{2}\right).$

Then for any fixed $\lambda_{2}>0$ and any $\alpha>1$, the diameter $d$ and
mean distance $\rho$ of the graph $G$ are bounded via

$\displaystyle\underline{d}(\lambda_{2})=\frac{4}{n\lambda_{2}}\leq
d\leq\overline{d}(\lambda_{2},\alpha)$ (23)
$\displaystyle\underline{\rho}(\lambda_{2})=\frac{2}{(n-1)\lambda_{2}}+\frac{n-2}{2(n-1)}\leq\rho\leq\overline{\rho}(\lambda_{2},\alpha).$
(24)

The least upper bounds can be derived by finding values of $\alpha_{d}$ and
$\alpha_{\rho}$ which minimize $\overline{d}(\lambda_{2},\alpha)$ and
$\overline{\rho}(\lambda_{2},\alpha)$, respectively. $\blacksquare$

A list of $\alpha_{d}$ and $\alpha_{\rho}$ values can be found in Table 1 in
[34]. To quantify the impacts of using the private $\lambda_{2}$ in these
bounds, we next bound the expectations of the private forms of $d$ and $\rho$.
These bounds use the upper incomplete gamma function $\Gamma(\cdot,\cdot)$ and
the imaginary error function $\textrm{erfi}(\cdot)$, defined as

$\Gamma(s,x)=\int_{x}^{\infty}t^{s-1}e^{-t}dt\,\,\,\textnormal{ and
}\,\,\,\textrm{erfi}(x)=\frac{2}{\sqrt{\pi}}\int_{0}^{x}e^{t^{2}}dt.$ (25)

Using the private $\lambda_{2}$, expectation bounds are as follows.

######  Theorem 4 (_Expectation bounds for $d$ and $\rho$; Solution to Problem
4_).

For any $\lambda_{2}>0$, denote its private value by $\tilde{\lambda}_{2}$.
Let $\tilde{d}$ and $\tilde{\rho}$ denote the estimates of the diameter and
mean distance, respectively, when computed with $\tilde{\lambda}_{2}$. Then
the expectations $E[\tilde{d}]$ and $E[\tilde{\rho}]$, obey

$\displaystyle\frac{4}{nE[\tilde{\lambda}_{2}]}\leq E[\tilde{d}]\leq
E[\overline{d}(\tilde{\lambda}_{2},\alpha_{d})]\qquad\textnormal{ and }$ (26)
$\displaystyle\frac{2}{(n-1)E[\tilde{\lambda}_{2}]}+\frac{n-2}{2(n-1)}\leq
E[\tilde{\rho}]\leq E[\overline{\rho}(\tilde{\lambda}_{2},\alpha_{\rho})],$
(27)

where

$\displaystyle
E[\overline{d}(\tilde{\lambda}_{2},\alpha_{d})]\\!=\\!\left[2\sqrt{\frac{\lambda_{n}(\alpha_{d}^{2}-1)}{4\alpha_{d}}}E\\!\left[\sqrt{\frac{1}{\tilde{\lambda}_{2}}}\right]\\!+\\!2\right]\\!\\!\left[\log_{\alpha_{d}}\frac{n}{2}\right]$
$\displaystyle\begin{multlined}E[\overline{\rho}(\tilde{\lambda}_{2},\alpha_{\rho})]=\left[\sqrt{\frac{\lambda_{n}(\alpha_{\rho}^{2}-1)}{4\alpha_{\rho}}}E\left[\frac{1}{\sqrt{\tilde{\lambda}_{2}}}\right]+1\right]\\\
\cdot\left[\frac{n}{n-1}\right]\cdot\left[\frac{1}{2}+\log_{\alpha_{\rho}}\frac{n}{2}\right]\end{multlined}E[\overline{\rho}(\tilde{\lambda}_{2},\alpha_{\rho})]=\left[\sqrt{\frac{\lambda_{n}(\alpha_{\rho}^{2}-1)}{4\alpha_{\rho}}}E\left[\frac{1}{\sqrt{\tilde{\lambda}_{2}}}\right]+1\right]\\\
\cdot\left[\frac{n}{n-1}\right]\cdot\left[\frac{1}{2}+\log_{\alpha_{\rho}}\frac{n}{2}\right].$

We can compute the expectation terms with $\tilde{\lambda}_{2}$ via

$\displaystyle\begin{multlined}E\left[\frac{1}{\sqrt{\tilde{\lambda}_{2}}}\right]=\frac{1}{C(\lambda_{2},b_{e})}\frac{1}{2b_{e}}\left(\sqrt{\pi}\sqrt{b_{e}}e^{-\frac{\lambda_{2}}{b_{e}}}\left(\textrm{erfi}\left(\sqrt{\frac{\lambda_{2}}{b_{e}}}\right)\right)\right.\\\
\left.+\sqrt{b_{e}}e^{\frac{\lambda_{2}}{b_{e}}}\left(\Gamma\left(\frac{1}{2},\frac{n}{b_{e}}\right)-\Gamma\left(\frac{1}{2},\frac{\lambda_{2}}{b_{e}}\right)\right)\right)\end{multlined}E\left[\frac{1}{\sqrt{\tilde{\lambda}_{2}}}\right]=\frac{1}{C(\lambda_{2},b_{e})}\frac{1}{2b_{e}}\left(\sqrt{\pi}\sqrt{b_{e}}e^{-\frac{\lambda_{2}}{b_{e}}}\left(\textrm{erfi}\left(\sqrt{\frac{\lambda_{2}}{b_{e}}}\right)\right)\right.\\\
\left.+\sqrt{b_{e}}e^{\frac{\lambda_{2}}{b_{e}}}\left(\Gamma\left(\frac{1}{2},\frac{n}{b_{e}}\right)-\Gamma\left(\frac{1}{2},\frac{\lambda_{2}}{b_{e}}\right)\right)\right)$
$\displaystyle\begin{multlined}E[\tilde{\lambda}_{2}]=\frac{1}{2C(\lambda_{2},b_{e})}\left(2\lambda_{2}+b_{e}e^{-\frac{\lambda_{2}}{b_{e}}}-b_{e}e^{-\frac{n-\lambda_{2}}{b_{e}}}-ne^{-\frac{n-\lambda_{2}}{b_{e}}}\right),\end{multlined}E[\tilde{\lambda}_{2}]=\frac{1}{2C(\lambda_{2},b_{e})}\left(2\lambda_{2}+b_{e}e^{-\frac{\lambda_{2}}{b_{e}}}-b_{e}e^{-\frac{n-\lambda_{2}}{b_{e}}}-ne^{-\frac{n-\lambda_{2}}{b_{e}}}\right),$

where $C$ is from Definition 4.

_Proof:_ See Appendix F. $\blacksquare$

######  Remark 2.

A larger $\epsilon$ gives weaker privacy, and it results in a smaller value of
$b_{e}$ and a distribution of privacy noise that is more tightly concentrated
about its mean. Thus, a larger $\epsilon$ implies that the expected value
$E[\tilde{\lambda}_{2}]$ is closer to the exact, non-private $\lambda_{2}$,
which leads to smaller disagreements in the bounds on the true and expected
values of $d$ and $\rho$.

###  V-B Simulation results

Figure 2: The top plot shows the distance between the exact and expected upper
bounds for $d$. The bottom plot shows the distance between the corresponding
lower bounds. Figure 3: The top plot shows the distance between the exact and
expected upper bounds for $\rho$. The bottom plot shows the distance between
the corresponding lower bounds.

We next present simulation results for using the private value of
$\lambda_{2}$ to estimate $d$ and $\rho$. We consider networks of $n=30$
agents with different edge sets and hence different values of $\lambda_{2}$.
We let $\lambda_{n}=n$ and therefore the upper bounds on $d$ and $\rho$ in
Theorem 4 can reach their worst-case values. We apply the bounded Laplace
mechanism with $\delta=0.05$ and a range of $\epsilon\in[0.1,2]$. To
illustrate the effects of privacy in bounding diameter, we compute the
distance between the exact (non-private) upper bound on diameter in Lemma 3
and the expected (private) upper bound on diameter in Theorem 4. This distance
is shown in the upper plot in Figure 2, and the lower plot shows the analogous
distance for the diameter lower bounds. Figure 3 shows the corresponding
upper- and lower-bound distances for $\rho$.

In all plots, we see that the errors induced by privacy are small. Moreover,
there is a general decrease in the distance between the exact and private
bounds as $\epsilon$ grows. Recalling that a larger $\epsilon$ implies weaker
privacy, these simulations confirm that weaker privacy guarantees result in
smaller differences between the exact and expected bounds for $d$ and $\rho$,
as predicted in Remark 2.

##  VI Guidelines and Examples

Figure 4: The graph $G$ used in Examples 1-4, which is an Erdos-Renyi graph
with $n=50$ and $p=0.40.$

In this section, we develop guidelines for providing private responses to
queries of the Laplacian eigenvalues, as well as a series of examples to
highlight what type of information can be shared via queries of the Laplacian
spectrum, thereby solving Problem 5. Recall that a connected graph
$G\in\mathcal{G}_{n}$ has eigenvalues
$\lambda_{1}\leq\lambda_{2}\leq\dots\leq\lambda_{n},$ where $\lambda_{1}=0$
and $\lambda_{2}>0.$ In this section, we generate private eigenvalues
$\tilde{\lambda}_{i}$ according to a mechanism $W_{\lambda_{i}},$ which we
write as $\tilde{\lambda}_{i}\sim W_{\lambda_{i}}.$

The procedure for sharing one private eigenvalue is straightforward. Given a
graph $G,$ and privacy parameters $\epsilon$ and $\delta,$ we can compute the
eigenvalue $\lambda_{i}$ and the minimum $b$ required for
$(\epsilon,\delta)-$differential privacy, either edge or node, then add noise
with the bounded Laplace mechanism to get the private eigenvalue
$\tilde{\lambda}_{i}$. More care must be taken when answering queries of
multiple eigenvalues or the entire spectrum. Specifically, since we only
consider connected graphs we will always have $\lambda_{1}=0$ and thus there
is no need to privatize it. Furthermore, for $\lambda_{i}$ with
$i\in\\{2,\dots,n\\}$ we can define $n-1$ independent mechanisms that provide
$(\epsilon,\delta)-$differential privacy to each $\lambda_{i}.$ In general,
since we have $n-1$ queries that are each individually
$(\epsilon,\delta)-$differentially private, the privacy level for querying the
entire spectrum is $\big{(}(n-1)\epsilon,(n-1)\delta\big{)}-$differentially
private due to the Composition Theorem [10, Theorem 3.16]. After privatizing
the spectrum, the set $\\{\tilde{\lambda}_{i}\\}_{i=1}^{n}$ is no longer
guaranteed to have the ordering
$\tilde{\lambda}_{1}\leq\dots\leq\tilde{\lambda}_{n}.$ In applications where
the sorting of the private values is critical we can sort the private values
prior to sharing them. Sorting does not harm privacy because it is post-
processing on privatized data, but it will change the statistics of each
$\tilde{\lambda}_{i}.$

For the remainder of this section we provide a series of examples illustrating
the accuracy and utility of the edge privacy mechanism developed in Theorem 1.
In each of the examples, we calculate a metric to quantify accuracy of the
private information, and Table I gives statistical summaries of these
quantities.

Quantity | $\epsilon$ | $n$ | Average % error | Variance of Error
---|---|---|---|---
$\lambda_{2}(G)$ | $0.60$ | $50$ | $8.81\%$ | $0.26$
$Tr(L(G))$ | $0.35$ | $50$ | $5.15\%$ | $0.01$
$K(P)$ | $1.00$ | $50$ | $4.42\%$ | $0.01$
$\phi(G)$ | $2.50$ | $14$ | $9.01\%$ | $0.27$
TABLE I:  Summary of the quantities computed in Section VI. Values were
computed using $M=10^{4}$ private spectrum values. There are no columns for
$A$ and $\delta$ since they are fixed at $A=2$ and $\delta=0.05$ for all
simulations.  Figure 5: Errors in private values of $\lambda_{i}$ for
$i\in\\{2,\dots,5\\}.$ These results illustrate that edge privacy is able to
achieve high accuracy, even under strong privacy.

######  Example 1 (_Accuracy_).

Fix $G\in\mathcal{G}_{50}$ to be the graph shown in Figure 4. Fix
$\epsilon=0.6,\delta=0.05$, and $A=2.$ We generated $M=10^{4}$ private
$\tilde{\lambda}_{i}$’s for each $i\in\\{2,\dots,5\\}$ using an edge privacy
mechanism $W_{\lambda_{i}}^{e}$ with parameter $b_{e}$. Solving for the
minimum $b_{e}$ required for $(0.6,0.05)-$differential privacy gives
$b_{e}=6.386.$ To quantify the accuracy of the private spectrum for a fixed
$\epsilon$ and $\delta$ we analyze $\tilde{\lambda}_{i}-\lambda_{i}$ for
$i\in\\{2,\ldots,5\\}$. A histogram of the accuracy for the $M=10^{4}$ queries
is shown in Figure 5. For each of the eigenvalues, the error in the private
information is heavily concentrated near $0.$ This trend persists for the rest
of the $N=50$ eigenvalues as well as for larger networks with larger values of
$N$. This shows that edge privacy provides accurate spectrum values for large
networks, even with strong privacy.

In Figure 5, it appears that there is a slight bias in the private spectrum
values because the plots are not perfectly symmetric. This bias is made
precise by Theorem 3, and it is a function of the underlying graph $G$ through
its eigenvalues and a function of the privacy parameters $\epsilon$ and
$\delta$ through $b_{e}.$ This bias appears as a result of adding bounded
noise. Specifically, the density we use to generate $\tilde{\lambda}_{i}$ has
a peak at the true value $\lambda_{i}$ but is only supported on the interval
$[0,n]$, which means that the expected value will not be $\lambda_{i}$ unless
$\lambda_{i}=\frac{n}{2}$. Nonetheless, Figure 5 shows that this bias is small
even when using strong privacy. $\triangle$

Figure 6: The empirical mean and variance of the error in
$\tilde{\lambda}_{i}$ for $i\in\\{2,25,48\\}$ and $\epsilon\in[0.1,5].$ For
each $\epsilon,$ $M=10^{4}$ private values were generated to empirically
compute the values of $E[\tilde{\lambda}_{i}-\lambda_{i}]$ and
$\textnormal{Var}[\tilde{\lambda}_{i}-\lambda_{i}].$

######  Example 2 (_The Effect of $\epsilon$_).

Fix $G\in\mathcal{G}_{50}$ to be the graph shown in Figure 4. Fix
$\delta=0.05$ and $A=2.$ Let $\epsilon$ vary and take on values
$\epsilon\in[0.1,5].$ Then for each $\epsilon$, generate $M=10^{4}$ private
$\tilde{\lambda}_{i}$’s for $i\in\\{2,\dots,5\\}$ using an edge privacy
mechanism $W_{\lambda_{i}}^{e}$ with parameter $b_{e}$. For a given $\epsilon$
and eigenvalue $\lambda_{i},$ we quantify the quality of the private
information with the empirical values of $E[\tilde{\lambda}_{i}-\lambda_{i}]$
and $\textnormal{Var}[\tilde{\lambda}_{i}-\lambda_{i}]$ taken over the
$M=10^{4}$ private values. Figure 6 presents the values of
$E[\tilde{\lambda}_{i}-\lambda_{i}]$ and
$\textnormal{Var}[\tilde{\lambda}_{i}-\lambda_{i}]$ for $\epsilon\in[0.1,5].$
Recall that a larger $\epsilon$ implies weaker privacy.

In Figure 6, as $\epsilon$ grows and privacy is weakened, both
$E[\tilde{\lambda}_{i}-\lambda_{i}]$ and
$\textnormal{Var}[\tilde{\lambda}_{i}-\lambda_{i}]$ converge to $0$ relatively
quickly. This trend is consistent across the entire spectrum of the graph
Laplacian. This shows that even with relatively strong privacy, for example
$\epsilon=2$, the private spectra we share are highly accurate. Here we also
we see that under strong privacy, given by small $\epsilon,$ we are sharing
values of $\lambda_{2}$ that are much larger than the true value, and we are
sharing much smaller values of $\lambda_{48}.$ This occurs because of adding
bounded noise and because $\lambda_{2}$ and $\lambda_{48}$ are near the
boundaries of the allowable output range $[0,n].$ This example also
illustrates the loss of accuracy as privacy is strengthened.

Figure 7: Values of $\widetilde{Tr}(L)$ that are computed using private
eigenvalues. For privacy parameters $\epsilon=0.4$ and $\delta=0.05$, $10^{4}$
sets of eigenvalues were generated.

######  Example 3 (_Trace of the Laplacian_).

Fix $G\in\mathcal{G}_{50}$ to be the graph shown in Figure 4. Fix
$\epsilon=0.4$, $\delta=0.05$, and $A=2$. Recall that the trace of a matrix
$R\in\mathbb{R}^{n\times n}$ is given by the sum of its eigenvalues, i.e.,
$Tr(R)=\sum_{i=1}^{n}\lambda_{i}(R).$ Applying this to the graph Laplacian, we
have $Tr(L)=\sum_{i=1}^{n}\lambda_{i}(L).$ The trace of the graph Laplacian
can, for example, be used to compute the average degree of the network as
$d_{avg}=\frac{Tr(L)}{n}.$ Suppose that we do not have access to $G$ or $L(G)$
and we only have the private spectrum values
$\\{\tilde{\lambda}_{i}\\}_{i=1}^{N}$. Then we can use these eigenvalues to
estimate the trace of $L$ as
$\widetilde{Tr}(L)=\sum_{i=1}^{n}\tilde{\lambda}_{i}(L).$ To analyze the
accuracy of this estimate, $M=10^{4}$ sets of private spectra were generated
and used to estimate the trace. In Figure 7 we give a histogram of values of
$\widetilde{Tr}(L)-Tr(L)$ for these trace estimates. The trace of the graph
appearing in Figure 4 is $Tr(L)=736$ and the average estimate over the
$M=10^{4}$ queries was $774.$ We can see in Figure 7 that edge privacy
generally provides accurate estimates of the trace, with the majority of
private trace estimates falling within $\pm 10\%$ of the true trace value.

However, there is a bias in the distribution of private trace estimates, and
we tend to overestimate the trace. To quantify this overestimate, we analyze
$E\left[\widetilde{Tr}(L)-Tr(L)\right].$ Plugging in
$Tr(L)=\sum_{i=1}^{n}\lambda_{i}(L)$ and simplifying gives

$E\left[\widetilde{Tr}(L)-Tr(L)\right]=\sum_{i=1}^{n}E\left[\tilde{\lambda}_{i}(L)\right]-\lambda_{i}(L).$
(28)

Then applying Theorem 3 gives

$E\left[\widetilde{Tr}(L)-Tr(L)\right]=\sum_{i=1}^{n}\frac{1}{2C(\lambda_{i},b)}\left(2\lambda_{i}+be^{-\frac{\lambda_{i}}{b}}\right.\left.-(n+b)e^{-\frac{n-\lambda_{i}}{b}}\right)-\lambda_{i}(L),$
(29)

where $C$ is from Definition 4. In Example 1, there was a small bias in the
values of $\tilde{\lambda}_{i}$ due to using bounded noise to achieve
differential privacy. Here the bias for the trace is larger because we are
summing each $\tilde{\lambda}_{i}$ and the bias is amplified due to summing
biased terms. Nonetheless, accurate trace estimates can still be attained,
even under strong privacy. $\triangle$

Figure 8: The values of $\frac{\widetilde{K}(P)-K(P)}{K(P)}$ in Example 4. The
average value of $\frac{\widetilde{K}(P)-K(P)}{K(P)}$ is $0.2519$. In general,
we overestimate the Kemeny constant of the graph $G$ in Figure 4, but the
majority of results are within $\pm 10\%$ of its true value.

######  Example 4 (_Kemeny’s Constant_).

In network control, network level discrete-time consensus dynamics are
governed by the matrix $P=I-\gamma L(G),$ where $\gamma$ is a step-size which
must obey $\gamma\leq\frac{1}{\max_{i}d_{i}}$ in order to achieve
consensus[35, Theorem 2]. When $G$ is a connected, undirected graph, $P$ can
be interpreted as the transition matrix of a symmetric Markov chain. The
Kemeny constant of a Markov chain is the expected time it takes to transition
from a state $i$ in a Markov chain to another state sampled from its
stationary distribution and can be used to compute the error in consensus
protocols subject to noise [36]. The Kemeny constant of the Markov chain with
transition matrix $P=I-\gamma L(G)$ can be computed as
$K(P)=\sum_{i=2}^{n}\frac{1}{1-\lambda_{i}(P)}$ [37]. Note that
$\lambda_{i}(P)=1-\gamma\lambda_{i}(L)$ and thus
$K(P)=\frac{1}{\gamma}\sum_{i=2}^{n}\frac{1}{\lambda_{i}(L)}.$ Given private
spectrum values we can estimate the Kemeny constant as
$\widetilde{K}(P)=\frac{1}{\gamma}\sum_{i=2}^{n}\frac{1}{\tilde{\lambda}_{i}(L)}.$
We fix $\gamma=\frac{1}{N}$, and with this step-size the graph in Figure 4 has
$K(P)=102.70.$

We now fix $\epsilon=1.0$, $\delta=0.05$, and $A=2$. We generate $M=10^{4}$
private spectra for $G$ in Figure 4 and these values are used to compute
$\widetilde{K}(P).$ To quantify the accuracy of the estimates of the Kemeny
constant, we analyze the relative error $\frac{\widetilde{K}(P)-K(P)}{K(P)}$
whose values for the $M=10^{4}$ private spectra are presented in Figure 8.
Here, we can see that we overestimate the Kemeny constant, but the average
error for these queries is only $4.42\%.$ This shows that sharing the private
spectrum can share relatively accurate information about the Kemeny constant
and thus about discrete-time consensus dynamics while providing edge
differential privacy.

Figure 9: The cycle graph on $n=14$ nodes, $C_{14},$ used in Example 5. Figure
10: The error in the estimate of Cheeger’s constant for the cycle graph in
Figure 9 and the parameters in Example 5. We usually overestimate Cheeger’s
constant using private information. This means we are estimating that the
graph is more connected than it really is, though these estimates are often
fairly accurate.

######  Example 5 (_Cheeger’s Inequality_).

In this example we discuss how private Laplacian spectra can be used to
estimate the isoperimetric number, $\phi(G),$ of a graph $G$. The
isoperimetric number, or the Cheeger constant, is a measure of how connected a
graph is or more specifically how easy it is to disconnect a graph [38]. In
general, the isoperimetric number is NP-hard to compute and Cheeger’s
inequality gives an easily computable upper bound on the isoperimetric number
via
$\phi(G)\leq\phi_{ub}:=\sqrt{\lambda_{2}\left(\max_{i}d_{i}-\lambda_{2}\right)}$
[38, Theorem 4.2].

In this example, we estimate $\phi(G)$ using Cheeger’s inequality for cases in
which we do not have access to $G$ and only have its private Laplacian
spectrum. To estimate $\lambda_{2},$ we use the private value
$\tilde{\lambda}_{2}.$ For $\max_{i}d_{i}$, we estimate this with
$\tilde{d}(G)=\frac{1}{n}\sum_{i=1}^{n}\tilde{\lambda}_{i}.$ Then plugging
these estimates into Cheeger’s inequality, we have the estimate
$\tilde{\phi}(G)=\sqrt{\tilde{\lambda}_{2}\left(2\tilde{d}(G)-\tilde{\lambda}_{2}\right)}.$

Since the isoperimetric number is not feasible to compute for large networks,
we cannot run simulations on the graph appearing in Figure 4 to demonstrate
the accuracy of our estimates. Thus, we fix $G$ to be the cycle or ring graph
on $n$ nodes, $C_{n},$ which has a known Cheeger’s constant of
$\phi(C_{n})=\frac{4}{n}$ [39]. For this example, we fix $n=14$. The graph
$G=C_{14}$ is shown in Figure 9 and $\phi(C_{14})=\frac{2}{7}$. To analyze the
accuracy of using Cheeger’s inequality with private spectra, we generate
$M=10^{4}$ private Laplacian spectra $\\{\tilde{\lambda}_{i}\\}_{i=1}^{n}$ and
use them to privately estimate $\phi(G)$.

Before discussing the accuracy of our estimates we will discuss the accuracy
of the Cheeger’s inequality itself. For $C_{14},$ we have
$\phi(C_{14})=\frac{2}{7}=0.2857$ and plugging in $\lambda_{2}$ and
$\max_{i}d_{i}=2$ into Cheeger’s inequality gives $\phi_{ub}=0.8678.$ This is
more than $3$ times the true value. Thus, to distinguish between errors
inherent to Cheeger’s inequality itself and errors due to privacy, we will
compare our estimate to the upper bound from Cheeger’s inequality,
$\phi_{ub}$.

In Figure 10, we show the accuracy of the resulting estimates given by
$\frac{\tilde{\phi}(G)-\phi_{ub}}{\phi_{ub}}$ for $10^{4}$ queries satisfying
$(2.5,0.05)-$differential privacy. Here, we typically over estimate Cheeger’s
constant. This means that we are estimating that the graph is more connected
than it truly is. Comparing to the non-private Cheeger’s inequality upper
bound given by $\phi_{ub}$, the use of private spectra in computations results
in a slightly looser bound on average. However the estimates are relatively
accurate with an average normalized error of $9.01\%$, with a variance of only
$0.27.$ Overall, this example shows that using private spectrum information to
estimate the isoperimetric number is relatively accurate and does not have
much more error than when true spectrum values are used. $\triangle$

##  VII Conclusions

This paper presented two differential privacy mechanisms for edge and node
privacy of the spectra of graph Laplacians of unweighted, undirected graphs.
Bounded noise was used to provide private values that are still accurate, and
the private values of Laplacian spectrum were shown to give accurate estimates
of the diameter and mean distance of a graph, the trace of the Laplacian, the
Kemeny constant, and Cheeger’s inequality. Future work includes the
development of new privacy mechanisms for other algebraic graph properties.

## References

  * [1] Wei Ren, R. W. Beard, and E. M. Atkins, “A survey of consensus problems in multi-agent coordination,” in _Proceedings of the 2005, American Control Conference, 2005._ , 2005.
  * [2] J. Scott, “Social network analysis,” _Sociology_ , vol. 22, no. 1, pp. 109–127, 1988.
  * [3] M. D. Shirley and S. P. Rushton, “The impacts of network topology on disease spread,” _Eco. Complexity_ , vol. 2, no. 3, pp. 287–299, 2005.
  * [4] Y. Zheng, L. Wang, and Y. Zhu, “Consensus of heterogeneous multi-agent systems,” vol. 5, no. 16, pp. 1881–1888.
  * [5] P. Van Mieghem, J. Omic, and R. Kooij, “Virus spread in networks,” _IEEE/ACM Transactions on Networking_ , vol. 17, no. 1, pp. 1–14, 2009.
  * [6] S. Freitas and D. H. Chau, “Evaluating graph vulnerability and robustness using tiger,” 2020.
  * [7] S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith, “Analyzing graphs with node differential privacy,” in _Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography_. Springer-Verlag, 2013, p. 457–476.
  * [8] V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev, “Private analysis of graph structure,” _ACM Trans. Database Syst._ , vol. 39, no. 3, 2014.
  * [9] S. P. Kasiviswanathan and A. Smith, “On the ’semantics’ of differential privacy: A bayesian formulation,” _Journal of Privacy and Confidentiality_ , vol. 6, no. 1, Jun. 2014.
  * [10] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” vol. 9, no. 3, pp. 211–407.
  * [11] W.-Y. Day, N. Li, and M. Lyu, “Publishing graph degree distribution with node differential privacy,” in _Proceedings of the 2016 International Conference on Management of Data_ , 2016, p. 123–138.
  * [12] E. Shen and T. Yu, “Mining frequent graph patterns with differential privacy,” in _Proceedings of the 19th ACM International Conference on Knowledge Discovery and Data Mining_ , 2013, pp. 545–553.
  * [13] X. Ding, X. Zhang, Z. Bao, and H. Jin, “Privacy-preserving triangle counting in large graphs,” in _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_. Association for Computing Machinery, 2018, p. 1283–1292.
  * [14] M. Hay, C. Li, G. Miklau, and D. Jensen, “Accurate estimation of the degree distribution of private networks,” in _2009 Ninth IEEE International Conference on Data Mining_ , 2009, pp. 169–178.
  * [15] C. Task and C. Clifton, “A guide to differential privacy theory in social network analysis,” in _International Conference on Advances in Social Networks Analysis and Mining_ , 2012, pp. 411–417.
  * [16] N. M. M. de Abreu, “Old and new results on algebraic connectivity of graphs,” _Linear Algebra and its Applications_ , vol. 423, no. 1, pp. 53–73, 2007.
  * [17] V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev, “Private analysis of graph structure,” _Proceedings of the VLDB Endowment_ , vol. 4, no. 11, pp. 1146–1157, 2011.
  * [18] C. Hawkins and M. Hale, “Differentially private formation control,” in _2020 59th IEEE Conference on Decision and Control (CDC)_ , 2020.
  * [19] P. Gohari, M. Hale, and U. Topcu, “Privacy-preserving policy synthesis in markov decision processes,” in _2020 59th IEEE Conference on Decision and Control (CDC)_ , 2020.
  * [20] P. Gohari, B. Wu, C. Hawkins, M. Hale, and U. Topcu, “Differential privacy on the unit simplex via the dirichlet mechanism,” _IEEE Transactions on Information Forensics and Security_ , vol. 16, 2021.
  * [21] J. Cortés, G. E. Dullerud, S. Han, J. Le Ny, S. Mitra, and G. J. Pappas, “Differential privacy in control and network systems,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 4252–4272.
  * [22] M. Fiedler, “Algebraic connectivity of graphs,” vol. 23.
  * [23] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” _IEEE Transactions on Automatic Control_ , vol. 49, no. 9, pp. 1520–1533, 2004.
  * [24] W. Ren and E. Atkins, “Distributed multi-vehicle coordinated control via local information exchange,” _International Journal of Robust and Nonlinear Control_ , vol. 17, pp. 1002–1033, 2007.
  * [25] M. C. De Gennaro and A. Jadbabaie, “Decentralized control of connectivity for multi-agent systems,” in _Proceedings of the 45th IEEE Conference on Decision and Control_ , 2006, pp. 3628–3633.
  * [26] A. Nedić, A. Olshevsky, and W. Shi, _Decentralized Consensus Optimization and Resource Allocation_ , 2018, pp. 247–287.
  * [27] N. Holohan, S. Antonatos, S. Braghin, and P. Mac Aonghusa, “The bounded laplace mechanism in differential privacy,” _arXiv preprint arXiv:1808.10410_ , 2018.
  * [28] Y. Wang, X. Wu, and L. Wu, “Differential privacy preserving spectral graph analysis,” in _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , 2013, pp. 329–340.
  * [29] B. Chen, C. Hawkins, K. Yazdani, and M. Hale, “Edge differential privacy for algebraic connectivity of graphs,” in _2021 60th IEEE Conference on Decision and Control (CDC)_. IEEE, 2021, pp. 2764–2769.
  * [30] M. Fiedler, “A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory,” _Czechoslovak Mathematical Journal_ , vol. 25, no. 4, pp. 619–633, 1975.
  * [31] M. Mesbahi and M. Egerstedt, _Graph Theoretic Methods in Multiagent Networks_ , 2010.
  * [32] P. Gohari, B. Wu, C. Hawkins, M. Hale, and U. Topcu, “Differential privacy on the unit simplex via the dirichlet mechanism,” _IEEE Transactions on Information Forensics and Security_ , vol. 16, pp. 2326–2340, 2021\.
  * [33] M. J. Paldino, W. Zhang, Z. D. Chu, and F. Golriz, “Metrics of brain network architecture capture the impact of disease in children with epilepsy,” _NeuroImage: Clinical_ , vol. 13, pp. 201–208, 2017.
  * [34] B. Mohar, “Eigenvalues, diameter, and mean distance in graphs,” _Graph. Comb._ , 1991.
  * [35] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 215–233, 2007.
  * [36] A. Jadbabaie and A. Olshevsky, “Scaling laws for consensus protocols subject to noise,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 4, pp. 1389–1402, 2018.
  * [37] M. Levene and G. Loizou, “Kemeny’s constant and the random surfer,” _The American mathematical monthly_ , vol. 109, no. 8, pp. 741–745, 2002.
  * [38] B. Mohar, “Isoperimetric numbers of graphs,” _Journal of combinatorial theory, Series B_ , vol. 47, no. 3, pp. 274–291, 1989.
  * [39] C. Godsil and G. F. Royle, _Algebraic graph theory_. Springer Science & Business Media, 2001, vol. 207.
  * [40] D. S. Bernstein, _Matrix mathematics: theory, facts, and formulas_. Princeton university press, 2009.
  * [41] S. Kirkland, “Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality,” _Discrete Mathematics_ , vol. 310, no. 4, pp. 911–921, 2010.

###  -A Proof of Lemma 1

Fix an adjacency parameter $A\in\mathbb{N}$ and consider two graphs
$G,G^{\prime}\in\mathcal{G}_{n}$ such that
$\textnormal{Adj}_{e,A}(G,G^{\prime})=1$. Denote their corresponding graph
Laplacians by $L$ and $L^{\prime}$, and define the matrix $P$ such that
$L^{\prime}=L+P$. Then, we write

$\displaystyle\Delta\lambda_{e,i}$
$\displaystyle=\max_{G,G^{\prime}\in\mathcal{G}_{n}}\left|\lambda_{i}\left(L+P\right)-\lambda_{i}\left(L\right)\right|.$
(30)

We will use the following lemma.

######  Lemma 4 ([40, Theorem 8.4.11]).

Let $A,B\in\mathbb{R}^{n\times n}$ be two symmetric matrices. Then
$\lambda_{i}(A+B)\leq\lambda_{i+j}(A)+\lambda_{n-j}(B).$

Applying Lemma 4 to split up $\lambda_{i}(L+P$), we obtain
$\Delta\lambda_{i,e}\leq\lambda_{i}(L)+\lambda_{n}(P)-\lambda_{i}(L)=\lambda_{n}(P).$
The matrix $P$ encodes the differences between $L$ and $L^{\prime}$ as
follows. For any $i$, if the diagonal entry $P_{ii}=1$, then node $i$ has one
more edge in $G^{\prime}$ than it does in $G$. If $P_{ii}=-1$, then node $i$
has one fewer edge in $G^{\prime}$ than it does in $G$. Other values of
$P_{ii}$ indicate the addition or removal of more edges. Because edge
adjacency allows for the addition or removal of up to $A$ edges, we have
$-A\leq P_{ii}\leq A$.

For off-diagonal entries, $P_{ij}=1$ indicates that $G^{\prime}$ contains the
edge $(i,j)$ and $G$ does not; the converse holds if ${P_{ij}=-1}$. Then, for
any row of $P$, the diagonal entry has absolute value at most $A$, and the
absolute sum of the off-diagonal entries is at most $A$. By Geršgorin’s circle
theorem [40, Fact 4.10.16.], we have $\lambda_{n}(P)\leq 2A.$ $\blacksquare$

###  -B Proof of Lemma 2

Let $G^{-}\in\mathcal{G}^{n-1}$ be the graph obtained by deleting vertex $v$
and its incident edges from $G$. Then

$-1\leq\lambda_{2}(G^{-})-\lambda_{2}(G)\leq n-2.$ (31)

The lower bound in Equation (31) is given in [41, Theorem 1.1] and the upper
bound in [41, Theorem 2.3].

We now analyze the case where we add a node $v$ and arbitrary incident edges
to obtain the graph $G^{+}\in\mathcal{G}^{n+1}.$ Using [41, Theorem 1.1], we
have that

$\lambda_{2}(G^{+})-\lambda_{2}(G)\leq 1.$ (32)

To lower bound $\lambda_{2}(G^{+})-\lambda_{2}(G),$ we can apply the same
methods to obtain the upper bound in Equation (31). Let $K_{n}$ be the
complete graph on $n$ nodes. Suppose that $G\neq K_{n}.$ Then
$\lambda_{2}(G)\leq n-2$ and

$\lambda_{2}(G^{+})-\lambda_{2}(G)\geq\lambda_{2}(G^{+})-(n+2),$ (33)

and since $\lambda_{2}(G^{+})>0$ we have

$\lambda_{2}(G^{+})-\lambda_{2}(G)>2-n$ (34)

for $G\neq K_{n}$.

Now suppose $G=K_{n}$ and we add a node with degree $d\geq 1,$ i.e., we add
$d$ incident edges. It can be shown that $\lambda_{2}(G^{+})=d$ [41, Theorem
2.3], and thus

$\displaystyle\lambda_{2}(G^{+})-\lambda_{2}(G)$ $\displaystyle=d-n$ (35)
$\displaystyle\geq 1-n.$ (36)

With this, we achieve equality when $d=1,$ which occurs when the added node
has one incident edge. Thus, for any $G$ and $G^{+}$ obtained by adding a
node, we combine (32), (34), and (36) to find

$1-n\leq\lambda_{2}(G^{+})-\lambda_{2}(G)\leq 1.$ (37)

Lastly, Equations (31) and (37) imply that for any $G,G^{\prime}$ satisfying
$\textnormal{Adj}_{n}(G,G^{\prime})=1$, we have

$|\lambda_{2}(G^{\prime})-\lambda_{2}(G)|\leq\max\left\\{n-1,n-2,1\right\\},$
(38)

and thus $\Delta\lambda_{2,n}\leq n-1.$ $\blacksquare$

###  -C Proof of Corollary 1

We begin with the condition in Theorem 2 that

$b_{n}\geq\frac{n-1}{\epsilon-\log\left(\frac{2-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}}{1-e^{-\frac{n}{b_{n}}}}\right)-\log(1-\delta)}.$

To find a necessary condition, we must find a lower bound on the right hand
side of the expression. To achieve this, we focus on the argument of the log
first. We note that if

$\frac{2-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}}{1-e^{-\frac{n}{b_{n}}}}>1,$
(39)

then the $\log$ term will be positive and we can eliminate it from the
denominator to obtain the desired bound.

To show this positivity we begin with the fact that $1>e^{-\frac{1}{b_{n}}}$
and $1-e^{-\frac{n-1}{b_{n}}}>0$ for any $n\geq 2$ and $b_{n}>0$. Dividing the
first inequality by $1-e^{-\frac{n-1}{b_{n}}}$ gives

$\displaystyle\frac{1}{1-e^{-\frac{n-1}{b_{n}}}}$
$\displaystyle>\frac{e^{-\frac{1}{b_{n}}}}{1-e^{-\frac{n-1}{b_{n}}}}.$ (40)

We rearrange this and manipulate the inequality further to find

$\displaystyle 1-e^{-\frac{n-1}{b_{n}}}$
$\displaystyle>e^{-\frac{1}{b_{n}}}(1-e^{-\frac{n-1}{b_{n}}})$ (42)
$\displaystyle 1-e^{-\frac{n-1}{b_{n}}}$
$\displaystyle>e^{-\frac{1}{b_{n}}}-e^{-\frac{n}{b_{n}}}$ (43) $\displaystyle
1-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}$
$\displaystyle>-e^{-\frac{n}{b_{n}}}$ (44) $\displaystyle
2-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}$
$\displaystyle>1-e^{-\frac{n}{b_{n}}}$ (45)
$\displaystyle\frac{2-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}}{1-e^{-\frac{n}{b_{n}}}}$
$\displaystyle>1.$ (46)

This implies that
$-\log\left(\frac{2-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}}{1-e^{-\frac{n}{b_{n}}}}\right)<0$,
which gives us

$\frac{n-1}{\epsilon-\log\left(\frac{2-e^{-\frac{n-1}{b_{n}}}-e^{-\frac{1}{b_{n}}}}{1-e^{-\frac{n}{b_{n}}}}\right)-\log(1-\delta)}>\frac{n-1}{\epsilon-\log(1-\delta)}.$

Thus, choosing $b_{n}$ according to
$b_{n}>\frac{n-1}{\epsilon-\log(1-\delta)}$ is necessary to satisfy
$(\epsilon,\ \delta)$-node differential privacy. $\blacksquare$

###  -D Proof of Corollary 2

Following the proof of Corollary 1, we show that the argument of the $\log$ in
Theorem 1 is larger than $1.$ We begin with $1>e^{-\frac{2A}{b}}$ and follow a
similar sequence of steps to Corollary 1:

$\displaystyle 1$ $\displaystyle>e^{-\frac{2A}{b}}$ (47) $\displaystyle
1-e^{-\frac{n-2A}{b}}$
$\displaystyle>e^{-\frac{2A}{b}}\left(1-e^{-\frac{n-2A}{b}}\right)$ (48)
$\displaystyle 1-e^{-\frac{n-2A}{b}}$
$\displaystyle>e^{-\frac{2A}{b}}-e^{-\frac{n}{b}}$ (49) $\displaystyle
2-e^{-\frac{2A}{b}}-e^{-\frac{n-2A}{b}}$ $\displaystyle>1-e^{-\frac{n}{b}}$
(50)
$\displaystyle\frac{2-e^{-\frac{2A}{b}}-e^{-\frac{n-2A}{b}}}{1-e^{-\frac{n}{b}}}$
$\displaystyle>1.$ (51)

Thus, by an argument similar to that in Corollary 1, we find that

$b_{e}>\frac{2A}{\epsilon-\log(1-\delta)}$ (52)

is a necessary condition for the satisfaction of $(\epsilon,\delta)$-edge
differential privacy. $\blacksquare$

###  -E Proof of Theorem 3

We first compute $E[\tilde{\lambda}_{i}]$ as

$\displaystyle E\left[\tilde{\lambda}_{i}\right]$
$\displaystyle=\frac{1}{C(\lambda_{i},b_{e})}\frac{1}{2b_{e}}\int_{0}^{n}xe^{-\frac{\left|x-\lambda_{i}\right|}{b_{e}}}dx$
(53)
$\displaystyle=\frac{1}{C(\lambda_{i},b_{e})}\frac{1}{2b_{e}}\left(\int_{0}^{\lambda_{i}}xe^{-\frac{\lambda_{i}-x}{b_{e}}}dx+\int_{\lambda_{i}}^{n}xe^{-\frac{x-\lambda_{i}}{b_{e}}}dx\right)$
(54)
$\displaystyle=\frac{1}{2C(\lambda_{i},b_{e})}\left(2\lambda_{i}+b_{e}e^{-\frac{\lambda_{i}}{b_{e}}}-b_{e}e^{-\frac{n-\lambda_{i}}{b_{e}}}-ne^{-\frac{n-\lambda_{i}}{b_{e}}}\right)$
(55)
$\displaystyle=\frac{1}{2C(\lambda_{i},b_{e})}\left(2\lambda_{i}+b_{e}e^{-\frac{\lambda_{i}}{b_{e}}}-(n+b_{e})e^{-\frac{n-\lambda_{i}}{b_{e}}}\right).$
(56)

With (56) we can compute $E\left[\tilde{\lambda}_{i}-\lambda_{i}\right]$ as

$\displaystyle E\left[\tilde{\lambda}_{i}-\lambda_{i}\right]$
$\displaystyle=E\left[\tilde{\lambda}_{i}\right]-\lambda_{i}$ (57)
$\displaystyle=\frac{1}{2C(\lambda_{i},b_{e})}\left(2\lambda_{i}+b_{e}e^{-\frac{\lambda_{i}}{b_{e}}}-(n+b_{e})e^{-\frac{n-\lambda_{i}}{b_{e}}}\right)-\lambda_{i}.$
(58)

$\blacksquare$

###  -F Proof of Theorem 4

Since both lower bounds are convex functions with respect to $\lambda_{2}>0$,
we can use Jensen’s inequality and we have

$\displaystyle E[\tilde{d}]\geq
E[\underline{d}(\tilde{\lambda}_{2})]=E\left[\frac{4}{n\tilde{\lambda}_{2}}\right]\geq\frac{4}{nE[\tilde{\lambda}_{2}]}$
(59) $\displaystyle\begin{multlined}E[\tilde{\rho}]\geq
E[\underline{\rho}(\tilde{\lambda_{2}})]=E\left[\frac{2}{(n-1)\tilde{\lambda}_{2}}+\frac{n-2}{2(n-1)}\right]\\\
\geq\frac{2}{(n-1)E[\tilde{\lambda}_{2}]}+\frac{n-2}{2(n-1)}.\end{multlined}E[\tilde{\rho}]\geq
E[\underline{\rho}(\tilde{\lambda_{2}})]=E\left[\frac{2}{(n-1)\tilde{\lambda}_{2}}+\frac{n-2}{2(n-1)}\right]\\\
\geq\frac{2}{(n-1)E[\tilde{\lambda}_{2}]}+\frac{n-2}{2(n-1)}.$ (62)

The value of $E[\tilde{\lambda}_{2}]$ can be computed as

$\displaystyle E[\tilde{\lambda}_{2}]$
$\displaystyle=\frac{1}{C_{\lambda_{2}}(b)}\frac{1}{2b}\int_{0}^{n}xe^{-\frac{|x-\lambda_{2}|}{b}}dx$
$\displaystyle=\frac{1}{C_{\lambda_{2}}(b)}\frac{1}{2b}\left(\int_{0}^{\lambda_{2}}xe^{-\frac{\lambda_{2}-x}{b}}dx+\int_{\lambda_{2}}^{n}xe^{-\frac{x-\lambda_{2}}{b}}dx\right)$
$\displaystyle=\frac{1}{2C_{\lambda_{2}}(b)}\left(2\lambda_{2}+be^{-\frac{\lambda_{2}}{b}}-be^{-\frac{n-\lambda_{2}}{b}}-ne^{-\frac{n-\lambda_{2}}{b}}\right).$

We next compute the expectation term
$E\left[\frac{1}{\sqrt{\tilde{\lambda}_{2}}}\right]$ as

$\displaystyle E\left[\frac{1}{\sqrt{\tilde{\lambda}_{2}}}\right]$
$\displaystyle=\frac{1}{C_{\lambda_{2}}(b)}\frac{1}{2b}\int_{0}^{n}\frac{1}{\sqrt{x}}e^{-\frac{|x-\lambda_{2}|}{b}}dx$
$\displaystyle=\frac{1}{C_{\lambda_{2}}(b)}\frac{1}{2b}\left(\int_{0}^{\lambda_{2}}\frac{1}{\sqrt{x}}e^{-\frac{\lambda_{2}-x}{b}}dx+\int_{\lambda_{2}}^{n}\frac{1}{\sqrt{x}}e^{-\frac{x-\lambda_{2}}{b}}dx\right)$
$\displaystyle=\frac{1}{C_{\lambda_{2}}(b)}\frac{1}{2b}\left(\sqrt{\pi}\sqrt{b}e^{-\frac{\lambda_{2}}{b}}\left(\textrm{erfi}\left(\sqrt{\frac{\lambda_{2}}{b}}\right)\right)+\sqrt{b}e^{\frac{\lambda_{2}}{b}}\left(\Gamma\left(\frac{1}{2},\frac{n}{b}\right)-\Gamma\left(\frac{1}{2},\frac{\lambda_{2}}{b}\right)\right)\right).$

Then we can find the desired upper bounds by applying the linearity of
expectation. $\blacksquare$