Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
Preprint
Abstract
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ölder-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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Improved Clustering Algorithms for the Bipartite Stochastic Block ModelIEEE Transactions on Information Theory, 2021
- Optimal graphon estimation in cut distanceProbability Theory and Related Fields, 2018
- Consistency of spectral clustering in stochastic block modelsThe Annals of Statistics, 2015
- Sparse regression learning by aggregation and Langevin Monte-CarloJournal of Computer and System Sciences, 2012
- Consistency of community detection in networks under degree-corrected stochastic block modelsThe Annals of Statistics, 2012
- Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsityMachine Learning, 2008
- Information Theory and Mixing Least-Squares RegressionsIEEE Transactions on Information Theory, 2006
- Clustering with block mixture modelsPattern Recognition, 2003
- Stochastic blockmodels: First stepsSocial Networks, 1983
- Representations for partially exchangeable arrays of random variablesJournal of Multivariate Analysis, 1981