# Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2018.

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

- [Conformal Prediction for Network-Assisted Regression](https://mlsanity.com/paper/2302.10095/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Modeling and Correcting Bias in Sequential Evaluation](https://mlsanity.com/paper/2205.01607/) (2022)
- [Fitting Low-rank Models on Egocentrically Sampled Partial Networks](https://mlsanity.com/paper/2303.11230/) (2023)
- [A Deep Learning Method for Optimal Investment Under Relative Performance Criteria Among Heterogeneous Agents](https://mlsanity.com/paper/2402.07365/) (2024)
- [Estimating Dyadic Treatment Effects with Unknown Confounders](https://mlsanity.com/paper/2405.16547/) (2024)
- [Network-based Neighborhood regression](https://mlsanity.com/paper/2407.04104/) (2024)

## Abstract (arXiv)

This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection, and hypothesis testing. For each problem, we review state-of-the-art results in the literature followed by general principles behind the optimal procedures that lead to minimax estimation and testing. This allows us to connect problems in network analysis to other statistical inference problems from a general perspective.