Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
We give a simple, computationally efficient, and node-differentially-private algorithm for estimating the parameter of an Erdos-Renyi graph---that is, estimating p in a G(n,p)---with near-optimal accuracy. Our algorithm nearly matches the information-theoretically optimal exponential-time algorithm for the same problem due to Borgs et al. (FOCS 2018). More generally, we give an optimal, computationally efficient, private algorithm for estimating the edge-density of any graph whose degree distribution is concentrated on a small interval.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Node Reliability: Approximation, Upper Bounds, and Applications to Network Robustness
This paper discusses the reliability of a graph in which the links are perfectly reliable but the nodes may fail with certain probability p. Calculating graph node reliability is an NP-Hard problem. We introduce an effic…
Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
This article unveils a new relation between the Nishimori temperature parametrizing a distribution P and the Bethe free energy on random Erdos-Renyi graphs with edge weights distributed according to P. Estimating the Nis…
Bayesian InferenceGeneral ClassificationNode ClassificationRelationSharp Threshold for the Frechet Mean (or Median) of Inhomogeneous Erdos-Renyi Random Graphs
We address the following foundational question: what is the population, and sample, Frechet mean (or median) graph of an ensemble of inhomogeneous Erdos-Renyi random graphs? We prove that if we use the Hamming distance t…
Graph Neural Networks for Scalable and Transferable Node Centrality Approximation
Graph Neural Networks (GNNs) provide a learning-based framework for approximating graph quantities that are expensive to compute exactly. This paper investigates GNNs for scalable approximation of betweenness and closene…
Graph Deconvolutional Generation
Graph generation is an extremely important task, as graphs are found throughout different areas of science and engineering. In this work, we focus on the modern equivalent of the Erdos-Renyi random graph model: the graph…
DecoderGraph GenerationGraph Matching