# Private Graphon Estimation for Sparse Graphs

arXiv: https://arxiv.org/abs/1506.06162 · HTML: https://mlsanity.com/paper/1506.06162/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2015.

## Built on by (most cited first, 17 of 17)

- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Asymptotics of Network Embeddings Learned via Subsampling](https://mlsanity.com/paper/2107.02363/) (2021)
- [Scalable Implicit Graphon Learning](https://mlsanity.com/paper/2410.17464/) (2024)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [Privacy-Preserving Community Detection for Locally Distributed Multiple Networks](https://mlsanity.com/paper/2306.15709/) (2023)
- [Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust](https://mlsanity.com/paper/2405.16663/) (2024)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphs](https://mlsanity.com/paper/2311.10610/) (2023)
- [Asymptotics of ℓ2 Regularized Network Embeddings](https://mlsanity.com/paper/2201.01689/) (2022)
- [It's My Data Too: Private ML for Datasets with Multi-User Training Examples](https://mlsanity.com/paper/2503.03622/) (2025)
- [Low-Complexity and Consistent Graphon Estimation from Multiple Networks](https://mlsanity.com/paper/2603.15578/) (2026)
- [Differentially Private Modeling of Disease Transmission within Human Contact Networks](https://mlsanity.com/paper/2604.07493/) (2026)

## Abstract (arXiv)

We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive information of individual members. Given a sparse input graph G, our algorithms output a node-differentially-private nonparametric block model approximation. By node-differentially-private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges. If G is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon W, our model guarantees consistency, in the sense that as the number of vertices tends to infinity, the output of our algorithm converges to W in an appropriate version of the L2 norm. In particular, this means we can estimate the sizes of all multi-way cuts in G. Our results hold as long as W is bounded, the average degree of G grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate. We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results.