# Co-clustering of Nonsmooth Graphons

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2015.

## 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)
- [Distribution-Free Matrix Prediction Under Arbitrary Missing Pattern](https://mlsanity.com/paper/2305.11640/) (2023)

## Abstract (arXiv)

Performance bounds are given for exploratory co-clustering/ blockmodeling of bipartite graph data, where we assume the rows and columns of the data matrix are samples from an arbitrary population. This is equivalent to assuming that the data is generated from a nonsmooth graphon. It is shown that co-clusters found by any method can be extended to the row and column populations, or equivalently that the estimated blockmodel approximates a blocked version of the generative graphon, with estimation error bounded by OP(n-1/2). Analogous performance bounds are also given for degree-corrected blockmodels and random dot product graphs, with error rates depending on the dimensionality of the latent variable space.