# Reducing Crowdsourcing to Graphon Estimation, Statistically

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2017.

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

- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [Unsupervised Crowdsourcing with Accuracy and Cost Guarantees](https://mlsanity.com/paper/2207.01988/) (2022)
- [Matrix Estimation for Individual Fairness](https://mlsanity.com/paper/2302.02096/) (2023)
- [Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing](https://mlsanity.com/paper/2301.00006/) (2022)
- [Spectral Clustering for Crowdsourcing with Inherently Distinct Task Types](https://mlsanity.com/paper/2302.07393/) (2023)

## Abstract (arXiv)

Inferring the correct answers to binary tasks based on multiple noisy answers in an unsupervised manner has emerged as the canonical question for micro-task crowdsourcing or more generally aggregating opinions. In graphon estimation, one is interested in estimating edge intensities or probabilities between nodes using a single snapshot of a graph realization. In the recent literature, there has been exciting development within both of these topics. In the context of crowdsourcing, the key intellectual challenge is to understand whether a given task can be more accurately denoised by aggregating answers collected from other different tasks. In the context of graphon estimation, precise information limits and estimation algorithms remain of interest. In this paper, we utilize a statistical reduction from crowdsourcing to graphon estimation to advance the state-of-art for both of these challenges. We use concepts from graphon estimation to design an algorithm that achieves better performance than the em majority voting scheme for a setup that goes beyond the em rank one models considered in the literature. We use known explicit lower bounds for crowdsourcing to provide refined lower bounds for graphon estimation.