Analysis of networks: privacy in Bayesian networks and problems in lattice models

Abstract

This thesis deals with differential privacy in Bayesian inference, probabilistic graphical models and information-theoretic settings. It also studies the expansion property and enumeration problems of certain subgraphs of networks.

The contributions of this thesis fall into three main categories:

(i) We establish results for Bayesian inference, providing a posterior sampling algorithm preserving differential privacy by placing natural conditions on the priors. We prove bounds on the sensitivity of the posterior to training data, which delivers a measure of robustness, from which differential privacy follows within a decision-theoretic framework. We provide bounds on the mechanism's utility and on the distinguishability of datasets. These bounds are complemented by a novel application of Le Cam's method to obtain lower bounds. We also explore inference on probabilistic graphical models specifically, in terms of graph structure. We show how the posterior sampling mechanism lifts to probabilistic graphical models and bound KL-divergence when releasing an empirical posterior based on a modified prior. We develop an alternate approach that uses the Laplace mechanism to perturb posterior parameterisations, and we apply techniques for released marginal tables that maintain consistency in addition to privacy, by adding Laplace noise in the Fourier domain. We also propose a maximum a posteriori estimator that leverages the exponential mechanism.

(ii) We generalize a prior work that considered differential privacy as a trade-off between information leakage and utility in noisy channels. By assuming certain symmetric properties of the graphs induced by the Hamming-1 adjacency relation on datasets, the authors showed the relation between utility and differential privacy. We prove the utility results still hold without any assumption on the structure of induced graphs. Our analysis applies to the graph of datasets induced by any symmetric relation, therefore is applicable to generalized notions of differential privacy.

(iii) In a different direction in graph analysis within statistical mechanics, we discover the relation between graph energy per vertex of a regular lattice and that of its clique-inserted lattice using spectral techniques. We obtain the asymptotic energy per vertex of 3-12-12 and 3-6-24 lattices. We derive the formulae expressing the number of spanning trees and dimer covering of the k-th iterated clique-inserted lattices in terms of those of the original one. We show that new families of expander networks can be constructed from the known ones by clique-insertion. We modify the transfer matrix method and use it to obtain upper and lower bound for the entropy of number independent sets on the 4-8-8 lattice. We show that the boundary conditions have no effect on the entropy constant. We also introduce a random graph model, where we study the annealed entropy of independent set per vertex. We show that the annealed entropy can be computed in terms of the largest eigenvalue (in modulus) of corresponding expected transfer matrix. Experiments suggest that this annealed entropy is highly correlated to the corresponding Shannon entropy.