When Do Differentially Private Inputs Protect Graph Shift Operators?
TL;DR
It is shown that the zero placement that limits the privacy loss also raises the floor on the adversary's reconstruction error, and the log-likelihood ratio between the releases of two adjacent topologies is governed by the distances from each zero to the graph frequencies of the two GSOs.
Abstract
We study the differential privacy (DP) of a graph shift operator (GSO) when an analyst observes the output of a graph filter. In particular, we study the setting in which the input signals to the graph filter are drawn from a differentially private distribution. Unlike approaches that perturb the GSO or the filter output, we use the randomness already present in the inputs to protect the GSO. This yields an equivalent level of privacy protection to that of the perturbation methods without adding noise, and thus a better privacy-utility trade-off. We provide an explicit characterization of the privacy loss and its certificate in terms of the zeros of the graph filter. In doing so, we show that the log-likelihood ratio between the releases of two adjacent topologies is governed by the distances from each zero to the graph frequencies of the two GSOs. Then, by uniformly bounding the log-likelihood ratio over the adjacent topologies, we obtain an explicit $(\varepsilon,\delta)$-DP guarantee for Gaussian inputs. We further show, via a Cram\'er--Rao bound, that the zero placement that limits the privacy loss also raises the floor on the adversary's reconstruction error. Finally, empirical validation is performed on a synthetic network of financial exposures, where the largest position a pair can conceal and the accuracy with which it can be sized are collinear across pairs. Both are set by the graph-frequency content of the pair, and the full network becomes recoverable only as the certified budget grows.