# Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 49 references that are in the map.
- First posted on arXiv 7 Apr 2023.

## Builds on (most cited first, 17 of 17)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Stochastic blockmodel approximation of a graphon: Theory and consistent estimation](https://mlsanity.com/paper/1311.1731/) (2013)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Network histograms and universality of blockmodel approximation](https://mlsanity.com/paper/1312.5306/) (2013)
- [A goodness-of-fit test for stochastic block models](https://mlsanity.com/paper/1412.4857/) (2014)
- [Analysis of spectral clustering algorithms for community detection: the general bipartite setting](https://mlsanity.com/paper/1803.04547/) (2018)
- [Convexified Modularity Maximization for Degree-corrected Stochastic Block Models](https://mlsanity.com/paper/1512.08425/) (2015)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [Optimal Estimation and Completion of Matrices with Biclustering Structures](https://mlsanity.com/paper/1512.00150/) (2015)
- [Spectral Thresholds in the Bipartite Stochastic Block Model](https://mlsanity.com/paper/1506.06737/) (2015)
- [Optimal Bipartite Network Clustering](https://mlsanity.com/paper/1803.06031/) (2018)
- [Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing](https://mlsanity.com/paper/1811.06055/) (2018)
- [Sparse network asymptotics for logistic regression](https://mlsanity.com/paper/2010.04703/) (2020)

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

- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Network Learning with Semi-relaxed Gromov-Wasserstein](https://mlsanity.com/paper/2606.02223/) (2026)

## Abstract (arXiv)

Many real-world data sets can be presented in the form of a matrix whose entries correspond to the interaction between two entities of different natures (number of times a web user visits a web page, a student's grade in a subject, a patient's rating of a doctor, etc.). We assume in this paper that the mentioned interaction is determined by unobservable latent variables describing each entity. Our objective is to estimate the conditional expectation of the data matrix given the unobservable variables. This is presented as a problem of estimation of a bivariate function referred to as graphon. We study the cases of piecewise constant and H"older-continuous graphons. We establish finite sample risk bounds for the least squares estimator and the exponentially weighted aggregate. These bounds highlight the dependence of the estimation error on the size of the data set, the maximum intensity of the interactions, and the level of noise. As the analyzed least-squares estimator is intractable, we propose an adaptation of Lloyd's alternating minimization algorithm to compute an approximation of the least-squares estimator. Finally, we present numerical experiments in order to illustrate the empirical performance of the graphon estimator on synthetic data sets.