An official website of the United States government
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.
more »
« less
Edge Differential Privacy for Algebraic Connectivity of Graphs
Graphs are the dominant formalism for modeling multi-agent systems. The algebraic connectivity of a graph is particularly important because it provides the convergence rates of consensus algorithms that underlie many multi-agent control and optimization techniques. However, sharing the value of algebraic connectivity can inadvertently reveal sensitive information about the topology of a graph, such as connections in social networks. Therefore, in this work we present a method to release a graph’s algebraic connectivity under a graph-theoretic form of differential privacy, called edge differential privacy. Edge differential privacy obfuscates differences among graphs’ edge sets and thus conceals the absence or presence of sensitive connections therein. We provide privacy with bounded Laplace noise, which improves accuracy relative to conventional unbounded noise. The private algebraic connectivity values are analytically shown to provide accurate estimates of consensus convergence rates, as well as accurate bounds on the diameter of a graph and the mean distance between its nodes. Simulation results confirm the utility of private algebraic connectivity in these contexts.
more »
« less
- Award ID(s):
- 1943275
- PAR ID:
- 10394644
- Date Published:
- Journal Name:
- Proceedings of the 2021 60th IEEE Conference on Decision and Control (CDC)
- Page Range / eLocation ID:
- 2764 to 2769
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)As multi-agent systems proliferate, there is in-creasing demand for coordination protocols that protect agents’ sensitive information while allowing them to collaborate. To help address this need, this paper presents a differentially private formation control framework. Agents’ state trajectories are protected using differential privacy, which is a statistical notion of privacy that protects data by adding noise to it. We provide a private formation control implementation and analyze the impact of privacy upon the system. Specifically, we quantify tradeoffs between privacy level, system performance, and connectedness of the network’s communication topology. These tradeoffs are used to develop guidelines for calibrating privacy in terms of control theoretic quantities, such as steady-state error, without requiring in-depth knowledge of differential privacy. Additional guidelines are also developed for treating privacy levels and network topologies as design parameters to tune the network’s performance. Simulation results illustrate these tradeoffs and show that strict privacy is inherently compatible with strong system performance.more » « less
-
We consider a class of multi-agent cooperative consensus optimization problems with local nonlinear convex constraints where only those agents connected by an edge can directly communicate, hence, the optimal consensus decision lies in the intersection of these private sets. We develop an asynchronous distributed accelerated primal-dual algorithm to solve the considered problem. The proposed scheme is the first asynchronous method with an optimal convergence guarantee for this class of problems, to the best of our knowledge. In particular, we provide an optimal convergence rate of $$\mathcal O(1/K)$$ for suboptimality, infeasibility, and consensus violation.more » « less
-
We establish average consensus on graphs with dynamic topologies prescribed by evolutionary games among strategic agents. Each agent possesses a private reward function and dynamically decides whether to create new links and/or whether to delete existing ones in a selfish and decentralized fashion, as indicated by a certain randomized mechanism. This model incurs a time-varying and state-dependent graph topology for which traditional consensus analysis is not applicable. We prove asymptotic average consensus almost surely and in mean square for any initial condition and graph topology. In addition, we establish exponential convergence in expectation. Our results are validated via simulation studies on random networks.more » « less
-
The process of data mining with differential privacy produces results that are affected by two types of noise: sampling noise due to data collection and privacy noise that is designed to prevent the reconstruction of sensitive information. In this paper, we consider the problem of designing confidence intervals for the parameters of a variety of differentially private machine learning models. The algorithms can provide confidence intervals that satisfy differential privacy (as well as the more recently proposed concentrated differential privacy) and can be used with existing differentially private mechanisms that train models using objective perturbation and output perturbation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CDC45484.2021.9683306
